---

          Оптимизация маршрутов на дорожной сети

 

Автор: Степанов В. П.

Источник: Публикация [Перейти]
     

УДК 681.3 Россия, МГТУ им. Н.Э. Баумана

Постановка задачи 

Известными для решения задачи являются: дорожная сеть города, место отправления  и место назначения.  Необходимо выбрать оптимальный и все близкие к нему маршруты проезда из места отправления до места назначения, которые учитывают реальную обстановку на дорогах: возможные заторы на дорогах и варианты их объезда, задержки перед светофорами на перекрестках, различные скорости движения транспорта на отдельных участках дорожной сети города.

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

Существует ряд реализованных программ, позволяющих искать кратчайший путь проезда по дорожной сети на электронной карте. В рассмотренных системах используются различные критерии оптимальности пути – от критерия кратчайшего расстояния до сложных критериев оценки времени с учетом информации о пробках. В отмеченных работах в основном рассматривается алгоритмы поиска только оптимального пути. Только в работе описан алгоритм поиска K маршрутов отклонения от оптимального на основе оптимального маршрута, проходящего через  K вершин графа.

Математическая модель. Множество всех возможных трасс поездки по улицам города представляется в виде ориентированного графа G= (A, W), где A –  множество вершин, W – множество дуг. Вершинам этого графа соответствуют: перекрестки на улицах города, место отправления i∈A и место назначения j∈A. Вершины графа - это места дорожной сети, где имеются возможности  выбора дальнейшего маршрута поездки по городу. Ребрам графа соответствуют магистрали и улицы между  двумя вершинами.  Для ребер графа задаются матрица расстояний L= |l_sd| и матрица возможных скоростей движения С = |с_sd|,  s, d∈A.  Для каждой вершины графа s∈Aс учетом наличия или отсутствия светофора задаются  значения z_s – время задержки на перекрестке. Тогда t_sd – время движения по ребру (s, d) определяется по формуле: t_sd = l_sd/ с_sd +z_s, s, d ∈ A.                                      

Для заданных  начальных и конечных вершин графа i и j  требуется определить маршрут проезда R_ij, затрачивающего минимальное время, а также множество всех близких к оптимальному  маршрутов, которые отличаются от оптимального на заданную величину Ε. Определение множества всех близких к оптимальному маршрутов позволяет при окончательном выборе  учесть дополнительные неформализованные требования.

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

Как известно, в алгоритме Дейкстры для поиска кратчайшего пути вершинам графа приписывают временные или постоянные пометки. Пометки определяют для вершины верхнюю границу длины пути отi вершины до текущей. Величины временных пометок вершин постепенно уменьшаются. Значение пометки определяет возможную длину пути от начальной до этой вершины. На каждом шаге алгоритма только одна из пометок с минимальным значением на рассматриваемом уровне выбирается в качестве постоянной. Это значит, что значение пометки является длиной кратчайшего пути из i вершины в текущую вершину.

Введем следующие обозначения: V(s) – множество ребер, входящих или выходящих из вершины s, где  (V(s) ⊆ W); |V(s)| – мощность  множества;  p_sj – пометки  вершины s ∈ A, j= 0, 2, …,|V(s)|-1;  B – множество вершин с постоянными пометками для j = 0.

Алгоритм первого этапа поиска оптимального маршрута состоит из шести шагов:

Шаг 1. Присвоить пометке начальной вершины p_i0 = 0 и считать постоянной. Для всех остальных вершин s ∈ A\{i} установить p_s0 =  ∞   и считать эти пометки временными. Установить d = i;  B = {i}.  Обновить метки.

Шаг 2. Для всех вершин  s ∈ V(d) вычисляются новые значения p_sj =  p_dj  +  t_ds ,  j = 0, 2, …, |V(s)|-1.  Таким образом, для каждой вершины  будет определено время проезда для всех возможных путей от исходной вершины  i  до вершины  s.

Для j = 0  временные пометки вычисляются, используя выражение p_s0 = min[ p_s0 , ( p_d0  +  t_ds)] и превращаются эти пометки в постоянные.

Шаг 3. Среди всех вершин с временными пометками s∈A\B найти такую вершину k, для которой значение пометки минимально  p_k0 = minp_s.

Шаг 4. Считать пометку p_k0  постоянной и установить d = k.  В множество B добавить вершину k.

Шаг 5. Если d¹j, то перейти к шагу 2.  Если d = j, то p_k0  является  длиной  кратчайшего  пути R_ij из вершины  i в вершину j.

Шаг 6. Если все пометки всех вершин постоянные, т.е.  B = A, то на этом определение времени оптимального пути завершается.

После этого происходит восстановление маршрута проезда.

