Jerarquías de contracción

En informática , el método de jerarquías de contracción es una técnica de aceleración para encontrar el camino más corto en un gráfico . Las aplicaciones más intuitivas son los sistemas de navegación para automóviles: el usuario quiere conducir de un lugar a otro por la ruta más rápida posible. La métrica optimizada aquí es el tiempo de viaje. Las intersecciones se representan mediante vértices y los tramos de carretera que las conectan mediante aristas . Los pesos de los bordes representan el tiempo que lleva conducir por este segmento de la carretera. Un camino desde hasta es una secuencia de bordes (secciones de carretera); el camino más corto es aquel que tiene la suma mínima de pesos de borde entre todos los caminos posibles. El camino más corto en un gráfico se puede calcular utilizando el algoritmo de Dijkstra pero, dado que las redes de carreteras constan de decenas de millones de vértices, esto no es práctico. ^[1] Las jerarquías de contracción son un método de aceleración optimizado para explotar las propiedades de los gráficos que representan redes de carreteras. ^[2] La aceleración se logra creando accesos directos en una fase de preprocesamiento que luego se utilizan durante una consulta de ruta más corta para omitir vértices "sin importancia". ^[2] Esto se basa en la observación de que las redes de carreteras son altamente jerárquicas. Algunas intersecciones, por ejemplo los cruces de autopistas, son "más importantes" y están más arriba en la jerarquía que, por ejemplo, un cruce que conduce a un callejón sin salida. Se pueden utilizar atajos para guardar la distancia calculada previamente entre dos cruces importantes, de modo que el algoritmo no tenga que considerar la ruta completa entre estos cruces en el momento de la consulta. Las jerarquías de contracción no saben qué caminos los humanos consideran "importantes" (por ejemplo, autopistas), pero se les proporciona el gráfico como entrada y pueden asignar importancia a los vértices usando heurísticas. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Las jerarquías de contracción no sólo se aplican a los algoritmos de aceleración en los sistemas de navegación de automóviles , sino también en los planificadores de rutas basados ​​en la web , la simulación de tráfico y la optimización logística. ^{[3] [1] [4]} Las implementaciones del algoritmo están disponibles públicamente como software de código abierto . ^{[5] [6] [7] [8] [9]}

Algoritmo

El algoritmo de jerarquías de contracción (CH) es un enfoque de dos fases para el problema del camino más corto que consta de una fase de preprocesamiento y una fase de consulta . Como las redes de carreteras cambian con poca frecuencia, se puede utilizar más tiempo (de segundos a horas) para realizar algunos cálculos antes de responder las consultas. Con estos datos precalculados, se pueden responder muchas consultas en muy poco tiempo (microsegundos) cada una. ^{[1] [3]} Los CH dependen de atajos para lograr esta aceleración. Un atajo conecta dos vértices y no adyacentes en el gráfico original. El peso de sus bordes es la suma de los pesos de los bordes en el camino más corto . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

Consideremos dos grandes ciudades conectadas por una carretera. Entre estas dos ciudades hay multitud de cruces que conducen a pequeños pueblos y suburbios. La mayoría de los conductores quieren ir de una ciudad a otra (tal vez como parte de una ruta más grande) y no tomar una de las salidas del camino. En el gráfico que representa el diseño de esta carretera, cada intersección está representada por un nodo y se crean bordes entre las intersecciones vecinas. Para calcular la distancia entre estas dos ciudades, el algoritmo tiene que recorrer todos los bordes a lo largo del camino, sumando su longitud. Calcular previamente esta distancia una vez y almacenarla en un borde adicional creado entre las dos grandes ciudades ahorrará cálculos cada vez que esta carretera deba evaluarse en una consulta. Esta ventaja adicional se denomina "atajo" y no tiene equivalente en el mundo real. El algoritmo de jerarquías de contracción no tiene conocimiento sobre los tipos de carreteras, pero es capaz de determinar qué atajos deben crearse utilizando únicamente el gráfico como entrada.

Para encontrar una ruta desde el algoritmo, puede omitir los vértices grises y utilizar el atajo discontinuo . Esto reduce la cantidad de vértices que el algoritmo debe considerar. El peso de los bordes del atajo desde hasta es la suma de los pesos de los bordes de la ruta más corta . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

