Навигационное устройство для планирования зависящего от времени маршрута

Навигационное устройство для планирования зависящего от времени маршрута

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Настоящее изобретение относится к способу планирования маршрута до пункта назначения; он находит прикладную программу в компьютерно-выполняемых системах, которые позволяют планировать оптимальный маршрут езды.

УРОВЕНЬ ТЕХНИКИ

Автомобильная поездка является большей частью повседневной жизни для коммерческих и других организаций, а также для частных лиц. Издержки задержек движения транспорта очень велики. Только чисто финансовая стоимость была оценена в миллиардах английских фунтов стерлингов [CFIT]. При наличии указанных издержек очень важны системы, которые могут помогать водителям оптимизировать их поездку, например, путем выбора наилучшего маршрута и избегания задержек в дорожных пробках. Фактически выросло разнообразное множество информационных водительских систем.

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

- На веб-сайтах обеспечиваются системы планирования статического маршрута посредством головных организаций дорожного движения (AA - Автомобильная ассоциация, RAC - Королевский автомобильный клуб). Они позволяют водителям приезжать в промежуточные пункты поездки и получать инструкции маршрута и вождения для данного маршрута.

• Были внедрены внутритранспортные персональные навигационные системы (PNS), основанные на GPS (глобальной системе позиционирования). Они используют положение транспортного средства и маршрут, вычисленный с использованием традиционной функции статической стоимости, для представления водителю инструкций для следования к его пункту назначения. Такие системы начали внедрять информацию движения транспорта в свои службы, но они не встроены в выбор маршрута; пользователь может наблюдать задержки, где они сильно влияют на выбранный маршрут, и вручную направлять систему перепланировать маршрут, избегая участков дороги с задержкой, если он считает это необходимым.

• Для идентификации задержек дорожного движения и для подачи информации в системы оповещения используются системы отслеживания движения транспорта в реальном масштабе времени, основанные на различных технологиях (например, мобильные телефоны, фиксированные камеры, GPS слежение за автопарком).

По мере того как увеличиваются дорожные пробки, системы, обеспечивающие планирование маршрута, становятся более восприимчивыми к ошибкам. Водитель будет не доволен, если, запросив быстрейший маршрут из А в B, затем окажется в дорожной пробке на 50 мин. Аналогично водители не будут доверять системе, которая направляет их по оживленной дороге A, где они едут в колонне позади HGV со скоростью 50 миль в час, тогда как они могли бы проехать намного быстрее по маршруту несколько более длинной автострады.

Известные методы улучшенного планирования маршрута требуют присвоения индивидуальных технических скоростей дорогам или отрезкам дорог, которые более правильно отражают ожидаемую скорость, с которой транспортные средства могут по ним ездить. Упомянутое присвоение в основном бывает статическим, то есть отрезку дороги присваивается фиксированная стоимость после исследования и анализа, и указанная стоимость впоследствии постоянно используется как стоимость отрезка дороги в алгоритме выбора маршрутной схемы. Стоимость может быть пересмотрена, но пересмотр настолько же дорог, насколько первоначальное присвоение стоимости. Следовательно, алгоритмы планирования маршрута в навигационных устройствах вычисляют время прохождения участка маршрута с использованием типов дорог, заданных в базе данных карт, хранимых в устройстве; можно предположить, что транспортные средства в среднем едут с установленными пределами скорости для данного типа дороги или с некоторой скоростью, согласующейся с классом дороги. Упомянутые базы данных карт от компаний, подобных TeleAtlas и NavTech, являются результатом дорогостоящего и тщательного исследования дорог, обычно по всей стране. Таким образом, сильная сторона этого подхода состоит в том, что время прохождения может оцениваться для каждой дороги в базе данных карт. Но его слабая сторона состоит в том, что предположение езды с установленным пределом скорости безусловно терпит неудачу для областей с дорожными пробками, так как устройства не имеют надежной информации движения транспорта. Общий подход для вычисления маршрута самой низкой стоимости (например, быстрейший) можно считать всеобъемлющим, но неточным в случае возникновения дорожной пробки.

В последние годы стали широко распространенными GPS переносные спутниковые навигационные устройства с усовершенствованными алгоритмами планирования маршрута, такими как GO™ от компании TomTom International BV, и многие обычные водители используют их; выгода от внедрения в такие системы эффективных данных движения транспорта является значительной.

