RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. IMI UdGU:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izv. IMI UdGU, 2019, Volume 54, Pages 102–121 (Mi iimi385)  

The routing problems with optimization of the starting point: dynamic programming

A. G. Chentsovab, P. A. Chentsovac

a N. N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
b Institute of Radioelectronics and Information Technologies, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
c Mechanical Engineering Institute, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia

Abstract: 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.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-08-01385_а
This research was supported by the Russian Foundation for Basic Research (projects no. 17–08–01385).


DOI: https://doi.org/10.20537/2226-3594-2019-54-08

Full text: PDF file (470 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.6
MSC: 93C83
Received: 30.07.2019
Language:

Citation: A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izv. IMI UdGU, 54 (2019), 102–121

Citation in format AMSBIB
\Bibitem{CheChe19}
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper The routing problems with optimization of the starting point: dynamic programming
\jour Izv. IMI UdGU
\yr 2019
\vol 54
\pages 102--121
\mathnet{http://mi.mathnet.ru/iimi385}
\crossref{https://doi.org/10.20537/2226-3594-2019-54-08}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000512131100008}


Linking options:
  • http://mi.mathnet.ru/eng/iimi385
  • http://mi.mathnet.ru/eng/iimi/v54/p102

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
    Number of views:
    This page:72
    Full text:20
    References:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020