Russian Universities Reports. Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Russian Universities Reports. Mathematics:
Year:
Volume:
Issue:
Page:
Find






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


Russian Universities Reports. Mathematics, 2022, Volume 27, Issue 137, Pages 95–124
DOI: https://doi.org/10.20310/2686-9667-2022-27-137-95-124
(Mi vtamu249)
 

This article is cited in 4 scientific papers (total in 4 papers)

Scientific articles

Dynamic programming in the routing problem: decomposition variant

A. G. Chentsovab, P. A. Chentsovba

a N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences
b Ural Federal University named after the First President of Russia B. N. Yeltsin
References:
Abstract: The questions of applying the dynamic programming (DP) apparatus to the routing problem with constraints and cost functions with the tasks list dependence are investigated. It is supposed that binary partition of the task set is given; tasks of the first task group must be fulfilled before the fulfillment of the task of the second group begins. In each of the groups, precedence conditions may be present. This setting can be applied in the case of sheet cutting on CNC machines, where two above-mentioned groups form zones planned at the cutting stage. In general case, for the optimal solution construction, the two-stage variant of DP is used. Linking two versions of DP is realized by identification of the criterion terminal component for service problem of the first group with extremum function connected with the second group. The connection of optimal solutions for above-mentioned two problems allows to construct an optimal solution for the initial joint problem. Based on the theoretical constructions algorithm realized on personal computer is constructed; computing experiment is realized.
Keywords: dynamic programming, route, precedence conditions.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation 075-02-2021-1383
The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075-02-2021-1383).
Received: 01.12.2021
Document Type: Article
UDC: 517.958, 530.145.6
MSC: 93C15, 49N30, 49N35
Language: Russian
Citation: A. G. Chentsov, P. A. Chentsov, “Dynamic programming in the routing problem: decomposition variant”, Russian Universities Reports. Mathematics, 27:137 (2022), 95–124
Citation in format AMSBIB
\Bibitem{CheChe22}
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper Dynamic programming in the routing problem: decomposition variant
\jour Russian Universities Reports. Mathematics
\yr 2022
\vol 27
\issue 137
\pages 95--124
\mathnet{http://mi.mathnet.ru/vtamu249}
\crossref{https://doi.org/10.20310/2686-9667-2022-27-137-95-124}
Linking options:
  • https://www.mathnet.ru/eng/vtamu249
  • https://www.mathnet.ru/eng/vtamu/v27/i137/p95
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Russian Universities Reports. Mathematics
    Statistics & downloads:
    Abstract page:121
    Full-text PDF :34
    References:14
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024