Optimasi Vehicle Routing Problem pada Distribusi Tabung LPG Menggunakan Metode Ant Colony Optimization

Devitasari Simamora; Riri Syafitri Lubis; Sri Ulfa Rahayu

doi:10.37905/euler.v14i1.37481

Optimasi Vehicle Routing Problem pada Distribusi Tabung LPG Menggunakan Metode Ant Colony Optimization

Devitasari Simamora, Riri Syafitri Lubis, Sri Ulfa Rahayu

Abstract

Inefficient distribution can increase operational costs; therefore, determining optimal routes is essential to support an efficient distribution process. This problem can be formulated as a Vehicle Routing Problem (VRP), which concerns optimizing vehicle routes from a depot to multiple destinations with minimum travel distance. This study aims to optimize the distribution route of LPG cylinders at PT Jaya Sari Artha by considering 12 distribution points. The method used is Ant Colony Optimization (ACO), a heuristic algorithm inspired by the foraging behavior of ants in finding the shortest path. The data used consist of actual travel distances between distribution points obtained from Google Maps. The results show that the implementation of ACO in the VRP model produces a distribution route with a total distance of 117.40 km, shorter than the company’s initial route of 134.50 km. Thus, a distance saving of 17.10 km or 12.72% was achieved. These findings indicate that the ACO method is effective in solving VRP and improving the efficiency of LPG cylinder distribution in a real-world case.

Keywords

Ant Colony Optimization; Distribution; Route; Vehicle Routing Problem

Full Text:

PDF

References

M. Yetrina and D. S. Nainggolan, “Penentuan Rute Distribusi Untuk Meminimasi Biaya Distribusi di UKM Habil Snack,” J. Teknol. Dan Sist. Inf. Bisnis, vol. 3, no. 1, pp. 247–253, 2021, doi: https://doi.org/10.47233/jteksis.v3i1.221

M. N. Azura and R. S. Lubis, “Application of Dynamic Programming in Determining The Shortest Route PT JNE Using Backward Recursive Equation,” EduMatSains J. Pendidikan, Mat. dan Sains, vol. 9, no. 1, pp. 310–318, 2024, doi: 10.33541/edumatsains.v9i1.5982

R. N. Devita and A. P. Wibawa, “Teknik Teknik Optimasi Knapsack Problem,” Sains, Apl. Komputasi dan Teknol. Inf., vol. 2, no. 1, pp. 35–40, 2020, doi: http://dx.doi.org/10.30872/jsakti.v2i1.3299

D. P. Rohmawati, P. T. B. Ngastiti, and Z. Sya’diyah, “Implementasi Algoritma A* Dalam Penentuan Rute Terpendek (Studi Kasus: Jarak Tempuh Desa Sridadi Rembang Menuju Universitas Billfath Lamongan),” MATHunesa J. Ilm. Mat., vol. 12, no. 3, pp. 646–653, 2024, doi: https://doi.org/10.26740/mathunesa.v12n3.p646-653

F. Armanda and R. F. Sari, “Optimization of Liquid Petroleum Gas (LPG) Gas Cylinder Distribution Route with Saving Matrix Method,” Numer. J. Mat. Dan Pendidik. Mat., vol. 7, no. 1, pp. 99–110, 2023, doi: https://doi.org/10.25217/numerical.v7i1.3452.

A. V. Fatnita and L. Lukmandono, “Optimasi Rute DIstribusi Tabung LPG 3 Kg Dengan Menggunakan Algoritma Genetika Pada Penyelesaian Capacitated Vehicle Routing Problem (CVRP)(Studi kasus pada PT. Jana Pusaka Migas),” in Prosiding Seminar Nasional Sains dan Teknologi Terapan Institut Teknologi Adhi Tama Surabaya, Surabaya, 2020, doi: https://ejurnal.itats.ac.id/sntekpan/article/view/1213/977

M. A. Adri, D. J. Panjaitan, and H. Cipta, “Vehicle Routing Problem (VRP) dalam Penentuan Rute Terpendek Pendistribusian Tabung Gas LPG Dengan Mempertimbangkan Jumlah Permintaan,” J. Ilm. Mat. Dan Terap., vol. 19, no. 1, pp. 49–57, 2022, doi: 10.22487/2540766x.2022.v19.i1.15885.

E. S. Sulistyono, “Model Rute Perjalanan Minimal Dengan Menggunakan Vehicle Routing Problem Pada PT X,” J. Teknol. Dan Sist. Inf. Bisnis, vol. 4, no. 2, pp. 293–299, 2022, doi: 10.47233/jteksis.v4i2.497.

M. C. Sugiono, “Model vehicle routing problem untuk penentuan rute distribusi unit sepeda motor dengan metode saving matrix,” Journal Industrial Servicess, vol. 7, no. 2, pp. 0–3, 2022.

I. Fatikawati, S. Syaripuddin, and M. N. Huda, “Implementasi Algoritma Genetika dalam Menentukan Rute Terpendek Pendistribusian Barang PT. J&T Samarinda,” Basis J. Ilm. Mat., vol. 2, no. 2, pp. 12–21, 2023, doi: https://doi.org/10.30872/basis.v2i2.1071

N. W. A. F. Lestari, I. W. A. Widhiatmika, A. Wafa, N. M. Nola, and A. V. R. Hutabarat, “Optimalisasi Penentuan Jalur Distribusi Terpendek dalam Pengiriman Produk Chemical Pembersih Kolam Renang Menggunakan Metode Nearest Neighbor,” J. Syntax Admiration, vol. 6, no. 3, pp. 1426–1436, 2025, doi: https://doi.org/10.46799/jsa.v6i3.2177

