Un algoritmo para planificar rutas más rápidas con arcos dependientes del tiempo en redes urbanas

Abstract

Los sistemas de navegación implementados en los dispositivos móviles permiten a los usuarios buscar las rutas más cortas entre pares de puntos. Muchos de los productos comerciales existentes suponen de manera simplificada que el tiempo de viaje para atravesar cada arco de una red de carreteras es fijo, una vez establecida una hora de inicio. Sin embargo, el tiempo real de viaje a lo largo de un tramo de carretera dentro de las ciudades depende de muchos factores que están relacionados con la congestión del tráfico, las condiciones climáticas, posibles incidencias, etc. y, en consecuencia, depende del tiempo. Como se puede mostrar fácilmente, la determinación de los itinerarios más cortos en un contexto dependiente del tiempo puede dar como resultado diferentes rutas óptimas desde el mismo origen según diferentes horarios de salida. Suponiendo la disponibilidad de los datos estimados del tiempo requerido para transitar a lo largo de cada tramo de la red de calles, una vez que se ha fijado previamente la hora de salida, proponemos en este trabajo un algoritmo eficiente de obtención de rutas más rápidas sobre arcos dependientes del tiempo, de tal modo que la suma de los tiempos de conducción se minimice, lo que en paralelo permite mejorar el consumo de combustible y reducir las emisiones contaminantes asociadas. Una evaluación experimental se lleva a cabo para mostrar la efectividad del algoritmo aportado.