Optimization of Vehicle Routing Problem Using Particle Swarm Optimization: A Case Study Watering Plants in Yogyakarta City

Riski Andriyansah(1*), Utaminingsih Linarti(2),

(1) Universistas Ahmad Dahlan
(2) Universitas Ahmad Dahlan Yogyakarta
(*) Corresponding Author
DOI: https://doi.org/10.23917/jiti.v21i2.19753

Abstract

Dinas Lingkungan Hidup (DLH) Yogyakarta City always tries to monitor, control, and control activities regarding all aspects of the environment, one of which is watering plants. The right path must be selected so as not to exceed the time limit set. This study aims to determine the direction of watering plants in Sector 3 for Vehicle Route Problem (VRP) using the Particle Swarm Optimization (PSO) and compare the performance results of the PSO method with the Genetic Algorithm (GA) in previous studies. The VRP criteria are heterogeneous fleet, intermediated facility, multi-trip, split delivery, and times window   (VRPHFIFMTSDTW). The results of the comparison between the two methods, namely, the GA method, are better than the PSO method in terms of computational time efficiency and fitness value. The total travel time for the GA method is 22 minutes, or 2.1% faster than the PSO method. In contrast, the total distance traveled by the PSO method is 345 meters shorter than the GA method. These two methods' results are also excellent compared to the current watering route. The difference in total mileage is about 20.4%, and total travel time is about 11.7% between the two methods.

Keywords

Comparison; DLH; Genetic Algorithm; Particle Swarm Optimization; VRP

Full Text:

PDF

References

Abdallah, M. Ben, & Ennigrou, M. (2020). Hybrid Multi-agent Approach to Solve the Multi-depot Heterogeneous Fleet Vehicle Routing Problem with Time Window (MDHFVRPTW). Advances in Intelligent Systems and Computing, 923, 376–386. https://doi.org/10.1007/978-3-030-14347-3_37

Alinezhad, H., Yaghubi, S., Hoseini-Motlagh, S.-M., Allahyari, S., & Saghafi Nia, M. (2018). An Improved Particle Swarm Optimization for a Class of Capacitated Vehicle Routing Problems. International Journal of Transportation Engineering, 5(4).

Angelelli, E., Speranza, M. G., Alie Kiely, N., & Speranza, M. G. (2002). The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 137(2), pp. 233-247. www.elsevier.com/locate/dsw

Ariyati, M. R., & Musthafa, A. R. (2018). Autonomous Robot Path Planning Menggunakan Perbandingan Metode Particle Swarm Optimization dan Genetic Algorithm, Jurnal Buana Informatika, 9(2), pp. 61-70.

Armandi, E., Purwani, A., & Linarti, U. (2019). Optimasi Rute Pengangkutan Sampah Kota Yogyakarta Menggunakan Hybrid Genetic Algorithm. Jurnal Ilmiah Teknik Industri, 18(2), 236–244. https://doi.org/10.23917/jiti.v18i2.8744

Arvianto, A., Setiawan, A. H., & Saptadi, S. (2014). Model Vehicle Routing Problem dengan Karakteristik Rute Majemuk, Multiple Time Windows, Multiple Products dan Heterogeneous Fleet untuk Depot Tunggal. Jurnal Teknik Industri, 16(2), 85–96. https://doi.org/10.9744/jti.16.2.85-96

Belmecheri, F., Christian, P., Yalaoui, F., & Amodeo, L. (2010). Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : (IPDPSW) Atlanta, (Georgia) USA, April 19-23, 2010. IEEE.

Efendi, R., Anggriani, K., & Sari, E. H. (2017). (Efendy wak_komp)1180-2338-1-PB.

El-Shorbagy, M. A., & Hassanien, A. E. (2018). Particle Swarm Optimization from Theory to Applications. International Journal of Rough Sets and Data Analysis, 5(2), 1–24. https://doi.org/10.4018/ijrsda.2018040101

Erdem, Y., Demirtas¸, D., Erhan¨ozdemir, E. E., & Demirtas¸, U. D. (2015). A particle swarm optimization for the dynamic vehicle routing problem. Conference: 2015 6th International Conference on Modeling, Simulation, and Applied Optimization (ICMSAO).

