Me encanta esta pregunta, porque es un tema poco abierto y he trabajado en la implementación de algoritmos de ETA crowdsourced para rutas dadas en algunos de mis proyectos anteriores.
Tengo respuestas a otras dos versiones de esta pregunta aquí:
- ¿Qué algoritmos usan los servicios de mapas para encontrar direcciones?
- ¿Qué algoritmos utiliza Google Maps para que la búsqueda de rutas sea tan rápida?
Como señaló Yevgeni, este no es un tema público y las soluciones de código abierto no satisfacen las expectativas la mayor parte del tiempo. Mucha gente le diría en el campo de los sistemas de geolocalización y las soluciones relacionadas con algoritmos Graph, que el conjunto de algoritmos utilizados no está oculto. Sin embargo, las soluciones exactas tampoco son de conocimiento común.
- Cómo resolver estos problemas matemáticos a continuación
- Cómo hacer un proyecto de chatbot
- ¿Cuáles son los famosos algoritmos de Java para principiantes?
- Dado un gran diccionario de N frases cortas (1 o 2 términos) y una gran porción de texto, ¿puedo encontrar de manera eficiente las coincidencias para esas frases en el texto en tiempo sub-N, mientras perdono * los pequeños errores?
- ¿Por qué la notación O grande no se parece más a O (c) y O (cn) en lugar de a O (1) y O (n), esto último no tiene sentido?
- La diferencia es el uso del cliente y la entrega de una solución para ese resultado requerido.
Waze está más enfocado en llevarlo al Punto B en un tiempo determinado, lo que significa que el cambio de ruta en cada punto final de un borde es menos problemático y es por eso que a algunos usuarios les encanta. - Mientras que Google Maps, se enfoca en darle al usuario una ETA, y usar esta ruta con la ETA dada es el objetivo, en lugar de cambiar de ruta al Punto B con tanta frecuencia como lo haría Waze.
- En cuanto a la congestión para Waze, los pesos en los bordes se equilibrarán mientras se vuelve a calcular la ruta en el camino.
- De la misma forma en que Google Maps podría confiar en los teléfonos Android u otros usuarios de mapas, una de las fortalezas de Waze es la red que tiene también. El uso de esas transmisiones de datos en vivo puede evitar causar difusión de gráficos.
Para encontrar un documento específico, no creo que haya tantos o habrá una receta específica para responder al mejor algoritmo de enrutamiento. Debido a mi experiencia laboral personal y quizás a un conocimiento limitado, la mayoría de los algoritmos gráficos pueden tener implementaciones híbridas para obtener mejores resultados.
Como:
- Usando un algoritmo para encontrar el límite superior, mientras que otro para calcular el límite inferior, y dar un resultado equilibrado.
- Otros ajustes, como el almacenamiento en caché de los pesos de los bordes, para actualizaciones más rápidas al buscar una ruta.
- El aprendizaje automático es un gran factor seguro, pero no es la respuesta definitiva para dar una ruta y hacer una ETA exacta para el destino requerido.
- Usar factores como: Eventos que suceden y rutas principalmente tomadas.
- El clima como otro factor.
- Patrones en el hábito de conducir en toda la ciudad
- Todo lo anterior puede dar una muy buena oportunidad para sacar conclusiones para una ruta.
Puede usar algunos simuladores básicos para explorar las implementaciones posteriores de Dijkstra VS los otros algoritmos para este tema:
Pathfinding JS es una biblioteca de código abierto para soluciones de juegos basados en Grid, pero los mapas también pueden considerarse una grilla para simplificar y sacar algunas conclusiones sobre cómo un algoritmo específico puede hacer un mejor trabajo en un escenario:
PathFinding.js
Como estaba hablando de Waze haciendo muchos más recálculos utilizando los pesos de las actualizaciones, aquí hay un hilo que menciona cómo también se deciden las salidas y giros de la autopista:
[Actualización de página] Cómo Waze determina las maniobras de giro / mantenimiento / salida
Consulte el Wiki de Waze, son más abiertos sobre algunos de sus enfoques:
Página Wiki de Waze
El uso del mapa es lo más relevante para hacer una mejor implementación de un algoritmo gráfico. Por ejemplo, la siguiente publicación del equipo de Ingeniería de Uber dijo que Google Maps ETA no es tan preciso como quisieron muchas veces:
fuente: Cuando las ETA de Google fallan …
En realidad, funciona bien, pero no con el mismo resultado que el producto Uber lo quiere.
La joya aquí es que se puede lograr un mejor resultado utilizando un Dijkstra o una colección de algoritmos gráficos en el camino, dependiendo de la necesidad del cliente. La maldición es que puede salir mal de muchas maneras, es por eso que comenzar con un camino simple y directo más corto puede funcionar realmente bien. Luego divergen a otras implementaciones híbridas, incluidos modelos predictivos para algunas partes de los algoritmos.
Si está interesado en este tema, hay algunas buenas lecturas en línea:
- Journal of Graph Algorithms and Applications
- IEEE Xplore PDF de texto completo: (Graph Algo in Vision)
- Optimización de algoritmos gráficos en sistemas similares a Pregel (Semih Salihoglu y Jennifer Widom @ Stanford)
- Algoritmos de gráficos paralelos (membresía ACM requerida)
Además de todos estos factores mencionados, Google todavía tiene una ventaja sobre muchas otras soluciones debido a las tecnologías adecuadas utilizadas. Usar algo como BigQuery, debajo, usar “Dremel, que puede escanear 35 mil millones de filas sin un índice en decenas de segundos “ es absolutamente un gran impulso para la fuerza bruta de algunos resultados si todo lo demás falla.
