Movement routing tasks focused on engineering applications are being investigated which leads to formulations involving constraints and complicated cost functions. It is assumed that the entire set of tasks is divided into a sum of clusters, the maintenance of which is ordered; when visiting each cluster, the task of optimizing the order of tasks and (in a situation with multiple movements) trajectories that are implemented in accordance with the selected sequence should be solved (each time). For partial tasks, precedence constraints and cost functions that depend on the job list are possible, which is typical for many applications. In practice, it is necessary to find "good"solutions to the overall problem in an acceptable amount of time. In this paper, decomposition that is consistent with job clusters and separate dynamic programming are used to achieve this goal. As a result, the optimization of composite solutions is achieved with acceptable performance. An optimal algorithm has been implemented on a multi-core PC, and an extensive computational experiment has been conducted. Possible applications include the control of tool with using of regions when sheet cutting in CNC machines.
Keywords: decomposition, dynamic programming, route, precedence conditions
Received April 01, 2026
Revised April 20, 2026
Accepted April 27, 2026
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, 620077 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, 620077 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: chentsov.p@mail.ru
REFERENCES
1. 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.
2. Little J., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Oper. Res., 1963, vol. 11, no. 6, pp. 972–989. https://doi.org/10.1287/opre.11.6.972
3. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Vol. 12. NY, Springer, 2007, 830 p. https://doi.org/10.1007/b101971
4. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey, Princeton Univ. Press, 2012, 248 p. ISBN: 9780691163529 .
5. 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 .
6. Bellman R. Dynamic programming treatment of the travelling salesman problem. J. ACM, 1962, vol. 9, no. 1, pp. 61–63. https://doi.org/10.1145/321105.321111
7. Held M., Karp R.M. A dynamic programming approach to sequencing problems. J. Soc. Industr. Appl. Math., 1962, vol. 10, no. 1, pp. 196–210.
8. Chisman J.A. The clustered traveling salesman problem. Comput. Oper. Res., 1975, vol. 2, no. 2, pp. 115–119.
9. 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 .
10. 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).
11. Frolovskii V.D. Automation of design of control programs for thermal metal cutting on CNC equipment. Inform. Tekhnol. v Proyekt. i Proizv., 2005, no. 4, pp. 63–66 (in Russian).
12. Dewil R., Vansteenwegen P., Cattrysse D. Construction heuristics for generating tool paths for laser cutters. Inter. J. Product. Res., 2014, vol. 52, no. 20, pp. 5965–5984. https://doi.org/10.1080/00207543.2014.895064
13. Ye J., Chen Z.G. An optimized algorithm of numerical cutting-path control in garment manufacturing. Adv. Mat. Res., 2013, vol. 796, pp. 454–457. https://doi.org/10.4028/www.scientific.net/AMR.796.454
14. Lee M.K., Kwon K.B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm. Int. J. Prod. Res., 2006, vol. 44, no. 24, pp. 5307–5326.
15. Hoeft J., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem. IIE Transact., 1997, vol. 29, no. 9, pp. 719–731. https://doi.org/10.1080/07408179708966382
16. 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 (in Russian). https://doi.org/10.21538/0134-4889-2022-28-2-215-248
17. Chentsov A.G., Chentsov P.A. Dynamic programming in the routing problem: decomposition variant. Vestnik Ros. Univ. Mat., 2022, vol. 27, no. 137, pp. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
18. 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. https://doi.org/10.1134/S0005117923050053
19. Chentsov A.G., Chentsov P.A. Dynamic programming and decomposition in extreme routing problems. Proc. Steklov Inst. Math., 2025, vol. 329, suppl. 1, pp. S39–S63. https://doi.org/10.1134/S0081543825600796
20. Kuratowski K., Mostowski A. Set theory. Warszawa, PWN Polish Sci. Publ., 1967, 417 p. Translated to Russian under the title Teoriya mnozhestv, Moscow, Mir Publ., 1970, 416 p.
21. Dieudonne J. Foundations of modern analysis, NY, Acad. Press, 1960, 384 p. Translated to Russian under the title Osnovy sovremennogo analiza, Moscow, Mir Publ., 1964, 432 p.
22. Warga J. Optimal control of differential and functional equations, NY, Acad. Press, 1972, 531 p. https://doi.org/10.1016/C2013-0-11669-8 . Translated to Russian under the title Optimal’noe upravlenie differentsial’nymi i funktsional’nymi uravneniyami, Moscow, Nauka Publ., 1977, 624 p.
23. Cormen T.H., Leiserson C.E., Rivest R.L. Introduction to algorithms (1st ed.), MIT Press and McGraw-Hill, 1990, 1028 p. ISBN: 0-262-03141-8 . Translated to Russian under the title Algoritmy: postroyeniye i analiz, Moscow, MCNMO Publ., 1999, 955 p. ISBN: 5-900916-37-5
24. Chentsov A.G. Ekstremal’nyye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [Extremal problems of routing and assignment distribution: theoretical issues]. Moscow, Inst. Comp. Res.; Izhevsk, Sci. Center “Regular and Chaotic Dynamics”, 2008, 239 p. ISBN: 978-5-93972-654-2 .
25. Chentsov A.G., Chentsov P.A. Multi-level dynamic programming in routing problems with constraints. Izv. IMI UdGU, 2025, vol. 66, pp. 115–165. https://doi.org/10.35634/2226-3594-2025-66-09
26. Chentsov A.G., Chentsov P.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
27. 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
28. Lawler E.L. Efficient implementation of dynamic programming algorithm for sequencing problems. Report: BW 106/79. Amsterdam, Stichting Math. Centr., 1979.
Cite this article as: A.G. Chentsov, P.A. Chentsov. Dynamic programming and decomposition in multi-stage routing problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026, vol. 32, no. 3, pp. 281–300.
