Построение фронта транспортной доступности

Фронт транспортной доступности представляет собой линию (изохрону), в каждую точку которой можно попасть из стартовой точки примерно при одном и том же уровне затрат L. В массиве накопленных затрат Q ищутся точки, удовлетворяющие условию: q (i)? L. Степень приближения должна быть задана (например, в процентах от уровня L). Узловым точкам изохроны соответствуют координаты (xi, yi). По этим координатам можно приближенно построить фронт транспортной доступности, соединив их отрезками прямых линий.

Алгоритм прокладки оптимального маршрута при комбинированном движении Комбинированное движение состоит из этапа движения по транспортной сети с использованием транспортных средств и этапа движения по пересеченной местности.

Построение первого приближения.

• 1. С помощью волнового алгоритма определяются достижимые затраты на перемещение из стартового узла во все узлы транспортной сети.
• 2. Узлы транспортной сети рассматриваются как стартовые точки для оптимального алгоритма движения по пересеченной местности, причем для стартовых точек задается начальный уровень затрат, полученный при расчете движения по транспортной сети.
• 3. С помощью волнового алгоритма рассчитывается оптимальный маршрут движения по пересеченной местности от множества стартовых точек.
• 4. Выделяется оптимальная стартовая точка (узел транспортной сети, принадлежащий оптимальному маршруту).

Точность первого приближения определяется максимальным расстоянием между оптимальной стартовой точкой и смежными с ней узлами.

Уточнение решения.

• 1. Сегменты транспортной сети, инцидентные оптимальной стартовой точке, детализируются дополнительным числом узлов.
• 2. С помощью волнового алгоритма определяются достижимые затраты на перемещение из стартового узла к вновь образованным дополнительным узлам транспортной сети. С помощью этапов фильтрации (ослабления дуг) уточняется решение на транспортной сети.
• 3. Множество дополнительных узлов сети вместе с оптимальной стартовой точкой рассматривается как стартовые точки для оптимального алгоритма движения по пересеченной местности, причем для стартовых точек задается уровень затрат, полученный при расчете движения по транспортной сети.
• 4. С помощью волнового алгоритма рассчитывается оптимальный маршрут движения по пересеченной местности от множества стартовых точек.
• 5. Выделяется оптимальная стартовая точка.
• 6. При необходимости построения точного маршрута выполняются этапы фильтрации в алгоритме движения по пересеченной местности.

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