Multi-criteria vehicle routing problem for a real-life parcel locker-based delivery

• Autorzy: Idzikowski Radosław , Rudy Jarosław , Jaroszczuk Michał

Identyfikatory

DOI

10.24425/ijet.2025.153624

• Języki publikacji: EN

Abstrakty

EN

In this paper, a multi-criteria Vehicle Routing Problem with distance and capacity constraints for modelling a delivery system with parcel locker, is considered. The problem is formulated and two optimization criteria are defined. The first criterion minimizes the total travel time of all vehicles and the second criterion minimizes the total penalty for late delivery of orders. Three solving methods, relying on the concept of Pareto-optimality, are proposed: a greedy constructive heuristic, a Tabu Search metaheuristic and a Genetic Algorithm. A number of benchmark instances are created using real-life parcel locker locations and traveling times, from one of the major cities in Poland. In preliminary research, sorting strategies for the greedy method are tested, with the sorting based on deadline-arrival difference to priority ratio yielding the best performance in all tested cases. Next, computer experiments are performed to evaluate the quality of the proposed methods, using the concept of Hypervolume Indicator. Results confirm that both Tabu Search and Genetic Algorithm significantly improve the solution provided by the greedy algorithm, with Genetic Algorithm being the most effective on average. However, results also indicate that both Tabu Search and Genetic Algorithm have different effectiveness in different cases. It is concluded that the best performance is achieved by both algorithms being used in parallel, complementing each other.

Słowa kluczowe

EN

Vehicle Routing Problem; parcel lockers; multicriteria optimization; operations research; Pareto optimality; metaheuristics

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 3
• Strony: 17
• Opis fizyczny: Bibliogr. 25 poz., rys., tab.

Twórcy

autor

Idzikowski Radosław

• Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, Poland

• https://orcid.org/0000-0001-5232-1998

autor

Rudy Jarosław

• Department of Control Systems and Mechatronics, Wrocław University of Science

• https://orcid.org/0000-0003-1095-6041

autor

Jaroszczuk Michał

• Department of Control Systems and Mechatronics, Wrocław Universitet of Technology

• https://orcid.org/0009-0009-8617-889X

Bibliografia

