ОБ ОДНОЙ ЗАДАЧЕ МАРШРУТИЗАЦИИ С ВНУТРЕННИМИ РАБОТАМИ

Илья Борисович Чеблоков, Александр Георгиевич Ченцов

Результат исследований: Вклад в журналСтатья

Аннотация

Рассматривается маршрутная задача о посещении сечений мультифункций с ограничениями в виде условий предшествования. Кроме того, по постановке предусматривается выполнение некоторых работ на упомянутых сечениях. Каждое решение определяется в виде упорядоченной пары, компоненты которой имеют смысл маршрута (перестановки индексов) и трассы (траектории) перемещений по сечениям мультифункций. Согласование трассы и маршрута реализуется на основе процедур последовательного выбора упорядоченных пар (пунктов прибытия и отправления) из декартовых квадратов сечений мультифункций, занумерованных в соответствии с маршрутом. Агрегирование стоимостей предполагается аддитивным; совокупный критерий включает стоимости (внешних) перемещений между сечениями мультифункций, внутренних работ и финального состояния. При построении расширения основной задачи, порождающего используемую далее функцию Беллмана, применяется эквивалентное преобразование ограничений: допустимость маршрутов по предшествованию заменяется допустимостью по вычеркиванию (заданий из списка), что соответствует варианту ограничений на текущие перемещения с одного множества на другое. Получен аналог уравнения Беллмана в виде процедуры преобразования слоёв функции Беллмана. Операция, определяющая данное преобразование, используется далее для построения эвристических алгоритмов, реализованных на ПЭВМ.
Переведенное названиеAbout one route problem with interior works
Язык оригиналаРусский
Страницы (с-по)298-317
Число страниц20
ЖурналТруды института математики и механики УрО РАН
Том18
Номер выпуска1
СостояниеОпубликовано - 2012

ГРНТИ

  • 27.41.00 Вычислительная математика

Уровень публикации

  • Перечень ВАК

Fingerprint Подробные сведения о темах исследования «ОБ ОДНОЙ ЗАДАЧЕ МАРШРУТИЗАЦИИ С ВНУТРЕННИМИ РАБОТАМИ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать