Исследование генетического алгоритма решения задачи множественной маршрутизации транспортных средств с чередованием объектов двух типов

В статье рассматривается задача маршрутизации нескольких транспортных средств, особенностью которой является требование чередования объектов двух видов в результирующих маршрутах. При этом объекты загрузки должны быть обязательно посещены ровно один раз, а центры разгрузки могут входить в маршруты транспортных средств неограниченное число раз. Необходимо минимизировать максимальную из длин маршрутов транспортных средств, то есть, другими словами, сократить разброс длин полученных маршрутов. Для решения поставленной задачи предлагается использовать генетический алгоритм. С этой целью способ построения хромосом, операторы отбора особей, скрещивания и мутации модернизируются с учетом специфики задачи, причем каждая хромосома включает маршруты всех транспортных средств. Основная часть статьи посвящена исследованию и настройке параметров предложенного алгоритма решения. Для разных размерностей решаемых задач оцениваются длины полученных маршрутов транспортных средств в зависимости от размера популяции, числа итераций алгоритма, а также значения коэффициента мутации. На основе проведенного исследования разработаны рекомендации по применению предложенного алгоритма в рамках поставленной задачи. Также проводится оценка работоспособности и результативности алгоритма в сравнении с точным методом решения. Показано, что предложенный алгоритм позволяет получать решения, близкие к оптимальному, за существенно меньшее время.

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. Головцов Д.Л. Задача маршрутизации судов с различной грузоподъёмностью морского транспортного комплекса арктической зоны России. Вестник государственного университета морского и речного флота им. адмирала С.О. Макарова. 2015;(6):85–92.

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. Гвоздев Л.Р., Медведева Т.А. Решение задачи маршрутизации транспортных средств с временными окнами с помощью алгоритма муравьиных колоний. Молодой исследователь Дона. 2022;(3):58–61.

8. Долгова О.Э., Пересветов В.В. Муравьиный алгоритм с ослаблением ограничений по временным окнам в решении задачи маршрутизации транспорта. Вычислительные технологии. 2018;23(5):49–62. 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. Медведев С.Н. Математическая модель и алгоритм решения задачи маршрутизации транспортных средств с несколькими центрами с чередованием и единым местом сбора. Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2021;(1):21–32. 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