General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki:

Personal entry:
Save password
Forgotten password?

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2018, Volume 28, Issue 3, Pages 348–363 (Mi vuu643)  

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


Dynamic programming in the generalized bottleneck problem and the start point optimization

A. G. Chentsovab, A. A. Chentsovb, A. N. Sesekinba

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

Abstract: We consider one non-additive routing problem, which is a generalization of the well-known “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 above-mentioned 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.

Funding Agency Grant Number
Russian Academy of Sciences - Federal Agency for Scientific Organizations 30
The work was supported by the Presidium of the Russian Academy of Sciences, project no. 30 “Theory and Technology of Multilevel Decentralized Group Control in Conditions of Conflict and Cooperation”.


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

Bibliographic databases:

UDC: 517.6
MSC: 49L20, 90C39
Received: 06.06.2018

Citation: A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “Dynamic programming in the generalized bottleneck problem and the start point optimization”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 28:3 (2018), 348–363

Citation in format AMSBIB
\by A.~G.~Chentsov, A.~A.~Chentsov, A.~N.~Sesekin
\paper Dynamic programming in the generalized bottleneck problem and the start point optimization
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2018
\vol 28
\issue 3
\pages 348--363

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izv. IMI UdGU, 54 (2019), 102–121  mathnet  crossref
    2. A. G. Chentsov, A. A. Chentsov, “K voprosu o marshrutizatsii peremeschenii v zadache s dinamicheskimi ogranicheniyami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 29:3 (2019), 363–381  mathnet  crossref
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:135
    Full text:78

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