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

Формула изобретения

1. Навигационное устройство, запрограммированное с:

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

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

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

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

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

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

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

5. Устройство по п.1, в котором стоимость, ассоциированная с конкретным маршрутом, является оценочным временем, затраченным для достижения пункта назначения.

6. Устройство по п.1, в котором стоимость, ассоциированная с конкретным маршрутом, представляет собой потребление топлива, ассоциированное с упомянутым маршрутом.

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

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

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

10. Устройство по п.1, в котором программное обеспечение вычисляет стоимость маршрута как часть алгоритма минимизации стоимости.

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

12. Устройство по п.11, в котором измерение действительных потоков движения транспортных средств или данных движения выводится из GPS трассировок, сохраняемых навигационным устройством, основанным на GPS системе, в передвижении вдоль участков маршрута.

13. Устройство по п.12, в котором трассировки GPS посылаются по сотовой беспроводной сети непосредственно устройством в систему отслеживания движения транспорта.

14. Устройство по п.12, в котором трассировки GPS посылаются непосредственно устройством в систему отслеживания движения транспорта.

15. Устройство по п.12, в котором трассировки GPS посылаются по мобильному телефону, соединенному с устройством по пикосети или другой форме соединения.

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

17. Устройство по п.11, в котором измерение реальных потоков или движения транспортных средств достигается посредством измерения местоположения мобильных телефонов.

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

19. Устройство по п.11, в котором измерение реальных потоков или движения транспортных средств достигается с использованием контурных датчиков в дорогах.

20. Устройство по п.11, в котором измерение реальных потоков или движения транспортных средств достигается с использованием систем на основе камер.

21. Устройство по п.11, в котором измерение реальных потоков или движения транспортных средств достигается с использованием транспортных средств, оборудованных радиомаяками.

22. Устройство по п.1, в котором зависящие от времени издержки способны динамически обновляться.

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

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

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

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

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

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

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

30. Устройство по п.1, в котором пункт назначения включает в себя два или несколько пунктов назначения.

31. Устройство по п.1, которое вычисляет маршрут до пункта назначения с самой низкой стоимостью.

32. Устройство по п.1, которое планирует самый быстрый маршрут.

33. Устройство по п.1, которое планирует маршрут с самым низким потреблением топлива.

34. Устройство по п.1, которое планирует маршрут с самыми низкими финансовыми расходами.

35. Устройство по п.1, в котором зависящие от времени издержки помещаются в устройство.

36. Устройство по п.1, в котором зависящие от времени издержки посылаются в устройство по запросу устройства.

37. Устройство по п.35 или 36, в котором зависящие от времени издержки, принимаемые устройством, ограничиваются классом типов дорог.

38. Устройство по п.1, которое включает в себя зависящие от времени издержки на том же запоминающем устройстве, которое включает в себя базу данных карт.

39. Устройство по п.1, которое получает доступ к зависящим от времени издержкам, которые хранятся в удаленном сервере.

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

41. Устройство по п.39, в котором удаленный сервер посылает в устройство стоимость, ассоциированную с движением от старта до пункта назначения.

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

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

44. Устройство по п.39, в котором:

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

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

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

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

46. Устройство по п.39, в котором:

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

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

47. Устройство по п.1, которое предлагает оптимальное начальное время для проезда.

48. Устройство по п.1, которое представляет собой навигационное устройство, основанное на GPS системе.

49. Устройство по п.1, которое представляет собой мобильный телефон с системой пеленгации.

50. Устройство по п.1, в котором система пеленгации представляет собой GPS систему.

51. Устройство по п.1, которое на постоянное время встраивается в двигатель транспортного средства.

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

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

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

Описание изобретения к патенту

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

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

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

