Routenzuweisung - Route assignment

Eine kurze Geschichte der Verkehrstechnik

Die Routenzuweisung , Routenauswahl oder Verkehrszuweisung betrifft die Auswahl von Routen (alternativ als Pfade bezeichnet) zwischen Ursprüngen und Zielen in Transportnetzen . Es ist der vierte Schritt in dem herkömmlichen Transportprognosemodell folgende Verkehrserzeugung , Verkehrsverteilung und Moduswahl . Die zonale Austauschanalyse der Reiseverteilung liefert Abflugtabellen für Ursprung und Ziel. Die Analyse der Modusauswahl zeigt an, welche Reisenden welchen Modus verwenden . Um den Bedarf an Einrichtungen sowie Kosten und Nutzen zu ermitteln, müssen wir die Anzahl der Reisenden auf jeder Route und Verbindung des Netzwerks kennen (eine Route ist einfach eine Kette von Verbindungen zwischen Ursprung und Ziel). Wir müssen Verkehrs- (oder Reise-) Aufgaben übernehmen. Angenommen, es gibt ein Netz von Autobahnen und Verkehrssystemen und eine vorgeschlagene Ergänzung. Wir wollen zuerst das gegenwärtige Muster der Verkehrsverzögerung kennen und dann wissen, was passieren würde, wenn die Hinzufügung vorgenommen würde.

Allgemeine Ansätze

Langjährige Techniken

Das Problem der Schätzung, wie viele Benutzer sich auf jeder Route befinden, besteht seit langem. Die Planer begannen, sich intensiv damit zu beschäftigen, als Autobahnen und Schnellstraßen ausgebaut wurden. Die Autobahn bot ein überlegenes Serviceniveau gegenüber dem lokalen Straßennetz und leitete den Verkehr vom lokalen System ab. Ablenkung war zunächst die Technik. Es wurden Reisezeitverhältnisse verwendet, die unter Berücksichtigung von Kosten, Komfort und Servicelevel gemildert wurden .

Die Forscher der Chicago Area Transportation Study (CATS) entwickelten Umleitungskurven für Autobahnen im Vergleich zu lokalen Straßen. Auch in Kalifornien gab es viel Arbeit, denn Kalifornien hatte frühe Erfahrungen mit der Autobahnplanung. Zusätzlich zu einer Art Umleitungsarbeit hat das CATS einige technische Probleme angegriffen, die auftreten, wenn man mit komplexen Netzwerken arbeitet. Ein Ergebnis war der Bellman-Ford-Moore-Algorithmus zum Auffinden kürzester Wege in Netzwerken.

Das Problem, das der Umleitungsansatz nicht behandelte, war das Feedback aus der Verkehrsmenge auf Verbindungen und Routen. Wenn viele Fahrzeuge versuchen, eine Einrichtung zu nutzen, wird die Einrichtung überlastet und die Reisezeit verlängert sich. In Ermangelung einer Möglichkeit, Rückmeldungen zu berücksichtigen, ignorierten frühe Planungsstudien (tatsächlich die meisten im Zeitraum 1960-1975) Rückmeldungen. Sie verwendeten den Moore-Algorithmus, um kürzeste Pfade zu bestimmen, und ordneten den gesamten Verkehr den kürzesten Pfaden zu. Dies wird als Alles-oder-Nichts-Zuweisung bezeichnet, da sich entweder der gesamte Verkehr von i nach j entlang einer Route bewegt oder nicht.

Die Alles-oder-Nichts- oder kürzeste Pfadzuweisung ist aus technisch-rechnerischer Sicht nicht trivial. Jede Verkehrszone ist mit n - 1 Zonen verbunden, sodass zahlreiche Pfade zu berücksichtigen sind. Darüber hinaus sind wir letztendlich am Verkehr auf Links interessiert. Eine Verbindung kann Teil mehrerer Pfade sein, und der Verkehr entlang von Pfaden muss Link für Link summiert werden.

Es kann ein Argument für den Alles-oder-Nichts-Ansatz vorgebracht werden. Es geht so: Die Planungsstudie soll Investitionen unterstützen, damit auf allen Links ein gutes Serviceniveau verfügbar ist. Anhand der mit dem geplanten Servicelevel verbundenen Fahrzeiten geben Berechnungen an, wie der Verkehr fließen wird, sobald Verbesserungen vorgenommen wurden. Bei Kenntnis der Verkehrsmengen auf Verbindungen kann die Kapazität berechnet werden, die bereitgestellt werden muss, um das gewünschte Serviceniveau zu erreichen.

