Все выпуски

В статье рассматривается экстремальная задача маршрутизации с ограничениями. В общей формулировке предполагается, что объектами посещения являются любые непустые конечные множества — мегаполисы. Основной прикладной задачей, рассматриваемой в данном исследовании, является задача оптимизации траектории движения инструмента для станков листовой резки с ЧПУ, известная как проблема пути резания. Эта проблема возникает на этапе разработки управляющих программ для станков с ЧПУ. Возможны и другие приложения. В частности, результаты исследования могут быть использованы в задаче минимизация дозы облучения при демонтаже системы радиационно-опасных элементов после аварий на АЭС и в транспортных проблемах. В качестве ограничений исследуются ограничения предшествования. Они могут быть использованы для уменьшения вычислительной сложности. В качестве основного метода исследования использовалось широко понимаемое динамическое программирование. Предлагаемая реализация метода учитывает ограничения предшествования и зависимость целевых функций от списка задач. Последняя относится к классу очень сложных состояний, которые определяют допустимость маршрута на каждом шаге маршрутизации, в зависимости от уже выполненных или, наоборот, еще не завершенных задач. Применительно к задаче резки зависимость целевой функции от списка задач позволяет уменьшать термические деформации материала при резке. В работе математическая формализация экстремальной задачи маршрутизации с дополнительными ограничениями, описание метода и полученный с его помощью точный алгоритм. Оптимизации подлежат порядок выполнения задач, конкретная траектория процесса, и его начальная точка.

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.

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

Issues related to solving the additive problem of sequential traversal of sets with precedence restrictions and cost functions that allow dependence on the list of tasks are considered. The basic method is a broadly understood dynamic programming (DP), supplemented in the case of problems of appreciable dimension by decompositions of the family of tasks and transformation of the parameters of the original problem. Possible applications are related, in particular, to the problem of tool control in figured sheet cutting of parts on CNC machines. In this problem, an important circumstance is taking into account the precedence conditions, which have, in particular, the following meaning: in the case of a part with holes, cutting of each of the internal contours (corresponding to the holes) should precede cutting of the external contour. The quality criterion itself in this problem, as a rule, is additive. Another type of constraints concerns avoiding thermal deformations of parts. When using the approach with penalties for violating the conditions associated with effective heat dissipation during cutting, cost functions arise that allow dependence on the list of tasks completed to date. Note that in another applied problem, namely, in the problem of dismantling radiation hazardous objects, cost functions arise with dependence on the list of tasks that have not been completed at the moment (and, consequently, concern the objects that have not been dismantled). As a result, we arrive at a very general problem with precedence constraints and cost functions with dependence on the list of tasks. The decomposition applied in the case of a noticeable dimensionality with subsequent implementation of the DP requires, on the one hand, the development of clustering methods, and, on the other, the construction of an adequate structure for distributing global precedence conditions among clusters. In the theoretical part of the work, the case of two clusters is discussed, which makes it possible to cover with a single scheme a number of practically interesting problems of a range (in terms of dimensionality) type. An algorithm for constructing a composite solution is indicated, including a stage of clustering training based on a greedy algorithm. This “composite” algorithm is implemented on a PC; a computational experiment was carried out.

Рассматривается маршрутная задача о посещении сечений мультифункций с ограничениями в виде условий предшествования. Кроме того, по постановке предусматривается выполнение некоторых "работ" на упомянутых сечениях. Каждое решение определяется в виде упорядоченной пары, компоненты которой имеют смысл маршрута (перестановки индексов) и трассы (траектории) перемещений по сечениям мультифункций. Согласование трассы и маршрута реализуется на основе процедур последовательного выбора упорядоченных пар (пунктов прибытия и отправления) из декартовых "квадратов" сечений мультифункций, занумерованных в соответствии с маршрутом. Агрегирование стоимостей предполагается аддитивным; совокупный критерий включает стоимости (внешних) перемещений между сечениями мультифункций, внутренних "работ" и финального состояния. При построении расширения основной задачи, порождающего используемую далее функцию Беллмана, применяется эквивалентное преобразование ограничений: допустимость маршрутов по предшествованию заменяется допустимостью по вычеркиванию (заданий из списка), что соответствует варианту ограничений на текущие перемещения с одного множества на другое. Получен аналог уравнения Беллмана в виде процедуры преобразования слоёв функции Беллмана. Операция, определяющая данное преобразование, используется далее для построения эвристических алгоритмов, реализованных на ПЭВМ.

The route problem about visiting of multifunction sections with constraints of type of preceding conditions is considered. By setting of this problem the fulfilment of works on the above-mentioned sections is provided. Any solution is defined in the form of the ordered pair for which components have the sense of the route (the index permutation) and the trace (trajectory) of the movements with respect to sections of multifunctions. The agreement of the trace and route is realized by procedures of the sequential choice of ordered pairs (the point of arrival and the starting point) of Descartes "squares" of the multifunction sections numbered in correspondence with a route. The cost aggregation is presupposed additive; the total criterion includes the costs of (exterior) movements between sections of multifunctions, interior works, and the final state. Under constructing of extension of the basic problem that realizes the used Bellman function, the equivalent transformation of constraints is applied: admissibility of routes by preceding is replaced onto admissibility by deletion of tasks (of the list) that corresponds to the constraints variant with respect to the current movements from one set onto another. An analog of the Bellman equation realized by procedure of the transformation of layers of Bellman function is obtained. The operation defining this transformation is further used for constructing of heuristic algorithms realized on PC.

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

The paper considers the problem of reducing the complexity of $NP$-hard problems by using related problems for which an optimal or acceptable solution is already known. For multi-agent routing tasks, a technique is used based on network clustering consistent with traveling salesman routes on each cluster and constructing routes that take into account the limitation of delivery time windows. A mathematical model is presented that corresponds to a block of pseudo-Boolean conditional optimization with constraints in the form of disjunctive normal forms that allows polynomial solvability and a block of time constraints. The results of choosing metaheuristics based on related problems are used in a program for the delivery of goods by many agents to consumers located at the vertices of the regional infrastructure road network.

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

The problem of sequential traversal of megapolises with precedence conditions is investigated; this problem is oriented to mechanical engineering — CNC metal cutting machines. There is the following setting singularity: the terminal component of additive criterion contains the dependence on the starting point. This singularity leads to the fact that the natural solution procedure based on dynamic programming must be applied individually for every starting point. The investigation goal consists in the construction of an optimizing algorithm for determining a complex including a route (a variant of megapolis numbering), a trajectory, and a starting point. The proposed algorithm realizes an idea of directed enumeration of starting points. This algorithm is realized as a program for PC; computations for model examples are made.