A model of "nonadditive" routing problem where the costs depend on the set of pending tasks

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

We consider a generalization of the bottleneck (minimax) routing problem. The problem is to successively visit a number of megalopolises, complicated by precedence of constraints imposed on the order of megalopolises visited and the fact that the cost functions (of movement between megalopolises and of interior tasks) may explicitly depend on the list of tasks that are not completed at the present time. The process of movement is considered to be a sequence of steps, which include the exterior movement to the respective megalopolis and the following completion of (essentially interior) jobs connected with the megalopolis. The quality of the whole process is represented by the maximum cost of steps it consists of; the problem is to minimize the mentioned criterion (which yields a minimax problem, usually referred to as a "bottleneck problem"). Optimal solutions, in the form of a route-track pair (a track, or trajectory, conforms to a specific instance of a tour over the megalopolises, which are numbered in accordance with the route; the latter is defined by the transposition of indices), are constructed through a "nonstandard" variant of the dynamic programming method, which allows to avoid the process of constructing of all the values of the Bellman function whenever precedence constraints are present.

Еще

Dynamic programming, route, precedence constraints, sequential ordering problem

Короткий адрес: https://sciup.org/147159302

IDR: 147159302   |   DOI: 10.14529/mmp150102

Список литературы A model of "nonadditive" routing problem where the costs depend on the set of pending tasks

  • Гэри, М. Вычислительные машины и труднорешаемые задачи/М. Гэри, Д. Джонсон. -М.: Мир, 1982. -416 с.
  • Меламед, И.И. Задача коммивояжера. Вопросы теории/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 9. -С. 3-34.
  • Меламед, И.И. Задача коммивояжера. Точные алгоритмы/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 10. -С. 3-29.
  • Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 11. -С. 3-26.
  • Беллман, Р. Применение динамического программирования к задаче о коммивояжере/Р. Беллман//Кибернетический сборник. -М.: Мир, 1964. -Т. 9 -С. 219-228.
  • Хелд, М. Применение динамического программирования к задачам упорядочения/М. Хелд, Р.М. Карп//Кибернетический сборник. -М.: Мир, 1964. -Т. 9. -С. 202-218.
  • Алгоритм для решения задачи о коммивояжере/Дж. Литл, К. Мурти, Д. Суини, К. Кэрел//Экономика и математические методы. -1965. -Т. 1. -С. 94-107.
  • 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.
  • Сергеев, С.И. Алгоритмы решения минимаксной задачи коммивояжера. I/С.И. Сергеев//Автоматика и телемеханика. -1995. -№ 7. -С. 144-150.
  • Сесекин, А.Н. Маршрутизация с абстрактной функцией агрегирования стоимостей перемещений/А.Н. Сесекин, А.А. Ченцов, А.Г. Ченцов//Труды Института математики и механики УрО РАН. -2010. -Т. 16. -№ 3. -С. 240-264.
  • Куратовский, К. Теория множеств/К. Куратовский, М. Мостовский. -М.: Мир, 1970. -416 с.
  • Дьедонне, Ж. !Основы современного анализа!/!Ж. Дьедонне. !-!М.: Мир, !1964.
  • Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории/А.Г. Ченцов. -М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008 -240 с.
  • Ченцов, А.А. Экстремальная задача маршрутизации "на узкие места" с ограничениями в виде условий предшествования/А.А. Ченцов, А.Г. Ченцов//Труды Института математики и механики УрО РАН. -2008. -Т. 14. -№ 2. -С. 129-142.
  • Чеблоков, И.Б. Об одной задаче маршрутизации с внутренними работами/И.Б. Чеблоков, А.Г. Ченцов//Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. -2012. -№ 2. -С. 96-119.
  • Ченцов, А.Г. К вопросу о маршрутизации комплексов работ/А.Г. Ченцов//Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. -2013. -№ 1. -С. 59-82.
Еще
Статья обзорная