Heuristische Verfahren

Um die Auswirkung der Verkehrsbelastung auf die Fahrzeiten und das Verkehrsgleichgewicht zu berücksichtigen, wurden mehrere heuristische Berechnungsverfahren entwickelt. Eine Heuristik wird schrittweise ausgeführt. Der zuzuweisende Verkehr ist in Teile unterteilt (normalerweise 4). Weisen Sie den ersten Teil des Datenverkehrs zu. Berechnen Sie neue Fahrzeiten und weisen Sie den nächsten Teil des Verkehrs zu. Der letzte Schritt wird wiederholt, bis der gesamte Verkehr zugewiesen ist. Die CATS verwendeten eine Variation davon; es wurde zeilenweise in der OD-Tabelle zugewiesen.

Die in der FHWA- Sammlung von Computerprogrammen enthaltene Heuristik geht einen anderen Weg.

• 0. Laden Sie zunächst den gesamten Datenverkehr mit einem Alles-oder-Nichts-Verfahren.
• 1. Berechnen Sie die resultierenden Fahrzeiten und weisen Sie den Verkehr neu zu.
• 2. Beginnen Sie nun mit der Neuzuweisung mit Gewichten. Berechnen Sie die gewichteten Fahrzeiten in den beiden vorherigen Ladungen und verwenden Sie diese für die nächste Zuordnung. Die letzte Iteration wird mit 0,25 und die vorherige mit 0,75 gewichtet.
• 3. Fahren Sie fort.

Diese Verfahren scheinen "ziemlich gut" zu funktionieren, sind aber nicht genau.

Frank-Wolfe-Algorithmus

Dafermos (1968) wandte den Frank-Wolfe-Algorithmus (1956, Florian 1976) an, mit dem das Problem des Verkehrsgleichgewichts gelöst werden kann. Angenommen, wir erwägen ein Autobahnnetz. Für jede Verbindung gibt es eine Funktion, die die Beziehung zwischen Widerstand und Verkehrsaufkommen angibt. Das Bureau of Public Roads (BPR) hat eine Funktion für Überlastungen (oder Volumenverzögerungen oder Verbindungsleistungen) entwickelt, die wir als S _a (v _a ) bezeichnen werden.

${\ displaystyle S_ {a} \ left ({v_ {a}} \ right) = t_ {a} \ left ({1 + 0,15 \ left ({\ frac {v_ {a}} {c_ {a}}) \ right) ^ {4}} \ right)}$

• t _a = freie Flusslaufzeit auf Verbindung a pro Zeiteinheit
• v _a = Verkehrsaufkommen auf Verbindung a pro Zeiteinheit (etwas genauer: Fluss, der versucht, Verbindung a zu verwenden ).
• c _a = Verbindungskapazität a pro Zeiteinheit
• S _a (v _a ) ist die durchschnittliche Reisezeit für ein Fahrzeug auf Verbindung a

Es gibt andere Überlastungsfunktionen. Das CATS verwendet seit langem eine andere Funktion als das BPR, aber es scheint kaum einen Unterschied zwischen den Ergebnissen zu geben, wenn die CATS- und BPR-Funktionen verglichen werden.

Gleichgewichtszuordnung

Um Pfaden und Verbindungen Verkehr zuzuweisen, müssen Regeln gelten, und es gibt die bekannten Wardrop-Gleichgewichtsbedingungen . Das Wesentliche dabei ist, dass Reisende sich bemühen, den kürzesten (am wenigsten widerstandsfähigen) Weg vom Ursprung zum Ziel zu finden, und ein Netzwerkgleichgewicht entsteht, wenn kein Reisender den Reiseaufwand verringern kann, indem er auf einen neuen Weg wechselt. Diese werden als benutzeroptimale Bedingungen bezeichnet, da kein Benutzer von der Änderung der Fahrwege profitieren wird, sobald sich das System im Gleichgewicht befindet.

Das optimale Gleichgewicht des Benutzers kann durch Lösen des folgenden nichtlinearen Programmierproblems gefunden werden

${\ displaystyle \ min \ sum _ {a} {\ int _ {0} ^ {v_ {a}} {S_ {a} \ left (x \ right)}} dx}$

