|
Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2012, выпуск 1, страницы 96–119
(Mi vuu313)
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
МАТЕМАТИКА
Об одной задаче маршрутизации с внутренними работами
И. Б. Чеблоковa, А. Г. Ченцовb a Кафедра вычислительных методов и уравнений математической
физики, Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, Россия, г. Екатеринбург
b Отдел управляемых систем, Институт математики и механики УрО РАН, Россия, г. Екатеринбург
Аннотация:
Рассматривается маршрутная задача о посещении сечений мультифункций с ограничениями в виде условий предшествования. Кроме того, по постановке предусматривается выполнение некоторых “работ” на упомянутых сечениях. Каждое решение определяется в виде упорядоченной пары, компоненты которой имеют смысл маршрута (перестановки индексов) и трассы (траектории) перемещений по сечениям мультифункций. Согласование трассы и маршрута реализуется на основе процедур последовательного выбора упорядоченных пар (пунктов прибытия и отправления) из декартовых “квадратов” сечений мультифункций, занумерованных в соответствии с маршрутом. Агрегирование стоимостей предполагается аддитивным; совокупный критерий включает стоимости (внешних) перемещений между сечениями мультифункций, внутренних “работ” и финального состояния. При построении расширения основной задачи, порождающего используемую далее функцию Беллмана, применяется эквивалентное преобразование ограничений: допустимость маршрутов по предшествованию заменяется допустимостью по вычеркиванию (заданий из списка), что соответствует варианту ограничений на текущие перемещения с одного множества на другое. Получен аналог уравнения Беллмана в виде процедуры преобразования слоёв функции Беллмана. Операция, определяющая данное преобразование, используется далее для построения эвристических алгоритмов, реализованных на ПЭВМ.
Ключевые слова:
маршрут, перестановка, трасса, функция Беллмана.
Поступила в редакцию: 09.02.2011
Образец цитирования:
И. Б. Чеблоков, А. Г. Ченцов, “Об одной задаче маршрутизации с внутренними работами”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2012, № 1, 96–119
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vuu313 https://www.mathnet.ru/rus/vuu/y2012/i1/p96
|
Статистика просмотров: |
Страница аннотации: | 365 | PDF полного текста: | 159 | Список литературы: | 44 | Первая страница: | 1 |
|