На втором этапе алгоритма задается допустимое значение отклонения от оптимального значения E. На первом этапе, в отличие от алгоритма Дейкстры,  для каждой вершины в зависимости от мощности множества V(s) вычисляются по формуле (2) и запоминается не одно, а ряд значений пометок. Затем для каждой вершины отбрасываются те значения пометок, для которых выполняется соотношение:  p_sj  > (p_k0+ E),   s ∈  V(d),    j = 0, 2, ..., |V(s)|-1.

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

Схема работы алгоритма для примера. На рис.1 приведена схема работы предложенного алгоритма  для простого примера графа, состоящего из 9 вершин и 20 ребер. Приведенные для всех вершин ряд значений чисел внутри выделенных  прямоугольников представляют собой ряд значений пометок, которые получены на втором этапе алгоритма. На первом месте в этом ряду располагаются пометки, получаемые по алгоритму Дейкстры. Эти пометки выделены жирным шрифтом. Полученный оптимальный маршрут  длиной 7 проходит через  вершины 1 - 7 - 4. Для поиска всех близких к оптимальному маршрутов задано значение E = 27. В конце работы алгоритма получены два близких к оптимальному маршрута  с длинами 16 и 34, проходящие, соответственно, через вершины 1 – 2 – 7 – 4  и  1 – 8 – 5 – 4. 

Программная реализация алгоритма. Алгоритм решения задачи реализован в виде программного комплекса (ПК) на языке JAVA для IBMPC. Программный комплекс предназначен для работы  через систему меню  с  использованием мыши. Меню включает в себя следующие пункты: загрузка файла карты, определение узлов графа на карте, построение ребер графа, удаление узлов, удаление ребер, поиск путей, сохранение  и удаление найденных маршрутов. 

Карта улиц города Москвы загружается из  внешнего файла. Исходные данные генерируются на основе данных программы Mosmap. Затем с помощью указателя мыши на перекрестках улиц назначаются вершины графа. При этом имеется возможность ввода характеристики вершин графа – перекрестков: название и время задержки.  После этого указывается схема соединений вершин графа между собой для  дорожной сети города. Далее клавишами мыши указываются начальная и конечная вершины ребра. С помощью контекстного меню можно задать характеристики дорог – ребер графа: название улицы, длина, средняя скорость движения. ПК дает возможность оперативного изменения  характеристик вершин и ребер графа на карте города, а также показать карту города с требуемой подробностью.

В ПК реализованы три алгоритма: алгоритм Дейкстры, алгоритм нахождения Kкратчайших маршрутов и предлагаемый алгоритм нахождения всех  E близких к оптимальному маршрутов.

В верхней части окна расположено главное меню и кнопка «Режим редактирования». В центре окна находится карта, а справа –  окно с закладками «Результаты» и «Свойства». В расположенном  внизу окна  статус строке  отображается  информация о находящей   рядом с курсором мыши маршруте и времени поиска оптимальных маршрутов.

Главное  меню ПК содержит следующие пункты:

1. Файл – «Загрузить» – открывает диалоговое окно для выбора файла карты.

2. Файл – «Сохранить» – сохраняет текущий граф карты.

3. Вид – «Очистить маршрут» – стирает отображенный на карте маршрут.

4. Вид – «Показывать расстояния» – для каждого участка дороги отображает расстояние или время движения с заданной на этом участке  скоростью.

Выводы

1. Предложена математическая модель задачи выбора оптимального и всех  близких к нему  маршрутов  в виде задачи дискретного программирования и алгоритм ее решения. Определение всех близких к оптимальному маршрутов позволяет при окончательном выборе маршрута учесть дополнительные неформализованные требования.

2. Предложенный алгоритм, являющийся модификацией известного алгоритма Дейкстры, реализован в виде программного комплекса на языке JAVA. Результаты проводимых расчетов представляются в удобном виде на электронной карте города.

3. Проведенные расчеты подтверждают, что алгоритм Дейкстры более эффективен для поиска оптимального пути. Предложенный алгоритм поиска всех  близких к оптимальному маршрутов показывает хорошую производительность для графов дорог  достаточно больших  размеров.

 Литература

1. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 c.

2. Степанов В.П. О математическом моделировании дорожной сети города для выбора маршрута проезда: Тез. док. науч. конф. МГТУ им. Н.Э.Баумана.- М, 2005, c.110-111.

3. Степанов В.П. О математическом моделировании дорожной сети. //  Новые информационные технологии в автоматизированных системах: Материалы тринадцатого научно-практического семинара. – МИЭМ. М., 2010, c. 237 – 243. 

4. Моисеев Н.Н. Численные методы в теории оптимальных систем. – М.: Наука, 1971. – 424 c.