Metodología y sistema de optimización de ruta con navegación GPS, combinando datos de tráfico dinámicos.

Metodología para la obtención, procesamiento y distribución de datos del tráfico y planificación de ruta más precisa en asistentes de navegación personal (ANP),

de navegación GPS.

Dicha metodología consiste en:

a) una Metodología de Obtención de Datos (MOD), caracterizada por un procedimiento para el registro y procesamiento de datos del tráfico dinámicos y parámetros del vehículo por un ANP, que aseguran la validez, autenticidad, verificabilidad y unicidad de los datos recogidos; consistiendo estos en los rasgos temporales distintivos, la velocidad y duración del viaje a través de cada segmento, estado de la carretera, condiciones climatológicas, tipo de vehículo, si se trata de un día laboral o festivo; proporcionando así datos de modo que los mapas del ANP también se actualizan con las nuevas carreteras no registradas hasta ahora,

b) una Metodología de Incorporación de Datos (MID), caracterizada por:

i. la comprobación por parte del Sistema Central (SC) de la integridad, autenticidad, unicidad y validez de los datos proporcionados por un ANP, mediante el modulo SID del software del cliente, al SC, y

ii. por la incorporación estadística y codificación de dichos datos en un único "mapa global", que es un mapa de la base de datos mundial, después del procesamiento en modo offline de los datos obtenidos por el ANP, realizado por el SC,

c) una Metodología de Distribución de Datos (MDD), caracterizada por:

i) la selección por parte del módulo del servidor del SDD y la distribución a los usuarios del ANP de los datos actualizados de mapas desde la única base de datos del "mapa global" del SC, ii) asegurar la integridad, autenticidad y unicidad de los datos, y iii) la incorporación de los datos recodificados en el sistema de mapas disponible del ANP.

d) Metodología de Planificación de Ruta (MPR), caracterizada por el uso de datos de mapas actualizados por la MID y seleccionados por la MDD, en combinación con los mapas convencionales de un ANP, para que el ANP pueda inferir y mejorar las decisiones de planificación de ruta desde un punto de origen hasta un destino final, con o sin destinos intermedios, basada en:

iii. Datos del tráfico dinámicos, es decir, usando la combinación de información: hora del día, día de la semana, estación del año, tipo de vehículo, tipo de condiciones climatológicas, estado de la carretera y tipo de día festivo, o laborable, y iv. criterios de decisión, como puedan ser, menor tiempo empleado en un viaje, menor coste de gasolina, o una combinación de ambos, especificado por el usuario/conductor,

y siendo dicha metodología implementada con un Sistema Central (SC) y uno o varios ANP portátiles en modo offline. Considerando que, la MOD obtiene información relativa a la densidad del tráfico en cada segmento de la carretera, basándose en la velocidad de cada tipo de vehículo y en el estado de la carretera en un periodo temporal determinado, datos proporcionados por conductores que viajan en la red de carreteras haciendo uso de su ANP.

Considerando que, la MOD se caracteriza por registrar, para cada segmento de carretera recorrido, una combinación de información consistente en los rasgos temporales distintivos del viaje, la duración del viaje y longitud del segmento, las condiciones climatológicas o el estado de la carretera, el tipo de vehículo.

Considerando que, la MOD se caracterizada también por registrar los datos en segmentos de carretera no registrados, propiciando así la creación de potenciales nuevos mapas.

