СПОСОБ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО МАРШРУТА И УСТРОЙСТВО
METHOD OF DETERMINING OPTIMUM ROUTE AND DEVICE

Изобретение относится к области управления движением транспортных средств и, в частности, к выбору маршрута движения с учетом загруженности участков дорог.
Известен способ определения оптимального маршрута движения транспортного средства по дорожной сети населенного пункта, (патент РФ 2153194), который заключается в том, что в память компьютера абонента введена электронная карта дорожной сети населенного пункта, на основании предварительно полученных параметров движения определяют среднестатистические скоростные индексы на каждом участке дорожного движения, от внешнего источника (предпочтительно, центральной станции) получают предпочтительно по каналу связи информацию, которую считают актуальной (далее - актуальную информацию), о скоростях находящихся в движении транспортных средств, после чего производят коррекцию скоростных индексов тех участков дорожной сети, по которым имеется актуальная информация, по каналу связи передают информацию о скорректированных скоростных индексах другим абонентам, по данным о пункте назначения абонента (в память компьютера абонента вводят данные о пункте назначения) определяют предпочтительный маршрут с учетом уточненных скоростных индексов участков дорожной сети населенного пункта, в процессе движения по выбранному маршруту, в случае изменения скоростных индексов участков дорожной сети населенного пункта производят коррекцию оптимальных маршрутов движения до пункта назначения.
Недосток данного метода заключается в низкой вероятности выбора оптимального маршрута в условиях дорожного движения в современном мегаполисе.
Указанный метод способен рассчитать и позволить выбирать маршруты, близкие к оптимальным, в условиях относительно свободного движения с незначительным количеством участков с затруднением движения. В таких условиях вычислительное затруднением движения. В таких условиях вычислительное устройство (компьютер) абонента после получения информации о коррекции скоростных индексов соответствующих участков дорожной сети будет рассчитывать и строить маршрут в обход участков с низкими скоростными индексами. Хотя протяженность маршрута при этом и возрастет, но время в пути уменьшится за счет увеличения скорости движения. Поскольку актуальная информация о скоростях дорожного движения имеется только для части участков, то маршрут в общем случае будет проходить также через участки, по которым нет информации. При этом даже если и нет актуальной информации о скоростях движения на улицах, по которым строится объезд, вероятность встретить там участок с затрудненным движением по сравнению со средним статистическим значением мала, т.к. в целом движение по большинству улиц свободно, т.е. информация, полученная от датчиков на движущихся транспортных средствах, позволяет приблизить маршрут к оптимальному.
Ситуация кардинально меняется в современном мегаполисе, особенно в часы «пик» или при неблагоприятных погодных условиях. В такой обстановке относительное количество участков со свободным движением мало. И вероятность, что на участке с отсутствующей актуальной информацией реальная скорость движения ниже статистической, велика. В этих условиях объезд участка с затрудненным движением по соседним улицам, как в рассмотренном предыдущем примере, с большой долей вероятности может привести не только к удлинению маршрута, но и к увеличению времени нахождения в пути, т.к. на улицах, по которым осуществляется объезд, движение может быть не менее затрудненным, а информация об этом отсутствовать. Т.е. вероятность построения маршрута, близкого к оптимальному, в условиях интенсивного дорожного движения снижается.
Техническим результатом изобретения является уменьшение среднего времени прохождения маршрута в условиях интенсивного движения.
Формируют карту подконтрольной дорожной сети с присвоением вычисленных скоростных индексов участкам дорожного движения.
Периодически (с предварительно назначенной периодичностью) принимают информацию от стационарных и нестационарных датчиков о скоростях движения на части участков дорожной сети (эту информацию считают актуальной и используют как основу для выполнения перерасчета и корректировки скоростных индексов соответствующих участков дорожной сети).
Подконтрольную дорожную сеть разбивают на одну или несколько областей.
a
b
b
a
В пределах каждой области по части или по всем участкам дорожной сети, для которых перед этим проводилась коррекция скоростных индексов на основе актуальной информации, рассчитывают среднюю скорость V без учета проведенной коррекции и среднюю скорость V с учетом проведенной коррекции и вычисляют отношение X=V/V, при этом в случае отсутствия таких участков дорожной сети отношение X устанавливается равным 1.
a(X)
b
a
b(X)
b
a
В пределах каждой области для каждого участка дорожной сети, для которого перед этим не проводилась коррекция скоростного индекса на основе актуальной информации, пересчитывают скоростной индекс путем умножения скоростного индекса этого участка дорожной сети на функцию K от отношения X=V/V, а для каждого участка дорожной сети, для которого проводилась коррекция скоростного индекса на основе актуальной информации, проводят дополнительный пересчет скоростного индекса путем деления скорректированного скоростного индекса этого участка дорожной сети на функцию K от отношения X=V/V.
a(X)
b(X)
b(X)
(X)
a(X)
b(X)
(X)
(X)
(X)
(X)
При этом функции K и K выбирают со следующими свойствами: K>0, K=K∗K представляет собой функцию со следующими свойствами: 0<K<1 при X=0, K неубывающая функция при X>0, K=1 при X=1, K≤X при X>1.
Получают данные о текущем местоположении абонента и конечной точке маршрута и вычисляют рекомендуемый оптимальный маршрут с учетом скорректированных скоростных индексов участков дорожной сети.
b(X)
b(X)
Функция K для большинства случаев может быть выбрана из условия K=1 для любых X.
(X)
(X)
Функция K может быть выбрана из условия K=X при X>1.
(X)
(X)
Функция K может быть выбрана из условия K=1 при X>1.
(X)
(X)
Кроме того, функция K может быть выбрана из условия K=a+(1-а)∗X при 0<X<1, где а выбирают из условия 0<a<1.
b
a
Отношение X=V/V может быть рассчитано только по тем участкам дорожной сети, для которых проводилась коррекция скоростных индексов на основе актуальной информации, которые входят в предварительно назначенный для каждой области перечень участков дорожной сети.
Областью или областями, на которые разбивают подконтрольную дорожную сеть, могут быть населенный пункт, районы населенного пункта, связные участки дорожного движения и т.д.
Среднюю скорость по каждой области можно вычислять различными способами. Наиболее предпочтительным является использование средневзвешенного арифметического или гармонического среднего, где в качестве веса используют длину соответствующего участка. Второй способ эквивалентен обратной величине от средневзвешенного арифметического времени проезда единицы длины каждого участка, где в качестве веса также используют длину участка. Могут быть использованы и более сложные веса. Например, каждому участку дорожного движения можно присвоить ранг по степени влияния или связи дорожной ситуации на нем с общей дорожной ситуацией или ситуацией на прилегающих дорожных участках. Для присвоения ранга можно использовать метод экспертных оценок или статистические данные. В этом случае в качестве веса может быть использовано произведение ранга на длину соответствующего участка.
При большом количестве участков дорожной сети в каждой области вычисление коэффициента X достаточно провести по выборке, включающей только часть участков дорожной сети, для которых проводилась коррекция скоростных индексов на основе актуальной информации. Выборка может быть реализована разными способами: выборка случайным образом, выборка участков дорожной сети с наибольшим рангом, либо выборка только тех участков дорожной сети, которые входят в заранее определенный (назначенный) перечень наиболее репрезентативных для каждой области участков дорожной сети. Указанный перечень может быть составлен, например, методом экспертных оценок или с помощью статистических данных.
Полезный эффект достигают за счет того, что располагая информацией о том, как изменились в среднем значения актуальных (т.е. полученные от внешних источников, преимущественно датчиков) скоростных индексов участков дорожного движения по сравнению co скоростными индексами тех же участков без учета актуальной информации, корректируют в том же направлении и скоростные индексы на тех участках, для которых нет актуальной информации. Вероятность этого предположения быстро растет при увеличении размера последовательности и выборки. Если область будет содержать, например, 1000 улиц, статистические значения скоростей которых известны, и на случайной выборке в 300 улиц зафиксируют двукратное уменьшение средней скорости по актуальным данным, то вероятность предположения, что средняя скорость на остальных 700-х улицах в данный момент тоже меньше, близка к 1. Таким образом, корректируя скоростные индексы участков дорожного движения, для которых нет актуальной информации, на основе данных об изменении средних скоростных индексов участков, для которых есть актуальная информация, статистически увеличивают адекватность скоростных индексов, используемых для прокладки оптимального маршрута.
Поскольку для прокладки оптимального маршрута важны не столько сами по себе абсолютные значения скоростей различных участков дорожного движения, сколько их соотношение, то в более общем случае для достижения положительного эффекта возможно как перерасчитывать (корректировать) скорости участков, для которых нет актуальных данных, в прямой зависимости от коэффициента X, так и актуальные данные скоростей тех участков, для которых есть актуальные данные, в обратной зависимости от коэффициента X.
b(X)
Для простоты сначала рассмотрим случай, когда перерассчитывают только скоростные индексы дорог, для которых нет актуальной информации о скорости движения. Это соответствует случаю выбора функции K=1.
a(X)
Перерасчет осуществляют путем умножения скоростных индексов соответствующих дорожных участков на функцию K, которая зависит от X, то есть от изменения отношения средних скоростей одних и тех же дорожных участков после получения актуальной информации и без ее учета.
a(X)
a(1)
Простейшим и близким к практике можно считать выбор функции K=a+(1-a)∗X. Это означает, что скорости на участках, для которых нет информации, изменяются линейно и в том же направлении, что и отношение средних скоростей X. При X=1, когда средние скорости с актуальной информацией и без нее совпадают, K=1 и коррекция отсутствует.
При малых значениях a скорости участков дорожного движения, для которых нет актуальной информации, уменьшают практически пропорционально X. Это означает, что нужно уменьшить значения скоростей на этих участках примерно во столько же раз, во сколько уменьшилась средняя актуальная скорость для участков, где такие данные имеются.
a(X)
a(X)
При больших значениях a степень коррекции уменьшается. В более общем случае, при X<1, если график функции K выгибается вверх относительно K=X, то это означает запаздывающую степень коррекции, а вниз - опережающую. Опережающая степень коррекции означает, что при прокладке оптимального маршрута предпочтение будет отдаваться маршрутам, где большая часть пути проходит по участкам дорожного движения с известной актуальной скоростью.
a(X)
a(X)
a(X)
a(X)
При X>1, наоборот, если график функций K выгибается вверх относительно K=X, то это означает опережающую степень коррекции, а вниз - запаздывающую. Величина функции K ограничена K≤X, т.к. нет оснований увеличивать вероятность прокладки маршрута по участкам дорожного движения с неизвестной актуальной скоростью в условиях, когда в среднем движение по участкам с известной актуальной скоростью свободно.
a(X)
b(X)
a(X)
(X)
a(X)
b(X)
a(X)
b(X)
b(X)
Все вышесказанное справедливо и для более общего случая, когда коррекцию осуществляют одновременно с использованием функций K и K, с тем лишь отличием, что все ранее сказанное про функцию K теперь относится к функции K=K∗K. Поскольку на функцию K умножают скорости участков, для которых нет актуальной информации, а на функцию K делят актуальные значения скоростей тех участков, для которых эти значения известны, то после проведения перерасчетов соотношение скоростей на всех участках дорожного движения будет таким же, как и в рассмотренном выше частном случае, когда K=1.
a(X)
b(X)
b(X)
Выбор конкретных значений функций K и K зависит от конкретных технических реализаций расчета оптимального маршрута, в которых используется данный метод. Например, если важно (например, для возможности визуального отображения), чтобы скорости участков дорожного движения наиболее адекватно отражали дорожную обстановку, то следует выбирать K=1.
a(X)
b(X)
Если же важно только оптимально рассчитать маршрут на аппаратных средствах мобильного клиента, в локальную карту которого заложены статистические скорости участков дорожного движения и который получает извне (например, по беспроводному каналу связи от центрального сервера) данные об актуальных скоростях участков дорожного движения, то может оказаться целесообразным выбор K=1. Такой выбор позволяет на стороне сервера, который располагает такой же картой, скорректировать только актуальные данные скоростей путем деления на функцию K, которые затем пересылаются мобильному клиенту. Мобильному клиенту при этом вообще не нужно делать каких-либо дополнительных операций при расчете оптимального маршрута.
Заявителем проведен патентно-информационный поиск, в результате которого не выявлены технические решения, содержащие заявляемую совокупность признаков. Следовательно, техническое решение можно считать новым. Из уровня техники неизвестно и неочевидно для специалиста влияние на указанный технический результат коррекции скоростных индексов участков дорожного движения с неизвестными актуальными скоростными индексами по изменениям статистических характеристик участков, для которых такая информация имеется, а также способ, которым такая коррекция осуществляется. Следовательно, заявляемое техническое решение соответствует критерию «изобретательский уровень».
Реализацию способа осуществляют следующим образом.
Формируют карту подконтрольной дорожной сети со скоростными индексами участков дорожного движения.
Принимают информацию от внешних источников (стационарных и нестационарных датчиков) о скоростях движения на части участков дорожной сети и на основе этой актуальной информации корректируют скоростные индексы соответствующих участков дорожной сети.
a
b
b
a
Подконтрольную дорожную сеть разбивают на одну или несколько областей. В пределах каждой области по части или по всем участкам дорожной сети, для которых проводилась коррекция скоростных индексов на основе актуальной информации, рассчитывают среднюю скорость V без учета проведенной коррекции и среднюю скорость V с учетом проведенной коррекции и вычисляют отношение X=V/V. В случае отсутствия таких участков в пределах рассматриваемой области дорожной сети отношение X устанавливают равным 1.
a(X)
b(X)
В пределах каждой области для каждого участка дорожной сети, для которого не проводилась коррекция скоростного индекса на основе актуальной информации, проводят коррекцию скоростного индекса путем умножения скоростного индекса этого участка дорожной сети на функцию K от отношения X, а для каждого участка дорожной сети, для которого проводилась коррекция скоростного индекса на основе актуальной информации, проводят дополнительную коррекцию скоростного индекса путем деления скорректированного скоростного индекса этого участка дорожной сети на функцию K от отношения Х.
a(X)
b(X)
Выбирают функции K и K со следующими свойствами:
(X)
Kb>0,
(X)
a(X)
b(X)
а их произведение K=K∗K представляет собой функцию со следующими свойствами:
(X)
(X)
0<K<1 при X=0, K неубывающая функция при X>0,
(X)
K=1 при X=1,
(X)
K≤X при X>1.
По данным о текущем местоположении абонента и конечной точке маршрута и вычисляют рекомендуемый оптимальный маршрут с учетом скорректированных скоростных индексов участков дорожной сети.
b(X)
b(X)
Функция K может быть выбрана из условия K=1 для любых X.
(X)
Кроме того, функция K может быть выбрана из условия
(X)
K=X при X>1 или
(X)
K=1 при X>1.
(X)
(X)
Кроме того, функция K может быть выбрана из условия K=a+(1-a)∗X при 0<X<1, где a выбирается из условия 0<a<1.
b
a
Отношение X=V/V может быть рассчитано только по тем участкам дорожной сети, для которых проводилась коррекция скоростных индексов на основе актуальной информации, которые входят в предварительно составленный для каждой области перечень участков дорожной сети.
Областью или областями, на которые разбивают подконтрольную дорожную сеть, могут быть населенный пункт в целом, районы населенного пункта, связные участки дорожного движения и т.д.
Среднюю скорость по каждой области можно вычислять различными способами. Полезный эффект все равно будет достигнут. Наиболее предпочтительным является использование средневзвешенного арифметического или гармонического среднего, где в качестве веса используют длину соответствующего участка.
Второй способ эквивалентен обратной величине от средневзвешенного арифметического времени проезда единицы длины каждого участка, где в качестве веса также используется длина участка. Могут быть использованы и более сложные веса. Например, каждому участку дорожного движения можно присвоить ранг по степени влияния или связи дорожной ситуации на нем с общей дорожной ситуацией или ситуацией на прилегающих дорожных участках. Для присвоения ранга можно использовать метод экспертных оценок или статистические данные. В этом случае в качестве веса может быть использовано произведение ранга на длину соответствующего участка.
При большом количестве участков дорожной сети в каждой области вычисление коэффициента X достаточно провести по выборке, включающей только часть участков дорожной сети, для которых проводилась коррекция скоростных индексов на основе актуальной информации. Выборку можно осуществлять разными способами: случайно, использовать участки дорожной сети с наибольшим рангом, либо только те участки дорожной сети, которые входят в заранее определенный (например, методом экспертных оценок или с помощью статистических данных) для каждой области перечень наиболее репрезентативных участков дорожной сети.
Устройство, реализующее заявленный способ, включает центральное вычислительное и координирующее устройства, связанные с координирующим устройством по каналам связи датчики скорости движения транспорта на всех или части участков дорожной сети, связанные с координирующим устройством по каналам связи персональные вычислительные (преимущественно мобильные) устройства (преимущественно на транспортных средствах), участвующие в дорожном движении.
Устройство работает в соответствии с описанным способом.
Устройство и способ промышленно применимы, поскольку используют промышленно выпускаемые компоненты и при взаимодействии реализуют промышленно применимые и апробированные функции.