• [1] M. Mohammadi, G. Rahmanifar, M. Hajiaghaei-Keshteli, G. Fusco, C. Colombaroni, and A. Sherafat, “A dynamic approach for the multi-compartment vehicle routing problem in waste management,” Renewable and Sustainable Energy Reviews, vol. 184, p. 113526, 2023. [Online]. Available: https://doi.org/10.1016/j.rser.2023.113526
• [2] M. Eusébio, T. Pinto, and M. Vieira, “The consistent vehicle routing problem: An application to the pharmaceutical supply chain,” in Optimization, Learning Algorithms and Applications, A. I. Pereira, A. Mendes, F. P. Fernandes, M. F. Pacheco, J. P. Coelho, and J. Lima, Eds. Cham: Springer Nature Switzerland, 2024, pp. 424-437.
• [3] C. Gracia, B. Velázquez-Martí, and J. Estornell, “An application of the vehicle routing problem to biomass transportation,” Biosystems Engineering, vol. 124, pp. 40-52, 2014. [Online]. Available: https://doi.org/10.1016/j.biosystemseng.2014.06.009
• [4] E. Ayyıldız, M. C. S¸ ahin, and A. Tas¸kın, “A multi depot multi product split delivery vehicle routing problem with time windows: A real cash in transit problem application in istanbul, turkey,” Journal of Transportation and Logistics, vol. 7, no. 2, pp. 213-232, 2023. [Online]. Available: https://doi.org/10.26650/JTL.2022.1113726
• [5] A. Sadeghi, F. Aros-Vera, H. Mosadegh, and R. YounesSinaki, “Social cost-vehicle routing problem and its application to the delivery of water in post-disaster humanitarian logistics,” Transportation Research Part E: Logistics and Transportation Review, vol. 176, p. 103189, 2023. [Online]. Available: https://doi.org/10.1016/j.tre.2023.103189
• [6] J. Wen and L. Yisong, “Vehicle routing optimization of urban distribution with self-pick-up lockers,” IEEE, pp. 1-6, 2016. [Online]. Available: https://doi.org/10.1109/LISS.2016.7854384
• [7] H. Abdullahi, L. Reyes-Rubiano, D. Ouelhadj, J. Faulin, and A. A. Juan, “Modelling and multi-criteria analysis of the sustainability dimensions for the green vehicle routing problem,” European Journal of Operational Research, vol. 292, pp. 143-154, 2021. [Online]. Available: https://doi.org/10.1016/j.ejor.2020.10.028
• [8] B. Gulmez, M. Emmerich, and Y. Fan, “Multi-objective optimization for green delivery routing problems with flexible time windows,” Applied Artificial Intelligence, vol. 38, 2024. [Online]. Available: https://doi.org/10.1080/08839514.2024.2325302
• [9] G. Srivastava, A. Singh, and R. Mallipeddi, “NSGA-II with objective-specific variation operators for multiobjective vehicle routing problem with time windows,” Expert Systems With Applications, vol. 176, p. 114779, 2021. [Online]. Available: https://doi.org/10.1016/j.eswa.2021.114779
• [10] J. Duan, Z. He, and G. G. Yen, “Robust multiobjective optimization for vehicle routing problem with time windows,” Transactions on Cybernetics, vol. 52, pp. 8300-8314, 2022. [Online]. Available: https://doi.org/10.1109/tcyb.2021.3049635
• [11] I. Orenstein, T. Raviv, and E. Sadan, “Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis,” EURO Journal on Transportation and Logistics, vol. 8, pp. 683-711, 2019. [Online]. Available: https://doi.org/10.1007/s13676-019-00144-7
• [12] W. Li, L. Kunpeng, P. N. R. Kumar, and Q. Tian, “Simultaneous product and service delivery vehicle routing problem with time windows and order release dates,” Applied Mathematical Modelling, vol. 89, pp. 669-687, 2021. [Online]. Available: https://doi.org/10.1016/j.apm.2020.07.045
• [13] B. Pan, Z. Zhang, and A. Lim, “Multi-trip time-dependent vehicle routing problem with time windows,” European Journal of Operational Research, vol. 291, pp. 218-231, 2021. [Online]. Available: https://doi.org/10.1016/j.ejor.2020.09.022
• [14] T. Cokyasar, A. Subramanyam, and O. Sahin, “Time-constrained capacitated vehicle routing problem in urban e-commerce delivery,” Transportation Research Record: Journal of the Transportation Research Board, vol. 2677, pp. 190-203, 2022. [Online]. Available: https://doi.org/10.1177/03611981221124592
• [15] J. Grabenschweiger, K. F. Doerner, R. F. Hartl, and M. W. P. Savelsbergh, “The vehicle routing problem with heterogeneous locker boxes,” Central European Journal of Operations Research, vol. 29, pp. 113-142, 2021. [Online]. Available: https://doi.org/10.1007/s10100-020-00725-2
• [16] R. Idzikowski, J. Rudy, and M. Jaroszczuk, “Solving a vehicle routing problem for a real-life parcel locker-based delivery,” in International Conference on Dependability of Computer Systems. Springer, 2024, pp. 69-79.
• [17] C.-L. Hwang and K. Yoon, Multiple Attribute Decision Making: Methods and Applications A State-of-the-Art Survey. Springer Berlin, Heidelberg, 1981.
• [18] R. Idzikowski, J. Rudy, and A. Gnatowski, “Solving non-permutation flow shop scheduling problem with time couplings,” Applied Sciences, vol. 11, no. 10, 2021. [Online]. Available: https://doi.org/10.3390/app11104425
• [19] J. L. Viegas, S. M. Vieira, E. M. P. Henriques, and J. M. C. Sousa, “A tabu search algorithm for the 3d bin packing problem in the steel industry,” in CONTROLO’2014 - Proceedings of the 11th Portuguese Conference on Automatic Control, A. P. Moreira, A. Matos, and G. Veiga, Eds. Cham: Springer International Publishing, 2015, pp. 355-364.
• [20] N. M. Razali, “An efficient genetic algorithm for large scale vehicle routing problem subject to precedence constraints,” Procedia-Social and Behavioral Sciences, vol. 195, pp. 1922-1931, 2015.
• [21] H. Park, D. Son, B. Koo, and B. Jeong, “Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm,” Expert Systems with Applications, vol. 165, p. 113959, 2021.
• [22] X. Xia, H. Qiu, X. Xu, and Y. Zhang, “Multi-objective workflow scheduling based on genetic algorithm in cloud environment,” Information Sciences, vol. 606, pp. 38-59, 2022.
• [23] D. Luxen and C. Vetter, “Real-time routing with OpenStreetMap data,” in Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ser. GIS ’11. New York, NY, USA: ACM, 2011, pp. 513-516. [Online]. Available: https://doi.org/10.1145/2093973.2094062
• [24] [hidden for review], “Github repository,” 2024, accessed on 04.10.2024. [Online]. Available: [hidden-for-review]
• [25] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257-271, 1999. [Online]. Available: https://doi.org/10.1109/4235.797969

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).