Задача маршрутизации, осложненная зависимостью функций стоимости и "текущих" ограничений от списка заданий
https://doi.org/10.18255/1818-1015-2016-2-211-227
Аннотация
Рассматривается задача маршрутизации перемещений, осложненная ограничениями различных типов (условия предшествования, ограничения на достижимость состояний при каждом перемещении и др.). Допускается многовариантность на этапе перемещений, что естественным образом приводит к задаче о посещении мегаполисов. Стоимости перемещений и работ, выполняемых при посещении мегаполисов, могут зависеть от списка заданий. Данный список может отвечать уже выполненным, либо, напротив, еще не выполненным заданиям. Допускается также, что "текущие" ограничения (на перемещения) могут зависеть от упомянутого списка заданий. Рассматриваемая постановка ориентирована на приложения к задачам атомной энергетики (проблема снижения облучаемости персонала АЭС при выполнении комплекса работ в условиях повышенной радиации) и машиностроения. В последнем случае, связанном с управлением инструментом при листовой резке деталей на машинах с ЧПУ, "текущие" ограничения на перемещения могут быть обусловлены тепловыми допусками по отношению к уже "пройденным" фрагментам листа. В статье приведена схема построения оптимального решения на основе широко понимаемого динамического программирования. Используемый при этом алгоритм реализован на ПЭВМ; результаты его применения иллюстрируются на модельных примерах.
Об авторах
А. Г. Ченцов
Институт математики и механики им. Н.Н. Красовского, ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990, Россия;
Уральский Федеральный Университет, ул. Мира, 19, г. Екатеринбург, 620002, Россия
Россия
Россия
член-корр. РАН
профессор
А. А. Ченцов
Институт математики и механики им. Н.Н. Красовского, ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990, Россия
Россия
Россия
канд. физ.-мат. наук
Список литературы
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).]
Рецензия
Для цитирования:
Ченцов А.Г., Ченцов А.А. Задача маршрутизации, осложненная зависимостью функций стоимости и "текущих" ограничений от списка заданий. Моделирование и анализ информационных систем. 2016;23(2):211-227. https://doi.org/10.18255/1818-1015-2016-2-211-227
For citation:
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
Просмотров:
971
Послать статью по эл. почте 