Penyelesaian Directed Rural Postman Problem

Abstract

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