Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2016, Volume 26, Issue 1, Pages 121–140
This article is cited in 2 scientific papers (total in 2 papers)
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
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.
route, trace, preceding conditions, dynamic programming.
PDF file (1482 kB)
MSC: 05A05, 97N70, 97N80
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
\by A.~G.~Chentsov, A.~A.~Chentsov
\paper Routing of displacements with dynamic constraints: ``bottleneck problem''
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
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
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
|Number of views:|