maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-2-211-227mais-330Research ArticleОригинальные статьиArticlesЗадача маршрутизации, осложненная зависимостью функций стоимости и "текущих" ограничений от списка заданийRoutization Problem Complicated by the Dependence of Costs Functions and «Current» Restrictions From the Tasks ListЧенцовА. Г.ChentsovA. G

член-корр. РАНпрофессор

correspondent-member of RASprofessor  

chentsov@imm.uran.ruЧенцовА. А.ChentsovA. A.

канд. физ.-мат. наук 

candidate of science 

chentsov.a@binsys.ruИнститут математики и механики им. Н.Н. Красовского, ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990, Россия; Уральский Федеральный Университет, ул. Мира, 19, г. Екатеринбург, 620002, РоссияРоссияN.N. Krasovskii Institute of Mathematics and Mechanics, S. Kovalevskaya str., 16, Ekaterinburg, 620990, Russia; Ural Federal University, Mira str., 19, Ekaterinburg, 620002, RussiaRussian FederationИнститут математики и механики им. Н.Н. Красовского, ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990, РоссияРоссияN.N. Krasovskii Institute of Mathematics and Mechanics, S.Kovalevskaya str., 16, Ekaterinburg, 620990, RussiaRussian Federation201620042016232211227Copyright © Ченцов А.Г., Ченцов А.А., 20162016Ченцов А.Г., Ченцов А.А.Chentsov A.G., Chentsov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/330

Рассматривается задача маршрутизации перемещений, осложненная ограничениями различных типов (условия предшествования, ограничения на достижимость состояний при каждом перемещении и др.). Допускается многовариантность на этапе перемещений, что естественным образом приводит к задаче о посещении мегаполисов. Стоимости перемещений и работ, выполняемых при посещении мегаполисов, могут зависеть от списка заданий. Данный список может отвечать уже выполненным, либо, напротив, еще не выполненным заданиям. Допускается также, что "текущие" ограничения (на перемещения) могут зависеть от упомянутого списка заданий. Рассматриваемая постановка ориентирована на приложения к задачам атомной энергетики (проблема снижения облучаемости персонала АЭС при выполнении комплекса работ в условиях повышенной радиации) и машиностроения. В последнем случае, связанном с управлением инструментом при листовой резке деталей на машинах с ЧПУ, "текущие" ограничения на перемещения могут быть обусловлены тепловыми допусками по отношению к уже "пройденным" фрагментам листа. В статье приведена схема построения оптимального решения на основе широко понимаемого динамического программирования. Используемый при этом алгоритм реализован на ПЭВМ; результаты его применения иллюстрируются на модельных примерах. 

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.