Fase de preprocesamiento

El algoritmo CH se basa en atajos creados en la fase de preprocesamiento para reducir el espacio de búsqueda, es decir, la cantidad de vértices que CH tiene que mirar en el momento de la consulta. Para lograr esto, se realizan contracciones iterativas de vértices. Cuando se contrae un vértice, se elimina temporalmente del gráfico y se crea un acceso directo entre cada par de vértices vecinos si el camino más corto desde hasta contiene . ^[2] El proceso de determinar si el camino más corto entre y contiene se llama búsqueda de testigos. Se puede realizar, por ejemplo, calculando una ruta desde hasta utilizando una búsqueda directa utilizando sólo nodos aún no contratados. ^[3] ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle \{u,w\}}$ ${\textstyle u}$ ${\textstyle w}$ ${\displaystyle v}$ ${\textstyle u}$ ${\textstyle w}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle w}$

La gráfica original es la recta (sólida). Los bordes discontinuos representan atajos, las flechas grises muestran qué dos bordes se combinan para formar el atajo respectivo. Los vértices se han dibujado para representar el orden de los nodos en el que se contraen, de abajo hacia arriba. La contracción del vértice introduce un atajo entre y con . Contracciones de los vértices e introducen un atajo respectivamente. Las contracciones de y no introducen ningún atajo y, por lo tanto, no se muestran . ${\displaystyle (a,b,c,d,e,f)}$ ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle \mathrm {dist} (b,d)=\mathrm {dist} (b,c)+\mathrm {dist} (c,d)}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle f}$

Orden de nodos

Los vértices del gráfico de entrada deben contraerse de una manera que minimice el número de aristas agregadas al gráfico mediante las contracciones. Como el orden óptimo de los nodos es NP-completo , se utilizan heurísticas ^{[10] . [2]}

Existen heurísticas ascendentes y descendentes . Por un lado, las heurísticas ascendentes, computacionalmente más baratas, deciden el orden en el que se contraerán los vértices de forma codiciosa ; esto significa que el orden no se conoce de antemano, sino que se selecciona el siguiente nodo para la contracción después de que se haya completado la contracción anterior. Por otro lado, la heurística de arriba hacia abajo precalcula todo el orden de los nodos antes de que se contraiga el primer nodo. Esto produce mejores resultados pero necesita más tiempo de preprocesamiento. ^[2]

En la heurística ascendente , se utiliza una combinación de factores para seleccionar el siguiente vértice para la contracción. Como la cantidad de accesos directos es el factor principal que determina el preprocesamiento y el tiempo de ejecución de la consulta, queremos mantenerlo lo más pequeño posible. Por lo tanto, el término más importante para seleccionar el siguiente nodo para la contracción es el número neto de aristas agregadas al contraer un nodo . Esto se define como donde está el número de atajos que se crearían si se contrajeran y es el número de aristas incidentes . Usando solo este criterio, una ruta lineal daría como resultado una jerarquía lineal (muchos niveles ) y no se crearían atajos. Al considerar el número de vértices cercanos que ya están contraídos, se logra una contracción uniforme y una jerarquía plana (menos niveles). Esto se puede hacer, por ejemplo, manteniendo un contador para cada nodo que se incrementa cada vez que se contrae un vértice vecino. Entonces se prefieren los nodos con contadores más bajos a los nodos con contadores más altos. ^[11] ${\displaystyle x}$ ${\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|}$ ${\displaystyle A(x)}$ ${\displaystyle x}$ ${\displaystyle |\{(u,x)\colon (u,x)\in E\}|}$ ${\displaystyle x}$

