СПОСОБЫ И СИСТЕМЫ ДЛЯ ДИНАМИЧЕСКИ АДАПТИВНЫХ ИЕРАРХИЧЕСКОГО ПРЕДСТАВЛЕНИЯ И ПРОКЛАДКИ МАРШРУТОВ ДОРОЖНОЙ СЕТИ

1. Способ для вычисления маршрутов в дорожной сети, состоящий в том, что:
предварительно обрабатывают данные маршрутов для одного или более внешних профилей, интегрированных в иерархию дорог в базе данных;
вычисляют кратчайшие расстояния для одного или более внешних профилей;
сливают кратчайшие расстояния для одного или более внешних профилей в базу данных;
идентифицируют один или более участков дорожной сети в качестве являющихся более предпочтительными, чем нормальный, на основании данных реального времени;
выражают один или более участков дорожной сети в качестве последовательности местоположений, содержащей уникально идентифицируемый путь;
динамически добавляют связи, описывающие последовательность местоположений, в иерархию дорог в базе данных; и
выполняют кластерную прокладку маршрута для приближения стоимостей прохождения маршрутов на основании данных дорожного движения реального времени.
2. Способ по п.1, в котором выполнение кластерной прокладки маршрута для приближения стоимостей прохождения маршрутов на основании данных дорожного движения реального времени состоит в том, что:
разделяют дорожную сеть на логическое кластерное дерево;
сохраняют время прохождения для каждого кластера в соседний кластер;
замещают эвристику для оценки стоимости от узла до центра противоположного фронта волны близкой стоимостью прохождения, в направлении прокладки маршрута, между кластером узла и кластером центра противоположной волны;
вычисляют стоимость для каждой связи, которая распространяется от узла фронта волны пункта назначения, по интервалу времени на основании подвергнутого кластерному приближению времени прохождения в таком узле, и
когда узлы из противоположных фронтов волны создают соединения, близкие стоимости на целевой волне замещаются вновь вычисленной стоимостью реального пути из пункта отправления.
3. Способ по п.1, в котором кратчайшие расстояния для одного или более профилей сливаются в базу данных.
4. Способ по п.3, в котором узел имеет максимальный приоритет значения узла между одним или более профилей, слитых в базу данных.
5. Способ по п.1, в котором интервалы времени с не имеющей физического смысла частотой изменения сжимаются в меньшие внешние профили.
6. Способ по п.5, в котором таблица перекрестных ссылок отображает ID дорожной сети, которые используются поставщиком данных дорожного движения, в ID дорожной сети, которые используются программным обеспечением прокладки маршрута.
7. Способ по п.6, в котором таблица перекрестных ссылок используется для идентификации, каким узлам и связям в существующей дорожной сети необходимо модифицироваться в ответ на данные реального времени.
8. Способ по п.7, в котором модифицированные связи, основанные на данных реального времени, дают алгоритму поиска пути возможность настраиваться на условия дорожного движения реального времени, интегрируя предоставленные извне объезды.
9. Способ по п.2, в котором дорожная сеть разделяется на кластерное дерево по критериям подразделения.
10. Способ по п.9, в котором критерии подразделения являются функцией плотности дорог на квадратную милю, коэффициента дорожных пробок, частоты прохождения или подобных критериев.
11. Способ по п.9, в котором сохраняется время прохождения из кластера в один или более соседних кластеров.
12. Способ по п.11, в котором время прохождения из кластера в кластер предварительно вычисляется и/или динамически поддерживается из испытательных значений данных реального времени.
13. Способ по п.9, в котором эвристика для оценки стоимости от узла до центра противоположного фронта волны замещается близкой стоимостью прохождения, в направлении прокладки маршрута, между кластером узла и кластером, где находится центр противоположного фронта волны.
14. Способ по п.13, в котором, когда узлы из противоположных фронтов волны создают соединения, близкие стоимости на целевой волне замещаются вновь вычисленной стоимостью реального пути из пункта отправления.
15. Машинно-читаемый запоминающий носитель, хранящий команды для вычисления маршрутов в дорожной сети по любому из способов по пп.1-14.
16. Система, содержащая:
модуль для предварительной обработки данных маршрутов для одного или более внешних профилей, интегрированных в иерархию;
модуль для динамического добавления связей в иерархию в ответ на данные реального времени об условиях дорожного движения; и
систему для кластерной прокладки маршрута для приближения стоимостей прохождения маршрутов на основании данных дорожного движения реального времени.
17. Способ для вычисления маршрутов в дорожной сети, состоящий в том, что:
a) идентифицируют один или более участков дорожной сети в качестве являющихся более предпочтительными, чем нормальный, на основании данных реального времени;
b) выражают один или более участков дорожной сети в качестве последовательности местоположений, содержащих уникально идентифицируемый путь;
c) используют последовательность местоположений, содержащую уникально идентифицируемый путь, для добавления одной или более связей в уже сконструированную иерархическую сеть дорог; и
d) дают алгоритму поиска пути возможность настроиться на данные реального времени.
18. Способ по п.17, в котором данные реального времени включают в себя условия дорожного движения.
19. Способ по п.17, в котором таблица перекрестных ссылок отображает ID дорожной сети, которые используются поставщиком данных дорожного движения, в ID дорожной сети, которые используются программным обеспечением прокладки маршрута.
20. Способ по п.19, в котором таблица перекрестных ссылок используется для идентификации, каким узлам и связям в существующей дорожной сети необходимо модифицироваться в ответ на данные реального времени.
21. Способ по п.17, в котором данные реального времени об условиях дорожного движения поставляются внешним источником.
22. Способ по п.17, в котором одиночное удлинение дороги может давать в результате многочисленные связи, добавляемые на разных уровнях иерархии.
23. Способ по п.17, в котором новые связи поставляются в алгоритм поиска пути таким же образом, как существующие связи.
24. Способ по п.17, в котором данные реального времени включают в себя интегрирование поставляемых извне объездов.
25. Способ по п.17, в котором одиночный объезд может давать в результате многочисленные связи, добавляемые на разных уровнях иерархии, снабженные надлежащим приоритетом и составленные как надлежит для каждого уровня.
26. Способ по п.17, дополнительно состоящий в том, что: инкрементально собирают один или более профилей в уже существующие ветви иерархии, когда большие участки сети имеют модифицированные времена прохождения.
27. Машинно-читаемый запоминающий носитель, хранящий команды для вычисления маршрутов в дорожной сети по любому из способов, изложенных в любом из пп.17-26.
28. Способ для улучшения вычисления оптимизированного по времени прохождения маршрута в дорожной сети, состоящий в том, что:
a) разделяют дорожную сеть на логическое кластерное дерево;
b) сохраняют время прохождения для каждого кластера в соседний кластер;
c) замещают эвристику для оценки стоимости от узла до центра противоположного фронта волны близкой стоимостью прохождения, в направлении прокладки маршрута, между кластером узла и кластером центра противоположной волны;
d) вычисляют стоимость для каждой связи, которая распространяется от узла фронта волны пункта назначения, по интервалу времени на основании подвергнутого кластерному приближению времени прохождения в таком узле, и
e) когда узлы из противоположных фронтов волны создают соединения, близкие стоимости на целевой волне замещаются вновь вычисленной стоимостью реального пути из пункта отправления.
29. Способ по п.28, дополнительно состоящий в том, что используют алгоритм A*.
30. Способ по п.28, в котором статистическая, реального времени и прогнозная информация о дорожном движении дает водителю возможность экономить время, выбирая маршрут, который требует меньшего времени, и повышать точность времени прохождения.
31. Способ по п.28, в котором данные реального времени об условиях дорожного движения содержат данные, форматированные в качестве RDS TMC, AGORA-C, VICS или другого способа привязки к местоположению.
32. Способ по п.28, дополнительно состоящий в том, что разделяют дорожную сеть на логическое кластерное дерево по критериям подразделения.
33. Способ по п.28, в котором критерии подразделения являются функцией плотности дорог на квадратную милю, дорожных пробок, частоты прохождения или подобных критериев.
34. Способ по п.28, в котором время прохождения из кластера в кластер предварительно вычисляется из статистических или прогнозных данных и/или динамически поддерживается из испытательных значений данных реального времени.
35. Способ по п.28, в котором испытательные данные времени выполнения используются для вычисления, как долго занимает, чтобы транспортное средство переходило из кластера в соседний кластер или из кластера узла в целевой кластер волны.
36. Машинно-читаемый запоминающий носитель, хранящий команды для улучшения вычисления оптимизированных по времени маршрутов в дорожной сети по любому из способов, изложенных в любом из пп.28-35.
37. Способ для улучшения вычисления оптимизированного по времени прохождения маршрута в дорожной сети, состоящий в том, что:
a) разделяют дорожную сеть на квадратное дерево;
b) сохраняют время прохождения для каждого квадрата в соседний квадрат;
c) замещают эвристику для оценки стоимости от узла до центра противоположного фронта волны близкой стоимостью прохождения, в направлении прокладки маршрута, между квадратом узла и квадратом центра противоположной волны;
d) вычисляют стоимость для каждой связи, которая распространяется от узла фронта волны пункта назначения, по интервалу времени на основании подвергнутого квадратному приближению времени прохождения в таком узле, и
e) когда узлы из противоположных фронтов волны создают соединения, близкие стоимости на целевой волне замещаются вновь вычисленной стоимостью реального пути из пункта отправления.
38. Способ по п.37, дополнительно состоящий в том, что используют алгоритм A*.
39. Способ по п.37, в котором данные реального времени об условиях дорожного движения содержат данные, форматированные в качестве RDS TMC, AGORA-C, VICS или другого способа привязки к местоположению.
40. Способ по п.37, в котором время прохождения из квадрата в квадрат предварительно вычисляется из статистических или прогнозных данных и/или динамически поддерживается из испытательных значений данных реального времени.
41. Способ по п.37, дополнительно состоящий в том, что разделяют дорожную сеть на логическое кластерное дерево с критериями подразделения в качестве функции плотности дорог на квадратную милю, дорожных пробок, частоты прохождения или подобных критериев.