¿Existe algún enfoque mejor para encontrar el camino más corto dentro de una red de tráfico (vehicular)?

Estimados compañeros programadores,

Estamos desarrollando software que simula el tráfico vehicular. Parte del proceso llamado "asignación" se refiere a la asignación de vehículos a sus rutas y tiene que usar algún tipo de algoritmo de búsqueda de ruta más corta.

Tradicionalmente, las personas hacen esto con Dijkstra, y cierta literatura científica parece indicar que A * y otras alternativas no ofrecen ninguna mejora significativa, tal vez debido a la naturaleza del gráfico.

Por lo tanto, también estamos usando Dijkstra. Surgió un pequeño problema porque, si trata los enlaces de tráfico (tramos de carreteras entre intersecciones) como bordes e intersecciones como nodos, no puede obtener un gráfico unidireccional clásico: al acercarse a una intersección, el lugar donde puede girar con frecuencia depende de de dónde vienes, mientras que en un gráfico tradicional puedes tomar cualquier ventaja de un nodo.

Resolvimos este problema con bastante facilidad al representar un par de enlace-intersección (llámelo "listón") como un nodo. Dado que necesitaría atravesar un enlace para llegar a cualquier "listón" o punto de elección subsiguiente, un borde se definiría como este recorrido y obtendrá un gráfico típico.

Los resultados se almacenan en una tabla simple, N x N, donde N es el número de "listones".

Aquí está el inconveniente (¿inevitable?). Si una red típica para nuestra simulación puede tener, digamos, 2000 intersecciones, tendrá alrededor de 6000 enlaces, es decir, N = 3V. Obviamente, si se cuenta en términos de intersecciones (V), ahora estamos hasta O (log (3V) * (3V + E)).

Podría argumentar que 3 (o 9) es un factor constante, pero desde el punto de vista práctico, ralentiza bastante las cosas y aumenta el espacio de almacenamiento a 3V x 3V.

¿Alguien tiene alguna idea de cómo podemos reestructurar esto para mejorar el rendimiento? ¿No es necesariamente un algoritmo alternativo, tal vez remodelar las estructuras de datos para que se ajusten a un gráfico de alguna otra manera?

algorithms performance data-structures simulation Greg Kramida
fuente

No estoy claro qué son N y V. ¿Es V el número de vértices (intersecciones) y N el número de arcos entre vértices? Además, ¿qué es E?

Mike Dunlavey

¿Qué recursos leíste? IIRC, A * está probado para encontrar la ruta óptima en la menor cantidad de tiempo dada una heurística pesimista. De hecho, A * regresa a Dijkstra con una heurística vacía / 0.

Steven Evers

Además, ¿qué representación gráfica estás usando? Los gráficos unidireccionales con listas de adyacencia permitirían fácilmente carreteras como bordes / intersecciones como nodos (en realidad, incluso una matriz de adyacencia lo haría, pero obviamente tendría que ser una matriz completa en lugar de triangular superior / inferior). TBH: Sugeriría una gran cantidad de literatura sobre programación de juegos, es un problema muy trabajado en ese campo y tiene las mismas restricciones de rendimiento más estrictas que estás mencionando.

Steven Evers

@SnOrfus: sí, pero no siempre puede representar una sola intersección como un solo nodo, por ejemplo, una intersección le permite girar a la izquierda o ir directamente pero no girar a la derecha, la matriz de adyacencia simple no podría representar eso ( peor si tienes una rotonda).

Lie Ryan

@LieRyan: Tal vez te estoy malinterpretando, pero eso no es diferente de una intersección donde no hay giro a la derecha y debería representarse de la misma manera.

Steven Evers

Respuestas:

Dijkstra encuentra el camino más corto entre un nodo dado y todos los demás nodos, por lo que espero que sea más costoso que A *. Sin embargo, ¿parece que está tratando de calcular previamente el costo y la ruta de un nodo a otro? Entonces Dijkstra es el camino a seguir.

En cuanto a una representación más simple, me vienen a la mente algunas cosas:

