Optimization of LPG Distribution on VRP Using Cheapest Insertion Heuristics Algorithms and Dynamic Programming
DOI:
10.29303/jm.v7i3.9694Published:
2025-07-29Downloads
Abstract
Determining the most efficient distribution route often encounters difficulties, especially at the LPG gas agency of PT. Cahaya Mentari Bumi Perkasa, where routes are primarily selected based only on the drivers' intuition. The firm manages 35 distribution sites with 3 fleets, each capable of holding 560 cylinders. This study seeks to identify the most efficient distribution route and assess the distribution costs of the company's existing route in comparison to the proposed route, utilizing the Vehicle Routing Problem (VRP) model, constrained by vehicle capacity and fluctuating demand, known as the Capacitated Vehicle Routing Problem (CVRP). The methodology employs the Cheapest Insertion Heuristics (CIH) algorithm to generate the first solution and utilizes Dynamic Programming (DP) as the precise technique for optimal route refinement. The findings indicate that employing Dynamic Programming to enhance the Cheapest Insertion Heuristics method effectively optimizes distribution routes, resulting in roughly 28% reduction in trip distance, 8.2% decrease in journey time, and 19,9% reduction in distribution expenses. The improvement decreased the number of trips from 9 to 8, resulting in enhanced fleet utilization.
Keywords:
Cheapest Insertion Heuristics Algorithm; Dynamic Programming; VRPReferences
Abadi Nugroho, A. N. (2020). Penerapan Metode Haversine Formula Untuk Penentuan Titik Kumpul pada Aplikasi Tanggap Bencana. Metik Jurnal, 4(2), 69–75. https://doi.org/10.47002/metik.v4i2.190
Adhi, A., Santosa, B., & Siswanto, N. (2019). A new metaheuristics for solving vehicle routing problem: Partial Comparison Optimization. IOP Conference Series: Materials Science and Engineering, 598(1). https://doi.org/10.1088/1757-899X/598/1/012023
Akmal, M. (2018). Penyelesaian Traveling Salesman Problem Dengan Dynamic Programming.
Ardiansyah, Mahendra, G. S., & Rahayu, P. W. (2024). Buku Ajar Sistem Pendukung Keputusan (1st ed.). PT. Sonpedia Publishing Indonesia. https://books.google.co.id/books/about/Buku_Ajar_Sistem_Pendukung_Keputusan.html?id=V_T-EAAAQBAJ&redir_esc=y
Aristi, G. (2015). Perbandingan Algoritma Greedy, Algoritma Cheapest Insertion Heuristics Dan Dynamic Programming Dalam Penyelesaian Travelling Salesman Problem. Paradigma, XVI(2), 52–58.
Chandra, A., & Setiawan, B. (2018). Optimasi Jalur Distribusi dengan Metode Vehicle Routing Problem (VRP). Jurnal Manajemen Transportasi & Logistik (JMTRANSLOG), 5(2), 105. https://doi.org/10.54324/j.mtl.v5i2.233
Elsa, A., Panjaitan, A. M., & Sipayung, T. N. (2023). Penerapan Program Dinamik dalam Menentukan Jalur Perjalanan Optimum dengan Prosedur Backward Recursive Equation. Journal on Education, 5(2), 4217–4225. https://doi.org/10.31004/joe.v5i2.1133
Fikri Akbar L, & Rosnani Ginting. (2019). Dynamic Programming dalam Penyelesaian Masalah Penjadwalan. Talenta Conference Series: Energy and Engineering (EE), 2(3). https://doi.org/10.32734/ee.v2i3.751
Gunawan, G., & Andriani, Y. (2023). Penerapan Algoritma Dynamic Programming Dalam Pencarian Judul Skripsi. J-SISKO TECH (Jurnal Teknologi Sistem Informasi Dan Sistem Komputer TGD), 6(1), 67. https://doi.org/10.53513/jsk.v6i1.7388
Hignasari, L. V. (2020). Komparasi Algoritma Cheapest Insertion Heuristic (CIH) Dan Greedy Dalam Optimasi Rute Pendistribusian Barang. Jurnal Ilmiah Vastuwidya, 2, 31–39. https://doi.org/10.47532/jiv.v2i2.87
Indrianti, N., Leuveano, R. A. C., Abdul-Rashid, S. H., & Ridho, M. I. (2025). Green Vehicle Routing Problem Optimization for LPG Distribution: Genetic Algorithms for Complex Constraints and Emission Reduction. Sustainability (Switzerland), 17(3). https://doi.org/10.3390/su17031144
Kendal, K. (2022). Optimalisasi Rute Distribusi Matras Pada Penyelesaian Capacitated Vehicle Routing Problem Dengan Metode Algoritma Genetika. Jurnal Cakrawala Ilmiah, 4(1), 1–8.
Khadafi, S., & Saputri, O. R. (2023). Implementasi Algoritma Cheapest Insertion Heuristics Berbasiskan Android Dan Google Maps Pada Pt.Xyz Implementation Cheapest Insertion Heuristics Algorithm Based on Android and Google Maps At Pt. Xyz. Jurnal Ilmiah NERO, 8(1), 9–20.
Miftahuddin, Y., Umaroh, S., & Karim, F. R. (2020). Perbandingan Metode Perhitungan Jarak Euclidean, Haversine, Dan Manhattan Dalam Penentuan Posisi Karyawan. Jurnal Tekno Insentif, 14(2), 69–77. https://doi.org/10.36787/jti.v14i2.270
Putra, R. H. D., Sujiani, H., & Safriadi, N. (2015). Penerapan Metode Haversine Formula Pada Sistem Informasi Geografis Pengukuran Luas Tanah. Jurnal Sistem Dan Teknologi Informasi (JUSTIN), 1(1), 1–6.
Rizki Putra Sinaga, & Faridawaty Marpaung. (2023). Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem. Jurnal Riset Rumpun Matematika Dan Ilmu Pengetahuan Alam, 2(2), 238–247. https://doi.org/10.55606/jurrimipa.v2i2.1614
Singal, L., & Rindengan, Y. D. Y. (2021). Comparative Analysis of Google Maps Coordinates Points and Professional GPS Tools in Manado City. Jurnal Teknik Informatika, 16(2), 157–164. https://ejournal.unsrat.ac.id/index.php/informatika/article/view/33878/32394
Soenandi, I. A., Joice, J., & Marpaung, B. (2019). Optimasi Capacitated Vehicle Routing Problem with Time Windows dengan Menggunakan Ant Colony Optimization. Jurnal Sistem Dan Manajemen Industri, 3(1), 59. https://doi.org/10.30656/jsmi.v3i1.1469
Soimun, A., Made, N., Puritasari, M., Diva, P., & Sadri, A. (2025). Optimization of the Capacitated Vehicle Routing Problem ( CVRP ) and Distribution Costs in a Drinking Water Company. Jurnal Penelitian Sekolah Tinggi Transportasi Darat, 16(1), 1–16. https://doi.org/10.55511/jpsttd.v16i1.722
Tarnoto, T., Wahyudin, W., & Fitriani, R. (2021). Optimasi rute distribusi gas LPG 3 kg menggunakan metode tabu search pada PT. SPI. Journal Industrial Servicess, 7(1), 43. https://doi.org/10.36055/jiss.v7i1.12010
Tegar, N. (2019). Panduan Lengkap Manajemen Distribusi. Anak Hebat Indonesia. https://books.google.co.id/books/about/Panduan_Lengkap_Manajemen_Distribusi.html?id=IQJWEAAAQBAJ&redir_esc=y
Triyanto, F., Adianto, H., & Susanty, S. (2019). Usulan Rancangan Rute Distribusi Gas LPG 3 Kg Menggunakan Metode Heuristik dan Metode Branch and Bound. Jurnal Online Insitut Teknologi Nasional, 03(03), 194–205.
Utomo, R. G., Maylawati, D. S., & Alam, C. N. (2018). Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP). Jurnal Online Informatika, 3(1), 61. https://doi.org/10.15575/join.v3i1.218
Waridah, A. N., & Madja, M. S. (2023). Algoritma hybrid genetika pada capacitated vehicle routing problem (CVRP) dan implementasinya. Jurnal MIPA Dan Pembelajarannya (JMIPAP), 2(8), 1–10.
Yudhi, Syarifah Ratih Eka Wahyuni, M. K. (2020). Pengoptimalan Rute Pendistribusian Tabung Gas Lpg 3 Kg Dengan Algoritma Sequential Insertion (Studi Kasus: Koperasi Pegawai Kantor Gubernur Kalimantan Barat). Bimaster : Buletin Ilmiah Matematika, Statistika Dan Terapannya, 9(4), 505–514.
License
Copyright (c) 2025 Siti Aisyah, Ismail Husein
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
