Geodesic
The routing problems with optimization of the starting point: dynamic programming
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 54 (2019), pp. 102-121

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

The extreme routing problem focused on engineering applications in mechanical engineering is considered. We mean the well-known task of tool controlling in the CNC sheet cutting machines. A mathematical model is presented which includes a system of megalopolises (nonempty finite sets) and cost functions depending on the list of tasks. Megalopolises are constructed on the basis of discretization of equidistant curves of part contours. The dependence on the list of tasks is connected with reasons associated with the dynamic constraints that arise in the process of task completion. Among all restrictions, the conditions of precedence are distinguished (earlier cutting of the inner contours and more earlier cutting of large parts). Rational consideration of the precedence conditions allows one to reduce the complexity of calculations when widely understood dynamic programming (DP) is used in the implementation that develops R. Bellman's scheme. This approach makes it possible to solve the problem of optimizing complexes, which include the initial state (starting point), the method of numbering megalopolises in the order of their visits, and the specific trajectory of the process. For a problem complicated by the dependence of the terminal function on the initial state, a decomposition algorithm is used, which allows, in a substantial part of the procedure, the application of a single (for all initial states) DP scheme. The optimal algorithm based on DP is implemented as a program for PC; a computational experiment is conducted.
Keywords: routing problem, dynamic programming, precedence conditions. 
@article{IIMI_2019_54_a7,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {The routing problems with optimization of the starting point: dynamic programming},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {102--121},
     publisher = {mathdoc},
     volume = {54},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2019_54_a7/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - The routing problems with optimization of the starting point: dynamic programming
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2019
SP  - 102
EP  - 121
VL  - 54
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2019_54_a7/
LA  - en
ID  - IIMI_2019_54_a7
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T The routing problems with optimization of the starting point: dynamic programming
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2019
%P 102-121
%V 54
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2019_54_a7/
%G en
%F IIMI_2019_54_a7
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, Tome 54 (2019), pp. 102-121. http://geodesic.mathdoc.fr/item/IIMI_2019_54_a7/