Geodesic
The choice of algorithms for solving a multi-agent routing problem based on solving related problems
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 3, pp. 449-465 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper considers the problem of reducing the complexity of $NP$-hard problems by using related problems for which an optimal or acceptable solution is already known. For multi-agent routing tasks, a technique is used based on network clustering consistent with traveling salesman routes on each cluster and constructing routes that take into account the limitation of delivery time windows. A mathematical model is presented that corresponds to a block of pseudo-Boolean conditional optimization with constraints in the form of disjunctive normal forms that allows polynomial solvability and a block of time constraints. The results of choosing metaheuristics based on related problems are used in a program for the delivery of goods by many agents to consumers located at the vertices of the regional infrastructure road network.
Keywords: multi-agent traveling salesman problem, time windows, metaheuristics, applied routing problem 
@article{VUU_2024_34_3_a8,
     author = {M. G. Kozlova and V. A. Lukyanenko and O. O. Makarov},
     title = {The choice of algorithms for solving a multi-agent routing problem based on solving related problems},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {449--465},
     year = {2024},
     volume = {34},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2024_34_3_a8/}
}
TY  - JOUR
AU  - M. G. Kozlova
AU  - V. A. Lukyanenko
AU  - O. O. Makarov
TI  - The choice of algorithms for solving a multi-agent routing problem based on solving related problems
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2024
SP  - 449
EP  - 465
VL  - 34
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VUU_2024_34_3_a8/
LA  - ru
ID  - VUU_2024_34_3_a8
ER  - 
%0 Journal Article
%A M. G. Kozlova
%A V. A. Lukyanenko
%A O. O. Makarov
%T The choice of algorithms for solving a multi-agent routing problem based on solving related problems
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2024
%P 449-465
%V 34
%N 3
%U http://geodesic.mathdoc.fr/item/VUU_2024_34_3_a8/
%G ru
%F VUU_2024_34_3_a8
M. G. Kozlova; V. A. Lukyanenko; O. O. Makarov. The choice of algorithms for solving a multi-agent routing problem based on solving related problems. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 3, pp. 449-465. http://geodesic.mathdoc.fr/item/VUU_2024_34_3_a8/

[1] Kozlova M.G., Lemtyuzhnikova D.V., Luk’yanenko V.A., Makarov O.O., “Models and algorithms for multiagent hierarchical routing with time windows”, Journal of Computer and Systems Sciences International, 62:5 (2023), 862–883 | DOI

[2] Kozlova M.G., Lukianenko V.A., Makarov O.O., “Multi-agent route planning in hierarchical networks”, Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies, 2023, no. 3, 32–50 (in Russian) | DOI

[3] Lemtyuzhnikova D.V., Luk’yanenko V.A., “Problems of studying difficult problems”, Intellektualizatsiya obrabotki informatsii (Tezisy dokladov 14 Mezhdunarodnoi konferentsii, Moscow 2022), Russian Academy of Sciences, Moscow, 2022, 437–442 (in Russian) http://www.machinelearning.ru/wiki/images/f/ff/Idp22.pdf | MR

[4] Bondarenko V.A., Maksimenko A.N., Geometric constructions and complexity in combinatorial optimization, LKI, Moscow, 2008

[5] Deza M.M., Laurent M., Geometry of cuts and metrics, Springer, Berlin, 1997 | DOI | MR | Zbl

[6] Gale D., “Neighboring vertices on a convex polyhedron”, Linear inequalities and related systems, Princeton University Press, Princeton, 1956, 255–263 | DOI | MR

[7] Zhuravlev Yu.I., Selected scientific works, Magistr, Moscow, 1998

[8] Emel’yanov S.V., Korovin S.K., Bobylev N.A., Bulatov A.V., Homotopies of extremal problems, Nauka, Moscow, 2001 | MR

[9] Lazarev A.A., Lemtyuzhnikova D.V., Werner F., “A metric approach for scheduling problems with minimizing the maximum penalty”, Applied Mathematical Modelling, 89, part 2 (2021), 1163–1176 | DOI | MR | Zbl

[10] Gakhov F.D., Cherskii Yu.I., Convolution type equations, Nauka, Moscow, 1978 | MR

[11] Belozub V., Kozlova M., Lukianenko V., “Approximated solution algorithms for Urysohn-type equations”, Journal of Physics: Conference Series, 1902:1 (2021), 01251 | DOI

[12] Petrovskii A.B., Spaces of sets and multisets, Editorial URSS, Moscow, 2003

[13] Makarov O.O., “Metaheuristics in related routing problems such as many traveling salesmen”, Tavricheskii Vestnik Informatiki i Matematiki, 2022, no. 3(56), 80–102 (in Russian) https://tvim.su/node/1134

[14] Burkhovetskii V.V., “Optimization and parallelization of simplified Balas’ and Christofides’ algorithm for the Traveling Salesman Problem”, Program Systems: Theory and Applications, 11:4(47) (2020), 3–16 (in Russian) | DOI

[15] Solomon benchmark https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark

[16] TSPLIB http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95

[17] Fan Hao, Ren Xiaoxue, Zhang Yueguang, Zhen Zimo, Fan Houming, “A chaotic genetic algorithm with variable neighborhood search for solving time-dependent Green VRPTW with fuzzy demand”, Symmetry, 14:10 (2022), 2115 | DOI

[18] Germanchuk M.S., “Solvability of pseudobulous conditional optimization problems of the type of many salesmen”, Taurida Journal of Computer Science Theory and Mathematics, 2021, no. 4(49), 30–55 | DOI

[19] Ivanko E.E., Stability and instability in discrete problems, Russian Academy of Sciences, Ural Branch, Yekaterinburg, 2013

[20] Ivanko E.E., “Adaptive stability in combinatorial optimization problems”, Proceedings of the Steklov Institute of Mathematics, 288:suppl. 1 (2015), 79–87 | DOI | MR

[21] Kozlova M.G., Lukianenko V.A., Makarov O.O., Program for building hierarchical routes in routing tasks on complex networks No 2024614604, Certificate of state registration of the computer program No 2024615891 Russian Federation: application 05.03.2024: publ. 13.03.2024; applicant V.I. Vernadsky Crimean Federal University, 2024