phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2021 - 3 issue » pp. 487-504

Archive of Issues

Russia Yekaterinburg
Year
2021
Volume
31
Issue
3
Pages
487-504
<<
>>
Section Mathematics
Title On sequential traversal of sets
Author(-s) Chentsov A.G.ab, Chentsov P.A.ab
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract 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
UDC 517.6
MSC 49L20, 90C39
DOI 10.35634/vm210310
Received 11 May 2021
Language Russian
Citation Chentsov A.G., Chentsov P.A. On sequential traversal of sets, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2021, vol. 31, issue 3, pp. 487-504.
References
  1. Chentsov A.G., Chentsov P.A. On routing problem with starting point optimization, Ural Mathematical Journal, 2020, vol. 6, no. 2, pp. 44-62. https://doi.org/10.15826/umj.2020.2.005
  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, 2020, vol. 55, pp. 135-154 (in Russian). https://doi.org/10.35634/2226-3594-2020-55-09
  3. Gutin G., Punnen A.P. The traveling salesman problem and its variations, Boston: Springer, 2007. https://doi.org/10.1007/b101971
  4. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton: Princeton University Press, 2012. https://zbmath.org/?q=an:1236.00007
  5. Gimadi E.Kh., Khachay M.Yu. Ekstremal'nye zadachi na mnozhestvakh perestanovok (Extreme problems on sets of permutations), Yekaterinburg: UMC UPI, 2016.
  6. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. I. Theoretical issues, Automation and Remote Control, 1989, vol. 50, issue 9, pp. 1147-1173. https://zbmath.org/?q=an:0705.90070
  7. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. II. Exact methods, Automation and Remote Control, 1989, vol. 50, issue 10, pp. 1303-1324. https://zbmath.org/?q=an:0705.90071
  8. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximate algorithms, Automation and Remote Control, 1989, vol. 50, issue 11, pp. 1459-1479. https://zbmath.org/?q=an:0704.90095
  9. Bellman R. Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, vol. 9, issue 1, pp. 61-63. https://doi.org/10.1145/321105.321111
  10. Held M., Karp R.M. A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, issue 1, pp. 196-210. https://doi.org/10.1137/0110015
  11. Kuratowski K., Mostowski A. Set theory, Amsterdam: North-Holland, 1967.
    Translated under the title Teoriya mnozhestv, Moscow: Mir, 1970.
  12. Dieudonné J. Foundations of modern analysis, New York: Academic Press, 1960.
    Translated under the title Osnovy sovremennogo analiza, Moscow: Mir, 1964.
  13. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extreme problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008.
  14. Chentsov A.G., Chentsov A.A., Sesekin A.N. Zadachi marshrutizatsii peremeshchenii s neadditivnym agregirovaniem zatrat (Routing problems with non-additive cost aggregation), Moscow: LENAND, 2021.
  15. Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal'naya marshrutizatsiya instrumenta mashin figurnoi listovoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy (Optimal tool routing on CNC sheet cutting machines. Mathematical models and algorithms), Yekateriburg: Ural Federal University, 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, 2012, vol. 73, issue 3, pp. 532-546. https://doi.org/10.1134/S0005117912030113
  17. Chentsov A.G., Chentsov P.A. Routing under constraints: problem of visit to megalopolises, Automation and Remote Control, 2016, vol. 77, issue 11, pp. 1957-1974. https://doi.org/10.1134/S0005117916110060
  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, 2009, vol. 13, no. 2, pp. 280-286 (in Russian). https://elibrary.ru/item.asp?id=15134316
  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, 2018, vol. 56, issue 14, pp. 4819-4830. https://doi.org/10.1080/00207543.2017.1421784
Full text
/doc/issues-2021/21-03-10.pdf
<< Previous article
Next article >>