пути по нескольким критериям сводится к решениюзадачи поиска
кратчайшего пути по нескольким критериям (MOSP, multi-objective
shortest path) — основной задачи в области многоцелевой оптимиза-
ции [5]. Задача многокритериальной оптимизации обычно NP-полная
(действительно, в случае MOSP), так как размер набора Парето обыч-
но экспоненциально возрастает. Даже для очень простых графов (цепь
узлов, соединенных ребрами) в задаче с двумя критериями число ре-
шений в наборе Парето растет экспоненциально. Поэтому на практике
для нахождения решения многокритериальной задачи используются
приближенные подходы. Можно применить такой подход, как отно-
сительная важность критериев оптимизации по весу и последующая
оптимизация весовой суммы. Этот подход сводит многокритериаль-
нуюзадачу к задаче с одним параметром, которая может быть решена
стандартным алгоритмом Дейкстры (используется модель, где каждый
критерий неотрицателен и аддитивен). Недостаток такого подхода —
проблемы выбора подходящих весовых параметров. Каждый пассажир
имеет свои предпочтения, и система может установить параметры не-
верно.
Еще один способ выбрать одно Парето-оптимальное решение — это
лексикографический порядок
. В упрощенной версии время–расширен-
ного подхода лексикографически первое решение может быть рассчи-
тано для любого
d
значений как вес ребер. Например, если
d
= 2
и
первый элемент — время в пути, а второй — число пересадок, то среди
всех быстрых путей находится один с минимальным числом переса-
док. В практической версии время–расширенного подхода могут быть
использованы только те критерии, где первый критерий — время в
пути.
Исследования известных алгоритмов поиска по расписаниям пока-
зали, что без применения специальной ускоряющей техники (модер-
низации алгоритмов) производительность обычно оказывается недо-
статочной. Средняя производительность особенно важна в системах с
центральным сервером, который должен обрабатывать сотни запросов
одновременно, например в Интернете или на транспортных термина-
лах (вокзалах, аэропортах). Подходы, описанные для решения упро-
щенной задачи наискорейшего прибытия, были хорошо изучены для
время–расширенной и время–зависимой моделей. Нахождение всех
подходящих путей с учетом времени пути, стоимости, числа переса-
док, естественно, гораздо сложнее, чем просто поиск наискорейшего
пути.
Алгоритм, который гарантирует точное решение (оптимальный
путь) для любого запроса, называют
сохраняющим расстояние
алго-
ритмом. На практике такие алгоритмы используются не очень часто,
так как время их работы обычно оказывается недопустимо большим.
102 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4
