1. На главную
  2. Электронные версии
  3. Известия РАН. Теория и системы управления
  4. № 5, 2023

Известия РАН. Теория и системы управления, 2023, № 5, стр. 103-126

МОДЕЛИ И АЛГОРИТМЫ МНОГОАГЕНТНОЙ ИЕРАРХИЧЕСКОЙ МАРШРУТИЗАЦИИ С ВРЕМЕННЫМИ ОКНАМИ

М. Г. Козлова a, *, Д. В. Лемтюжникова b, c, **, В. А. Лукьяненко a, ***, О. О. Макаров a, ****

a ФГАОУ ВО “Крымский федеральный университет им. В.И. Вернадского”,
Симферополь, Россия

b ИПУ им. В.А. Трапезникова РАН
Москва, Россия

c Московский авиационный институт (национальный исследовательский ун-т)
Москва, Россия

* E-mail: art-inf@mail.ru
** E-mail: darabbt@gmail.com
*** E-mail: art-inf@yandex.ru
**** E-mail: fantom2.00@mail.ru

Поступила в редакцию 28.03.2023
После доработки 18.04.2023
Принята к публикации 05.06.2023

Аннотация

Рассматривается задача моделирования реальных логистических систем, устроенных иерархическим образом. Формируются кластеры потребителей нижнего уровня, отвечающие ограничениям временных окон для каждого потребителя и кластера в целом. На каждом таком кластере строится маршрут агента-коммивояжера и выделяется вершина, наиболее близкая к центральному узлу, которая является вершиной перегрузки товара с большегрузных транспортных средств на малогрузные транспортные средства, обслуживающие кластеры потребителей. Вершины перевалки, в свою очередь, объединяются в маршруты коммивояжера более высокого уровня с учетом временных окон для маршрутов этого уровня. Программная реализация тестируется на известных сетях. Методика применима для синтеза центрального распределительного центра и системных распределительных центров нижнего уровня, а также для расчета необходимого числа транспортных средств (агентов).

Список литературы

  1. Liu F., Lu Ch., Gui L., Zhang Q., Tong X., Yuan M. Heuristics for Vechicle Ruoting Problem: a Survey and Recent Advance. 2023. arXiv:2303.04147v1 [cs.AI]. https://doi.org/10.48550/arXiv.2303.04147.

  2. Tan S.-Y., Yen W.-C. The Vehicle Routing Problem: State-of-the-Art Classification and Review // Applied Sciences. 2021. V. 11 (21). P. 10295. https://doi.org/10.3390/app112110295

  3. Li H., Wang H., Chen J., Bai M. Two-Echelon Vehicle Routing Problem with Satellite Bi-Synchronization // European J. Operational Research. 2020. V. 288 (3). https://doi.org/10.1016/j.ejor.2020.06.019

  4. Baldacci R., Mingozzi A., Roberti R., Clavo R. An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem // Operation Research. 2013. V. 61 (2). P. 298–314. https://doi.org/10.1287/opre.1120.1153

  5. Xiaobing G., Wang Y., Li Sh., Niu B. Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pick-Up Service Based on MCPSO // Mathematical Problems in Engineering. 2012. V. 2. https://doi.org/10.1155/2012/104279

  6. Fisher M.L. Optimal Solution of  Vehicle Routing Problems Using Minimum K-trees // Operations Research. 1994. V. 42 (2). P. 626–642.

  7. Kallehauge B., Larsen J., Madsen O., Solomon M. Vehicle Routing Problem with Time Windows // Column Generation. Springer US, 2006. https://doi.org/10.1007/0-387-25486-2_3

  8. Macedo R., Alves C., Carvalho J., Clautiaux F., Hanafi S. Solving the Vehicle Routing Problem with Time Windows and Multiple Routes Exactly Using a Pseudo-polynomial Model // European J. Operational Research. 2011. V. 214 (3). P. 536–545. https://doi.org/10.1016/j.ejor.2011.04.037

  9. Zhang W., Yang D., Zhang G., Gen M. Hybrid Multiobjective Evolutionary Algorithm with Fast Sampling Strategy-Based Global Search and Route Sequence Difference-Based Local Search for VRPTW // Expert Systems with Applications. 2020. V. 145. https://doi.org/10.1016/j.eswa.2019.113151

  10. Mahmoud M., Hedar A.-R. Three Strategies Tabu Search for Vehicle Routing Problem with Time Windows // Computer Science and Information Technology. 2014. V. 2 (2). P. 108–119. https://doi.org/10.13189/csit.2014.020208

  11. Solomon benchmark. URL: https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark/.

  12. Zhou Z., Ma X., Liang Z., Zhu Z. Multi-objective Multi-factorial Memetic Algorithm Based on Bone Route and Large Neighborhood Local Search for VRPTW // IEEE Congress on Evolutionary Computation (CEC). Glasgow, United Kingdom, 2020. https://doi.org/10.1109/CEC48606.2020.9185528.

  13. Shu H., Zhou H., He Z., Hu X. Two-Stage Multi-objective Evolutionary Algorithm Based on Classified Population for Tri-objective VRPTW // International J. Unconventional Computing. 2021. V. 16 (2–3). P. 141–171.

  14. Xu W., Wang X., Guo Q. Gathering Strength, Gathering Storms: Knowledge Transfer via Selection for VRPTW // Mathematics. 2022. V. 10 (16). https://doi.org/10.3390/math10162888

  15. Fan H., Ren X., Zhang Y. A Chaotic Genetic Algorithm with Variable Neighborhood Search for Solving Time-Dependent Green VRPTW with Fuzzy Demand // Symmetry. 2022. V. 14 (10). https://doi.org/10.3390/sym14102115

  16. Nasri M., Hafidi I., Metrane A. Multithreading Parallel Robust Approach for the VRPTW with Uncertain Service and Travel Times // Symmetry. 2020. V. 13 (1). https://doi.org/10.3390/sym13010036

  17. Kummer A.F., Buriol L.S., de Araújo O.C.B. A Biased Random Key Genetic Algorithm Applied to the VRPTW with Skill Requirements and Synchronization Constraints // GECCO’20: Genetic and Evolutionary Computation Conf. Cancun, Mexico, 2020. https://doi.org/10.1145/3377930.3390209

  18. Jungwirth A., Frey M., Kolisch R. The Vehicle Routing Problem with Time Windows, Flexible Service Locations and Time-Dependent Location Capacity, 2020. URL: https://www.semanticscholar.org/paper/The-vehicle-routing-problem-with-time-windows%2C-and-Jungwirth-Frey/22db87ca3cba4ea33561667c190f0443a93925bf.

  19. Poullet J. Leveraging Machine Learning to Solve the Vehicle Routing Problem with Time Windows, 2020. URL: https://hdl.handle.net/1721.1/127285.

  20. Figliozzi M.A. An Iterative Construction and Improvement Algorithm for the Vehicle Routing Problem with Soft Time Windows // Transp. Res. P. C. Emerg. Technol. 2010. V. 18 (5). https://doi.org/10.1016/j.trc.2009.08.005

  21. Melnikov A.N., Lyubimov I.I., Manayev K.I. Improvement of the Vehicles Fleet Structure of a Specialized Motor Transport Enterprise // Proc. Eng. 2016. V. 150. P. 1200–1208. https://doi.org/10.1016/j.proeng.2016.07.236

  22. Германчук М.С., Козлова М.Г., Лукьяненко В.А. Модели обобщенных задач коммивояжера в интеллектуализации поддержки принятия решений для геоинформационных систем // Географические и геоэкологические исследования на Украине и сопредельных территориях: сб. научных статей / Под общ. ред. Б.А. Вахрушева. Симферополь: ДИАЙПИ, 2013. Т. 1. С. 413–415.

  23. Rakhmangulov A., Kolga A., Osintsev N. Mathematical Model of Optimal Empty Rail Car Distribution at Railway Transport Nodes // Transp. Probl. 2014. V. 9 (3). P. 19–32.

  24. Uthayakumar R., Prlyan S. Pharmaceutical Supply Chain and Inventory Management Strategies: Optimization for a Pharmaceutical Company and a Hospital // Oper. Res. Heal Care. 2013. V. 2 (3). P. 52–64. https://doi.org/10.1016/j.orhc.2013.08.001

  25. Azzi A., Sgarbossa F., Bonin M. Drug Inventory Management And Distribution: Outsourcing Logistics to Third-Party Providers // Strateg Outsourcing Int. J. 2013. V. 6 (1). P. 48–64. https://doi.org/10.1108/17538291311316063

  26. French Ch., Smykay E.W., Bowersox D.J., Mossman F.H. Physical Distribution Management // Amer. J. Agric. Econ. 1961. V. 43 (3). P. 728–30.

  27. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Neural Networks. 1997. V. 1 (1). P. 53–66. https://doi.org/10.1109/4235.585892

  28. Dorigo M., Gambardella L.M. Ant Colonies for the Traveling Salesman Problem // BioSystems. 1997. V. 43. P. 73–81. https://doi.org/10.1016/S0303-2647(97)01708-5

  29. Stützle T. Local Search Algorithms for Combinatorial Problems – Analysis, Improvements, and New Applications // Dissertation. Germany, 1998. URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1869&rep=rep1&type=pdf

  30. Kohl N., Desrosiers J., Madsen O.B.G., Solomon M.M., Soumis F. 2-Path Cuts for the Vehicle Routing Problem with Time Windows // Transportation Science. 1999. V. 33. P. 101–116. https://doi.org/10.1287/trsc.33.1.101

  31. Taillard É.D. FANT: Fast Ant System // Technical Report. Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale. Lugano.1998.

  32. Badeau P., Gendreau M., Guertin F., Potvin J.-Y., Taillard É.D. A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows // Transp. Res. P. C. Emerg. Technol. 1997. V. 5 (2). P. 109–122. https://doi.org/10.1016/S0968-090X(97)00005-3

  33. Taillard É.D., Badeau P., Gendreau M., Guertin F., Potvin J.-Y.  A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows // Transportation Science. 1997. V. 31. P. 170–186.

  34. Kilby P., Prosser P., Shaw P. Guided Local Search for the Vehicle Routing Problem with Time Windows // Meta-Heuristics. Springer, Boston, MA, 1999. https://doi.org/10.1007/978-1-4615-5775-3_32

  35. Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems // Fourth Intern. Conf. on Principles and Practice of Constraint Programming, Springer-Verlag, 1998. P. 417–431.

  36. Dorigo M., Maniezzo V., Colorni A. Positive Feedback as a Search Strategy // Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991. URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.6342&rep=rep1&type=pdf.

  37. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a Colony of Cooperating Agents // IEEE Transactions on Systems, Man, and Cybernetics. 1996. V. 26 (1). P. 29–41. https://doi.org/10.1109/3477.484436

  38. Flood M.M. The Traveling Salesman Problem // Operations Research. 1956. V. 4. P. 61–75.

  39. Germanchuk M.S., Lukianenko V.A., Lemtyuzhnikova D.V. Metaheuristic Algorithms for Multiagent Routing Problems // Automation and Remote Control. 2021. V. 82 (10). P. 1787–1801. .https://doi.org/10.1134/S0005117921100155

  40. Scipy. URL: https://scipy.org/.

  41. Concorde TSP Solver. URL: https://www.math.uwaterloo.ca/tsp/concorde.html.

  42. PyConcorde. URL: https://github.com/jvkersch/pyconcorde.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Известия РАН. Теория и системы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал