An extremal constrained routing problem with internal losses

A. A. Chentsov ; A. G. Chentsov ; P. A. Chentsov

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2010), pp. 64-81.

Résumé

We consider the following problem: one has to visit a finite number of sets and perform certain work on each of them. The work is accompanied by certain (internal) losses. The movements from some set to another one are constrained and accompanied by external (aggregated additively) losses. We propose a “through” variant of the dynamic programming method, formulate an equivalent reconstruction problem, and develop an optimal algorithm based on an efficient dynamic programming method technique.

Détail

Keywords: dynamic programming, precedence conditions
Mots-clés : reconstruction problem.

Bibliographie

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

[2] Bellman R., “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kiberneticheskii sb., 9, 1964, 219–228 | MR

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

[4] Henry-Labordere A. L., “The record-balancing problem: a dynamic programming solution of a generalized traveling salesman problem”, Rev. Franç. Inform. Rech. Opér., 3:B-2 (1969), 43–49 | Zbl

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

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

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

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

[9] Chentsov A. A., Chentsov A. G., “O reshenii zadachi marshrutnoi optimizatsii metodom dinamicheskogo programmirovaniya”, Avtomatika i telemekhanika, 1998, no. 9, 117–129 | 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. A., Chentsov A. G., “Dynamic programming method in the generalized traveling salesman problem: the influence of inexact calculations”, Math. Comput. Modelling, 33:8–9 (2001), 801–819 | DOI | MR | Zbl

[12] Plotinskii Yu. M., “Obschaya zadacha razvozki”, Avtomatika i telemekhanika, 1973, no. 6, 100–104 | Zbl

[13] Melamed I. I., Plotinskii Yu. M., “Evristicheskii algoritm resheniya obobschennoi zadachi razvozki”, Avtomatika i telemekhanika, 1979, no. 12, 167–172 | Zbl

[14] Chentsov A. G., Chentsov P. A., “Marshrutizatsiya s usloviyami predshestvovaniya (zadacha kurera): metod dinamicheskogo programmirovaniya”, Vestn. UGTU–UPI, 15, 2004, 148–151

[15] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Ob odnom obobschenii zadachi kurera”, Algoritmy i program. sredstva parallel. vychislenii, 8, UrO RAN, Ekaterinburg, 2004, 178–235 | MR

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

[17] Chentsov A. G., “O strukture odnoi ekstremalnoi zadachi marshrutizatsii s ogranicheniyami v vide uslovii predshestvovaniya”, Vestn. Udmurtskogo un-ta. Matematika, 2006, no. 1, 127–150

[18] Chentsov A. G., “Ekstremalnye zadachi marshrutizatsii s ogranicheniyami”, Izv. instituta matem. i informatiki, 2006, no. 3, 163–166

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

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

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

[22] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitelnye algoritmy, Fizmatlit, M., 2007, 304 pp.

[23] Chentsov A. A., Chentsov A. G., “O realizatsii metoda dinamicheskogo programmirovaniya v obobschennoi zadache kurera”, Tr. Instituta matem. i mekhaniki, 13, no. 3, 2007, 136–160

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

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

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

[27] Bellman R., Dinamicheskoe programmirovanie, In. lit., M., 1974, 432 pp. | MR

[28] Sesekin A. N., Chentsov A. A., Chentsov A. G., Zadacha posledovatelnogo obkhoda mnozhestv, UGTU–UPI, Ekaterinburg, 2007, 91 pp.