Models and Algorithms for Multiagent Hierarchical Routing with Time Windows

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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).

About the authors

M. G. Kozlova

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

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

D. V. 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. A. Luk’yanenko

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

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

O. O. Makarov

Vernadsky Crimean Federal University, 295007, Simferopol, Russia

Author for correspondence.
Email: fantom2.00@mail.ru
Россия, Симферополь

References

  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.

Supplementary files



Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies