Archive of Issues
Russia Yekaterinburg
Section  Mathematics 
Title  Routing of displacements with dynamic constraints: “bottleneck problem” 
Author(s)  Chentsov A.G.^{ab}, Chentsov A.A.^{a} 
Affiliations  Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences^{a}, Ural Federal University^{b} 
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 
UDC  519.6 
MSC  05A05, 97N70, 97N80 
DOI  10.20537/vm160110 
Received  27 February 2016 
Language  Russian 
Citation  Chentsov A.G., Chentsov A.A. Routing of displacements with dynamic constraints: “bottleneck problem”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, vol. 26, issue 1, pp. 121140. 
References 

Full text 