Por otro lado, las heurísticas de arriba hacia abajo producen mejores resultados pero necesitan más tiempo de preprocesamiento. Clasifican los vértices que forman parte de muchos caminos más cortos como más importantes que aquellos que sólo son necesarios para unos pocos caminos más cortos. Esto se puede aproximar utilizando disecciones anidadas . ^[2] Para calcular una disección anidada, se separa recursivamente un gráfico en dos partes, que luego se separan en dos partes y así sucesivamente. Es decir, encuentre un subconjunto de nodos que, cuando se eliminan del gráfico, se separan en dos partes disjuntas de aproximadamente el mismo tamaño, de modo que . Coloque todos los nodos al final en el orden de nodos y luego calcule recursivamente la disección anidada para y , ^[12] la intuición es que todas las consultas de una mitad del gráfico a la otra mitad del gráfico deben pasar a través del pequeño separador y, por lo tanto, de los nodos. en este separador son de gran importancia. Las disecciones anidadas se pueden calcular eficientemente en redes de carreteras debido a sus pequeños separadores. ^[13] ${\displaystyle S\subseteq V}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G_{1},G_{2}}$ ${\displaystyle S\cup G_{1}\cup G_{2}=G}$ ${\displaystyle v\in S}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Fase de consulta

En la fase de consulta, se realiza una búsqueda bidireccional comenzando desde el nodo inicial y el nodo objetivo en el gráfico original, aumentada por los accesos directos creados en la fase de preprocesamiento. ^[2] El vértice más importante en el camino más corto entre y será o ellos mismos o más importante que ambos y . Por lo tanto, la minimización de vértices está en el camino más corto en el gráfico original y se mantiene. ^[2] Esto, en combinación con la forma en que se crean los accesos directos, significa que tanto la búsqueda hacia adelante como hacia atrás solo necesitan relajar los bordes que conducen a nodos más importantes (hacia arriba) en la jerarquía, lo que mantiene pequeño el espacio de búsqueda. ^[3] En todas las rutas arriba-(abajo-arriba)-abajo, la interna (abajo-arriba) se puede omitir, porque se ha creado un acceso directo en la etapa de preprocesamiento. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)}$ ${\displaystyle s-t}$ ${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)}$

Al calcular la ruta más corta desde hasta , la búsqueda hacia adelante (naranja) y hacia atrás (azul) solo necesita seguir los bordes que van hacia arriba en la jerarquía. La ruta encontrada está marcada en rojo y utiliza un atajo (discontinuo). ${\displaystyle s}$ ${\displaystyle t}$

Recuperación de ruta

Una consulta CH, como se describió anteriormente, proporciona el tiempo o la distancia desde pero no la ruta real. Para obtener la lista de bordes (carreteras) en el camino más corto, se deben descomprimir los atajos tomados. Cada atajo es la concatenación de dos aristas: dos aristas del gráfico original, dos atajos, o un atajo original y un atajo. Almacenar el vértice medio de cada atajo durante la contracción permite descomprimir recursivamente en tiempo lineal la ruta más corta. ^{[2] [3]} ${\displaystyle s}$ ${\displaystyle t}$

Jerarquías de contracción personalizadas

Si los pesos de los bordes se cambian con más frecuencia que la topología de la red, CH se puede extender a un enfoque de tres fases al incluir una fase de personalización entre el preprocesamiento y la fase de consulta. Esto se puede utilizar, por ejemplo, para cambiar entre la distancia más corta y el tiempo más corto o incluir información de tráfico actual, así como preferencias del usuario, como evitar ciertos tipos de carreteras (ferries, autopistas,...). En la fase de preprocesamiento, la mayor parte del tiempo de ejecución se dedica a calcular el orden en que se contraen los nodos. ^[3] Esta secuencia de operaciones de contracción en la fase de preprocesamiento se puede guardar para cuando se necesiten más adelante en la fase de personalización. Cada vez que se personaliza la métrica, las contracciones se pueden aplicar de manera eficiente en el orden almacenado utilizando la métrica personalizada. ^[2] Además, dependiendo de los nuevos pesos de los bordes, puede ser necesario volver a calcular algunos atajos. ^[3] Para que esto funcione, el orden de contracción debe calcularse utilizando disecciones anidadas independientes de la métrica. ^[1]

Extensiones y aplicaciones

Los CH, como se describió anteriormente, buscan una ruta más corta desde un nodo inicial a un nodo objetivo. Esto se denomina camino más corto uno a uno y se utiliza, por ejemplo, en los sistemas de navegación de automóviles. Otras aplicaciones incluyen hacer coincidir las trazas GPS con los segmentos de la carretera y acelerar los simuladores de tráfico que deben considerar las rutas probables tomadas por todos los conductores en una red. En la predicción de rutas, se intenta estimar hacia dónde se dirige probablemente un vehículo calculando qué tan bien sus posiciones actuales y pasadas coinciden con el camino más corto desde su punto de partida hasta cualquier objetivo posible. Esto se puede hacer de manera eficiente utilizando CH. ^[2]

