|
Section
|
Mathematics
|
|
Title
|
The routing bottlenecks problem (optimization within zones)
|
|
Author(-s)
|
Chentsov A.G.ab,
Chentsov A.A.a,
Chentsov P.A.ab
|
|
Affiliations
|
Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa,
Ural Federal Universityb
|
|
Abstract
|
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, route, precedence conditions
|
|
UDC
|
519.8
|
|
MSC
|
49L20, 90C39
|
|
DOI
|
10.35634/vm240206
|
|
Received
|
26 April 2024
|
|
Language
|
Russian
|
|
Citation
|
Chentsov A.G., Chentsov A.A., Chentsov P.A. The routing bottlenecks problem (optimization within zones), Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2024, vol. 34, issue 2, pp. 267-285.
|
|
References
|
- Gutin G., Punnen A.P. The traveling salesman problem and its variations, New York: Springer, 2007. https://doi.org/10.1007/b101971
- Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton: Princeton University Press, 2012. https://zbmath.org/1236.00007
- Gimadi E.Kh., Khachai M.Yu. Ekstremal'nye zadachi na mnozhestvakh perestanovok (Extreme problems on sets of permutations), Yekaterinburg: UMC UPI, 2016.
- Bellman R. Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, vol. 9, issue 1, pp. 61–63. https://doi.org/10.1145/321105.321111
- Held M., Karp R.M. A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, issue 1, pp. 196–210. https://doi.org/10.1137/0110015
- Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem, Operations Research, 1963, vol. 11, no. 6, pp. 972–989. https://doi.org/10.1287/opre.11.6.972
- Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. I: Theoretical issues, Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173. https://zbmath.org/0705.90070
- Sergeev S.I. Hybrid control systems and the dynamic traveling salesman problem, Automation and Remote Control, 2008, vol. 69, issue 1, pp. 42–51. https://doi.org/10.1134/S0005117908010050
- Sergeev 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, pt. 2, pp. 1027–1032. https://zbmath.org/0917.90252
- Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extreme problems of routing and distribution of tasks: theoretical questions), Moscow–Izhevsk: Regular and Chaotic Dynamics, 2008.
- Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal'naya marshrutizatsiya instrumenta mashin figurnoi listovoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy (Optimal tool routing on CNC sheet cutting machines. Mathematical models and algorithms), Yekateriburg: Ural Federal University, 2020.
- Chentsov A.G., Chentsov P.A. Dynamic programming in the routing problem: decomposition variant, Russian Universities Reports. Mathematics, 2022, vol. 27, issue 137, pp. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
- 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, 2022, vol. 28, no. 2, pp. 215–248 (in Russian). https://doi.org/10.21538/0134-4889-2022-28-2-215-248
- Chentsov A.G., Chentsov P.A. Two-stage dynamic programming in the routing problem with decomposition, Automation and Remote Control, 2023, vol. 84, issue 5, pp. 609–632. https://doi.org/10.25728/arcRAS.2023.10.71.001
- Chentsov A.G., Chentsov P.A. Additive routing problem for a system of high-priority tasks, Mathematical optimization theory and operations research: Recent trends, Cham: Springer, 2023, pp. 218–230. https://doi.org/10.1007/978-3-031-43257-6_17
- Chentsov A.G. A bottleneck routing problem with a system of priority tasks, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2023, vol. 61, pp. 156–186. https://doi.org/10.35634/2226-3594-2023-61-09
- Chentsov A.G., Chentsov A.A. Minimax routing problem with a system of priority tasks, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2023, vol. 62, pp. 96–124. https://doi.org/10.35634/2226-3594-2023-62-08
- Kuratowski K., Mostowski A. Set theory, Amsterdam: North-Holland, 1967.
- Dieudonné J.A. Foundations of modern analysis, New York: Academic Press, 1960. https://zbmath.org/0100.04201
- Cormen T.H., Leiserson C.E., Rivest R.L. Algoritmy: postroenie i analiz (Introduction to algorithms), Moscow: Moscow Center for Continuous Mathematical Education, 2000.
|
|
Full text
|
|
+7 (3412) 91 60 92
Russian