Routization Problem Complicated by the Dependence of Costs Functions and «Current» Restrictions From the Tasks List
https://doi.org/10.18255/1818-1015-2016-2-211-227
Abstract
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.
About the Authors
A. G Chentsov
N.N. Krasovskii Institute of Mathematics and Mechanics, S. Kovalevskaya str., 16, Ekaterinburg, 620990, Russia;
Ural Federal University, Mira str., 19, Ekaterinburg, 620002, Russia
Russian Federation
Russian Federation
correspondent-member of RAS
professor
A. A. Chentsov
N.N. Krasovskii Institute of Mathematics and Mechanics, S.Kovalevskaya str., 16, Ekaterinburg, 620990, Russia
Russian Federation
Russian Federation
candidate of science
References
1. Петунин А.А., “О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала”, Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика, 13:2 (35) (2009), 280—286; [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. Фроловский В.Д., “Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ”, Информационные технологии в проектировании и производстве, 2005, No4, 63—66; [Frolovskij V.D., “Avtomatizacija pro ektirovanija upravlja jushhih programm teplovo j rezki metalla na ob orudovanii s ChPU”, Informacionnye tehnologii v proektirovanii i proizvodstve, 2005, No4, 63–66, (in Russian).]
3. Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, Москва, 1982; [Gjeri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982, (in Russian).]
4. Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Вопросы теории”, Автоматика и телемеханика, 1989, No 9, 3–34; [Melamed I.I., Sergeev S.I., Sigal I.H., “Zadacha kommivojazhera. Voprosy teorii”, Avtomatika i telemehanika, 1989, No9, 3–34, (in Russian).]
5. Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Точные алгоритмы” , Автоматика и телемеханика, 1989, No 10, 3–29; [Melamed I.I., Sergeev S.I., Sigal I.H., “Zadacha kommivojazhera. Tochnye algoritmy”, Avtomatika i telemehanika, 1989, No 10, 3–29, (in Russian).]
6. Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Приближенные алгоритмы” , Автоматика и телемеханика, 1989, No 11, 3–26; [Melamed I.I., Sergeev S.I., Sigal I.H., “Zadacha kommivojazhera. Priblizhennye algoritmy”, Avtomatika i telemehanika, 1989, No 11, 3–26, (in Russian).]
7. Gutin G., Punnen A.P., The Traveling Salesman Problem and Its Variations, Kluwer, 2002.
8. Сигал И.Х., “Алгоритмы для решения бикритериальной задачи коммивояжера большой размерности”, Техническая кибернетика, 1990, No6, 143–155; [Sigal I.H., “Algoritmy dlja reshenija bikriterialnoj zadachi kommivojazhera bolshoj razmernosti”, Tehnicheskaja kibernetika, 1990, No 6, 143–155, (in Russian).]
9. Беллман Р., “Применение динамического программирования к задаче о коммивояжере”, Кибернетический сборник, 9 (1964), 219–228; [Bellman R., “Primenenie dinamicheskogo programmirovanija k zadache o kommivo jazhere”, Kiberneticheskij sbornik, 9 (1964), 219–228, (in Russian)].
10. Хелд М., Карп Р.М., “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник, 9 (1964), 202–218; [Held M., Karp R.M., “Primenenie dinamicheskogo programmirovanija k zadacham uporjadochenija”, Kiberneticheskij sbornik, 9 (1964), 202–218, (in Russian)].
11. Ченцов А.Г., Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, РХД, Москва–Ижевск, 2008; [Chentsov A.G., Jekstremalnye zadachi marshrutizacii i raspredelenija zadanij: voprosy teorii, RHD, Moskva–Izhevsk, 2008, (in Russian).]
12. Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями”, Изв. ВУЗов. Математика, 2010, No 6, 64–81; [Chentsov A.A., Chentsov A.G., Chentsov P.A., “Jekstremalna ja zadacha marshrutizacii peremeshhenij s ogranichenijami i vnutrennimi poterjami”, Izv. VUZov. Matematika, 2010, No 6, 64–81, (in Russian).]
13. Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Элементы динамического программирования в экстремальных задачах маршрутизации”, Проблемы управления, 2013, No5, 12–21; [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. Ченцов А.Г., “К вопросу о маршрутизации комплекса работ”, Вестник Удм. ун-та. Математика. Механика. Комп. науки., 2013, No 1, 59–82; [Chentsov A.G., “K voprosu o marshrutizacii kompleksa rabot”, Vestnik Udm. un-ta. Matematika. Mehanika. Komp. nauki., 2013, No 1, 59–82, (in Russian).]
15. Ченцов А.Г., “Задача последовательного обхода мегаполисов с условиями предшествования” , Автоматика и телемеханика, 2014, No 4, 170–190; [Chentsov A.G., “Zadacha posledovatelnogo obhoda megapolisov s uslovijami predshestvovanija”, Avtomatika i telemehanika, 2014, No 4, 170–190, (in Russian).]
16. Ченцов А.А., Ченцов А.Г., “Динамическое программирование в задаче маршрутизации с ограничениями и стоимостями, зависящими от списка заданий”, Доклады Академии Наук, 453:1 (2013), 20–23; [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).]
17. Ченцов А.А., Ченцов А.Г., “Задача маршрутизации с ограничениями, зависящими от списка заданий”, Доклады Академии Наук, 465:2 (2015), 154–158; [Chentsov A.A., Chentsov A.G., “Zadacha marshrutizacii s ogranichenijami, zavisjashhimi ot spiska zadanij”, Doklady Akademii Nauk, 465:2 (2015), 154–158, (in Russian).]
18. Куратовский К., Мостовский А., Теория множеств, Мир, Москва, 1970; [Kuratovskij K., Mostovskij A., Teorija mnozhestv, Mir, Moskva, 1970, (in Russian).]
19. Дьедонне Ж., Основы современного анализа, Мир, Москва, 1964; [D’edonne Zh., Osnovy sovremennogo analiza, Mir, Moskva, 1964, (in Russian).]
Review
For citations:
Chentsov A.G., Chentsov A.A. Routization Problem Complicated by the Dependence of Costs Functions and «Current» Restrictions From the Tasks List. Modeling and Analysis of Information Systems. 2016;23(2):211-227. (In Russ.) https://doi.org/10.18255/1818-1015-2016-2-211-227
Views:
992
Email this article 