Penyelesaian Masalah Rural Postman Problem pada Graf Campuran dengan Metode Corberan-Marti-Romero

Abstract

Rural Postman Problem (RPP) merupakan permasalahan dalam pencarian rute terpendek dengan biaya minimum dan hanya sebagian sisi atau sisi berarah diperlukan saja yang harus dilewati. Pada karya ilmiah ini dibahas mengenai mixed Rural Postman Problem (MRPP), di mana representasi graf dari MRPP memiliki dua jenis sisi, yaitu sisi berarah dan sisi tak berarah. Metode yang digunakan adalah metode yang dikembangkan oleh Corberan-Marti-Romero. Algoritme yang digunakan yakni algoritme Kruskal untuk menentukan minimum spanning tree dan algoritme van Aardenne-Ehrenfest-de Bruijn untuk menentukan sirkuit Euler. Selain itu, solusi dari masalah minimum cost flow digunakan untuk mengonstruksi graf yang balans dan genap. Contoh aplikasi MRPP dalam karya ilmiah ini adalah penentuan rute pengiriman barang (paket) dengan jarak minimum.