Geodesic
Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure
Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 3, pp. 101-124.

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

In the article we concern the questions connected with the realization of a dynamic programming method in problems of consequent visiting of megapolises. The realization is complicated by precedence conditions and works inside the megapolises. The scheme for constructing a reduced (partial) array of Bellman function values using parallel computing without loss in accuracy is suggested. This procedure is realized on a multiprocessor computing system; parallelizing is performed at the stage of Bellman function layers construction.
Mots-clés : route
Keywords: trace, precedence condition. 
@article{MAIS_2011_18_3_a9,
     author = {A. M. Grigoriev and E. E. Ivanko and A. G. Chentsov},
     title = {Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {101--124},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a9/}
}
TY  - JOUR
AU  - A. M. Grigoriev
AU  - E. E. Ivanko
AU  - A. G. Chentsov
TI  - Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2011
SP  - 101
EP  - 124
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a9/
LA  - ru
ID  - MAIS_2011_18_3_a9
ER  - 
%0 Journal Article
%A A. M. Grigoriev
%A E. E. Ivanko
%A A. G. Chentsov
%T Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure
%J Modelirovanie i analiz informacionnyh sistem
%D 2011
%P 101-124
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a9/
%G ru
%F MAIS_2011_18_3_a9
A. M. Grigoriev; E. E. Ivanko; A. G. Chentsov. Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure. Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 3, pp. 101-124. http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a9/

[1] I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “Zadacha kommivoyazhera. Voprosy teorii”, Avtomatika i telemekhanika, 1989, no. 9, 3–34 | MR

[2] I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “Zadacha kommivoyazhera. Tochnye algoritmy”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | MR | Zbl

[3] I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “Zadacha kommivoyazhera. Priblizhennye algoritmy”, Avtomatika i telemekhanika, 1989, no. 11, 3–26 | MR | Zbl

[4] R. Bellman, “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kiberneticheskii sbornik, 9 (1964), 219–228 | MR

[5] M. Kheld, R. M. Karp, “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kiberneticheskii sbornik, 9 (1964), 202–218

[6] S. I. Sergeev, “Gibridnye sistemy upravleniya i dinamicheskaya zadacha kommivoyazhera”, Avtomatika i telemekhanika, 2008, no. 1, 45–54 | MR | Zbl

[7] I. Kh. Sigal, A. P. Ivanova, Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitelnye algoritmy, Nauka, M., 2007

[8] 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–200

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

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

[11] 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

[12] A. G. Chentsov, Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs «Regulyarnaya i khaoticheskaya dinamika», Izhevskii institut kompyuternykh issledovanii, M., Izhevsk, 2008, 240 pp.

[13] L. N. Korotaeva, A. N. Sesekin, A. G. Chentsov, “Ob odnoi modifikatsii metoda dinamicheskogo programmirovaniya v zadache posledovatelnogo sblizheniya”, Zhurn. vychisl. matematiki i mat. fiziki, 29:8 (1989), 1107–1113 | MR | Zbl

[14] L. N. Korotaeva, E. M. Nazarov, A. G. Chentsov, “Ob odnoi zadache o naznacheniyakh”, Zhurn. vychisl. matematiki i mat. fiziki, 33:4 (1993), 483–494 | MR | Zbl

[15] A. A. Chentsov, A. G. Chentsov, “O reshenii zadachi marshrutnoi optimizatsii metodom dinamicheskogo programmirovaniya”, Avtomatika i telemekhanika, 1998, no. 9, 117–129 | MR | Zbl

[16] A. G. Chentsov, P. A. Chentsov, “Marshrutizatsiya s usloviyami predshestvovaniya (zadacha kurera): metod dinamicheskogo programmirovaniya”, Vestnik UGTU–UPI, 1:15(45) (2004), 148–152, Ekaterinburg

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

[18] T. Kormen, Ch. Leizerson, R. Rivest, Algoritmy: postroenie i analiz, MTsNMO, M., 2000, 960 pp.

[19] A. N. Sesekin, O. L. Tashlykov, S. E. Scheklein, M. Yu. Kuklin, A. G. Chentsov, A. A. Kadnikov, “Ispolzovanie metoda dinamicheskogo programmirovaniya dlya optimizatsii traektorii peremescheniya rabotnikov v radiatsionno opasnykh zonakh s tselyu minimizatsii oblucheniya”, Izvestiya vuzov. Yadernaya energetika, 2006, no. 2, 41–48

[20] O. L. Tashlykov, A. N. Sesekin, A. G. Chentsov, S. E. Scheklein, F. A. Balushkin, A. P. Khomyakov, “Vozmozhnosti matematicheskikh metodov modelirovaniya v reshenii problemy obluchaemosti personala”, Voprosy radiatsionnoi bezopasnosti, 2009, no. 4, 39–49

[21] O. L. Tashlykov, A. N. Sesekin, S. E. Scheklein, A. G. Chentsov, “Razrabotka optimalnykh algoritmov vyvoda AES iz ekspluatatsii s ispolzovaniem metodov matematicheskogo modelirovaniya”, Izvestiya vuzov. Yadernaya energetika, 2009, no. 2, 115–120