Vehicle routing problem simultaneous deliveries and pickups with split loads and time windows with genetic algorithm (case study in shipping company)

• Autorzy: Ferdianti Shea Amanda , Widyadana I Gede Agus

Identyfikatory

DOI

10.17270/J.LOG.2023.904

• Języki publikacji: EN

Abstrakty

EN

Background: This research addresses a Vehicle Routing Problem with Simultaneous Delivery and Pickup, Split Loads, and Time Windows (VRPSDPSLTW). In this research, the VRPSDPSLTW problem is adapted for Company X, a shipping company based in Surabaya. The main goal is to enhance the optimal utilization of vessel capacity in the field of shipping transportation and logistics. Little previous research has been done on VRPSDPSLTW at a shipping company. Methods: The optimization approach employed was the Genetic Algorithm (GA), which serves as a metaheuristic to effectively optimize vessel capacity utilization. The algorithm uses One Point Crossover and Swap Mutation operators and analyzes various mutation parameters to determine the best configuration. The GA was coded in R, and experiments were conducted to obtain the best parameter for the GA. Results: The research yielded several outcomes, including route plans, loaded and unloaded Twenty-Foot Equivalent Units (TEUs), travel times, and trip utility from the point of loading (POL) to the point of delivery (POD). In total, there were 85 port visits, surpassing the initial count of 35 ports. Some ports were visited multiple times, with the exception of Surabaya, which served as the home base for a fleet of 15 vessels. The average trip duration was approximately 35 days. Through experimentation, it was determined that employing 1,000 generations along with a mutation probability of 0.2 produces improved solutions. The Genetic Algorithm solution enhanced the average vessel capacity utilization, increasing it to 80.93%. This represents a significant 21.23% increase compared to the global average of 59.7% observed for similar vessel usage scenarios. Conclusions: Furthermore, through the introduction of novel route opportunities, the contributions of each vessel were effectively enhanced. This achievement resulted in an optimal average vessel capacity utilization that met the demand. The findings strongly advocate for the employment of the Genetic Algorithm, highlighting its potential to substantially improve vessel capacity utilization. Consequently, this approach has played a pivotal role in elevating the efficiency of transportation and logistics operations for Company X.

Słowa kluczowe

EN

vehicle routing problem; simultaneous deliveries and pickups; split loads; time windows; optimization; genetic algorithm

PL

problem z trasą pojazdu; jednoczesne dostawy i odbiory; dzielenie obciążeń; okna czasowe; optymalizacja; algorytm genetyczny

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2023
• Tom: Vol. 19, no. 4
• Strony: 577--593
• Opis fizyczny: Bibliogr. 20 poz., rys., tab., wykr.

Twórcy

autor

Ferdianti Shea Amanda

• Department of Industrial Engineering, Faculty of Industrial Technology Petra Christian University, East Java, Indonesia

autor

Widyadana I Gede Agus

• Department of Industrial Engineering, Faculty of Industrial Technology Petra Christian University, East Java, Indonesia

• https://orcid.org/0000-0001-9129-7468

Bibliografia

• 1. Arnold, F., Sörensen, K., 2019. What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Computers & Operations Research, 106, 280-288. https://doi.org/10.1016/j.cor.2018.02.007.
• 2. Cheng, C.-B., Wang, K.-P., 2009. Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm. Expert Systems with Applications, 36, 7758-7763. https://doi.org/10.1016/j.eswa.2008.09.001.
• 3. Dantzig, G. B., Ramser, J. H., 1959. The truck dispatching problem. Management Science, 6(1), 80-91.
• 4. Dewi, S. K., Utama, D. M., 2021. A new hybrid whale optimization algorithm for the green vehicle routing problem. Systems Science & Control Engineering, 9, 61-72. https://doi.org/10.1080/21642583.2020.1863276.
• 5. Dror, M., Laporte, G., Trudeau, P., 1994. Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3), 239–254.
• 6. Dror, M., Trudeau, P., 1989. Savings by split delivery routing. Transportation Science, 23(2), 141–145.
• 7. Escobar-Falcón, L., Álvarez-Martínez, D., Wilmer-Escobar, J., Granada-Echeverri, M., 2021. A specialized genetic algorithm for the fuel consumption heterogeneous fleet vehicle routing problem with bidimensional packing constraints. International Journal of Industrial Engineering Computations, 12, 191-204. https://doi.org/10.5267/j.ijiec.2020.11.003.
• 8. Ho, W., Ho, G. T. S., Ji, P., Lau, H. C. W., 2008. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21, 548-557. https://doi.org/10.1016/j.engappai.2007.06.001.
• 9. Karakatič, S., 2021. Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm. Expert Systems with Applications, 164, 114039. https://doi.org/10.1016/j.eswa.2020.114039.
• 10. Liu, S., Huang, W., Ma, H., 2009. An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E: Logistics and Transportation Review, 45, 434-445. https://doi.org/10.1016/j.tre.2008.10.003.
• 11. Mohammed, M. A., Abd Ghani, M. K., Hamed, R. I., Mostafa, S. A., Ahmad, M. S., & Ibrahim, D. A., 2017. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science, 21, 255-262. https://doi.org/10.1016/j.jocs.2017.04.003.
• 12. Nazif, H., Lee, L. S., 2012. Optimized crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36, 2110-2117. https://doi.org/10.1016/j.apm.2011.08.010.
• 13. Oliveira da Costa, P. R. de, Mauceri, S., Carroll, P., Pallonetto, F., 2018. A genetic algorithm for a green vehicle routing problem. Electronic Notes in Discrete Mathematics, 64, 65-74. https://doi.org/10.1016/j.endm.2018.01.008.
• 14. Protopopova, J., Kulik, S., 2020. Educational intelligent system using genetic algorithm. Procedia Computer Science, 169, 168-172. https://doi.org/10.1016/j.procs.2020.02.130.
• 15. Saxena, R., Jain, M., Malhotra, K., Vasa, K. D., 2020. An optimized OpenMP-based genetic algorithm solution to the vehicle routing problem. In The Smart Computing Paradigms: New Progresses and Challenges (Vol. 767, pp. 237-245). https://doi.org/10.1007/978-981-13-9680-9_20.
• 16. Sitek, P., Wikarek, J., Rutczyńska-Wdowiak, K., Bocewicz, G., Banaszak, Z., 2021. Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach. Neurocomputing, 423, 670-678. https://doi.org/10.1016/j.neucom.2020.02.126.
• 17. Toth, P., Vigo, D., 2002. The vehicle routing problem. SIAM. http://dx.doi.org/10.1137/1.9780898718515
• 18. Utama, D. M., Dewi, S. K., Wahid, A., Santoso, I., 2020. The vehicle routing problem for perishable goods: A systematic review. Cogent Engineering, 7, 1816148. https://doi.org/10.1080/23311916.2020.1816148.
• 19. Visutarrom, T., Chiang, T., 2019. An evolutionary algorithm with heuristic longest cycle crossover for solving the capacitated vehicle routing problem. In IEEE Congress on Evolutionary Computation (CEC), 2019 (pp. 673-680). https://doi.org/10.1109/CEC.2019.8789946.
• 20. Wang, Y., Ma, X., Lao, Y., Wang, Y., Mao, H., 2013. Vehicle routing problem simultaneous deliveries and pickups with split loads and time windows. Transportation Research Record Journal of the Transportation Research Board, 2378, 120-128. https://doi.org/10.3141/2378-13

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).