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

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

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

Об авторах

М. Г. Козлова

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

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

Д. В. Лемтюжникова

ИПУ им. В.А. Трапезникова РАН; Московский авиационный институт (национальный исследовательский ун-т)

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

В. А. Лукьяненко

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

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

О. О. Макаров

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

Автор, ответственный за переписку.
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.

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