Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
General information
Latest issue
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Izv. IMI UdGU:

Personal entry:
Save password
Forgotten password?

Izv. IMI UdGU, 2020, Volume 55, Pages 135–154 (Mi iimi395)  

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


To the question of optimization of the starting point in the routing problem with restrictions

A. G. Chentsov, P. A. Chentsov

Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia

Abstract: We consider the extreme routing problem with an additive criterion, the terminal component of which depends on the starting point. This dependence may be associated, in particular, with the requirement to return to the starting point region after completing the final system of tasks that need to be ordered. The work assumes that the tasks to be performed are related with visiting non-empty finite sets called megacities. In turn, the mentioned visits are associated with the performance of works, the costs of which are involved in the formation of the criterion. Finally, the costs of external movements (between megacities) supplement the formation of an additive criterion to be minimized. It is required to find a global extremum and a solution that includes a starting point, the order of visits to megacities and a specific trajectory of the process. The solution uses widely understood dynamic programming (DP). It is significant that procedures based on DP use starting point. Therefore, enumeration of mentioned points is required. The article proposes an approach to solving the problem of reducing this enumeration through the use of auxiliary DP that are universal with respect to the choice of a starting point. The optimal algorithm was built and implemented on a PC using the aforementioned approach.

Keywords: dynamic programming, route, precedence conditions.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-07-00637_а
This work was supported by RFBF, grant no. 18–07–00637.

DOI: https://doi.org/10.35634/2226-3594-2020-55-09

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

Bibliographic databases:

UDC: 519.6
MSC: 93C83
Received: 12.01.2020

Citation: A. G. Chentsov, P. A. Chentsov, “To the question of optimization of the starting point in the routing problem with restrictions”, Izv. IMI UdGU, 55 (2020), 135–154

Citation in format AMSBIB
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper To the question of optimization of the starting point in the routing problem with restrictions
\jour Izv. IMI UdGU
\yr 2020
\vol 55
\pages 135--154

Linking options:
  • http://mi.mathnet.ru/eng/iimi395
  • http://mi.mathnet.ru/eng/iimi/v55/p135

    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

    This publication is cited in the following articles:
    1. Alexander G. Chentsov, Pavel A. Chentsov, “On routing problem with starting point optimization”, Ural Math. J., 6:2 (2020), 44–62  mathnet  crossref  mathscinet
    2. A. G. Chentsov, P. A. Chentsov, “Ob odnoi zadache posledovatelnogo obkhoda mnozhestv”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 31:3 (2021), 487–504  mathnet  crossref
  • Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
    Number of views:
    This page:85
    Full text:21

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021