Los algoritmos de mapeo utilizados para la navegación a menudo se basan en el algoritmo de Dijkstra , una solución de libro de texto fundamental para encontrar las rutas más cortas en los gráficos. El algoritmo de Dijkstra es simple y elegante: en lugar de considerar todas las rutas posibles (un número exponencial), mejora iterativamente una solución inicial y funciona en tiempo polinomial . El algoritmo original y sus extensiones prácticas (como el algoritmo A * ) se utilizan millones de veces al día para enrutar vehículos en la red mundial de carreteras. Sin embargo, debido al hecho de que la mayoría de los vehículos funcionan con gasolina, estos algoritmos ignoran las consideraciones de reabastecimiento de combustible porque a) las estaciones de servicio generalmente están disponibles en todas partes al costo de un pequeño desvío, yb) el tiempo necesario para reabastecerse de combustible suele ser de solo unos minutos y es insignificante en comparación con el tiempo total de viaje.
Esta situación es diferente para los vehículos eléctricos (EV). Primero, las estaciones de carga de vehículos eléctricos no están disponibles con tanta frecuencia como las estaciones de servicio, lo que puede causar ansiedad por el alcance , el temor de que el automóvil se quede sin energía antes de llegar a una estación de carga. Esta preocupación es tan común que se considera una de las barreras para la adopción generalizada de vehículos eléctricos. En segundo lugar, cargar la batería de un vehículo eléctrico es una tarea que requiere más decisiones, porque el tiempo de carga puede ser una fracción significativa del tiempo total de viaje y puede variar ampliamente según la estación, el modelo de vehículo y el nivel de batería. Además, el tiempo de carga no es lineal; por ejemplo, se tarda más en cargar una batería del 90% al 100% que del 20% al 30%.
 |
| El EV solo puede recorrer una distancia hasta el rango ilustrado antes de tener que recargarse. Diferentes carreteras y diferentes estaciones tienen diferentes costos de tiempo. El objetivo es optimizar el tiempo total de viaje. |
Hoy, presentamos un nuevo enfoque para el enrutamiento de vehículos eléctricos integrado en la última versión de Google Maps integrado en su automóvil para vehículos eléctricos participantes que reduce la ansiedad de alcance al integrar estaciones de recarga en la ruta de navegación. Según el nivel de la batería y el destino, Maps recomendará las paradas de carga y los niveles de carga correspondientes que minimizarán la duración total del viaje. Para lograr esto, diseñamos una solución altamente escalable para recomendar rutas eficientes a través de estaciones de carga, que optimiza la suma del tiempo de conducción y el tiempo de carga juntos.
 |
| La ruta más rápida de Berlín a París para un automóvil a gas se muestra en la figura superior. La figura del medio muestra la ruta óptima para un EV de 400 km de autonomía (tiempo de viaje indicado - tiempo de carga excluido), donde los círculos blancos más grandes a lo largo de la ruta indican paradas de carga. La figura inferior muestra la ruta óptima para un EV de 200 km de autonomía. |
Enrutamiento a través de estaciones de carga
Una limitación fundamental en la selección de la ruta es que la distancia entre las paradas de recarga no puede ser mayor que la que el vehículo puede alcanzar con una carga completa. En consecuencia, el modelo de selección de ruta enfatiza el gráfico de estaciones de carga, en contraposición al gráfico de tramos de carretera de la red de carreteras, donde cada estación de carga es un nodo y cada viaje entre estaciones de carga es un borde. Teniendo en cuenta las diversas características de cada EV (como el peso, el nivel máximo de batería, el tipo de enchufe, etc.), el algoritmo identifica cuáles de los bordes son factibles para el EV en cuestión y cuáles no. Una vez que llega la solicitud de enrutamiento, el enrutamiento de Maps EV aumenta el gráfico factible con dos nuevos nodos, el origen y el destino, y con múltiples bordes nuevos (factibles) que describen los viajes potenciales desde el origen a sus estaciones de carga cercanas y al destino. de cada una de sus estaciones de carga cercanas.
El enrutamiento utilizando el algoritmo de Dijkstra o A * en este gráfico es suficiente para brindar una solución factible que optimice el tiempo de viaje para los conductores a los que no les importa en absoluto el tiempo de carga (es decir, los conductores que siempre cargan completamente sus baterías en cada estación de carga). ). Sin embargo, estos algoritmos no son suficientes para tener en cuenta los tiempos de carga. En este caso, el algoritmo construye un nuevo gráfico replicando cada nodo de la estación de carga varias veces. La mitad de las copias corresponden a ingresar a la estación con una batería parcialmente cargada, con una carga, x , que va del 0% al 100%. La otra mitad corresponde a salir de la estación con una carga fraccionada, y (nuevamente de 0% -100%). Agregamos un borde desde el nodo de entrada en la carga x al nodo de salida en la carga y (restringido por y> x), con un tiempo de carga correspondiente para pasar de xay. Cuando el viaje de la estación A a la estación B gasta una fracción ( z ) de la carga de la batería, introducimos un borde entre cada nodo de salida de la estación A al nodo de entrada correspondiente de la estación B (con carga x - z ). Después de realizar esta transformación, usar Dijkstra o A * recupera la solución.
 |
