About one route problem with interior works

I. B. Cheblokov ; A. G. Chentsov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2012), pp. 96-119

Résumé

The route problem about visiting of multifunction sections with constraints of type of preceding conditions is considered. By setting of this problem the fulfilment of works on the above-mentioned sections is provided. Any solution is defined in the form of the ordered pair for which components have the sense of the route (the index permutation) and the trace (trajectory) of the movements with respect to sections of multifunctions. The agreement of the trace and route is realized by procedures of the sequential choice of ordered pairs (the point of arrival and the starting point) of Descartes “squares” of the multifunction sections numbered in correspondence with a route. The cost aggregation is presupposed additive; the total criterion includes the costs of (exterior) movements between sections of multifunctions, interior works, and the final state. Under constructing of extension of the basic problem that realizes the used Bellman function, the equivalent transformation of constraints is applied: admissibility of routes by preceding is replaced onto admissibility by deletion of tasks (of the list) that corresponds to the constraints variant with respect to the current movements from one set onto another. An analog of the Bellman equation realized by procedure of the transformation of layers of Bellman function is obtained. The operation defining this transformation is further used for constructing of heuristic algorithms realized on PC.

Détail

Mots-clés : route, permutation
Keywords: trace, Bellman function.

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] 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] Geri M., Dzhonson D., Vychislitelnye mashiny i trudno reshaemye zadachi, Mir, M., 1982, 416 pp. | MR

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

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

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

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

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

[10] Leiten A. K., “Nekotorye modifikatsii zadachi kommivoyazhera”, Trudy Vychisl. tsentra Tart. un-ta, 28, 1973, 44–58 | MR

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

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

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

[14] Korotaeva L. N., Trukhin M. P., Chentsov A. G., “K voprosu o marshrutizatsii soedinenii”, Avtomatika i telemekhanika, 1997, no. 12, 175–192 | MR

[15] Zobnin B. B., Korotaeva L. N., Chentsov A. G., “Ob odnoi zadache marshrutnoi optimizatsii i ee prilozheniyakh”, Problemy peredachi informatsii, 33:4 (1997), 70–87 | MR | Zbl

[16] Chentsov A. A., Chentsov A. G., “O reshenii zadachi marshrutnoi optimizatsii metodom dinamicheskogo programmirovaniya”, Avtomatika i telemekhanika, 1998, no. 9, 117–129 | MR | Zbl

[17] Chentsov A. A., Chentsov A. G., “O reshenii zadachi marshrutnoi optimizatsii metodom dinamicheskogo programmirovaniya”, Izvestiya RAN. Teoriya i sistemy upravleniya, 1999, no. 3, 76–87 | MR

[18] Chentsov A. G., “O strukture odnoi ekstremalnoi zadachi marshrutizatsii s ogranicheniyami v vide uslovii predshestvovaniya”, Vestnik Udmurtskogo universiteta. Matematika, 2006, no. 1, 127–150

[19] Chentsov A. G., Chentsov P. A., “Marshrutizatsiya s usloviyami predshestvovaniya (zadacha kurera): metod dinamicheskogo programmirovaniya”, Na peredovykh rubezhakh nauki i inzhenernogo tvorchestva, Ch. 1, Vestnik UGTU-UPI, 15(45), GOU VPO UGTU-UPI, Ekaterinburg, 2004, 148–152

[20] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevskii institut kompyuternykh issledovanii, Moskva–Izhevsk, 2008, 240 pp.

[21] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Ekstremalnaya zadacha marshrutizatsii s vnutrennimi poteryami”, Trudy IMM UrO RAN, 14, no. 3, 2008, 183–201

[22] Chentsov A. G., “Metod dinamicheskogo programmirovaniya v ekstremalnykh zadachakh marshrutizatsii s ogranicheniyami”, Izvestiya RAN. Teoriya i sistemy upravleniya, 2010, no. 3, 52–66 | MR | Zbl

[23] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Ekstremalnaya zadacha marshrutizatsii peremeschenii s ogranicheniyami i vnutrennimi poteryami”, Izvestiya vysshikh uchebnykh zavedenii. Matematika, 2010, no. 6, 64–81 | MR | Zbl

[24] Kormen A., Leizerson Ch., Rivest R., Algoritmy. Postroeniya i analiz, MTsNMO, M., 2007, 1296 pp.