Dynamic programming in the routing problem: decomposition variant

A. G. Chentsov   ; P. A. Chentsov

Vestnik rossijskih universitetov. Matematika, Tome 27 (2022) no. 137, pp. 95-124

Résumé

The questions of applying the dynamic programming (DP) apparatus to the routing problem with constraints and cost functions with the tasks list dependence are investigated. It is supposed that binary partition of the task set is given; tasks of the first task group must be fulfilled before the fulfillment of the task of the second group begins. In each of the groups, precedence conditions may be present. This setting can be applied in the case of sheet cutting on CNC machines, where two above-mentioned groups form zones planned at the cutting stage. In general case, for the optimal solution construction, the two-stage variant of DP is used. Linking two versions of DP is realized by identification of the criterion terminal component for service problem of the first group with extremum function connected with the second group. The connection of optimal solutions for above-mentioned two problems allows to construct an optimal solution for the initial joint problem. Based on the theoretical constructions algorithm realized on personal computer is constructed; computing experiment is realized.

Détail

Keywords: dynamic programming, precedence conditions.
Mots-clés : route

Bibliographie

[1] G. Gutin, A. P. Punnen, The Traveling Salesman Problem and its Variations, Springer, Berlin, 2002, 850 pp. | MR

[2] W. J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University, United States, 2012, 228 pp. | MR | Zbl

[3] E. Kh. Gimadi, M. Yu. Khachai, Extremal Problems on Sets of Permutations, UMC UPI Publ., Ekaterinburg, 2016, 216 pp. (In Russian)

[4] M. Kubo, H. Kasugai, “The precedence constrained traveling salesman problem”, Journal of the Operations Research Society of Japan, 34:2 (1991), 152–172 | DOI | MR | Zbl

[5] Y. Salii, “Revisisting dynamic programming for precedence-constrained Traveling Salesman Problem and its time-dependent generalization”, European Journal of Operational Research, 272:1 (2019), 32–42 | DOI | MR | Zbl

[6] E. Balas, “New classes of efficiently solvable generalized Taveling Salesman Problems”, Annals of Operations Research, 86 (1999), 529–558 | DOI | MR | Zbl

[7] J. A. Chisman, “The clustered traveling salesman problem”, Computers and Operation Research, 2:2 (1975), 115–119 | DOI

[8] M. Yu. Khachai, E. D. Neznakhina, “Priblizhennye skhemy dlya obobschennoi zadachi kommivoyazhera”, Tr. IMM UrO RAN, 22, no. 3, 2016, 283–292 ; M. Yu. Khachai, E. D. Neznakhina, “Approximation schemes for the generalized Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 299:suppl. 1 (2017), 97–105 | DOI | MR

[9] F. C. J. Lokin, “Procedures for traveling salesman problems with additional constraints”, European of Journal Operation al Research, 3:2 (1979), 135–141 | DOI | Zbl

[10] S. S. Lebedev, “On the decomposition of some applied problems of discrete optimization”, Economics and Mathematical Methods, 44:2 (2008), 121–125 (In Russian)

[11] V. I. Tsurkov, Decomposition in High-dimensional Problems, Nauka Publ., Moscow, 1981, 350 pp. (In Russian) | MR

[12] A. A. Pervozvansky, V. G. Gaitsgori, Decomposition, Aggregation and Approximate Optimization, Nauka Publ., Moscow, 1975, 344 pp. (In Russian) | MR

[13] A. G. Chentsov, Extremal Problems of Routing and Job Distribution: Questions of Theory, Izhevsk Institute for Computer Research, Izhevsk, 2008, 238 pp. (In Russian)

[14] R. Bellman, “Application of Dynamic Programming to the Traveling Salesman Problem”, Cybernetic Collection, v. 9, eds. A. A. Lyapunov, O. B. Lupanov, Mir Publ., Moscow, 1964, 219–222 (In Russian)

[15] M. Held, R. M. Karp, “Application of Dynamic Programming to Ordering Problems”, Cybernetic Collection, v. 9, eds. A. A. Lyapunov, O. B. Lupanov, Mir Publ., Moscow, 1964, 202–218 (In Russian)

[16] A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Ekstremalnaya zadacha marshrutizatsii s vnutrennimi poteryami”, Tr. IMM UrO RAN, 14, no. 3, 2008, 183–201 ; A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Extremal routing problem with internal losses”, Proc. Steklov Inst. Math. (Suppl.), 264:suppl. 1 (2009), 87–106 | DOI | MR

[17] A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 54 (2019), 102–121 | MR | Zbl

[18] A. G. Chentsov, P. A. Chentsov, “Marshrutizatsiya v usloviyakh ogranichenii: zadacha o poseschenii megapolisov”, Avtomatika i telemekhanika, 2016, no. 11, 96–117 | Zbl

[19] A. G. Chentsov, “On the question of routing of work packages”, Vestnik Udmurtskogo Universiteta: Matematika, Mekhanika, Komp'yuternye Nauki, 2013, no. 1, 59–82 (In Russian) | MR | Zbl

[20] K. Kuratowski, A. Mostowski, Set Theory, Moscow, Mir Publ., 1970, 416 pp. (In Russian) | MR

[21] J. Dieudonnet, Fundamentals of Modern Analysis, Mir Publ., Moscow, 1964, 430 pp. (In Russian)

[22] T. Kormen, Ch. Leizerson, R. Rivest, Algorithms: Construction and Analysis, MCNMO, Moscow, 2000, 955 pp. (In Russian)

[23] J. Varga, Optimal Control of Differential and Functional Equations, Nauka Publ., Moscow, 1977, 624 pp. (In Russian)

[24] A. A. Petunin, A. G. Chentsov, P. A. Chentsov, Optimal Tool Routing of Shaped Sheet Cutting Machines with Numerical Control. Mathematical Models and Algorithms, Ural University Press, Ekaterinburg, 2020, 247 pp.