Обобщенная модель курьера с дополнительными ограничениями

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

Ключевые слова

маршрут; трасса; условия предшествования.

Литература

1. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
2. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
3. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
4. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - Berlin: Springer, 2002.
5. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - Т. 9. - С. 219-228.
6. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - Т. 9. - С. 202-218.
7. Петунин, А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала / А.А. Петунин // Вестник Уфимского государственного авиационного технического университета. - 2009. - Т. 13, № 2 (35). - C. 280-286.
8. Петунин, А.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов // Научно-технические ведомости СПбГПУ. Серия: Информатика. Телекоммуникации. Управление. - 2013. - № 2 (169). - С. 103-111.
9. Петунин, А.А. Об одной задаче маршрутизации перемещений инструмента при листовой резке деталей / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов // Моделирование и анализ информационных систем. - 2015. - № 2. - С. 278-294.
10. Фроловский, В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ / В.Д. Фроловский // Информационные технологии в проектировании и производстве. - 2005. - № 4. - С. 63-66.
11. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций // В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов; под общ. ред. И.А. Каляева. - М.: Новые технологии, 2012.
12. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
13. Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
14. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 1999.
15. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. / А.Г. Ченцов. - Москва; Ижевск: РХД, 2008.
16. Ченцов, А.Г. Задача последовательного обхода мегаполисов с условиями предшествования / А.Г. Ченцов // Автоматика и телемеханика. - 2014. - № 4. - С. 170-190.
17. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - № 1. - С. 58-82.
18. Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Автоматика и телемеханика. - 2012. - № 3. - С. 134-149.
19. Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. - 2012. - № 3. - С. 44-52.