Экстремальные пути на графах с одновременно меняющимися длительностями прохождения дуг

Полный текст

1. Введение. Широко используемые мобильные приложения, называемые навигаторами, наряду с несомненными достоинствами, обладают рядом существенных недостатков. В частности, маршрут из вершины в вершину, который они находят, строится, фактически, по одному принципу: они прокладывают кратчайший маршрут, привязанный, как правило, к основным магистралям. Это при широком их использовании способствует образованию транспортных пробок. Они также не учитывают, что кратчайший путь может быть далеко не самым быстрым: скорость его прохождения может быть низкой в силу загруженности его потоком транспорта.

Ясно, что длина дуги $—$ постоянная (физическая) величина, а вот время проезда по дуге в разное время суток может быть разным; например, это определяется разной степенью загруженности дуги потоком транспорта (под дугой здесь понимается участок автомобильной дороги) или степенью освещенности дороги в различное время суток.

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

На самом деле и в такой постановке задача остается динамической. Действительно, каков вес дуги если начало движения по ней происходит до часа пик, а завершается, когда чаc пик наступил? Это означает, что часть дуги мы проходим со скоростью, соответствующей движению до часа пик, а оставшуюся часть дуги со скоростью в часы пик. Перейдем к строгой постановке задачи о кратчайшем по времени пути на графе с одновременно меняющимися длительностями прохождения по его дугам.

