RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki:
Year:
Volume:
Issue:
Page:
Find






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


Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2016, Volume 26, Issue 1, Pages 121–140 (Mi vuu523)  

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

MATHEMATICS

Routing of displacements with dynamic constraints: “bottleneck problem”

A. G. Chentsovab, A. A. Chentsova

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620990, Russia
b Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia

Abstract: A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.

Keywords: route, trace, preceding conditions, dynamic programming.

Funding Agency Grant Number
Russian Science Foundation 14-11-00109


DOI: https://doi.org/10.20537/vm160110

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

Bibliographic databases:

UDC: 519.6
MSC: 05A05, 97N70, 97N80
Received: 27.02.2016

Citation: A. G. Chentsov, A. A. Chentsov, “Routing of displacements with dynamic constraints: “bottleneck problem””, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 26:1 (2016), 121–140

Citation in format AMSBIB
\Bibitem{CheChe16}
\by A.~G.~Chentsov, A.~A.~Chentsov
\paper Routing of displacements with dynamic constraints: ``bottleneck problem''
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2016
\vol 26
\issue 1
\pages 121--140
\mathnet{http://mi.mathnet.ru/vuu523}
\crossref{https://doi.org/10.20537/vm160110}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3485578}
\elib{http://elibrary.ru/item.asp?id=25681790}


Linking options:
  • http://mi.mathnet.ru/eng/vuu523
  • http://mi.mathnet.ru/eng/vuu/v26/i1/p121

    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. A. G. Chentsov, A. A. Chentsov, “A discrete-continuous routing problem with precedence conditions”, Proc. Steklov Inst. Math. (Suppl.), 300, suppl. 1 (2018), 56–71  mathnet  crossref  crossref  isi  elib
    2. A. G. Chentsov, A. N. Sesekin, A. A. Chentsov, “Dinamicheskoe programmirovanie v obobschennoi zadache «na uzkie mesta» i optimizatsiya tochki starta”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 28:3 (2018), 348–363  mathnet  crossref  elib
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:169
    Full text:55
    References:45

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