Geodesic
On sequential traversal of sets
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 31 (2021) no. 3, pp. 487-504
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of sequential traversal of megapolises with precedence conditions is investigated; this problem is oriented to mechanical engineering — CNC metal cutting machines. There is the following setting singularity: the terminal component of additive criterion contains the dependence on the starting point. This singularity leads to the fact that the natural solution procedure based on dynamic programming must be applied individually for every starting point. The investigation goal consists in the construction of an optimizing algorithm for determining a complex including a route (a variant of megapolis numbering), a trajectory, and a starting point. The proposed algorithm realizes an idea of directed enumeration of starting points. This algorithm is realized as a program for PC; computations for model examples are made.
Keywords: route optimization, dynamic programming, start point optimization. 
@article{VUU_2021_31_3_a9,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {On sequential traversal of sets},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {487--504},
     year = {2021},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2021_31_3_a9/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - On sequential traversal of sets
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2021
SP  - 487
EP  - 504
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VUU_2021_31_3_a9/
LA  - ru
ID  - VUU_2021_31_3_a9
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T On sequential traversal of sets
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2021
%P 487-504
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/VUU_2021_31_3_a9/
%G ru
%F VUU_2021_31_3_a9
A. G. Chentsov; P. A. Chentsov. On sequential traversal of sets. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 31 (2021) no. 3, pp. 487-504. http://geodesic.mathdoc.fr/item/VUU_2021_31_3_a9/

[1] Chentsov A. G., Chentsov P. A., “On routing problem with starting point optimization”, Ural Mathematical Journal, 6:2 (2020), 44–62 | DOI | Zbl

[2] Chentsov A. G., Chentsov P. A., “To the question of optimization of the starting point in the routing problem with restrictions”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 55 (2020), 135–154 (in Russian) | DOI | Zbl

[3] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, Boston, 2007 | DOI | Zbl

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

[5] Gimadi E. Kh., Khachay M. Yu., Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I. Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | Zbl

[7] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. II. Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | Zbl

[8] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | Zbl

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

[10] 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 | Zbl

[11] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967

[12] Dieudonné J., Foundations of modern analysis, Academic Press, New York, 1960 | Zbl

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

[14] Chentsov A. G., Chentsov A. A., Sesekin A. N., Routing problems with non-additive cost aggregation, LENAND, M., 2021

[15] Petunin A. A., Chentsov A. G., Chentsov P. A., Optimal tool routing on CNC sheet cutting machines. Mathematical models and algorithms, Ural Federal University, Yekateriburg, 2020

[16] Chentsov A. G., “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Automation and Remote Control, 73:3 (2012), 532–546 | DOI | Zbl

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

[18] Petunin A. A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta, 13:2 (2009), 280–286 (in Russian)

[19] Chentsov A. G., Chentsov P. A., Petunin A. A., Sesekin A. N., “Model of megalopolises in the tool path optimization for CNC plate cutting machines”, International Journal of Production Research, 56:14 (2018), 4819–4830 | DOI