En muchas intersecciones, puede venir y salir de la forma que desee. Es solo un subconjunto que tiene restricciones como "no girar a la izquierda". Por lo tanto, podría usar los "listones" solo para intersecciones donde realmente los necesita. Eso debería reducir en gran medida el tamaño allí mismo.

Puede hacer esto automáticamente buscando "listones equivalentes" y combinándolos. Dos listones son equivalentes si todos los enlaces que salen son iguales. Por ejemplo, si "Intersección X viene del Oeste" e "Intersección X viene del Sur", ambas conducen al mismo conjunto de otros nodos, con el mismo costo, entonces simplemente combínelos en un solo nodo.

¿Está seguro de que necesita / desea calcular previamente el mejor camino, en lugar de calcularlo en línea? Los videojuegos suelen calcular estas cosas en línea.

Además, ¿cómo estás representando los caminos? En su matriz, solo necesita representar el primer enlace en la ruta. Por ejemplo, para ir de la casa de Bob al trabajo de Bob, solo necesita conocer el primer enlace, ya que cuando lleguen allí, ahora puede buscar en su matriz cómo llegar desde el primer enlace al trabajo de Bob, lo que le dará el segundo enlace, etc.

Martin C. Martin
fuente

Combinar "listones" es de hecho una idea interesante. Tienes razón, estamos encontrando la ruta más corta entre cada par de nodos y luego generando rutas. En una simulación de tráfico típica, casi nunca se utilizan carreteras (¿por qué habría una carretera allí en primer lugar, verdad?). Cuando dice "en línea", ¿quiere decir en tiempo real? Todo lo que realmente podemos hacer es calcular las rutas más cortas "esperadas", ya que no sabemos exactamente cuáles serán las condiciones en algún enlace cuando el vehículo llegue allí. Actualizamos la matriz de ruta más corta según las condiciones actuales.

Greg Kramida

Sí, por "en línea", quiero decir en tiempo real, es decir, cuando Bob sale de su casa y quiere ir a trabajar, haga la A *.

Martin C. Martin el

Dependiendo de la frecuencia con la que deba actualizarse la matriz de ruta más corta, puede hacer mucho trabajo para la actualización y no terminar utilizando la mayoría de las celdas antes de volver a realizar la actualización. No conozco los detalles de su caso de uso, pero desde el exterior, parece que al menos vale la pena probar A *. Además, si bien todos los N nodos se usan en algún momento, eso no significa que todos los pares N ^ 2 se usarán en algún momento. La gente en el bloque de Bob, ¿cuántos destinos únicos tienen?

Martin C. Martin

Sí, estoy de acuerdo, probablemente valga la pena probar A *. Para algunas simulaciones, enrutamos una fracción de los vehículos en cada origen a casi todos los destinos, pero con mucho, no en todos los casos. Encontré algunos documentos sobre personas que utilizan diversas heurísticas con A * específicamente para redes de tráfico, voy a probarlas. Gracias por tu ayuda, Martin.

Greg Kramida

Tienes un gráfico grande y lo hiciste aún más grande. Martinc C. Martin aconsejó usar tornos solo cuando sea necesario, por lo que no entraré en esto.

Una de las cosas que podrían ayudarlo es transformar su gráfico en gráficos más pequeños.

La primera simplificación que me ayudó mucho (trabajé con redes de carreteras de estados europeos) fue "eliminar" nodos con digree 1 y 2 de forma recursiva. De esta manera, no tiene caminos sin salida, y las intersecciones en T (originalmente grado 3) se convierten en grado 2 y eso no es interesante, si no está siguiendo ese nodo o nodo en ese cull de sac eliminado.

Después de eso, puede intentar dividir su gráfico en partes que tengan una gran cantidad de nodos internos y bordes, pero que tengan una conexión mínima con otras partes. Para encontrarlos, utilicé un corte mínimo donde el sumidero y la fuente estaban tan lejos uno del otro (en los bordes) uno del otro y los bordes cercanos a ellos tenían una gran capacidad y los bordes en algún punto intermedio eran pequeños.

user470365
fuente