Routization problem complicated by the dependence of costs functions and > restrictions from the tasks list

A. G. Chentsov ; A. A. Chentsov

Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 2, pp. 211-227.

Résumé

The problem of a routization of the movements complicated by the restrictions of different type (preceding conditions, the restrictions on the attainability of states by each movement and others) is considered. A multivariance at the movement step is permitted, it is naturally resulted in the problem about the visiting of megalopolises. The costs of movements and jobs executed when visiting megalopolises may depend on the list of tacks. This list may correspond to performed or unperformed tasks. "Current" restrictions (on movements) may depend on the aforementioned list of tasks. The considered setting is oriented to the application with regard to a nuclear power engineering problems (the problem of decreasing irradiation of the nuclear power station staff when executing a complex of tasks under high radiation intensity) and the machine building. In the second case, which consists in controling a machine for the sheet cutting of details by the numerical program control machines, "current" restrictions on movements may be conditioned by temperature tolerance relative to the fragments of sheet which have already been "visited" by the cutting machine. The scheme of constructing the optimal solution based on the widely understood dynamic programming is considered in this article. The used algorithm is realized on a personal computer; the results of its application are illustrated by the modelling examples.

Détail

Mots-clés : route
Keywords: trace, preceding conditions.

Bibliographie

[1] Petunin A. A., “O nekotoryh strategijah formirovanija marshruta instrumenta pri razrabotke upravljajushhih programm dlja mashin termicheskoj rezki materiala”, Vestnik UGATU. Serija: Upravlenie, vychislitelnaja tehnika i informatika, 13:2 (35) (2009), 280–286 (in Russian)

[2] Frolovskij V. D., “Avtomatizacija proektirovanija upravljajushhih programm teplovoj rezki metalla na oborudovanii s ChPU”, Informacionnye tehnologii v proektirovanii i proizvodstve, 2005, no. 4, 63–66 (in Russian)

[3] Gjeri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 (in Russian) | MR

[4] Melamed I. I., Sergeev S. I., Sigal I. H., “Zadacha kommivojazhera. Voprosy teorii”, Avtomatika i telemehanika, 1989, no. 9, 3–34 (in Russian) | MR

[5] Melamed I. I., Sergeev S. I., Sigal I. H., “Zadacha kommivojazhera. Tochnye algoritmy”, Avtomatika i telemehanika, 1989, no. 10, 3–29 (in Russian) | MR | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. H., “Zadacha kommivojazhera. Priblizhennye algoritmy”, Avtomatika i telemehanika, 1989, no. 11, 3–26 (in Russian) | MR | Zbl

[7] Gutin G., Punnen A. P., The Traveling Salesman Problem and Its Variations, Kluwer, 2002 | MR | Zbl

[8] Sigal I. H., “Algoritmy dlja reshenija bikriterialnoj zadachi kommivojazhera bolshoj razmernosti”, Tehnicheskaja kibernetika, 1990, no. 6, 143–155 (in Russian) | MR | Zbl

[9] Bellman R., “Primenenie dinamicheskogo programmirovanija k zadache o kommivojazhere”, Kiberneticheskij sbornik, 9, Mir, M., 1964, 219–228 (in Russian) | MR

[10] Held M., Karp R. M., “Primenenie dinamicheskogo programmirovanija k zadacham uporjadochenija”, Kiberneticheskij sbornik, 9, Mir, M., 1964, 202–218 (in Russian)

[11] Chentsov A. G., Jekstremalnye zadachi marshrutizacii i raspredelenija zadanij: voprosy teorii, RHD, M.–Izhevsk, 2008 (in Russian)

[12] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Jekstremalnaja zadacha marshrutizacii peremeshhenij s ogranichenijami i vnutrennimi poterjami”, Izv. VUZov. Matematika, 2010, no. 6, 64–81 (in Russian) | MR | Zbl

[13] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Jelementy dinamicheskogo programmirovanija v jekstremalnyh zadachah marshrutizacii”, Problemy upravlenija, 2013, no. 5, 12–21 (in Russian)

[14] Chentsov A. G., “K voprosu o marshrutizacii kompleksa rabot”, Vestnik Udm. un-ta. Matematika. Mehanika. Komp. nauki, 2013, no. 1, 59–82 (in Russian) | Zbl

[15] Chentsov A. G., “Zadacha posledovatelnogo obhoda megapolisov s uslovijami predshestvovanija”, Avtomatika i telemehanika, 2014, no. 4, 170–190 (in Russian) | Zbl

[16] Chentsov A. A., Chentsov A. G., “Dinamicheskoe programmirovanie v zadache marshrutizacii s ogranichenijami i stoimostjami, zavisjashhimi ot spiska zadanij”, Doklady Akademii Nauk, 453:1 (2013), 20–23 (in Russian) | DOI | Zbl

[17] Chentsov A. A., Chentsov A. G., “Zadacha marshrutizacii s ogranichenijami, zavisjashhimi ot spiska zadanij”, Doklady Akademii Nauk, 465:2 (2015), 154–158 (in Russian) | DOI | Zbl

[18] Kuratovskij K., Mostovskij A., Teorija mnozhestv, Mir, M., 1970 (in Russian) | MR

[19] D'edonne Zh., Osnovy sovremennogo analiza, Mir, M., 1964 (in Russian)