Автомобильная поездка является большей частью повседневной жизни для коммерческих и других организаций, а также для частных лиц. Издержки задержек движения транспорта очень велики. Только чисто финансовая стоимость была оценена в миллиардах английских фунтов стерлингов [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. Когда для конкретного времени прохождения применяется алгоритм 9 минимизации стоимости, эта функция динамической стоимости приводит к более точному прогнозируемому времени проезда и к некоторому выбору маршрута, который ближе к оптимальному.

2.2 Маршрутизация с алгоритмом Dijkstra

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

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

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

2.3 Фиг.2. Пример

Демонстрируется, каким образом система динамической маршрутизации приводит к большой конкретной экономии времени для иллюстративного пробега. Рассмотрим следующую схематическую автодорожную карту. Водитель желает совершить поездку из Лилипутии в Бробдингнэг. Какой маршрут следует выбрать и сколько он займет времени? Карта помечена расстояниями вдоль дорог и скоростью следования, соответственно, в обеденный перерыв и в часы пик. Например, надпись 30 км (60 км/ч / 30 км/ч) указывает, что участок дороги имеет длину 30 км, и согласно лучшей информации, доступной для устройства прогнозирования времени прохождения, в обеденный перерыв (12:00) передвижение будет происходить со скоростью 60 км/ч, тогда как в час пик (16:00) передвижение будет происходить со скоростью 30 км/ч.

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

Обеденный перерыв

1. В 12:00 проезд из Лилипутии в Блефуску займет 30 мин при скорости 60 км/ч. В 12:30 (когда водитель прибыл в Блефуску) пробег в Бробдингнэг займет 20 мин при скорости 60 км/ч в течение следующих 20 мин. Суммарная длительность пробега составляет 50 мин.

2. В 12:00 проезд из Лилипутии в Лапуту займет 20 мин при скорости 60 км/ч. В 12:30 (прибытие в Лапуту) пробег в Бробдингнэг займет 40 мин при скорости 60 км/ч в течение следующих 20 мин, суммарная длительность составляет 60 мин. Таким образом, в обеденный перерыв безусловно лучше ехать через Блефуску.

Час пик

1. В 16:00 проезд из Лилипутии в Блефуску займет 60 мин при скорости 30 км/ч. Водитель прибывает в Блефуску в 17:00 и потратит следующие 20 мин в Бробдингнэг при скорости 20 км/ч. Суммарная длительность пробега составляет 120 мин.

2. В 16:00 проезд из Лилипутии в Лапуту займет 40 мин при скорости 30 км/ч. Водитель прибывает в Лапуту в 16:30, и в это время он потратит следующие 60 мин при скорости 40 км/ч для поездки в Бробдингнэг. Всего пробег займет 100 мин.

Таким образом, в час пик указанный выбор маршрута по Лапуту сэкономил водителю 20 мин.

3. Обновление/отслеживание выбранных маршрутов

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

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

Система маршрутизации периодически пересчитывает маршрут водителя от его текущего местоположения до пункта назначения;

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

3.1 Эффективная система распределенной динамической маршрутизации

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

Уровень техники в системах связи между PNS и CNS системами (например, пакетная радиосвязь общего назначения, GPRS) в основном не обеспечивает высокой полосы пропускания, низкого времени ожидания или непрерывной связи, так что проблемы связи должны решаться в пределах архитектуры конкретного варианта осуществления.

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

В системе распределенной динамической маршрутизации должны быть расположены развитые логические функции маршрутизации:

Отдельно в PNS системе:

Система PNS содержит последний моментальный снимок базы данных за прошлый период.

Система PNS принимает информацию дорожной пробки из CNS системы.

Система PNS осуществляет прогнозирование времени прохождения и систему маршрутизации, основанной на этом приближении.

Совместно используемые между PNS системой и CNS системой.

Обе системы CNS и PNS вычисляют маршрут для пользователя.

Информация CNS системы всегда лучше.

Системы CNS и PNS стараются гарантировать, что PNS система обеспечивает всегда достаточно хороший маршрут с минимальными сюрпризами для пользователя.

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

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

3.2 PNS маршрутизация

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

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

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

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

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

3.3 Совместно используемая маршрутизация

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

Например:

1. Водитель запрашивает PNS систему (определить маршрут A B).

2. Система PNS вычисляет (A rst B).

3. Система PNS посылает CNS системе (выбранный маршрут (rs))

какой маршрут просили сделать,

первый промежуточный пункт(ы) (эквивалентно первым участкам маршрута), который был выбран.

4. Система CNS вычисляет (маршрут A B) с использованием своей системы маршрутизации, которая по определению дает лучший возможный маршрут, который может генерировать эта технология (A xyz B).

5. Система CNS сравнивает маршрут, который она генерировала, с маршрутом, генерированным PNS системой. В этом примере, CNS система составила маршрут через пункты x, y и z, совершенно отличный от маршрута PNS системы, так что она считает необходимым поставить в известность PNS систему.

6. Там, где есть отличия, CNS система передает эти данные обратно водителю. В частности, необходимо только сразу передать их в начале маршрута. И необходимо передать только первое отличие; после приема отличия PNS система может вычислить оставшийся маршрут от следующего промежуточного пункта на дороге, обеспеченного PNS системой. Так, CNS система сообщает PNS системе (выбранный маршрут A B (x)), и PNS система вычисляет (маршрут A -через x- B), который к счастью PNS система вычислила как (A xyz B).

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

7. Система CNS продолжает отслеживать маршрут водителя, посылая уведомления, если она заново вычислит отличающийся маршрут позже.

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

3.4 Фиг.3. PNS маршрутизация в сети с низкой нагрузкой

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

Механизм состоит в следующем:

1. Система PNS строит маршрутизируемую область для маршрута от A до B и запрашивает CNS систему относительно значений стоимости в CNS по периодам времени, в течение которых маршрут должен использоваться для каких-либо участков дороги в маршрутизируемой области, которые имеют более низкую стоимость согласно функции стоимости в CNS системе, чем согласно функции стоимости в PNS системе. Система CNS знает, какая функция стоимости используется в PNS системе, потому что PNS система может сообщить CNS системе версию базы данных за прошлый период, которую она поддерживает. Система CNS поддерживает кодирование всех баз данных за прошлый период, которые присутствуют в заполнении PNS систем, так что она может определять для любого участка дороги, нужно ли возвращать в PNS систему значения стоимости каких-либо участков. Задается минимальная разность стоимости на участок d_s , так что CNS система только посылает в PNS систему участки дороги и значения стоимости CNS системы (участок, стоимость _CNS(участка)), которые удовлетворяют условию стоимость_CNS(участка) + d_s стоимости_PNS(участка), то есть те, которые ниже значения стоимости CNS системы, по меньшей мере, на d_s. В частности, число таких выбранных участков дороги и, следовательно, размер и стоимость сообщения будут малы.

2. Теперь система PNS строит модифицированную функцию стоимости, стоимость_маршрута_PNS, которая присваивает значения, возвращенные PNS системой для участков дороги с более низкой стоимостью на предыдущей стадии, и присваивает значения за прошлый период, поддерживаемые PNS системой для всех других участков дороги. Система PNS выполняет вычисление маршрутизации от A до B, используя стоимость_маршрута_PNS. Маршрут, выбранный этим вычислением, называется потенциальный маршрут лучший_маршрут_PNS. Функция стоимости в CNS системе, стоимость_маршрута_CNS, может прикреплять этому маршруту стоимость более высокую, чем стоимость_маршрута _PNS, потому что модифицированная функция стоимости в PNS системе не знает о необыкновенно высоких издержках (приравненные к участкам дороги с задержкой), о которых знает функция стоимости в CNS системе. Но из-за того, что модификация функции стоимости в PNS системе на предыдущей стадии, лучший_маршрут _PNS, будет иметь стоимость согласно PNS системе, которая не намного больше, чем участок с самой низкой стоимостью согласно стоимость_маршрута_CNS, который назван здесь лучший_маршрут_CNS. На самом деле:

Стоимость_маршрута_PNS(лучший_маршрут _PNS) стоимость_маршрута_CNS(лучший_маршрут _CNS) + счет_участков (лучший_маршрут_CNS )·d_s. Значение d_s, используемое в системе, выбирается, чтобы определить, как близко значение стоимость_маршрута_PNS(лучший_маршрут _PNS) должно быть к значению стоимость_маршрута _CNS(лучший_маршрут_PNS) в зависимости от времени и ширины полосы пропускания, требуемой для передачи участков дороги и издержек на стадии 1.

3. Теперь остается проверить, что стоимость, которую CNS система присваивает потенциальному маршруту, выбранному PNS системой, стоимость_маршрута _CNS(лучший_маршрут_PNS), не намного хуже, чем стоимость, которую присваивает себе PNS система. Чтобы сделать это, PNS система запрашивает значения стоимости в CNS системе для участков дороги на лучший_маршрут _PNS. Система CNS отправляет значения стоимости для этих участков дороги в PNS систему, и PNS система обновляет свою функцию стоимости, чтобы включить в себя эти значения стоимости участков дороги из CNS системы. Если CNS система сохраняет в силе номер версии накопленной за прошлый период базы данных PNS системы, или PNS система посылает номер версии снова на этот вопрос, то CNS системе необходимо только ответить на те значения стоимости участков дороги, которые отличаются от тех, которые PNS система удерживает в своей базе данных. Теперь функция стоимости в PNS системе будет стоимость_маршрута_PNS ^{обновлен}.

4. Теперь PNS система вычисляет значение стоимость_маршрута_PNS ^{обновлен}(лучший_маршрут_PNS ) стоимости потенциального маршрута, который был ранее выбран, в это время используя поддерживаемые CNS системой значения стоимости участков дороги на этом маршруте. Следует заметить, что стоимость_маршрута_PNS ^{обновлен}(лучший_маршрут_PNS ) = стоимость_маршрута_CNS(лучший_маршрут _PNS). Максимальная приемлемая разность стоимости dextra_route задается, чтобы проверять, нужно ли принимать лучший_маршрут_PNS как маршрут для предложения клиенту на данной стадии, лучший_маршрут _PNS принимается именно в случае, когда стоимость_маршрута _PNS ^{обновлен}(лучший_маршрут_PNS ) стоимость_маршрута_PNS(лучший_маршрут _PNS) + dextra_route. Значение dextra_route, используемое системой, выбирается, чтобы определить, насколько значение стоимость_маршрута _PNS ^{обновлен}(лучший_маршрут_PNS ) близко к значению стоимость_маршрута_CNS (лучший_маршрут_СNS) в зависимости от времени и полосы пропускания сети, которую потребляет устройство.

5. Если был принят лучший_маршрут _PNS, то процесс выбора маршрута завершается, и лучший_маршрут _PNS выдается пользователю PNS системы.

6. Если лучший_маршрут_PNS не был принят, то механизм возвращается к стадии 2, кроме того, что в это время значение стоимость_маршрута_PNS ^{обновлен} используется для выбора нового потенциального маршрута лучший_маршрут'_PNS. Если лучший_маршрут' _PNS = лучший_маршрут_PNS (или, при дальнейших итерациях, любой ранее выбранный потенциальный маршрут), то лучший_маршрут'_PNS принимается сразу. В противном случае, система выполняет тот же процесс снова, запрашивая значения стоимости CNS системы для лучший_маршрут' _PNS (стадия 3), обновляя значение стоимость_маршрута _PNS ^{обновлен} и вычисляя значение стоимость_маршрута' _PNS ^{обновлен}(лучший_маршрут'_PNS ) (стадия 4).