Системы отслеживания движения транспорта уровня техники были сосредоточены на обеспечении данных потока движения транспорта так, чтобы избегать пробок. Но упомянутые системы были в основном ограничены главными дорогами, вследствие инфраструктурных издержек развития отслеживающего оборудования (например, контурные датчики, зарытые в дорогах; системы на основе камер, такие как системы распознавания номерных знаков) или из-за того, что они полагались на системы подвижных транспортных средств, в которых отслеживается относительно небольшая пропорция всех транспортных средств (оборудованных аппаратными средствами специального назначения), обычно двигающихся по главным дорогам и не в городской зоне. Для коммерческих компаний по перевозкам такие ограничения могут быть приемлемыми потому, что их грузовики в основном используют главные дороги.

В целом, службы отслеживания движения транспорта не являются всеобъемлющими, но полезны, когда дорожная пробка возникает на дороге, которая отслеживается. Однако их пригодность ограничивается по двум причинам. Во-первых, потому что пользователя просто информируют о дорожной пробке; это обычно бывает бесполезно для пользователя, когда он запрашивает соответствующего действия, такого как план нового маршрута, учитывающего дорожную пробку. Во-вторых, дорожная пробка может расчиститься к тому времени, когда транспортное средство достигнет места, которое в данный момент указано как забитое дорожной пробкой. Там, где дорожная пробка прогнозируется (то есть когда она следует какой-то регулярности или прогнозируемости во времени, например, утренние часы пик или дорожная пробка вокруг стадиона, когда играют главный матч, или авария, которая перекрывает одну полосу движения главной дороги), можно оценивать, в какую возможную дорожную пробку попадет транспортное средство, как только оно достигнет дороги, которая в данный момент забита дорожной пробкой. Зависящий от времени поток движения транспорта или данные времени прохождения (например, в 8 часов утра, каждый понедельник, время прохождения для конкретного участка маршрута составляет 20 мин; оно составляет 15 мин в 13 часов дня и 5 мин в 11 часов вечера и т.д.) можно каким-то образом решить. Можно сделать ссылку на патент США 6356836 и более поздний WO 2004/021306. Но до настоящего времени, как было отмечено выше, подобный тип данных обычно применяется только к системам отслеживания движения транспорта, которые обеспечивают данные для относительно маленькой пропорции дорог в стране.

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Изобретение включает в себя способ планирования маршрута до пункта назначения. Он содержит следующие этапы:

(a) использование базы данных карт, которая определяет дороги в терминах участков маршрута и включает в себя фиксированную, заданную, не зависящую от времени стоимость, ассоциированную с каждым отличным участком маршрута в базе данных карт;

(b) использование программного обеспечения, которое позволяет планировать маршрут до пункта назначения и которое вычисляет оценочную стоимость достижения пункта назначения с использованием одного или нескольких участков маршрута;

при этом использование программного обеспечения включает в себя планирование маршрута посредством автоматического использования комбинации (i) зависящих от времени издержек для одного или нескольких участков маршрута в данном маршруте, так что некоторая стоимость применяется к прохождению конкретного участка маршрута, которая подходит для специфического времени, когда планируется пересекать, и (ii) фиксированных, заданных, не зависящих от времени издержек для тех участков маршрута, для которых зависящие от времени издержки не определены.

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

Дополнительные детали осуществления включают в себя следующее:

Зависящая от времени стоимость, ассоциированная с конкретным участком маршрута, относится к скорости автомобиля или временам прохождения участка маршрута, которые измеряются или выводятся и не являются фиксированными и заданными. Измерение может принимать разнообразное множество форм и будет описано позже. С другой стороны, фиксированная, заданная, не зависящая от времени стоимость, ассоциированная с конкретным участком маршрута, не измеряется или не выводится из действительного потока движения транспорта, но вместо этого является функцией (i) типа дороги, ассоциированного с этим участком маршрута, или (ii) предела скорости, применимого к этому участку маршрута. Не зависящие от времени издержки используются в комбинации с зависящими от времени издержками для тех участков маршрута, которые задаются как не зависящими от времени издержками, так и зависящими от времени издержками. Комбинация может принимать много различных форм, однако суть состоит в том, что есть некоторое значение в не зависящих от времени данных в установлении наиболее точной стоимости для участка маршрута, даже несмотря на то, что могут быть доступны некоторые зависящие от времени данные. Например, качество зависящих от времени данных может быть слишком низким, чтобы быть вполне надежными; объединение указанных данных с фиксированными, не зависящими от времени данными с подходящим относительным взвешиванием может дать наиболее приемлемую оценку. Подобным образом, зависящие от времени данные могут быть недоступны для специфического участка маршрута, но могут быть известны для подобных или близлежащих участков маршрута, и, следовательно, может оказаться возможным выведение некоторой временной зависимости, но, как прежде, может быть желательным некоторое взвешивание с фиксированными, не зависящими от времени данными.

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

