Geodesic
Iteration method in the routing problem with internal losses
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 15 (2009) no. 4, pp. 270-289
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The problem of a sequential traversal of sets is considered, which is complicated by the necessity of fulfilling (internal) tasks on the sets as well as by restrictions in the form of precedence conditions. It is assumed that the method of aggregating the losses is additive. For the appearing extremal problem with dependent variables, an equivalent transformation is built for the optimization problem on a Cartesian product. Based on this, an iteration method is constructed that uses a reconstructible model of the courier problem (a traveling salesman problem complicated by precedence conditions).
Mots-clés : route
Keywords: path, precedence conditions. 
@article{TIMM_2009_15_4_a22,
     author = {A. A. Chentsov and A. G. Chentsov and P. A. Chentsov},
     title = {Iteration method in the routing problem with internal losses},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {270--289},
     year = {2009},
     volume = {15},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2009_15_4_a22/}
}
TY  - JOUR
AU  - A. A. Chentsov
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - Iteration method in the routing problem with internal losses
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2009
SP  - 270
EP  - 289
VL  - 15
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TIMM_2009_15_4_a22/
LA  - ru
ID  - TIMM_2009_15_4_a22
ER  - 
%0 Journal Article
%A A. A. Chentsov
%A A. G. Chentsov
%A P. A. Chentsov
%T Iteration method in the routing problem with internal losses
%J Trudy Instituta matematiki i mehaniki
%D 2009
%P 270-289
%V 15
%N 4
%U http://geodesic.mathdoc.fr/item/TIMM_2009_15_4_a22/
%G ru
%F TIMM_2009_15_4_a22
A. A. Chentsov; A. G. Chentsov; P. A. Chentsov. Iteration method in the routing problem with internal losses. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 15 (2009) no. 4, pp. 270-289. http://geodesic.mathdoc.fr/item/TIMM_2009_15_4_a22/

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

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

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

[4] Bellman R., “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kibernet. sb., 9, Mir, M., 1964, 219–228

[5] Kheld M., Karp R. M., “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kibernet. sb., 9, Mir, M., 1964, 202–218

[6] Henry-Labordere A. L., “The record-balancing problem: a dynamic programming solution of a generalized travelling salesman problem”, R. I. R. O., 3:2 (1969), 43–49 | Zbl

[7] Laporte G., Nobert Y., “Generalized travelling salesman problem through $n$-sets of nodes: an integer programming approach”, INFOR, 21:1 (1983), 61–75 | Zbl

[8] Leiten A. K., “Nekotorye modifikatsii zadachi kommivoyazhera”, Tr. VTs Tart. un-ta, 28, 1973, 44–58 | MR

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

[10] Chentsov A. A., Chentsov A. G., “K voprosu o reshenii zadachi posledovatelnogo obkhoda mnozhestv s ispolzovaniem “nezamknutoi” zadachi kommivoyazhera”, Avtomatika i telemekhanika, 2002, no. 11, 151–166 | MR | Zbl

[11] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, M.–Izhevsk, 2008, 238 pp.

[12] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Obobschennaya versiya zadachi kurera”, Matematicheskii i prikladnoi analiz, Sb. nauchn. tr., Vyp. 2, Izd-vo Tyumen. gos. un-ta, Tyumen, 2005, 238–280

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

[14] Chentsov A. A., Chentsov A. G., “O realizatsii metoda dinamicheskogo programmirovaniya v obobschennoi zadache kurera”, Tr. In-ta matematiki i mekhaniki UrO RAN, 13, no. 3, 2008, 136–160

[15] Bellman R., Dinamicheskoe programmirovanie, IL, M., 1974, 432 pp.

[16] Bellman R., Kalaba R., Dinamicheskoe programmirovanie i osnovy sovremennoi teorii upravleniya, Nauka, M., 1969, 118 pp. | Zbl

[17] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Ekstremalnaya zadacha marshrutizatsii s vnutrennimi poteryami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14, no. 3, 2008, 183–201