Perbandingan Algoritma Ant Colony Optimization dan Large Neighborhood Search dalam Penyelesaian CVRP dengan Rute Jalan Nyata di Kota Pontianak
DOI:
https://doi.org/10.26418/jp.v11i3.97236Keywords:
Ant Colony Optimization (ACO), Large Neighborhood Search (LNS), Capacitated Vehicle Routing Problem (CVRP), Heuristik, OpenStreetMapsAbstract
Riset ini bertujuan untuk membandingkan kinerja algoritma Ant Colony Optimization (ACO) dan Large Neighborhood Search (LNS) dalam menyelesaikan permasalahan Capacitated Vehicle Routing Problem (CVRP) dengan rute jalan nyata di Kota Pontianak. ACO meniru perilaku semut yang menggunakan jejak feromon untuk menemukan jalur terpendek, sedangkan LNS mengeksplorasi solusi melalui pendekatan destroy and repair. Eksperimen dilakukan menggunakan data koordinat geografis dan rute jalan real yang divisualisasikan melalui OpenStreetMaps dengan implementasi berbasis JavaScript. Kontribusi penelitian ini adalah menyediakan evaluasi komprehensif terhadap pendekatan penyelesaian masalah perutean pada jaringan jalan yang kompleks serta menawarkan kerangka implementasi berbasis web yang dapat direplikasi untuk mendukung optimasi logistik dan pengembangan strategi pendistribusian barang secara lebih efisien. Hasil menunjukkan bahwa LNS menyelesaikan solusi dalam 1,198 detik, sekitar 21 kali lebih cepat dibandingkan ACO yang memerlukan waktu 25,229 detik. Total jarak tempuh LNS tercatat 102,48 km, lebih pendek 8,22 km atau 7,42% dibandingkan ACO yang mencapai 110,7 km. LNS juga mencatat penurunan jarak sebesar 10,72%, sedangkan ACO hanya 4,15%. Kesimpulannya, LNS unggul dalam efisiensi komputasi dan optimasi jarak tempuh, sementara ACO tetap efektif dalam eksplorasi awal dan kestabilan solusi.References
A. V Fatnita and 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),” Prosiding Seminar Nasional Sains Dan Teknologi Terapan, vol. 1, no. 1, pp. 39–46, 2020, [Online]. Available: https://ejournal.itats.ac.id/sntekpan/article/%0A view/1213
R. Arifin and D. T. Liputra, “Pemecahan Asymmetric Capacitated Vehicle Routing Problem with Time Windows (ACVRPTW) dengan Algoritma Sequential Insertion (SI) dan Ant Colony Optimization (ACO),” Jurnal Rekayasa Sistem Industri, vol. 12, no. 2, pp. 273–280, 2023, doi: 10.26593/jrsi.v12i2.6477.273-280.
P. A. Wicaksono and L. Kusniawati, “Optimasi Rute Pengiriman Bahan Baku Ckd Part Dengan Pendekatan Capacitated Vehicle Routing Problems (Cvrp) Di Pt Xyz,” Industrial Engineering Online Journal, vol. 12, no. 4, pp. 1–14, 2023, [Online]. Available: https://ejournal3.undip.ac.id/index.php/ieoj/article/view/40931
R. Nurlailawati, T. Bakhtiar, and P. T. Supriyo, “Masalah Antar-Jemput Barang Menggunakan Armada Kendaraan Listrik dengan Kapasitas Angkut dan Kapasitas Baterai Berbeda,” Jurnal Matematika Integratif, vol. 19, no. 2, pp. 173–182, 2023, doi: 10.24198/jmi.v19.n2.48627.173-182.
V. Nono, M. Sofitra, and D. Wijayanto, “Penyelesaian Capacitated Vehicle Routing Problem Dengan Menggunakan Algoritma Sweep Untuk Penentuan Rute Distribusi Untuk Depo PT. ABC Kubu Raya,” INTEGRATE: Industrial Engineering and Management System, vol. 4, no. 2, pp. 232–238, 2020.
E. Setyati and I. Juniwati, “Ant Colony Optimization untuk Menyelesaikan Perutean Distribusi Snack dengan Vehicle Routing Problem,” Jurnal Teknologi Informasi dan Terapan (J-TIT), vol. 9, no. 2, pp. 111–117, 2022, [Online]. Available: https://doi.org/10.25047/jtit.v9i2.296
S. Kristina, R. D. Sianturi, and R. Husnadi, “Penerapan Model Capacitated Vehicle Routing Problem (CVRP) Menggunakan Google OR-Tools untuk Penentuan Rute Pengantaran Obat pada Perusahaan Pedagang Besar Farmasi (PBF),” Jurnal Telematika, vol. 15, no. 2, pp. 101–106, 2020, [Online]. Available: https://doi.org/10.61769/telematika.v15i2.359
R. A. Pratama, P. H. Utomo, and S. Wibowo, “Perbandingan Solusi CVRP Pada Distribusi Buku Aqila Di Surakarta Menggunakan Algoritme Tabu Search Dan Algoritme ACO,” Jurnal Riset dan Aplikasi Matematika, vol. 6, no. 1, pp. 13–22, 2022.
A. Viktaria, Efektivitas Algoritma Simulated Annealing Dan Large Neighborhood Search Dalam Penyelesaian Pickup And Delivery Vehicle Routing Problem With Time Windows. Skripsi. Universitas Negeri Yogyakarta, 2015.
O. A. W. Riyanto and B. Santosa, “ACO-LS Algorithm for Solving No-wait Flow Shop Scheduling Problem,” International Conference on Soft Computing, Intelligence Systems, and Information Technology, Springer, pp. 89–97, 2015, doi: 10.1007/978-3-662-46742-8_8.
M. Dorigo and T. Stützle, Ant Colony Optimization: Overview and Recent Advances. Handbook of Metaheuristics, 2018. doi: 10.1007/978-1-4419-1665-5_8.
D. Pisinger and S. Røpke, “Large Neighborhood Search,” Handbook of Metaheuristics, 2018, doi: 10.1007/978-1-4419-1665-5_13.
H. Muna, “Performance Analysis of Ant Colony Algorithm (Ant Colony Optimization) in Solving Capacitated Vehicle Routing Problem (CVRP),” Science Tech: Jurnal Ilmu Pengetahuan dan Teknologi, vol. 8, no. 2, pp. 10–24, Agu. 2022. doi: 10.30738/st.vol8.no2.a12737
D. Yuliati, R. Qomaria, dan A. Hamid, “Optimalisasi Pencarian Rute Kapal Terbaik dengan Menggunakan Metode Ant Colony Optimization,” Jurnal Informatika Polinema, vol. 11, no. 1, pp. 29–36, 2024. doi: 10.33795/jip.v11i1.5075.
M. Fitriyani dan D. Ahmad, “Implementasi Ant Colony Optimization Algorithm (ACO) untuk pemilihan jalur tercepat evakuasi bencana tsunami oleh tim SAR di Kota Padang,” J. Riset dan Aplikasi Matematika (JRAM), vol. 8, no. 1, pp. 78–84, Mei 2024. doi: 10.26740/jram.v8n1.p78-84
D. Udjulawa and S. Oktarina, “Penerapan Algoritma Ant Colony Optimization Untuk Pencarian Rute Terpendek Lokasi Wisata,” Klik - Jurnal Ilmu Komputer, vol. 3, no. 1, pp. 26–33, 2022, doi: 10.56869/klik.v3i1.326.
M. D. Khairansyah, M. L. Ashari, and I. Mufidah, “Penentuan 7 Jalur Evakuasi Terpendek Pada Industri Plastik Menggunakan Ant Colony Optimization,” Jurnal Keselamatan Transportasi Jalan (Indonesian Journal of Road Safety), vol. 8, no. 1, pp. 53–61, 2021, doi: 10.46447/ktj.v8i1.312.
D. M. Ramdan and V. Hartati, "Route Optimization for Perishable Goods Distribution Using Ant Colony Optimization: A Capacitated Vehicle Routing Problem (CVRP) Case Study,"Electronic Journal of Education, Social Economics and Technology, vol. 6, no. 1, pp. 489-500, 2025, doi:10.33122/ejeset.v6i1.729
F. W. Ramadhani, W. P. Sari, A. Darmawan, and A. P. Rifai, "Multi-Vehicle Capacitated Vehicle Routing Problem For Rice Commodities In Indonesia Considering The Factors Of Weather-Induced Damages And Carbon Emissions," ASEAN EngineeringJournal, vol. 14, no. 2, pp. 195-207, Jun. 2024, doi:10.11113/aej.v14.21096.
R. Arifin and D. T. Liputra, "Pemecahan Asymmetric Capacitated Vehicle Routing Problem with Time Windows (ACVRPTW) dengan Algoritma Sequential Insertion (SI) dan Ant Colony Optimization (ACO)," Jurnal Rekayasa Sistem Industri, vol. 12, no. 2, pp. 273-280, oktober 2023, doi:10.26593/jrsi.v12i2.6477.273-280.
H. Fahmi, M. Zarlis, E. Nababan, and P. Sihombing, “Ant Colony Optimization (ACO) Algorithm for Determining The Nearest Route Search in Distribution of Light Food Production,” Journal of Physics: Conference Series, vol. 5166, p. 012045, 2020, doi: 10.1088/1742-6596/1566/1/012045.
A. N. Fadjriani, M. Sofitra, and D. Wijayanto, “Perencanaan Rute Dan Jadwal Distribusi Periodik Multi Product Pada PT. Wicaksana Overseas International Pontianak Menggunakan Metode Large Neighborhood Search,” INTEGRATE: Industrial Engineering and Management System, vol. 7, no. 1, pp. 211–220, 2023.
