Preview

Мехатроника, автоматизация, управление

Расширенный поиск

Динамическое программирование в задаче курьера со стоимостями, зависящими от списка заданий

Аннотация

Построена схема независимых вычислений функции Беллмана для задачи курьера (задача коммивояжера с условиями предшествования), в которой стоимости зависят от списка невыполненных (на текущий момент) заданий. Постановка и методы решения ориентированы на применение в задаче о демонтаже энергоблока АЭС, выведенного из эксплуатации.

Об авторах

А. Г. Ченцов
Институт математики и механики имени Н. Н. Красовского УрО PAH, Уральский федеральный университет, г. Екатеринбург
Россия


М. С. Кошелева
Институт математики и механики имени Н. Н. Красовского УрО PAH, Уральский федеральный университет, г. Екатеринбург
Россия


Список литературы

1. Ташлыков О. Л. Методы оценки и снижения дозовых нагрузок при ремонте АЭС: учеб. пособие. Екатеринбург: УГТУ-УПИ, 2009. 118 с.

2. Коробкин В. В., Сесекин А. Н., Ташлыков О. Л., Ченцов А. Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / Под общ. ред. член-корр. РАН И. А. Каляева. М.: Новые технологии, 2012. 234 с.

3. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. I. Вопросы теории; II. Точные алгоритмы; III. Приближенные алгоритмы // Автоматика и телемеханика. 1989. № 9. С. 3-34; № 10. С. 3-29; № 11. С. 3-26.

4. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1 (Вып. 1). С. 94-107.

5. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Kluwer, 2002. 830 р.

6. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернет. сборник. Т. 9. М.: Мир, 1964. С. 219-228.

7. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернет. сборник. Т. 9. М.: Мир, 1964. С. 202-218.

8. Ченцов А. Г. К вопросу о маршрутизации комплекса работ // Вестник Удм. ун-та. Математика. Механика. Комп. науки. 2013. № 1. С. 59-82.

9. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.: Ижевск: НИЦ "Регулярная и хаотическая динамика", 2008. 240 с.

10. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. 624 с.

11. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.

12. Сесекин А. Н., Ченцов А. А., Ченцов А. Г. Обобщенная задача курьера с функцией затрат, зависящей от списка заданий // Изв. РАН. ТиСУ. 2010. - № 2. С. 68-77.

13. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // Вестник ЮУрГУ. Сер. Мат. моделирование и программирование. 2012. № 18, вып. 12. С. 53-76.

14. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // АиТ. 2012. № 3. С. 134-149.

15. Кошелева М. С., Ченцов А. Г. Одна задача маршрутизации с ограничениями в виде условий предшествования // Проблемы управления и моделирования в сложных системах: Тр. XV Междунар. конф. Самара: Самар. НЦ РАН. 2013. С. 523-532.


Рецензия

Для цитирования:


Ченцов А.Г., Кошелева М.С. Динамическое программирование в задаче курьера со стоимостями, зависящими от списка заданий. Мехатроника, автоматизация, управление. 2015;16(4):232-244.

For citation:


Chentsov A.G., Kosheleva M.S. Dynamic Programming in the Precedence Constrained TSP with the Costs Depending on a List of Tasks. Mekhatronika, Avtomatizatsiya, Upravlenie. 2015;16(4):232-244. (In Russ.)

Просмотров: 304


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-6427 (Print)
ISSN 2619-1253 (Online)