| Un ejemplo de nuestra replicación de nodo / borde. En este caso, el algoritmo opta por pasar por la primera estación sin cargar y carga en la segunda estación del 20% al 80% de la batería. |
Esparsificación de gráficos
Para realizar las operaciones anteriores mientras aborda la ansiedad de alcance con confianza, el algoritmo debe calcular el consumo de batería de cada viaje entre estaciones con buena precisión. Por esta razón, Maps mantiene información detallada sobre las características de la carretera a lo largo del viaje entre dos estaciones (p. Ej., La longitud, la elevación y la pendiente, para cada segmento del viaje), teniendo en cuenta las propiedades de cada tipo de vehículo eléctrico.
Debido al volumen de información requerido para cada segmento, mantener una gran cantidad de bordes puede convertirse en una tarea que requiere mucha memoria. Si bien esto no es un problema para las áreas donde las estaciones de carga de vehículos eléctricos son escasas, existen lugares en el mundo (como el norte de Europa) donde la densidad de estaciones es muy alta. En tales ubicaciones, agregar una ventaja por cada par de estaciones entre las cuales puede viajar un vehículo eléctrico aumenta rápidamente a miles de millones de posibles bordes.
 |
| La figura de la izquierda ilustra la alta densidad de estaciones de carga en el norte de Europa. Los diferentes colores corresponden a diferentes tipos de enchufes. La figura de la derecha ilustra por qué el gráfico de enrutamiento aumenta de tamaño muy rápidamente a medida que aumenta la densidad de estaciones. Cuando hay muchas estaciones dentro del alcance entre sí, el gráfico de enrutamiento inducido es un gráfico completo que almacena información detallada para cada borde. |
Sin embargo, esta alta densidad implica que un viaje entre dos estaciones que están relativamente alejadas sin duda pasará por muchas otras estaciones. En este caso, mantener información sobre el borde largo es redundante, lo que hace posible simplemente agregar los bordes más pequeños ( llaves ) en el gráfico, lo que resulta en gráficos más dispersos y más factibles desde el punto de vista computacional.
El algoritmo de construcción de llave inglesa es una generalización directa de la codiciosa llave geométrica . Los viajes entre estaciones de carga se ordenan de más rápido a más lento y se procesan en ese orden. Por cada viaje entre los puntos A y B, los examina si el algoritmo subtrips más pequeños ya incluidas en la llave subsumen el viaje directo. Para ello, compara el tiempo de viaje y el consumo de batería que se puede lograr utilizando subtrips que ya están en la llave, con las mismas cantidades para la ruta directa a - b. Si se encuentran dentro de un pequeño umbral de error, el viaje directo de a a b no se agrega a la llave, de lo contrario, sí. La aplicación de este algoritmo de dispersión tiene un impacto notable y permite que el gráfico se sirva de manera eficiente para responder a las solicitudes de enrutamiento de los usuarios.
 |
| A la izquierda está la red de carreteras original (estaciones de vehículos eléctricos en rojo claro). El gráfico de la estación en el medio tiene bordes para todos los viajes factibles entre estaciones. El gráfico disperso de la derecha mantiene las distancias con muchos menos bordes. |
Resumen
En este trabajo, diseñamos una solución escalable para enrutar vehículos eléctricos en viajes largos para incluir acceso a estaciones de carga mediante el uso de dispersión de gráficos y un encuadre novedoso de algoritmos de enrutamiento estándar. ¡Estamos entusiasmados de poner ideas y técnicas algorítmicas en manos de los usuarios de Maps y esperamos ofrecer rutas sin estrés para los conductores de vehículos eléctricos de todo el mundo!
Agradecimientos
Agradecemos a nuestros colaboradores Dixie Wang, Xin Wei Chow, Navin Gunatillaka, Stephen Broadfoot, Alex Donaldson e Ivan Kuznetsov.
