The study of a genetic algorithm for solving the problem of multiple vehicle routing with alternating objects of two types

This article considers a multi-vehicle routing problem requiring alternating two types of objects in the resulting routes. Loading facilities must be visited exactly once, while unloading centers can be included in vehicle routes an unlimited number of times. It is necessary to minimize the maximum length of vehicle routes, or, in other words, to reduce the variance in the lengths of the resulting routes. A genetic algorithm is proposed for solving this problem. To this end, the chromosome construction method, individual selection operators, crossovers, and mutations are optimized to address the specifics of the problem, with each chromosome including the routes of all vehicles. The main part of the article is devoted to the study and tuning of the parameters of the proposed solution algorithm. For different problem dimensions, the lengths of the resulting vehicle routes are estimated depending on the population size, the number of algorithm iterations, and the mutation coefficient. Based on the conducted research, recommendations for applying the proposed algorithm to the given problem are developed. The algorithm's performance and effectiveness are also evaluated in comparison with an exact solution method. It is shown that the proposed algorithm allows obtaining solutions close to optimal in significantly less time.

1. El Bouyahyiouy K. The Selective Full Truckload Multi-Depot Vehicle Routing Problem with Time Windows: Formulation and a Genetic Algorithm. International Journal of Supply and Operations Management. 2022;9(3):299–320. https://doi.org/10.22034/ijsom.2022.109076.2168

2. Mbiadou Saleu R.G., Deroussi L., Feillet D., Grangeon N., Quilliot A. The Parallel Drone Scheduling Problem with Multiple Drones and Vehicles. European Journal of Operational Research. 2022;300(2):571–589. https://doi.org/10.1016/j.ejor.2021.08.014

3. Golovcov D.L. Vessels Routing Problem with Heterogeneous Fleetin Marine Transportation Complex Arctic Zone of Russia. Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova. 2015;(6):85–92. (In Russ.).

4. Lin Sh.-W., Yu V.F., Chou Sh.-Y. Solving the Truck and Trailer Routing Problem Based on a Simulated Annealing Heuristic. Computers & Operations Research. 2009;36(5):1683–1692. https://doi.org/10.1016/j.cor.2008.04.005

5. Semet F., Taillard E. Solving Real-Life Vehicle Routing Problems Efficiently Using Tabu Search. Annals of Operations Research. 1993;41(4):469–488. https://doi.org/10.1007/BF02023006

6. Villegas J.G., Prins Ch., Prodhon C., Medaglia A.L., Velasco N. A GRASP with Evolutionary Path Relinking for the Truck and Trailer Routing Problem. Computers & Operations Research. 2011;38(9):1319–1334. https://doi.org/10.1016/j.cor.2010.11.011

7. Gvozdev L.R., Medvedeva T.A. Solving the Problem of Vehicles Routing with Time Windows Using the Ant Colony Algorithm. Young Don Researcher. 2022;(3):58–61. (In Russ.).

8. Dolgova O.E., Peresvetov V.V. An Ant Colony Optimization Algorithm with Time Relaxed Window Constraints for Solving the Vehicle Routing Problem. Computational Technologies. 2018;23(5):49–62. (In Russ.). https://doi.org/10.25743/ICT.2018.23.5.005

9. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of Vehicle Routing and Scheduling Problems. Networks. 1981;11(2):221–227. https://doi.org/10.1002/net.3230110211

10. Posada A., Rivera J.C., Palacio J.D. Selective Vehicle Routing Problem: A Hybrid Genetic Algorithm Approach. In: Artificial Evolution: 14th International Conference, Évolution Artificielle, EA 2019, 29–30 October 2019, Mulhouse, France. Cham: Springer; 2020. P. 148–161. https://doi.org/10.1007/978-3-030-45715-0_12

11. Medvedev S.N., Medvedeva O.A., Zueva Y.R., Chernyshova G.D. Formulation and Algorithmization of the Interleaved Vehicle Routing Problem. In: Journal of Physics: Conference Series: Volume 1203: International Conference "Applied Mathematics, Computational Science and Mechanics: Current Problems", AMCSM 2018, 17–19 December 2018, Voronezh, Russia. Institute of Physics Publishing; 2019. https://doi.org/10.1088/1742-6596/1203/1/012053

12. Ghaziri H. Supervision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem. In: Meta-Heuristics: Theory and Applications. New York: Springer; 1996. P. 651–660. https://doi.org/10.1007/978-1-4613-1361-8_39

13. Mingozzi A., Bianco L., Ricciardelli S. Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints. Operations Research. 1997;45(3):365–377. https://doi.org/10.1287/opre.45.3.365

14. Medvedev S.N. A Mathematical Model and an Algorithm for Solving a Multi-Depot Vehicle Routing Problem with a Single End Point. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2021;(1):21–32. (In Russ.). https://doi.org/10.17308/sait.2021.1/3368

15. Medvedev S.N. Greedy and Adaptive Algorithms for Multi-Depot Vehicle Routing with Object Alternation. Automation and Remote Control. 2023;84(3):305–325. https://doi.org/10.1134/S0005117923030086