Одна особенность состоит в том, что оценочная стоимость достижения пункта назначения для конкретного водителя транспортного средства представляет собой функцию режима езды, ассоциированного с данным водителем. Следовательно, манера вождения (например, быстрая/агрессивная/спортивная/нормальная/медленная/осторожная) может иметь значительное влияние на издержки (особенно времена прохождения и потребление топлива). Способ позволяет выбирать различные режимы (например, самим водителем, вручную со списка меню, отображаемого на навигационном устройстве; или автоматически этим устройством путем отслеживания действительной езды); затем они используются для выбора подходящего набора издержек или весового коэффициента, применяемого к издержкам. Например, водитель, едущий в спортивном режиме, может иметь времена прохождения, сниженные на 5%, по-другому, чем в областях с очень большими дорожными пробками.

Как отмечалось выше, существует много способов измерения действительных потоков движения транспортных средств или данных движения. Например, это можно сделать с использованием GPS трассировок (обычно, запись данных GPS положения в регулярные моменты времен или на интервалах расстояний). Трассировки GPS могут сохраняться навигационным устройством, основанным на GPS системе, в передвижении вдоль участков маршрута. Трассировки GPS могут посылаться по сотовой беспроводной сети непосредственно устройством в систему отслеживания движения транспорта или посылаться непосредственно устройством в систему отслеживания движения транспорта. Трассировки GPS могут посылаться по мобильному телефону, соединенному с устройством по пикосети или другой форме соединения, или посылаться устройством, когда оно состыковано с ПК, к системе отслеживания движения транспорта.

Измерение реальных потоков или движения транспортных средств также может быть достигнуто посредством измерения местоположения мобильных телефонов; последнее можно выполнить посредством пассивного отслеживания сигнализации движения транспорта с мобильных телефонов на базовые станции. Измерение реальных потоков или движения транспортных средств также может быть достигнуто с использованием контурных датчиков в дорогах, или с использованием систем на основе камер (например, таких как системы распознавания номерных знаков), или с использованием транспортных средств, оборудованных радиомаяками.

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

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

• времени дня или ночи,

• дней недели,

• официальных выходных,

• школьных каникул,

• в общем случае, любого события, которое вероятно может влиять на издержки участка маршрута; или любой будущей ситуации, для которой можно вывести ее вероятное влияние на стоимость участка маршрута.

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

Другой аспект настоящего изобретения включает в себя навигационное устройство, запрограммированное с:

(a) базой данных карт, которая определяет дороги в терминах участков маршрута и включает в себя фиксированную, заданную, не зависящую от времени стоимость, ассоциированную с каждым отличным участком маршрута в базе данных карт; и

(b) программным обеспечением, которое позволяет планировать маршрут до пункта назначения и которое вычисляет оценочную стоимость достижения пункта назначения с использованием одного или нескольких участков маршрута;

в котором устройство может планировать маршрут посредством автоматического использования комбинации (i) зависящих от времени издержек для одного или нескольких участков маршрута в упомянутом маршруте, так что некоторая стоимость применяется к прохождению конкретного участка маршрута, которая подходит для специфического времени, когда планируется пересекать, и (ii) фиксированных, заданных, не зависящих от времени издержек для тех участков маршрута, которые не определены зависящими от времени издержками.

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

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

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

Также возможно:

(a) для обоих устройств - и устройства, и сервера, чтобы каждый отдельно использовал зависящие от времени издержки;

(b) для устройства, чтобы оно информировало сервер о маршруте с самыми низкими издержками, которые оно вычислило; и

(c) для сервера, чтобы он посылал уведомление в устройство, если маршрут с самой низкой стоимостью, который он вычислил, отличается от маршрута, который вычислило устройство.

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

Другой подход состоит в следующем:

(a) оба устройства - и устройство, и сервер, каждый отдельно использует зависящие от времени издержки;

(b) устройство идентифицирует участки дороги, для которых полезны последние данные, и запрашивает указанные последние данные из сервера.

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

Само устройство может представлять собой навигационное устройство, работающее с сигналами GPS. Это может быть мобильный телефон с системой пеленгации, такой как GPS. Это может быть переносное навигационное устройство, такое как GO от компании TomTom, или это может быть устройство, на постоянное время встраиваемое в двигатель транспортного средства.

Другие аспекты следующие:

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

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

Автомобили, включающие встроенную навигационную систему, работающую, чтобы планировать маршрут с использованием заданного выше способа.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

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

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

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

