Mejoramiento de un algoritmo de ambigüedad espacial topológico
Cargando...
Archivos
Fecha
2022
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
El problema de Map-Matching ocurre cuando se quiere integrar la posición GPS de un
ente, principalmente un vehículo, con la red vial en un mapa digital. La principal motivación
de esta investigación es implementar una mejora a un Algoritmo de Map-Matching Topológico
(TMMA) ya desarrollado en un estudio anterior, aplicando principalmente dos mejoras que
ayuden a obtener resultados en un menor tiempo computacional sin perjudicar la calidad
de estos. El objetivo es poder reducir el trabajo realizado por el algoritmo asegurando un
buen resultado, sin la necesidad de tener que estar variando los parámetros de entrada en
la búsqueda de un mejor rendimiento. Para poder llevar a cabo esta investigación, se realizó
un análisis previo de los datos de entrada para trabajar con información coherente que no
interfiriera en los resultados finales. De esta manera, se seleccionaron ocho set de datos
con mediciones GPS con frecuencia de 30 segundos, provenientes de vehículos de carga que
transitaron por la comuna de Renca, Santiago en febrero de 2015. Dentro de las mejoras
realizadas, se incorporó una obtención previa del radio de búsqueda óptimo que asegura que la
gran mayoría de las mediciones GPS tengan una vía cercana. En segundo lugar, se incluyó un
procedimiento encargado de filtrar las calles que no tienen la misma dirección en la que se iba
moviendo el vehículo. Con estas mejoras desarrolladas, se ejecutaron diferentes experimentos
con los ocho set de datos, que posteriormente se compararon con el algoritmo original respecto
al tiempo de ejecución y calidad de la solución. Donde se logró apreciar que seis de las ocho
rutas se resolvieron en un tiempo menor que con el algoritmo original. Asimismo, siete de las
ocho rutas obtuvieron un porcentaje de acierto igual o mejor. Analizando los resultados con un
mayor detalle, se logró apreciar que las mediciones que tenían una velocidad inferior a 5 km/h
entregaban una dirección (heading) imprecisa. Por lo tanto, se decidió realizar un experimento
que no considerara el filtro de las calles por su dirección, cuando un registro tuviera una
velocidad inferior a 5 km/h. Sin embargo, la los resultados obtenidos con la nueva mejora
mostraron ser despreciable como para considerar esta modificación en el algoritmo. Por otro
lado, se decidió evaluar cómo se comportaría con un set de datos al reducir la frecuencia de los registros a la mitad, quedando con un set de datos registrado cada 1 minuto. En el cual se logró
percibir que el tiempo computacional igualmente se redujo a la mitad, y el comportamiento
del algoritmo mejorado siguió siendo superior al algoritmo original. Por último, se realizó
una evaluación de sensibilidad para las variables de Tolerancia de Velocidad y de Heading,
donde se logró comprobar la importancia que ´estas tienen y como influyen directamente
en el rendimiento del algoritmo. Se espera que para una siguiente investigaci´on se puedan
estandarizar estas variables, tal como se hizo con el radio de búsqueda, el cual se selecciona
previamente de acuerdo al set de datos con el que se trabajará de forma independiente.
Notas
Tesis (Magíster en Ciencias de la Computación)
Palabras clave
Algoritmos Computacionales