A Simulated Annealing for Heterogenous Fleet Vehicle Routing Problem with Multiple Trips and Pickup-Delivery

Sari

ABSTRAK
Salah satu masalah paling krusial dalam Supply Chain Management (SCM) adalah perancangan jaringan distribusi yang secara signifikan memengaruhi biaya total. Salah satu masalah umum dalam distribusi adalah bagaimana merancang rute kendaraan yang optimal. Masalah ini dikenal sebagai Vehicle Routing Problem (VRP). Sebuah variasi VRP yang dikenal sebagai Heterogeneous Fleet Vehicle Routing Problem with Multiple Trips and Pickup and Delivery (HFVRPMTPD) memiliki karakteristik berikut: jenis kendaraan yang berbeda, perjalanan ganda, dan pengambilan serta pengantaran secara simultan. Penelitian ini membantu dalam menyelesaikan masalah yang dihadapi oleh Perusahaan Distribusi Liquefied Petroleum Gas (LPG) yang mengantarkan dan mengumpulkan tabung gas secara simultan dengan menggunakan jenis kendaraan yang berbeda-beda dan dapat melakukan perjalanan ganda sepanjang waktu operasi. Saat ini, perencanaan rute hanya didasarkan pada pengalaman pengemudi, yang mengakibatkan peningkatan jarak total, dan akhirnya mengarah pada waktu pengiriman yang tidak efisien. Peneliti mengusulkan pendekatan Simulated Annealing (SA) dengan menggunakan Savings Matrix dan Nearest Neighbor untuk mendapatkan solusi awal, dengan tujuan meminimalkan jarak total. Hasil penelitian menunjukkan bahwa rute yang diusulkan memberikan solusi yang lebih baik dalam hal jarak total dibandingkan dengan solusi saat ini dari perusahaan. Analisis sensitivitas terhadap parameter SA juga dilakukan untuk menilai kinerja algoritma yang diusulkan.

Kata kunci: Jaringan Distribusi, Vehicle Routing Problem, Heterogeneous Fleet Vehicle Routing Problem with Multiple Trips and Pickup and Delivery, Savings Matrix, Nearest Neighbor, Simulated Annealing

 

ABSTRACT
One of the most critical issues in Supply Chain Management (SCM) is the design of distribution networks that substantially affects the total cost. Designing optimal vehicle route plan is the most common issue in distribution. This problem is known as Vehicle Routing Problem (VRP). A VRP variant known as Heterogeneous Fleet Vehicle Routing Problem with Multiple Trips and Pickup and Delivery (HFVRPMTPD) involves the following characteristics: heterogenous vehicles, multiple trips, and simultaneous pickup and delivery. This research helps to solve the problems encountered by a Liquefied Petroleum Gas (LPG) Distribution Company which operates by delivering and collecting simultaneously the gas cylinders using heterogenous vehicle in multiple trips throughout the operation time. Currently, the route planning is solely based on the driver’s experience, resulting in increased total distance, and consequently leading to inefficient delivery times. We propose a Simulated Annealing (SA) with the initial solution obtained using Saving Matrix and Nearest Neighbor, aiming at minimizing the total distance. The results indicate that the proposed route provides a better solution in terms of total distance compared to the current solution of the company. Sensitivity analyses of the SA parameter are also conducted to assess the proposed algorithm’s performance.

Keywords: Distribution Networks, Heterogeneous Fleet Vehicle Routing Problem with Multiple Trips and Pickup and Delivery, Savings Matrix, Nearest Neighbor, Simulated Annealing