Berechnen Sie optimale Routen, während Sie alle verfügbaren Straßen im ArcGIS-Netzwerk berühren?

13

Zur Vorbereitung der Wintersaison wollen wir die optimalsten Streusalzrouten auf den Straßen berechnen. Die Analyse kennt folgende Kriterien:

  • Fahrzeuge starten und stoppen an einem einzigen Ladepunkt
  • Alle verfügbaren Straßen müssen mit Salz bestreut werden
  • Eine Route kann nicht länger als eine bestimmte Zeit dauern (nehmen wir 2 Stunden an)
  • aufgrund der begrenzten salzmenge pro fahrzeug ist die streckendistanz auf die verfügbare salzmenge begrenzt. (Nehmen wir 10 km an)

Der Netzwerkanalyst von ArcGIS (10.0) geht davon aus, dass Sie einen Start- und einen Endpunkt haben, um die Route zu berechnen. In diesem Fall geht es jedoch nicht darum, die schnellste Route vom Ursprung zum Ziel zu berechnen, sondern um die optimalsten Routen, um innerhalb eines begrenzten Zeitrahmens so viel Straßenentfernung wie möglich zurückzulegen.

Jetzt denken wir darüber nach, für jeden Straßenabschnitt Mittelpunkte zu berechnen und diese als Ziele für die Routenberechnung zu verwenden.

Mark Verschuur
quelle
2
Das klingt sehr nach Müllwagen-Routing, nur dass die LKWs zum Leeren ins Depot zurückkehren, während hier Salz nachgeladen wird. Beide müssen alle Teile eines Netzwerks besuchen.
PolyGeo
Sehr richtig. Haben Sie Tipps zur Lösung dieser Art von Routing-Fragen?
Mark Verschuur
In unserer Gerichtsbarkeit haben wir eine zusätzliche Variable, nämlich Sand. Da Straßen mit geringerem Volumen Sand und Straßen mit höherem Volumen Salz erhalten. Wenn Sie einen Chatroom mit mir einrichten möchten, können wir das Problem ausführlich besprechen. Ich kann Ihnen auch einen Einblick geben, was wir getan haben und ob unsere Lösungen vergleichbar sind
dassouki 17.10.13
Dies kann auf Probleme bei der Abholung und Auslieferung mehrerer Fahrzeuge reduziert werden, und es gibt viele Dokumente dazu.
Jakub Kania
Siehe auch
Chris W

Antworten:

5

Ich denke, ein Teil der Antwort hängt von der Anordnung des Straßennetzes ab, und diese Frage könnte es wert sein, an der Math Stack Exchange ( /math// ) veröffentlicht zu werden, da sie wie ein graphentheoretisches Problem erscheint. Ich denke nicht, dass dies die optimale Lösung sein wird, aber es könnte Ihnen helfen, näher zu kommen.

Sie können das Straßennetz in natürliche Regionen unterteilen, in denen die Summe der Segmentlängen in etwa der Menge entspricht, die ein LKW mit einer bestimmten Ladung zurücklegen kann. Dann könnten Sie für jede Region eine Eular-Tour durchführen, um die Route zu ermitteln, die alle Segmente berühren würde. Beispiel-Python-Code

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

Sie können dann das Routing zwischen Regionen und dem Depot in Betracht ziehen und die Zugriffswege für die verfügbaren LKWs in logische Segmente aufteilen. Hoffe das hilft.

Hotpepper
quelle
1

Ich würde diese Aufgabe so angehen. ArcGIS Network Analyst verfügt über einen Solver namens VRP , mit dem Sie Ihre Routen ordnen und verwalten können. Ich würde jede Straßenverbindung, die Sie in Ihrem Netzwerk-Dataset haben, in Punkt-Features konvertieren ( z. B. das GP-Tool „ Feature to Point (Datenverwaltung)“) oder Linien zuerst in einfache Segmente mit zwei Scheitelpunkten teilen und dann eine Mitte zum Mittelpunkt machen ).

In Bezug auf VRP werden diese zu Ihren Befehlen. Anschließend weisen Sie Ihre Routen einer bestimmten Zeit zu (2 Stunden), und Ihr Depotplatz ist sowohl Start- als auch Endpunkt. Angenommen, Sie haben mehrere Fahrzeuge, können Sie entweder mehrere Routen für ein Fahrzeug oder mehrere Routen für dasselbe Fahrzeug abrufen.

Ich empfehle dringend, das Lernprogramm durchzuarbeiten, um zu verstehen, wie Sie mit VRP in Network Analyst beginnen. Ich habe diesen Solver selbst für mehrere Projekte verwendet und fand ihn äußerst leistungsfähig und in hohem Maße anpassbar, um meinen geschäftlichen Workflow zu erfüllen.

Denken Sie daran, dass Network Analyst mit einer begrenzten Anzahl von Eingabeaufträgen gut funktioniert (in Ihrem Fall - Schwerpunkt der Straßen). Ich war mit mehreren tausend Bestellungen (bis zu 9.000) erfolgreich. Wenn Sie also eine wirklich große Stadt bedienen möchten, können Sie Ihre Routen auf bestimmte Stadtteile beschränken (in Bezug auf VRP - Route Zones).

Wenn Sie eine sofort einsatzbereite und leistungsstarke Lösung suchen, die speziell für das Routen von Punkten mit hoher Dichte entwickelt wurde, sollten Sie RouteSmart in Betracht ziehen . Es basiert auf ArcGIS und wurde entwickelt, um diese Art von Problemen zu lösen.

Alex Tereshenkov
quelle
Danke für die Vorschläge. Ich werde auf jeden Fall RouteSmart
Mark Verschuur