Geodesic
The routing bottlenecks problem (optimization within zones)
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 2, pp. 267-285 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A minimax routing problem with decomposition elements is considered. In the simplest case, it is supposed that the whole set of tasks is divided into a sum of two subsets (clusters), and execution of tasks from the second subset can be started only after the completion of all tasks from the first subset. For above-mentioned two-cluster problem, an algorithm has been constructed for finding the optimal compositional solution, including a route (permutation of task indices) and a starting point, which is based on the use of a broadly understood dynamic programming. Based on this approach, an algorithm was also constructed to solve the routing problem in the case of an arbitrary ordered finite set of clusters. The algorithm was implemented on a PC, and a computational experiment was carried out. Possible applications may be associated with some logistics tasks in small aviation, when it is necessary to ensure visits to many points by one vehicle (airplane, helicopter) with a limited non-stop flight range.
Keywords: dynamic programming, precedence conditions
Mots-clés : route 
@article{VUU_2024_34_2_a5,
     author = {A. G. Chentsov and A. A. Chentsov and P. A. Chentsov},
     title = {The routing bottlenecks problem (optimization within zones)},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {267--285},
     year = {2024},
     volume = {34},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a5/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
AU  - P. A. Chentsov
TI  - The routing bottlenecks problem (optimization within zones)
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2024
SP  - 267
EP  - 285
VL  - 34
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a5/
LA  - ru
ID  - VUU_2024_34_2_a5
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%A P. A. Chentsov
%T The routing bottlenecks problem (optimization within zones)
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2024
%P 267-285
%V 34
%N 2
%U http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a5/
%G ru
%F VUU_2024_34_2_a5
A. G. Chentsov; A. A. Chentsov; P. A. Chentsov. The routing bottlenecks problem (optimization within zones). Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 2, pp. 267-285. http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a5/

[1] Gutin G., Punnen A.P., The traveling salesman problem and its variations, Springer, New York, 2007 | DOI | MR | Zbl

[2] Cook W.J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, Princeton, 2012 | MR | Zbl

[3] Gimadi E.Kh., Khachai M.Yu., Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016

[4] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[5] Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 (in Russian) | DOI | MR | Zbl

[6] Little J.D.C., Murty K.G., Sweeney D.W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[7] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl | Zbl

[8] Sergeev S.I., “Hybrid control systems and the dynamic traveling salesman problem”, Automation and Remote Control, 69:1 (2008), 42–51 | DOI | MR | Zbl

[9] Sergeev S.I., “Algorithms for the minimax problem of the traveling salesman. I: An approach based on dynamic programming”, Automation and Remote Control, 56:7, pt. 2 (1995), 1027–1032 | MR | Zbl | Zbl

[10] Chentsov A.G., Extreme problems of routing and distribution of tasks: theoretical questions, Regular and Chaotic Dynamics, Moscow–Izhevsk, 2008

[11] Petunin A.A., Chentsov A.G., Chentsov P.A., Optimal tool routing on CNC sheet cutting machines. Mathematical models and algorithms, Ural Federal University, Yekateriburg, 2020

[12] Chentsov A.G., Chentsov P.A., “Dynamic programming in the routing problem: decomposition variant”, Russian Universities Reports. Mathematics, 27:137 (2022), 95–124 (in Russian) | DOI | MR | Zbl

[13] Chentsov A.G., Chentsov P.A., “An extremal two-stage routing problem and procedures based on dynamic programming”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 28:2 (2022), 215–248 (in Russian) | DOI | MR

[14] Chentsov A.G., Chentsov P.A., “Two-stage dynamic programming in the routing problem with decomposition”, Automation and Remote Control, 84:5 (2023), 609–632 | DOI | MR | Zbl

[15] Chentsov A.G., Chentsov P.A., “Additive routing problem for a system of high-priority tasks”, Mathematical optimization theory and operations research: Recent trends, Springer, Cham, 2023, 218–230 | DOI | MR

[16] Chentsov A.G., “A bottleneck routing problem with a system of priority tasks”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 61 (2023), 156–186 (in Russian) | DOI | Zbl

[17] Chentsov A.G., Chentsov A.A., “Minimax routing problem with a system of priority tasks”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 62 (2023), 96–124 (in Russian) | DOI | MR

[18] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967 | MR

[19] Dieudonné J.A., Foundations of modern analysis, Academic Press, New York, 1960 | Zbl

[20] Cormen T.H., Leiserson C.E., Rivest R.L., Introduction to algorithms, Moscow Center for Continuous Mathematical Education, Moscow, 2000