×
Chentsov, Aleksandr Georgievich; Chentsov, Pavel Aleksandrovich

On sequential traversal of sets. (Russian. English summary) Zbl 1486.90204

Vestn. Udmurt. Univ., Mat. Mekh. Komp’yut. Nauki 31, No. 3, 487-504 (2021).
Summary: 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.

MSC:

90C39 Dynamic programming

Keywords:

route optimization; dynamic programming; start point optimization
PDF BibTeX XML Cite
\textit{A. G. Chentsov} and \textit{P. A. Chentsov}, Vestn. Udmurt. Univ., Mat. Mekh. Komp'yut. Nauki 31, No. 3, 487--504 (2021; Zbl 1486.90204)
Full Text: DOI MNR

References:

[1] Chentsov A. G., Chentsov P. A., “On routing problem with starting point optimization”, Ural Mathematical Journal, 6:2 (2020), 44-62 · Zbl 1465.90084
[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) · Zbl 1458.90071
[3] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, Boston, 2007 · Zbl 1113.90134
[4] Cook W. J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, Princeton, 2012 · Zbl 1236.00007
[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 0705.90070
[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 0705.90071
[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 0704.90095
[9] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61-63 · Zbl 0106.14102
[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 · Zbl 0106.14103
[11] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967 · Zbl 0204.31301
[12] Dieudonné J., Foundations of modern analysis, Academic Press, New York, 1960 · Zbl 0100.04201
[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 · Zbl 1451.90165
[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 · Zbl 1307.90192
[17] Chentsov A. G., Chentsov P. A., “Routing under constraints: problem of visit to megalopolises”, Automation and Remote Control, 77:11 (2016), 1957-1974 · Zbl 1356.90153
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.