Geodesic
On a routing problem with constraints that include dependence on a task list
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 4, pp. 178-195 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the solution of a routing problem complicated by constraints and by a possible dependence of the cost function on a task list. In addition, the statement admits that some of the constraints may be formed depending on a current list of tasks. Possible applications of this problem include routing the workers' movements under increased radiation in the process of dismantling radiation sources as well as steering a numerically controlled machine tool during the sheet cutting of parts. We propose a modification of widely understood dynamic programming and use it to design two versions of an algorithm, which are implemented as computer programs.
Keywords: dynamic programming, precedence constraints.
Mots-clés : route 
@article{TIMM_2015_21_4_a16,
     author = {M. S. Kosheleva and A. A. Chentsov and A. G. Chentsov},
     title = {On a routing problem with constraints that include dependence on a task list},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {178--195},
     year = {2015},
     volume = {21},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_4_a16/}
}
TY  - JOUR
AU  - M. S. Kosheleva
AU  - A. A. Chentsov
AU  - A. G. Chentsov
TI  - On a routing problem with constraints that include dependence on a task list
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 178
EP  - 195
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_4_a16/
LA  - ru
ID  - TIMM_2015_21_4_a16
ER  - 
%0 Journal Article
%A M. S. Kosheleva
%A A. A. Chentsov
%A A. G. Chentsov
%T On a routing problem with constraints that include dependence on a task list
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 178-195
%V 21
%N 4
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_4_a16/
%G ru
%F TIMM_2015_21_4_a16
M. S. Kosheleva; A. A. Chentsov; A. G. Chentsov. On a routing problem with constraints that include dependence on a task list. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 4, pp. 178-195. http://geodesic.mathdoc.fr/item/TIMM_2015_21_4_a16/

[1] Petunin A.A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayuschikh programm dlya mashin termicheskoi rezki materiala”, Vestn. UGATU (Upravlenie, vychislitelnaya tekhnika i informatika), 13:2(35) (2009), 280–286

[2] Petunin A.A., Chentsov A.G., Chentsov P.A., “K voprosu o marshrutizatsii dvizheniya instrumenta v mashinakh listovoi rezki s chislovym programmnym upravleniem”, Nauch.-tekhn. vedomosti SPbGPU (Informatika. Telekommunikatsii. Upravlenie), 2013, no. 2(169), 103–111

[3] Frolovskii V.D., “Avtomatizatsiya proektirovaniya upravlyayuschikh programm teplovoi rezki metalla na oborudovanii s ChPU”, Informatsionnye tekhnologii v proektirovanii i proizvodstve, 2005, no. 4, 63–66, M.

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

[5] Gutin G., Punnen A.P., The traveling salesman problem and its variations, Comb. Optim., 12, Kluwer Academic Publishers, Dordrecht, 2002, 830 pp. | MR | Zbl

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

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

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

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

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

[11] Chentsov A.G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, RKhD, M.; Izhevsk, 2008, 238 pp.

[12] Chentsov A.G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. Udm. un-ta. Matematika. Mekhanika. Komp. nauki, 2013, no. 1, 59–82 | Zbl

[13] Chentsov A.G., “Zadacha posledovatelnogo obkhoda megapolisov s usloviyami predshestvovaniya”, Avtomatika i telemekhanika, 2014, no. 4, 170–190 | Zbl

[14] Chentsov A.A., Chentsov A.G., “Zadacha posledovatelnogo obkhoda megapolisov”, Vestn. Tambov. un-ta. Estestv. i tekhn. nauki, 19:2 (2014), 454–475

[15] Chentsov A.G., Cheblokov I.B., “Ob odnoi zadache marshrutizatsii s vnutrennimi rabotami”, Vestn. Udm. un-ta. Matematika. Mekhanika. Komp. nauki, 2012, no. 1, 96–1197 | MR

[16] Chentsov A.A., Chentsov A.G., “Zadachi marshrutizatsii s ogranicheniyami, zavisyaschimi ot spiska zadanii”, Dokl. RAN, 465:2 (2015), 154–158 | DOI