Все выпуски

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

The article deals with the problem of admissible routing for a system of cycles each of which contains exterior permutation and works connected with megalopolises (non-empty finite sets) visiting. In the initial setting, a resource constraint is given; this constraint should be fulfilled for every cycle under permutation. The solvability conditions in this problem are connected with the extremum of the auxiliary bottleneck routing problem without above-mentioned constraint, in which the apparatus of widely understood dynamic programming (DP) is used. A particular case of the setting is the known bottleneck courier problem which can be used (in particular) for routing a vehicle (airplane or helicopter) aiming to realize the given shipping system with a limited fuel reserve on each flight. An algorithm implemented on a personal computer is constructed.

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

A minimax routing problem with decomposition elements is considered. In the simplest case, it is supposed that the whole set of tasks is divided into a sum of two subsets (clusters), and execution of tasks from the second subset can be started only after the completion of all tasks from the first subset. For above-mentioned two-cluster problem, an algorithm has been constructed for finding the optimal compositional solution, including a route (permutation of task indices) and a starting point, which is based on the use of a broadly understood dynamic programming. Based on this approach, an algorithm was also constructed to solve the routing problem in the case of an arbitrary ordered finite set of clusters. The algorithm was implemented on a PC, and a computational experiment was carried out. Possible applications may be associated with some logistics tasks in small aviation, when it is necessary to ensure visits to many points by one vehicle (airplane, helicopter) with a limited non-stop flight range.

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

The complicated variant of the problem of sequential megalopolis circuit with constraints in the form of preceding conditions is considered. The additional constraints on the junction character for fragments of exterior permutations and interior works (with respect to megalopolis) are imposed upon. It is supposed that costs of exterior permutations and interior works depend on the task list explicitly. The procedure of the dynamic programming type and (on their base) algorithm on the functional level are constructed.

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

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

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

The problem of sequential megalopolis circuit with constraints in the form of preceding conditions and (interior) works realized in the megalopolises is considered. The singularity is a dependence of costs of exterior permutations and interior works on the task list. The iteration method with elements of decompositions of the joint solution defined as a pair «route-trace» is constructed.

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

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.

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

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

The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation.

The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.