2. Постановка задачи и алгоритм её решения. Рассмотрен новый класс ориентированных графов с парами весов на дугах ${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}{\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$. Веса дуг положительны и означают время прохождения соответствующей дуги. Задано время $T$; если $t_u+{\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}\le \mathrm{<mi>\; </mi>}T$ ( $t_u$ $—$ время начала прохождения по дуге $u$ ), то «действует» вес ${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, если $t_u\ge T$, то «действует» вес ${\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$; в иных случаях действует «переходной вес дуги», который строится естественным образом по весам ${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, ${\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$. Такие графы можно считать частным случаем динамических графов (см. [1, 3$–$5]).

Рассмотрена задача нахождения кратчайшего по времени пути на таком графе из заданной вершины при указанном времени старта в произвольную вершину графа. Ясно, что задача имеет четкое практическое истолкование, а именно, $T$ $—$ время начала «часа пик», а пары весов дуг $—$ времена прохождения по дуге ( ${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ до «часа пик», ${\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ во время «часа пик»). «Пиковость» означает, что для для весовых функций дуг ${\rho }_1$ и ${\rho }_2$ выполнено условие

${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}\le {\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}\forall u\in U\mathrm{.}$ (1)

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

Ещё одной особенностью, отличающей предложенный алгоритм от алгоритма Э. Дейкстры, является изменение «смысла» используемых в нём меток вершин. В классическом алгоритме Э. Дейкстры метка вершины в случае нахождения кратчайшего по времени прохождения пути имеет следующий времени прохождения из начальной вершины в текущую; в нашем случае, когда мы ищем кратчайший по времени прохождения путь, при указанном времени начала движения (времени старта) метка вершины $—$ это время прибытия в неё при указанном времени старта. Таким образом, исходная метка стартовой вершины полагается равной времени старта и не меняется в процессе применения алгоритма, а исходные метки остальных верщин полагаются равными $+\infty$ (в классическом алгоритме начальная метка стартовой вершины равна $0$ ).

Как известно, алгоритм Э. Дейкстры $—$ один из первых динамических алгоритмов, основанный на выполнении шагов пересчета меток вершин до тех пор, пока изменяется метка хотя бы одной из вершин графа. Пересчет метки вершины y осуществляется по дугам, которые заканчиваются в вершине $y$, по следующему правилу: сравниваются между собой $M_y$ и величина $M_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, определенная равенством

$M_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{M}_x+\rho \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}f\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}x\mathrm{<mo>;</mo>}y\mathrm{<mo\; stretchy="false">)</mo>,}$ (2)

причем

$\text{если }{M}_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo><</mo>}{M}_y\mathrm{,}\text{то }{M}_y\mathrm{<mo>:</mo><mo>=</mo>}{M}_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>.}$ (3)

В этом случае говорят, что метка вершины $y$ была пересчитана через метку вершины $x$ по дуге, приходящей из вершины $x$ в вершину $y$. Установившиеся метки вершин имеют известный смысл $—$ наименьшее возможное время прибытия из начальной вершины в данную вершину. Массив меток позволяет восстановить сам экстремальный путь из начальной вершины в заданную вершину. В нашем случае правило (3) пересчета меток остается прежним, а формула (2) для $M_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, заменяется на следующую:

$M_y\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\left\{\begin{array}{cc}{M}_x+{\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}& \text{если }{M}_x+{\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}\le T\mathrm{<mo>;</mo>}\\ M_x+{\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}& \text{если }{M}_x\ge T\mathrm{<mo>;</mo>}\\ T+\frac{\mathrm{<mo\; stretchy="false">(</mo>}{\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}T-M_x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}{\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}}\cdot {\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}& \text{в иных случаях}\text{.}\end{array}\right.$ (4)

Что означают выражения, содержащиеся в правой части за фигурной скобкой в (4)? Первая строка $—$ пересчет метки вершины, когда это происходит до достижения времени $T$. Вторая строка $—$ пересчет метки, когда это происходит после достижения времени $T$, а нижняя строка означает, что пересчет метки происходит в переходной момент $—$ часть дуги $u$ мы проходим, используя её вес ${\rho }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, а её оставшуюся часть, используя её вес ${\rho }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$.

Фактически это означает, что мы имеем дело как бы с тремя графами. На первом из них дуги имеют весовую функцию ${\rho }_1$, на втором $—$ дуги имеют весовую функцию ${\rho }_2$, на третьем графе веса дуг определены третьей строкой формулы (3), т.е. динамически.

Восстановление экстремального пути непосредственно по массиву меток из-за формулы (3), которая применяется при пересчете меток, можно осуществить, но это, в отличие от классического случая, представляется делом достаточно трудоемким. Вместо этого вместе с динамическим массивом меток вершин создается ещё один динамический массив вершин, через которые осуществлен персчет метки. Это позволяет легко восстанавливать найденный экстремальный путь.

3. Примеры, иллюстрирующие алгоритм. Продемонстрируем работу алгоритма на нескольких примерах.

Пример 1 Рассмотрим следующий граф:

 

 

«Дробью» над дугой указаны веса дуги до часа пик и во время часа пик в минутах; Т=8:00. Ясно, что при времени старта t ≤ 7:40 из вершины 1 время нахождения в пути в вершину 5 равно 20 минутам, при старте в 7:44 время прохождения пути равно 23 минутам, при старте в 7:45 время прохождения пути равно 25 минутам, а при старте в 8:00 в пути составит 40 минут.

Пример 2 Рассмотрим теперь следующий граф:

 

 

Применение описанного выше алгоритма для нахождения кратчайшего по времени пути из вершины 1 в вершину 5 при времени старта $t\le 7:40$ время прохождения кратчайшего пути равно 20 минутам; этот путь проходит через вершины 2, 3, 4.

При времени старта 7:44 кратчайший по времени путь из вершины 1 в вершину 5 проходит через вершины 2, 3, 4, 9, 10, а время в пути составляет 23 минуты. При старте в 7:50 кратчайший по времени путь из вершины 1 в вершину 5 проходит через вершины 2, 3, 8, 9, 10 и время в пути составляет 24 минуты. При старте в 7:56 кратчайший по времени путь из вершины 1 в вершину 5 проходит через вершины 2, 3, 8, 9, 10, и время в пути составляет 28 минут.

Обращаем внимание читателей на значительное расхождение во времени прохождения кратчайшего пути при старте в 7:44 (23 минуты) и при старте в 7:56 (28 минут) и на то, что изменился сам кратчайший по времени путь.

Замечания.

1. Предложенный в работе алгоритм в отличие от классического алгоритма Э. Дейкстры уже не является чисто дискретным, поскольку у дуг графа при переходе от времени меньшего Т ко времени большего чем Т возникают динамические веса (вторая строка в правой части формулы (4)).
2. Ясно, что кратчайшее время, найденное по алгоритму, нужно считать в приложениях приближенным, поскольку исходные веса можно считать средним временем прохождения дуги графа до наступления часа пик и во время часа пик.
3. Если перестроить все навигаторы на использование предложенного нами алгоритма, то это приведет к изменению структуры существующих транспортных потоков, т.е. к изменению весов дуг (см. замечание 2). Поэтому предлагаемый в работе алгоритм целесообразно использовать в навигаторах специального применения на транспортных средства специально назначения (медицинская помощь, пожарные автомобили и т. п.).
4. Ясно как модернизировать описанный алгоритм на случай, когда задано не только Т $—$ время начала часа пик, но и задано время окончания часа пик, и веса дуг после окончания часов пик равны ${\rho }_1\left(u\right)$ или равны ${\rho }_3\left(u\right)$.
5. Допущение (1) может быть опущено, мы им нигде и не пользовались. Оно было выписано лишь для «оправдания термина «часы пик».

Об авторах

Яков Михайлович Ерусалимский

Южный федеральный университет

Автор, ответственный за переписку.
Email: ymerusalimskiy@sfedu.ru
Россия, Ростов-на-Дону

Максим Игоревич Осипов

Южный федеральный университет

Email: makosipov@sfedu.ru
Россия, Ростов-на-Дону

Владимир Александрович Скороходов

Южный федеральный университет

Email: vaskorohodov@sfedu.ru
Россия, Ростов-на-Дону

Список литературы

Дополнительные файлы