Algoritmos utilizados por Network Analyst
Los solucionadores de enrutamiento de Network Analyst, en concreto los solucionadores Ruta, Instalación más cercana y Matriz de coste OD, se basan en el conocido algoritmo de Dijkstra para buscar las trayectorias más cortas. Cada uno de estos tres solucionadores implementa dos tipos de algoritmos de búsqueda de trayectorias. 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 confluencias, 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 poder modelar las ubicaciones en cualquier punto a lo largo de un borde, no solo en las confluencias.
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 buscar la trayectoria 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 confluencias, S, cuya trayectoria más corta final desde s ya se ha calculado. El algoritmo encuentra repetidamente la confluencia del conjunto de confluencias que tiene la estimación de la trayectoria más corta mínima, la agrega al conjunto de confluencias S y actualiza las estimaciones de trayectoria más corta de todos los vecinos de esta confluencia que no están en S El algoritmo continúa hasta que la confluencia de destino se agrega a S.
Ruta
Utiliza el conocido algoritmo de Dijkstra, antes descrito.
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
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. El dataset de red puede admitir hasta tres niveles jerárquicos. 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. Esto se hace buscando simultáneamente desde las ubicaciones de origen y de destino, así como conexiones o puntos de entrada en caminos de red superior y, a continuación, buscando los caminos 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. Éste es el problema del viajante de comercio o TSP. El TSP es un problema combinatorio, lo que significa que no existe ninguna manera sencilla de 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 dentro de ArcGIS 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 de manera interna 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 problema del viajante de comercio. 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 es necesario 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 esas restricciones minimizando una función objetivo, compuesta de costes operativos y preferencias del usuario tales como la importancia de cumplir 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 los órdenes de una ruta a otra e intercambiando órdenes entre rutas. Las heurísticas utilizadas en este proceso se basan en metaheurística de búsqueda de tabúes y están patentadas, pero se han investigado y desarrollado continuamente de manera interna en ESRI durante muchos años, y producen rápidamente buenos resultados.
Más información sobre la resolución de problemas de rutas para vehículos
Área de servicio
El solucionador Área de servicio también se basa en el algoritmo de Dijkstra para recorrer la red. Su objetivo es devolver un subconjunto de entidades de borde conectadas tal que se encuentren dentro de la distancia de red o la tolerancia de costes especificada; además, puede devolver las líneas clasificadas por un conjunto de valores de corte dentro de los que pueden caer los bordes. El solucionador de área de servicio puede generar líneas, polígonos que rodean estas líneas, o ambos.
Los polígonos se generan colocando la geometría de las líneas recorridas por el solucionador Área de servicio en una estructura de datos de red irregular de triángulos (TIN). La distancia de red a lo largo de las líneas sirve como alto de las ubicaciones dentro del TIN. Las ubicaciones no recorridas por el área de servicio se colocan con un valor de altura mucho mayor. Con esta TIN se utiliza una rutina de generación de polígonos para crear regiones que abarquen áreas entre los valores de corte especificados. El algoritmo de generación de polígonos tiene lógica adicional para producir los polígonos generalizados o detallados, y afrontar los muchos casos especiales que se pueden encontrar.
Ubicación-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. Éste es un problema combinatorio de tipo N elige P, y el espacio de soluciones se hace sumamente grande. No se puede obtener soluciones óptimas examinando todas las combinaciones. Por ejemplo, incluso un problema pequeño como 100 elige 10 contiene más de 17 billones 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 diferentes. 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 creando un grupo de buenas soluciones. A continuación, 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-asignación