La verdad es que la mayoría de las personas utilizan una variación personalizada del algoritmo A * . Verá esto en la mayoría de los "grandes" (no puedo decir quiénes son en un foro público, pero puedo decirle que probablemente use uno de ellos, garantizado), donde la modificación de las heurísticas es Muy dependiente de los conjuntos de datos que utilizan.
Ya mencionó pgrouting , lo cual consideraría una opción "tradicional". Es bueno para hacer algoritmos de enrutamiento simples y para la mayoría de los problemas. También es fácil de usar y utiliza una base de datos tradicional en su backend.
Sin embargo, realmente depende de la escala y el tipo de problema que intenta resolver y el enrutamiento es un problema graph .
Una vez más, los "chicos grandes" suelen tener una gran cantidad de datos asociados con su gráfico (por ejemplo, datos de tráfico, rutas de autobuses, rutas de senderismo) que afectan el algoritmo de enrutamiento. Estos se conocen como planificadores de viaje multimodales (donde también tiene la opción de planificar "modos", sin caminos para bicicletas, solo transporte público, ese tipo de cosas). Puede pensar que la planificación del viaje también se convierte en un tema sensible al tiempo (es decir, si retrocede un poco atrás, podrá tomar el metro que lo lleva a su destino adelante mucho más rápido que si intentara navegar los bordes hacia adelante utilizando el costo más bajo).
Los "chicos grandes" no almacenan sus datos en una base de datos tradicional per se, utilizan gráficos precalculados (¡bienvenidos clusters de hadoop / mapreduce!). Como puedes imaginar, estos gráficos se vuelven realmente grandes, por lo que saber cómo conectar los bordes de los gráficos adyacentes puede ser un desafío.
De todos modos, le recomendaría que vea algunos proyectos de gráficos de enrutamiento multimodales:
Graphserver viene a la mente. No hay mucha documentación, pero sí mucha codicia pura (AFAIK, creo que MapQuest utiliza una variación de este proyecto para algunos de sus productos de enrutamiento).
Otra opción sería la OpenTripPlanner que tiene detrás mucha gente inteligente (incluidas las personas de graphserver).