Metodologia y sistema de optimizacion de ruta con navegacion GPS, combinando datos de trafico dinamicos. Se trata de una metodologia y un sistema que mejoran la precision de los sistemas de navegacion GPS, o "Asistentes de Navegacion Personal" (ANP) , en la planificacion de una ruta, utilizando una combinacion de datos basada en el registro de datos dinamicos del trafico del usuario. Una de las operaciones mas utiles de un ANP es la determinacion de la ruta optima (o no optima) entre dos puntos (origen y destino) , basada en unos criterios y condiciones especificos. El problema teorico de la optimizacion de ruta entre dos nodos en un sistema de nodos interconectados, donde cada enlace (borde) entre dos nodos tiene un respectivo peso constante (estatico) o variable (dinamico) , asociado al mismo, hace decadas que se conoce y se ha resuelto mediante varios metodos (por ejemplo, Dijkstra, los algoritmos de Bellman - Ford para la determinacion del camino mas corto, etcetera) . Los primeros ANP disponibles en el mercado hasta la actualidad han usado principalmente datos estaticos (pesos) , asociados con cada "segmento de carretera" (definidos como parte de una carretera o camino, de corta distancia, y entre dos intersecciones u otros dos puntos de referencia intermedios) , como puede ser la media de tiempo en ese segmento de la carretera, normalmente calculado arbitrariamente o basado en la velocidad permitida (estatica) en dicho segmento. Metodos mas recientes recomiendan la correlacion de cada segmento de carretera con informacion en funcion del tiempo o relacionada con el usuario, obteniendo asi mejores resultados de planificacion de ruta. Dicha informacion en funcion del tiempo seria por ejemplo la informacion sobre el trafico, que depende del dia y la hora en que el usuario pasa por un cierto recorrido, y que se obtiene gracias a un ANP por medio de un servidor offline y un canal de comunicacion. La informacion, que dependera del usuario, contendra una seleccion de rutas o preferencias del usuario, basadas en los habitos registrados y en su perfil. Hasta ahora, se han propuesto varios metodos y sistemas para registrar la informacion dinamica, como por ejemplo:

- sensores de trafico, que proporcionan informacion en tiempo real/ online, u off-line, sobre varios parametros del trafico en las carreteras principales,

- proveedores de telefonia movil, que proporcionan informacion sobre la densidad de telefonos moviles (y por consiguiente la densidad de coches) en varias areas, suministrando asi una indicacion de la densidad del trafico en esas areas,

- usuarios de telefonos moviles con GPS, que proporcionan informacion en tiempo real, en servidores web centrales, sobre las condiciones del trafico, etc.

