A MODIFIED INTELLIGENT WATER DROPS ALGORITHM FOR MULTIPLE OBJECTIVES MULTIPLE DEPOT OPEN VEHICLE ROUTING PROBLEM

Kadek Gemilang Santiyuda; Yu-en Chou; I Wayan Kintara Anggara Putra

Authors

Kadek Gemilang Santiyuda National Taiwan University of Science and Technology
Yu-en Chou National Taiwan University of Science and Technology
I Wayan Kintara Anggara Putra Christian Duta Wacana University

Keywords:

Transportaion, Multiple Objectives,, Pareto Optimality, MO-IWD-SA, MDOVRP

Abstract

The delivery cost was once the only concern in transportation, but as society needs to grow, multiple objectives are to be considered in route planning. The efforts of companies to optimize their transportation issues also grow. One of the efforts is to utilize transportation services without directly owning any vehicle and courier to cut management and maintenance costs. The outsourcing of vehicles and couriers to solve multiple objectives of route planning can be formulated into multiple objectives of multiple depot vehicle routing problems (MDOVRP). In this research, a modification of intelligent water drops (IWD) is proposed to find a set of reasonable solutions in the sense of Pareto optimality (Pareto front, PF) for the multiple objectives of MDOVRP. The proposed method applies simulated annealing (SA) probability and a PF optimization method called SPEA2 into IWD (MO-IWDSA). The proposed method is then tested by modifying the hybrid multiple objective evolutionary algorithm (HMOEA) (Bi, Han dan Tang, 2017). The two methods are tested to solve multiple objectives of MDOVRP, an online catering company in Jakarta. The proposed method proved to show improvement in the quality of PF up to 6.4%. The researchers tested their new method with a real-world example: an online catering service in Jakarta. The method uses advanced algorithms inspired by natural processes, like how rivers find the easiest path to flow, combined with other mathematical tools. The result? A better delivery system that improved efficiency by 6.4%, helping the company save money and serve customers faster.

References

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company.

Sariklis, G., & Powell, S. G. (2000). A branch-and-bound algorithm for the multiple depot vehicle routing problem. European Journal of Operational Research, 121(2), 405-420. https://doi.org/10.1016/S0377-2217(99)00269-9

Tarantilis, C. D., & Kiranoudis, C. T. (2002). A heuristic method for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 29(12), 1699-1718. https://doi.org/10.1016/S0305-0548(01)00077-2

Montoya-Torres, J. R., Guerrero, F. A., & Valenzuela, J. C. (2015). A review of the multiple depot open vehicle routing problem: Models, solution methods, and applications. Computers & Industrial Engineering, 86, 119-138. https://doi.org/10.1016/j.cie.2015.03.015

Moncayo-Martínez, D., & Mastrocinque, E. (2016). Modifications of the Improved Water Drops (IWD) algorithm for multi-objective supply chain optimization. International Journal of Advanced Manufacturing Technology, 85(1-4), 653-665. https://doi.org/10.1007/s00170-015-7414-2

Ong, S. H., Niu, Z., & Nee, A. Y. C. (2013). Multi-objective job shop scheduling using the Improved Water Drops (IWD) algorithm. Journal of Manufacturing Science and Engineering, 135(6), 061007. https://doi.org/10.1115/1.4025782

Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. In Proceedings of the IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making (pp. 95-100). IEEE. https://doi.org/10.1109/CIMDM.2001.928251

Ezugwu, A. E., et al. (2018). A hybrid of IWD and simulated annealing for solving the multiple depot vehicle routing problem. Computers & Industrial Engineering, 118, 102-118. https://doi.org/10.1016/j.cie.2018.02.020

Ong, Y. S., Niu, Z., & Nee, A. Y. C. (2013). A multi-objective approach to job shop scheduling with Pareto dominance. International Journal of Advanced Manufacturing Technology, 64(9–12), 1485–1496. https://doi.org/10.1007/s00170-012-4485-x

