Об одной задаче маршрутизации с внутренними работами

 pdf (301K)

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

Ключевые слова: маршрут, перестановка, трасса, функция Беллмана.
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2012, вып. 1, с. 96-119
DOI: 10.20537/vm120109

About one route problem with interior works

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.

Keywords: route, permutation, trace, Bellman function.
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2012, issue 1, pp. 96-119

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref