Die Routing-Solver in der ArcGIS Network Analyst extension – d. h. der Routen-Solver, der Solver für die nächstgelegene Einrichtung und der Start-Ziel-Kostenmatrix-Solver – basieren auf dem bekannten Dijkstra-Algorithmus zum Suchen des kürzesten Wegs. In jedem Solver werden zwei Typen von Algorithmen zur Wegbestimmung verwendet. Der erste Typ ist der genaue kürzeste Weg, und der zweite ist ein hierarchischer Weg-Solver für eine schnellere Performance. Der klassische Dijkstra-Algorithmus löst ein Problem des kürzesten Wegs für einen nicht gerichteten, nicht negativ gewichteten Graphen. Für die Verwendung im Kontext von Transportdaten in der Praxis wird dieser Algorithmus so geändert, dass Benutzereinstellungen wie Beschränkungen für Einbahnstraßen und Wenden, Knotenimpedanzen, Barrieren und Einschränkungen für die Straßenseite berücksichtigt werden und ein vom Benutzer angegebenes Kostenattribut minimiert wird. Die Performance des Dijkstra-Algorithmus wird weiter optimiert, indem bessere Datenstrukturen, z. B. D-Heaps, verwendet werden. Darüber hinaus muss der Algorithmus die Standorte an beliebigen Stellen entlang einer Kante modellieren, nicht nur an Knoten.
Dijkstra-Algorithmus
Der klassische Dijkstra-Algorithmus löst ein Problem des kürzesten Wegs für einen gewichteten Graphen mit einer Quelle. Zum Ermitteln des kürzesten Wegs von einem Startpunkt s zu einem Ziel d verfügt der Dijkstra-Algorithmus über verschiedene Knoten S, für die der kürzeste Weg von s bereits berechnet wurde. Der Algorithmus sucht im Knotensatz wiederholt einen Knoten, der die geringste Schätzung für den kürzesten Weg aufweist, fügt ihn dem Knotensatz "S" hinzu und aktualisiert die Schätzungen für den kürzesten Weg für alle Nachbarn dieses Knotens, die nicht in "S" enthalten sind. Der Algorithmus fährt fort, bis der Zielknoten zu "S" hinzugefügt wird.
Route
Für die Route wird der bekannte Dijkstra-Algorithmus verwendet, der oben beschrieben wird.
Nächstgelegene Einrichtung
Für die nächstgelegene Einrichtung wird ein Algorithmus mit mehreren Ursprüngen und Zielen auf Grundlage des Dijkstra-Algorithmus verwendet. Er verfügt über Optionen, mit denen nur die kürzesten Wege berechnet werden, wenn sie sich in einem bestimmten Grenzwert befinden, oder mit dem eine bestimmte Anzahl von nächstgelegenen Einrichtungen ermittelt werden kann.
Weitere Informationen zum Suchen der nächstgelegenen Einrichtung
Start-Ziel-Kostenmatrix
Für die Start-Ziel-Kostenmatrix wird ein Algorithmus mit mehreren Ursprüngen und Zielen auf Grundlage des Dijkstra-Algorithmus verwendet. Er verfügt über Optionen, mit denen nur die kürzesten Wege berechnet werden, wenn sie sich in einem bestimmten Grenzwert befinden, oder mit dem eine bestimmte Anzahl von nächstgelegenen Zielen ermittelt werden kann. Der Start-Ziel-Kostenmatrix-Solver ist mit dem Solver für die nächstgelegene Einrichtung vergleichbar. Es wird jedoch nicht die Form des ermittelten kürzesten Pfads berechnet, um den Aufwand zu reduzieren und die Performance zu optimieren.
Weitere Informationen zum Erstellen einer Start-Ziel-Kostenmatrix
Hierarchische Routenerstellung
Die Ermittlung des genauen kürzesten Pfads in einem landesweiten Netzwerk-Dataset ist aufgrund der großen Anzahl von Kanten, die durchsucht werden müssen, sehr zeitaufwändig. Zum Verbessern der Performance können Netzwerk-Datasets die natürliche Hierarchie in einem Transportsystem modellieren, wobei das Befahren einer Autobahn dem Fahren auf Ortsstraßen vorgezogen wird. Wenn ein hierarchisches Netzwerk erstellt wurde, wird mit einer Abwandlung des bidirektionalen Dijkstra eine Route zwischen einem Ursprung und einem Ziel berechnet.
Das übergeordnete Ziel ist hierbei, die Impedanz zu minimieren und gleichzeitig die Hierarchie der höheren Rangstufe im Netzwerk zu bevorzugen. Für die hierarchische Routenerstellung werden gleichzeitig vom Ursprungs- und Zielstandort aus Verbindungs- oder Zufahrtspunkte für Straßen höherer Ebenen gesucht. Anschließend werden die Straßen der höheren Ebenen durchsucht, bis Segmente vom Ursprung und vom Ziel aufeinandertreffen. Da die Suche auf die oberste Hierarchieebene eingeschränkt wird, werden weniger Kanten durchsucht, und die Performance wird verbessert. Es handelt sich um einen heuristischen Algorithmus. Das Ziel sind eine schnelle Performance und gute Lösungen, es kann jedoch nicht garantiert werden, dass der kürzeste Weg gefunden wird. Damit diese Heuristik erfolgreich ist, muss die Hierarchie der obersten Ebene verbunden sein, da bei Erreichen einer Sackgasse nicht auf einer niedrigeren Ebene fortgefahren wird.
Allgemein ist es sinnvoll, diesen Solver in einem hierarchischen Netzwerk zu verwenden, bei dem die Kantengewichtungen auf der Fahrzeit basieren. So wird nachempfunden, wie die Bewegungen in einem Autobahnnetz normalerweise erfolgen.
Option für "Problem des Handlungsreisenden" im Routen-Solver
Der Routen-Solver verfügt über die Option zum Generieren der optimalen Reihenfolge zum Anfahren von Stopp-Standorten. Dies wird als das Problem des Handlungsreisenden oder Traveling Salesman Problem (TSP) bezeichnet. Bei TSP handelt es sich um ein kombinatorisches Problem, d. h. es gibt kein einheitliches Verfahren zum Ermitteln der besten Reihenfolge. Mit Heuristik werden in relativ kurzer Zeit gute Lösungen für diese Art von Problemen ermittelt. Bei der TSP-Implementierung in Network Analyst werden auch Zeitfenster für die Stopps berücksichtigt. Dies bedeutet, dass die optimale Reihenfolge für das Anfahren der Stopps mit minimaler Verspätung gefunden wird.
Der Solver für den Handlungsreisenden generiert zunächst eine Start-Ziel-Kostenmatrix zwischen allen Stopps, für die eine Reihenfolge festgelegt werden soll, und ermittelt mit einem Algorithmus auf Grundlage einer Tabu-Suche die beste Reihenfolge zum Anfahren der Stopps. Bei einer Tabu-Suche handelt es sich um einen metaheuristischen Algorithmus zum Lösen von kombinatorischen Problemen. Es handelt sich dabei um einen Algorithmus für die lokale Suche. Die genaue Implementierung der Tabu-Suche ist proprietär, sie wurde jedoch von Esri intensiv untersucht und entwickelt, um schnell gute Ergebnisse zu erzielen.
Vehicle Routing Problem mit Zeitfenstern
Das Vehicle Routing Problem (VRP) ist ein erweiterte Version von TSP. Beim TSP wird ein Satz von Stopps in die optimale Reihenfolge gebracht. Bei einem VRP muss ein Satz von Aufträgen einem Satz von Routen oder Fahrzeugen so zugewiesen werden, dass die allgemeinen Transportkosten minimiert werden. Außerdem müssen praktische Einschränkungen wie Fahrzeugkapazitäten, Lieferzeitfenster und Spezialisierung der Fahrer berücksichtigt werden. Das VRP führt zu einer Lösung, in der diese Einschränkungen berücksichtigt werden. Gleichzeitig wird eine objektive Funktion minimiert, die aus Betriebskosten und Benutzereinstellungen besteht, z. B. die Gewichtung des Einhaltens von Zeitfenstern.
Der VRP-Solver generiert zunächst eine Start-Ziel-Kostenmatrix der Kosten für den kürzesten Weg zwischen allen Auftrags- und Depot-Standorten im Netzwerk. Anhand dieser Kostenmatrix wird eine erste Lösung erstellt, indem die Aufträge einzeln in die am besten geeignete Route eingefügt werden. Die erste Lösung wird dann optimiert, indem die Aufträge der einzelnen Routen neu angeordnet werden. Außerdem werden Aufträge zwischen Routen verschoben und ausgetauscht. Die in diesem Verfahren verwendete Heuristik basiert auf einer Tabu-Such-Metaheuristik und ist proprietär. Sie wurde jedoch bei Esri über mehrere Jahre ständig bearbeitet und entwickelt und führt schnell zu guten Ergebnissen.
Einzugsgebiet
Der Einzugsgebiet-Solver basiert ebenfalls auf dem Dijkstra-Algorithmus zum Durchqueren des Netzwerks. Das Ziel ist die Rückgabe einer Teilmenge der verbundenen Kanten-Features, die innerhalb der angegebenen Netzwerkentfernung bzw. der Kostengrenze liegen. Darüber hinaus können Linien zurückgegeben werden, die nach einem Satz von Unterbrechungswerten kategorisiert werden, unter die eine Kante fällt. Der Einzugsgebiet-Solver kann Linien, Polygone um diese Linien oder beides generieren.
Die Polygone werden erzeugt, indem die Linien mit einer vom Benutzer angegebenen Entfernung gepuffert werden. Optional können Benutzer hochwertige Polygone bis zu einer vom Benutzer angegebenen Entfernung erstellen, sodass die Polygone die gesamte Fläche enthalten, die näher an den Polygonzuglinien liegt als an den Nicht-Polygonzuglinien.
Location-Allocation
Location-Allocation ist ein Solver für das Standortproblem von Einrichtungen. Das heißt, wenn N geeignete Einrichtungen und M Bedarfspunkte mit einer Gewichtung gegeben sind, wird eine Teilmenge P der Einrichtungen ausgewählt, sodass die Summe der gewichteten Entfernungen von jedem M zum nächsten P minimiert wird. Dies ist ein kombinatorisches Problem des Typs "Auswahl von P aus N", und der Lösungsraum wird sehr groß. Optimale Lösungen können nicht durch die Überprüfung aller Kombinationen ermittelt werden. Beispielsweise enthält sogar ein kleines Problem wie die Auswahl von 10 aus 100 über 17 Billionen Kombinationen. Außerdem verfügt der Location-Allocation-Solver über Optionen zur Lösung einer Vielzahl von Standortproblemen, z. B. zum Minimieren der gewichteten Impedanz, zur Maximierung der Flächendeckung oder zum Erreichen des Ziel-Marktanteils. Zur Lösung von Location-Allocation-Problemen wird Heuristik verwendet.
Der Location-Allocation-Solver generiert zunächst eine Start-Ziel-Kostenmatrix der Kosten für den kürzesten Weg zwischen allen Einrichtungs- und Bedarfspunktstandorten im Netzwerk. Dann wird unter Verwendung eines als Hillsman-Bearbeitung bezeichneten Vorgangs eine bearbeitete Version der Kostenmatrix erstellt. Dieser Bearbeitungsvorgang ermöglicht es diesem allgemeinen Solver, eine Vielzahl von Problemtypen heuristisch zu lösen. Der Location-Allocation-Solver generiert dann verschiedene halbzufällige Lösungen und wendet eine Stützpunktersetzungsheuristik (Teitz und Bart) an, um diese Lösungen zu verfeinern und eine Gruppe guter Lösungen zu erstellen. Mit einer Metaheuristik wird diese Gruppe guter Lösungen kombiniert, um bessere Lösungen zu erzeugen. Wenn keine weitere Verbesserung möglich ist, gibt die Metaheuristik die beste gefundene Lösung zurück. Die Kombination von einer bearbeiteten Matrix, halbzufälligen ersten Lösungen, einer Stützpunktersetzungsheuristik und einer verfeinernden Metaheuristik ergibt schnell nahezu optimale Ergebnisse.
Weitere Informationen zum Ausführen einer Location-Allocation-Analyse