Модель «неаддитивной» задачи маршрутизации с функциями стоимости, зависящими от списка заданий

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

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

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

Литература

1. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.
2. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
3. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
4. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
5. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - М.: Мир, 1964. - Т. 9 - С. 219-228.
6. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - М.: Мир, 1964. - Т. 9. - С. 202-218.
7. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. -Т. 1. - С. 94-107.
8. The Travelling Salesman Problem and Its Variations (Combinatorial Optimization) / edt. by Gutin G.Z, Punnen A.P. - V. 12. - Dordrecht: Kluwer Academic Publishers, 2002. - 830 p.
9. Сергеев, С.И. Алгоритмы решения минимаксной задачи коммивояжера. I / С.И. Сергеев // Автоматика и телемеханика. - 1995. - № 7. - С. 144-150.
10. Сесекин, А.Н. Маршрутизация с абстрактной функцией агрегирования стоимостей перемещений / А.Н. Сесекин, А.А. Ченцов, А.Г. Ченцов // Труды Института математики и механики УрО РАН. - 2010. - Т. 16. - № 3. - С. 240-264.
11. Куратовский, К. Теория множеств / К. Куратовский, М. Мостовский. - М.: Мир, 1970. - 416 с.
12. Дьедонне, Ж. !Основы современного анализа! / !Ж. Дьедонне. !- !М.: Мир, !1964.
13. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - М.; Ижевск: НИЦ <<Регулярная и хаотическая динамика>>, Ижевский институт компьютерных исследований, 2008 - 240 с.
14. Ченцов, А.А. Экстремальная задача маршрутизации <<на узкие места>> с ограничениями в виде условий предшествования / А.А. Ченцов, А.Г. Ченцов // Труды Института математики и механики УрО РАН. - 2008. - Т. 14. - № 2. - С. 129-142.
15. Чеблоков, И.Б. Об одной задаче маршрутизации с внутренними работами / И.Б. Чеблоков, А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2012. - № 2. - С. 96-119.
16. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - № 1. - С. 59-82.