7. В конечном счете, и обычно очень быстро, при заданном рациональном выборе значения dextra_route принимается один из потенциальных маршрутов, который генерирует система. Так же можно показать, что PNS система должна, в конце концов, принять потенциальный маршрут, потому что функция стоимости стоимость_маршрута _PNS ^{обновлен} будет стабилизироваться равной значению стоимость_маршрута_CNS, при котором точка стоимость_маршрута_PNS ^{обновлен} = стоимость_маршрута_PNS и условие принятия для текущего потенциального маршрута, стоимость_маршрута_PNS ^{обновлен}(лучший_маршрут_PNS ) стоимость_маршрута_PNS(лучший_маршрут _PNS) + dextra_route, будет сразу схватываться.

8. Система выдает принятый маршрут пользователю PNS системы.

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

10. По мере того как водитель едет к пункту назначения, система может периодически запрашивать (как на стадии 3) издержки для остающихся участков дороги принятого маршрута. Если задержка накапливается дальше по маршруту, PNS система может автоматически переделывать маршрут от текущего положения посредством возобновления алгоритма на стадии 4.

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

3.5 Снижение издержек связи

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

Нумерация участков относительно местоположения

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

Нумерация участков относительно маршрута

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

Когда, как обычно бывает, большой отрезок маршрута находится на одной и той же дороге, может быть использовано кодирование длины пробега. Тогда маршрут может быть представлен как (3, 13, 2, 28, 2, 15) значение:

3-й выход - следующий перекресток

прямо через следующие 12 перекрестков

2-й выход на 14-ом перекрестке

прямо через следующие 28 перекрестков

2-й выход на 29-ом перекрестке

прямо через 15 перекрестков

прибытие.

Библиография

Dijkstra: Edsgar W.Dijkstra, A Note on Two Prоblems in Connection with Graphs,1959.

CFIT: UK Commission for Integrated Transport, Congestion Charging.

RoDIN24: Applied Generics, RoDIN24 real-time road traffic information, 2005.