Archive of Issues
Russia Yekaterinburg
Section  Mathematics 
Title  Dynamic programming in the generalized bottleneck problem and the start point optimization 
Author(s)  Chentsov A.G.^{ab}, Chentsov A.A.^{a}, Sesekin A.N.^{ab} 
Affiliations  Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences^{a}, Ural Federal University^{b} 
Abstract  We consider one nonadditive routing problem, which is a generalization of the wellknown “bottleneck problem”. The parameter is assumed to be a positive number, the degree of which determines the weight of the corresponding stage of the displacement system. By varying the parameter, it is possible to make the initial or, on the contrary, the final stages of displacement dominant. The variant of aggregation of values with the abovementioned weights corresponds to the ideological formulation of the “bottleneck problem”, but opens the possibility of investigating new versions of routing problems with constraints. It is assumed, however, that the statement of the problem is complicated by the dependence of values on the list of tasks and includes restrictions in the form of precedence conditions. In addition, in the interest of optimization, an arbitrary choice of the initial state from a given a priori set is allowed. For the construction, the apparatus of widely understood dynamic programming is used. The possibility of realizing a global extremum with any degree of accuracy under conditions when the set of possible initial states is not finite is investigated. 
Keywords  route optimization, dynamic programming, start point optimization 
UDC  517.6 
MSC  49L20, 90C39 
DOI  10.20537/vm180306 
Received  6 June 2018 
Language  Russian 
Citation  Chentsov A.G., Chentsov A.A., Sesekin A.N. Dynamic programming in the generalized bottleneck problem and the start point optimization, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2018, vol. 28, issue 3, pp. 348363. 
References 

Full text 