Toda esta informacion en funcion del tiempo se registra y unifica en servidores centrales off-line, los cuales a su vez proporcionan sus datos, cuando se solicitan, mediante subscripciones en tiempo real. La mayoria de los sistemas de navegacion GPS disponibles (para vehiculos o telefonos moviles) usan informacion estatica que se registra en mapas, para ejecutar un calculo de navegacion y definir rutas especificas desde un origen hasta un destino final determinados (o destinos intermedios) . Durante los ultimos 5 aros, se han publicado numerosos articulos sobre la mejora en la planificacion de ruta de estos sistemas, introduciendo datos no estaticos (o en funcion del tiempo) , obtenidos principalmente a traves de fuentes y estaciones externas (sensores, servidores web, etc.) , asi como mediante diversos canales de comunicacion, tales como GSM, GPRS, WiFi, WiMAX, etc., y conexiones (sistema de datos flotantes del coche, FCD) . Ademas, la obtencion de datos desde ANP moviles y su libre distribucion a usuarios de sistemas ANP es un metodo que se ha estado usado durante los ultimos 3 aros por la Fundacion OpenStreetMap (http//openstreetmap.org) . Sin embargo, estos datos son generales (es decir, no pueden ser aprovechados directamente por los ANP disponibles) y los sistemas respectivos no procesan ni distribuyen informacion sobre segmentos de carretera para la optimizacion de la ruta, sino que tan solo componen un mapa global sin datos sobre el trafico de la red de carreteras.

BIBLIOGRAFIA

º Jin Y. Yen, 'An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", in Quarterly of Applied Mathematics, 27, pp. 526-530, 1970.

º Richard Bellman, 'On a Routing Problem", in Quarterly of Applied Mathematics, 16 (1) , pp. 87-90, 1958.

º Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 'Introduction to Algorithms", 2nd edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

º F. Benjamin Zhan, and Charles E. Noon, 'Shortest Path Algorithms: An Evaluation Using Real Road Networks", Transportation Science 32 (1) : 65-73, 1998.

º C. Zhang, X. Yang and X. Yan, 'Methods for Floating Car Sampling Period Optimization", Journal of Transportation Systems Engineering and Information Technology, vol. 7, issue 3, pp.100-104, June 2007.

• M.E. Fouladvand and A.H. Darooneh, 'Statistical Analysis of Floating Car Data: an empirical study", The European Physical Journal B, vol. 47, issue 2, 319-328, 2005.

Referencias enInternet

- El Algoritmo del camino mas corto de Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s algorithm

- El Algoritmo de Bellman-Ford: http://en.wikipedia.org/wiki/Bellman-Ford algorithm

Patentes relacionadas:

WO98/54682:Generacion y entrega de informacion relacionada con la localizacion durante el viaje. Diferencias: Se trata de un sistema que localiza vehiculos en movimiento equipados con un transmisor de deteccion de posicion.

US2003/0083813:Sistema de navegacion que proporciona informacion sobre el trafico en tiempo real y la procesa. Diferencias: Es un sistema que funciona en condiciones de trafico en tiempo real transmitidas a traves de una red de comunicacion.

US2004/0044465:Determinacion de una ruta automatizada basandose en el recorrido del dia de la ruta. Diferencias: Trata sobre la computacion de una ruta mediante un sistema central y la transmision online de la misma a sistemas moviles (ANP) , en contraposicion a nuestro metodo de computacion local por medio del ANP.

EP1387145 (2004) :Sistema de navegacion dinamico diferencial por navegacion offboard (externa al vehiculo) . Diferencias: Sistema en el que las condiciones de trafico en tiempo real se transmiten a traves de una red de comunicacion, en contraposicion a nuestro sistema, en el que la trasmision de informacion sobre el trafico es en tiempo casi real y no requiere una red de comunicacion activa (metodo offline) .

WO2007/042796: Metodo y dispositivo de navegacion para la planificacion de la ruta en funcion del tiempo. Diferencias: Informa exhaustivamente sobre metodos generales para el uso de informacion en funcion del tiempo en la de planificacion de la ruta, sin definir claramente ciertos detalles como el uso de un soporte magnetico con codificacion y compresion de datos especificos, procedimientos de filtrado de informacion falsa, metodos para seleccionar e incorporar datos en funcion del tiempo con una constante temporal, etcetera. La diferenciacion especifica de nuestro metodo y sistemas es esencial, para que estos puedan ser aplicados a escala mundial (es decir, para el desarrollo de un sistema de "mapa mundial" realista y viable al que contribuyan usuarios de todo el mundo) . Ademas, esta patente tampoco distingue la informacion de la variante basada en el tipo de vehiculo, como lo hacemos nosotros. Estos parametros extras generan problemas de mayor complejidad, que requieren soluciones mas complejas e implementaciones al sistema.

WO2007/044213:Calculo de ruta optima basado en el analisis de cohortes. Diferencias: En general trata sobre la "informacion variable" (informacion atributiva de cohortes o series) , transmitida desde un "sistema de navegacion remota" a un ANP, sin definir el metodo, los procedimientos que aseguren la validez y fiabilidad, los procedimientos de obtencion, seleccion e incorporacion de los datos. Por otro lado, este metodo no envia al sistema central todos los datos sobre la red de carreteras, sino solamente aquellos datos que no esten incluidos en la ruta inicialmente sugerida por el sistema. Para sistemas con diferentes algoritmos de planificacion de ruta, nuestro metodo de grabacion e incorporacion de datos es mas completo.

WO 2008/005187: Inferir informacion sobre la velocidad en las carreteras para una planificacion de ruta acorde con el contexto. Diferencias: En general trata sobre la obtencion de datos sin definir un metodo especifico. Usa un proceso estadistico diferente para la incorporacion de nuevos datos en el procesador central. No define... [Seguir leyendo]

1. Metodologia para la obtencion, procesamiento y distribucion de datos del trafico y planificacion de ruta mas precisa en asistentes de navegacion personal (ANP) , de navegacion GPS.

Dicha metodologia consiste en:

a) una Metodologia de Obtencion de Datos (MOD) , caracterizada por un procedimiento para el registro y procesamiento de datos del trafico dinamicos y parametros del vehiculo por un ANP, que aseguran la validez, autenticidad, verificabilidad y unicidad de los datos recogidos; consistiendo estos en los rasgos temporales distintivos, la velocidad y duracion del viaje a traves de cada segmento, estado de la carretera, condiciones climatologicas, tipo de vehiculo, si se trata de un dia laboral o festivo; proporcionando asi datos de modo que los mapas del ANP tambien se actualizan con las nuevas carreteras no registradas hasta ahora,

b) una Metodologia de Incorporacion de Datos (MID) , caracterizada por:

i. la comprobacion por parte del Sistema Central (SC) de la integridad, autenticidad, unicidad y validez de los datos proporcionados por un ANP, mediante el modulo SID del software del cliente, al SC, y

ii. por la incorporacion estadistica y codificacion de dichos datos en un unico "mapa global", que es un mapa de la base de datos mundial, despues del procesamiento en modo offline de los datos obtenidos por el ANP, realizado por el SC,