En escenarios de uno a muchos , se proporcionan un nodo inicial y un conjunto de nodos objetivo y se debe calcular la distancia para todos . La aplicación más destacada para consultas de uno a varios son las búsquedas de puntos de interés. Los ejemplos típicos incluyen encontrar la gasolinera, el restaurante o la oficina de correos más cercanos utilizando el tiempo de viaje real en lugar de la distancia geográfica como métrica. ^[2] ${\displaystyle s}$ ${\displaystyle T}$ ${\displaystyle \mathrm {dist} (s,t)}$ ${\displaystyle t\in T}$

En el escenario del camino más corto de muchos a muchos , se proporciona un conjunto de nodos iniciales y un conjunto de nodos objetivo y se debe calcular la distancia para todos . Esto se utiliza, por ejemplo, en aplicaciones logísticas. ^[2] Los CH se pueden extender a consultas de muchos a muchos de la siguiente manera. Primero, realice una búsqueda hacia atrás y hacia arriba desde cada archivo . Para cada vértice escaneado durante esta búsqueda, se almacena en un depósito . Luego, se ejecuta una búsqueda hacia arriba desde cada , verificando para cada segmento no vacío, si la ruta sobre el vértice correspondiente mejora la mejor distancia. Es decir, si es por alguno . ^{[2] [3]} ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \mathrm {dist} (s_{i},t_{i})}$ ${\displaystyle (s_{i},t_{j})\in S\times T}$ ${\displaystyle t_{j}\in T}$ ${\displaystyle u}$ ${\displaystyle \mathrm {dist} (t_{j},u)}$ ${\displaystyle \beta (u)}$ ${\displaystyle s_{i}\in S}$ ${\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})}$ ${\displaystyle (s_{i},t_{j})\in S\times T}$

Algunas aplicaciones incluso requieren cálculos uno a todos , es decir, encontrar las distancias desde un vértice fuente a todos los demás vértices del gráfico. Como el algoritmo de Dijkstra visita cada borde exactamente una vez y, por lo tanto, se ejecuta en tiempo lineal, es teóricamente óptimo. El algoritmo de Dijkstra, sin embargo, es difícil de paralelizar y no es óptimo para la caché debido a su mala localidad. Los CH se pueden utilizar para una implementación más óptima de caché. Para ello, se realiza una búsqueda hacia arriba seguida de un escaneo hacia abajo de todos los nodos en el gráfico enriquecido con accesos directos. La operación posterior escanea la memoria de forma lineal, ya que los nodos se procesan en orden de importancia decreciente y, por lo tanto, se pueden colocar en la memoria en consecuencia. ^[14] Tenga en cuenta que esto es posible porque el orden en el que se procesan los nodos en la segunda fase es independiente del nodo de origen . ^[2] ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

En producción, los sistemas de navegación para automóviles deberían poder calcular rutas de viaje más rápidas utilizando información de tráfico prevista y mostrar rutas alternativas. Ambos se pueden hacer usando CH. ^[2] El primero se llama enrutamiento con redes dependientes del tiempo donde el tiempo de viaje de un borde determinado ya no es constante sino que es una función de la hora del día en que se ingresa al borde. Las rutas alternativas deben tener una apariencia fluida, significativamente diferentes del camino más corto pero no significativamente más largas. ^[2]

Los CH se pueden ampliar para optimizar múltiples métricas al mismo tiempo; esto se llama planificación de rutas multicriterio . Por ejemplo, se podrían minimizar tanto el costo como el tiempo de viaje. Otro ejemplo son los vehículos eléctricos para los cuales la carga de batería disponible limita las rutas válidas, ya que la batería no puede funcionar vacía. ^[2]

Teoría

Se han establecido una serie de límites sobre el preprocesamiento y el rendimiento de consultas de las jerarquías de contracción. A continuación, sea el número de vértices en el gráfico, el número de aristas, la dimensión de la carretera , el diámetro del gráfico, la profundidad del árbol y el ancho del árbol . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle D}$ ${\displaystyle td}$ ${\displaystyle tw}$

