МЕТОД РЕШЕНИЯ ПРОБЛЕМЫ МУЛЬТИ-КОММИВОЯЖЁРА В СРЕДЕ БЕЗ ПРЕПЯТСТВИЙ НА ОСНОВЕ УМЕНЬШЕНИЯ РАЗМЕРА ПРОСТРАНСТВА РЕШЕНИЙ
Аннотация
Проводится анализ проблемы мульти коммивояжера, которая в отличие от знаме-
нитой задачи коммивояжера, задействует несколько коммивояжёров, которые посещают
заданное количество городов ровно один раз и возвращаются в исходное положение с ми-
нимальными затратами на поездку. Задача мульти коммивояжера является важной для
области оптимизации маршрутов и распределения назначений между несколькими аген-
тами. Основной целью исследования является разработка эффективного метода решения
данной проблемы, который позволит сократить время выполнения задач и оптимизиро-
вать использование ресурсов. В ходе исследования был создан инновационный метод, осно-
ванный на уменьшении размерности пространства решений. Этот метод позволяет более
эффективно управлять нагрузкой и ресурсами, что в свою очередь способствует миними-
зации общего времени выполнения задач. Особенностью метода является его универсаль-
ность и применимость в различных сценариях, включая ситуации с разным количеством
задач и коммивояжеров. Такой подход обеспечивает более широкий охват и позволяет
оценить применимость метода в различных контекстах, что является важным преиму-
ществом данного исследования. Для оценки эффективности разработанного метода было
проведено сравнительное исследование с использованием классического метода решения
проблемы мульти коммивояжера. Оценка результатов осуществлялась на основе трех
ключевых критериев: вычислительного времени получения решения задачи мульти комми-
вояжера, суммарной длины пройденных маршрутов коммивояжерами и максимальной дли-
ны маршрута среди них. Анализ экспериментальных данных показал, что разработанный
метод значительно превосходит классический подход по всем рассматриваемым критери-
ям в большинстве экспериментов, так как при использовании предложенного метода сред-
нее время расчета для задачи мульти коммивояжера уменьшается на 56% по сравнению с
наилучшим известным классическим результатом, при этим средняя сумма длины прой-
денных маршрутов коммивояжерами соответственно уменьшается на 12% и максималь-
ная длина пути среди пройдённых агентами маршрутов (дисбаланс нагрузки) уменьшается
на 8%, что подтверждает высокую эффективность предложенного метода и перспек-
тивность для практического применения в различных сферах, где требуется оптимизация
маршрутов и распределения задач между несколькими исполнителями
Литература
2007.
2. Braekers K., Ramaekers K. Nieuwenhuyse I. The vehicle routing problem: State of the art classification
and review, Comput. Ind. Eng., 99.
3. Oncan T. A survey of the generalized assignment problem and its applications // INFOR:
Information Systems and Operational Research. – 2007. – Vol. 45. – P. 123-141.
4. Van Buer M.G., Woodru D.L., Olson R.T. Solving the medium newspaper production/distribution
problem // European Journal of Operational Research. – 1999. – 115. – P. 237-253.
5. Carter A.E., Ragsdale C.T. Scheduling pre-printed newspaper advertising inserts using genetic
algorithms // Omega. – 2002. – P. 415-421.
6. Kewei Huang, Dingwei Wang. Multiple traveling salesman problem and its application to hot
rolling planning // Application Research of Computers. – July 2007. – 24 (7). – P. 43-46.
7. Tang L., Liu J., Ronga А., Yang Z. A multiple traveling salesman problem model for hot rolling
schedule in Shanghai Baoshan Iron and Steel Complex // European Journal of Operational
Research. – 2000. – 124 (2). – P. 267-282.
8. Kim K.H., Park Y.M. A crane scheduling method for port container terminals // European
Journal of Operational Research. – 2004. – 156. – P. 752-768.
9. Sheldon H. Jacobson, Laura A. McLay, Shane N. Hall, Darrall Henderson, Diane E. Vaughan.
Optimal search strategies using simultaneous generalized hill climbing algorithms // Mathematical
and Computer Modelling. – 2006. – 43. – P. 1061-1073.
10. Evelyn C. Brown, Cliff T. Ragsdale, Arthur E. Carter. A grouping genetic algorithm for the
multiple traveling salesperson problem // International Journal of Information Technology &
Decision Making. – 2007. – Vol. 6, No. 2. – P. 333-347.
11. Harrath Y., Salman A.F., Alqaddoumi A., Hasan H., Radhi A. A novel hybrid approach for solving
the multiple traveling salesmen problem // Arab. J. Basic Appl. Sci. – 2019. – P. 103-112.
12. Gomes D.E., Iglésias M.I.D., Proença A.P., Lima T.M., Gaspar P.D. Applying a Genetic Algorithm
to a m-TSP: Case Study of a Decision Support System for Optimizing a Beverage Logistics
Vehicles Routing Problem // Electronics. – 2021.
13. Akbay M.A., Kalayci C.B. A Variable Neighborhood Search Algorithm for Cost-Balanced
Travelling Salesman Problem // In Proceedings of the Metaheuristics Summer School,
Taormina, Italy, 2018.
14. Muño -Herrera S., Suchan K. Constrained Fitness Landscape Analysis of Capacitated Vehicle
Routing Problems // Entropy. – 2022. – Vol. – P. 53.
15. Xu H.L., Zhang C.M. The research about balanced route MTSP based on hybrid algorithm // In
Proceedings of the 2009 International Conference on Communication Software and Networks,
Chengdu, China, 2009. – P. 533-536.
16. Khoufi I., Laouiti A., Adjih C. A Survey of Recent Extended Variants of the Traveling Salesman
and Vehicle Routing Problems for Unmanned Aerial Vehicles // Drones. – 2019. – Vol. 3.
– P. 66.
17. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. A Hybrid Approach GABC–
LS to Solve MTSP // In Proceedings of the Optimization, Learning Algorithms and Applications.
– Springer International Publishing: Cham, Switzerland, 2022. – P. 520-532.
18. Dorigo M., Birattari M., Stutzle T. Ant colony optimization // IEEE Comput. Intell. Mag.
– 2006. – P .28-39.
19. Zhan S.C., Xu J., Wu J. The optimal selection on the parameters of the ant colony algorithm //
Bull. Sci. Technol. – 2003. – P. 381-386.
20. Dorigo M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano,
Milano, Italy, 1992.
21. Gambardella L.M., Dorigo M. Ant-Q: A reinforcement learning approach to the traveling
salesman problem // In Machine Learning Proceedings. – Elsevier: Amsterdam, The Netherlands,
1995. – P. 252-260.
22. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem // Biosystems.
– 1997. – P. 73-81.
23. Bullnheimer B., Hartl R., Strauss C. A New Rank Based Version of the Ant System—A Computational
Study // Cent. Eur. J. Oper. Res. – 1999. – P. 25-38.
24. Guntsch M., Middendorf M. A population based approach for ACO // In Proceedings of the
Workshops on Applications of Evolutionary Computation, Kinsale, Ireland, 3–4 April 2002.
– Springer: Berlin/Heidelberg, Germany, 2002. – P. 72-81.
25. Blum C. Theoretical and Practical Aspects of Ant Colony Optimization. – IOS Press: Amsterdam,
The Netherlands, 2004. – Vol. 282.
26. Хуссейн Ф.А., Финаев В.И. Исследование эффективности алгоритма искусственных по-
тенциалов, муравьиного алгоритма и их комбинации при планировании траектории
движения мобильного робота // Компьютерные и информационные технологии в науке,
инженерии и управлении (КомТех-2020). – 2020. – С. 39-48.
27. Huang K.L., Liao C.J. Ant colony optimization combined with taboo search for the job shop
scheduling problem // Comput. Oper. Res. – 2008. – P. 1030-1046.
28. Xiao J., Li L. A hybrid ant colony optimization for continuous domains // Expert Syst. Appl.
– 2011. – P. 11072-11077.
29. Rahmani R., Yusof R., Seyedmahmoudian M., Mekhilef S. Hybrid technique of ant colony and
particle swarm optimization for short term wind energy forecasting // J. Wind. Eng. Ind.
Aerodyn. – 2013. – P. 163-170.
30. Lah Ivo. A new kind of numbers and its application in the actuarial mathematics // Boletim do
Instituto dos Actuários Portugueses. – 1954. – P. 7-15.
31. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. Ant-Balanced Multiple Traveling
Salesmen: ACO-BMTSP // Algorithms. – 2023. – P. 37.
