Geodesic
Minimax routing problem with a system of priority tasks
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 62 (2023), pp. 96-124.

Voir la notice de l'article provenant de la source Math-Net.Ru

For a minimax routing problem with precedence conditions and cost functions that allow dependence on the list of tasks, we study the statement for which some of the tasks are allocated as first-priority ones. Other tasks can be started only after the fulfillment of priority tasks. The tasks themselves are connected with visiting megacities and, in particular, individual cities (terms corresponding to works in the field of solving the traveling salesman problem). One needs to find the extremum of arising two-stage problem with a minimax criterion, as well as the optimal compositional solution. In the paper, the optimal algorithm implemented on a PC is substantiated and built; a computational experiment is carried out. Possible applications may be related to some problems of aviation logistics in which it is required to ensure the visit of one vehicle (airplane or helicopter) to a system of aerodromes under a limited fuel reserve at each stage of the flight task; refueling is expected at points of visit (it is also assumed that a set of priority tasks is allocated).
Keywords: dynamic programming
Mots-clés : decomposition, route. 
@article{IIMI_2023_62_a7,
     author = {A. G. Chentsov and A. A. Chentsov},
     title = {Minimax routing problem with a system of priority tasks},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {96--124},
     publisher = {mathdoc},
     volume = {62},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2023_62_a7/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
TI  - Minimax routing problem with a system of priority tasks
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2023
SP  - 96
EP  - 124
VL  - 62
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2023_62_a7/
LA  - ru
ID  - IIMI_2023_62_a7
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%T Minimax routing problem with a system of priority tasks
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2023
%P 96-124
%V 62
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2023_62_a7/
%G ru
%F IIMI_2023_62_a7
A. G. Chentsov; A. A. Chentsov. Minimax routing problem with a system of priority tasks. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 62 (2023), pp. 96-124. http://geodesic.mathdoc.fr/item/IIMI_2023_62_a7/

[1] Chentsov A.G., Chentsov A.A., “Dynamic programming and questions of solvability of route bottleneck problem with resource constraints”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki, 32:4 (2022), 569–592 (in Russian) | DOI | MR | Zbl

[2] 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

[3] Chentsov A.G., Chentsov A.A., Sesekin A.N., “Dynamic programming in the task of a courier to bottlenecks with application in aviation logistics”, Management and processing of information in technical systems: Proceedings of the XVIII All-Russian scientific and practical conference and the XIV youth school-seminar (April 3–7, 2023, Dombai, Karachay-Cherkess Republic), Taganrog, 2023, 34–44

[4] Chentsov A.G., Chentsov P.A., “Dynamic programming in the routing problem: decomposition variant”, Vestnik Rossiiskikh Universitetov. Matematika, 27:137 (2022), 95–124 (in Russian) | DOI

[5] 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

[6] 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

[7] Chentsov A.G., Chentsov A.A., Sesekin A.N., Routing problems with non-additive cost aggregation, URSS, Moscow, 2021

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

[9] 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

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

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

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

[13] 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

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

[15] 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 | DOI | MR | Zbl

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

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

[18] Warga J., Optimal control of differential and functional equations, Academic Press, 1972 | MR | Zbl

[19] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to algorithms, MIT Press, Cambridge, 1990 | MR | Zbl

[20] Chentsov A.G., Extreme tasks of routing and distribution of tasks: theory questions, Regular and Chaotic Dynamics, Institute of Computer Science, Moscow–Izhevsk, 2008

[21] Chentsov A.G., Chentsov A.A., “On the question of finding the value of the route problem with constraints”, Journal of Automation and Information Sciences, 48:2 (2016), 11–27 | DOI | MR | MR