Geodesic
Dynamic programming in the routing problem: decomposition variant
Vestnik rossijskih universitetov. Matematika, Tome 27 (2022) no. 137, pp. 95-124

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: dynamic programming, precedence conditions.
Mots-clés : route 
@article{VTAMU_2022_27_137_a6,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {Dynamic programming in the routing problem: decomposition variant},
     journal = {Vestnik rossijskih universitetov. Matematika},
     pages = {95--124},
     publisher = {mathdoc},
     volume = {27},
     number = {137},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTAMU_2022_27_137_a6/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - Dynamic programming in the routing problem: decomposition variant
JO  - Vestnik rossijskih universitetov. Matematika
PY  - 2022
SP  - 95
EP  - 124
VL  - 27
IS  - 137
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VTAMU_2022_27_137_a6/
LA  - ru
ID  - VTAMU_2022_27_137_a6
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T Dynamic programming in the routing problem: decomposition variant
%J Vestnik rossijskih universitetov. Matematika
%D 2022
%P 95-124
%V 27
%N 137
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VTAMU_2022_27_137_a6/
%G ru
%F VTAMU_2022_27_137_a6
A. G. Chentsov; P. A. Chentsov. Dynamic programming in the routing problem: decomposition variant. Vestnik rossijskih universitetov. Matematika, Tome 27 (2022) no. 137, pp. 95-124. http://geodesic.mathdoc.fr/item/VTAMU_2022_27_137_a6/