Prognostic based real-time decision making approach for the dynamic and stochastic shortest path problem for electric vehicles

Abstract

La congestión en el tráfico vehicular es cada día más común en las grandes ciudades, lo que conduce a un significativo incremento en los tiempos de viaje. Los sistemas de ruteo trabajan en la búsqueda de rutas óptimas (minimizando tiempos de viaje o costos en general), ya sea para un vehículo o una flota. Por consiguiente, los sistemas de ruteo juegan un rol fundamental para evitar los grandes retrasos causados por la congestión. Dichos sistemas de ruteo deben ser capaces de incorporar toda la información disponible (actual e histórica) en el proceso de toma de decisiones; es decir, decidir una ruta óptima no solo considerando la situación actual, sino también posibles modelos de evolución basados en datos históricos. Típicamente en la literatura de transporte este problema es llamado Problema Dinámico-Estocástico de ruta más corta. Particularmente, es de interés desarrollar sistema de ruteos para vehículos eléctricos; debido a que estos son considerados la alternativa más prometedora al recambio de los vehículos convencionales. Esto conlleva un desafío, ya que en el caso de vehículos eléctricos, la ruta más rápida no necesariamente es la más óptima desde el punto de vista energético; por lo cual ambas variables (tiempo de viaje y consumo energético) deben ponerse en la balanza al momento de realizar la toma de decisiones. En el presente trabajo una estrategia en tiempo real para el Problema Dinámico-Estocástico de ruta más corta para un vehículo eléctrico es presentada. Esta estrategia consiste en un enfoque de toma de decisiones basadas en pronóstico. El algoritmo propuesto funciona por etapas. En la primera etapa, un conjunto de rutas candidatas son seleccionadas mediante una heurística diseñada ad-hoc para este propósito; ésta garantiza una rápida ejecución y diversidad en las soluciones. Luego, cada candidata es evaluada mediante Pronóstico basado en Filtro de Partículas; esto permite realizar una predicción del tiempo de viaje y consumo energético incorporando información actual del tráfico y una caracterización de la evolución futura del tráfico. Finalmente, la ruta óptima es decidida minimizando un funcional de costo que incorpora en el valor esperado del tiempo de viaje y consumo energético. La estrategia de ruteo es analizada mediante un estudio por simulaciones, el cual corrobora que el problema en estudio puede ser resuelto efectivamente mediante la por la estrategia propuesta. Además, los resultados muestran que realizando toma de decisiones en ruta (es decir, actualización de ruta óptima periódicamente) se puede reducir los tiempos de viaje y el consumo energético. En otras palabras, las actualizaciones en ruta permiten una operación más eficiente de los vehículos eléctricos. Adicionalmente, los resultados advierten un trade-off entre el tiempo de viaje y el consumo eléctrico. Ello pues en general, la ruta más rápida conlleva un mayor gasto energético. Por lo último, se resalta la importancia de tener claridad respecto a que es más prioritario al momento de tomar decisión de ruta: tiempo de viaje o consumo de energía, pues aquello definirá la ruta óptima a seguir.