Dynamic programming and questions of solvability of route bottleneck problem with resource constraints

A. G. Chentsov   ; A. A. Chentsov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 32 (2022) no. 4, pp. 569-592

Résumé

The article deals with the problem of admissible routing for a system of cycles each of which contains exterior permutation and works connected with megalopolises (non-empty finite sets) visiting. In the initial setting, a resource constraint is given; this constraint should be fulfilled for every cycle under permutation. The solvability conditions in this problem are connected with the extremum of the auxiliary bottleneck routing problem without above-mentioned constraint, in which the apparatus of widely understood dynamic programming (DP) is used. A particular case of the setting is the known bottleneck courier problem which can be used (in particular) for routing a vehicle (airplane or helicopter) aiming to realize the given shipping system with a limited fuel reserve on each flight. An algorithm implemented on a personal computer is constructed.

Détail

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

Bibliographie

[1] Chentsov A.G., Chentsov A.A., Sesekin A.N., Zadachi marshrutizatsii peremeschenii s neadditivnym agregirovaniem zatrat, Lenand, M., 2021

[2] Petunin A.A., Chentsov A.G., Chentsov P.A., “Optimalnaya marshrutizatsiya v zadachakh posledovatelnogo obkhoda megapolisov pri nalichii ogranichenii”, Chelyabinskii fiziko-matematicheskii zhurnal, 7:2 (2022), 209–233 | DOI | MR

[3] Gutin G., Punnen A., The traveling salesman problem and its variations, Springer, New York, 2007 | DOI | MR

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

[5] Gimadi E.Kh., Khachai M.Yu., Ekstremalnye zadachi na mnozhestvakh perestanovok, UMTs UPI, Ekaterinburg, 2016

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

[7] Melamed I.I., Sergeev S.I., Sigal I.Kh., “Zadacha kommivoyazhera. Tochnye metody”, Avtomatika i telemekhanika, 1989, no. 10, 3–29

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

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

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

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

[12] Sergeev S.I., “Algoritmy resheniya minimaksnoi zadachi kommivoyazhera. I. Podkhod na osnove dinamicheskogo programmirovaniya”, Avtomatika i telemekhanika, 1995, no. 7, 144–150

[13] Chentsov A.G., Chentsov A.A., “Marshrutizatsiya peremeschenii pri dinamicheskikh ogranicheniyakh: zadacha «na uzkie mesta»”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 26:1 (2016), 121–140 | DOI | MR

[14] Chentsov A.G., Chentsov A.A., Sesekin A.N., “Dinamicheskoe programmirovanie v obobschennoi zadache «na uzkie mesta» i optimizatsiya tochki starta”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 28:3 (2018), 348–363 | DOI | MR

[15] Kuratovskii K., Mostovskii A., Teoriya mnozhestv, Mir, M., 1970

[16] Dedonne Zh., Osnovy sovremennogo analiza, Mir, M., 1964

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

[18] Chentsov A.G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, Regulyarnaya i khaoticheskaya dinamika, Izhevskii institut kompyuternykh issledovanii, M.-Izhevsk, 2008

[19] Chentsov A.G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 | DOI

[20] Chentsov A.G., “Odna parallelnaya protsedura postroeniya funktsii Bellmana v obobschennoi zadache kurera s vnutrennimi rabotami”, Avtomatika i telemekhanika, 2012, no. 3, 134–149

[21] Chentsov A.G., Chentsov A.A., “K voprosu o nakhozhdenii znacheniya marshrutnoi zadachi s ogranicheniyami”, Problemy upravleniya i informatiki, 2016, no. 1, 41–54

[22] Lawler E.L., Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW106, Stichting Mathematisch Centrum, Amsterdam, 1979