Penyelesaian Multi Depot Vehicle Routing Problem with Time Windows Menggunakan Particle Swarm Optimization Algorithm

Khairunnisa Aulia Azzahra, Khusnul Novianingsih, Dewi Rachmatin

Abstract


AbstractThis research addresses the Multi Depot Vehicle Routing Problem with Time Windows (MDVRPTW), the problem of determining vehicle routes from several depots to multiple customers while considering time window constraints for each route. The goal of solving MDVRPTW is to obtain optimal routes with the shortest total travel time without exceeding their respective time windows. The Particle Swarm Optimization (PSO) algorithm is used to solve MDVRPTW, adapted from the social behavior of a flock of birds in search of food. The algorithm operates through initialization, evaluation, route construction, and route updates to achieve optimality. The research was tested on a case study involving raw material pickup for a company with 2 storage depots and 169 agents. The implementation of PSO successfully generated an average travel time of 7.83 hours for each route, indicating adherence to time windows and fulfillment of vehicle capacity.

Keywords:Multi Depot Vehicle Routing Problem, Particle Swarm Optimization, Route, Time Windows


Penelitian ini membahas Multi Depot Vehicle Routing Problem with Time Windows (MDVRPTW), masalah penentuan rute kendaraan dari sejumlah depot ke beberapa pelanggan dengan mempertimbangkan batasan time windows dalam setiap rutenya. Tujuan penyelesaian MDVRPTW adalah mendapatkan rute optimal dengan total travel time terkecil dan tidak melebihi time windows-nya. Algoritma Particle Swarm Optimization (PSO) digunakan untuk menyelesaikan MDVRPTW. Cara kerja PSO diadaptasi dari perilaku sosial dari sekawanan burung dalam mencari makan. Algoritma ini bekerja dengan cara melakukan inisialisasi, mengevaluasi, mengonstruksi rute, dan memperbaharui rute hingga optimal. Penelitian diuji pada studi kasus pengambilan bahan baku suatu perusahaan dengan 2 depot penyimpanan dan 169 agen. Implementasi PSO berhasil membentuk rata-rata travel time setiap rute adalah 7,83 jam yang artinya time windows tidak dilanggar dan kapasitas kendaraan terpenuhi.

Keywords


Multi Depot Vehicle Routing Problem, Particle Swarm Optimization, Rute, Time Windows

Full Text:

PDF

References


Bae, H., & Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Applied Mathematical Modelling, 40(13-14), 6536-6549.

Bae, H., Moon, I., & Yun, W. (2016). A Time-Varying Lot Sizes Approach for The Economic Lot Scheduling Problem with Return. International Journal of Production Research. 54(11). p.3380-3396.

Bai, Q. (2010). Analysis of Particle Swarm Optimization Algorithm. Computer and Information Science (3:1). p.180.

Crevier, B., Cordeau, J. F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European journal of operational research, 176(2), p.756-773.

Fitriana, R., & Moengin, P., & Kusumaningrum, U. (2019). Improvement Route for Distribution Solutions MDVRP (Multi Depot Vehicle Routing Problem) using Genetic Algorithm. IOP Conference Series Materials Science and Engineering. 528(1). p.12–42. IOP Publishing.

Gamayanti, N., Alkaff, A., Mangatas, R. (2015). Optimisasi Multi Depot Vehicle Routing Problem (MDVRP) dengan Variabel Travel Time Menggunakan Algoritma Particle Swarm Optimization. JAVA Journal of Electrical and Electronics Engineering. 13(1). Surabaya

Kennedy J, Eberhart RC (1995) Particle swarm optimization?. Proceedings of the IEEE international conference on neural networks. p. 1942–1948.

Shami, T.M., El-Saleh, A.A., Alswaitti, M., Al-Tashi, Q., Summakieh, M.A., & Mirjalili, S. (2022). Particle Swarm Optimization: A Comprehensive Survey. IEEE Access. 10. p. 10031-10061.

Venter, G., & Sobieszczanski-Sobieski, J. (2003). Particle swarm optimization. AIAA journal, 41(8), 1583-1589.

Wang, D., Tan, D., & Liu, L. (2018). Particle swarm optimization algorithm: an overview. Soft computing, 22, p. 387-408.

Yeun, L.C., Ismail, W.R., Omar, K., & Zirour, M. (2008). Vehicle routing problem: models and solutions. Journal of Quality Measurement and Analysis.




DOI: https://doi.org/10.17509/jem.v12i1.69199

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Mathematics Program Study, Universitas Pendidikan Indonesia

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

  

 Google Scholar Logo PNG vector in SVG, PDF, AI, CDR format