маршруттрассаусловия предшествованияroutetracepreceding conditionsReferencesПетунин А.А., “О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала”, Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика, 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).]Петунин А.А., “О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала”, Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика, 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).]Фроловский В.Д., “Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ”, Информационные технологии в проектировании и производстве, 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).]Фроловский В.Д., “Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ”, Информационные технологии в проектировании и производстве, 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).]Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, Москва, 1982; [Gjeri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982, (in Russian).]Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, Москва, 1982; [Gjeri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982, (in Russian).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Вопросы теории”, Автоматика и телемеханика, 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).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Вопросы теории”, Автоматика и телемеханика, 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).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Точные алгоритмы” , Автоматика и телемеханика, 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).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Точные алгоритмы” , Автоматика и телемеханика, 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).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Приближенные алгоритмы” , Автоматика и телемеханика, 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).]Меламед И.И., Сергеев С.И., Сигал И.Х., “Задача коммивояжера. Приближенные алгоритмы” , Автоматика и телемеханика, 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).]Gutin G., Punnen A.P., The Traveling Salesman Problem and Its Variations, Kluwer, 2002.Gutin G., Punnen A.P., The Traveling Salesman Problem and Its Variations, Kluwer, 2002.Сигал И.Х., “Алгоритмы для решения бикритериальной задачи коммивояжера большой размерности”, Техническая кибернетика, 1990, No6, 143–155; [Sigal I.H., “Algoritmy dlja reshenija bikriterialnoj zadachi kommivojazhera bolshoj razmernosti”, Tehnicheskaja kibernetika, 1990, No 6, 143–155, (in Russian).]Сигал И.Х., “Алгоритмы для решения бикритериальной задачи коммивояжера большой размерности”, Техническая кибернетика, 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 (1964), 219–228; [Bellman R., “Primenenie dinamicheskogo programmirovanija k zadache o kommivo jazhere”, Kiberneticheskij sbornik, 9 (1964), 219–228, (in Russian)].Беллман Р., “Применение динамического программирования к задаче о коммивояжере”, Кибернетический сборник, 9 (1964), 219–228; [Bellman R., “Primenenie dinamicheskogo programmirovanija k zadache o kommivo jazhere”, Kiberneticheskij sbornik, 9 (1964), 219–228, (in Russian)].Хелд М., Карп Р.М., “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник, 9 (1964), 202–218; [Held M., Karp R.M., “Primenenie dinamicheskogo programmirovanija k zadacham uporjadochenija”, Kiberneticheskij sbornik, 9 (1964), 202–218, (in Russian)].Хелд М., Карп Р.М., “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник, 9 (1964), 202–218; [Held M., Karp R.M., “Primenenie dinamicheskogo programmirovanija k zadacham uporjadochenija”, Kiberneticheskij sbornik, 9 (1964), 202–218, (in Russian)].Ченцов А.Г., Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, РХД, Москва–Ижевск, 2008; [Chentsov A.G., Jekstremalnye zadachi marshrutizacii i raspredelenija zadanij: voprosy teorii, RHD, Moskva–Izhevsk, 2008, (in Russian).]Ченцов А.Г., Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, РХД, Москва–Ижевск, 2008; [Chentsov A.G., Jekstremalnye zadachi marshrutizacii i raspredelenija zadanij: voprosy teorii, RHD, Moskva–Izhevsk, 2008, (in Russian).]Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями”, Изв. ВУЗов. Математика, 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).]Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями”, Изв. ВУЗов. Математика, 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).]Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Элементы динамического программирования в экстремальных задачах маршрутизации”, Проблемы управления, 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).]Ченцов А.А., Ченцов А.Г., Ченцов П.А., “Элементы динамического программирования в экстремальных задачах маршрутизации”, Проблемы управления, 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).]Ченцов А.Г., “К вопросу о маршрутизации комплекса работ”, Вестник Удм. ун-та. Математика. Механика. Комп. науки., 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).]Ченцов А.Г., “К вопросу о маршрутизации комплекса работ”, Вестник Удм. ун-та. Математика. Механика. Комп. науки., 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).]Ченцов А.Г., “Задача последовательного обхода мегаполисов с условиями предшествования” , Автоматика и телемеханика, 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).]Ченцов А.Г., “Задача последовательного обхода мегаполисов с условиями предшествования” , Автоматика и телемеханика, 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).]Ченцов А.А., Ченцов А.Г., “Динамическое программирование в задаче маршрутизации с ограничениями и стоимостями, зависящими от списка заданий”, Доклады Академии Наук, 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).]Ченцов А.А., Ченцов А.Г., “Динамическое программирование в задаче маршрутизации с ограничениями и стоимостями, зависящими от списка заданий”, Доклады Академии Наук, 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).]Ченцов А.А., Ченцов А.Г., “Задача маршрутизации с ограничениями, зависящими от списка заданий”, Доклады Академии Наук, 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).]Ченцов А.А., Ченцов А.Г., “Задача маршрутизации с ограничениями, зависящими от списка заданий”, Доклады Академии Наук, 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).]Куратовский К., Мостовский А., Теория множеств, Мир, Москва, 1970; [Kuratovskij K., Mostovskij A., Teorija mnozhestv, Mir, Moskva, 1970, (in Russian).]Куратовский К., Мостовский А., Теория множеств, Мир, Москва, 1970; [Kuratovskij K., Mostovskij A., Teorija mnozhestv, Mir, Moskva, 1970, (in Russian).]Дьедонне Ж., Основы современного анализа, Мир, Москва, 1964; [D’edonne Zh., Osnovy sovremennogo analiza, Mir, Moskva, 1964, (in Russian).]Дьедонне Ж., Основы современного анализа, Мир, Москва, 1964; [D’edonne Zh., Osnovy sovremennogo analiza, Mir, Moskva, 1964, (in Russian).]

The authors declare that there are no conflicts of interest present.