Dispositivo de navegación y método para el cálculo de ruta con dependencia temporal.

Un método de determinación de perfiles de coste de rutas que usa datos de mapa divididos en una pluralidad de regiones (600;

602, 604, 606, 608), los datos de mapa que comprenden:

una pluralidad de segmentos navegables (304a, 304b, 304c, 304d) que representan segmentos de trayectos navegables de los datos de mapa, cada segmento navegable que tiene una función de coste que varía con la hora asociada; y

datos de coste mínimo (704) para los segmentos navegables dentro de cada región de los datos de mapa que identifican, para cada una de las otras regiones, si un segmento navegable es parte de un trayecto de coste mínimo para la otra región en cualquier periodo de tiempo,

el método que comprende usar al menos un aparato de procesamiento para:

buscar rutas desde un origen a un destino, la búsqueda que comprende determinar si uno o más segmentos navegables de un conjunto de segmentos navegables conectados a un nodo se identifican por los datos de coste mínimo como parte de un trayecto de coste mínimo para regiones que comprenden el origen y destino y, si uno o más de los segmentos navegables del conjunto se identifican como que son parte de un trayecto de coste mínimo, explorar desde el conjunto solamente los uno o más segmentos navegables que se identifican como que son parte de un trayecto de coste mínimo;

caracterizado por que el método comprende usar el al menos un aparato de procesamiento para: determinar un perfil de coste de las rutas en el tiempo a partir de las funciones de coste que varían con la hora de los segmentos navegables que se exploran,

en donde determinar un perfil de coste de las rutas en el tiempo comprende:

combinar un primer perfil de coste (C1) asociado con un primer trayecto de coste mínimo y un segundo perfil de coste (C2) asociado con un segundo trayecto de coste mínimo cuando el primer y segundo trayectos de coste mínimo se cruzan en un nodo.

Dispositivo de navegaciïn y mïtodo para el cïlculo de ruta con dependencia temporal

Campo de la invenciïn La presente invenciïn se refiere a un mïtodo informatizado de determinaciïn de una ruta usando datos de mapa y sistemas relacionados. En particular, pero no exclusivamente, el mïtodo se puede usar en un dispositivo de navegaciïn usado para facilitar una planificaciïn de ruta.

Antecedentes de la invenciïn Son conocidos algoritmos de planificaciïn de ruta (tales como el mïtodo Dijkstra, mïtodo A* o mïtodos Moore/Pape) . No obstante, ïstos pueden ser algo lentos. Un ejemplo de cïmo se puede aumentar la velocidad de tal planificaciïn de ruta se muestra en la US 6 636 800. La US 6 636 800 enseïa un procesamiento previo de datos de mapa dividiendo el mapa en regiones y determinando un ïrbol de trayectos mïs cortos (trayectos de coste mïnimo) para cada regiïn del mapa. Estos datos procesados previamente se almacenan en memoria y se usan durante el cïlculo de una ruta.

Mïs especïficamente, cuando un origen estï dentro una regiïn y un destino estï dentro de otra regiïn, se puede usar el ïrbol predeterminado de trayectos mïs cortos para determinar rïpidamente el trayecto entre las regiones a ser usadas como parte de la ruta. Tal mïtodo reduce el nivel de procesamiento requerido para determinar una ruta debido a que reduce el nïmero de trayectos explorados desde que un usuario solicita la determinaciïn de una ruta.

Se entenderï que trayecto “mïs corto” no necesariamente significa el trayecto de la distancia mïs corta sino que significa el trayecto que tiene el coste mïnimo. El coste del trayecto dependerï de los factores que se consideren como especificados en una fïrmula de coste y pueden tener en cuenta factores tales como la ruta mïs rïpida y el uso de combustible.

Tal mïtodo tiene mucho ïxito cuando los trayectos mïs cortos entre regiones permanecen estïticos. No obstante, los cambios en las condiciones del trïfico con el tiempo pueden cambiar el trayecto que es el mïs corto entre regiones de manera que el ïrbol procesado previamente ya no identifica los trayectos mïs cortos verdaderos entre regiones. Esto puede provocar a una ruta que se determina que no sea la ruta ïptima para los criterios especificados.

“Engineering and Augmenting Route Planning Algorithms” de Daniel Delling, 10 de febrero de 2009, XP002612394 describe las ideas detrïs de varias tïcnicas de aceleraciïn para encaminamiento estïtico exacto en redes de carreteras.

