Автоматика и телемеханика, № 4, 2017 Системный анализ и исследование операций 2017 г. А.А. ПЕТУНИН, д-р техн. наук (aapetunin@gmail.com) (Уральский Федеральный Университет, Екатеринбург), c А.А. ЧЕНЦОВ, канд. физ.-мат. наук (chentsov.a@binsys.ru) (Институт математики и механики им Н.Н. Красовского УрО РАН, Екатеринбург), А.Г. ЧЕНЦОВ, член-корр. <...> РАН (chentsov@imm.uran.ru), П.А. ЧЕНЦОВ, канд. физ.-мат. наук (chentsov.p@mail.ru) (Институт математики и механики им Н.Н. Красовского УрО РАН, Уральский Федеральный Университет, Екатеринбург) ЭЛЕМЕНТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В КОНСТРУКЦИЯХ ЛОКАЛЬНОГО УЛУЧШЕНИЯ ЭВРИСТИЧЕСКИХ РЕШЕНИЙ ЗАДАЧ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ1 Рассматриваются методы решения задач маршрутизации с условиями предшествования, использующие итерационные режимы на основе беллмановских вставок с пересчетом условий предшествования исходной задачи; предполагается, что размерность последней достаточно велика, что не позволяет в связи с трудностями вычислений непосредственно применять динамическое программирование в “глобальном” варианте. <...> Введение Настоящая работа посвящена исследованию методов решения задачи последовательного обхода мегаполисов с условиями предшествования. <...> Данная задача имеет своим прототипом известную труднорешаемую задачу коммивояжера (ЗК) [1–3], но содержит целый ряд существенных особенностей, многие из которых мотивированы соображениями прикладного характера. <...> В частности, проблемы такого рода возникают при разработке управляющих программ для листовой резки деталей на машинах с числовым программным управлением (ЧПУ); см. <...> . Резка осуществляется по эквидистантам контуров упомянутых деталей, которые достаточно плотно упакованы на листе, а множество возможных точек врезки в контуры и точек выключения инструмента можно ограничить конечным набором мегаполисов, что позволяет интерпретировать процесс резки в терминах дискретной оптимизационной модели. <...> 106 и размерность задачи о посещении мегаполисов <...>