Enrutamiento de nodos de tránsito

En matemáticas aplicadas , el enrutamiento de nodos de tránsito se puede utilizar para acelerar el enrutamiento de ruta más corta mediante el cálculo previo de conexiones entre nodos de acceso comunes a una subred relevante para viajes de larga distancia. ^{[ 1 ]}

El enrutamiento de nodos de tránsito como marco de trabajo se estableció en 2007 ^{[ 1 ]} y en los años posteriores surgieron numerosas implementaciones concretas, como enfoques que utilizan cuadrículas, jerarquías de autopistas ^{[ 2 ]} y jerarquías de contracción ^{[ 3 ]} . El enrutamiento de nodos de tránsito es un enfoque estático que requiere el preprocesamiento de las distancias por pares entre nodos importantes en el grafo (véase más adelante cómo se eligen esos nodos). No se ha publicado ningún enfoque dinámico ^{[ 4 ] .}

Intuición

Los viajes de larga distancia suelen implicar conducir por un subconjunto de la red vial, como autopistas, en lugar de, por ejemplo, carreteras urbanas. A esta subred solo se puede acceder mediante nodos de acceso dispersos . Al compararlas entre sí, múltiples rutas de larga distancia que parten del mismo punto siempre utilizan la misma cantidad reducida de nodos de acceso cercanos al punto de partida para acceder a esta red. Del mismo modo, a destinos similares siempre se llega utilizando los mismos nodos de acceso cercanos. Esta intuición solo se aplica a los viajes de larga distancia. En trayectos cortos, es posible que nunca se utilicen dichos nodos de acceso, ya que la ruta más rápida hacia el destino solo utiliza carreteras locales.

Dado que el número de nodos de acceso es pequeño en comparación con el número total de nodos en una red vial, todas las rutas más cortas que conectan dichos nodos entre sí pueden precalcularse y almacenarse. Por lo tanto, al calcular la ruta más corta, solo es necesario calcular las rutas a los nodos de acceso cercanos a la ubicación de inicio y destino.

Marco general

El enrutamiento de nodos de tránsito comienza con una selección de nodos de tránsito. $T\subsetequ V$ como un subconjunto de todos los nodos $V$ de la red vial.
Para cada nodo $v\in V$ conjuntos dedicados de nodos de acceso directo ${\overrightarrow {A}}(v)\subseteteq T$ y nodos de acceso hacia atrás ${\overleftarrow {A}}(v)\subseteteq T$ se eligen de entre todos los nodos de tránsito.
Ahora, distancias por pares entre nodos de tránsito $D_{T}$ y distancias entre nodos $v$ y sus nodos de acceso correspondientes $d_{A}$ se calculan y se almacenan.
Ahora se puede calcular la distancia entre dos nodos como $d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)$

Filtro de localidad

Las rutas cortas entre puntos de inicio y destino cercanos pueden no requerir nodos de tránsito. En este caso, el marco anterior genera distancias incorrectas, ya que obliga a las rutas a visitar al menos un nodo de tránsito.

Para evitar este tipo de problemas, se puede utilizar un filtro de localidad . Para unas ubicaciones de inicio y destino dadas, el filtro de localidad decide si se debe aplicar el enrutamiento del nodo de tránsito o si se debe utilizar una rutina de reserva (consulta local).

Ejemplos concretos

El enrutamiento de nodos de tránsito no es un algoritmo, sino simplemente un marco para acelerar la planificación de rutas. El marco general deja abiertas algunas preguntas que deben responderse para su implementación:

¿Cómo se seleccionan los nodos de tránsito?
¿Cómo se eligen los nodos de acceso?
¿Qué filtro de localidad se debe utilizar?
¿Cómo deben gestionarse las consultas locales?

Las siguientes implementaciones de ejemplo de este marco responden a estas preguntas utilizando diferentes métodos subyacentes, como la agrupación de nodos en celdas de una cuadrícula superpuesta ^{[ 2 ]} y una implementación más sofisticada basada en jerarquías de contracción . ^{[ 3 ]}

Enfoque geométrico mediante cuadrículas