La JP 2004-233230 describe un terminal de navegaciïn que puede mostrar la informaciïn de congestiïn de trïfico sobre el pronïstico de una carretera, se realiza la visualizaciïn de ruta de dos o mïs rutas recomendadas teniendo en cuenta la predicciïn de congestiïn de trïfico que se puede encontrar cuando se cambia la hora de salida y la hora de llegada, y aspira a mostrar al usuario la diferencia del efecto de dos o mïs rutas recomendadas teniendo en cuenta la predicciïn de congestiïn de trïfico.

La US 2004/0249568 describe un dispositivo de almacenamiento que almacena datos de mapa incluyendo datos de enlace de enlaces respectivos que constituyen las carreteras en un mapa, y datos estadïsticos que incluyen el tiempo de viaje (velocidad de movimiento) que se determina por valores estadïsticos de informaciïn de trïfico recogida en el pasado, con respecto a cada uno de los enlaces. La US 2004/0249568 ademïs describe que el dispositivo de navegaciïn usa para cada candidata de hora de salida, los datos de mapa y los datos estadïsticos de una colecciïn de condiciones que corresponden a los estados tras pasar cada uno de los enlaces de constituciïn de ruta que constituyen la ruta, para obtener el tiempo de viaje para cada uno de los enlaces de constituciïn de ruta. A partir de entonces, los tiempos de viaje de los enlaces de constituciïn de ruta respectivos obtenidos de esta manera se suman, y se obtiene el tiempo de viaje entre la posiciïn de salida y el destino.

Compendio de la invenciïn Segïn un primer aspecto de la invenciïn se proporciona un mïtodo de determinaciïn de perfiles de coste de rutas usando datos de mapa segïn la reivindicaciïn 1.

El perfil de coste permite a un usuario y/o un aparato de navegaciïn determinar cïmo cambiar la hora de viaje alterarï el coste de la ruta. De este modo, se puede seleccionar una hora de viaje en base al perfil de coste.

Segïn un segundo aspecto de la invenciïn se proporciona una portadora de datos que tiene almacenada en la misma instrucciones que, cuando se ejecutan por un aparato de procesamiento, hacen al aparato de procesamiento ejecutar un mïtodo segïn el primer aspecto de la invenciïn.

Segïn un tercer aspecto de la invenciïn se proporciona un dispositivo informïtico que comprende una memoria que

tiene almacenados en la misma datos de mapa segïn la reivindicaciïn 11.

Breve descripciïn de las figuras Ahora sigue a modo de ejemplo solamente una descripciïn detallada de realizaciones de la presente invenciïn con referencia a los dibujos anexos en los que:

La Figura 1 es una ilustraciïn esquemïtica de una parte ejemplar de un Sistema de Posicionamiento Global

(GPS) utilizable por un dispositivo de navegaciïn;

La Figura 2 es un esquema de un servidor y dispositivo de navegaciïn en comunicaciïn a travïs de un canal de comunicaciones;

La Figura 3a es un esquema de un dispositivo de navegaciïn;

La Figura 3b es una representaciïn esquemïtica de una pila de arquitectura empleada por el dispositivo de navegaciïn de la Figura 3a;

La Figura 4 es una vista en perspectiva de un dispositivo de navegaciïn;

La Figura 5 muestra una parte de un mapa ejemplo que se genera por realizaciones de la invenciïn;

La Figura 6 muestra el mapa de la Figura 5 en el que se muestran nodos usados para encaminamiento;

La Figura 7 muestra el mapa de la Figura 5 que sigue el procesamiento;

La Figura 8 muestra un ejemplo de cïmo los nodos, en algunas realizaciones, se asignan al mapa de la Figura

7;

La Figura 9 ilustra un ejemplo de cïmo se puede dividir un mapa en una pluralidad de regiones anidadas;

La Figura 9a ilustra una mejora de la divisiïn de la Figura 9;

La Figura 10 muestra un ejemplo de conjunto de vectores de bit utilizados por realizaciones de la invenciïn;

La Figura 10a ilustra cïmo se utiliza informaciïn de perfil de tiempo durante una exploraciïn Dijkstra de una red;

La Figura 11 muestra un ejemplo de formato de fichero para un fichero de una realizaciïn de la invenciïn;

La Figura 12 muestra una realizaciïn de cïmo se pueden codificar la tabla de reasignaciïn de regiïn y las listas

de ID de regiïn de la Figura 11;

La Figura 13 muestra un ejemplo de formato de fichero para la regiïn anidada mïs tosca como se ilustra en la

Figura 3;

La Figura 14 muestra un ejemplo de formato de fichero para regiones anidadas distintas de la mïs tosca;

La Figura 15 ejemplifica la coalescencia de bits dentro de un esquema de codificaciïn;

La Figura 16 ejemplifica el efecto de la coalescencia de bits;

La Figura 17 tambiïn ejemplifica el efecto de la coalescencia de bits;

La Figura 18 muestra un mapa que resalta rutas consideradas usando las tïcnicas de encaminamiento de la

TïCNICA ANTERIOR;

La Figura 19 muestra un mapa que resalta rutas consideradas por realizaciones de la invenciïn actual;

La Figura 20 muestra un ejemplo del mïtodo de bïsqueda A* (TïCNICA ANTERIOR) ;

La Figura 21 muestra una modificaciïn a la Figura 20 usada por al menos algunas realizaciones de la invenciïn;

La Figura 22 muestra un diagrama de flujo que perfila los pasos del mïtodo;

La Figura 23 muestra un visualizador de un dispositivo de navegaciïn que ilustra las velocidades esperadas en

los segmentos navegables de la ruta;

La Figura 24 muestra un visualizador de un dispositivo de navegaciïn que ilustra un perfil de coste para una o mïs rutas entre un origen y destino;

La Figura 25 muestra un visualizador de un dispositivo de navegaciïn que ilustra un perfil de coste de una o mïs

rutas entre un origen y un destino;

La Figura 26 muestra un visualizador de un dispositivo de navegaciïn que ilustra una ruta entre un origen y destino para una hora de viaje particular y un control para cambiar la hora de viaje;

La Figura 27 muestra una actualizaciïn del visualizador de la Figura 26 despuïs de que el usuario ha alterado la hora de viaje;

La Figura 28 muestra una actualizaciïn del visualizador de la Figura 27 despuïs de que el usuario ha alterado la hora... [Seguir leyendo]

1. Un mïtodo de determinaciïn de perfiles de coste de rutas que usa datos de mapa divididos en una pluralidad de regiones (600; 602, 604, 606, 608) , los datos de mapa que comprenden:

una pluralidad de segmentos navegables (304a, 304b, 304c, 304d) que representan segmentos de trayectos 5 navegables de los datos de mapa, cada segmento navegable que tiene una funciïn de coste que varïa con la hora asociada; y

datos de coste mïnimo (704) para los segmentos navegables dentro de cada regiïn de los datos de mapa que identifican, para cada una de las otras regiones, si un segmento navegable es parte de un trayecto de coste mïnimo para la otra regiïn en cualquier periodo de tiempo,

el mïtodo que comprende usar al menos un aparato de procesamiento para:

buscar rutas desde un origen a un destino, la bïsqueda que comprende determinar si uno o mïs segmentos navegables de un conjunto de segmentos navegables conectados a un nodo se identifican por los datos de coste mïnimo como parte de un trayecto de coste mïnimo para regiones que comprenden el origen y destino y, si uno o mïs de los segmentos navegables del conjunto se identifican como que son parte de un trayecto de coste mïnimo, explorar desde el conjunto solamente los uno o mïs segmentos navegables que se identifican como que son parte de un trayecto de coste mïnimo;

caracterizado por que el mïtodo comprende usar el al menos un aparato de procesamiento para:

determinar un perfil de coste de las rutas en el tiempo a partir de las funciones de coste que varïan con la hora de los segmentos navegables que se exploran,

en donde determinar un perfil de coste de las rutas en el tiempo comprende:

combinar un primer perfil de coste (C1) asociado con un primer trayecto de coste mïnimo y un segundo perfil de coste (C2) asociado con un segundo trayecto de coste mïnimo cuando el primer y segundo trayectos de coste mïnimo se cruzan en un nodo.

2. Un mïtodo segïn la reivindicaciïn 1, en donde el paso de combinar el primer (C1) y segundo (C2) perfiles de coste comprende superponer los dos perfiles de coste y determinar al menos uno de un perfil de coste mïximo (UB) y mïnimo (LB) para propagaciïn adicional.

