Abstract:
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.
The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075-02-2021-1383).
Citation:
A. G. Chentsov, P. A. Chentsov, “Dynamic programming in the routing problem: decomposition variant”, Russian Universities Reports. Mathematics, 27:137 (2022), 95–124
This publication is cited in the following 5 articles:
A. G. Chentsov, A. A. Chentsov, P. A. Chentsov, “Zadacha marshrutizatsii «na uzkie mesta» (optimizatsiya v predelakh zon)”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 34:2 (2024), 267–285
A. G. Chentsov, P. A. Chentsov, “Nekotorye konstruktsii resheniya zadach marshrutizatsii s ispolzovaniem dekompozitsii i preobrazovanii tselevykh mnozhestv”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 34:4 (2024), 518–540
A. G. Chentsov, “Zadacha marshrutizatsii «na uzkie mesta» s sistemoi pervoocherednykh zadanii”, Izv. IMI UdGU, 61 (2023), 156–186
A. G. Chentsov, P. A. Chentsov, “Two-stage dynamic programming in the routing problem with decomposition”, Autom. Remote Control, 84:5 (2023), 609–632
A. G. Chentsov, A. A. Chentsov, “Minimaksnaya zadacha marshrutizatsii s sistemoi pervoocherednykh zadanii”, Izv. IMI UdGU, 62 (2023), 96–124