Application of metaheuristics for multi-trip capacitated vehicle routing problem with time window

• Autorzy: Niyomphon Kantapong , Nakkiew Warisa

Identyfikatory

DOI

10.30657/pea.2024.30.30

• Języki publikacji: EN

Abstrakty

EN

This study focuses on the delivery routing problem faced by a transport company located in Phuket, Thailand. The goal of this study is to find a daily optimum route in order to minimize the total trans portation cost, which comprises fixed costs associated with vehicle rental and variable costs calculated based on factors of travel distance, fuel prices, and fuel consumption. The complexity of this problem is compounded by the fact that customer demand often exceeds a vehicle capacity, in terms of weight and volume. In addition, delivery must be made within specific time windows. To tackle this issue, the delivery routing problem is classified as a multi-trip capacitated vehicle routing problem with time window (MTCVRPTW). Since the problem is NP-hard, an application of metaheuristic is more prac tical to determine the delivery routing of the company within a reasonable computing time. In this study, Particle Swarm Optimization (PSO) and Differential Evolution (DE) algorithm are applied to solve MTCVRPTW. The numerical results show that DE provides better solution quality compared to those obtained from PSO and company current practices.

Słowa kluczowe

EN

vehicle routing problem; multi-trip; time window; particle swarm optimization; differential evolution

PL

problem z wyznaczaniem tras pojazdów; wielokrotna podróż; okno czasowe; optymalizacja roju cząstek; ewolucja różnicowa

• Wydawca: Oficyna Wydawnicza Stowarzyszenia Menedżerów Jakości i Produkcji
• Czasopismo: Production Engineering Archives
• Rocznik: 2024
• Tom: Vol. 30, Iss. 3
• Strony: 303--313
• Opis fizyczny: Bibliogr. 29 poz,. rys., tab.

Twórcy

autor

Niyomphon Kantapong

• Department of Industrial Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, Thailand

• https://orcid.org/0009-0002-3705-0135

autor

Nakkiew Warisa

• Department of Industrial Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, Thailand

• https://orcid.org/0000-0003-4515-3273

Bibliografia

