Los solucionadores de generación de rutas de Extensión ArcGIS Network Analyst (es decir, los solucionadores Ruta, Instalación más cercana y Matriz de coste OD) se basan en el conocido algoritmo de Dijkstra para buscar las rutas más cortas. Cada uno de estos solucionadores implementa dos tipos de algoritmos de búsqueda de ruta. El primer tipo es la trayectoria exacta más corta y el segundo es un solucionador de trayectorias jerárquicas para un mejor rendimiento. El algoritmo de Dijkstra clásico resuelve un problema de trayectoria más corta en un gráfico sin dirección, no negativo, ponderado. Para utilizarlo dentro del contexto de los datos de transporte del mundo real, este algoritmo se ha modificado para respetar configuraciones de usuario tales como restricciones unidireccionales, restricciones de giro, impedancia de cruces, barreras y restricciones de lado de calle, mientras se minimiza un atributo de coste especificado por el usuario. El rendimiento del algoritmo de Dijkstra se mejora aún más utilizando mejores estructuras de datos, tales como almacenamientos dinámicos d. Además, el algoritmo debe modelar las ubicaciones en cualquier punto a lo largo de un borde, no solo en los cruces.
Algoritmo de Dijkstra
El algoritmo de Dijkstra clásico resuelve el problema de la trayectoria más corta de origen único en un gráfico ponderado. Para encontrar la ruta más corta desde una ubicación de origen s a una ubicación de destino d, el algoritmo de Dijkstra mantiene un conjunto de cruces, S, cuya ruta más corta final desde s ya se ha calculado. El algoritmo encuentra repetidamente un cruce en el conjunto de cruces que tiene la estimación mínima de la ruta más corta, la agrega al conjunto de cruces S y actualiza las estimaciones de ruta más corta de todos los vecinos de este cruce que no están en S. El algoritmo continúa hasta que el cruce de destino se agrega a S.
Ruta
Ruta utiliza el conocido algoritmo de Dijkstra, descrito anteriormente.
Instalación más cercana
Instalación más cercana utiliza un algoritmo de varios orígenes y varios destinos basado en el algoritmo de Dijkstra. Tiene opciones para calcular solo las rutas más cortas si están dentro de una tolerancia especificada o para resolver para un número fijo de instalaciones más cercanas.
Más información sobre cómo buscar la instalación más cercana
Matriz de coste OD
Matriz de coste OD utiliza un algoritmo de varios orígenes y varios destinos basado en el algoritmo de Dijkstra. Tiene opciones para calcular solo las rutas más cortas si están dentro de una tolerancia especificada o para resolver para un número fijo de destinos más cercanos. El solucionador Matriz de coste OD es similar al solucionador Instalación más cercana, pero difiere en que no calcula la forma de la trayectoria más corta resultante para reducir la sobrecarga y mejorar el rendimiento.
Enrutamiento jerárquico
Buscar la ruta más corta exacta en un dataset de red nacional consume mucho tiempo, debido al gran número de bordes que hay que buscar. Para mejorar el rendimiento, los datasets de red pueden modelar la jerarquía natural de un sistema de transportes donde conducir por carreteras interestatales es preferible a conducir por carreteras locales. Una vez creada una red jerárquica, se utiliza una modificación bidireccional de Dijkstra para calcular una ruta entre un origen y un destino.
El objetivo global aquí es minimizar la impedancia favoreciendo las jerarquías de orden superior presentes en la red. La generación de rutas jerárquica lo hace buscando simultáneamente desde las ubicaciones de origen y de destino, así como conexiones o puntos de entrada en carreteras de nivel superior y, a continuación, buscando las carreteras de nivel superior hasta que se encuentren los segmentos procedentes del origen y del destino. Cuando la búsqueda está restringida a la jerarquía superior, se busca en un número más pequeño de bordes, lo que resulta en un mejor rendimiento. Observe que se trata de un algoritmo heurístico; su objetivo es un rendimiento rápido y buenas soluciones, pero no garantiza que se vaya a encontrar la trayectoria más corta. Para que esta heurística tenga éxito, la jerarquía de nivel superior debe estar conectada, puesto que no descenderá a un nivel inferior si encuentra un callejón sin salida.
En general, tiene sentido utilizar este solucionador en una red jerárquica donde los pesos de los bordes se basen en el tiempo de viaje. Así se imita la manera como las personas conducen normalmente en una red de carreteras.
La opción del problema del viajante de comercio para el solucionador Ruta
El solucionador Ruta tiene la opción de generar la secuencia óptima para visitar las ubicaciones de parada. Este es el problema del viajante de comercio o TSP. El TSP es un problema combinatorio, lo que significa que no hay una manera directa para encontrar la mejor secuencia. Se utilizan heurísticas para buscar buenas soluciones a estos tipos de problemas en un período corto de tiempo. La implementación de TSP en Network Analyst también controla las ventanas de tiempo en las paradas; es decir, encuentra la secuencia óptima para visitar las paradas con un retraso mínimo.
El solucionador del viajante de comercio empieza por generar una matriz de costes de origen-destino entre todas las paradas que se van a secuenciar y utiliza un algoritmo basado en la búsqueda de tabúes para encontrar la mejor secuencia para visitar las paradas. La búsqueda de tabúes es un algoritmo metaheurístico para resolver problemas combinatorios. Se clasifica dentro de los algoritmos de búsqueda locales. La implementación exacta de la búsqueda de tabúes está patentada, pero se ha investigado y desarrollado ampliamente en Esri para producir rápidamente buenos resultados.
Problema de generación de rutas para vehículos con ventanas de tiempo
El problema de generación de rutas para vehículos (VRP) es un superconjunto del TSP. En un TSP, se secuencia un conjunto de paradas de manera óptima. En un VRP, se debe asignar un conjunto de órdenes a un conjunto de rutas o vehículos de modo que se minimice el coste total de la trayectoria. También debe respetar las restricciones del mundo real, que incluyen la capacidad de los vehículos, las ventanas de tiempo de entrega y las especializaciones de los conductores. El VRP genera una solución que respeta estas restricciones minimizando al mismo tiempo una función objetivo, compuesta de costes operativos y preferencias del usuario, tales como la importancia de cumplir con las ventanas de tiempo.
El solucionador VRP empieza por generar una matriz de origen-destino de los costes de las trayectorias más cortas entre todas las ubicaciones de orden y depósito a lo largo de la red. Con esta matriz de costes, construye una solución inicial insertando las órdenes de una en una en la ruta más adecuada. A continuación, la solución inicial se mejora cambiando la secuencia de las órdenes en cada ruta, así como moviendo las órdenes de una ruta a otra e intercambiando órdenes entre rutas. Las heurísticas utilizadas en este proceso se basan en una metaheurística de búsqueda de tabúes y están patentadas, pero se han investigado y desarrollado continuamente en Esri durante muchos años y producen rápidamente buenos resultados.
Más información sobre el problema de generación de rutas para vehículos
Área de servicio
El solucionador Área de servicio también se basa en el algoritmo de Dijkstra para realizar un trazado poligonal de la red. Su objetivo es devolver un subconjunto de entidades de eje conectadas tal y como son dentro de la distancia de red o valor límite de coste especificados. Además, puede devolver las líneas clasificadas por un conjunto de valores de descanso que se encuentren dentro de un borde. El solucionador de área de servicio puede generar líneas, polígonos que rodean estas líneas, o ambos.
Los polígonos se generan creando una zona de influencia con las líneas mediante una distancia proporcionada por el usuario. Opcionalmente, los usuarios pueden crear polígonos de alta calidad, de manera que los polígonos contengan toda el área situada más cerca de las líneas atravesadas por el trazado poligonal que las líneas no atravesadas, hasta una distancia proporcionada por el usuario.
Ubicación y asignación
Ubicación-asignación es un solucionador para el problema de la ubicación de instalaciones. Es decir, dadas N instalaciones candidatas y M puntos de demanda con un peso, elegir un subconjunto de instalaciones, P, tal que se minimice la suma de las distancias ponderadas desde cada M hasta el P más cercano. Este es un problema combinatorio de tipo N elige P, y el espacio de soluciones se hace sumamente grande. No se pueden obtener soluciones óptimas examinando todas las combinaciones. Por ejemplo, incluso un problema pequeño como 100 elige 10 contiene más de 17 trillones de combinaciones. Además, el solucionador de ubicación-asignación tiene opciones para resolver una variedad de problemas de ubicación tales como minimizar la impedancia ponderada, maximizar la cobertura o lograr una cuota de mercado objetivo. Para resolver los problemas de ubicación-asignación se utilizan heurísticas.
El solucionador de ubicación-asignación empieza por generar una matriz de origen-destino de los costes de las trayectorias más cortas entre todas las instalaciones y las ubicaciones de los puntos de demanda a lo largo de la red. A continuación, construye una versión revisada de la matriz de costes mediante un proceso conocido como edición de Hillsman. Este proceso de edición permite que la misma heurística de solucionador global resuelva diversos tipos de problemas. A continuación, el solucionador de ubicación-asignación genera un conjunto de soluciones semialeatorias y aplica una heurística de sustitución de vértices (Teitz y Bart) para refinar estas soluciones, lo que crea un grupo de buenas soluciones. Una metaheurística combina este grupo de buenas soluciones para crear soluciones mejores. Cuando no es posible ninguna mejora adicional, la metaheurística devuelve la mejor solución encontrada. La combinación de una matriz editada, soluciones iniciales semialeatorias, una heurística de sustitución de vértices y una metaheurística de refinado produce rápidamente resultados casi óptimos.
Más información sobre cómo realizar un análisis de ubicación y asignación