El primer análisis del desempeño de la jerarquía de contracción se basa en parte en una cantidad conocida como dimensión de la carretera . Si bien la definición de esta cantidad es técnica, intuitivamente un gráfico tiene una dimensión de carretera pequeña si para cada hay un conjunto disperso de vértices de modo que cada camino más corto de longitud mayor que incluya un vértice de . Calcular el valor exacto de la dimensión de la carretera es NP-duro ^{[15] [16]} y muy probablemente W[1]-duro , ^[17] pero para las cuadrículas se sabe que la dimensión de la carretera es . ^[18] ${\displaystyle r>0}$ ${\displaystyle S_{r}}$ ${\displaystyle r}$ ${\displaystyle S_{r}}$ ${\displaystyle h\in \Theta ({\sqrt {n}})}$

Se presentó un análisis alternativo en la línea de trabajo Jerarquía de contracción personalizable. Los tiempos de ejecución de consultas pueden estar limitados por . Como la profundidad del árbol puede limitarse en términos del ancho del árbol, también es un límite superior válido. La fuente principal es ^[19] , pero las consecuencias para los peores tiempos de ejecución se detallan mejor en ^{[20] .} ${\displaystyle O(td^{2})}$ ${\displaystyle O((tw\log n)^{2})}$

Rendimiento de preprocesamiento

Rendimiento de consultas

Referencias