• 1. Banomyong, R., Grant, D.B., Varadejsatitwong, P. and Julagasigorn, P., 2022. Developing and validating a national logistics cost in Thailand. Transport Policy, 124, 5-19. DOI:10.1016/j.tranpol.2021.04.026
• 2. Cattaruzza, D., Absi, N., Feillet, D., 2016. Vehicle routing problems with multiple trips. 4or, 14, 223-259. DOI:10.1007/s10288-016-0306-2
• 3. Clarke, G., Wright, J. W.,1964. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581. DOi:10.1287/opre.12.4.568
• 4. Du, L., He, R., 2012. Combining nearest neighbor search with tabu search for large-scale vehicle routing problem. Physics Procedia, 25, 1536-1546. DOI:10.1016/j.phpro.2012.03.273
• 5. Dumez, D., Lehuédé, F. and Péton, O., 2021. A large neighborhood search approach to the vehicle routing problem with delivery options. Transpor tation Research Part B: Methodological, 144, 103-132, DOI: 10.1016/j.trb.2020.11.012
• 6. Eraslan, E., Derya, T., 2010. Daily newspaper distribution planning with in teger programming: an application in Turkey. Transportation Planning and Technology, 33(5), 423-433. DOi: 10.1080/03081060.2010.502374
• 7. Geetha, S., Vanathi, P. T., Poonthalir, G., 2012. Metaheuristic approach for the multi-depot vehicle routing problem. Applied Artificial Intelligence, 26(9), 878-901. DOI: 10.1080/08839514.2012.727344
• 8. Hernandez, F., Feillet, D., Giroudeau, R., Naud, O., 2014. A new exact algorithm to solve the multi-trip vehicle routing problem with time win dows and limited duration. 4or, 12, 235-259. DOI: 10.1007/s10288-013 0238-z
• 9. Hu, F., Wu, F., 2010. Diploid hybrid particle swarm optimization with differ ential evolution for open vehicle routing problem. 2010 8th World Con gress on Intelligent Control and Automation, Jinan, 2692-2697.
• 10. Kumari, M., De, P. K., Chaudhuri, K., Narang, P., 2023. Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem. Re sults in Control and Optimization, 13, 100292. DOI: 10.1016/j.rico.2023.100292
• 11. Kachitvichyanukul, V., 2012. Comparison of three evolutionary algorithms: GA, PSO, and DE. Industrial Engineering and Management Systems, 11(3), 215-223. DOI: 10.7232/iems.2012.11.3.215
• 12. Lyu, J., He, Y., 2021. A two-stage hybrid metaheuristic for a low-carbon ve hicle routing problem in hazardous chemicals road transportation. Ap plied Sciences, 11(11), 4864. DOI: 10.3390/app11114864
• 13. Maffioli, F., 2003. The vehicle routing problem: A book review. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), 149-153. DOI: 10.1007/s10288-003-0013-7
• 14. Neira, D. A., Aguayo, M. M., De la Fuente, R., Klapp, M. A., 2020. New compact integer programming formulations for the multi-trip vehicle routing problem with time windows. Computers & Industrial Engineer ing, 144, 106399. DOI: 10.1016/j.cie.2020.106399
• 15. Marinakis, Y., Iordanidou, G. R., Marinaki, M., 2013. Particle swarm optimi zation for the vehicle routing problem with stochastic demands. Applied Soft Computing, 13(4), 1693-1704. DOI: 10.1016/j.asoc.2013.01.007
• 16. MirHassani, S. A., Abolghasemi, N., 2011. A particle swarm optimization al gorithm for open vehicle routing problem. Expert Systems with Applica tions, 38(9), 11547-11551. DOI: 10.1016/j.eswa.2011.03.032
• 17. Moghaddam, B. F., Ruiz, R., Sadjadi, S. J., 2012. Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Com puters & Industrial Engineering, 62(1), 306-317. DOI: 10.1016/j.cie.2011.10.001
• 18. Niyomphon, K., Wisittipanich, W., 2022. A Mathematical Model for Multi Trip Vehicle Routing Problem with Time Window in Transportation Business. ICLS2022 16th International Congress on Logistics and SCM System, Khon Kaen, Thailand, 94
• 19. Tang, J., Yu, Y., Li, J., 2015. An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport. Transportation Research Part E: Logistics and Transportation Review, 73, 114-132. DOI: 10.1016/j.tre.2014.11.001
• 20. Tirkolaee, E. B., Alinaghian, M., Hosseinabadi, A. A. R., Sasi, M. B., San gaiah, A. K., 2019. An improved ant colony optimization for the multi trip Capacitated Arc Routing Problem. Computers & Electrical Engineer ing, 77, 457-470. DOI: 10.1016/j.compeleceng.2018.01.040
• 21. Tirkolaee, E. B., Hosseinabadi, A. A. R., Soltani, M., Sangaiah, A. K., Wang, J., 2018. A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services. Sustainability, 10(5), 1366. DOI: 10.3390/su10051366
• 22. Theurich, F., Fischer, A., Scheithauer, G., 2021. A branch-and-bound ap proach for a Vehicle Routing Problem with Customer Costs. EURO Jour nal Computational Optimization, 9, 100003. DOi: 10.1016/j.ejco.2020.100003
• 23. Utamima, A., Pradina, K. R., Dini, N. S., Studiawan, H., 2015. Distribution route optimization of gallon water using genetic algorithm and tabu search. Procedia Computer 10.1016/j.procs.2015.12.132 Science, 72, 503-510. DOI:
• 24. Wisittipanich, W., Phoungthong, K., Srisuwannapa, C., Baisukhan, A., Wisit tipanit, N., 2021. Performance comparison between particle swarm opti mization and differential evolution algorithms for postman delivery rout ing problem. Applied Sciences, 11(6), 2703. DOI: 10.3390/app11062703
• 25. Wisittipanit, N., Baisukhan, A., Srisuwannapa, C., 2021. Comparisons of VRP Optimization Algorithmic Methods for the Optimal Routing of Mul tiple Delivery Vehicles with Time Constraint. International Journal of Engineering Sciences, 13(4), 131-140. DOI: 10.36224/ijes.130401
• 26. Xu, S. H., Liu, J. P., Zhang, F. H., Wang, L., Sun, L. J., 2015. A combination of genetic algorithm and particle swarm optimization for vehicle routing problem with time windows. Sensors, 15(9), 21033-21053. DOI: 10.3390/s150921033
• 27. Yağmur, E., Kesen, S. E., 2021. Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: Memetic algorithm and simulated annealing approaches. Computers & Industrial Engineering, 161, 107649. DOI: 10.1016/j.cie.2021.107649
• 28. Yeh, W. C., Tan, S. Y., 2021. Simplified swarm optimization for the hetero geneous fleet vehicle routing problem with time-varying continuous speed function. Electronics, 10(15), 1775. DOI: 10.3390/electron ics10151775
• 29. Zhen, L., Ma, C., Wang, K., Xiao, L., Zhang, W., 2020. Multi-depot multi trip vehicle routing problem with time windows and release dates. Trans portation Research Part E: Logistics and Transportation Review, 135, 101866. DOI: 10.1016/j.tre.2020.101866

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 i promocja sportu (2025).