Geodesic
An extremal two-stage routing problem and procedures based on dynamic programming
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 215-248 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We study a routing problem in which the set of tasks is represented as the union of two disjoint subsets. The tasks from the first subset must be completed before the execution of the tasks from the second subset. Each task is associated with a visit to a megalopolis (a nonempty finite set) in order to perform some work. The choice of the order in which the tasks are performed is subject to precedence conditions, which are localized for the mentioned two subsets of the total set of tasks. The cost functions used in the formation of the additive criterion may involve a dependence on the list of tasks. To construct a solution, a two-stage procedure based on dynamic programming is proposed. An optimal algorithm is constructed and implemented as a computer program. A model problem about shaped sheet cutting on CNC machines is solved.
Keywords: dynamic programming, precedence conditions.
Mots-clés : route 
@article{TIMM_2022_28_2_a17,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {An extremal two-stage routing problem and procedures based on dynamic programming},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {215--248},
     year = {2022},
     volume = {28},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - An extremal two-stage routing problem and procedures based on dynamic programming
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 215
EP  - 248
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/
LA  - ru
ID  - TIMM_2022_28_2_a17
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T An extremal two-stage routing problem and procedures based on dynamic programming
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 215-248
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/
%G ru
%F TIMM_2022_28_2_a17
A. G. Chentsov; P. A. Chentsov. An extremal two-stage routing problem and procedures based on dynamic programming. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 215-248. http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/

[1] Gutin G., Punnen A., The traveling salesman problem and its variations, Springer, Berlin, 2002, 850 pp. | MR

[2] Cook W. J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton Univ. Press, Princeton, New Jersey, 2012, 228 pp. | MR | Zbl

[3] Gimadi E. Kh., Khachai M. Yu., Ekstremalnye zadachi na mnozhestvakh perestanovok, Izd-vo UMTs UPI, Ekaterinburg, 2016, 220 pp.

[4] Petunin A. A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayuschikh programm dlya mashin termicheskoi rezki materiala”, Vest. Ufim. gos. aviatsionnogo tekhnich. un-ta, 13:2 (2009), 280–286

[5] Petunin A. A., Chentsov A. G., Chentsov P. A., Optimalnaya marshrutizatsiya instrumenta mashin figurnoi listovoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy, Izd-vo UrFU, Ekaterinburg, 2020, 248 pp.

[6] Litl Dzh., Murti K., Suini D., Kerel K., “Algoritm dlya resheniya zadachi o kommivoyazhere”, Ekonomika i mat. metody, 1:1 (1965), 94–107

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

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

[9] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera”, Avtomatika i telemekhanika, 1989, no. 9, 3–33 ; no. 10, 3–29 ; no. 11, 3–26 | Zbl | Zbl | Zbl

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

[11] Chentsov A. G., Chentsov A. A., “Diskretno-nepreryvnaya zadacha marshrutizatsii s usloviyami predshestvovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 23:1 (2017), 275–292 | MR

[12] Chentsov A. G., Chentsov P., “The routing problems with optimization of the starting point: dynamic programming”, Izv. In-ta matematiki i informatiki Udmurt. gos. un-ta, 54 (2019), 102–121 | MR | Zbl

[13] Chentsov A. G., Chentsov P. A., “Marshrutizatsiya v usloviyakh ogranichenii: zadacha o poseschenii megapolisov”, Avtomatika i telemekhanika, 2016, no. 11, 96–117 | Zbl

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

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

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

[17] Varga Dzh., Optimalnoe upravlenie differentsialnymi i funktsionalnymi uravneniyami, Nauka, M., 1977, 624 pp.

[18] Chentsov A. G., Chentsov A. A., Sesekin A. N., “O zadache posledovatelnogo obkhoda megapolisov s usloviyami predshestvovaniya i funktsiyami stoimosti s zavisimostyu ot spiska zadanii”, Tr. In-ta matematiki i mekhaniki UrO RAN, 26:3 (2020), 219–234 | MR

[19] Chentsov A. G., “K voprosu o marshrutizatsii kompleksov rabot”, Vest. Udmurt. un-ta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 | MR | Zbl