Sidang Tugas Akhir

Dita Sri Wahyuni Manik
g54140008

Penyelesaian Rural Postman Problem pada Graf Campuran Menggunakan Metode Heuristik

Salah satu permasalahan dalam menentukan rute terpendek dengan biaya minimum adalah Rural Postman Problem (RPP). Pada karya ilmiah ini dibahas mengenai mixed RPP (MRPP), dimana representasi graf dari MRPP memiliki dua jenis sisi, yaitu sisi berarah dan sisi tak berarah. Metode yang digunakan adalah metode heuristik konstruktif. Graf yang dihasilkan adalah graf yang balans dan genap sehingga graf tersebut mempunyai sirkuit Euler. Untuk menentukan sirkuit Euler, digunakan algoritme van Aardenne-Ehrenfest-de Bruijn.