phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2022 - 4 issue » pp. 569-592

Archive of Issues

Russia Yekaterinburg
Year
2022
Volume
32
Issue
4
Pages
569-592
<<
>>
Section Mathematics
Title Dynamic programming and questions of solvability of route bottleneck problem with resource constraints
Author(-s) Chentsov A.G.ab, Chentsov A.A.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract The article deals with the problem of admissible routing for a system of cycles each of which contains exterior permutation and works connected with megalopolises (non-empty finite sets) visiting. In the initial setting, a resource constraint is given; this constraint should be fulfilled for every cycle under permutation. The solvability conditions in this problem are connected with the extremum of the auxiliary bottleneck routing problem without above-mentioned constraint, in which the apparatus of widely understood dynamic programming (DP) is used. A particular case of the setting is the known bottleneck courier problem which can be used (in particular) for routing a vehicle (airplane or helicopter) aiming to realize the given shipping system with a limited fuel reserve on each flight. An algorithm implemented on a personal computer is constructed.
Keywords dynamic programming, route, precedence conditions
UDC 519.8
MSC 49L20, 90C39
DOI 10.35634/vm220406
Received 7 September 2022
Language Russian
Citation 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, 2022, vol. 32, issue 4, pp. 569-592.
References
  1. Chentsov A.G., Chentsov A.A., Sesekin A.N. Zadachi marshrutizatsii peremeshchenii s neadditivnym agregirovaniem zatrat (Routing problems with non-additive cost aggregation), Moscow: Lenand, 2021.
  2. Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal routing in problems of sequential traversal of megapolises in the presence of constraints, Chelyabinskiy Fiziko-Matematicheskiy Zhurnal, 2022, vol. 7, issue 2, pp. 209-233 (in Russian). https://doi.org/10.47475/2500-0101-2022-17205
  3. Gutin G., Punnen A. The traveling salesman problem and its variations, New York: Springer, 2007. https://doi.org/10.1007/b101971
  4. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton, New Jercy: Princeton University Press, 2012. https://zbmath.org/?q=an:1236.00007
  5. Gimadi E.Kh., Khachay M.Yu. Ekstremal'nye zadachi na mnozhestvakh perestanovok (Extreme problems on sets of permutations), Yekaterinburg: UMC UPI, 2016.
  6. 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/?q=an:0705.90070
  7. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. II: Exact methods, Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324. https://zbmath.org/?q=an:0705.90071
  8. 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. https://zbmath.org/?q=an:0704.90095
  9. 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
  10. 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
  11. 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
  12. 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, pp. 1027-1032. https://zbmath.org/?q=an:0917.90252
  13. 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, issue 1, pp. 121-140. https://doi.org/10.20537/vm160110
  14. 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, issue 3, pp. 348-363. https://doi.org/10.20537/vm180306
  15. Kuratowski K., Mostowski A. Set theory, North-Holland, 1967.
  16. Dieudonné J.A. Foundations of modern analysis, New York: Academic Press, 1960.
  17. Cormen T.H., Leizerson C.E., Rivest R.L. Introduction to algorithms, Cambridge: MIT Press, 1990.
  18. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extreme tasks of routing and distribution of tasks: theory questions), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008.
  19. Chentsov A.G. To question of routing of works complexes, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, issue 1, pp. 59-82 (in Russian). https://doi.org/10.20537/vm130107
  20. Chentsov A.G. On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs, Automation and Remote Control, 2012, vol. 73, issue 3, pp. 532-546. https://doi.org/10.1134/S0005117912030113
  21. Chentsov A.G., Chentsov A.A. To the question of finding the value of a constrained route task, Problemy Upravlenia i Informatiki, 2016, no. 1, pp. 41-54 (in Russian).
  22. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems. Report BW106, Amsterdam: Stichting Mathematisch Centrum, 1979.
Full text
/doc/issues-2022/22-04-06.pdf
<< Previous article
Next article >>