Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования
Автор: Ченцов Александр Георгиевич, Ченцов Павел Александрович
Рубрика: Математическое моделирование
Статья в выпуске: 2 т.11, 2018 года.
Бесплатный доступ
Рассматривается задача маршрутизации перемещений с ограничениями и функциями стоимости, допускающими зависмость от списка заданий. Предполагается, что начальное условие процесса с дискретным временем может выбираться в пределах метрического пространства, удовлетворяющего условию полной ограниченности. По постановке задачи предполагается посещение конечной системы мегаполисов (непустых конечных множеств) с выполнением тех или иных работ, стоимости которых зависят всякий раз от пункта прибытия и пункта отправления. Стоимости перемещений и выполняемых работ агрегируются аддитивно. Для решения используется вариант широко понимаемого динамического программирования, обеспечивающий нахождение ε-оптимального решения при любом значении ε>0.
Маршрутная задача, ограничения, точка старта
Короткий адрес: https://sciup.org/147232888
IDR: 147232888 | DOI: 10.14529/mmp180207
Список литературы Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования
- 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.
