Penyelesaian Directed Rural Postman Problem
View/ Open
Date
2010Author
Nakasumi, Rangga
Hanum, Farida
Bakhtiar, Toni
Metadata
Show full item recordAbstract
Rural Postman Problem (RPP) merupakan masalah penentuan rute optimal dengan syarat ada
rute-rute tertentu yang harus dilewati, sedangkan rute lainnya boleh dilewati. Jika suatu rute
dilewati, maka haruslah dilewati tepat satu kali. Dalam karya ilmiah ini akan dibahas penyelesaian
RPP pada graf berarah atau Directed Rural Postman Problem (DRPP) dengan menggunakan dua
algoritme heuristik, yaitu algoritme Balance & Connect (B&C) dan algoritme Connect & Balance
(C&B). Formulasi masalah transportasi digunakan untuk mengubah graf takbalans menjadi graf
balans. Penentuan path terpendek diselesaikan dengan menggunakan algoritme Dijkstra, dan
penentuan minimum spanning tree diselesaiakan dengan menggunakan Algoritme Prim. Solusi
DRPP dengan menggunakan algoritme B&C dan algoritme C&B berupa sirkuit Euler yang bisa
ditentukan dengan menggunakan algoritme van Aardenne−Ehrenfest & de Bruijn. Contoh aplikasi
yang digunakan dalam karya ilmiah ini adalah penentuan rute optimal antar-jemput padi gilingan
Collections
- UT - Mathematics [1395]