Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования

Бесплатный доступ

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