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/

[1] Gutin G., Punnen A., The traveling salesman problem and its variations, Springer, Berlin, 2002 | MR

[2] Cook W. J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, Princeton, New Jersey, 2012 | MR | Zbl

[3] Chentsov A. G., Chentsov P. A., “Optimization of the start point in the GTSP with the precedence conditions”, Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 11:2 (2018), 83–95 (in Russian) | DOI | Zbl

[4] Chentsov A. G., Chentsov P. A., “On one routing task with the optimization of the start-finish point”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 52 (2018), 103–115 (in Russian) | DOI

[5] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[6] Held M., Karp R. M., “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[7] Chentsov A. A., Chentsov A. G., Sesekin A. N., “Dynamic programming in a generic bottleneck problem and starting point optimization”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 28:3 (2018), 348–363 (in Russian) | DOI | Zbl

[8] Kuratowski K., Mostowski A., Set theory, North-Holland Publishing Company, Amsterdam, 1967 | MR

[9] Dieudonne J., Foundations of modern analysis, Academic Press, New York, 1960 | MR | Zbl

[10] Cormen T., Leiserson C., Rivest R., Introduction to algorithms, MIT Press, Cambridge, 1990 | MR | Zbl

[11] Chentsov A. G., Extremal problems of routing and assignment of tasks: questions of theory, Regular and Chaotic Dynamics, Institute of Computer Science, Moscow–Izhevsk, 2008

[12] Chentsov A. G., “Problem of successive megalopolis traversal with the precedence conditions”, Automation and Remote Control, 75:4 (2014), 728–744 | DOI | MR | Zbl

[13] Chentsov A. G., “To question of routing of works complexes”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, 59–82 (in Russian) | DOI

[14] Chentsov A. G., Chentsov P. A., “Routing under constraints: Problem of visit to megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 | DOI | MR | Zbl

[15] Lawler E. L., Efficient implementation of dynamic programming algorithms for sequencing problems, CWI. Technical Reports, BW 106/79, Stichting Mathematish Centrum. Mathematische Besliskunde, 1979, 16 pp.

[16] Chentsov A. G., Chentsov P. A., “Dynamic programming and heuristic methods in routing problems”, Izvestiya Yuzhnogo Federal'nogo Universiteta. Tekhnicheskie Nauki, 2017, no. 9, 169–181 (in Russian) | DOI