Geodesic
On a Nonstationary Route Problem with Constraints
Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 4, pp. 5-24.

Voir la notice de l'article provenant de la source Math-Net.Ru

The extremal route problem of permutations under constraints in the form of preceding conditions is investigated. It is supposed that an executer leaves the initial point (the base) after which he visits a system of megalopolises (finite goal sets) and performs some work on each megalopolis. The cost functions for executor permutations and interior works depend on the “visiting moment” that can correspond to the real time or can also correspond to the natural regular succession (the first visiting, the second visiting, and so on). An economic variant of the widely interpreted dynamic programming method (DPM) is constructed. On this basis an optimal computer realized algorithm is constructed. A variant of a greed algorithm is proposed.
Mots-clés : route
Keywords: trace, dynamic programming, preceding conditions. 
@article{MAIS_2012_19_4_a0,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {On a {Nonstationary} {Route} {Problem} with {Constraints}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {5--24},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a0/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - On a Nonstationary Route Problem with Constraints
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2012
SP  - 5
EP  - 24
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a0/
LA  - ru
ID  - MAIS_2012_19_4_a0
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T On a Nonstationary Route Problem with Constraints
%J Modelirovanie i analiz informacionnyh sistem
%D 2012
%P 5-24
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a0/
%G ru
%F MAIS_2012_19_4_a0
A. G. Chentsov; P. A. Chentsov. On a Nonstationary Route Problem with Constraints. Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 4, pp. 5-24. http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a0/

[1] A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Ekstremalnaya zadacha marshrutizatsii s vnutrennimi poteryami”, Trudy Instituta matematiki i mekhaniki UrO RAN, 14:3 (2008), 183–201

[2] A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Ekstremalnaya zadacha marshrutizatsii peremeschenii s ogranicheniyami i vnutrennimi poteryami”, Izvestiya vuzov. Matematika, 2010, no. 6, 64–81 | MR | Zbl

[3] A. G. Chentsov, “Ob optimalnoi marshrutizatsii v usloviyakh ogranichenii”, Doklady RAN, 423:3 (2008), 303–307 | MR | Zbl

[4] A. G. Chentsov, “Metod dinamicheskogo programmirovaniya v ekstremalnykh zadachakh marshrutizatsii s ogranicheniyami”, Izv. RAN. Teoriya i sistemy upravleniya, 2010, no. 3, 52–66 | MR

[5] A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Metod iteratsii v zadache marshrutizatsii s vnutrennimi poteryami”, Trudy Instituta matematiki i mekhaniki UrO RAN, 15:4 (2009), 270–289

[6] A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Usloviya predshestvovaniya v odnoi zadache ekstremalnoi marshrutizatsii s vnutrennimi rabotami”, Sb. nauchnykh trudov, Algoritmy i programmnye sredstva parallelnykh vychislenii, 10, In-t matematiki i mekhaniki UrO RAN, Ekaterinburg, 2010, 60–76

[7] A. G. Chentsov, Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, RKhD, Moskva–Izhevsk, 2008, 238 pp.

[8] L. V. Tonkov, A. G. Chentsov, “K voprosu optimalnogo vybora marshruta v usloviyakh vremennogo diskontirovaniya”, Kibernetika i sistem. analiz, 1999, no. 1, 95–106 | MR | Zbl

[9] K. Kuratovskii, A. Mostovskii, Teoriya mnozhestv, Mir, M., 1970, 416 pp. | MR

[10] Zh. Dedonne, Osnovy sovremennogo analiza, Mir, M., 1964, 430 pp. | MR

[11] Kormen T., Leizerson Ch., Rivest R., Algoritmy: Postroenie i analiz, MTsNMO, M., 2002, 960 pp.

[12] A. M. Grigorev, E. E. Ivanko, A. G. Chentsov, “Dinamicheskoe programmirovanie v obobschennoi zadache kurera s vnutrennimi rabotami: elementy parallelnoi struktury”, Modelirovanie i analiz informatsionnykh sistem, 18:3 (2011), 101–124

[13] N. N. Krasovskii, Igrovye zadachi o vstreche dvizhenii, Nauka, M., 1970, 420 pp. | MR

[14] N. N. Krasovskii, A. I. Subbotin, Pozitsionnye differentsialnye igry, Nauka, M., 1985, 518 pp. | MR