| Volltext |
Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.
1 Einleitung
Die städtische Verkehrsbelastung wächst kontinuierlich – größer werdende Städte und Bevölkerungszuwächse haben das urbane Verkehrsaufkommen in Europa und Nordamerika in den letzten beiden Dekaden verdoppelt und noch höhere Zuwächse allein für die 439 städtischen Gebiete der Vereinigten Staaten von Amerika auf 4,2 Milliarden Stunden und 87,2 Milliarden Dollar innerhalb eines Jahres. Ebenso sind die zusätzlichen Belastungen durch verschwendeten Treibstoff, Lärm und Verschmutzung zu berücksichtigen.
Eine Reduzierung von Verkehrsstaus allein durch einen Ausbau der Straßennetzwerke ist aufgrund der beschränkten Platzverhältnisse in Städten oft unmöglich. Neben der Stärkung des öffentlichen Nahverkehrs muss also die bereits vorhandene Infrastruktur leistungsfähiger gemacht werden. Während die Straßen selbst kaum Einfluss auf die Verkehrssteuerung erlauben, besitzen Kreuzungen mit Lichtsignalanlagen (LSA) zahlreiche Parameter, die für die Optimierung verwendet werden können. Das grundlegende Konzept einer grünen Welle, also die Abstimmung der Lichtsignale entlang einer Durchfahrtsstraße, wurde bereits 1925 und somit nur ein Jahr nach der Installation der ersten Lichtsignalanlage in Deutschland am Potsdamer Platz in Berlin von Adolph zum Patent angemeldet [2]. Aber erst 1964 begannen Morgan und Little [3] mit einer ausführlichen mathematischen Analyse grüner Wellen und präsentieren mit MAXBAND eine graphische Lösung für Freigabezeitba¨ nder und Bandbreitenmaximierung im Raum-Zeit-Diagramm.
Forciert durch leichter verfügbare und preisgünstigere Verkehrsdetektoren (zum Beispiel Induktionsschleifen, Bewegungsmelder, Videokameras) beschäftigt sich die Forschung der letzten Jahre verstärkt mit der adaptiven Steuerung von Verkehr, insbesondere mit LSAs, die schnell auf den tatsächlichen Verkehr reagieren können. Interessante Reglerkonzepte wurden vorgestellt, zum Beispiel [4], dennoch bleibt die hohe Bedeutung der klassischen Festzeitschaltung weiterhin erhalten. Dafü r gibt es zahlreiche Gründe. Zum einen fallen adaptive Systeme bei hohem Verkehrsaufkommen in der Regel auf Festzeitschaltungen zurück, wenn die Sensoren Bedarf auf allen Straßen melden [5]. Zum zweiten basieren Systeme wie SYLVIA+ und SCOOT, die häufig in der Praxis eingesetzt werden, auf Festzeitschaltungen. Diese Schaltung werden durch Freigabezeitanpassung, also Phasendehnung oder Phasenverkürzung der Grünphase, dem aktuellen Verkehrsaufkommen angepasst. Anschließend versuchen spezielle Algorithmen, die ursprünglichen Versatzzeiten im Netzwerk wieder herzustellen. Nicht zuletzt hat sich für volladaptive Systeme gezeigt, dass eine zugrunde liegende Festzeitschaltung helfen kann, ein Aufschaukeln und Degenerieren der adaptiven Lösung zu verhindern [6]. Festzeitschaltungen sind also nicht nur ein mögliches Konzept für die Regelung innersta¨ dtischen Verkehrs, sondern bilden die Basis für viele adaptive Ansätze. Zahlreiche Arbeiten befassen sich daher auch mit der Verbesserung solcher Schaltungen. Optimierungsverfahren für Versatzzeiten zwischen verschiedenen Kreuzungen bei Festzeitschaltungen wurden unter anderem von [7, 8, 9, 10, 11] entwickelt und vorgestellt.
Aus mathematischer Sicht lassen sich die Optimierungsansätze für die Signalanlagenkoordinierung grob in zwei Klassen einteilen. Dabei kann man zwischen heuristischen Optimierungsalgorithmen und exakter mathematischer Programmierung und den jeweils zugrunde liegenden Modellen unterscheiden. Die erste Klasse basiert auf genetischen Algorithmen, Fuzzy- Logik oder neuronalen Netzen. Sie arbeiten oft sehr schnell, aber liefern meist nur Näherungsergebnisse oder lokale Optima, die zwar in der Praxis eine deutliche Verbesserung zum Status quo darstellen können, die tatsächlich optimale Lösung wird jedoch meist nicht gefunden. Ferner bieten diese Verfahren auch keine Möglichkeit, die Qualität der erhaltenen Lösungen durch Schranken oder andere Maße zu bewerten. In der zweiten Klasse können meist nicht alle Modelleigenschaften und Parameter exakt abgebildet werden, aber Optimierungsverfahren, die zum Beispiel auf Linearer Programmierung beruhen, stellen beweisbar gute Lösungen bereit, die zudem auch als Schranken oder Startlo¨sungen für die erste Klasse genutzt werden können. Bei der Optimierung von LSA-Koordinierungen wird oft das Altern von Festzeitschaltungen [12] nicht hinreichend berücksichtigt. Meist ist zu beobachten, dass ehemals sehr effiziente Koordinierungen mit der Zeit schlechter werden. Dies liegt zum einen am steigenden Verkehrsaufkommen, zum anderen kann jeder Eingriff in die Signalpläne die Routenwahl der Nutzer beeinflussen. Verkehrsteilnehmer suchen den schnellsten Weg zu ihrem Ziel und wechseln daher auf gut koordinierte Verkehrsadern. Durch das dadurch gestiegende Verkehrsaufkommen können sie die fein abgestimmte Koordinierung auf ebendieser Straße wieder zerstören. Die Bestimmung von optimalen Koordinierungen steht somit in enger Wechselwirkung mit dem Verkehrsumlegungsproblem. Beide Fragestellungen müssen aus unserer Sicht als eine einheitliche Optimierungsaufgabe betrachtet werden. Allsop und Charlesworth [13] haben hierfür bereits einen teilweise einheitlichen Ansatz studiert und ein iteratives Verfahren präsentiert. Chiou [14] nutzt ein gradientenbasiertes Verfahren für die Berechnung lokaler Optima innerhalb ihres Verkehrsmodells. Neuere Ergebnisse wurden von Bell und Ceylan [15] sowie von Teklu et al. [16] mit genetischer Programmierung erzielt. Möhring et al. [17] gehen ebenfalls von einem iterativen Ansatz aus.
In dieser Arbeit stellen wir einen neuen Ansatz für die gleichzeitige Optimierung der Lichtsignalanlagenkoordinierung und der Verkehrsumlegung vor. Unser Modell basiert auf einem zeitexpandiertem Netzwerk, dass die Periodizität der Lichtsignalanlagen nutzt, um den Zeithorizont zu beschränken. Genauer gesagt nutzen wir eine zyklische Expansion mit einer realistischen Implementierung von Lichtsignalanlagen. Unser Modell erfasst verkehrsabhängige Fahrzeiten, vermeidet aber nichtlineare Fahrzeitfunktionen und ihre aufwändigere Analyse. Stattdessen fußt die Verkehrsumlegung auf separaten Funktionen für Fahrzeit auf den Straßen und Wartezeit an den Lichtsignalanlagen. Für fixierte Koordinierungen kann daher das Umlegungsproblem effizient gelöst werden. Das Problem gleichzeitiger Optimierung von Koordinierung und Umlegung kann als gemischt-ganzzahliges Programm formuliert werden. Dies liefert Garantien für die Qualität der Lösungen und bietet ein einfaches Konzept für die Behandlung von Nutzergleichgewichten.
Diese Arbeit ist wie folgt aufgebaut. In Abschnitt 2 führen wir die benötigten Definitionen und Fachbegriffe ein, bevor wir in Abschnitt 3 das zeitlich expandierte Netzwerk vorstellen; in den folgenden Abschnitten 4 und 5 untersuchen wir Fahrzeiten in unserem Modell und präsentieren Simulationsergebnisse der erhaltenen Lösungen mit VISSIM und MATSim. Abschließend fassen wir die Ergebnisse zusammen und geben einen Ausblick auf weitere Arbeiten.
2 Vorbetrachtung
In diesem Abschnitt werden wir einige grundlegende Definitionen und Zusammenhänge skizzieren, die für das Verständnis des Modells und der damit erzielten Ergebnisse benötigt werden. Aufgrund der zahlreichen Aspekte innerstädtischen Verkehrs konzentrieren wir uns auf Konzepte für Lichtsignalanlagen und Verkehrsumlegung. Lichtsignalanlagen an Kreuzungen sind durch verschiedene Parameter gekennzeichnet: insbesondere sind das Umlaufzeit, Freigabezeiten, Anordnung der Phasen und der Versatz zwischen den Signalanlagen an benachbarten Kreuzungen. Im Falle von Festzeitschaltungen hat jede einzelne Lichtsignalanlage eine charakteristische Signalfolge (Sequenz) von Rot und Grün, die regelmäßig mit Umlaufzeit Γ wiederholt wird. Das Verhältnis zwischen rot und grün bezeichnen wir mit Rot-Grün-Split. Im Signalzeitenplan sind die Längen und der (innere) Versatz der Grünzeiten festgelegt. Daraus ergeben sich auch entsprechende Zwischenzeiten, die zur Räumung der Konfliktflächen benötigt werden, also das kollisionsfreie Queren der Kreuzung ermöglichen.
Wenn alle Lichtsignalanlagen eines Straßennetzwerkes die gleiche Umlaufzeit haben, kann der Versatz der Kreuzungen bezüglich einer einheitlichen Systemzeit untersucht werden. Wenn ein Fahrzeug t Zeiteinheiten benötigt, um die Strecke zwischen zwei aufeinander folgenden Kreuzungen zu überwinden, und die Freigabezeit der Signalgruppe an der zweiten Kreuzung beginnt exakt t Zeiteinheiten nach der Grünphase an der ersten Kreuzung, dann existiert ein durchgehendes Grünband und das Fahrzeug erfährt eine grüne Welle.
Bild 1: Signalzeitenpläne für zwei Lichtsignalanlagen
Die wichtigsten Parameter von Lichtsignalanlagen sind in Abbildung 1 graphisch dargestellt. Alle diese Parameter können grundsätzlich für die Optimierung betrachtet werden, wobei natürlich gewisse Randbedingungen wie zum Beispiel minimale Freigabezeiten etc. berücksichtigt werden müssen. Wir konzentrieren uns in dieser Arbeit auf den Versatz zwischen aufeinanderfolgenden Lichtsignalanlagen und nehmen alle anderen Parameter als fixiert an. Zusätzlich setzen wir eine gemeinsame Umlaufzeit voraus. Diese Annahme ist allerdings nicht einschränkend: wenn verschiedene Umlaufzeiten auftreten, kann stattdessen das kleinste gemeinsame Vielfache als gemeinsame Umlaufzeit genutzt werden.
Das Straßennetzwerk stellen wir als gerichteten Graphen G = (V, A) mit Knotenmenge V und Kantenmenge A dar. Wir werden im Weiteren die Bezeichnungen aus Tabelle 1 verwenden.
Tabelle 1: Notation für Lichtsignalanlagen in einem Straßennetzwerk
Um den Nutzen einer Lichtsignalanlagenoptimierung zu bewerten, können zahlreiche Kriterien herangezogen werden. Am gebräuchlichsten ist die durchschnittliche Wartezeit oder die Anzahl der Anhaltevorgänge (Stops). Auch gewichtete Kombinationen dieser beiden Größen werden genutzt. Sun et al. [18] zeigen, dass die Umlaufzeit großen Einfluss auf diese Größen hat. Lange Umlaufzeiten verringern Stops, während kürzere Umlaufzeiten zu geringeren Wartezeiten führen.
Da in unserem Modell gleichzeitig optimale Lichtsignalanlagenkoordinierungen und Verkehrsumlegungen berechnet werden, nutzen wir die Gesamtreisezeit aller Verkehrsteilnehmer als Optimalitätskriterium. Die Fahrer können beliebige Routen wählen. Wenn nur Stops und Wartezeiten zur Bewertung herangezogen würden, könnte ein Verkehrsteilnehmer lange Umwege wählen, um Stops oder Wartezeiten zu vermeiden. Wir nehmen an, dass die meisten Verkehrsteilnehmer am schnellsten Weg zwischen ihrem Start und Zielort interessiert sind. LSAs sollen so geschalten werden, dass den Verkehrsteilnehmern eine möglichst geringe Gesamtreisezeit ermöglicht wird. Die Optimierung der Versatzzeiten bezeichnen wir als Signalkoordinierungsproblem.
Um Verkehrsumlegung zu definieren, benötigen wir das Konzept der Flüsse und Mehrgüter- Flüsse aus der kombinatorischen Optimierung. Aufgrund des Umfangs der zugrunde liegenden Theorie verweisen wir hier auf ein Standardwerk zu Netzwerkoptimierung [19]. Kurz zusammengefasst ist ein Fluss eine Funktion f : A 1→ R≥0, die Kapazitätsschranken und Flusserhaltung erfüllen muss. In unserem Straßennetzwerk bedeutet dies also, dass die maximale Verkehrslast auf eine Straße beschränkt ist und nicht überschritten werden kann. Weiterhin müssen alle Fahrzeuge, die in einen Kreuzungsbereich einfahren, diesen auch wieder verlassen. Für jede Kante im Netzwerk sei eine Fahrzeitfunktion gegeben. Wir verlangen außerdem, dass alle Bedarfe zwischen Quellen und Senken erfüllt werden. An verschiedenen Startpunkten im Netzwerk sind also Verkehrsteilnehmer mit unterschiedlichen Reisezielen verteilt und jeder muss zu seinem Bestimmungsort geleitet werden.
Als Verkehrsumlegungsproblem bezeichnen wir hierbei das Finden einer Verteilung des Verkehrs in einem Straßennetzwerk, so dass alle Verkehrsbedarfe, Kapazitätsschranken und Flusserhaltungen erfüllt sind. Umlegungsverfahren suchen nach optimalen Verteilungen in Bezug auf verschiedene Zielfunktionen.
Eine Möglichkeit für diese Zielfunktion ist die Minimierung der Gesamtreisezeit aller Nutzer im Netzwerk, Summe e∈A f (e) · t(f (e)). Hierbei ist t(f (e)) : R≥0 1→ R≥0 die Reisezeitfunktion, welche die Zeit beschreibt, die eine Flusseinheit in Abhängigkeit von der Flussmenge f (e) benötigt, um entlang der Kante e zu fahren. Die Lösung dieses Minimierungsproblem s heißt Systemoptimum. Während diese Lösung gut für das System als Ganzes ist, kann sie dennoch unfair zu einzelnen Nutzern sein. Diese könnten ihre eigene Reisezeit eventuell deutlich verbessern, indem sie auf andere Routen wechseln, damit aber den Verkehrsfluss als Ganzes empfindlich stören.
Im Gegensatz zum Systemoptimum erfüllt ein Fluss, bei dem kein Verkehrsteilnehmer eine schnellere Route für sich selbst finden kann, das Prinzip von Wardrop und wird Nutzergleichgewicht genannt. Dieses Gleichgewicht wird oft für die Modellierung von Verkehr genutzt, in dem erfahrene Verkehrsteilnehmer die Routen wählen, welche ihre eigene Reisezeit minimieren. Offensichtlich entsteht eine Lücke zwischen diesem "egoistischen" Nutzergleichgewicht und dem Systemoptimum. Diese Differenz wird oft mit Preis der Anarchie bezeichnet. Eine ausführliche Untersuchung dieses egoistischen Routings (selfish routing) findet sich in [20].
Das Problem, das Nutzergleichgewicht zu finden, werden wir als Verkehrsumlegungsproblem bezeichnen. Um die Reisezeit t(f (e)) für eine gegebene Straße in Abhängigkeit vom Verkehrsaufkommen auf dieser Straße zu bestimmen, nutzen viele statische Flussmodelle so genannte link-performance-Funktionen. Um sowohl Fahrzeit auf den Straßen als auch Wartezeit an den Kreuzungen abzubilden, werden passende monotone, konvexe, nichtlineare Funktionen verwendet [21, 22]. Durch die Nichtlinearität kann das Verkehrsumlegungsproblem nicht einfach durch Standardnetzwerkalgorithmen gelöst werden, sondert erfordert aufwändigere Verfahren.
Anzumerken ist, dass das hier beschriebene, klassische statische Verkehrsmodell kein zeitabhängiges Verhalten abbildet. Zum Beispiel können die (statischen) link-performance- Funktionen keine Pulks von Fahrzeugen oder unterschiedliche Ankunftszeiten während der Signalphasen einer Kreuzung darstellen. Aber diese Pulks sind essentiell für die Modellierung innerstädtischen Verkehrs, da sie gerade durch die Lichtsignalanlagen gebildet werden, bei denen wartende Verkehrsteilnehmer gemeinsam bei Beginn der Grünphase starten. Auf innerstädtischen Straßen ist also Verkehr nicht gleichmäßig über die Zeit verteilt. Die Ausbildung von Pulks hängt dabei signifikant von der gewählten Koordinierung ab.
Unser Verkehrsmodell. In unserem Verkehrsmodell treffen wir die folgende Annahme. Die Reisezeit auf einer Straße zwischen zwei Kreuzungen teilt sich in zwei Komponenten auf: die Fahrzeit bei einer vorgegebenen Geschwindigkeit, die benötigt wird, um die Entfernung zu überwinden, und die Wartezeit an der nächsten Kreuzung, zum Beispiel an einer roten LSA. Im einzelnen nehmen wir an, dass die Fahrzeit unabhängig vom Verkehrsaufkommen ist. Während diese Annahme für Autobahnen oder Fernstraßen nicht zutrifft, so gilt sie doch annähernd im innerstädtischem Bereich, da hier Distanzen klein sind und eine strikte Geschwindigkeitsbeschränkung gilt. Die Geschwindigkeit eines Fahrzeugs unterscheidet sich meist nur gering von der Geschwindigkeit eines Pulks bei freier Fahrt. Die Wartezeit in unserem Modell wird hingegen als linear von der Verkehrslast abhängig angenommen. Das Multiplizieren von Last und Reisezeit ergibt somit ein quadratisches Verhalten der Gesamtfahrzeit auf dieser Straße. Wir werden in den nächsten Abschnitten zeigen, dass diese Annahmen nicht zu restriktiv sind und durch Simulationsergebnisse bestätigt werden können.
3 Ein neues Modell
In diesem Abschnitt beschreiben wir kurz die verschiedenen Komponenten unseres neuen Modells, die verwendet werden, um das Umlegungs- und Signalkoordinierungsproblem gleichzeitig zu lösen. Es handelt sich hierbei um eine zyklische Zeitexpansion, eine Expansion von Kreuzungen und eine passende Implementierung von Lichtsignalanlagen. Darauf aufbauend werden wir ein gemischt-ganzzahliges Programm (MIP) formulieren und grundlegende Eigenschaften des Modells diskutieren.
3.1 Modellierung von Lichtsignalanlagen
Zyklisch zeitexpandierte Netzwerke. Der Begriff zeitexpandierter Netzwerke wurde im Kontext dynamischer Netzwerkflüsse eingeführt. Anders als bei üblichen statischen Flüssen reisen die Flusseinheiten im dynamischen Fall in zeitlicher Abhängigkeit durch das Netzwerk. Dynamische Flüsse wurden bereits von Ford und Fulkerson in ihrer grundlegenden Arbeit über Netzwerkflusstheorie untersucht [23] (siehe [24] für weitere Referenzen). Bereits in dieser Arbeit führten sie das Konzept zeitexpandierter Netzwerke ein. In diesen expandierten Netzwerken werden von jedem Knoten des Originalnetzwerkes Kopien angelegt, jeweils eine für jeden gewünschten Zeitschritt. Diese Knoten werden dann so durch Kanten verbunden, dass die Knoten entsprechend der Reisezeit auf dieser Kante verknüpft sind. Abbildung 2 zeigt ein einfaches Beispiel eines zeitexpandierten Netzwerkes. Der große Vorteil von dynamischen Flüssen ist die Möglichkeit, das komplette zeitliche Verhalten einer Flusseinheit auf ihrem Weg durch das Netzwerk abzubilden. Im Gegensatz dazu kann ein statischer Fluss nur das zeitunabhängige Verhalten der Flusseinheiten abbilden. Mit Hilfe zeitexpandierter Graphen können dynamische Flüsse nicht nur modelliert, sondern zahlreiche Netzwerkflussproblem auch effizient gelöst werden (effizient bzgl. der Größe der Zeitexpansion).
Wie bereits motiviert, ist für Lichtsignalanlagen und ihre Koordinierung ein zeitabhängiges Modell, das den Versatz zwischen aufeinander folgenden Lichtsignalen abbilden kann, angestrebt. Dynamische Flüsse und zeitexpandierte Netzwerke scheinen dafür ein geeignetes mathematisches Mittel zu sein. Allerdings sind zeitexpandierte Netzwerke eher ineffizient, wenn der Zeithorizont groß ist, da dies die Anzahl der benötigten Netzwerkkopien bestimmt, die zur Verfügung gestellt und verwaltet werden müssen. Aufgrund des periodischen Verhaltens von Lichtsignalanlagen ist es jedoch für unsere Aufgabenstellung nicht notwendig, eine vollständige Zeitexpansion zu nutzen. Stattdessen schlagen wir eine zyklische Zeitexpansion vor, bei der wir nur k ∈ N Zeitschritte der Größe t = Γ / k verwenden und Kanten entsprechend der Fahrzeit modulo k mit angepassten Kapazitäten hinzufügen.
Bei einer Zeitexpansion von einem Zeitschritt pro Sekunde und einer Umlaufzeit von 60 Sekunden ergibt sich also eine zyklische Expansion in 60 Schritte. Für die praktische Anwendung ist diese Genauigkeit der Zeitexpansion bereits ausreichend. Bei einem angenommen Verkehrsstrom von 1800 Fahrzeugen pro Stunde ergibt sich daraus bereits eine skalierte Kantenkapazität von lediglich einem halben Fahrzeug. Das heißt, bereits bei einem Bedarf von einem Fahrzeug zwischen einem Start-Ziel-Paar wird der Fluss bereits auf mehrere, zeitlich benachbarte Kanten verteilt.
Um außerdem die Möglichkeit des Wartens an Kreuzungen zu modellieren, werden alle Kopien eines Knotens v in chronologischer Ordnung zyklisch mit Wartekanten vivi+1 verbunden (siehe Abbildung 2 und 4). Jeder Wartekante werden Kosten von einem Zeitschritt zugewiesen. Sind nun Flusswerte auf den Kanten des Netzwerks gegeben, so erhält man durch Multiplizieren von Flusswert und Reisezeit und Aufsummieren über alle Wartekanten die Gesamtwartezeit. Steigender Fluss an einer ausgewählten Kreuzung wird die Wartezeit erho¨hen. Sind die ausgehenden Kanten aus der Kreuzung in ihrer Kapazität stark beschra¨nkt, müssen weitere Wartekanten genutzt werden. Daher steigt die Wartezeit nicht linear, sondern zeigt bei zunehmendem Fluss ein quadratisches Verhalten. Gleichzeitig kann die Kapazität der Wartekante genutzt werden, um die maximale Länge der Warteschlange zu begrenzen.
Bild 2: Einfaches Beispiel für die Zeitexpansion eines Graphen mit 4 Knoten. Meist wird der Graph für einen beliebigen Zeithorizont expandiert und somit sehr groß. In unserem Modell werden die Zeitschritte jedoch zyklisch verknüpft, die Größe bleibt damit überschaubar. Wartekanten garantieren schließlich, dass Fluss auch in einem Knoten verweilen kann.
Kreuzungen. Um Kreuzungen mit verschiedenen Spuren, Abbiegerichtungen und inneren Signalversatzzeiten adequat modellieren zu können, nutzen wir einen Standardansatz. Jeder Kreuzungsknoten wird in mehrere Knoten für ein- und ausgehenden Verkehr aufgespalten; innere Kanten verbinden diese Knoten entsprechend der Spuren und Abbiegerichtungen (siehe Abbildung 3). Jeder dieser inneren Kanten wird ein Signal zugeordnet.
Bild 3: Expandierte Kreuzung mit Kanten für jede Abbiegemöglichkeit
Lichtsignalanlagen. Aufbauend auf den oben erklärten Expansionen können die Lichtsignalanlagen selbst über binäre Entscheidungsvariablen modelliert werden, die die Kapazitäten der inneren Kanten einer Kreuzung an- oder ausschalten, je nach Signalplan und entsprechendem Zeitschritt (siehe Abbildung 4). Für jedes Signal, also jede innere Kreuzungskante e des nicht zeitexpandierten Netzwerks, wird eine Matrix Ae ∈ {0, 1}k×k vorgegeben; hierbei bedeutet Aeij = 1, dass das zugehörige Signal im Zeitschritt j Grün ist, wenn Versatz i Γ /k gewählt wird. Jede Zeile der Matrix steht für einen bestimmten Versatz und legt den Ablauf der Phasen des Signals fest. Somit ist die innere Schaltungslogik der Lichtsignalanlage gewährleistet, da selbstverständlich die Versatzzeit einheitlich für die Kreuzung gewählt wird.
Formel siehe PDF.
Für jede Kreuzung n führen wir k binäre Variablen bn = (bn1, ..., bnk) ∈ {0, 1}k mit der Nebenbedingung (...) ein, die die gewählte Versatzzeit der Kreuzung beschreiben. Genauer ist bni = 1 äquivalent zu Versatzzeit ρn = i Γ / k an Kreuzung n. Wird dieser charakteristische Vektor bn mit Ae an die Kapazität ce einer Spur multipliziert, so schaltet dies die Kapazität der Kante an und aus und stellt somit Grün- und Rotphasen dar. Nutzt man diese zeitabhängige Kapazitätsschranke fe ≤ bnAece für alle inneren Spuren einer Kreuzung (wobei ce entsprechend der Granularität der Zeitexpansion gewählt wird), kann das komplette dynamische Verhalten einer Lichtsignalanlage in unserem Modell abgebildet werden.
Bild 4: Zyklische Expanision einer Lichtsignalanlage
Nach dem Zusammenfügen der oben beschriebenen Komponenten erhalten wir folgende Definition eines zyklisch-zeitexpandierten Netzwerkes.
Definition 1 (Zyklisch-zeitexpandiertes Netzwerk). Ein zyklisch-zeitexpandiertes Verkehrsnetzwerk ist ein Netzwerk, das aus einem Verkehrsnetzwerk G = (V, A) durch (i) Expandieren der Kreuzungen mit Spuren für alle Abbiegemöglichkeiten, (ii) zyklischer Zeitexpansion entsprechend der Umlaufzeit und (iii) Expansion der Signalschaltpläne erhalten wird.
3.2 Modellierung der Verkehrsumlegung
Aufbauend auf dem zyklisch-zeitexpandiertem Netzwerk betrachten wir nun das Verkehrsumlegungsproblem. Obwohl man den Fluss als zeitlich durch das expandierte Netzwerk wandernd ansehen kann, sollte man dieses Modell dennoch eher als statisches Modell betrachten, dass einige zeitabhängige Aspekte eines Verkehrsflusses abdeckt. Durch die zyklische Wiederholung der Knoten- und Kantenkopien kann ein durch das Netzwerk wanderndes Flusspartikel als Repräsentant einer Menge zeitlich wiederholter Flusspartikel angesehen werden, die jeweils im Abstand der Umlaufzeit durch das Netz fließen.
Hierbei sei erwähnt, dass es eine eng verwandte Interpretation von statischen Netzwerkflüssen für Verkehrsnetzwerke gibt. In dieser Interpretation betrachtet man flussfu¨hrende Pfade im statischen Netzwerk als eine Abbildung der entsprechenden Menge Flusspartikel, die mit einer bestimmten Flussrate zeitlich durch das Netz wandern. Mit anderen Worten repräsentiert also der flussführende Pfad im statischen Netzwerk eine konstante Rate von Fluss auf diesem Pfad im realen, zeitabhängen Verkehrsnetz.
Mit dieser Interpretation können die beiden Modelle, das zyklisch expandierte Netzwerk und die statische Umlegung, vereinigt werden. Im Wesentlichen müssen die Bedarfe der einzelnen Start-Ziel-Paare auf die entsprechenden Kopien von Start- und Zielknoten verteilt werden. Auf die präzise Beschreibung dieser Konstruktion wird an dieser Stelle verzichtet.
Damit sind alle benötigten Parameter des Netzwerks gegeben. Es kann nun ein übliches Mehrgüterzirkulationsproblem für das zyklisch-zeitexpandierte Netzwerk formuliert und um binäre Entscheidungsvariablen für Lichtsignalanlagen erga¨nzt werden. Um das entsprechende gemischt-ganzzahlige Programm in einem lesbaren Format zu halten, geben wir hier eine etwas vereinfachte Form an und verzichten auf einige Details und Indizes.
Formel siehe PDF.
Die Nebenbedingungen von Typ (I) beschreiben die Kapazitätsschranken, Typ (II) formuliert Flusserhaltung und (III) erzwingt Fluss entsprechend der Bedarfe. Typ (IV) garantiert, dass je Kreuzung exakt eine Versatzzeit ausgewählt wird und Typ(V) verbietet Fluss auf den internen Kreuzungskanten je nach gewa¨hlter Versatzzeit.
4 Fahrzeitanalyse
Unser zyklisch-zeitexpandiertes Modell baut auf einer wesentlichen Annahme auf: die Reisezeit auf einer innerstädtischen Straße lässt sich in zwei Komponenten zerlegen, und zwar
1. eine konstante, vom Verkehrsaufkommen unabhängige Fahrzeit und
2. eine von Verkehr und LSA-Koordinierung abhängige Wartezeit.
Diese Annahme mag zunächst sehr kritisch erscheinen. In der Fachliteratur, zum Beispiel [21, 22], wird stets ein nichtlinear Zusammenhang zwischen durchschnittlicher Fahrzeit und Verkehrsaufkommen angenommen. Die dort beschriebenen Fahrzeitfunktionen (link performance functions, Latenzfunktionen) sind monoton wachsend und konvex. Dies wird durch die eigene Erfahrung untermauert, dass bei erhöhtem Verkehrsaufkommen deutlich mehr Zeit für eine gewisse Strecke benötigt wird. In diesem Abschnitt soll untersucht werden, welche Konsequenzen sich aus unserem Ansatz für die Fahrzeiten in dem dargestellten Modell ergeben.
4.1 Gleichmäßiger Verkehr
Wir betrachten ein einfaches Netzwerk aus zwei Straßen und einer dazwischen geschalteten LSA wie in Abbildung 4. Zunächst wollen wir annehmen, dass der Verkehr gleichmäßig über die Zeit verteilt an der LSA ankommt. Auf jeder Kantenkopie der eingehenden Kante in Abbildung 4 komme also der gleiche Flusswert x ≤ c an. Fluss, der auf Kanten fließt, die bei Grün ankommen, kann die LSA direkt passieren. Fluss, der bei Rot ankommt, muss die Wartekanten nutzen. Dabei summieren sich die bei Rot ankommenden Flusseinheiten auf. Ist x klein, so kann dieser Fluss auf der ersten ausgehenden Kante bei Grün abfließen. Wird x größer, so wird der Punkt erreicht, bei dem die Kapazität der ersten ausgehenden Kante ausgeschöpft ist. Weiterer Fluss muss nun eine zusätzliche Wartekante nutzen und kann erst auf der zweiten ausgehenden Kante abfließen. Sukzessives Erhöhen des eingehenden Flusses führt nun dazu, dass immer mehr der ausgehenden Kanten mit voller Last genutzt werden.
Berechnen wir für dieses Szenario in unserem Modell die durchschnittliche Fahrzeit pro Flusseinheit, so ergibt sich der in Abbildung 5 dargestellte Zusammenhang. Offensichtlich spiegelt also auch die unserem Modell innewohnende Fahrzeit den in der Literatur beschriebenen monoton wachsenden und konvexen Zusammenhang zwischen Verkehrsstärke und Fahrzeit wider, auch wenn eine Fahrzeitfunktion nicht ohne Weiteres angeben werden kann. Das heißt, obwohl wir im vorgestellten Modell nur lineare Funktionen nutzen, ist die inherente Fahrzeitfunktion keineswegs linear oder gar konstant. Vielmehr wird durch die zyklische Zeitexpansion die Nichtlinearität durch stückweise lineare Funktionen approximiert.
Bild 5: Durchschnittliche Reisezeit (Fahr- und Wartezeit) auf einer Straße mit einer LSA, berechnet mit dem vorgestellten Modell. Der ankommende Verkehr wird als gleichverteilt über die Zeit angenommen
4.2 Pulks von Fahrzeugen
Die Annahme im vorherigen Abschnitt, dass Fahrzeuge gleichverteilt über die Zeit an einer LSA ankommen, ist im innerstädtischen Verkehr oft nicht erfüllt. Gerade LSAs führen dazu, dass sich Pulks von Fahrzeugen bilden, da die an einer LSA wartenden Fahrzeuge gemeinsam bei Grün losfahren. Eine gewisse Zeitspanne während der Umlaufzeit wird die Straße mit maximaler Kapazität benutzt; während der verbleibenden Zeit bleibt die Straße dagegen leer.
Das vorgestellte Modell eignet sich hervorragend, um solche Pulks von Fahrzeugen darzustellen. Anstatt einer gleichmäßigen Verteilung der Flusswerte auf die zeitlichen Kopien einer Kante können einige Flusswerte auf konsekutiven Kopien mit dem auf dieser Kante maximal zulässigem Flusswert belegt werden, andere Kopien hingegen mit Fluss 0. Dies entspricht dem eben beschriebenen Verhalten. Unser Modell kann somit auch die Fahrt eines Pulks durch das Netzwerk abbilden. Dabei können Pulks durchaus zerteilt, vereinigt, gestaucht oder gestreckt werden.
Wir wiederholen nun das gedankliche Experiment aus dem vorherigen Abschnitt 4.1. Statt gleichmäßig über die Umlaufzeit verteilt eintreffenden Verkehrs betrachten wir nun einen Pulk von Fahrzeugen. Hierfür benötigen wir drei Parameter, um den Pulk zu beschreiben:
- die Ankunft des ersten Fahrzeugs an der LSA, relativ zum Beginn der Grünphase
- die Länge des Pulks (vereinfacht hier in Zeitschritten gemessen, dies kann über die Kapazität der Straße in die Anzahl Fahrzeuge umgerechnet werden)
- die Dichte des Pulks (weiterhin schöpfe der ankommende Pulk die Kantenkapazität voll aus)
Des Weiteren habe die eingehende Straße zwei Fahrspuren, die sich kurz vor der LSA in 4 Fahrspuren aufteilen. Die ausgehende Straße hat somit die doppelte Kapazität und die Fahrzeuge können nebeneinander warten und gleichzeitig bei Grün losfahren. In Abbildung 7 ist der Zusammenhang zwischen mittlerer Fahrzeit und Pulklänge für einen Pulk, der zehn Sekunden vor Grünbeginn an der LSA eintrifft, dargestellt. Zunächst sinkt die mittlere Fahrzeit bei steigender Pulklänge, also höherem Verkehrsaufkommen, da spätere Fahrzeuge durch die höhere Kapazität der Ausgangsstraße kürzer warten müssen.
Bild 6: Simulation des beschriebenen Szenarios (Ausschnitt eines Screenshot aus VISSIM 5.10, ptv AG)
Bild 7: Mit dem vorgestellten Modell berechnete mittlere Fahrzeit pro Fahrzeug für einen Pulk, der 10 Sekunden vor Grünbeginn an der LSA ankommt. Durch die höhere Kapazität der ausgehenden Straße wird der Pulk verdichtet. Später ankommende Fahrzeuge müssen kürzer warten als die zuerst angekommenen.
Dieses Ergebnis erscheint zunächst überraschend, da die durchschnittliche Fahrzeit bei steigendem Verkehr sinkt. Mit Hilfe der beiden bekannten Verkehrssimulationen VISSIM (ptv AG) und MATSim (TU Berlin und ETH Zürich) lässt sich dieses erwartungswidrige Verhalten der Fahrzeit jedoch reproduzieren (vgl. auch Abschnitt 5). In Abbildung 6 ist ein Aussschnitt aus dem in VISSIM nachgestelltem Szenario zu sehen. Eine vorgeschaltete LSA sorgt für die Ankunft entsprechender Pulks. Die Fahrzeit wird hingegen nur zwischen zwei Messpunkten etwa 120 m vor bzw 10 m hinter der eigentlichen LSA gemessen. In Abbildung 8 ist der gemessene Zusammenhang zwischen Fahrzeit und Pulklänge dargestellt.
Bild 8: Gemessene mittlere Fahrzeit für das Szenario aus Abbildung 6 in Abhängigkeit vonder Länge des ankommenden Pulks. Die Übereinstimmung mit der zuvor mit dem vorgestellten Modell berechneten Fahrzeit (Abbildung 7) ist sehr deutlich.
Einerseits zeigt der Vergleich zwischen der mit unserem Modell vorhergesagten Fahrzeit (Abbildung 7) mit der gemessenen Fahrzeit (Abbildung 8) sehr gute Übereinstimmung. Dies legt nahe, dass unsere Modellannahmen nicht zu vereinfachend sind. Sie eignen sich im Gegenteil sogar dazu, die komplexen Fahrzeitzusammenhänge beim Auftreten von LSAs und Pulks deutlich besser zu beschreiben als herkömmliche Modelle.
Andererseit widerlegt das präsentierte Beispiel die oft gemachten Annahmen an linkperformance-Funktionen. Diese werden meist als konvex, monoton wachsend und als lediglich von der Verkehrsstärke abhängig angesehen, was auch bei der Berechnung von Nutzergleichgewichten explizit ausgenutzt wird. Diese Annahmen mögen im außerstädtischen Bereich auf Landstraßen oder Autobahnen zutreffen. Im innerstädtischen Bereich können aus unserer Sicht diese Annahmen an link-performance-Funktionen nicht getroffen werden. Fahrzeiten hängen hier signifikant von weiteren Parametern wie der Koordinierung und Pulkbildung ab.
4.3 Weitere Eigenschaften
Aus mathematischer/algorithmischer Sicht sind weitere Eigenschaften unseres Modells interessant. Dafür nehmen wir zunächst an, dass die Versatzzeiten aller LSAs fixiert sind, also sämtliche Entscheidungsvariablen im MIP (Abschnitt 3.2) fest gesetzt wurden. Mit dieser fixierten Koordinierung geht das MIP in ein gewöhnliches lineares Programm (LP) über, also effizient lösbar. Alternativ können aus dem Netzwerk alle Rotkanten entfernt werden. Jeder Algorithmus für das min-cost-circulation-Problem kann nun für die Bestimmung einer Umlegung genutzt werden.
Satz 1. Im zyklisch-zeitexpandierten Modell kann eine Verkehrsumlegung für eine fixierte Koordinierung effizient bestimmt werden.
Dies heißt also, dass aus algorithmischer Sicht das Bestimmen einer Umlegung ein einfaches Problem ist und für praktisch relevante Instanzen schnell berechnet werden kann.
Weiterhin können wir eine interessante Eigenschaft der Optimallösung selbst für beliebige Koordinierungen nachweisen.
Folgerung 1. Eine optimale Lösung (Systemoptimum des vorgeschlagenen Multi-Commodity-Min-Cost-Flow-Problems ist auch ein Nutzergleichgewicht nach Wardrop.
Beweis. Alle Reisezeiten im expandierten Netzwerk sind konstant. Damit hat der Wechsel eines Verkehrsteilnehmers auf eine andere Route keinen Einfluss auf die Reisezeiten. Daher ist das Systemoptimum konsequenterweise auch ein Nutzergleichgewicht.
Somit kann ein Nutzergleichgewicht auch mit unserem einfachen Modell sehr gut bestimmt werden. Dies ist um so praktischer, da die bisher in der Literatur hauptsächlich untersuchten Verfahren zur effizienten Bestimmung von Nutzergleichgewichten Eigenschaften der link- performance-Funktionen voraussetzen, die wie eben nachgewiesen im innerstädtischen Bereich nicht gelten. Unsere Lösung kann als Approximation eines Nutzergleichgewichts im ursprünglichen, noch nicht expandierten Netzwerk angesehen werden. Die Genauigkeit ha¨ngt dabei von der Anzahl der Schritte in der Zeitexpansion ab. Eine Projektion der unserem Modell inherenten Fahrzeit auf eine link-performance-Funktion für das nicht expandierte Netzwerk ist jedoch nur schwer anzugeben und eine entsprechende Fahrzeitfunktion hinge von mehreren Parametern ab.
Zusammenfassend gilt für das vorgestellte Modell:
- Für fixierte Lichtsignalanlagenschaltungen ist das Verkehrsumlegungsproblem in zyklisch-zeitexpandierten Netzwerken effizient lösbar.
- Das Verkehrsumlegungs- und Signalkoordinierungsproblem sind gemeinsam in einem gemischt-ganzzahligen linearen Programm (MIP) formulierbar.
- Zusammenhänge zwischen LSAs und Pulks werden trotz der einfachen Fahrzeitfunktionen im zyklisch-expandierten Netzwerk sehr gut abgebildet.
- Die ermittelten Optimallösungen sind zugleich Nutzergleichgewichte.
5 Simulationsergebnisse
In diesem Abschnitt werden wir die Anwendbarkeit unseres Modells mit Hilfe von Simulationen auswerten. Wir verwenden zwei anerkannte Werkzeuge für Verkehrssimulationen: MATSim (TU Berlin) und VISSIM (ptv AG).
5.1 Szenarien
Für die Untersuchungen verwenden wir Ausschnitte der Innenstädte von Portland und Denver, für die wir Vergleichsergebnisse von Wünsch [9] nutzen können. Diese Straßennetzwerke bestehen aus einem rechtwinkligen Netz mit 16 bzw. 36 Kreuzungen und hauptsächlich Einbahnstraßen. Da dies eher untypisch für europäische Straßennetze ist, untersuchen wir außerdem die Innenstadt von Cottbus mit 29 Kreuzungen in unregelmäßiger Anordnung und mit in beiden Richtungen befahrbaren Straßen. Weiterhin variieren wir die Verkehrslast in den 10 bis 20 Start-Ziel-Paaren je Szenario von niedrig bis sehr hoch.
Die Daten für die Straßennetze und LSAs der beiden amerikanischen Städte wurden uns für diese Untersuchung freundlicherweise von unserem Forschungspartner ptv AG zur Verfügung gestellt. Die Daten für das Cottbusnetzwerk haben wir hauptsächlich selbst gesammelt bzw. OpenStreetMap entnommen. Für den Verkehr stehen Start-Ziel-Matrizen zur Verfügung, die zunächst nur aus dem beobachteten Verkehrsaufkommen geschätzt wurden. Zukünftig sollen auch hier reale Daten verwendet werden, für die Erprobung des Modells ist dies jedoch zunächst nicht relevant. Die Routenwahl selbst findet, wie bereits dargestellt, im Modell statt.
Bild 9: Innenstadt von Cottbus. Das dargestellt Netz enthält nur Hauptstraßen und signalisierte Kreuzungen und erstreckt sich über etwa 7,5 km2
5.2 Simulation
Für die Simulation benutzen wir zwei sehr unterschiedlich Verfahren. VISSIM von ptv AG bietet eine mikroskopische Verkehrssimulation [25], das heißt, Verkehrsteilnehmer werden einzeln mitsamt ihrer Dynamik modelliert. Dafür verfügt VISSIM zum Beispiel über dem Stand der Technik entsprechende Modelle für Beschleunigungsverhalten und Spurwechsel. Die Software MATSim wird hauptsächlich an der TU Berlin und der ETH Zürich entwickelt und ist eine auf Warteschlangen beruhende, planbasierte Multiagentensimulation. Die Fahrzeugdynamik ist hier sehr stark vereinfacht, stattdessen können aber sehr große Netzwerke mit mehreren zehntausend Straßen und mehreren hunderttausend Verkehrsteilnehmern simuliert werden. MATSim nutzt für die Verkehrsumlegung einen iterativen Ansatz (siehe [26] für weitere Informationen).
Im Simulationsprozess zeigt sich die Anwendbarkeit unseres Modells für gleichzeitige Umlegung und Koordinierung. Tatsächlich bilden sich grüne Wellen und die Reisezeiten sind deutlich kürzer im Vergleich zu zufällig gewählten Versatzzeiten. Dies zeigt auch, dass die Annahme an lastunabhängige Fahrzeiten und lastabhängige Wartezeiten nicht zu vereinfachend ist. In Tabelle 2 sind typische Zahlen für das Cottbus-Szenario dargestellt (zyklische Expansion in 90 Zeitschritte, 10 Start-Ziel-Paare mit durchschnittlich je 0,2 Fahrzeugen pro Sekunde, 200 zufällige Koordinierungen und 20 Simulationsläufe je Koordinierung). Gegenüber zufällig gewählten Koordinierungen wird die Wartezeit je nach Verkehrslast um 30 bis 70 Prozent reduziert.
Um unsere Ergebnisse mit anderen Optimierungsverfahren zu vergleichen, nutzen wir die Ergebnisse von [9] für das Portland-Szenario. Dafür schalten wir die Routenwahl bei unserem Ansatz aus. Die Vergleichsdaten stammen von TRANSYT, einem auf genetischer Programmierung beruhendem Werkzeug zur Koordinierung, und dem Platoonmodell von Wünsch [9]. Tabelle 3 fasst die Ergebnisse zusammen, in Klammern sind jeweils die Rechenzeiten angegeben.
Für die Koordinierung ohne gleichzeitige Umlegung erhalten wir mit unserem Modell konkurrenzfähige Lösungen. TRANSYT nutzt ein deutlich feineres Verkehrsmodell und kann damit auf Kosten der Rechenzeiten in diesem kleinen Szenario eine etwas bessere Lösung ermitteln. Außerdem haben wir für diesen Test zunächst keine Parameter unseres Modells kalibriert; beispielsweise lässt sich möglicherweise durch leichtes Unter- oder Überschätzen der Geschwindigkeit der Verkehrsteilnehmer unsere Koordinierung noch weiter verbessern.
Tabelle 2: Simulationsergebnisse für die optimierte Routenwahl und Koordinierung in Cottbus (MAT-Sim). Die angegebene Verbesserung bezieht sich auf die Gesamtfahrzeit. Die darin enthaltene Mindestfahrzeit, die sich allein aus erlaubter Höchstgeschwindigkeit und Entfernung ergibt, ist jedocheine triviale untere Schranke. Wird nur die zusätzliche verkehrsbedingte Reisezeit betrachtet, so wird diese mit unserem Optimierungsansatz um 70 Prozent reduziert.
Tabelle 3: Simulationsergebnisse für Portland (VISSIM). Auch ohne Parameterfeintuning liefert unser Ansatz bereits sehr gute Ergebnisse. Die reale Koordinierung ist aus einem versatzzeitoptimierten, größeren Nezwerk entnommen und damit für das Teilnetzwerk nicht optimal.
Das vorgestellte, kleine Netzwerk von Portland lässt jedoch kaum unterschiedliche Routen zwischen den Start-Ziel-Paaren zu. Die kürzeste Alternativroute zwischen den meisten Start-Ziel-Paaren ist, bedingt durch die Einbahnstraßen, deutlich länger als der direkte Weg. Der kürzeste Weg ist somit trotz eventuell schlechter Koordinierung und langer Wartezeiten für viele Verkehrsteilnehmer die beste Wahl. Daher kann über die eigentliche Leistungsfähigkeit unseres Modells hier noch keine Aussage getroffen werden kann.
Überraschenderweise liefern beide Simulationen für die untersuchten Szenarios sehr ähnliche Ergebnisse, was aufgrund des unterschiedlichen Ansatzes nicht unbedingt zu erwarten war. Tatsächlich ergeben sich nahezu identische Verkehrsverteilungen und Fahrzeiten. Andererseits heißt dies, dass unsere ermittelten Koordinierungen im gewissen Sinne robust sind. Unser Modell ist also nicht auf ein bestimmtes Simulationswerkzeug zugeschnitten, um dort besonders gute Ergebnisse zu erzielen, sondern die Lösungen erweisen ihre gute Qualtität auch bei völlig unterschiedlichen Simulationsansätzen. Demnach sollten die Lösungen auch im Praxistest bestehen können.
5.3 Vorteile gleichzeitiger Verkehrsumlegung
Die Hauptintention unseres Modells war die Rückkopplung zwischen Verkehrsumlegung und Lichtsignalanlagenkoordinierung. Wir zeigen den Vorteil dieses Ansatzes zunächst anhand eines kleinen Beispiels. Gegeben seien zwei parallele Straßen zwischen zwei Kreuzungen A und B mit zwei zusätzlichen Kreuzungen auf jeder Route. Wir suchen nun nach einer optimalen Umlegung und Koordinierung, wenn die gleiche Menge Fahrzeuge jeweils von A nach und von B nach A fahren möchte. Wir nehmen dafür weiterhin identische Signalpläne für alle Kreuzungen (Umlaufzeit 60 s, grün für 27 s) und eine einheitliche Fahrzeit von 20 Sekunden zwischen aufeinander folgenden Kreuzungen an. Das Straßennetzwerk ist in Abbildung 10 dargestellt.
Bild 10: Kleines Beispiel für simultane Umlegung und Koordinierung
Um zunächst eine statische Verkehrsumlegung zu ermitteln, nehmen wir eine einheitliche, streng konvexe Fahrzeitfunktion für alle Straßen an, wie sie meist in der Literatur verwendet wird. Ein konventioneller Ansatz würde zunächst mit Hilfe dieser Funktionen eine Verkehrsumlegung bestimmen. Die Konvexität würde in diesem Fall zu gleichmäßig aufgeteilten Verkehrslasten führen. 50% aller Fahrzeuge jeder Richtung würden also jeweils die untere bzw. obere Route nutzen. Wir fixieren diese Verkehrsumlegung und berechnen anschließend mit unserem Modell eine optimale Koordinierung. Dies vergleichen wir zur Reisezeit, wenn wir stattdessen mit unserem Modell Umlegung und Koordinierung gleichzeitig optimieren.
Bei der gleichmäßigen Verkehrsumlegung entstehen zahlreiche Konflikte durch den sich begegnenden Verkehr. Insgesamt stellt sich in der Simulation eine durchschnittliche Wartezeit von 25,2 Sekunden bei optimaler Koordinierung ein. Im Gegensatz dazu bietet die Lösung mit gleichzeitiger Optimierung ein völlig anderes Bild. Sämtliche Fahrzeuge von A nach B werden der unteren Route zugewiesen, während alle Verkehrsteilnehmer der Gegenrichtung über die obere Strecke geleitet werden. Dadurch können grüne Wellen koordiniert werden und die durchschnittliche Wartezeit sinkt um 75% auf 6,1 Sekunden.
Der beschriebene Effekt getrennter Verkehrsströme tritt auch in realen Szenarien auf, fällt aber natürlich nicht so dramatisch aus wie in diesem speziell gewählten Beispiel. Um dies nachzuweisen, wurde der folgende Ansatz gewählt. Als erstes wird mit Hilfe von VISUM eine klassische Umlegung bestimmt. VISUM ist eine Verkehrsplannungssoftware von ptv und unterstützt zahlreiche Umlegungsverfahren nach dem aktuellen Stand der Technik. Als nächstes wird diese Umlegung in unserem Modell fixiert und dafür mit unserem Ansatz eine optimale Koordinierung bestimmt. Danach wird Umlegung und Koordinierung simultan mit unserem Modell optimiert und die Lösungen verglichen.
Zum Nachweis wurde die Cottbus-Instanz mit 17 Start-Ziel-Paaren untersucht. Der Gesamtbedarf wurde so gewählt, dass etwa 200 Autos pro Zyklus von 90 Sekunden ihre Fahrt antreten. Bei der Optimierung mit beiden Strategien kann eine um 11 % reduzierte Wartezeit bei freier Routenwahl festgestellt werden (siehe Tabelle 4). Weiterhin weist VISUM meist kürzeste Routen zu. Daher begegnen sich Fahrzeuge mit entgegengesetztem Start und Ziel. Im Gegensatz dazu stellt die freie Umlegung eine Art Kreisbewegung um das Stadtzentrum her. Mehr Verkehrsteilnehmer werden dem äußeren Ring zugewiesen und umfahren das Stadtzentrum. Etwa zwei Drittel bewegen sich dabei im Uhrzeigersinn und nur ein Drittel nutzt den Ring entgegen dem Uhrzeigersinn. Die Lösungen sind in den Abbildungen 11 bis 14 graphisch veranschaulicht.
Diese völlig anderen, aber sehr effizienten Umlegungen und Koordinierungen charakterisieren unser präsentiertes Modell. Wir sind der Meinung, dass vergleichbare Lösungen ohne gleichzeitige Umlegung und Koordinierung oder durch adaptive Signale nicht erreicht werden können. Gleichzeitig legen unsere Ergebnisse nahe, dass Lichtsignalanlagen auch aktiv zur Lenkung innerstädtischen Verkehrs genutzt werden können.
Bild 11: Die von VISUM bestimmte Umlegung von 17 Start-Ziel-Paaren im Cottbus-Szenario. Die Farbe codiert die Verkehrsbelastung von Dunkelgrün (bis 100 Fahrzeuge pro Stunde und Fahrspur) über Gelb (bis 400 Fahrzeuge pro Stunde und Fahrspur) bis Dunkelrot (mehr als 800 Fahrzeuge pro Stunde und Fahrspur). Auffallend ist die sehr gleichmäßige Verteilung von Verkehr im Netz.
Bild 12: Verkehrsumlegung für dasgleiche Szenario wie in Abbildung 11, bei gleichzeiter Optimierung der LSA-Koordinierung mit dem vorgestellten Modell.Der äußere Ring wird bevorzugt im Uhrzeigersinn genutzt. Die Sprünge in der Verkehrsbelastung auf einigen Straßen resultieren aus einer Veränderung der Fahrspuranzahl an dieser Stelle.
Bild 13: Aufteilung der Verkehrsströme für ein Start-Ziel-Paar aus Abbildung 12. Jeweils 400 Fahrzeuge pro Stunde sollen zwischen dem Einkaufszentrum im Norden und dem Wohngebiet im Süden (rot) und in entgegengesetzer Richtung (grün) verkehren. VISUM weißt alle Fahrzeuge auf die kürzeste Route quer durch die Innenstadt. Mit unserem Modell schließen sich die Fahrzeuge zum Teil der Zirkulation auf dem äußeren Ring an. Die Farbintensität kodiert hierbei dieStärke der einzelnen Verkehrsströme.
Bild 14: Die über alle Fahrzeuge integrierte Wartezeit, aufgeschlüsselt nach LSA, nach Optimierung mit unserem Modell. Dunkelgrün bedeutet eine Gesamtwartezeit aller Fahrzeuge an dieser LSA von weniger als 50 Sekunden, dunkelrot steht für mehr als 400 Sekunden. Mit Blick auf die Verkehrsbelastung in Abbildung 12 ist die Wartezeit gerade auf Straßen mit hoher Belastung gering, also eine gute Koordinierung erreicht. Die höchsten Wartezeiten treten an den Zubringerstraßen auf, an denen die Fahrzeuge als gleichverteilt über die Zeit angenommen werden.
Tabelle 4: Mit Hilfe des zyklisch-zeitexpandierten Netzwerks und freier Umlegung können die verkehrsbedingten zusätzlichen Fahrzeiten von 9000 auf 8000 Sekunden reduziert werden. Diese 1000 Sekunden werden während jedes Umlaufs, also aller 90 Sekunden eingespart. Während eines Umlaufs starten etwa 200 Fahrzeuge im Netz.
6 Zusammenfassung
Der Hauptvorteil unseres Modells ist die gleichzeitige Beschreibung des Verkehrsumlegungs- und Lichtsignalanlagenkoordinierungsproblems in einem einfachen linearen, gemischt-ganzzahligen Programm (MIP). Die Wechselwirkung zwischen Verkehrsteilnehmern und Signalkoordinierung wird berücksichtigt und bietet beachtliches Potential für bessere Lösungen. Weiterhin erlaubt unser Modell die effiziente Lösung des Umlegungsproblems für fixierte Koordinierungen. Wir haben gezeigt, dass Pulks von Fahrzeugen als ein wichtiges Merkmal innerstädtischen Verkehrs sehr gut nachgebildet werden können. Insbesondere das Umlegungsverfahren eignet sich für einen zeitnahen Einsatz in der praktischen Verkehrsplanung. Mit vergleichsweise geringem Aufwand könnte das vorgestellte Modell soweit modifiziert werden, dass entsprechende Algorithmen mit nur geringer Nutzerinteraktion Umlegungen unter Einfluss einer LSA- Koordinierung bestimmen können. Die Integration passender Module in Verkehrsplannungssoftware ist denkbar.
Die Simulationsergebnisse legen die Anwendbarkeit unseres Modells für reale Straßennetzwerke nahe. Trotz der Größe der MIP-Formulierung werden gute Lösungen schnell erhalten. Beim Lösen des MIP mit einem üblichen Solver wird außerdem eine duale Schranke für die Optimallösung berechnet. Dieser garantierte beschränkte Abstand zur Optimalität erlaubt es, die Qualität der Lösung zu bewerten. Weiterhin lassen sich in der Duallösung kritische Engstellen des Straßen- und Signalnetzes erkennen und bewerten. Dies ist ein großer Vorteil gegenüber heuristischen Ansätzen wie genetischer Programmierung oder neuronalen Netzen.
Das Modell bietet noch zahlreiche Möglichkeiten, wie Verkehr trotz der einfachen Annahme konstanter Fahrzeiten noch realitätsnaher abgebildet werden kann. So können auch Anfahrtverzögerungen oder nicht signalisierte Kreuzungen mit Vorrangsrichtungen bis zu einem gewissen Grad abgebildet werden. Aus Platzgründen konnte darauf in dieser Arbeit nicht näher eingegangen werden.
Zukünftige Arbeiten werden sich mit der Verfeinerung des Modells, der weiteren Beschleunigung der Rechenzeiten insbesondere bei Koordinierungen und weiteren möglichst praxisnahen Tests beschäftigen.
7 Danksagung
Die Autoren möchten Christian Liebchen und Gregor Wünsch danken, die an den ersten Ideen für das zyklisch zeitexpandierte Netzwerk beteiligt waren; Gregor Wünsch gestattete uns freundlicherweise die Nutzung von Abbildung 1. Wir möchten der ptv AG und ganz besonders Herrn Dr. Klaus Nökel für die Bereitstellung von Szenarien, die Möglichkeit zur Nutzung von VISUM und VISSIM für unsere Experimente sowie für fruchtbare Diskussionen danken. Gleichermaßen gilt unser Dank Prof. Dr. Kai Nagel und seiner Arbeitsgruppe fu¨r die Bereitstellung von MATSim samt LSA-Modul.
Diese Arbeit wurde vom Bundesministerium für Bildung und Forschung im Rahmen des ADVEST-Projekts im Programm Mathematik für Innovationen in Industrie und Dienstleistungen gefördert.
Literatur
[1] SCHRANK, D. und T. LOMAX: 2009 Urban Mobility Report. Texas Transportation Institut, 2009. Verfügbar unter http://tti.tamu.edu/documents/mobility report 2009 wappx. pdf.
[2] ADOLPH, J.: Regelung des Wagenverkehrs in Straßen mittels elektrischer Signallampen. Reichspatentamt, 1925. DE 439255 A.
[3] MORGAN, J. T. und J. D. C. LITTLE: Synchronizing traffic signals for maximal bandwidth. Journal of the Operations Research Society of America, 12(6):896–912, 1964.
[4] LÄMMER, S.: Reglerentwurf zur dezentralen Online-Steuerung von Lichtsignalanlagen in Straßennetzwerken. Doktorarbeit, Technische Universität Dresden, 2007.
[5] BRETHERTON, R. D. und G. I. RAI: The use of SCOOT in low flow conditions. Traffic Engineering & Control, Seiten 574–576, 1982.
[6] LÄMMER, S.: Stabilitätsprobleme vollverkehrsabhängiger Lichtsignalsteuerungen. Technischer Bericht, Technische Universität Dresden, 2009.
[7] GARTNER, N. H., J. D. C. LITTLE und H. GABBAY: Optimization of traffic signal settings by mixed-integer linear programming, Part I: The network coordination problem. Transportation Sciences, 9:321–343, 1966.
[8] LITTLE, J. D. C.: The Synchronizing of Traffic Signals by Mixed-Integer Linear Programming. Operations Research 14, Seiten 568–594, 1966.
[9] WÜNSCH, G.: Coordination of Traffic Signals in Networks. Doktorarbeit, Technische Universität Berlin, 2008.
[10] KÖHLER, E., R. H. MÖHRING und G. WÜNSCH: Minimizing Total Delay in Fixed-Time Controlled Traffic Networks. In: Proceedings of Operations Research (OR), 2004.
[11] ROBERTSON, D. I.: TRANSYT method for area traffic control. Traffic Engineering & Control, 10:276 – 281, 1969.
[12] BELL, M. C. und R. D. BRETHERTON: Ageing of fixed-time traffic signal plans. In: 2nd International Conference on Road Traffic Control, London, 1986.
[13] ALLSOP, R. E. und J. A. CHARLESWORTH: Traffic in a signal-controlled road network: An example of different signal timings inducing different routeings. Traffic Eng. Control, 18(5): 262–265, 1977.
[14] CHIOU, S. W.: Optimization of Area Traffic Control for Equilibrium Network Flows. Doktorarbeit, University College London, 1999.
[15] BELL, M. G. H. und H. CEYLAN: Traffic signal timing optimization based on genetic alorithm approach, including drivers’ routing. Transportation Research Part B, 38:329–342, 2004.
[16] TEKLU, F., A. SUMALEE und D. WATLING: A genetic algorithm approach for optimizing traffic control signals considering routing. Computer-Aided Civil and Infrastructure Engineering, 22:31–43, 2007.
[17] MÖHRING, R. H., K. NÖKEL und G. WÜNSCH: A model and fast optimization method for signal coordination in a network. In: ZUYLEN, H. VAN und F. MIDDELHAM (Herausgeber): Proceedings of the 11th IFAC Symposium on Control in Transportation Systems - CTS 2006, Seiten 73–78, Delft, The Netherlands, 2006.
[18] SUN, D., R. F. BENEKOHAL und S. T. WALLER: Multiobjective traffic signal timing optimizing using non-dominated sorting genetic algorithm. In: IEEE IV2003 Intelligent Vehicles Symposium, 2003.
[19] AHUJA, R. K., T. L. MAGNANTI und J. B. ORLIN: Network flows. Prentice Hall, 1993.
[20] ROUGHGARDEN, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge, MA, 2005.
[21] GARTNER, N. H., C. J. MESSER und A. K. RATHI (Herausgeber): Revised Monograph on Traffic Flow Theory: A State-of-the-Art ReportTraffic flow theory. Turner-Fairbank Highway Research Center, Federal Highway Administration, U.S. Dept. of Transportation, 2005. Verfügbar unter http://www.tfhrc.gov/its/tft/tft.htm.
[22] DIOS ORTU´ ZAR, JUAN DE und LUIS G. WILLUMSEN: Modelling Transport. Wiley, Chichester, 2006.
[23] FORD, L. R. und D. R. FULKERSON: Flow in Networks. Princeton University Press, Princeton, 1962.
[24] KÖHLER, E., R. H. MÖHRING und M. SKUTELLA: Traffic networks and flows over time. In: LERNER, J., D. WAGNER und K. A. ZWEIG (Herausgeber): Algorithmics of Large and Complex Networks, LNCS 5515, Seiten 166–196. Springer, 2009.
[25] VISSIM MANUAL. Verfügbar unter http://www.ptvag.com/.
[26] HOMEPAGE MATSIM. Verfügbar unter http://www.matsim.org/. |