vorbehaltlich:

${\ displaystyle v_ {a} = \ sum _ {i} {\ sum _ {j} {\ sum _ {r} {\ alpha _ {ij} ^ {ar} x_ {ij} ^ {r}}} }}$

${\ displaystyle \ sum _ {r} {x_ {ij} ^ {r} = T_ {ij}}}$

${\ displaystyle v_ {a} \ geq 0, \; x_ {ij} ^ {r} \ geq 0}$

wo ist die Anzahl der Fahrzeuge auf dem Weg r vom Ursprung i zum Ziel j . Die Einschränkung (2) besagt also, dass alle Reisen stattfinden müssen - i = 1 ... n; j = 1 ... n${\ displaystyle x_ {ij} ^ {r}}$

${\ displaystyle \ alpha _ {ij} ^ {ar}}$= 1, wenn sich die Verbindung a auf dem Weg r von i nach j befindet; sonst Null. Die Einschränkung (1) summiert also den Verkehr auf jeder Verbindung. Für jede Verbindung im Netzwerk gibt es eine Einschränkung. Die Einschränkung (3) stellt keinen negativen Verkehr sicher.

Beispiel

Ein Beispiel von Eash, Janson und Boyce (1979) wird die Lösung des nichtlinearen Programmproblems veranschaulichen. Es gibt zwei Verbindungen von Knoten 1 zu Knoten 2, und für jede Verbindung gibt es eine Widerstandsfunktion (siehe Abbildung 1). Bereiche unter den Kurven in Abbildung 2 entsprechen der Integration von 0 zu a in Gleichung 1, sie summieren sich auf 220.674. Beachten Sie, dass die Funktion für Link b in umgekehrter Richtung dargestellt ist.

${\ displaystyle S_ {a} = 15 \ left ({1 + 0.15 \ left ({\ frac {v_ {a}} {1000}} \ right) ^ {4}} \ right)}$

${\ displaystyle S_ {b} = 20 \ left ({1 + 0,15 \ left ({\ frac {v_ {b}} {3000}} \ right) ^ {4}} \ right)}$

${\ displaystyle v_ {a} + v_ {b} = 8000}$

Abbildung 1: Zwei-Routen-Netzwerk

Abbildung 2: Grafische Lösung des Gleichgewichtszuordnungsproblems

Abbildung 3: Zuordnung von Fahrzeugen, die die Gleichgewichtsbedingung nicht erfüllen

Im Gleichgewicht befinden sich 2.152 Fahrzeuge auf Verbindung a und 5847 auf Verbindung b . Die Reisezeit ist auf jeder Route gleich: ca. 63.

Abbildung 3 zeigt eine Zuordnung von Fahrzeugen, die nicht mit der Gleichgewichtslösung übereinstimmt. Die Kurven sind unverändert. Bei der neuen Zuordnung von Fahrzeugen zu Routen muss der schattierte Bereich in die Lösung einbezogen werden, sodass die Lösung in Abbildung 3 um den Bereich des schattierten Bereichs größer ist als die Lösung in Abbildung 2.

Reisewahlen integrieren

Das städtische Verkehrsplanungsmodell wurde als eine Reihe von Schritten entwickelt, die befolgt werden müssen, und Modelle wurden für die Verwendung in jedem Schritt entwickelt. Manchmal gab es Schritte in Schritten, wie es bei der ersten Aussage des Lowry-Modells der Fall war . In einigen Fällen wurde festgestellt, dass Schritte integriert werden können. Im Allgemeinen abstrahieren die Schritte von Entscheidungen, die gleichzeitig getroffen werden können, und es wäre wünschenswert, dies in der Analyse besser zu wiederholen.

Disaggregierte Nachfragemodelle wurden zuerst entwickelt, um das Problem der Modusauswahl zu behandeln. Bei diesem Problem wird davon ausgegangen, dass man sich für eine Reise entschieden hat, wohin diese Reise führen wird und zu welcher Zeit die Reise durchgeführt wird. Sie wurden verwendet, um den implizierten breiteren Kontext zu behandeln. In der Regel wird ein verschachteltes Modell entwickelt, das beispielsweise mit der Wahrscheinlichkeit einer Reise beginnt , dann die Auswahl zwischen Orten untersucht und dann den Modus auswählt. Die Reisezeit ist etwas schwieriger zu behandeln.