1. Dibbelt, Julián; Strasser, Ben; Wagner, Dorothea (5 de abril de 2016). "Jerarquías de contracción personalizables". Revista de algorítmica experimental . 21 (1): 1–49. arXiv : 1402.0402 . doi :10.1145/2886843. S2CID  5247950.
2. Bast, Hannah; Delling, Daniel; Goldberg, Andrés V.; Müller-Hannemann, Matthias; Pajor, Thomas; Lijadoras, Peter; Wagner, Dorotea; Werneck, Renato F. (2016). "Planificación de Rutas en Redes de Transporte". Ingeniería de algoritmos . Apuntes de conferencias sobre informática. vol. 9220, págs. 19–80. arXiv : 1504.05140 . doi :10.1007/978-3-319-49487-6_2. ISBN 978-3-319-49486-9. S2CID  14384915.
3. Geisberger, Robert; Lijadoras, Peter; Schultes, Dominik; Vetter, cristiano (2012). "Enrutamiento exacto en grandes redes de carreteras utilizando jerarquías de contracción". Ciencia del transporte . 46 (3): 388–404. doi :10.1287/trsc.1110.0401.
4. Delling, Daniel; Lijadoras, Peter; Schultes, Dominik; Wagner, Dorotea (2009). "Ingeniería de algoritmos de planificación de rutas". Algorítmica de redes grandes y complejas . Apuntes de conferencias sobre informática. vol. 5515, págs. 117-139. doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
5. "OSRM: máquina de enrutamiento de código abierto".
6. "Wiki-OpenTripPlanner".
7. "Web: GraphHopper".
8. "GitHub-Tempus". GitHub . 9 de septiembre de 2021.
9. "GitHub: kit de enrutamiento". GitHub . 24 de enero de 2022.
10. Bauer, Reinhard; Delling, Daniel; Lijadoras, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorotea (1 de marzo de 2010). "Combinación de técnicas de aceleración jerárquicas y dirigidas a objetivos para el algoritmo de dijkstra". Revista de algorítmica experimental . 15 : 2.1. doi :10.1145/1671970.1671976. ISSN  1084-6654. S2CID  1661292.
11. Geisberger, Robert; Lijadoras, Peter; Schultes, Dominik; Delling, Daniel (2008). "Jerarquías de contracción: enrutamiento jerárquico más rápido y sencillo en redes de carreteras". En McGeoch, Catherine C. (ed.). Algoritmos experimentales . Apuntes de conferencias sobre informática. vol. 5038. Springer Berlín Heidelberg. págs. 319–333. doi :10.1007/978-3-540-68552-4_24. ISBN 9783540685524. S2CID  777101.
12. Bauer, Reinhard; Colón, Tobías; Rutter, Ignaz; Wagner, Dorotea (13 de septiembre de 2016). "Tamaño del espacio de búsqueda en jerarquías de contracción". Informática Teórica . 645 : 112-127. doi : 10.1016/j.tcs.2016.07.003 . ISSN  0304-3975.
13. Delling, Daniel; Goldberg, Andrés V.; Razenshteyn, Ilya; Werneck, Renato F. (mayo de 2011). "Partición de gráficos con cortes naturales". Simposio internacional de procesamiento distribuido y paralelo del IEEE 2011 . págs. 1135-1146. CiteSeerX 10.1.1.385.1580 . doi :10.1109/ipdps.2011.108. ISBN  978-1-61284-372-8. S2CID  6884123.
14. Delling, Daniel; Goldberg, Andrés V.; Nowatzyk, Andreas; Werneck, Renato F. (2011). "PHAST: árboles de rutas más cortas acelerados por hardware". Simposio internacional de procesamiento distribuido y paralelo del IEEE 2011 . págs. 921–931. doi :10.1109/ipdps.2011.89. ISBN 978-1-61284-372-8. S2CID  1419921.
15. Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Publicación, Ian (1 de enero de 2018). "Una $(1+\varepsilon)$ -Incrustación de gráficos de dimensiones de carreteras bajas en gráficos de ancho de árbol acotado". Revista SIAM de Computación . 47 (4): 1667-1704. arXiv : 1502.04588 . doi :10.1137/16M1067196. ISSN  0097-5397. S2CID  11339698.
16. Blum, Johannes (2019). "Jerarquía de parámetros de la red de transporte y resultados de dureza". En Jansen, el diputado Bart; Telle, Jan Arne (eds.). 14º Simposio Internacional sobre Computación Exacta y Parametrizada (IPEC 2019). Actas internacionales de Leibniz en informática. vol. 148. Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. págs. 4:1–4:15. doi :10.4230/LIPIcs.IPEC.2019.4. ISBN 978-3-95977-129-0. S2CID  166228480.
17. Blum, Johannes; Disser, Yann; Feldmann, Andreas Emil; Gupta, Siddharth; Zych-Pawlewicz, Anna (2022). "En conjuntos de golpes dispersos: desde una cobertura de vértice justa hasta la dimensión de la carretera". En Dell, Holger; Nederlof, Jesper (eds.). 17º Simposio Internacional sobre Computación Exacta y Parametrizada (IPEC 2022) . Actas internacionales de Leibniz en informática. vol. 249. Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 5:1–5:23. doi :10.4230/LIPIcs.IPEC.2022.5. ISBN 978-3-95977-260-0.
18. Abraham, Ittai; Fiat, Amós; Goldberg, Andrés (2010). Dimensión de la carretera, caminos más cortos y algoritmos demostrablemente eficientes (PDF) . Actas del simposio anual ACM-SIAM de 2010 sobre algoritmos discretos. doi : 10.1137/1.9781611973075.64 .
19. Dibbelt, Julián; Strasser, Ben; Wagner, Dorotea (2016). "Jerarquías de contracción personalizables". Revista ACM de algorítmica experimental . 21 : 1–49. arXiv : 1402.0402 . doi :10.1145/2886843. S2CID  5247950.
20. Hamann, Michael; Strasser, Ben (2018). "Bisección de gráficos con optimización de Pareto". Revista ACM de algorítmica experimental . 23 : 1–34. arXiv : 1504.03812 . doi :10.1145/3173045. S2CID  3395784.
21. Funke, Stefan; Storandt, Sabine (2015). "Eficiencia demostrable de jerarquías de contracción con preprocesamiento aleatorio". Algoritmos y Computación . Apuntes de conferencias sobre informática. vol. 9472, págs. 479–490. doi :10.1007/978-3-662-48971-0_41. ISBN 978-3-662-48971-0.
22. Blum, Johannes; Funke, Stefan; Storandt, Sabine (2018). Espacios de búsqueda sublineales para la planificación de rutas más cortas en redes de carreteras y redes (PDF) . AAAI.

enlaces externos

Implementaciones de código abierto

• https://www.graphhopper.com/
• https://github.com/ifsttar/Tempus
• https://github.com/RoutingKit/RoutingKit
• http://project-osrm.org/
• http://www.opentripplanner.org/