Об одном нестационарном варианте обобщенной задачи курьера с внутренними работами

Рассматривается задача последовательного обхода мегаполисов с условиями предшествования и выполнением работ в пределах данных мегаполисов. Предполагается, что стоимости перемещений зависят от параметра, который имеет смысл дискретного времени; упомянутая зависимость может отражать приоритеты клиентов, связанных с обслуживаемыми мегаполисами и частично компенсирующих затраты исполнителей. Построенный метод решения объективно отвечает широко понимаемому динамическому программированию, применяемому для решения задачи маршрутизации с ограничениями. Предложено расширение исходной задачи, использующее эквивалентное преобразование системы ограничений, в результате чего допустимость (маршрутов) по предшествованию заменяется допустимостью 'по вычеркиванию', (заданий из списка). Тем самым ограничения на маршрут в целом сводятся к системе ограничений на текущие перемещения, что позволяет получить уравнение Беллмана. Для использования последнего в вычислительной процедуре построения слоев функции Беллмана используется подход, в рамках которого предусматривается построение всего массива значений упомянутой функции; данный подход базируется на использовании только существенных (по предшествованию) списков заданий, чем достигается экономия вычислений.
Приложения развиваемой теории могут быть связаны с задачами, касающимися снижения облучаемости персонала атомных электростанций при работах в условиях аварийных ситуаций, а также с задачами транспортного обслуживания большого числа клиентов при наличии условий приоритетности, влияющих на выбор очередности обслуживания.

Ключевые слова

маршрут, условия предшествования, динамическое программирование.

Литература

1. Ченцов, А.А. Экстремальная задача маршрутизации с внутренними потерями / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Труды Института математики и механики УрО РАН. - 2008. - Т. 14, № 3. - С. 183-201.
2. Ченцов, А.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Изв. ВУЗов. Математика. - 2010. - № 6. - C. 64-81.
3. Ченцов, А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями / А.Г. Ченцов // Изв. РАН. Теория и системы управления. - 2010. - № 3. - C. 52-66.
4. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - М.; Ижевск: НИЦ 'Регулярная и хаотическая динамика', Ижевский ин-т компьютер. исследований, 2008. - 240 с.
5. Тонков, Л.В. К вопросу оптимального выбора маршрута в условиях временного дисконтирования / Л.В. Тонков, А.Г. Ченцов // Кибернетика и систем. анализ. - 1999. - № 1. - С. 95-106.
6. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970. - 416 c.
7. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2002. - 960 с.
8. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон; пер. с англ. Е.В. Левнера и М.А. Фрумкина. - М.: Мир, 1982. - 416 с.
9. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
10. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
11. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
12. Алгоритмы для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, вып. 1. - С. 94-107.
13. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - М.: Мир, 1964. - Т. 9. - С. 219-228.
14. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - М.: Мир, 1964. - Т. 9. - С. 202-218.
15. Laporte, G. Generalized Travelling Salesman Problem Through n-Sets of Nodes: an Integer Programming Approach / G. Laporte, Y. Nobert // INFOR. - 1983. - V. 21, № 1. - P. 61-75.
16. Henry-Labordere, A.L. The Record-Balancing Problem: a Dynamic Programming Solution of a Generalized Travelling Salesman Problem / A.L. Henry-Labordere // Rev. Franc. Inform. Rech. - 1969. - V. 3 - № 2. - P. 43-49.
17. Лейтен, А.К. Некоторые модификации задачи коммивояжера / А.К. Лейтен // Тр. ВЦ Тарт. ун-та. - 1973. - Вып. 28. - С. 44-58.
18. Коротаева, Л.Н. Об одной модификации метода динамического программирования в задаче последовательного сближения / Л.Н. Коротаева, А.Н. Сесекин, А.Г. Ченцов // Журн. вычисл. математики и мат. физики. - 1989. - Т. 29, № 8. - C. 1107-1113.
19. Ченцов, А.А. О решении задачи маршрутной оптимизации методом динамического программирования / А.А. Ченцов, А.Г. Ченцов // Автоматика и телемеханика. - 1998. - № 9. - С. 117-129.
20. Ченцов, А.Г. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования / А.Г. Ченцов, П.А. Ченцов // Вестн. УГТУ-УПИ. На передовых рубежах науки и инженерного творчества. - Екатеринбург, 2004. - Ч. 1, № 15 (45) - С. 148-152.
21. Ченцов, А.А. О реализации метода динамического программирования в обобщенной задаче курьера / А.А. Ченцов, А.Г. Ченцов // Тр. Ин-та математики и механики УрО РАН. - 2007. - Т. 13, № 3. - С. 136-160.
22. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования / О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, А.Г. Ченцов// Изв. ВУЗов. Ядерная энергетика. - 2009. - № 2. - С. 115-120.
23. Возможности математических методов моделирования в решении проблемы снижения облучаемости персонала / О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, Ф.А. Балушкин, А.Г. Ченцов, А.П. Хомяков // Вопросы радиационной безопасности. - 2009. - № 4. - С. 39-49.
24. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения / А.Н. Сесекин, О.Л. Ташлыков, С.Е. Щеклеин, М.Ю. Куклин, А.Г. Ченцов, А.А. Кадников // Изв. ВУЗов. Ядерная энергетика. - 2006. - № 2. - С. 41-48.
25. Сесекин, А.Н. Задачи маршрутизации перемещений / А.Н. Сесекин, А.А. Ченцов, А.Г. Ченцов. - СПб: Лань, 2011. - 240 с.
26. Ташлыков, О.Л. Организация и технология атомной энергетики / О.Л. Ташлыков. - Екатеринбург: УГТУ-УПИ, 2005. - 148 с.