Bryansk, Bryansk, Russian Federation
Bryansk, Bryansk, Russian Federation
We consider the factors influencing the choice and assessment of the quality of the route in the road network. A formula is proposed for assessing the quality of a route in the road network in terms of optimizing the path between two points. The model was tested on 60 created graphs. With their help, the optimal parameters of the user model were selected. Methods for setting the parameters of the considered model are proposed for the developed formula. The resulting model has a moderate complexity in assessing the quality of the route and its software implementation, while simultaneously covering the most important characteristics of the road network and supporting efficient pathfinding on the graphs of the road network. It also provides good customization of the model.
optimal route, roads network graph, mathematical model, model parameters’ setting, optimal path problem
Введение
Современные транспортные дорожные системы достаточно сложны. Большинство современных дорог являются наследием прошлых эпох, когда объемы перевозок были не значительными для повышения пропускной способности строятся новые транспортные пути, но они как правило так же имеют существенные ограничения пропускной способности ввиду существующих архитектурных ограничений. В результате городские транспортные пути представляют собой сложную схему с огромным количеством ограничений в движении, но позволяющих попасть в пункт назначения достаточно большим количеством маршрутов.
В связи с этим задача поиска оптимального пути (маршрута) в дорожной сети находится среди важнейших задач, имеющих непосредственное отношение к системам навигации, а также программным продуктам для поддержки беспилотного управления. В самом просто случае достаточно проложить самый кратчайший путь между заданными пунктами. Однако такой подход имеет ряд недостатков, например, на некотором участке дороги могут проводится ремонтные работы, что сделает прохождение дольше участка планируемого, кроме этого, на некоторых участках могут быть созданы искусственные скоростные ограничения в виде знаков и светофоров [3]. Также кратчайший путь может стать невыгодным, с точки зрения минимального времени, затрачиваемого для попадания в пункт назначения, при заторах, например, на некотором участке дороги скорость движения в разы упадет после аварии. Так, рис. 1 иллюстрирует ситуацию, в которой изначально выгодный кратчайший путь становится невыгодным, если на его участке авария замедляет движение остальных автомобилей.
Рис. 1. Пример неоптимальности кратчайшего пути
Опытным водителям известно, что оптимальный путь и кратчайший – это не всегда одно и тоже. В пример можно привести маршрут с большим количество светофоров. В этом случае лучше поехать по пути, который на 10-20 % длиннее, но преодолеть его быстрее, проведя намного меньше времени перед светофорами. В частности, опытным путем установлено, что если увеличивать среднюю скорость движения (иногда находясь на грани нарушения дозволенных скоростей), то при большом числе светофоров время пути не сокращается, поскольку ожидаемая экономия времени растрачивается на светофорах [4].
Кроме этого, важно учитывать схему работы светофоров – при одном и том же расположении светофоров, и разных режимах синхронизации среднее время прохождения участка часто оказывается различным. Например, может быть сдвиг во времени подачи одноименных сигналов соседних светофоров, а может быть подача одновременных сигналов одинаковой продолжительности на соседних светофорах.
Однако программы не могут «рассуждать» как люди. Необходимы математические модели, позволяющие оценивать качество маршрута в городской дорожной сети, представленной графом, вершины которого – узловые точки (к примеру, перекрестки), а дуги или ребра – участки дорог. При этом важен баланс между сложностью, точностью модели, широтой спектра охватываемых ситуаций и быстродействием алгоритмов ее реализации.
Характеристика современных методов решения
К настоящему моменту исследователями представлены многочисленные варианты оценки качества маршрутов дорожной сети. Однако все они характеризуются различными
недостатками.
Модель, рассматриваемая в [3], основывается на среднем времени проезда по автомагистрали. Каждое ребро в графе дорожной сети представлено параметром скорости, а также параметров класса дороги и знаками ограничения скорости. Однако не учитывается такой фактор, как ширина дорог, хотя научно доказана её значимость. Так, в [2] на основе эмпирических данных показано, что имеется статистически значимая связь между шириной дорог и скоростью движения транспорта, наиболее выраженная, если речь идет об узких участках дорог, чья ширина мала для комфортного интенсивного движения.
В модели, описываемой в [8], множество всех возможных трасс поездки по улицам города представляется в виде ориентированного графа. Вершинам графа соответствуют перекрестки на улицах города. Вершины графа – это места дорожной сети, где есть возможности выбора дальнейшего маршрута движения. Это делает модель ограниченной – например, нужно, некоторым образом, обозначать въезды на крупные склады и иные участки, где нельзя куда-либо свернуть. Для графа задаются матрица расстояний и матрица возможных скоростей движения. Модель также предполагает возможные задержки при прохождении вершин графа ввиду наличия светофоров, но не предусматривает возможности наличия светофоров на дугах или ребрах. Вместо того, чтобы допустить позиции светофоров как свойство дуги или ребра, согласно модели [8] требуется вводить паразитные вершины и связи. Как только требуется установить светофор не в вершине, появится новая вершина, а также новое ребро (рис. 2). При этом появившаяся вершина может быть никак не связана с перекрестком, точкой изменения свойств участка дороги (например, въездом на ремонтируемую часть), тупиком или другим практически важным объектом. Если на прямолинейном участке, на который нельзя въехать или с которого нельзя повернуть, несколько светофоров, структура графа становится намного сложнее, чем могла бы быть, если бы мы допустили светофоры на дугах или ребрах.
Важно отметить, что игнорирование факторов, существенно влияющих на качество маршрута, является не единственной ошибкой при оценке качества маршрутов дорожной сети. Есть ошибки другого рода.
1. Неудачный выбор структуры графа. Как показано в [6], неудачный выбор варианта кодирования дорожной сети графом может увеличить в 1,5-2 раза количество вершин и дуг или ребер в графе.
2. Чрезмерное усложнение модели качества маршрутов дорожной сети. Одной из основ эффективного математического моделирования является достижение баланса между сложностью и точностью. Адекватный выбор математической модели реального объекта является результатом компромисса между количеством и качеством исходной информации об объекте и сложностью модели [7]. Платформа «Яндекс Маршрутизация» [9] использует сложную систему параметров – не только светофоры и знаки ограничения, но и данные о риске заторов и даже габариты транспорта, для которого необходимо проложить маршрут. Учитывается более 50 параметров. К сожалению, такие, образно говоря, чрезмерно развитые, математические модели сложны в программировании и в настройке параметров.
В связи с этим предлагается достаточно простая модель, не значительно уступающая по точности, использующим едва ли не все параметры, которые в принципе можно измерить.
Описание предлагаемой модели
Предлагаемая модель предполагает кодирование дорог с помощью ориентированного графа. Если между двумя узлами двустороннее движение, они соединяются дугами в две стороны, если одностороннее движение – одной дугой. Каждой дуге приписываются ширина дорожного участка, наибольшая возможная скорость, а также ставятся в соответствие светофоры (рис. 3). Предельно допустимая скорость движения определяется или исходя из Правил дорожного движения и знаков ограничения скорости, или исходя из реальных возможностей движения по участку дороги с учетом качества полотна и разных препятствий движению. Вершины могут быть и связанными с реальной сетью дорог (тупики, выезды из домов, места, в которых есть выбор направления движения, и т.д.), и введенными искусственно. На рис. 3 фактически у нас линейный участок дороги, и средние вершины обусловлены лишь отличием части дороги по своим свойствам – например, из-за ремонта полотна поток движется медленно и из двух полос дорога доступна единственная. Такие вершины «искусственные» по своей природе, но это более эффективное кодирование графа дорожной сети, чем предлагаемое в [3] введение дополнительных массивов для каждого ребра либо дуги, чтобы хранить ограничения по скоростям в пределах участка дорожной сети. Говоря иными словами, мы требуем, чтобы каждый участок был однородным по свойствам. Светофоры могут быть и на дугах, и в вершинах. При подсчете количества светофоров на пути в графе мы включаем в учёт все светофоры, которые имеются как в вершинах графа, лежащих на пути, так и на дугах пути.
Рис. 2. Модели, допускающая размещение светофора только в вершинах
Рис. 3. Принцип кодирования участков дорог
На основе данных из работы [5], а также при помощи анализа тестовых графовых систем, дорожной сети Брянской области и города Брянска был предложен и закреплен вид формулы для оценки качества маршрута:
.
Приняты следующие обозначения wi – ширина i-го дорожного участка, включенного в маршрут, vi – максимальная допустимая скорость движения по нему, Li – длина участка, n – количество участков, N – общее число светофоров на пути. Например, на рис. 3 при движении от левого края к правому n = N = 3. Остальные величины в формуле являются параметрами модели.
Компоненты формализуют влияние скорости и ширины на предпочтительность участка дорожной сети. В случае если бы автомобиль мог двигаться по участкам строго со скоростями vi, можно было бы считать . Однако на практике это невозможно. К примеру, вследствие заторов, необходимости избегать потенциально опасных ситуаций при наличии неосторожных водителей на других машинах, а также невозможности по законам физики мгновенно менять скорость на 10-20 км/ч, реальная скорость будет отличаться от потенциальной. Отличие бывает и в верхнюю сторону – например, иногда экипажу скорой помощи или полиции нужно превысить разрешенную скорость.
Вся сумма в представленной формуле качества фактически является метрикой качества пути без учета светофоров, а слева от суммы находится дополнительный множитель, ухудшающий оценку качества пути по мере роста количества светофоров (назовем данный множитель функцией поправки). Величина показывает, во сколько раз мы оцениваем увеличение времени прохождения пути, если на нем много светофоров. Величина p > 0 по факту отвечает за важность минимизации количества светофоров на пути – чем выше значение p, тем быстрее возрастает предложенная функция поправки (рис. 4).
Как отмечалось в [5], форма графика функции поправки зависит от параметра z > 1: чем выше значениеz, тем более медленный рост функции поправки. Применение компонента вместо позволяет обеспечить наличие точки перегиба при N > 0. Перегиб необходим для изменений в поведении функции поправки с ростом N. При маленьких значениях N функция возрастает медленно и практически не «отрывается» от линии y = 1. Это объясняется тем, что при небольшом количестве, равномерно расположенных на достаточно длинном пути, светофоров, влияние на оценку качества пути практически не оказывает. Далее рост, рассматриваемой функции поправки, становится значительным – до тех пор, пока число светофоров не станет достаточно большим, после чего добавление еще одного светофора несущественно скажется на качестве пути.
Рис. 4. Функции поправки для светофоров (p1<p2)
Важными свойствами формулы качества являются:
1. Включает в себя классические метрики качества пути. При получаем сумму длин участков пути. При получаем суммарное время в пути в предположении, что на каждом участке осуществляется движение с максимально допустимой скоростью, таким образом получаем модель, близкую к приведенной в [8].
2. Пусть найден некоторый путь P из точки старта S в точку назначения E, для которого формула качества дала значение F. Пусть также, пытаясь найти другие пути, прошли из S в некоторую точкуD, отличную от E. Тогда, если для пути из S в D значение по формуле качества выше F, нет смысла пытаться продолжить поиск пути в E из D: перед нами заведомо неэффективное частичное решение. За счет такого свойства можно эффективно использовать предложенную формулу качества для различных стратегий поиска оптимального пути, использующих поиск в глубину. Именно на поиск в глубину с эффективными отсечениями заведомо неперспективных частичных решений ориентирована данная модель, хотя ее можно использовать и с другими алгоритмами поиска оптимального пути в графе. Например, предлагаемую формулу можно использовать в рамках стратегии поиска в глубину, рассмотренной в [1]. Идея в том, чтобы перестать расширять частичное решение, как только оно стало заведомо неперспективным. Исходя из свойств формулы, если частичное решение оказалось хуже ранее найденного пути Z из Sв F, при попытке его расширения оценка стоимости не может улучшиться, поэтому решение заведомо хуже Z.
3. В зависимости от значений параметров , рассматриваемая формула может использоваться для различных режимов движения транспорта – например, в одних случаях требуется добраться до цели как можно быстрее, в других – экономить топливо, и т.д. Также параметры будут разниться для случаев обычного транспорта и транспорта с включенным проблесковым маячком: в частности, в последнем случае снижается приоритет светофоров по сравнению с отсутствием маячка.
Кроме этого, в предложенную формулу вводится параметр, не входящий в саму формулу качества, но влияющий на поиск оптимального пути. Если есть пути P и Q между стартовой и конечной точками, причем , то при условии, что у Q меньше дуг, путь Q предпочтителен, хотя он и хуже P согласно формуле качества. Очевидно, что , но этот параметр не должен значительно превышать единицу. При u = 1 имеем строгую оптимизацию с целевой функцией . Необходимость u > 1 в ряде случаев обусловлена тем, что при переходе от одной дуги к другой нередко требуется замедляться, особенно если речь идет о поворотах. Следовательно, лучше избегать путей со значительным количеством дуг, даже ценой умеренного ухудшения в смысле функции φ.
Для получения адекватных результатов требуется, некоторым образом, оценивать параметры , чтобы можно было использовать нашу формулу качества и математическую модель качества в целом. Это возможно сделать путем экспертного опроса. Для этого создаются 50-100 тестовых графов дорожных сетей, на каждом из графов выбираются две точки пути (начало и конец), и для каждой из задач требуется опросить ряд опытных водителей, какой путь из возможных бы они выбрали. Там, где возникли разногласия, есть два варианта действий:
1) отсечь данный граф;
2) считать, что есть несколько правильных путей, и требуется, чтобы по модели был выбран любой из нескольких правильных путей.
Допущение 2-3 правильных путей имеет смысл, если имеется на порядок больше путей в графе между заданными точками.
Осуществляется подбор параметров модели на ЭВМ так, чтобы значения параметров позволили успешно пройти все составленные тесты. Таким образом ставится оптимизационная задача, где процент пройденных тестов – целевая функция, подлежащая максимизации. Тривиальный метод подбора – выбрать интервалы для поиска каждого из параметров и шаг варьирования, и далее проверять каждый параметр с заданным шагом варьирования. Поскольку функция φ достаточно сложная, такой подход следует считать относительно надежным с точки зрения минимизации рисков упустить варианты, дающие 100%-ное прохождение тестов. При высокой производительности ЭВМ и эффективной реализации (распараллеливание по потокам, отказ от проверки наборов параметров, близких к оказавшихся неэффективными, и т.д.) такой метод является оправданным. При этом, если в пространстве остается слишком широкая область решений, при которых проходятся все тесты, ее следует сокращать расширением тестовой выборки графов.
Выводы
С помощью 60 различных графов, каждый из которых охватывал некоторую часть дорог Брянска, при условиях, когда приоритетна минимизация времени в пути, и когда длина пути по важности имеет приблизительно равное значение по сравнению с остальными факторами, взятыми вместе, был получен следующий набор параметров: , давший успешное прохождение всех тестов. При смещении значения любого из полученных параметров на 0,01, процент успешно пройденных тестов падал, причем иногда значительно.
Выполним интерпретацию полученных нами параметров.
1. Адекватность полученных параметров подтверждается тем, что получено , это соотношение формализует высказывание «длина пути по своей важности имеет приблизительно равное значение по сравнению с прочими факторами в совокупности.
2. Низкий приоритет ширины дорог является вполне оправданным. Например, часто удобно объехать дороги, где частые заторы, по небольшим улицам. В [4] обращено внимание, что, как правило, навигационные программы настроены так, что не учитывают это. Предложенная модель позволяет избежать предвзятого мышления, ведущего к неаргументированному предпочтению широких дорог: широкие дороги обычно центральные и ввиду лучшего качества полотна допускают более быстрое движение, однако именно на центральных дорогах чаще заторы.
Если по-другому задать желаемые пути в тестах, то были бы получены другие наборы оптимальных параметров. Например, рекомендуемый набор бы изменился, если бы настраивали модель для транспорта экстренных служб: тогда светофоры имеют не столь большое значение, и желаемые отклики в тестах были бы иными. Заметим, что настройка параметров чрезвычайно схожа с обучением нейросетей, где также требуются пары (входы, желаемые выходы).
Созданная модель оценки качества путей характеризуется такими преимуществами, как умеренная сложность модели и ее программной реализации с одновременным охватом наиболее важных характеристик дорожной сети и поддержкой эффективного (с точки зрения быстродействия) поиска путей на графах дорожной сети. В перспективе предполагается учитывать такие свойства, как распределение светофоров в пределах пути и структурные особенности графа дорожной сети, способные указать на уровень риска заторов. Например, разумно полагать, что есть разница, распределены ли светофоры более-менее равномерно по анализируемому пути или же есть небольшой участок сразу с несколькими светофорами, который трудно проехать без существенных задержек. Пример ситуации, способной указать на высокий риск заторов, - наличие вершины, где число входящих дуг выше числа исходящих при схожей ширине участков дорог и допустимой скорости движения.
1. Azarchenkov,A.A. Graphs processing algorithms application for vehicles movement modeling / A.A. Azarchenkov, N.I. Marchenkov // Science and innovations of 21th century: actual issues, discoveries and achievements. Collection of article of the 10th International scientific-practical conference. – Penza: Science and education, 2018. – pp . 15-19.
2. Gorbachev, P.F. Road’s with influence on speed of car movement in urban roads / P.F. Gorbachev et al // Car vehicles. – 2019. – No. 44. – pp. 50-58.
3. Ignatyuk, V.A. Design of roads network model with parameters based on Dijkstra algorithm for shortest path problem / V.A. Ignatyuk // Bulletin of the Vladivostok State University of Economics and Service. – 2009. – No. 3. – pp. 180-187.
4. How to spend as little time as possible caused by traffic lights. – Access point: https://1gai.ru/baza-znaniy/sovety/513117-kak-tratit-menshe-vremya-na-svetoforah.html.
5. Marchenkov, N.I. Mathematical modeling of quality estimation of urban road network’s routes / Marchenkov N.I., A.A. Azarchenkov // High tech and innovations in science. Collection of the best articles of the International scientific conference. – St. Petersburg: State scientific and research institution «The National Progress», 2020. –pp. 211-217.
6. Marchenkov, N.I. Comparison of methods of road networks encoding based on graphs / N.I. Marchenkov // The Russian science: tendencies and opportunities. – Moscow: The Pen, 2018. – pp. 143-146.
7. Sokolov, A.V. Balance between complexity and accurate measurements / A.V. Sokolov, V.V. Voloshinov // International Journal of Open Information Technologies. – 2018. – No. 9. – pp. 33-41.
8. Stepanov, V.P. Issues of mathematical modeling of road networks / V.P. Stepanov // The modern IT in automated systems. – 2010. – No. 13. – pp. 237-243.
9. Yandeks Marshrutizaciya. – Rezhim dostupa: https://yandex.ru/routing/.
