Descripción Description
Método y sistema de búsquedas de rutas óptimas empleando la localización de terminales de comunicación móviles Method and search system for optimal routes using the location of mobile communication terminals
Sector técnicoTechnical sector
[1] La invención se encuadra en el sector técnico de las telecomunicaciones, los servicios para dispositivos de comunicación móvil y los servicios de asistencia a la conducción de automóviles u otros vehículos. Concretamente se sitúa en el campo de los servicios basados en la localización de dispositivos de comunicación móvil y de cálculo de rutas óptimas en sistemas de asistencia a la conducción de vehículos. [1] The invention falls within the technical sector of telecommunications, services for mobile communication devices and assistance services for driving cars or other vehicles. Specifically, it is in the field of services based on the location of mobile communication devices and calculation of optimal routes in vehicle assistance systems.
Técnica anterior Prior art
[2] Actualmente los sistemas de localización de terminales móviles se basan en sistemas satélite (GPS) o en técnicas de localización de los terminales que emplean algún tipo de comunicación móvil, por ejemplo: WIFI, GSM, UMTS, etc.. Entre los métodos de localización de terminales móviles actuales cabe citar: CeIl-ID, E-CeIl ID, A-GPS, U- TDOA, E-OTD. Estos sistemas son empleados generalmente por operadores de [2] Currently mobile terminal location systems are based on satellite systems (GPS) or terminal location techniques that employ some type of mobile communication, for example: WIFI, GSM, UMTS, etc. Among the methods The location of current mobile terminals include: CeIl-ID, E-CeIl ID, A-GPS, U-TDOA, E-OTD. These systems are generally used by operators of
telefonía o de comunicación para localizar terminales móviles. En otros sistemas de localización es el propio dispositivo el que realiza el cálculo de la posición identificando señales cuya posición es bien conocida. telephony or communication to locate mobile terminals. In other location systems it is the device itself that calculates the position by identifying signals whose position is well known.
[3] Por otra parte, los métodos de búsqueda de rutas óptimas para la asistencia a la [3] On the other hand, the search methods for optimal routes for assistance to
conducción de vehículos utilizan para su cálculo mapas vectoriales de ejes viarios. Driving vehicles use vector maps of road axes for their calculation.
Dichos ejes se encuentran ponderados incluyendo información sobre el ancho de la vía, la velocidad máxima u otros parámetros empleados en el cálculo de los caminos óptimos. Generalmente los datos de las velocidades medias de los ejes viarios no se actualizan de manera continua ni en línea y se encuentran predefinidos en el dispositivo en el momento de calcular la trayectoria. These axes are weighted including information on the width of the track, the maximum speed or other parameters used in the calculation of the optimal paths. Generally the data of the average speeds of the road axes are not updated continuously or online and are predefined in the device at the time of calculating the trajectory.
[4] Entre las mejoras realizadas en estos sistemas para la actualización del estado de los [4] Among the improvements made in these systems to update the status of
ejes viarios se encuentra el uso de mecanismos de comunicación de incidencias de tráfico. Los sistemas de comunicación de incidencias de tráfico actuales son principalmente RDS y TMC. Ambos sistemas transmiten la información de incidentes puntuales en las vías como accidentes, cortes, obras, etc.. Dichos sistemas no proporcionan información sobre las velocidades medias actualizadas de cada eje viario. road axes is the use of traffic incident communication mechanisms. The current traffic incident communication systems are mainly RDS and TMC. Both systems transmit the information of specific incidents on the roads such as accidents, cuts, works, etc. These systems do not provide information on the updated average speeds of each road axis.
Otra mejora aportada por algunos sistemas destinados al cálculo de rutas óptimas es la recogida de datos estadísticos de los recorridos de los usuarios. Another improvement contributed by some systems destined to the calculation of optimal routes is the collection of statistical data of the routes of the users.
[5] En cualquier caso, ninguno de estos sistemas permite conocer el estado de la red [5] In any case, none of these systems allows to know the state of the network
viaria de forma actualizada, es decir, no disponen de una estimación de las velocidades medias de cada eje viario en un instante dado.up-to-date road, that is, they do not have an estimate of the speeds means of each road axis at a given time.
[6] Los sistemas de búsqueda de rutas óptimas para la asistencia a la conducción de vehículos realizan posteriormente el cálculo del camino óptimo usando las ponderaciones de cada eje viario. Habitualmente se emplea el algoritmo de Dijkstra con este fin. [6] The optimal route search systems for the assistance of driving vehicles subsequently calculate the optimal road using the weights of each road axis. The Dijkstra algorithm is usually used for this purpose.
[7] En resumen, los sistemas de búsqueda de rutas óptimas para vehículos existentes emplean ponderaciones de los ejes viarios predefinidas o de actualización poco frecuente. Los sistemas existentes no incorporan el estado actual del tráfico en los ejes viarios, salvo incidencias puntuales o estadísticas de recorridos, por tanto las rutas calculadas no garantizan ser óptimas en un instante dado ya que no tiene en cuenta el estado de circulación en ese momento de las vías de comunicación empleadas por los vehículos en su recorrido. [7] In summary, the optimal route search systems for existing vehicles use weights of predefined road axes or infrequent updates. Existing systems do not incorporate the current state of traffic on road axes, except for specific incidents or route statistics, therefore the calculated routes do not guarantee to be optimal at any given time since it does not take into account the state of traffic at that time of the communication routes used by the vehicles in its route.
Problema técnico Technical problem
[8] Los métodos de búsqueda de rutas óptimas para la asistencia a la conducción de vehículos utilizan para su cálculo mapas vectoriales de ejes viarios. Dichos ejes se encuentran ponderados incluyendo información sobre el ancho de la vía, la velocidad máxima u otros parámetros útiles para el cálculo de los caminos óptimos. Estos datos no tienen en cuenta el estado actualizado del tráfico en los ejes viarios. La información de las ponderaciones de los ejes no se actualizan de manera continua ni en línea y no reflejan el estado presente del tráfico en los ejes viarios. Las rutas calculadas no garantizan ser óptimas. [8] The methods of searching for optimal routes for vehicle driving assistance use vector maps of road axes for their calculation. These axes are weighted including information on the width of the track, the maximum speed or other useful parameters for the calculation of the optimal paths. This data does not take into account the updated state of traffic on road axes. The information of the axle weights are not updated continuously or online and do not reflect the current state of traffic on the road axes. The calculated routes do not guarantee to be optimal.
Solución técnica Technical solution
[9] Para solventar el problema de la actualización de la información de tráfico en cada eje del mapa, la presente invención se centra en conseguir información actualizada y precisa del estado del tráfico en cada eje viario para incorporarlo al sistema de cálculo de rutas óptimas. [9] To solve the problem of updating traffic information on each axis of the map, the present invention focuses on obtaining updated and accurate information on the state of traffic on each road axis to incorporate it into the optimal route calculation system.
[10] La información del tráfico de las vías también puede utilizarse para recalcular rutas previamente establecidas. Esto puede ser especialmente útil en caso de que el tráfico, que pueda afectarnos en nuestro recorrido, cambie de manera brusca. [10] Road traffic information can also be used to recalculate previously established routes. This can be especially useful in case the traffic, which may affect us on our route, changes abruptly.
[11] Esta invención se refiere al uso de la información de localización de terminales [11] This invention relates to the use of terminal location information
móviles u otros dispositivos comunicación para la determinación actualizada del estado del tráfico en los ejes viarios, su posterior uso en el cálculo de rutas óptimas u otros estudios derivados de la explotación de la información actualizada del tráfico que ha sido obtenida por este método. mobiles or other communication devices for the updated determination of traffic status on road axes, their subsequent use in the calculation of optimal routes or other studies derived from the exploitation of updated traffic information that has been obtained by this method.
[12] La presente invención permite establecer las ponderaciones actualizadas de los ejes viarios basadas en el estado del tráfico actual. Posteriormente se emplea un algoritmo para el cálculo de la ruta óptima, habitualmente se trata del algoritmo de Dijkstra, pero puede utilizarse cualquier otro ideado para este fin.[12] The present invention makes it possible to establish the updated weights of the road axes based on the current traffic status. Subsequently an algorithm is used to calculate the optimal route, usually it is the Dijkstra algorithm, but Any other idea can be used for this purpose.
[13] El sistema de búsqueda de rutas óptimas para vehículos basado en el estado del[13] The optimal route search system for vehicles based on the state of the
tráfico admite diversas estructuras lógicas de sus elementos. El modo de operación del sistema depende de la implementación hardware y software particular que se realice. Algunos de estos componentes pueden encontrarse en un sistema completamente central o distribuido entre el propio dispositivo de comunicación del usuario y otros sistemas. Traffic supports various logical structures of its elements. The mode of operation of the system depends on the particular hardware and software implementation performed. Some of these components can be found in a completely central system or distributed between the user's own communication device and other systems.
Efectos ventajosos Advantageous effects
[14] El sistema de búsqueda de rutas óptimas por localización de terminales de comunicación móvil tiene en cuenta el tráfico de vehículos y permite establecer la mejor ruta según la situación actual de tráfico. Pueden beneficiarse del ahorro de tiempo y combustible todos los conductores de vehículos automóviles así como servicios de emergencia que emplee este tipo de transporte. También las empresas de logística y transportes por carretera se beneficiarían de la optimización de sus rutas así como de una mejor predicción de los tiempos de sus envíos. [14] The optimal route search system by location of mobile communication terminals takes into account vehicle traffic and allows the best route to be established according to the current traffic situation. All motor vehicle drivers and emergency services that use this type of transportation can benefit from time and fuel savings. Logistics and road transport companies would also benefit from the optimization of their routes as well as a better prediction of their shipping times.
[15] La información obtenida sobre el tráfico actual en una red viaria tiene otras muchas aplicaciones a parte del cálculo de rutas óptimas. La explotación de los datos actualizados de tráfico en la red viaria obtenidos por el método de localización de terminales u otros dispositivos de comunicación móvil es útil para: [15] The information obtained on current traffic on a road network has many other applications besides the calculation of optimal routes. The exploitation of the updated traffic data on the road network obtained by the method of locating terminals or other mobile communication devices is useful for:
[16] 1. La realización de estudios sobre el uso de infraestructuras viarias destinados a su diseño, mantenimiento y ampliación. [16] 1. Carrying out studies on the use of road infrastructure for its design, maintenance and expansion.
2. La estimación precisa de tiempos de recorrido y cálculo de rutas óptimas aplicados al transporte público, servicios de emergencias, servicios de logística y transporte de mercancías. 2. The precise estimation of travel times and calculation of optimal routes applied to public transport, emergency services, logistics services and freight transport.
3. La realización de estudios sobre el ahorro energético y desarrollo sostenible basado en la optimización del uso de vehículos automóviles. 3. The realization of studies on energy saving and sustainable development based on the optimization of the use of motor vehicles.
4. El trazado y actualización de cartografía de las zonas transitadas por los dispositivos móviles de comunicación. 4. The mapping and updating of cartography of the areas traveled by mobile communication devices.
Descripción breve de las figuras Brief description of the figures
[17] [17]
Mejor manera de realizar la invención Best way to realize the invention
[18] A continuación se describe un ejemplo de realización del sistema de búsqueda de rutas óptimas para terminales GSM y los elementos necesarios del sistema de localización basados en tecnología U-TDOA. [18] An example of the realization of the optimal route search system for GSM terminals and the necessary elements of the location system based on U-TDOA technology is described below.
[19] Los usuarios de terminales móviles son localizados por un sistema U-TDOA. Dicho sistema de localización consistente en distintas estaciones base con un mecanismo muy preciso de medición de las diferencias en los tiempos de llegada de la señal GSM del usuario. El sistema de localización se compone de estas estaciones base, a las que llamamos LMU, y también de un sistema central de cálculo de las posiciones llamado SMLC. Dicho sistema calcula la localización del usuario con una precisión aproximada de 50 metros.[19] Mobile terminal users are located by a U-TDOA system. Said location system consisting of different base stations with a very precise mechanism for measuring the differences in the arrival times of the GSM signal of the Username. The location system consists of these base stations, which we call LMU, and also a central position calculation system called SMLC. This system calculates the user's location with an accuracy of approximately 50 meters.
[20] La información recibida de forma periódica (aproximadamente cada 20 segundos en el sistema GSM) permite calcular la velocidad media aproximada en ese intervalo de tiempo del terminal móvil y asignarla a la ponderación de los ejes viarios recorridos. En cada intervalo de tiempo, las posiciones recibidas son convenientemente corregidas; se realiza la eliminación de valores atípicos y se emplean otros métodos estadísticos que tienen en cuenta los datos de localización del mismo terminal en el mismo recorrido. [20] The information received periodically (approximately every 20 seconds in the GSM system) makes it possible to calculate the approximate average speed in that time interval of the mobile terminal and assign it to the weighting of the traveled road axes. In each time interval, the positions received are conveniently corrected; the elimination of outliers is carried out and other statistical methods that take into account the location data of the same terminal in the same route are used.
[21] Las velocidades medias son tratadas estadísticamente y previamente se ha ano- nimizando la identidad del propietario del terminal móvil que ha generado dicha información. [21] The average speeds are treated statistically and the identity of the owner of the mobile terminal that generated the information has been previously analyzed.
[22] Como resultado se obtienen las velocidades medias de los ejes viarios por los que transitan los usuarios de la operadora en cada momento. Esto supone un amplio porcentaje de los ejes viarios de una ciudad y una gran cantidad de información de las principales vías a interurbanas. La información de las vías que no están en uso puede suplirse por información estadística histórica o pueden emplearse las velocidades nominales predefinidas de la red viaria. [22] As a result, the average speeds of the road axes through which the operator's users travel at each moment are obtained. This represents a large percentage of the road axes of a city and a large amount of information on the main interurban routes. The information of the routes that are not in use can be supplied by historical statistical information or the predefined nominal speeds of the road network can be used.
[23] Con la base de información de las velocidades medias de los ejes viarios se presta el servicio de cálculo de rutas óptimas a los usuarios de terminales móviles. En caso de que los usuarios dispongan de algún tipo de sistema de asistencia a la conducción, dicho sistema solicita el cálculo de la ruta a nuestro servicio e incorpora la respuesta en su sistema de visualización de la cartografía y de la ruta. Existe también la posibilidad de que el terminal reciba el estado de tráfico de la red viaria y sea el propio dispositivo quien realice el cálculo de la ruta óptima. [23] With the information base of the average speeds of the road axes, the optimal route calculation service is provided to mobile terminal users. In the event that users have some type of driving assistance system, this system requests the calculation of the route to our service and incorporates the response in its system of visualization of the cartography and the route. There is also the possibility that the terminal receives the traffic status of the road network and it is the device itself that calculates the optimal route.
[24] La información estadística sobre el tráfico almacenada admite otras aplicaciones industriales descritas en este documento como: [24] Statistical information on stored traffic supports other industrial applications described in this document as:
[25] 1. La realización de estudios sobre el uso de infraestructuras viarias destinados a su diseño, mantenimiento y ampliación. [25] 1. Carrying out studies on the use of road infrastructure for its design, maintenance and expansion.
2. La estimación precisa de tiempos de recorrido y cálculo de rutas óptimas aplicados al transporte público, servicios de emergencias, servicios de transporte de mercancías y logística. 2. The precise estimation of travel times and calculation of optimal routes applied to public transport, emergency services, freight transport services and logistics.
3. La realización de estudios sobre el ahorro energético y desarrollo sostenible basado en la optimización de rutas de vehículos. 3. The realization of studies on energy saving and sustainable development based on the optimization of vehicle routes.
4. El trazado y actualización de cartografía de las zonas transitadas por los dispositivos móviles de comunicación. Modo de realizar la invención4. The mapping and updating of cartography of the areas traveled by mobile communication devices. How to carry out the invention
[26] A continuación se presenta un ejemplo de operación del sistema para clarificar el funcionamiento del mismo. El servicio propuesto sería prestado por un operador de telefonía móvil (por ejemplo, un operador de telefonía GSM) que emplee un sistema de localización de terminales móviles (por ejemplo, U-TDOA): [26] Below is an example of the operation of the system to clarify its operation. The proposed service would be provided by a mobile telephone operator (for example, a GSM telephone operator) that uses a mobile terminal location system (for example, U-TDOA):
[27] 1. El operador actualiza la información de tráfico de los ejes viarios: [27] 1. The operator updates the traffic information of the road axes:
1. Se realiza el almacenamiento de las posiciones de los terminales móviles localizados después de cuadrar los tiempos de recepción, intensidad y dirección de la señal del dispositivo móvil (localización por diferencia de tiempos de llegada U-TODA). Dicha información puede ser anonimizada (tratamiento de la información para impedir la identificación del individuo propietario del terminal o dispositivo) para proteger la privacidad de los datos de los ciudadanos en caso de que la legislación aplicable así lo requiera. En cualquier caso, el sistema realiza un uso estadístico de la información de localización de los usuarios. 1. The storage of the positions of the mobile terminals located after setting the reception times, intensity and direction of the signal of the mobile device (location by difference of arrival times U-TODA) is performed. Such information can be anonymized (information processing to prevent the identification of the individual owner of the terminal or device) to protect the privacy of citizens' data in case the applicable legislation so requires. In any case, the system makes statistical use of user location information.
2. Proyección y corrección de las posiciones recibidas sobre los ejes viarios cercanos. La corrección se realiza por medio de la proyección simple sobre los ejes cercanos. Dicha información permite definir uno o varios segmentos sobre los ejes viarios colindantes en los que el terminal o dispositivo puede encontrarse con cierta probabilidad. La estimación de estos segmentos se mejora empleando el propio algoritmo de Dijkstra sobre el conjunto de datos disponibles de la ruta del mismo terminal o dispositivo. 2. Projection and correction of the positions received on the nearby road axes. The correction is made by simple projection on the nearby axes. This information allows to define one or several segments on the adjacent road axes in which the terminal or device can be with a certain probability. The estimation of these segments is improved by using Dijkstra's own algorithm on the set of data available from the route of the same terminal or device.
3. Una vez tenemos la información registrada se emplean distintos métodos estadísticos para descartar valores atípicos: 3. Once we have the information registered, different statistical methods are used to discard outliers:
1. Eliminación de errores del sistema de localización 1. Elimination of location system errors
2. Eliminación de valores de posiciones de terminales pertenecientes a peatones, personas que no respeten los límites de velocidad de la vía, etc. 2. Elimination of values of terminal positions belonging to pedestrians, people who do not respect the speed limits of the road, etc.
La información depurada sirve para establecer los valores de velocidades medias actuales en los ejes viarios sobre los que circulan usuarios de la red de telefonía móvil en ese momento.The purified information is used to establish the current average speed values on the road axes on which users of the mobile telephone network circulate at that time.
2. Se incorpora la información del tráfico actual de los ejes viarios al sistema de cálculo de rutas óptimas. El cálculo de las rutas óptimas puede ser realizado por el operador, valiéndose de la información anterior, o por el propio dis- positivo móvil. Cuando el cálculo de las rutas óptimas sea realizado por el dispositivo móvil, el sistema tendrá la opción de enviar al terminal la información completa del estado de tráfico de todos los ejes viarios o sólo los cambios desde su última actualización.2. The current traffic information of the road axes is incorporated into the optimal route calculation system. The calculation of the optimal routes can be performed by the operator, using the above information, or by the own positive mobile. When the calculation of the optimal routes is carried out by the mobile device, the system will have the option of sending the complete traffic status information of all the road axes to the terminal or only the changes since its last update.
3. El programa de asistencia a la conducción de vehículos visualiza la ruta y 3. The vehicle driving assistance program displays the route and
comprueba periódicamente que la ruta sigue siendo efectivamente la óptima. Periodically check that the route is still the optimum.
Aplicabilidad industrialIndustrial applicability
[28] Entre las principales aplicaciones industriales figuran: [28] Among the main industrial applications are:
1. Sistemas de cálculo de rutas óptimas basadas en el tráfico actual en la red 1. Optimal route calculation systems based on current network traffic
viaria road
2. Realización de estudios sobre el uso de las infraestructuras viarias destinados a su diseño, mantenimiento y ampliación. 2. Studies on the use of road infrastructure for its design, maintenance and expansion.
3. Estimación precisa de tiempos de recorrido y cálculo de rutas óptimas 3. Accurate estimation of travel times and calculation of optimal routes
aplicados al transporte público, servicios de emergencias, servicios de transporte de mercancías y logística. applied to public transport, emergency services, freight transport services and logistics.
4. Realización de estudios sobre el ahorro energético y desarrollo sostenible 4. Conducting studies on energy saving and sustainable development
basado en la optimización de rutas de vehículos automóviles. based on the optimization of motor vehicle routes.
5. El trazado y actualización de cartografía de las zonas transitadas por los dispositivos móviles de comunicación. 5. The mapping and updating of cartography of the areas traveled by mobile communication devices.
Lista de secuencias Sequence list
[29] [29]