Cálculo de rutas óptimas mientras toca todas las carreteras disponibles en la red ArcGIS?

13

Para la preparación de la temporada de invierno, queremos calcular las rutas más óptimas para rociar sal en las carreteras. El análisis conoce los siguientes criterios:

  • los vehículos comienzan y se detienen en un solo punto de carga
  • todos los caminos disponibles deben ser rociados con sal
  • una ruta no puede durar más de un tiempo de certificación (supongamos 2 horas)
  • Debido a la carga limitada de sal por vehículo, la distancia de una ruta se limita a la cantidad de sal disponible. (supongamos 10 km)

El analista de red de ArcGIS (10.0) asume que tiene un punto de inicio y un punto final para calcular la ruta. Sin embargo, en este caso no se trata de calcular la ruta más rápida desde el origen hasta el destino, sino sobre las rutas más óptimas para cubrir la mayor distancia posible de la carretera dentro de un período de tiempo limitado.

Ahora estamos pensando en calcular puntos medios para cada sección del camino y usarlos como destinos para calcular la ruta.

Mark Verschuur
fuente
2
Esto se parece mucho a la ruta del camión de basura solo cuando los camiones regresan al depósito para vaciarse mientras que aquí se vuelve a cargar la sal. Ambos necesitan visitar todas las partes de una red.
PolyGeo
Muy cierto. ¿Tiene consejos para resolver este tipo de preguntas de enrutamiento?
Mark Verschuur
En nuestra jurisdicción tenemos una variable adicional, que es Sand. dado que las carreteras de menor volumen obtienen arena y las de mayor volumen obtienen sal. Si desea iniciar una sala de chat conmigo y podemos discutir el problema por completo. También puedo darle una idea de lo que hemos hecho y si nuestras soluciones pueden compararse
dassouki
Se puede reducir a un problema de recogida y entrega de vehículos múltiples y hay muchos documentos al respecto.
Jakub Kania

Respuestas:

5

Creo que parte de la respuesta depende del diseño de la red de carreteras, y vale la pena publicar esta pregunta en Math Stack Exchange ( /math// ), ya que parece un problema de teoría de grafos. No creo que esta sea la solución óptima, pero podría ayudarlo a acercarse.

Podría dividir la red de carreteras en regiones naturales, donde la suma de la longitud de los segmentos será aproximadamente igual a la cantidad que un camión podría cubrir con una carga determinada. Luego, para cada región, puede realizar un recorrido eularian para obtener la ruta que tocaría todos los segmentos. Código de Python de muestra

def eulerian_tour(network_graph):
    graph = network_graph[:]
    route = []
    def find_route(start):
        for (i, j) in graph:
            if i == start:
                graph.remove((i, j))
                find_route(j)
            elif j == start:
                graph.remove((i, j))
                find_route(i)
        route.append(start)

    find_route(graph[0][0])
    route.reverse()
    return route

Luego, puede considerar el enrutamiento entre regiones y el depósito, y dividir la ruta de acceso en segmentos lógicos para los camiones disponibles. Espero que esto ayude.

Guindilla
fuente
1

Enfocaría esta tarea de esta manera. ArcGIS Network Analyst tiene un solucionador llamado VRP , que puede ayudarlo a ordenar y administrar sus rutas. Convertiría cada enlace de carretera que tenga en su dataset de red a entidades de puntos ( herramienta GP de Característica a punto (Gestión de datos) , por ejemplo, o tal vez primero dividir líneas en segmentos simples de dos vértices y luego obtener un centro para convertirse en un punto central )

Hablando en términos de VRP, esos se convertirán en sus pedidos. Luego asigna sus rutas limitándolas a un cierto tiempo (2 horas), y su lugar de depósito será tanto el punto de inicio como el de parada. Suponiendo que tiene múltiples vehículos, podrá obtener múltiples rutas para un vehículo o múltiples rutas para el mismo vehículo.

Recomiendo ir a través de un tutorial que lo ayudará a comprender cómo comenzar con VRP en Network Analyst. Yo mismo utilicé este solucionador para múltiples proyectos y descubrí que es extremadamente potente y personalizable en gran medida para satisfacer el flujo de trabajo de mi negocio.

Recuerde que Network Analyst funcionaría bien con un número limitado de pedidos de entrada (en su caso, centroide de carreteras). Tuve éxito con varios miles de pedidos (hasta 9,000). Entonces, si desea servir a una ciudad realmente grande, puede limitar sus rutas para operar solo dentro de ciertas partes de la ciudad (en términos de VRP - Zonas de ruta).

Si está buscando una solución más innovadora y potente diseñada específicamente para el enrutamiento de puntos de alta densidad, considere usar RouteSmart . Está construido sobre ArcGIS y fue diseñado para resolver este tipo de problemas.

Alex Tereshenkov
fuente
Gracias por las sugerencias Definitivamente veré RouteSmart
Mark Verschuur el