PERFORMANSI ANALISIS ALGORITMA KOLONI SEMUT (ANT COLONY OPTIMIZATION) DALAM MENYELESAIKAN PERMASALAHAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)

Authors

  • Izza Hasanul Muna PT Telkom Indonesia

DOI:

https://doi.org/10.12928/admathedu.v12i1.22385

Keywords:

Ant Colony Optimization, Capacitated Vehicle Routing Problem (CVRP), VRP, Optimization

Abstract

Algoritma koloni semut (ACO) merupakan sebuah algoritma yang diperkenalkan oleh Moyson dan Manderick dan selanjutnya dikembangkan oleh Marco Dorigo. Algoritma ini telah diterapkan dalam berbagai masalah optimasi, salah satunya adalah Capacitated Vehicle Routing Problem (CVRP). Tujuan dari penelitian ini adalah untuk menyelidiki tingkat performansi algoritma koloni semut (ACO) dalam menyelesaikan CVRP. Performansi ACO nantinya diukur berdasarkan 3 faktor, yaitu penggunaan memori, waktu eksekusi dan tingkat akurasi. Selain itu, dilakukan pula identifikasi pengaruh perubahan setting parameter terhadap performansi ACO. Hasil penelitian menunjukkan bahwa ACO memiliki penformasi yang cukup baik dalam menyelesaikan CVRP, baik dari segi penggunaan memori, waktu eksekusi maupun tingkat akurasi. Akan tetapi, performansi ACO ternyata juga dipengaruhi oleh beberapa parameternya. Hasil temuan dalam penelitian ini menunjukkan bahwa terdapat beberapa parameter ACO yang memiliki pengaruh signifikan terhadap performansi algoritma, yaitu jumlah semut, , nilai  dan . Sedangkan parameter yang lain, yaitu Q dan , kurang berpengaruh terhadap performansi ACO.

References

Borcinova, Z. (2017). Two models of the capacitated vehicle routing problem. Croatian Operational Research Review, 8(2). https://doi.org/10.17535/crorr.2017.0029

CVRP Benchmark. (n.d.). Retrieved November 15, 2021, from http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

Hillier, F., & Lieberman, G. (2010). Introduction to Operation Research. McGraw-Hill.

Karakatic, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519–532.

Karjono, K. (Karjono), Budiyanto, U. (Utomo), & Luhur, M.-. (Moedjiono). (2016). Aplikasi Penjadwalan Crew Ship Menggunakan Ant Colony Optimization: Studi Kasus PT Scorpa Pranedya. In Jurnal TICOM (Vol. 5, Issue 1).

Kristina, S., Sianturi, R. D., & Husnadi, R. (2020). Penerapan Model Capacitated Vehicle Routing Problem (CVRP) Menggunakan Google OR-Tools untuk Penentuan Rute Pengantaran Obat pada Perusahaan Pedagang Besar Farmasi (PBF). Jurnal Telematika, 15(2).

Kurniati, N. I., Rahmatulloh, A., & Rahmawati, D. (2019). Perbandingan Performa Algoritma Koloni Semut Dengan Algoritma Genetika – Tabu Search Dalam Penjadwalan Kuliah. Computer Engineering, Science and System Journal, 4(1). https://doi.org/10.24114/cess.v4i1.11387

Lestari, H. P., & Sari, E. R. (2014). Penerapan algoritma koloni semut untuk optimisasi rute distribusi pengangkutan sampah di kota Yogyakarta. Jurnal Sains Dasar, 2(1). https://doi.org/10.21831/jsd.v2i1.2373

Muna, I. H. (2019). Models and Methods for routing problems in Logistics. Brno University of Technology.

Redi, A. A. N. P., Maula, F. R., Kumari, F., Syaveyenda, N. U., Ruswandi, N., Khasanah, A. U., & Kurniawan, A. C. (2020). Simulated annealing algorithm for solving the capacitated vehicle routing problem: a case study of pharmaceutical distribution. Jurnal Sistem Dan Manajemen Industri, 4(1). https://doi.org/10.30656/jsmi.v4i1.2215

Ropke, S. (2005). Heuristic and exact algorithms for vehicle routing problems. In Unpublished PhD thesis, Computer Science Department, University of Copenhagen (Issue December).

Shahab, M. L., & Irawan, M. I. (2016). Algoritma Genetika untuk Capacitated Vehicle Routing Problem. Jurnal Sains Dan Seni, 4(2), 89–94.

Toth, P., & Vigo, D. (2002a). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1–3). https://doi.org/10.1016/S0166-218X(01)00351-1

Toth, P., & Vigo, D. (2002b). The Vehile Routing Problem. In SIAM Society for Industrial and Applied Mathematics.

Xu, H., Pu, P., & Duan, F. (2018). Dynamic Vehicle Routing Problems with Enhanced Ant Colony Optimization. Discrete Dynamics in Nature and Society, 2018. https://doi.org/10.1155/2018/1295485

Yücenur, G. N., & Demirel, N. Ç. (2011). A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications, 38(9). https://doi.org/10.1016/j.eswa.2011.03.077

Yuwono, B., Aribowo, A. S., & Siswanto Budi Wardoyo. (2009). Implementasi Algoritma Koloni Semut Pada Proses Pencarian Jalur Terpendek Jalan Protokol Di Kota Yogyakarta. Seminar Nasional Informatika 2009, 2009(semnasIF).

Zarman, A., Irfan, M., & Uriawan, W. (2016). Implementasi Algoritma Ant Colony Optimization pada Aplikasi Pencarian Lokasi Tempat Ibadah Terdekat di Kota Bandung. Jurnal Online Informatika.

Published

2022-11-08

Issue

Vol. 12 No. 1: Juni 2022

Section

Articles

License

License and Copyright Agreement

In submitting the manuscript to the journal, the authors certify that:

  • They are authorized by their co-authors to enter into these arrangements.
  • The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the AdmathEdu Author Guidelines at http://journal.uad.ac.id/index.php/admathedu/about/submissions#onlineSubmissions
  • That it is not under consideration for publication elsewhere,
  • That its publication has been approved by all the author(s) and by the responsible authorities “tacitly or explicitly“ of the institutes where the work has been carried out.
  • They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
  • They agree to the following license and copyright agreement.

Copyright

Authors who publish with the AdmathEdu agree to the following terms:

  1. Authors retain copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.


Ciptaan disebarluaskan di bawah Lisensi Creative Commons Atribusi-BerbagiSerupa 4.0 Internasional.