Для водителя, который желает совершить специфический проезд, существуют различные технические средства для предложения маршрута в дорожной сети. Проезд может быть задан между двумя пунктами, или может быть более сложным проездом, включающим в себя многочисленные местоположения, которые нужно посетить, необязательно в конкретном порядке. Такой вид проезда обычно предпринимает водитель по доставке. Какой бы ни была форма проезда, цель состоит в том, чтобы минимизировать стоимость, ассоциированную с проездом. Наиболее очевидная стоимость - это длительность времени, но может быть существенной любая другая стоимость, например, топливо, используемое при совершении поездки. Пользователи могут ограничивать возможность выбора используемых дорог, например, для некоторых классов коммерческих транспортных средств запрещено использовать все маршруты, за исключением магистральных маршрутов, которые находятся вне больших городов с пригородами. Указанные технические средства обычно реализуются в виде алгоритмов, заключенных в компьютерные системы, которые присваивают некоторую стоимость отрезку маршрута и которые применяют алгоритмы минимизации стоимости [Dijkstra] к графику перекрестков и маршрутов. В простом случае, стоимость является фиксированной для каждого маршрута, и имеется время проезда по маршруту при передвижении с нормальной скоростью маршрута (обычно упомянутая цифра составляет предел скорости для сомнительной дороги, или значение, просто выведенное из предела скорости). Такая величина может быть названа статической функцией стоимости.

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

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

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

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

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

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

Система, показанная на фиг.1, содержит:

• Систему 1 отслеживания движения транспорта,

• систему 2 маршрутизации.

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

1. Система отслеживания движения транспорта (TMS)

Система 1 отслеживания движения транспорта, например от фирмы Applied Generics′ RoDIN24 [RoDIN24], содержит некую операционную систему сбора данных, и которая наблюдает через некоторый механизм за движением транспорта в намеченной географической области.

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

• Накопленная за прошлый период информация времени прохождения для участков дороги, сохраненная в базе данных 5. На заданной частоте оценка системы для текущего времени, необходимого для пересечения участка дороги, записывается в базе данных наряду с любыми другими параметрами, которые генерирует система, относящимися к дорожному движению на участке маршрута. Способ для вычисления оценки времени прохождения зависит от системы отслеживания движения транспорта; в модели RoDIN24 она выводится из движения мобильных телефонов, которые, как с большой степенью вероятности предполагает система, пересекают сомнительный участок. Может быть сделана ссылка на патент WO 0245046, содержание которого включено здесь ссылкой.

• Информация и уведомление о дорожной пробке 6. Система 6 идентифицирует, какие участки дороги значительно забиты дорожными пробками (передвижение с технической скоростью, намного меньше ожидаемой), и выдает уведомления заинтересованным клиентам, использующим согласованный протокол.

1.1 Прогнозирование времени прохождения

Система 1 отслеживания движения транспорта пополняется модулем 3 прогнозирования времени прохождения. Он предназначается для того, чтобы обеспечивать оценку ожидаемого времени прохождения по любому участку дороги в пределах TMS системы 1 в любое требуемое будущее время. Следует обратить внимание на то, что модуль 3 прогнозирования времени прохождения, который всегда обеспечивает время прохождения на пределе скорости дороги, является необязательным примером этой системы и, когда он объединен с системой маршрутизации, служит для выполнения прогнозирования маршрута традиционным статическим способом. Следовательно, накопленная за прошлый период база данных 5 или системы информации/уведомления о дорожной пробке могут обеспечить незначащие данные, тогда позиция по умолчанию такова, что время прохождения является просто функцией предела скорости, то есть известные, фиксированные, независящие от времени данные.

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

Обычным для исследований транспорта является разделение на категории по типу дня, а в пределах дня конкретного типа - разделение на категории: время на часы пик, часы минимальной нагрузки, дневное время, вечернее время и т.д.

Типы дня могут быть следующие:

• Будни;

• Пятницы, которые имеют картину, отличную от других будних дней;

• Субботы;

• Воскресные дни;

• Официальные нерабочие дни.

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

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

• В будний день, школьная сессия, 08:00-08:15, среднее оценочное время прохождения составляет 43 мины.

• В пятницу, школьные каникулы, 08:30-08:45, среднее оценочное время прохождения составляет 27 мин.

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

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

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

2. Пеленгатор маршрута

Пеленгация маршрута может осуществляться в системе 2 с использованием любого алгоритма поиска маршрута, который присваивает издержки линиям связи в сети. Функция динамической стоимости просто интегрируется в алгоритм маршрутизации.

2.1 Функция динамической стоимости

Функция динамической стоимости представляет собой функцию участка дороги и исследуемого времени (предположительно будущего). Она отличается от функции статической стоимости, которая является функцией только участка дороги. Наиболее общая функция статической стоимости представляет собой время прохождения на пределе 7 скорости, но вместо нее можно выбрать другие функции стоимости 8. Хорошая функция динамической стоимости может быть реализована путем использования механизма прогнозирования времени прохождения из TMS системы 1. Когда для конкретного времени прохож