En un enfoque basado en cuadrícula , el cuadrado que delimita todos los nodos se subdivide equitativamente en celdas cuadradas.

¿Cómo se seleccionan los nodos de acceso?

Para cada celda $C$ Se puede encontrar un conjunto de nodos de acceso mirando un área interior. $I$ de 5x5 celdas y un área exterior $O$ de 9x9 celdas alrededor $C$ . Centrándonos en los nodos de cruce (extremos de aristas que cruzan el límite de $C$ , $I$ o $O$ ), los nodos de acceso para $C$ son esos nodos de $I$ que forman parte de un camino más corto desde algún nodo en $C$ a un nodo en $O$ . Como nodos de acceso para un nodo arbitrario $v\in C$ todos los nodos de acceso de $C$ son seleccionados (puntos rojos en la imagen de la derecha).

¿Cómo se seleccionan los nodos de tránsito?

El conjunto de nodos de tránsito es exactamente la unión de todos los conjuntos de nodos de acceso.

¿Qué filtro de localidad se debe utilizar?

La forma en que se seleccionan los nodos de acceso implica que, si el origen y el destino están separados por más de cuatro celdas de la cuadrícula, se debe pasar por un nodo de tránsito por la ruta más corta y la distancia se puede calcular como se describió anteriormente. Si están más cerca, se utiliza un algoritmo alternativo para obtener la distancia.

¿Cómo deben gestionarse las consultas locales?

Las consultas locales solo son necesarias si el punto de inicio y el destino ya se encuentran cerca, por lo que se puede elegir cualquier algoritmo de ruta más corta adecuado, como el algoritmo de Dijkstra o extensiones del mismo.

Requisitos de espacio

Las distancias precalculadas entre cada nodo y el nodo de acceso correspondiente, así como las distancias entre pares de nodos de tránsito, deben almacenarse en tablas de distancias.

En la implementación basada en cuadrícula descrita anteriormente, esto resulta en 16 bytes de almacenamiento necesarios para cada nodo del grafo de carreteras. Un grafo completo de la red de carreteras de EE. UU. tiene 23.947.347 nodos. ^{[ 5 ]} Por lo tanto, se requerirían aproximadamente 383 MB de almacenamiento para guardar las tablas de distancias.

Utilizando jerarquías de contracción

¿Cómo se seleccionan los nodos de tránsito?

Por definición, una jerarquía de contracción mueve los nodos importantes (es decir, los nodos que forman parte de muchos caminos más cortos) a la parte superior de la jerarquía. Por lo tanto, se puede seleccionar un conjunto de nodos de tránsito como la $k$ nodos superiores de la jerarquía de contracción.

¿Cómo se seleccionan los nodos de acceso?

Nodos de acceso directo de un nodo $v$ se puede encontrar ejecutando la búsqueda ascendente de la jerarquía de contracción comenzando en $v$ Durante la búsqueda ascendente , los bordes que salen de los nodos de tránsito previamente encontrados no se relajan. Cuando la búsqueda no tiene más nodos ascendentes por resolver, aquellos nodos de tránsito que se han resuelto son los nodos de acceso de $v$ Los nodos de acceso hacia atrás se pueden encontrar de forma análoga.

¿Qué filtro de localidad se debe utilizar?

Si el nodo más alto de la ruta ascendente-descendente más corta en la jerarquía no forma parte del conjunto de nodos de tránsito, entonces la consulta fue local. Esto implica que ni la parte ascendente de la ruta (que comienza en el nodo de inicio) ni la parte descendente (que termina en el nodo de destino) pueden contener un nodo de tránsito, y debe haber un nodo común en ambas rutas. Durante el cálculo de los nodos de acceso, el espacio de búsqueda (todos los nodos visitados hacia la parte superior de la jerarquía) para cada nodo se puede almacenar sin incluir los nodos de tránsito. Al realizar una consulta, se comprueba la intersección de esos espacios de búsqueda para el nodo de inicio y el nodo de destino. Si esos espacios son disjuntos , se puede utilizar el enrutamiento por nodos de tránsito, ya que las rutas ascendente y descendente deben encontrarse en un nodo de tránsito. De lo contrario, podría existir una ruta más corta sin un nodo de tránsito.