Wilsons doppelt eingeschränktes Entropiemodell war der Ausgangspunkt für Bemühungen auf aggregierter Ebene. Dieses Modell enthält die Einschränkung

${\ displaystyle t_ {ij} c_ {ij} = C}$

Dabei handelt es sich um die Verbindungsreisekosten, die sich auf den Verkehr auf einer Verbindung beziehen, und C ist eine Ressourcenbeschränkung, die beim Anpassen des Modells an Daten angepasst werden muss. Anstatt diese Form der Beschränkung zu verwenden, kann die bei der Verkehrszuweisung verwendete monoton ansteigende Widerstandsfunktion verwendet werden. Das Ergebnis bestimmt die Bewegungen von Zone zu Zone und weist den Netzwerken Verkehr zu. Dies ist aus der Art und Weise, wie man sich das System vorstellen würde, sehr sinnvoll. Der Verkehr von Zone zu Zone hängt vom Widerstand ab, der durch Überlastung verursacht wird. ${\ displaystyle c_ {ij}}$${\ displaystyle t_ {ij}}$

Alternativ kann die Verbindungswiderstandsfunktion in der Zielfunktion enthalten sein (und die Gesamtkostenfunktion aus den Einschränkungen eliminiert werden).

Ein verallgemeinerter Ansatz der disaggregierten Auswahl hat sich ebenso entwickelt wie ein verallgemeinerter aggregierter Ansatz. Die große Frage ist die der Beziehungen zwischen ihnen. Wenn wir ein Makromodell verwenden, möchten wir wissen, welches disaggregierte Verhalten es darstellt. Wenn wir eine Mikroanalyse durchführen, möchten wir die aggregierten Auswirkungen der Analyse kennen.

Wilson leitet ein schwerkraftähnliches Modell mit gewichteten Parametern ab, die etwas über die Attraktivität von Herkunft und Ziel aussagen. Ohne zu viel Mathematik können wir Wahrscheinlichkeitsaussagen basierend auf der Attraktivität schreiben, und diese haben eine ähnliche Form wie einige Arten von disaggregierten Nachfragemodellen.

Integration der Reiseanforderung in die Routenzuweisung

Es ist seit langem bekannt, dass die Nachfrage nach Reisen vom Netzangebot beeinflusst wird. Das Beispiel einer neuen Brückenöffnung, bei der keine zuvor zusätzlichen Verkehr ausgelöst hat, ist seit Jahrhunderten bekannt. Es wurde viel geforscht, um Methoden zu entwickeln, mit denen das Prognosesystem dieses Phänomen direkt berücksichtigen kann. Evans (1974) veröffentlichte eine Dissertation über eine mathematisch strenge Kombination des Schwerkraftverteilungsmodells mit dem Gleichgewichtszuweisungsmodell. Das früheste Zitat dieser Integration ist die Arbeit von Irwin und Von Cube, wie sie von Florian et al. (1975), die die Arbeit von Evans kommentieren:

"Die Arbeit von Evans ähnelt in gewisser Weise den von Irwin und Von Cube ['Kapazitätsbeschränkung in Zuweisungsprogrammen für mehrere Reisemodi' HRB Bulletin 347 (1962)] für eine Transportstudie von Toronto entwickelten Algorithmen . Ihre Arbeit ermöglicht Rückmeldungen zwischen überlasteten Zuweisungen und Auslöseverteilung, obwohl sie sequentielle Prozeduren anwenden. Ausgehend von einer anfänglichen Lösung des Verteilungsproblems werden die interzonalen Auslösungen den anfänglich kürzesten Routen zugewiesen. Für aufeinanderfolgende Iterationen werden neue kürzeste Routen berechnet und ihre Längen als Zugriffszeiten für die Eingabe verwendet das Verteilungsmodell. Die neuen interzonalen Flüsse werden dann in einem gewissen Verhältnis zu den bereits gefundenen Routen zugewiesen. Die Prozedur wird gestoppt, wenn die interzonalen Zeiten für die aufeinanderfolgende Iteration quasi gleich sind. "

Florian et al. schlugen eine etwas andere Methode zur Lösung der kombinierten Verteilungszuordnung vor, bei der der Frank-Wolfe-Algorithmus direkt angewendet wurde. Boyce et al. (1988) fassen die Forschung zu Netzwerkgleichgewichtsproblemen zusammen, einschließlich der Zuordnung mit elastischer Nachfrage.

