Geodesic
On the application of the minimax traveling salesman problem in aviation logistics
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 16 (2023) no. 3, pp. 20-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the problem of organizing a system of movement between the given points (cities) under conditions of resource constraints and in the presence of precedence conditions. The solvability conditions for this problem are extracted from the solution to the minimax traveling salesman problem (the bottleneck problem) without resource constraints. The solution to this extreme routing problem is determined on the basis of a broadly understood dynamic programming in its “non-additive” version. Possible applications may be related to the formation of the route of a vehicle (airplane or helicopter) in order to organize a transportation system in conditions of fuel shortage; it is assumed that in addition to the mandatory visits to all points, there are requirements for the passing movement of goods between some of the points, which creates additional restrictions (precedence conditions). To solve an auxiliary extremal problem, an optimal algorithm is constructed and implemented on a PC.
Keywords: movement routing, constraint system, dynamic programming. 
@article{VYURU_2023_16_3_a1,
     author = {A. G. Chentsov and A. A. Chentsov and A. N. Sesekin},
     title = {On the application of the minimax traveling salesman problem in aviation logistics},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {20--34},
     year = {2023},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2023_16_3_a1/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
AU  - A. N. Sesekin
TI  - On the application of the minimax traveling salesman problem in aviation logistics
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2023
SP  - 20
EP  - 34
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURU_2023_16_3_a1/
LA  - ru
ID  - VYURU_2023_16_3_a1
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%A A. N. Sesekin
%T On the application of the minimax traveling salesman problem in aviation logistics
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2023
%P 20-34
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/VYURU_2023_16_3_a1/
%G ru
%F VYURU_2023_16_3_a1
A. G. Chentsov; A. A. Chentsov; A. N. Sesekin. On the application of the minimax traveling salesman problem in aviation logistics. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 16 (2023) no. 3, pp. 20-34. http://geodesic.mathdoc.fr/item/VYURU_2023_16_3_a1/

[1] Chentsov A.G., Chentsov A.A., Sesekin A.N., Motion Routing Problems with Non-Additive Cost Aggregation, URSS, M., 2020 (in Russian)

[2] Chentsov A.G., Chentsov A.A., “Routing of Displacements with Dynamic Constraints: “Bottleneck Problem””, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye nauki, 26:1 (2016), 121–140 (in Russian) | MR | Zbl

[3] Chentsov A.G., Chentsov A.A., Sesekin A.N., “Dynamic Programming in the Generalized Bottleneck Problem and the Start Point Optimization”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye nauki, 28:3 (2018), 348–363 (in Russian) | MR | Zbl

[4] Chentsov A.G., Chentsov A.A., “Dynamic Programming and Issues of Solvability of the Problem of Routing “to Bottlenecks” with Resource Constraints”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye nauki, 32:4 (2022), 569–592 (in Russian) | MR | Zbl

[5] G. Gutin, A.P. Punnen, The Traveling Salesman Problem and its Variations, Springer, Berlin, 2002 | MR

[6] W.J. Cook, In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, Princeton, New Jersey, 2012 | MR | Zbl

[7] Gimadi E.H., Khachay M.Yu., Extreme Problems on Permutation Sets, UMC UPI, Ekaterinburg, 2016

[8] Melamed I.I., Sergeev S.I, Sigal I.Kh., “The Travelling Salesman Problem: Issues in Theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[9] Melamed I.I., Sergeev S.I, Sigal I.Kh., “The Traveling Salesman Problem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[10] Melamed I.I., Sergeev S.I, Sigal I.Kh., “The Traveling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[11] Little J., Murthy K., Sweeny D., Karel C., “An Algorithm for the Travelling Salesman Problem”, Operation Research, 11:6 (1963), 972–989 | DOI | Zbl

[12] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the Association for Computing Machinery, 9 (1962), 61–63 | DOI | MR | Zbl

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

[14] Serveev S.I., “Algorithms for 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

[15] Kuratowski K., Mostowski A., Sets Theory, North-Holland Publishing Company, Amsterdam, 1967 | MR

[16] Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960 | MR | Zbl

[17] Cormen T.H., Leiserson Ch.E., Rivest R.L., Introduction to Algorithms, MIT Press and McGraw-Hill, 1990 | MR | Zbl

[18] Chentsov A.G., Extremal Problems of Routing and Distribution of Tasks: Questions of Theory, NIC, Izhevsk, 2008 (in Russian)

[19] Chentsov A.G., “To Question of Routing of Works Complexes”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'yuternye nauki, 2013, no. 1, 59–82 (in Russian) | DOI | MR | Zbl

[20] E.L. Lawler, “Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems”, CWI Technical Report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 106:79 (1979), 1–16

[21] Chentsov A.G., Chentsov A.A., “To the Question of Finding the Value of a Route Problem with Restrictions”, Problemy upravleniya i informatiki, 2016, no. 1, 41–54 (in Russian) | MR