c) una Metodologia de Distribucion de Datos (MDD) , caracterizada por: i) la seleccion por parte del modulo del servidor del SDD y la distribucion a los usuarios del ANP de los datos actualizados de mapas desde la unica base de datos del "mapa global" del SC, ii) asegurar la integridad, autenticidad y unicidad de los datos, y iii) la incorporacion de los datos recodificados en el sistema de mapas disponible del ANP.

d) Metodologia de Planificacion de Ruta (MPR) , caracterizada por el uso de datos de mapas actualizados por la MID y seleccionados por la MDD, en combinacion con los mapas convencionales de un ANP, para que el ANP pueda inferir y mejorar las decisiones de planificacion de ruta desde un punto de origen hasta un destino final, con o sin destinos intermedios, basada en:

iii. Datos del trafico dinamicos, es decir, usando la combinacion de informacion: hora del dia, dia de la semana, estacion del aro, tipo de vehiculo, tipo de condiciones climatologicas, estado de la carretera y tipo de dia festivo, o laborable, y

iv. criterios de decision, como puedan ser, menor tiempo empleado en un viaje, menor coste de gasolina, o una combinacion de ambos, especificado por el usuario/conductor,

y siendo dicha metodologia implementada con un Sistema Central (SC) y uno o varios ANP portatiles en modo offline.

Considerando que, la MOD obtiene informacion relativa a la densidad del trafico en cada segmento de la carretera, basandose en la velocidad de cada tipo de vehiculo y en el estado de la carretera en un periodo temporal determinado, datos proporcionados por conductores que viajan en la red de carreteras haciendo uso de su ANP.

Considerando que, la MOD se caracteriza por registrar, para cada segmento de carretera recorrido, una combinacion de informacion consistente en los rasgos temporales distintivos del viaje, la duracion del viaje y longitud del segmento, las condiciones climatologicas o el estado de la carretera, el tipo de vehiculo.

Considerando que, la MOD se caracterizada tambien por registrar los datos en segmentos de carretera no registrados, propiciando asi la creacion de potenciales nuevos mapas.

Considerando que, los "datos de seguimiento", que son los recogidos por la MOD, almacenados en el soporte de almacenamiento del ANP y subidos al servidor, por medio del Paso 1 de la MID, se registran en un soporte de almacenamiento, en el ANP, en un formato codificado y comprimido, para asegurar la privacidad de los datos personales del usuario. Considerando que, junto con los "datos de seguimiento", se registra tambien informacion adicional en el soporte de almacenamiento del ANP, como una "firma digital" y una "resumen del mensaje" de los datos, de modo que se asegure y compruebe la integridad y autenticidad de la informacion registrada en el sistema central, impidiendo o rechazando de este modo multiples entradas por parte de los usuarios.

Considerando que, el MID se refiere a un procedimiento ejecutado en el Sistema Central (SC) , externo al ANP, incorporando los "datos de seguimiento" en los mapas centrales y las bases de datos centrales a traves del modulo del servidor SID.

Considerando que, la MID se caracteriza por la verificacion de la integridad, autenticidad y unicidad de los "datos de seguimiento" recogidos por el SOD. Considerando que, la MID tambien se caracteriza por el almacenamiento temporal en el sistema central, de los datos obtenidos, hasta que estos son verificados comparandolos con otros "datos de seguimiento" subidos por otros usuarios y que corresponden a los mismos segmentos de carretera, antes que dichos datos se consideren validos para su distribucion y esten disponibles para el resto de usuarios del ANP.

Considerando que, la verificacion de los "datos de seguimiento" se ejecuta por medio de un procedimiento estadistico, con una muestra estadistica suficiente, cuyo resultado es la creacion de una base de datos codificada de "mapa global".

Considerando que, la MDD se refiere a un procedimiento ejecutado por el Sistema Central, que distribuye datos actualizados de mapas, producidos por la MID, para los usuarios del ANP.

Considerando que, la MDD se caracteriza por la ejecucion de un procedimiento de distribucion de un subconjunto de datos del "mapa global" que reside en el SC para el usuario del ANP que los solicite, con una combinacion de contribucion por parte del usuario, incluyendo area del mapa y densidad de datos del mapa.

