Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования
Автор: Ченцов Александр Георгиевич, Ченцов Павел Александрович
Рубрика: Математическое моделирование
Статья в выпуске: 2 т.11, 2018 года.
Бесплатный доступ
Рассматривается задача маршрутизации перемещений с ограничениями и функциями стоимости, допускающими зависмость от списка заданий. Предполагается, что начальное условие процесса с дискретным временем может выбираться в пределах метрического пространства, удовлетворяющего условию полной ограниченности. По постановке задачи предполагается посещение конечной системы мегаполисов (непустых конечных множеств) с выполнением тех или иных работ, стоимости которых зависят всякий раз от пункта прибытия и пункта отправления. Стоимости перемещений и выполняемых работ агрегируются аддитивно. Для решения используется вариант широко понимаемого динамического программирования, обеспечивающий нахождение ε-оптимального решения при любом значении ε>0.
Маршрутная задача, ограничения, точка старта
Короткий адрес: https://sciup.org/147232888
IDR: 147232888 | УДК: 519.6 | DOI: 10.14529/mmp180207
Optimization of the start point in the GTSP with the precedence conditions
The paper is devoted to the routing problem with constraints and cost functions that can depend on the list of tasks. It is assumed that the initial condition for the process with discrete time can be selected within a metric space that satisfies the condition of complete boundedness. It is supposed that the problem includes a visiting of a finite system of megalopolises (non-empty finite sets) with the fulfillment of some works. The cost of these works each time depend on the point of arrival and the point of departure. The costs of movement and work are aggregated additively. For the problem solution widely understood dynamic programming method providing ε -optimal solution for any ε>0 is used.
Список литературы Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования
- Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - N.Y.: Springer, 2002.
- Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. - New Jersey: Princeton University Press, 2012.
- Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 9. - C. 3-34.
- Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 10. - C. 3-29.
- Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 11. - C. 3-26.
- Ченцов, А.Г. Задача маршрутизации с ограничениями, зависящими от списка заданий / А.Г. Ченцов, А.А. Ченцов // Доклады Академии наук. - 2015. - Т. 465, № 2. - C. 154-158.
- Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - C. 96-117.
- Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Автоматика и телемеханика. - 2012. - № 3. - С. 134-149.
- Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2012.
- Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - Т. 9. - С. 219-228.
- Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - Т. 9. - С. 202-218.
- Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, вып. 1. - C. 94-107.
- Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир. - 1970.
- Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир. - 1964.
- Кормен, Т. Алгоритмы: Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2002.
- Энгелькинг, Р. Общая топология / Р. Энгелькинг. - М.: Мир, 1986.
- Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ Регулярная и хаотическая динамика, 2008.
- Ченцов, А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.А. Ченцов, А.Г. Ченцов // Проблемы управления и информатики. - 2016. - № 1. - C. 41-54.
- 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.
- Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - № 1. - С. 59-82.
