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, 2012, Issue 1, Pages 96–119 (Mi vuu313)  

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


About one route problem with interior works

I. B. Cheblokova, A. G. Chentsovb

a Department of Computational Methods and Mathematical Physics, Ural Federal University named after the First President of Russia B. N. Yeltsin, Yekaterinburg, Russia
b Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russia

Abstract: The route problem about visiting of multifunction sections with constraints of type of preceding conditions is considered. By setting of this problem the fulfilment of works on the above-mentioned sections is provided. Any solution is defined in the form of the ordered pair for which components have the sense of the route (the index permutation) and the trace (trajectory) of the movements with respect to sections of multifunctions. The agreement of the trace and route is realized by procedures of the sequential choice of ordered pairs (the point of arrival and the starting point) of Descartes “squares” of the multifunction sections numbered in correspondence with a route. The cost aggregation is presupposed additive; the total criterion includes the costs of (exterior) movements between sections of multifunctions, interior works, and the final state. Under constructing of extension of the basic problem that realizes the used Bellman function, the equivalent transformation of constraints is applied: admissibility of routes by preceding is replaced onto admissibility by deletion of tasks (of the list) that corresponds to the constraints variant with respect to the current movements from one set onto another. An analog of the Bellman equation realized by procedure of the transformation of layers of Bellman function is obtained. The operation defining this transformation is further used for constructing of heuristic algorithms realized on PC.

Keywords: route, permutation, trace, Bellman function.

Full text: PDF file (300 kB)
References: PDF file   HTML file
UDC: 517.977
MSC: 76D55, 90C27
Received: 09.02.2011

Citation: I. B. Cheblokov, A. G. Chentsov, “About one route problem with interior works”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2012, no. 1, 96–119

Citation in format AMSBIB
\by I.~B.~Cheblokov, A.~G.~Chentsov
\paper About one route problem with interior works
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2012
\issue 1
\pages 96--119

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Cycle of papers

    This publication is cited in the following articles:
    1. A. G. Chentsov, Ya. V. Salii, “A model of “nonadditive” routing problem where the costs depend on the set of pending tasks”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 8:1 (2015), 24–45  mathnet  crossref  elib
    2. M. S. Kosheleva, A. A. Chentsov, A. G. Chentsov, “O zadache marshrutizatsii s ogranicheniyami, vklyuchayuschimi zavisimost ot spiska zadanii”, Tr. IMM UrO RAN, 21, no. 4, 2015, 178–195  mathnet  mathscinet  elib
    3. 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
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:196
    Full text:72
    First page:1

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