Оptimization of the Start Point in the Gtsp with the Precedence Conditions

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

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

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

Литература

1. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - N.Y.: Springer, 2002.
2. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. - New Jersey: Princeton University Press, 2012.
3. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 9. - C. 3-34.
4. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 10. - C. 3-29.
5. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 11. - C. 3-26.
6. Ченцов, А.Г. Задача маршрутизации с ограничениями, зависящими от списка заданий / А.Г. Ченцов, А.А. Ченцов // Доклады Академии наук. - 2015. - Т. 465, № 2. - C. 154-158.
7. Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - C. 96-117.
8. Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Автоматика и телемеханика. - 2012. - № 3. - С. 134-149.
9. Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2012.
10. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - Т. 9. - С. 219-228.
11. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - Т. 9. - С. 202-218.
12. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, вып. 1. - C. 94-107.
13. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир. - 1970.
14. Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир. - 1964.
15. Кормен, Т. Алгоритмы: Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2002.
16. Энгелькинг, Р. Общая топология / Р. Энгелькинг. - М.: Мир, 1986.
17. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ ' Регулярная и хаотическая динамика', 2008.
18. Ченцов, А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.А. Ченцов, А.Г. Ченцов // Проблемы управления и информатики. - 2016. - № 1. - C. 41-54.
19. Lawler, E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems / E.L. Lawler // CWI. Technical Reports. Stichting Mathematish Centrum. Mathematische Besliskunde. - 1979. - BW 106/79 - P. 1-16.
20. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - № 1. - С. 59-82.