RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik YuUrGU. Ser. Mat. Model. Progr.:
Year:
Volume:
Issue:
Page:
Find






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


Vestnik YuUrGU. Ser. Mat. Model. Progr., 2015, Volume 8, Issue 1, Pages 24–45 (Mi vyuru247)  

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

Survey Articles

A model of “nonadditive” routing problem where the costs depend on the set of pending tasks

A. G. Chentsovab, Ya. V. Saliiab

a Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russian Federation
b Ural Federal University Named after the First President of Russia B. N. Yeltsin, Yekaterinburg, Russian Federation

Abstract: We consider a generalization of the bottleneck (minimax) routing problem. The problem is to successively visit a number of megalopolises, complicated by precedence of constraints imposed on the order of megalopolises visited and the fact that the cost functions (of movement between megalopolises and of interior tasks) may explicitly depend on the list of tasks that are not completed at the present time. The process of movement is considered to be a sequence of steps, which include the exterior movement to the respective megalopolis and the following completion of (essentially interior) jobs connected with the megalopolis. The quality of the whole process is represented by the maximum cost of steps it consists of; the problem is to minimize the mentioned criterion (which yields a minimax problem, usually referred to as a “bottleneck problem”). Optimal solutions, in the form of a route-track pair (a track, or trajectory, conforms to a specific instance of a tour over the megalopolises, which are numbered in accordance with the route; the latter is defined by the transposition of indices), are constructed through a “nonstandard” variant of the dynamic programming method, which allows to avoid the process of constructing of all the values of the Bellman function whenever precedence constraints are present.

Keywords: dynamic programming; route; precedence constraints; sequential ordering problem.

DOI: https://doi.org/10.14529/mmp150102

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

Bibliographic databases:

UDC: 519.6
MSC: 90C90, 90C39
Received: 22.09.2014
Language:

Citation: A. G. Chentsov, Ya. V. Salii, “A model of “nonadditive” routing problem where the costs depend on the set of pending tasks”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 8:1 (2015), 24–45

Citation in format AMSBIB
\Bibitem{CheSal15}
\by A.~G.~Chentsov, Ya.~V.~Salii
\paper A model of ``nonadditive'' routing problem where the costs depend on the set of pending tasks
\jour Vestnik YuUrGU. Ser. Mat. Model. Progr.
\yr 2015
\vol 8
\issue 1
\pages 24--45
\mathnet{http://mi.mathnet.ru/vyuru247}
\crossref{https://doi.org/10.14529/mmp150102}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000422198500002}
\elib{http://elibrary.ru/item.asp?id=23052004}


Linking options:
  • http://mi.mathnet.ru/eng/vyuru247
  • http://mi.mathnet.ru/eng/vyuru/v8/i1/p24

    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, “Marshrutizatsiya peremeschenii pri dinamicheskikh ogranicheniyakh: zadacha “na uzkie mesta””, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 26:1 (2016), 121–140  mathnet  crossref  mathscinet  elib
    2. 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
  • Number of views:
    This page:142
    Full text:57
    References:17

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