On the Nonstationary Variant of Generalized Courier Problem with Interior Works
Abstract
The problem of the sequential circuit of megalopolises with preceding conditions and necessity of the interior works in megalopolises is considered in the article. It is supposed that the costs of permutations depend on the parameter having the sense of a discrete time. The above-mentioned dependence can reflect priorities of clients connected with served megalopolises and partially compensating inputs of executers. The constructed method corresponds to dynamic programming in a broad sense which is applied to solve the route problem with constraints. The extension of the problem, which use equivalent transformation of the system of constraints as a result of which route admissibility by precedence is changed into admissibility by deletion (the task from the list), introduced in the article. Therefore route constraints are reduced to the system of constraints by current interchange that allows us to obtain Bellman equations. To apply the later in the computational procedure of layers construction of Bellman equation we use the approach which implies the construction of the whole array of the values for the function mentioned; this approach is based on the use of essential lists of tasks (by precedence), which the saving of computations is achieved by.
References
Ченцов, А.А. Экстремальная задача маршрутизации с внутренними потерями / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Труды Института математики и механики УрО РАН. - 2008. - Т. 14, № 3. - С. 183-201.
Ченцов, А.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Изв. ВУЗов. Математика. - 2010. - № 6. - C. 64-81.
Ченцов, А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями / А.Г. Ченцов // Изв. РАН. Теория и системы управления. - 2010. - № 3. - C. 52-66.
Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский ин-т компьютер. исследований, 2008. - 240 с.
Тонков, Л.В. К вопросу оптимального выбора маршрута в условиях временного дисконтирования / Л.В. Тонков, А.Г. Ченцов // Кибернетика и систем. анализ. - 1999. - № 1. - С. 95-106.
Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970. - 416 c.
Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2002. - 960 с.
Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон; пер. с англ. Е.В. Левнера и М.А. Фрумкина. - М.: Мир, 1982. - 416 с.
Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
Алгоритмы для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, вып. 1. - С. 94-107.
Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - М.: Мир, 1964. - Т. 9. - С. 219-228.
Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - М.: Мир, 1964. - Т. 9. - С. 202-218.
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.
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.
Лейтен, А.К. Некоторые модификации задачи коммивояжера / А.К. Лейтен // Тр. ВЦ Тарт. ун-та. - 1973. - Вып. 28. - С. 44-58.
Коротаева, Л.Н. Об одной модификации метода динамического программирования в задаче последовательного сближения / Л.Н. Коротаева, А.Н. Сесекин, А.Г. Ченцов // Журн. вычисл. математики и мат. физики. - 1989. - Т. 29, № 8. - C. 1107-1113.
Ченцов, А.А. О решении задачи маршрутной оптимизации методом динамического программирования / А.А. Ченцов, А.Г. Ченцов // Автоматика и телемеханика. - 1998. - № 9. - С. 117-129.
Ченцов, А.Г. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования / А.Г. Ченцов, П.А. Ченцов // Вестн. УГТУ-УПИ. На передовых рубежах науки и инженерного творчества. - Екатеринбург, 2004. - Ч. 1, № 15 (45) - С. 148-152.
Ченцов, А.А. О реализации метода динамического программирования в обобщенной задаче курьера / А.А. Ченцов, А.Г. Ченцов // Тр. Ин-та математики и механики УрО РАН. - 2007. - Т. 13, № 3. - С. 136-160.
Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования / О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, А.Г. Ченцов// Изв. ВУЗов. Ядерная энергетика. - 2009. - № 2. - С. 115-120.
Возможности математических методов моделирования в решении проблемы снижения облучаемости персонала / О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, Ф.А. Балушкин, А.Г. Ченцов, А.П. Хомяков // Вопросы радиационной безопасности. - 2009. - № 4. - С. 39-49.
Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения / А.Н. Сесекин, О.Л. Ташлыков, С.Е. Щеклеин, М.Ю. Куклин, А.Г. Ченцов, А.А. Кадников // Изв. ВУЗов. Ядерная энергетика. - 2006. - № 2. - С. 41-48.
Сесекин, А.Н. Задачи маршрутизации перемещений / А.Н. Сесекин, А.А. Ченцов, А.Г. Ченцов. - СПб: Лань, 2011. - 240 с.
Ташлыков, О.Л. Организация и технология атомной энергетики / О.Л. Ташлыков. - Екатеринбург: УГТУ-УПИ, 2005. - 148 с.
