On the Application of the Minimax Traveling Salesman Problem in Aviation Logistics

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.

References

1. Chentsov A.G., Chentsov A.A., Sesekin A.N. Zadachi marshrutizacii peremeshchenij s neadditivnym agregirovaniem zatrat [Motion Routing Problems with Non-Additive Cost Aggregation]. Moscow, URSS, 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, 2016, vol. 26, no. 1, pp. 121–140. (in Russian)
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, 2018, vol. 28, no. 3, pp. 348–363. (in Russian)
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, 2022, vol. 32, no. 4, pp. 569–592. (in Russian)
5. Gutin G., Punnen A.P. The Traveling Salesman Problem and its Variations. Berlin, Springer, 2002.
6. Cook W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. Princeton, New Jersey, Princeton University Press, 2012.
7. Gimadi E.H., Khachay M.Yu. Ektremalnye zadachi na mnogestvah perestanovok [Extreme Problems on Permutation Sets]. Ekaterinburg, UMC UPI, 2016.
8. Melamed I.I., Sergeev S.I, Sigal I.Kh. The Travelling Salesman Problem: Issues in Theory. Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173.
9. Melamed I.I., Sergeev S.I, Sigal I.Kh. The Traveling Salesman Problem. Exact Methods. Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303–1324.
10. Melamed I.I., Sergeev S.I, Sigal I.Kh. The Traveling Salesman Problem. Approximate Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 1459–1479.
11. Little J., Murthy K., Sweeny D., Karel C. An Algorithm for the Travelling Salesman Problem. Operation Research, 1963, vol. 11, no. 6, pp. 972–989. DOI: 10.1287/oper.11.6.972.
12. Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the Association for Computing Machinery, 1962, vol.9, pp. 61–63. DOI: 10.1145/321105.321111.
13. Held M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196–210. DOI: 10.1137/0110015.
14. Serveev S.I. Algorithms for the Minimax Problem of the Traveling Salesman. I. An Approach Based on Dynamic Programming. Automation and Remote Control, 1995, vol. 56, no.7, pp.1027–1032.
15. Kuratowski K., Mostowski A. Sets Theory. Amsterdam, North-Holland Publishing Company, 1967.
16. Dieudonne J. Foundations of Modern Analysis. New York, Academic Press, 1960.
17. Cormen T.H., Leiserson Ch.E., Rivest R.L. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990.
18. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii [Extremal Problems of Routing and Distribution of Tasks: Questions of Theory]. Izhevsk, NIC, 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, pp. 59–82. (in Russian) DOI: 10.20537/vm130107
20. Lawler E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems. CWI Technical Report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 1979, vol. 106, no. 79, pp. 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, pp. 41–54. (in Russian)