Deje la siguiente parte de un gráfico:
Cuando uso la función shortest_path entre los puntos A y B, obtuve la ruta azul. ¿Por qué pasó esto?
postgis
postgresql
pgrouting
José Alejandro
fuente
fuente
Respuestas:
Así es como se comporta shortest_path (algoritmo de Dijkstra) en pgRouting. Si hay dos bordes con el mismo origen y destino, se utiliza uno aleatorio (para ser precisos: el primero, que sale de la base de datos). No conozco ninguna solución para eso, pero hay algunas soluciones.
Si es posible, debe dividir uno de esos bordes en dos. No lo he probado, pero debería corregir ese comportamiento.
Otra solución para el caso, cuando no puede modificar su conjunto de datos. Agregue el campo 'short_alternative' a su tabla. Consulta de muestra, modifíquela según sus necesidades. Espero que explique la idea:
Ahora, el borde '0.098' contendrá la identificación del borde '0.011'. Todos los demás bordes tendrán un valor nulo en el campo más corto_alternativo. Después de haber realizado la consulta shortest_path, verifique el conjunto de datos devuelto; si alguna de las filas tiene un campo más corto_alternativo, cámbielo.
fuente
El problema ya se ha descrito en la respuesta anterior. Es un problema de algoritmos de ruta más corta "basados en vértices", que solo se preocupan por el origen y el destino.
Hay un ticket en el rastreador de problemas y una posible solución para cambiar la implementación del algoritmo: https://github.com/pgRouting/pgrouting/issues/34 (Sería bueno si alguien pudiera probar esto y enviar una solicitud de extracción; - )
Otra posibilidad es dividir los "enlaces de carreteras paralelas" como se mencionó anteriormente. O puede utilizar el algoritmo Shooting Star, que se enruta de borde a borde para que "sepa" sobre ambos enlaces de carretera.
O puede intentar ordenar la red de carreteras por costo y luego seleccionar solo combinaciones distintas de origen y destino:
Esto supone que busca la ruta menos costosa. De lo contrario, debes hacerlo
ORDER BY ... DESC
.Debe probar si esto afecta el rendimiento.
fuente
De hecho, he creado un parche para pgRouting, que soluciona el problema: https://github.com/pgRouting/pgrouting/issues/78
fuente