Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры


https://doi.org/10.18255/1818-1015-2011-3-101-124

Полный текст:


Аннотация

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

Об авторах

Алексей Михайлович Григорьев
Институт математики и механики УрО РАН
Россия


Евгений Евгеньевич Иванко
Институт математики и механики УрО РАН
Россия


Александр Георгиевич Ченцов
Институт математики и механики УрО РАН
Россия


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

1. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989. №9. С. 3-34.

2. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика, 1989. №10. С. 3-29.

3. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика, 1989. №11. С. 3-26.

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

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

6. Сергеев С.И. Гибридные системы управления и динамическая задача коммивояжера // Автоматика и телемеханика, 2008. №1. С. 45-54.

7. Сигал И.X., Иванова A.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Наука, 2007. С. 304.

8. Ченцов А.А., Чепцов А.Г., Чепцов П.A. Экстремальная задача маршрутизации с внутренними потерями / / Труды Института математики и механики УрО РАН. 2008. Т.14, №3. С. 183-200.

9. Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии Наук. 2008. Т.423, №3. С. 303-307.

10. Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Известия РАН. Теория и системы управления. 2010. №3. С. 52-66.

11. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. С. 64-81.

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

13. Коротаева Л.П., Сесекин А.П., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат, физики, 1989. Т. 29, № 8. С. 1107-1113.

14. Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журн. вычисл. математики и мат. физики, 1993. Т. 33, № 4. С. 483-494.

15. Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования / / Автоматика и телемеханика. 1998. № 9. С. 117-129.

16. Ченцов А.Г., Ченцов П.А. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования // Вестник УГТУ- УПИ. Екатеринбург, 2004. Ч. 1. №15 (45). С. 148-152.

17. Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 с.

18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.

19. Сесекин А.Н., Ташлыков О.Л., Щеклеин С.Е., Куклин М.Ю., Ченцов А.Г., Кадников А. А. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения // Известия вузов. Ядерная энергетика. 2006. № 2. С. 41-48.

20. Ташлыков О. Л., Сесекин А.Н., Ченцов А. Г., Щеклеин С. К., Балушкин Ф. А., Хомяков А. П. Возможности математических методов моделирования в решении проблемы облучаемости персонала // Вопросы радиационной безопасности. 2009. № 4. С. 39-49.

21. Ташлыков О.Л., Сесекин А.Н.. Щеклеин С.Е., Ченцов А.Г. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования // Известия вузов. Ядерная энергетика. 2009. № 2. С. 115-120.


Дополнительные файлы

Для цитирования: Григорьев А.М., Иванко Е.Е., Ченцов А.Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры. Моделирование и анализ информационных систем. 2011;18(3):101-124. https://doi.org/10.18255/1818-1015-2011-3-101-124

For citation: Grigoriev A.M., Ivanko E.E., Chentsov A.G. Dynamic Programming in a Generalized Courier Problem with Inner Tasks: Elements of a Parallel Structure. Modeling and Analysis of Information Systems. 2011;18(3):101-124. (In Russ.) https://doi.org/10.18255/1818-1015-2011-3-101-124

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

Обратные ссылки

  • Обратные ссылки не определены.


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


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)