Problems of movement routing with precedence constraints and cost functions depending on the list of tasks are considered. Variants of additive cost aggregation and minimax statement (bottleneck problem) are studied. It is assumed that the entire set of tasks related to visiting megalopolises (nonempty finite sets) is divided into the sum of two clusters; as a result, two particular problems arise: preliminary and final. The execution of tasks of the final problem can be started only after the completion of all tasks of the preliminary one. The aim of the study is to optimize compositional solutions in the cases of additive and minimax statements. A unified approach is proposed related to the separate solution of the preliminary and final problems using broadly understood dynamic programming. An optimal algorithm for the compositional solution of problems of significant dimension with practically acceptable performance is constructed. Possible applications may include the problem of dismantling radiation-hazardous objects, tool control during shaped sheet cutting on CNC machines, and some transport problems related to logistical problems in small aviation.
Keywords: dynamic programming, compositional solutions, precedence conditions.
Received October 14, 2024
Revised November 4, 2024
Accepted November 11, 2024
Published online: December 1, 2024
Alexander Georgievich Chentsov, Dr. Phys.-Math. Sci, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: chentsov@imm.uran.ru
Pavel Alexandrovich Chentsov, Cand. Sci. (Phys.-Math.) Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: chentsov.p@mail.ru
REFERENCES
1. Gutin G., Punnen A. The traveling salesman problem and its variations. NY, Springer New York, 2002, 830 p. https://doi.org/10.1007/b101971
2. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey, Princeton University Press, 2012, 248 p. ISBN: 9780691163529 .
3. Gimadi E.Kh., Khachai M.Yu. Ekstremal’nyye zadachi na mnozhestvakh perestanovok [Extremal problems on permutation sets]. Yekaterinburg, Izd-vo UMTS UPI, 2016, 220 p. ISBN: 978-8-8295-0497-7 .
4. Sergeev S.I. Algorithms for solving a minimax traveling salesman problem. I. An approach based on dynamic programming. Autom. Remote Control, 1995, vol. 56, no. 7, pp. 1027–1032.
5. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173; vol. 50, no. 10, pp. 1303–1324; vol. 50, no. 11, pp. 1459–1479.
6. Bellman R. Application of dynamic programming to the traveling salesman problem. Kiberneticheskiy sbornik, 1964, vol. 9, pp. 219–228 (in Russian).
7. Held M., Karp R.M. Application of dynamic programming to ordering problems. Kiberneticheskiy sbornik, 1964, vol. 9, pp. 202–218 (in Russian).
8. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsiy [Routing methods and their applications in problems of improving the safety and efficiency of nuclear power plants]. Moscow, Iz-vo “Novyye tekhnologii”, 2012, 234 p. ISBN: 978-5-94694-027-6 .
9. Chentsov A.G., Chentsov A.A. A model variant of the problem about radiation sources utilization (iterations based on optimization insertions). Izv. IMI UdGU, 2017, vol. 50, pp. 83–109 (in Russian). https://doi.org/10.20537/2226-3594-2017-50-08
10. Chentsov A.G., Chentsov A.A., Sesekin A.N. One task of routing jobs in high radiation conditions. Izv. IMI UdGU, 2021, vol. 58, pp. 94–126 (in Russian). https://doi.org/10.35634/2226-3594-2021-58-06
11. Petunin A.A. About some strategies of the programming of tool route by developing of control programs for thermal cutting machines. Vestnik UGATU, 2009, vol. 13, no. 2, pp. 280–286 (in Russian).
12. Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal’naya marshrutizatsiya instrumenta mashin figurnoy listovoy rezki s chislovym programmnym upravleniyem. Matematicheskiye modeli i algoritmy [Optimal routing of the tool of figured sheet cutting machines with numerical control. Mathematical models and algorithms], Yekaterinburg, UrFU, 2020, 247 p. ISBN: 978-5-7996-3016-4 .
13. Chentsov A.G., Chentsov A.A. Routing under constraints: problem of visit to megalopolises. Autom. Remote Control, 2016, vol. 77, no. 11, pp. 1957–1974. https://doi.org/10.1134/S0005117916110060
14. Petunin A.A., Chentsov A.G., Chentsov P.A. To the question about instrument routing in the automated machines of the sheet cutting. Nauchno-Tekhnicheskiye Vedomosti SPbGPU, Ser. Computer Science. Telecommunications and Control Systems, 2013, no. 2 (169), pp. 103–111 (in Russian).
15. Chentsov A.G., Chentsov A.A., Sesekin A.N. Zadachi marshrutizacii peremeshchenij s neadditivnym agregirovaniem zatrat [Problems of routing of movements with non-additive aggregation of costs]. 2nd edt., Moscow, Lenand Publ., 2021, 230 p. ISBN: 978-5-9710-8057-2 .
16. Chentsov A.G., Chentsov A.A. Generalized model of courier with additional restrictions. Vestnik YuUrGU. Matematicheskoye modelirovaniye i programmirovaniye, 2016, vol. 9, no. 1, pp. 46–58 (in Russian). https://doi.org/10.14529/mmp160104
17. Chentsov A.G., Chentsov A.A., Sesekin A.N. Dynamic programming in the generalized bottleneck problem and the start point optimization. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2018, vol. 28, no. 3, pp. 348–363 (in Russian). https://doi.org/10.20537/vm180306
18. Chentsov A.G. Ekstremal’nyye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii: nauchnoye izdaniye [Extremal problems of routing and assignment distribution: theoretical issues: scientific publication]. Moscow, Institute of Computer Research; Izhevsk, Scientific Center “Regular and Chaotic Dynamics”, 2008, 239 p. ISBN: 978-5-93972-654-2 .
19. Sigal I.Kh., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie : modeli i vychislitel’nye algoritmy [Introduction to applied dynamic programming]. Moscow: Fizmatlit, 2007, 304 р.
20. Chentsov A.G., Chentsov P.A. An extremal two-stage routing problem and procedures based on dynamic programming. Tr. Inst. Mat. Mekh. UrO RAN, 2022, vol. 28, no. 2, pp. 215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248
21. Chentsov A.G., Chentsov P.A. Two-stage dynamic programming in the routing problem with decomposition elements. Autom. Remote Control, 2023, vol. 84, no. 5, pp. 609–632.
22. Chentsov A.G. A bottleneck routing problem with a system of priority tasks. Izv. IMI UdGU, 2023, vol. 61, pp. 156–186 (in Russian). https://doi.org/10.35634/2226-3594-2023-61-09
23. Chentsov A.G., Chentsov P.A. Dynamic programming in the routing problem: decomposition variant. Vestnik Ross. Univ. Matematika, 2022, vol. 27, no. 137, pp. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
24. Kuratowski K., Mostowski A. Set theory. Warszawa: PWN — Polish Sci. Publ., 1968, 417 p. ISBN: 9780444534170 . Translated to Russian under the title Teoriya mnozhestv. Moscow: Mir Publ., 1970, 416 p.
25. Cormen T., Leiserson C., Rivest R. Introduction to algorithms. NY: McGraw-Hill, 1990, 1028 p. ISBN: 0-262-53091-0 . Translated to Russian under the title Algoritmy: postroenie i analiz, Moscow: MTsNMO Publ., 2002. 960 p. ISBN: 5-900916-37-5 .
26. Warga J. Optimal control of differential and functional equations. NY: Acad. Press, 1972. 624 p. ISBN: 9781483259192 . Translated to Russian under the title Optimal’noe upravlenie differentsial’nymi i funktsional’nymi uravneniyami, Moscow: Nauka Publ., 1977. 624 p.
27. Chentsov А.G. To question of routing of works complexes. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013, vol. 1, pp. 59–82 (in Russian).
28. Chentsov A.G., Chentsov A.A., Chentsov P.A. The routing bottlenecks problem (optimization within zones). Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2024, vol. 34, no. 2, pp. 267–285 (in Russian). https://doi.org/10.35634/vm240206
Cite this article as: A.G. Chentsov, P.A. Chentsov. Dynamic programming and decomposition in extreme routing problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 1, pp. 247–272 .