E. Setyati and I. Juniwati, “Ant Colony Optimization Ant Colony Optimization untuk menyelesaikan perutean distribusi Snack dengan Vehicle Routing Problem,” J. Teknol. Inf. dan Terap., vol. 9, no. 2, pp. 111–117, 2022, doi: https://doi.org/10.25047/jtit.v9i2.296

F. I. Ningsih and R. F. Sari, “Optimization of 3 Kg LPG Gas Distribution Route at PT Arafizza Sikumbang Using the VRP Model and Clarke and Wright Savings Algorithm,” J. Mandalika Mathematics and Education, vol. 7, no. 3, pp. 1286-1298, 2025, doi: http://dx.doi.org/10.29303/jm.v7i3.9835

A. N. Rohmah, “Analisis Optimasi Rute Distribusi Barang Menggunakan Vehicle Routing Problem (Vrp) Model Sweep Method Pada PT. XYZ,” J. Ilm. Manaj. dan Akunt., vol. 3, no. 1, pp. 243–253, 2026, doi: https://doi.org/10.69714/k1gd2g70

A. C. S. Arif and S. Suseno, “Usulan Rute Pendistribusi Menggunakan Algoritma Clarke And Wright Savings Dan Sequential Insertion,” J. Ilm. Tek. Ind. dan Inov., vol. 2, no. 3, pp. 31–44, 2024, doi: https://doi.org/10.59024/jisi.v2i3.727

M. Pratiwi and R. S. Lubis, “Distribution Route Optimization Using Nearest Neighbor Algorithm and Clarke and Wright Savings,” Sinkron, vol. 8, no. 3, pp. 1638–1652, 2023, doi: 10.33395/sinkron.v8i3.12622.

M. Azahra and M. Habiburrohman, “A Minimization of Fuel Costs in Pharmaceutical Distribution Using Clarke-Wright Savings Heuristic and Nearest Neighbor Methods,” MATHunesa J. Ilm. Mat., vol. 13, no. 3, pp. 545–553, 2025, doi: https://doi.org/10.26740/mathunesa.v13n3.p545-553.

William, R. S. Sitompul, A. R. Hia, R. Malau, and S. P. Tamba, “Penerapan Metode Ant Colony Pptimization (ACO) dalam Menentukan Jalur Alternatif Solusi Kemacetan Kota Medan,” J. TEKINKOM, vol. 7, pp. 325–335, 2024, doi: 10.37600/tekinkom.v7i1.1221.

A. I. Pratiwi, S. Sustariyah, A. Z. Wathoni, S. Pazri, and D. C. Ahsanunadia, “Penentuan Rute Terbaik Pendistribusian Dengan Metode Ant Colony Optimization (Studi Kasus Perusahaan Jasa Pergudangan Sparepart Jawa Barat),” Ind. Xplore, vol. 8, no. 2, pp. 259–268, 2023, doi: https://doi.org/10.36805/teknikindustri.v8i2.5644

L. Syahr, M. Khoswara, H. S. A. H, and S. Suseno, “Pencarian Rute Optimal Distribusi Melalui Pendekatan Metode Ant Colony Optimization (ACO),” J. Teknol. dan Manaj. Ind. Terap., vol. 2, no. 2, pp. 63–71, 2023, doi: 10.55826/tmit.v2i2.105.

W. A. Riyantara, R. Simatupang, E. Wolok, I. H. Lahay, and H. Uloli, “Analisis Penentuan Rute Distribusi Produk Makanan Menggunakan Pendekatan Algoritma Ant Colony Optimization (ACO) PT. Cipta Langgeng Mitra Sukses: Penelitian,” J. Pengabdi. Masy. dan Ris. Pendidik., vol. 4, no. 1, pp. 4765–4774, 2025.

S. N. Jumaedi, W. Abidin, and T. A. Nurman, “Penerapan Algoritma Ant Colony Optimization (ACO) Rute Jalur Terpendek (Studi Kasus Distribusi Barang JNE Wilayah Bumi Tamalanrea Permai (BTP)),” J. MSA (Matematika dan Stat. serta Apl., vol. 12, no. 1, pp. 108–115, 2024, doi: https://doi.org/10.24252/msa.v12i1.50753

N. A. Husna, D. Hendri, H. Z. Haq, and A. Rahmadeyan, “Implementasi Algoritma Ant Colony Optimization untuk Penentuan Jalur Terpendek Klinik dari Lokasi Rawan Kecelakaan Di Kota Pekanbaru: Implementation of the Ant Colony Optimization Algorithm for Determination of the Shortest Clinic Path From Accident-Prone Locations in Pekanbaru City,” in SENTIMAS: Seminar Nasional Penelitian dan Pengabdian Masyarakat, 2023, pp. 112–119. doi: https://journal.irpi.or.id/index.php/sentimas

A. Ihsan, T. A. Adlie, and S. Harliansyah, “Optimalisasi Pencarian Jalur Terpendek Mobile Robot dengan Menggunakan Metode Ant Colony Optimization (ACO),” Techné J. Ilm. Elektrotek., vol. 23, no. 1, pp. 39–54, 2024, doi: 10.31358/techne.v23i1.389.

DOI: https://doi.org/10.37905/euler.v14i1.37481