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

Firda Nur Rizkiani, Rosmala Sari, Arif Imran

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


Kata Kunci


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

Teks Lengkap:

PDF

Referensi


Golden, B., Raghavan, S., & Wasil, E., (2008). “The Vehicle Routing Problem: Latest Advances and New Challengesâ€. Springer, New York, 43, pp. 01.

Toth, P., & Vigo, D., (2014). “The Vehicle Routing Problem with Time Windowsâ€. Computers & Operations Research, 51, pp. 257-267.

Pujawan, N., & Er, M., (2017), Supply Chain Management (3 ed.), ANDI.

Clarke, G., & Wright, J. W., (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Pointsâ€. Operations Research, 12(4), pp. 568-581.

Pramudita, A. S., (2019). “Usulan Rute Distribusi Sebagai Upaya Mencapai Keunggulan Kompetitif Melalui Efisiensi Biaya Transportasi PT Pos Indonesiaâ€, Jurnal Logistik Bisnis, 09(2), pp. 90–96.

Rizkya, Indah, et al., (2019). “Design of Distribution Routes Using Saving Matrix Method to Minimize Transportation Costâ€, International Conference on Sustainable Engineering and Creative Computing (ICSECC), IEEE, pp. 48-51.

Rohandi, S.M., Imran, A., & Prassetiyo, H., (2014). “Penentuan rute distribusi produk obat menggunakan metode sequential insertion dan Clarke & Wright savings (Studi kasus di PT X bandung)â€, Reka Integra, 2(2).

Suyudi, A., Imran, A., & Susanti, S., (2015).†Usulan Rancangan Rute Pendistribusian Air Galon Hanaang Menggunakan Algoritma Nearest Neighbour dan Local Searchâ€, Reka Integra, 3(4).

Vincent, F. Y., Lin, S. W., Lee, W., & Ting, C. J., (2010). “A Simulated Annealing Heuristic for the Capacitated Location Routing Problemâ€, Computers & Industrial Engineering, 58(2), pp. 288-299.

Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P., (1983). “Optimization by Simulated Annealingâ€, Science, 220(4598), pp. 671-680.

Alsumairat, N., & Alrefaei, M., (2021). “Solving Hybrid-Vehicle Routing Problem using Modified Simulated Annealingâ€, International Journal of Electrical and Computer Engineering, 11(6), pp. 4922–4931.

Ilhan, I., (2020). “A Population based Simulated Annealing Algorithm for Capacitated Vehicle Routing Problemâ€, Turkish Journal of Electrical Engineering and Computer Sciences, 28(3), pp. 1217–1235.

Imran, A., (2013). “A Variable Neighborhood Search-Based Heuristic for The Multi-Depot Vehicle Routing Problemâ€, Jurnal Teknik Industri, 15(2), pp. 95-102.

Imran, A., Luis, M., & Okdinawati, L., (2016). “A Variable Neighborhood Search for The Heterogeneous Fixed Fleet Vehicle Routing Problemâ€, Jurnal Teknologi, 78(9), pp. 53-58.

Vincent, F. Y., Susanto, H., Jodiawan, P., Ho, T. W., Lin, S. W., & Huang, Y. T., (2022). “A Simulated Annealing Algorithm for The Vehicle Routing Problem with Parcel Lockers, IEEE Access, 10, pp. 20764-20782.




DOI: https://doi.org/10.26760/jrh.v7i3.277-288

Refbacks

  • Saat ini tidak ada refbacks.



Alamat redaksi dan tata usaha:

Lembaga Penelitian dan Pengabdian Masyarakat Institut Teknologi Nasional
Fakultas, gedung 14 Lantai 3
Jl. PHH. Mustapa 23 Bandung 40124
Tlp. 022-7272215 Pes. 159, Fax. 022-7202892,
e-mail: hrekayasa@itenas.ac.id


Terindeks:

  


STATISTIK PENGUNJUNG
Flag Counter
 

Lihat Statistik

Jurnal ini terlisensi oleh Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons License