Models and Algorithms for Multiagent Hierarchical Routing with Time Windows

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

The problem of modeling real logistics systems arranged in a hierarchical manner is considered. Clusters of lower level consumers are formed that meet the time window (TW) constraints for each consumer and the cluster as a whole. In each such cluster, a traveling salesman’s route is constructed and the vertex closest to the central node, which is the vertex of reloading goods from heavy vehicles (Vs) to light Vs serving consumer clusters, is selected. The transshipment vertices, in turn, are combined into higher level traveling salesmen’s routes, taking into account TWs for routes of this level. The software implementation is tested on well-known networks. The technique is applicable for the synthesis of the central distribution center and system distribution centers of the lower level, as well as for calculating the required number of vehicles (agents).

作者简介

M. Kozlova

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

Email: art-inf@mail.ru
Россия, Симферополь

D. Lemtyuzhnikova

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, 117997, Moscow, Russia; Moscow Aviation Institute (National Research University), 125993, Moscow, Russia

Email: darabbt@gmail.com
Россия, Москва; Россия, Москва

V. Luk’yanenko

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

Email: art-inf@yandex.ru
Россия, Симферополь

O. Makarov

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

编辑信件的主要联系方式.
Email: fantom2.00@mail.ru
Россия, Симферополь

参考

  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.

补充文件

附件文件
动作
1. JATS XML
下载
2.

下载 (58KB)
索引源数据
3.

下载 (104KB)
索引源数据
4.

下载 (256KB)
索引源数据
5.

下载 (239KB)
索引源数据
6.

下载 (177KB)
索引源数据
7.

下载 (131KB)
索引源数据
8.

下载 (213KB)
索引源数据
9.

下载 (203KB)
索引源数据
10.

下载 (209KB)
索引源数据
11.

下载 (204KB)
索引源数据
12.

下载 (206KB)
索引源数据
13.

下载 (204KB)
索引源数据
14.

下载 (266KB)
索引源数据
15.

下载 (239KB)
索引源数据
16.

下载 (299KB)
索引源数据
17.

下载 (220KB)
索引源数据
18.

下载 (377KB)
索引源数据
19.

下载 (298KB)
索引源数据

版权所有 © М.Г. Козлова, Д.В. Лемтюжникова, В.А. Лукьяненко, О.О. Макаров, 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

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

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».