Considerando que, la MDD tambien se caracteriza por los procedimientos que proporcionan, codifican, comprimen, y almacenan los datos del mapa, solicitados por un usuario de ANP, en un fichero, que posteriormente seran puestos a disposicion del usuario que los solicite, asegurando y comprobando asi al ANP la integridad y autenticidad de la informacion registrada asi como previniendo de manera eficaz usos multiples de los mismos datos del mapa por parte de otros usuarios de ANP.

Considerando que, la MDD tambien se caracteriza por la verificacion, mediante un modulo de software del ANP, de la integridad y autenticidad de los datos proporcionados a peticion del usuario por la MDD.

Considerando que, la MDD tambien se caracteriza por la incorporacion de los datos recibidos en el interior del ANP y del uso combinado de los datos dinamicos del mapa en paralelo con los datos estaticos existentes localizados en los ANP de los usuarios, asegurando de este modo un acceso mas rapido y una aprovechamiento optimo de los datos del mapa por parte del algoritmo de planificacion de ruta del ANP.

Considerando que, la MPR se caracteriza por la determinacion, por medio del software adecuado del ANP, de la ruta mas corta desde un punto de partida hasta un destino final, con o sin destinos intermedios, por medio de la combinacion de datos estaticos de mapas existentes que residen en el ANP, con los datos dinamicos almacenados por la MDD.

Considerando que, la MPR tambien se caracteriza por la estimacion del coste de la gasolina en una ruta especifica y la consecuente determinacion, por parte del software del ANP, de la ruta mas efectiva en cuanto a coste, desde un determinado punto de partida hasta el destino final, con o sin destinos intermedios, por medio de la combinacion de datos estaticos de mapas existentes que residen en el ANP, con los datos dinamicos almacenados por la MDD.

Considerando que, la MPR tambien se caracteriza por la capacidad de combinar las modalidades de optimizacion de ruta anteriormente mencionadas, basadas en ciertos criterios, seleccionadas de manera interactiva por el usuario del ANP, tanto para una red de carreteras registrada en el mapa como no registrada en el mismo.

2. Sistema para la obtencion, procesamiento y distribucion de datos del trafico para la computacion de rutas optimas por parte del ANP, consistiendo dicho sistema en:

a) un Sistema de Obtencion de Datos (SOD) , que ejecuta la MOD de la reivindicacion numero 1,

b) un Sistema de Incorporacion de Datos (SID) , que ejecuta la MID de la reivindicacion numero 1,

c) un Sistema de Distribucion de datos (SDD) , que ejecuta la MDD de la reivindicacion numero 1,

d) un Sistema de Planificacion de Ruta (SPR) que ejecuta la MPR de la reclamacion numero 1,

Todos ellos distribuidos parte en un Sistema Central (SC) y parte en un ANP portatil.

Considerando que, el SOD consiste en la combinacion de un dispositivo del ANP, equipado con un receptor GPS, y software, ejecutando la MOD de la reivindicacion numero 1.

Considerando que, el SID consiste en dos subsistemas interactivos, un subsistema "cliente SID", y un subsistema "servidor central SID", y ejecuta la MID de la reivindicacion numero 1.

Considerando que, el anteriormente mencionado subsistema "cliente SID" consiste en un dispositivo ANP, equipado con un receptor GPS, y un software, que ejecuta el procedimiento de la MID de la reivindicacion 1, que corresponde al ANP del cliente.

Considerando que, el anteriormente mencionado subsistema "servidor central SID" consiste en un sistema de procesamiento (SP) , conectado a internet, que ejecuta los procedimientos de la reivindicacion numero 1, correspondiente al SC. Considerando que, el SDD consiste en dos subsistemas interactivos, un subsistema "cliente SDD", y un subsistema "servidor central SDD", y ejecuta la MDD de la reivindicacion numero 1.

Considerando que, el anteriormente mencionado subsistema "cliente SDD" consiste en un dispositivo de ANP, equipado con un receptor GPS, y un software, que ejecuta los procedimientos de la MDD de la reivindicacion numero 1, que corresponde al ANP del cliente.

Considerando que, el anteriormente mencionado subsistema "servidor central SDD" consiste en un sistema procesador, con varios niveles, clusteres de multiprocesamiento, con aceleradores criptograficos y balanceadores de carga, conectado a internet, y que ejecuta los procedimientos de la reivindicacion numero 1, que corresponde al SC.

Considerando que, el SPR consiste en la combinacion de un dispositivo de ANP, equipado con un receptor GPS, y 20 un software, que ejecuta la MPR de la reivindicacion numero 1.