Bi, Z., Han, X., & Tang, L. (2017). Hybrid multiple objective evolutionary algorithm and local search for multiple depot vehicle routing problem. Computers & Industrial Engineering, 113, 47-58. https://doi.org/10.1016/j.cie.2017.07.011

I Made Dedy Setiawan, Ryan Pratama Putra, & Putu Sugiartawan. (2023). Media Pembelajaran Interaktif Pada Materi Klasifikasi Hewan untuk Siswa Sekolah Dasar. Jurnal Imiah Pendidikan Dan Pembelajaran, 6(3), 588–598. https://doi.org/10.23887/jipp.v6i3.56641

Kassaymeh, S., Al-Laham, M., Al-Betar, M. A., Alweshah, M., Abdullah, S., & Makhadmeh, S. N. (2022). Backpropagation Neural Network optimization and software defect estimation modelling using a hybrid Salp Swarm optimizer-based Simulated Annealing Algorithm. Knowledge-Based Systems, 244, 108511. https://doi.org/10.1016/j.knosys.2022.108511

Made, N., Trisnayanti, R., & Sugiartawan, P. (2022). Multimedia Interaktif Infografis Desa Agro Kreatif Bingin Ambe Koripan Berbasis Android. Jurnal Sistem Informasi Dan Komputer Terapan Indonesia (JSIKTI), 5(2), 63–74. https://doi.org/10.33173/jsikti.178

Rizky, M. A., Sugiartawan, P., Studi, P., & Informatika, T. (2022). Sistem Informasi Kegiatan Kelompok Tani Di UPT HPT Dan Keswan Praya Timur 1,2, 5(2), 87–96. https://doi.org/10.33173/jsikti.

Sudiarsa, I. W., Sudipa, I. G. I., Sugiartawan, P., Maharianingsih, N. M., & Pande, N. K. N. N. (2023). Information System for Monitoring Production Process of Dried Kelor Leaf Dried Using the FAST Method. Sinkron, 8(4), 2748–2756. https://doi.org/10.33395/sinkron.v8i4.13095

Sudiarsa, I. wayan, Sugiartawan, P.,Sudipa, I. G. I., Maharianingsih, N. M., & Putra, I. K. A. (2023). Sistem Pengering Daun Kelor Berbasis Internet of Things dan Artificial Intteligence. IJEIS (Indonesian Journal of Electronics and Instrumentation Systems), 13(2), 183. https://doi.org/10.22146/ijeis.89823

Sugiartawan, P., & Desnanjaya, I. G. N. (2022). Smart Farming Untuk Pengaturan Suhu Ruangan Pada Budidaya Jamur Tiram Berbasis Backpropagation. IJEIS (Indonesian Journal of Electronics and Instrumentation Systems), 12(2), 191. https://doi.org/10.22146/ijeis.78546

Sugiartawan, P., Hartati, S.,& Musdholifah, A. (2020). Modeling of a tourism group decision support system using risk analysis based knowledge base. International Journal of Advanced Computer Science and Applications, 11(7), 354–363. https://doi.org/10.14569/IJACSA.2020.0110747

Sugiartawan, P., Pulungan, R., & Sari, A. K. (2017). Prediction by a Hybrid of Wavelet Transform and Long-Short-Term-Memory Neural Network. International Journal of Advanced Computer Science and Applications, 8(2), 326–332. https://doi.org/10.14569/ijacsa.2017.080243

Sugiartawan, P., & Santoso, S. G. (2022). Multivariate Forecasting Curah Hujan Menggunakan. Seminar Nasional Corisindo : Institut Teknologi Dan Bisnis STIKOM Bali, 580–585.

Sugiartawan, P., Suryawan, I. G. T., & Indawan, I. G. A. (2022). Sistem Informasi Keuangan Pada Koperasi Karya Utama Mandiri. Jurnal Sistem Informasi Dan Komputer Terapan Indonesia, 5(2), 97–108. https://doi.org/10.33173/jsikti.181