Hendrawan, B. E. (2007). Implementasi Algoritma Paralel Genetic Algorithm Untuk Penyelesaian Heterogeneous Fleet Vehicle Routing Problem. Final Project, Faculty of Information Technology,ITS Surabaya.

Isdianto, W., Linarti, U., Dahlan, A., Ringroad Selatan, J., & Yogyakarta, I. (2021). Penentuan Rute Optimal Penyiraman Tanaman Kota Yogyakarta Menggunakan Genetic Algorithm. Performa: Media Ilmiah Teknik Industri, 20(2), 121-132. https://doi.org/10.20961/performa.YY.Z.98765

Iswari, T., & Asih, A. M. S. (2018). Comparing genetic algorithm and particle swarm optimization for solving capacitated vehicle routing problem. IOP Conference Series: Materials Science and Engineering, 337(1). https://doi.org/10.1088/1757-899X/337/1/012004

Lukman, I., Hanafi, R., & Parenreng, S. M. (2019). Optimasi Biaya Distribusi pada HFVRP Menggunakan Algoritma Particle Swarm Optimization. Jurnal Optimasi Sistem Industri, 18(2), 164–175. https://doi.org/10.25077/josi.v18.n2.p164-175.2019

Paranduk, L., Indriani, A., Hafid, M., & Rahmawati, J. (2018). Sistem Informasi Penjadwalan Mata Kuliah Menggunakan Algoritma Genetika Berbasis Web. In Seminar Nasional Aplikasi Teknologi Informasi (SNATi).

Prathama, W. A., & Sulistyo, S. R. (2016). Penentuan Rute Distribusi Bantuan Medis untuk Bencana Erupsi Gunung Merapi di Yogyakarta. Program Studi Teknik Industri Departemen Teknik Mesin dan Industri RO-87 ISBN 978 602 73461 3 0

Sathya, P. D., & Kayalvizhi, R. (2010). PSO-Based Tsallis Thresholding Selection Procedure for Image Segmentation. International Journal of Computer Applications, 5(4).

Shi, Y., Zurada, J. M., Wilamowski, B. M., & Bonissone, P. P. (2004). Particle Swarm Optimization " " President’s Message. www.ieee-nns.org,

Sombuntham, P., & Kachitvichyanukul, V. (2010). Multi-depot vehicle routing problem with pickup and delivery requests. AIP Conference Proceedings, 1285, 71–85. https://doi.org/10.1063/1.3510581

Sun, H., Dong, K., Zhang, Q, & Yan, R. (2015). An improved particle swarm algorithm for heterogeneous fleet vehicle routing problem with two-dimensional loading constraints. Proceedings of the 2015 International Conference on Materials Engineering and Information Technology Applications.

Suprayogi, S. (2020). Penentuan rute truk pengumpulan dan pengangkutan sampah di Bandung. https://www.researchgate.net/publication/47716346

Talbi, E.-G. (2009). Metaheuristics : from design to implementation. John Wiley & Sons.

Talukder, S. (2011). Mathematical Modelling and Applications of Particle Swarm Optimization. www.bth.se/com

Tuegeh, M., & Purnomo, M. H. (2009). Modified Improved Particle Swarm Optimization For Optimal Generator Scheduling. Seminar Nasional Aplikasi Teknologi Informasi.

Wardhana, P. A., Aurachman, R., & Santosa, B. (2019). Penentuan Rute Armada Pengiriman PT. AAA Menggunakan Algoritma Two-Phase Tabu Search Pada Vehicle Routing Problem With Heterogeneous Fleet And Time Windows Untuk Mengatasi Keterlambatan Pengiriman. JISI, 6(2). https://doi.org/10.24853/jisi.6.2.135-143

Wiyanti, D. T. (2013). Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem (Optimization Algorithm for Solving Travelling Salesman Problem). In Juli (Vol. 11, Issue 1).

Wu, D. Q., Dong, M., Li, H. Y., & Li, F. (2016). Vehicle routing problem with time windows using multi-objective co-evolutionary approach. International Journal of Simulation Modelling, 15(4), 742–753. https://doi.org/10.2507/IJSIMM15(4)CO19

Article Metrics

Abstract view(s): 299 time(s)
PDF: 159 time(s)

Refbacks

  • There are currently no refbacks.