3. Un mïtodo segïn la reivindicaciïn 1, en donde el paso de combinar el primer (C1) y segundo (C2) perfiles de coste comprende determinar un perfil de coste medio para propagaciïn adicional.

4. Un mïtodo segïn cualquier reivindicaciïn precedente, en donde la funciïn de coste que varïa con la hora

asociada con un segmento navegable comprende datos de perfil de velocidad que identifican la velocidad esperada en el segmento navegable a diferentes horas.

5. Un mïtodo segïn cualquier reivindicaciïn precedente, en donde el perfil de coste de las rutas con el tiempo se determina en respuesta a recibir una peticiïn de perfil de coste, la peticiïn de perfil de coste que incluye un periodo de tiempo dentro del cual estï confinada la bïsqueda de rutas.

6. Un mïtodo segïn cualquiera de las reivindicaciones 1 a 4, que comprende recibir una peticiïn de una ruta entre el origen y el destino a una hora de viaje particular, el perfil de coste de las rutas con el tiempo que se determina para una ventana de tiempo que incluye esa hora de viaje particular, el mïtodo que ademïs comprende:

determinar a partir del perfil de coste si a otra hora dentro de esa ventana de tiempo el coste de la ruta es menor que el coste para la hora particular y, si el coste es menor, causar la visualizaciïn de un mensaje (2015) que informa al usuario de la otra hora de viaje.

7. Un mïtodo segïn cualquiera de las reivindicaciones 1 a 4, que comprende recibir desde un usuario a travïs de una interfaz de usuario una selecciïn de una hora de viaje y causar una visualizaciïn para mostrar una imagen de la ruta determinada a partir del perfil de coste a la hora de viaje recibida.

8. Un mïtodo segïn la reivindicaciïn 7, que comprende permitir al usuario cambiar la hora de viaje mientras que

ve la imagen de la ruta, y, en respuesta a un cambio en la hora de viaje, actualizar la visualizaciïn con una imagen de una nueva ruta determinada a partir del perfil de coste para la hora de viaje cambiada.

9. Un mïtodo segïn la reivindicaciïn 8, que comprende causar la visualizaciïn de un control deslizante que representa la hora de viaje y actualizar la visualizaciïn con la imagen de la nueva ruta en respuesta a la interacciïn del usuario con el control deslizante.

10. Una portadora de datos que tiene almacenadas sobre la misma instrucciones que, cuando se ejecutan por un aparato de procesamiento, causan al aparato de procesamiento ejecutar un mïtodo segïn cualquier reivindicaciïn precedente.

11. Un dispositivo informïtico que comprende una memoria que tiene almacenados en la misma datos de mapa divididos en una pluralidad de regiones (600; 602, 604, 606, 608) , los datos de mapa que comprenden:

una pluralidad de segmentos navegables (304a, 304b, 304c, 304d) que representan segmentos de trayectos navegables de los datos de mapa, cada segmento navegable que tiene una funciïn de coste que varïa con la hora asociada; y

datos de coste mïnimo (704) para los segmentos navegables dentro de cada regiïn de los datos de mapa que identifican, para cada una de las otras regiones, si un segmento navegable es parte de un trayecto de coste mïnimo para la otra regiïn en cualquier periodo de tiempo,

el aparato de procesamiento dispuesto para:

buscar rutas desde un origen a un destino, la bïsqueda que comprende determinar si uno o mïs segmentos navegables de un conjunto de segmentos navegables conectados a un nodo se identifican por los datos de coste mïnimo como parte de un trayecto de coste mïnimo para regiones que comprenden el origen y destino y, si uno o mïs de los segmentos navegables del conjunto se identifican como que son parte de un trayecto de coste mïnimo, explorar desde el conjunto solamente el uno o mïs segmentos navegables que se identifican como que son parte de un trayecto de coste mïnimo;

caracterizado por que el aparato de procesamiento estï dispuesto para:

determinar un perfil de coste de las rutas en el tiempo a partir de las funciones de coste que varïan con la hora 20 de los segmentos navegables que se exploran,

en donde determinar un perfil de coste de las rutas en el tiempo comprende:

combinar un primer perfil de coste (C1) asociado con un primer trayecto de coste mïnimo y un segundo perfil de coste (C2) asociado con un segundo trayecto de coste mïnimo cuando el primer y segundo trayectos de coste se cruzan en un nodo.