¿Cómo deben gestionarse las consultas locales?

Las consultas locales utilizan el algoritmo de consulta habitual de la jerarquía de contracción.

Véase también

Referencias

1 2 Bast, H.; Funke, S.; Sanders, P.; Schultes, D. (2007-04-27). "Enrutamiento rápido en redes viales con nodos de tránsito". Science . 316 (5824): 566. Bibcode : 2007Sci...316..566B . doi : 10.1126/science.1137521 . ISSN 0036-8075 . PMID 17463281 . S2CID 16559205 .
1 2 Bast, Holger; Funke, Stefan; Matijevic, Domagoj; Sanders, Peter; Schultes, Dominik (2007-01-06), "En tránsito hacia consultas de ruta más corta en tiempo constante en redes viales", Actas del noveno taller sobre ingeniería y experimentos de algoritmos (ALENEX) de 2007 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 46–59 , doi : 10.1137/1.9781611972870.5 , ISBN 9781611972870{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
1 2 Arz, Julian; Luxen, Dennis; Sanders, Peter (2013), "Reconsideración del enrutamiento de nodos de tránsito", Experimental Algorithms , Springer Berlin Heidelberg, pp. 55–66 , arXiv : 1302.5611 , Bibcode : 2013arXiv1302.5611A , doi : 10.1007/978-3-642-38527-8_7 , ISBN 9783642385261, S2CID 14371800 {{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
↑ Schultes, Dominik; Sanders, Peter (2007), "Enrutamiento dinámico de nodos de autopista", Algoritmos experimentales , Notas de clase en ciencias de la computación, vol. 4525, Springer Berlin Heidelberg, pp. 66–79 , doi : 10.1007/978-3-540-72845-0_6 , ISBN 9783540728443
↑ "9.º Desafío de Implementación de DIMACS: Rutas más cortas" . users.diag.uniroma1.it . Consultado el 15 de julio de 2019 .

[:0-1] 1 2 Bast, H.; Funke, S.; Sanders, P.; Schultes, D. (2007-04-27). "Enrutamiento rápido en redes viales con nodos de tránsito". Science . 316 (5824): 566. Bibcode : 2007Sci...316..566B . doi : 10.1126/science.1137521 . ISSN 0036-8075 . PMID 17463281 . S2CID 16559205 .

[:1-2] 1 2 Bast, Holger; Funke, Stefan; Matijevic, Domagoj; Sanders, Peter; Schultes, Dominik (2007-01-06), "En tránsito hacia consultas de ruta más corta en tiempo constante en redes viales", Actas del noveno taller sobre ingeniería y experimentos de algoritmos (ALENEX) de 2007 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 46–59 , doi : 10.1137/1.9781611972870.5 , ISBN 9781611972870{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[:2-3] 1 2 Arz, Julian; Luxen, Dennis; Sanders, Peter (2013), "Reconsideración del enrutamiento de nodos de tránsito", Experimental Algorithms , Springer Berlin Heidelberg, pp. 55–66 , arXiv : 1302.5611 , Bibcode : 2013arXiv1302.5611A , doi : 10.1007/978-3-642-38527-8_7 , ISBN 9783642385261, S2CID 14371800 {{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[4] Schultes, Dominik; Sanders, Peter (2007), "Enrutamiento dinámico de nodos de autopista", Algoritmos experimentales , Notas de clase en ciencias de la computación, vol. 4525, Springer Berlin Heidelberg, pp. 66–79 , doi : 10.1007/978-3-540-72845-0_6 , ISBN 9783540728443

[5] "9.º Desafío de Implementación de DIMACS: Rutas más cortas" . users.diag.uniroma1.it . Consultado el 15 de julio de 2019 .

[ 4 ] .

[ 5 ]

Intuición

Marco general

Filtro de localidad

Ejemplos concretos

Enfoque geométrico mediante cuadrículas

Requisitos de espacio

Utilizando jerarquías de contracción

Véase también

Referencias

Articulos relacionados