Pengembangan heuristik pada kasus heterogeneous vehicle routing problems with time windows and fixed costs

Vehicle routing problem (VRP) adalah model logistik yang bertujuan mencari distribusi rute terbaik dari sekumpulan kendaraan untuk melayani beberapa konsumen. Model ini cukup populer dalam kajian akademis maupun penerapannya di industri sehingga telah dikembangkan dalam berbagai varian, namun varian yang semakin mendekati kondisi riil lapangan sangat kompleks dan menuntut banyak penyederhaan dalam pemodelannya. Pada penelitian ini akan dikembangkan metode heuristik untuk model VRP dengan armada kendaraan heterogen yang memperhatikan kendala waktu dan biaya tetap atau disebut heterogeneous vehicle routing problems with time windows and fixed costs (HVRPTWF). Aplikasi model ini relevan dengan ruang lingkup logistik maritim yang juga digunakan sebagai studi kasus penelitian. Dua metode heuristik dimaksud adalah heuristik load yang bekerja dengan prinsip large-first-small-last dalam pengalokasian permintaan konsumen ke kapal, dan heuristik ray yang bekerja dengan prinsip sweep algorithm dalam pembentukan rute besar. Kedua metode akan dikombinasikan dengan prosedur pemecahan rute Split dan algoritma local search dari penelitian lain untuk memperbaiki rute awal yang dihasilkan. Solusi optimal dengan pendekatan programa linier, dua metode heuristik, dan metode random akan saling dibandingkan untuk melihat kinerjanya dalam hal optmalitas dan waktu komputasi. Hasil eksperimen menunjukkan heuristik load memiliki optimality gap terkecil terhadap solusi optimal dibandingkan dua metode lainnya dengan waktu komputasi tercepat. Sebaliknya, metode random dari literatur lain selain tidak efektif dalam meminimumkan total biaya, juga tidak efisien dalam hal waktu komputasi akibat seringnya terjadi infeasible splitting.