Chris Pendleton anunció en el blog de Bing Maps que lanzaron una actualización importante en su «motor de enrutamiento» de instrucciones de manejo. El nuevo motor de enrutamiento es dos veces más rápido que el anterior y agrega más funciones, como agregar hasta 3 rutas en una solicitud. Anteriormente, Bing Maps usaba un algoritmo de enrutamiento llamado […]
Chris Pendleton Anunciado en el blog de Bing Maps que han publicado una actualización importante en su «motor de enrutamiento» de instrucciones de manejo. El nuevo motor de enrutamiento es dos veces más rápido que el anterior y agrega más funciones, como agregar hasta 3 rutas en una solicitud.
Anteriormente, Bing Maps usaba un algoritmo de enrutamiento llamado algoritmo de Dijkstra. Lo reemplazaron por uno nuevo llamado «Planificación de ruta personalizable» o «CRP» para abreviar. El nuevo algoritmo de planificación de ruta personalizable es «dos veces más rápido» que el algoritmo de Dijkstra, según Chris Pendleton.
Chris también publicó un extracto de cómo funciona este nuevo algoritmo de cálculo de enrutamiento:
Algoritmo básico. Nuestra etapa de preprocesamiento independiente de métricas divide el gráfico en celdas conectadas con un máximo de U (un parámetro de entrada) vértices cada una, con la menor cantidad posible de arcos de límites (arcos con puntos finales en diferentes celdas). La etapa de personalización métrica crea un gráfico H que contiene todos los vértices de los límites (aquellos con al menos un vecino en otra celda) y arcos de límites de G. También contiene una camarilla para cada celda C: para cada par (v; w) de vértices de límites en C, creamos un arco (v; w) cuyo costo es el mismo que el camino más corto (restringido a C) entre v y w (o infinito si w no es accesible desde v). Lo hacemos ejecutando Dijkstra desde cada vértice del límite. Tenga en cuenta que H es una superposición [24]: la distancia entre dos vértices cualesquiera en H es la misma que en G. Finalmente, para realizar una consulta entre syt, ejecutamos una versión bidireccional del algoritmo de Dijkstra en el gráfico que consiste en la unión de H, Cs y Ct. (Aquí Cv denota el subgrafo de G inducido por los vértices en la celda que contiene v.) Como ya se mencionó, esta es la estrategia básica de los métodos basados en separadores. En particular, HiTi [19] utiliza separadores y camarillas basados en bordes para representar cada celda. Desafortunadamente, HiTi no se ha probado en grandes redes de carreteras; los experimentos se limitaron a pequeñas cuadrículas, y la prueba de concepto original no parece haber sido optimizada utilizando técnicas modernas de ingeniería de algoritmos. Nuestra primera mejora sobre HiTi y algoritmos similares es utilizar PUNCH [5] para dividir el gráfico. Desarrollado recientemente para hacer frente a las redes de carreteras, habitualmente encuentra soluciones con la mitad de los bordes de los límites (o menos), en comparación con los separadores de uso general (como METIS [20]) comúnmente utilizado por algoritmos anteriores. Las mejores particiones reducen el tiempo y el espacio de personalización, lo que conduce a consultas más rápidas. Para nuestros experimentos, usamos series relativamente largas de PUNCH, que tomaron aproximadamente una hora. Nuestros resultados no cambiarían mucho si usáramos la versión básica de PUNCH, que es solo un 5% peor pero se ejecuta en solo unos minutos. Usamos el paralelismo: las consultas ejecutan búsquedas hacia adelante y hacia atrás en dos núcleos de CPU, y la personalización usa los cuatro (cada celda se procesa de forma independiente).
Historias relacionadas:
- Bing Maps ajusta su navegación
- Bing Maps The Mall
- Bing Maps amplía las opciones para compartir y editar
- Los nuevos mapas de aeropuertos de Bing tienen como objetivo facilitar los viajes aéreos
- Google Maps vs. Bing Maps: enfrentamiento de planificación de vacaciones de verano
- «Game Changer» de Bing Maps: imágenes aéreas de alta resolución que llegarán a todo Estados Unidos y Europa occidental