A.G. Chentsov, P.A. Chentsov. An extremal two-stage routing problem and procedures based on dynamic programming ... P. 215-248

We study a routing problem in which the set of tasks is represented as the union of two disjoint subsets. The tasks from the first subset must be completed before the execution of the tasks from the second subset. Each task is associated with a visit to a megalopolis (a nonempty finite set) in order to perform some work. The choice of the order in which the tasks are performed is subject to precedence conditions, which are localized for the mentioned two subsets of the total set of tasks. The cost functions used in the formation of the additive criterion may involve a dependence on the list of tasks. To construct a solution, a two-stage procedure based on dynamic programming is proposed. An optimal algorithm is constructed and implemented as a computer program. A model problem about shaped sheet cutting on CNC machines is solved.

Keywords: dynamic programming, route, precedence conditions

Received April 4, 2022

Revised April 26, 2022

Accepted April 30, 2022

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 20-08-00873).

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.P. The traveling salesman problem and its variations. Berlin: Springer, 2002, 850 p. ISBN: 0-306-48213-4 .

2.   Cook W.J. In pursuit of the traveling salesman: Mathematics at the limits of computation. Princeton: Princeton University Press, 2012, 228 p. ISBN: 0691152705 .

3.   Gimadi E.Kh., Khachai M.Yu. Ekstremal’nye zadachi na mnozhestvakh perestanovok [Extremal problems on sets of permutations]. Yekaterinburg: UMC UPI, 2016, 220 p. ISBN: 978-5-8295-0497-7 .

4.   Petunin A.A. On some strategies of forming tool routes at developing the control programs for the thermal machine cutting. Vestn. UGATU, Ser. Upravl., Vychisl. Tekhn., Informat., 2009, vol. 13, no. 2, pp. 280–286 (in Russian).

5.   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 of figured sheet cutting machines with computer numerical control: Mathematical models and algorithms]. Yekaterinburg: UrFU Publ., 2020. 248 p. ISBN: 978-5-7996-3016-4 .

6.   Little L.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. doi: 10.1287/opre.11.6.972 

7.   Bellman R. Dynamic programming treatment of the travelling salesman problem. J. of the ACM (JACM), 1962, vol. 9, no. 1, pp. 61–63. doi: 10.1145/321105.321111 

8.   Held M., Karp R.M. A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math., 1962, vol. 10, no. 1, pp. 196–210. doi: 10.1137/0110015 

9.   Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact methods. Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173; no. 10, pp. 1303–1324; no. 11, pp. 1459–1479.

10.   Chentsov A.G. Ekstremal’nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii [Extreme routing and distribution tasks: theory questions]. Moscow; Izhevsk: R&C Dynamics Publ., 2008, 238 p. ISBN: 978-5-93972-654-2 .

11.   Chentsov A.G., Chentsov A.A. A discrete-continuous routing problem with precedence conditions. Proc. Steklov Inst. Math., 2018, vol. 300, suppl. 1, pp. 56–71. doi: 10.1134/S0081543818020074 

12.   Chentsov A.G., Chentsov P.A. The routing problems with optimization of the starting point: dynamic programming. Izv. IMI UdGU, 2019, vol. 54, pp. 102–121 (in Russian). doi: 10.20537/2226-3594-2019-54-08 

13.   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. doi: 10.1134/S0005117916110060 

14.   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.

15.   Dieudonné J. Foundations of modern analysis. NY: Acad. Press Inc., 1960, 361 p. Translated to Russian under the title Osnovy sovremennogo analiza, Moscow: Mir Publ., 1964, 430 p.

16.   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.

17.   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.

18.   Chentsov A.G., Chentsov A.A., Sesekin A.N. On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks. Trudy Inst. Mat. i Mekh. UrO RAN, 2020, vol. 26, no. 3, pp. 219–234. (in Russian). doi: 10.21538/0134-4889-2020-26-3-219-234 

19.   Chentsov A.G. To question of routing of works complexes. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013, no. 1, pp. 59–82 (in Russian).

Cite this article as: A.G. Chentsov, P.A. Chentsov. 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.