Dynamic programming in the routing problem: decomposition variant

Cover Page

Cite item

Full Text

Abstract

The questions of applying the dynamic programming (DP) apparatus to the routing problem with constraints and cost functions with the tasks list dependence are investigated. It is supposed that binary partition of the task set is given; tasks of the first task group must be fulfilled before the fulfillment of the task of the second group begins. In each of the groups, precedence conditions may be present. This setting can be applied in the case of sheet cutting on CNC machines, where two above-mentioned groups form zones planned at the cutting stage. In general case, for the optimal solution construction, the two-stage variant of DP is used. Linking two versions of DP is realized by identification of the criterion terminal component for service problem of the first group with extremum function connected with the second group. The connection of optimal solutions for above-mentioned two problems allows to construct an optimal solution for the initial joint problem. Based on the theoretical constructions algorithm realized on personal computer is constructed; computing experiment is realized.

About the authors

Aleksandr G. Chentsov

N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences; Ural Federal University named after the first President of Russia B. N. Yeltsin

Email: chentsov@imm.uran.ru
Doctor of Physics and Mathematics, Corresponding Member of the Russian Academy of Sciences, Chief Researcher; Professor 16 S. Kovalevskaya St., Yekaterinburg 620108, Russian Federation; 19 Mira St., Yekaterinburg 620002, Russian Federation

Pavel A. Chentsov

N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences; Ural Federal University named after the first President of Russia B. N. Yeltsin

Email: chentsov.p@mail.ru
Candidate of Physics and Mathematics, Senior Researcher; Senior Researcher 16 S. Kovalevskaya St., Yekaterinburg 620108, Russian Federation; 19 Mira St., Yekaterinburg 620002, Russian Federation

References

  1. G. Gutin, A.P. Punnen, The Traveling Salesman Problem and its Variations, Springer, Berlin, 2002, 850 pp.
  2. W.J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University, United States, 2012, 228 pp.
  3. Э.Х. Гимади, М.Ю. Хачай, Экстремальные задачи на множествах перестановок, УМЦ УПИ, Екатеринбург, 2016, 216 с.
  4. M. Kubo, H. Kasugai, “The precedence constrained traveling salesman problem”, Journal of the Operations Research Society of Japan, 34:2 (1991), 152-172.
  5. Y. Salii, “Revisisting dynamic programming for precedence-constrained Traveling Salesman Problem and its time-dependent generalization”, European Journal of Operational Research, 272:1 (2019), 32-42.
  6. E. Balas, “New classes of efficiently solvable generalized Taveling Salesman Problems”, Annals of Operations Research, 86 (1999), 529-558.
  7. J.A. Chisman, “The clustered traveling salesman problem”, Computers and Operation Research, 2:2 (1975), 115-119.
  8. М.Ю. Хачай, Е.Д. Незнахина, “Приближенные схемы для обобщенной задачи коммивояжера”, Тр. ИММ УрО РАН, 22, 2016, 283-292.
  9. F.C.J. Lokin, “Procedures for traveling salesman problems with additional constraints”, European of Journal Operation al. Research, 3:2 (1979), 135-141.
  10. С.С. Лебедев, “О декомпозиции некоторых прикладных задач дискретной оптимизации”, Экономика и математические методы, 44:2 (2008), 121-125.
  11. В.И. Цурков, Декомпозиция в задачах большой размерности, Наука, М., 1981, 350 с.
  12. А.А. Первозванский, В.Г. Гайцгори, Декомпозиция, агрегирование и приближенная оптимизация, Наука, М., 1975, 344 с.
  13. А.Г. Ченцов, Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, Ижевский институт компьютерных исследований, Ижевск, 2008, 238 с.
  14. Р. Беллман, “Применение динамического программирования к задаче о коммивояжере”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 219-222.
  15. М. Хелд, Р.М. Карп, “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 202-218.
  16. А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов, “Экстремальная задача маршрутизации с внутренними потерями”, Тр. ИММ УрО РАН, 14, 2008, 183-201.
  17. A.G. Chentsov, P.A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 54 (2019), 102-121.
  18. А.Г. Ченцов, П.А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автоматика и телемеханика, 2016, №11, 96-117.
  19. А.Г. Ченцов, “К вопросу о маршрутизации комплексов работ”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, №1, 59-82.
  20. К. Куратовский, А. Мостовский, Теория множеств, Мир, М., 1970, 416 с.
  21. Ж. Дьедонне, Основы современного анализа, Мир, М., 1964, 430 с.
  22. Т. Кормен, Ч. Лейзерсон, Р. Ривест, Алгоритмы: построение и анализ, МЦНМО, М., 2000, 955 с.
  23. Дж. Варга, Оптимальное управление дифференциальными и функциональными уравнениями, Наука, М., 1977, 624 с.
  24. А.А. Петунин, А.Г. Ченцов, П.А. Ченцов, Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы, Издательство Уральского университета, Екатеринбург, 2020, 247 с.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».