Ringkasan |
: |
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. Salah satu jenis RPP ialah Stacker Crane Problem (SCP), yaitu RPP pada graf campuran yang harus melewati setiap sisi berarah. SCP dapat diselesaikan menggunakan dua macam algoritme heuristik, yaitu algoritme Largearcs dan algoritme Smallarcs yang dalam langkahlangkah penyelesaian juga memerlukan beberapa algoritme lain. Penentuan path terpendek diselesaikan dengan algoritme Dijkstra, penentuan minimum bipartite matching diselesaikan dengan metode Hungaria, penentuan minimum spanning tree diselesaikan dengan algoritme Prim, dan sirkuit Euler ditentukan dengan algoritme van Aardenne-Ehrenfest & de-Bruijn dan algoritme Fleury. Untuk menyelesaikan masalah SCP perlu dipilih sirkuit Euler terpendek dari dua algoritme heuristik yang digunakan. Contoh aplikasi SCP dalam karya ilmiah ini adalah penentuan rute pengiriman katering dengan jarak minimum. |