Von der Erweiterung Erweiterung "ArcGIS Network Analyst" verwendete Algorithmen
Die Routen-Solver in der Erweiterung Erweiterung "ArcGIS Network Analyst" – d. h. der Routen-, Nächste Einrichtung- und Start-Ziel-Kostenmatrix-Solver – basieren auf dem bekannten Dijkstra-Algorithmus zum Suchen des kürzesten Weges. In jedem der drei 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 können, 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 einen Satz von Knoten S, für die der kürzeste Weg von s bereits berechnet wurde. Der Algorithmus sucht wiederholt einen Knoten im Satz von Knoten, der die geringste Schätzung für den kürzesten Weg aufweist, fügt ihn dem Satz von Knoten 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
Hierbei wird der bekannte Dijkstra-Algorithmus verwendet, der oben beschrieben wird.
Nächste Einrichtung
Hierbei 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
Hierbei 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.
Der übergeordnete Ziel ist hierbei, die Impedanz zu minimieren und gleichzeitig die Hierarchie der höheren Rangstufe im Netzwerk zu bevorzugen. Hierzu 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 intern intensiv untersucht und entwickelt, um schnell gute Ergebnisse zu erzielen.
Vehicle Routing Problem mit Zeitfenstern
Das Vehicle Routing Problem (VRP) ist ein erweiterte Version des Problem des Handlungsreisenden. 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-Suchen-Metaheuristik und ist proprietär. Sie wurde jedoch bei Esri intern über mehrere Jahre ständig bearbeitet und entwickelt und führt schnell zu guten Ergebnissen.
Weitere Informationen zum Lösen eines Vehicle Routing Problem
Einzugsgebiet
Der Einzugsgebiet-Solver basiert ebenfalls auf dem Dijkstra-Algorithmus zum Durchqueren des Netzwerks. Das Ziel besteht darin, einen Teilsatz von verbundenen Kanten-Features zurückzugeben, die sich in dem angegebenen Grenzbereich für Netzwerkdistanz oder Kosten befinden. Außerdem können die Linien 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 generiert, indem die Geometrie der Linien, die der Einzugsgebiet-Solver durchquert, in eine TIN-Datenstruktur (Triangulated Irregular Network, Unregelmäßiges Dreiecksnetz) eingefügt wird. Die Netzwerkentfernung entlang dieser Linien dient als Höhe der Standorte im TIN. Standorte, die vom Einzugsgebiet nicht durchlaufen werden, werden mit einem deutlich höheren Wert für die Höhe eingefügt. Mit diesem TIN wird eine Routine für die Polygonerstellung verwendet, um Bereiche zu isolieren, die Bereiche zwischen den angegebenen Unterbrechungswerten umschließen. Der Algorithmus zum Generieren von Polygonen verfügt über zusätzliche Logik, um die generalisierten oder detaillierten Polygone zu erstellen und die Vielzahl von Sonderfällen zu behandeln, die vorkommen können.
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 anderer Problemtypen heuristisch zu lösen. Der Location-Allocation-Solver generiert dann einen Satz von halbzufälligen 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 dann 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