Diskussion

Ein Drei-Verbindungs-Problem kann nicht grafisch gelöst werden, und die meisten Transportnetzprobleme betreffen eine große Anzahl von Knoten und Verbindungen. Eash et al. Untersuchten beispielsweise das Straßennetz in DuPage County, wo es etwa 30.000 Einbahnstraßen und 9.500 Knoten gab. Da die Probleme groß sind, wird ein Algorithmus benötigt, um das Zuweisungsproblem zu lösen, und der Frank-Wolfe-Algorithmus (mit verschiedenen modernen Modifikationen seit der Erstveröffentlichung) wird verwendet. Beginnen Sie mit einer Alles-oder-Nichts-Zuweisung und befolgen Sie dann die von Frank-Wolfe entwickelte Regel, um zum Mindestwert der Zielfunktion zu iterieren. (Der Algorithmus wendet aufeinanderfolgende mögliche Lösungen an, um eine Konvergenz zur optimalen Lösung zu erreichen. Er verwendet ein effizientes Suchverfahren, um die Berechnung schnell zur optimalen Lösung zu bewegen.) Die Fahrzeiten entsprechen den beiden Variablen in diesem Programmierproblem.

Es ist interessant, dass der Frank-Wolfe-Algorithmus 1956 verfügbar war. Seine Anwendung wurde 1968 entwickelt, und es dauerte fast zwei weitere Jahrzehnte, bis der erste Gleichgewichtszuweisungsalgorithmus in häufig verwendete Transportplanungssoftware ( Emme und Emme / 2 , entwickelt) eingebettet wurde von Florian und anderen in Montreal). Wir möchten aus der langsamen Anwendungsbeobachtung keine allgemeinen Schlussfolgerungen ziehen, hauptsächlich weil wir Gegenbeispiele über das Tempo und Muster der Technikentwicklung finden können. Zum Beispiel wurde die Simplex-Methode zur Lösung linearer Programmierprobleme ausgearbeitet und weit verbreitet angewendet, bevor ein Großteil der Programmiertheorie entwickelt wurde.

Die Problemstellung und der Algorithmus haben allgemeine Anwendungen im Tiefbau - Hydraulik, Bauwerke und Konstruktion. (Siehe Hendrickson und Janson 1984).

Empirische Studien zur Routenwahl

Routenzuweisungsmodelle basieren zumindest teilweise auf empirischen Studien darüber, wie Personen Routen in einem Netzwerk auswählen . Solche Studien konzentrieren sich im Allgemeinen auf einen bestimmten Modus und verwenden entweder angegebene Präferenzmodelle oder offenbarte Präferenzmodelle .

Fahrrad

Es wurde festgestellt, dass Radfahrer ausgewiesene Radwege bevorzugen und steile Hügel meiden.

Öffentlicher Verkehr

Der öffentliche Verkehr wurde lange Zeit im Zusammenhang mit der Routenzuweisung berücksichtigt, und es wurden viele Studien zur Wahl der Transitroute durchgeführt. Unter anderem versuchen Transitbenutzer, die Gesamtreisezeit, die Zeit oder die Entfernung zu Fuß und die Anzahl der Transfers zu minimieren.

Siehe auch

• Routenwahl (Begriffsklärung)

Anmerkungen

Allgemeine Referenzen

• Dafermos, Stella. C. und FT Sparrow Das Problem der Verkehrszuweisung für ein allgemeines Netzwerk. "J. of Res. Des National Bureau of Standards, 73B, S. 91-118. 1969.
• Florian, Michael ed., Verkehrsgleichgewichtsmethoden, Springer-Verlag, 1976.
• Eash, Ronald, Bruce N. Janson und David Boyce Equilibrium Trip Assignment: Vorteile und Implikationen für die Praxis, Transportation Research Record 728, S. 1–8, 1979.
• Evans, Suzanne P .. "Ableitung und Analyse einiger Modelle zur Kombination von Reiseverteilung und -zuweisung." Transportation Research, Band 10, S. 37–57 1976
• Hendrickson, CT und BN Janson, "Eine gemeinsame Netzwerkflussformulierung für mehrere Tiefbauprobleme" Civil Engineering Systems 1 (4), S. 195–203, 1984