Все выпуски

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

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

Предложенный алгоритм реализован в итерационном режиме: полученное после первой вставки на основе динамического программирования решение в виде пары «маршрут-трасса» принимается за исходное, для которого вновь конструируется вставка. При этом начало этой новой вставки выбирается случайно в пределах, определяемых возможностями формирования скользящего «окна» ощутимой, но все же достаточной для применения экономичной версии динамического программирования размерности. Далее процедура повторяется. Работа итерационного алгоритма иллюстрируется решением модельных задач, включая варианты с достаточно плотной «упаковкой» заготовок деталей на листе, что типично для машиностроительного производства.

Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.

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

Рассматривается модификация ранее разработанного генератора шестигранных сеток из воксельных данных для построения моделей, заданных в форме CAD геометрии. Генератор относится к семейству методов, основанных на модификации регулярной сетки, и является универсальным с точки зрения возможности использования в качестве исходных данных как объемного (воксельного), так и STL-поверхностного представления геометрии модели. В настоящее время алгоритм работает с CAD моделями, описанными в хорошо известном формате STL. Вместе с тем, метод позволяет обрабатывать поверхности более высокого порядка, описанные в произвольном формате, если определены соответствующие процедуры для операций проекции и пересечения. Для определения начальной позиции узлов сетки используется полученный из STL-геометрии файл объемных данных в виде «знакопределенных полей расстояний». Разработана специальная процедура проецирования с целью адаптации построенной ортогональной сетки к границам модели. Данный подход обеспечивает аппроксимацию острых ребер и углов и выполняется перед любыми другими операциями построения сетки. Реализован дополнительный функционал для улучшения качества сетки, включающий вставку дополнительных граничных слоев, разбиение ячеек плохого качества и оптимизированное сглаживание узлов. Алгоритм протестирован на значительном числе моделей, часть из которых приведена в качестве примеров.

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

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

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