A. Horni

IVT, ETH Zurich

Umlegung

Zwischenfragen

PPT → Netz

Wozu?

z.B. Prognosen

(z.B. Reisezeit im Netz, Streckenbelastung, …)

→ Planungswerkzeug

Umlegungsverfahren (generell 4-Stufen-Ansatz) – wozu?

z.B. 4-Stufen-Ansatz

Strassennetz

Direkte Lenkung von realen Verkehrsflüssen

Umlegung =

4. Schritt des 4-Stufen-Ansatzes

3

1

4 6

12

3

Zürich

Zug

Frauenf

ZugFfZürich Ziel

Quelle

6 12

4

3

234

4→?

4→?

?

Verkehrserzeugung

Verkehrsanziehung

VerkehrsverteilungVerkehrsmittelwahl

2

20

Umlegung

(Routenwahl)

tP=35 min [1 + P (lP/cP)P]

Herleitung am Bsp. QZ. Airolo-Göschenen

BPR:

t = t0 [1 + (load/capacity)]

Nutzenmaximierung (t)

→ Reisezeitminimierung

Keiner kann durch alleinigen Wechsel

gewinnen!

Nachfrage 1600 Fzg./h

T = P = 1; T = P = 2

cT = 1600 Fzg./h cP = 1500 Fzg./h

?

?

tT=25min [1 + T (lT/cT)T]

Wardrop-Gleichgewicht: Alle Wege, die zwischen einem Quelle-Ziel-Paar benutzt werden, haben dieselbe Reisezeit (generalisierten Kosten).

Alle nicht benutzten Wege zwischen einem Quelle-Ziel-Paar haben eine höhere Reisezeit (generalisierte Kosten)

lT ~ 1200 Fzg./h

lP ~ 400 Fzg./h

Berechnung des Gleichgewichtspunktes?

• BelastungTunnel; BelastungPass = Nachfrage - BelastungTunnel

• Riesige Anzahl von Netzwerkkanten, welche Einfluss aufeinander haben.

• Nichtlineares System x

→ Nicht analytisch (oder graphisch) lösbar

→ Iterativ, numerisches Verfahren wird benötigt

Berechnungsverfahren

• Wie könnte das aussehen?

• Gewicht Schale → Fahrtzeit (bzw. generalisierte Kosten)• Unterschiedliche Schalen → unterschiedliche

Strassenparameter: t0, Kapazität,

Berechnungsverfahren

• Verschiedene Umlegungsverfahren

Nicht iterativ:

Lege kleine Portionen auf die jeweils leichtere Schale bis Mehl komplett auf der Waage.

→ Incremental assignment (Ortuzar S. 340)

Iterativ:

Verschiebe solange Mehl von der schwereren Schale zur leichteren bis beide gleich schwer sind.

→ Method of Successive Averages (Ortuzar S. 342)

?

?

SCANS

MSA → Prüfungsaufgabe!

• Method of Successive Averages (MSA)

• Anteil Mehl → Umlegungsparameter

• Verfeinerung:

Starte (falls Ungleichgewicht gross) mit grossem und lasse immer kleiner werden, sonst haben wir irgendwann Oszillationen ohne weitere Annäherung ans Gleichgewicht.

• Randbemerkung:

Berechnung von in Abhängigkeit zum Abstand vom GG → Frank-Wolfe (kommt nicht an Prüfung!)

MSA – 2 Routen

A B

Belastung: x

t: 50 min

Belastung: y

t: 40 min

Anteil von x

→ min

Anteil von der langsameren auf die schnellere Route

MSA – 3 Routen

A B

Belastung: x

t: 50 min

Belastung: y

t: 40 min

Anteil von x

→ min

Belastung: z

t: 60 min

Anteil von z

Anteil von allen langsameren auf die schnellste Route

400 + 800 Fzg./h = 1200 Fzg./h400 + 800 Fzg./h = 1200 Fzg./h

MSA – 2 Quell-Zielbeziehungen

Airolo

Anteil von 400 Fzg./h

Göschenen

Andermatt

QZ 1: Airolo-Göschenen, 1600 Fzg./h

Route 1: Pass tAirolo-Andermatt + tAndermatt-Göschenen

Route 2: Tunnel tTunnel

QZ 2: Andermatt-Göschenen, 800 Fzg./h

Route 1: Passabfahrt tAndermatt-Göschenen

1200 Fzg./h

400 Fzg./h

tAndermatt-Göschenen

tAirolo-Andermatt

tTunnel

Umlegung: Jede QZ. einzeln →

ABER: Zeit kombiniert!

A

C

B1240 Fzg./h

360 Fzg./h 360 + 800 Fzg./h = 1200 Fzg./h

GG: ~400; ~1200

Quell-Zielbeziehung - Klärung

Airolo Göschenen

Andermatt

QZ 1: Airolo-Göschenen

Quelle: A

Ziel: B (nicht C!)

QZ 2: Andermatt-Göschenen

Quelle: C

Ziel: B

A B

C

MSA - Rechenbeispiel

A BTunnel

Pass

konstant 0.1

(10% von der langsameren auf die schnellere Route)

160.0 Fzg./h

Tunnel Pass

It Bel.

F/h

t

(min)

Bel.

F/h

t

(min)

t(min)

0 1600 50.0 0 35.0 15.0

1 1440.0 45.3 160.0 35.4 9.9

2 1296.0 41.4 304.0 36.4 5.0

3 1166.4 38.3 433.6 38.0 0.3

4 1049.8 35.8 550.2 39.7 3.9

5 1104.8 36.9 495.2 38.8 1.9

144.0 Fzg./h

0.1 * 1600.0 Fzg./h → 160.0 Fzg./h

0.1 * 1440.0 Fzg./h → 144.0 Fzg./h

129.6 Fzg./h

0.1 * 1296.0 Fzg./h → 129.6 Fzg./h

0.1 * 1166.4 Fzg./h → 116.6 Fzg./h

116.6 Fzg./h

0.1 * 550.2 Fzg./h → 55.0 Fzg./h

55.0 Fzg./h

Nachfrage 1600 Fzg./h

T = P = 1; T = P = 2

cT = 1600 Fzg./h cP = 1500 Fzg./h

tP=35 min [1 + P (lP/cP)P]

tT=25min [1 + T (lT/cT)T]

Prüfung: Initialisierung gegeben

MSA → Ortuzar (Hilfsflüsse Fa)

A B

Belastung: x

t: 50 min

Belastung: y

t: 40 min

Anteil von x

→ min

Belastung: z

t: 60 min

Anteil von z

2: y + * x + * z

= (1-) * y + * y + * (x+z)

= (1-) * y + * (x+y+z)

= (1-) * y + * Fa

1

2

3

3: (1-) * z + * 0

→ Fa = x + y + z (komplette Nachfrage auf günstigste Route)

1: (1-) * x + * 0

Salopp formuliert:

Anteil von allen langsameren auf

die schnellste Route

Fa

Allgemeines zum Verfahren

• Geschwindigkeit ↔ Genauigkeit

( konstant)

• Stabilität bez. Konvergenz

Verfahren soll natürlich von jedem beliebigen Startpunkt aus

zum Gleichgewicht konvergieren!

• Gibt es mehrere Gleichgewichte?

• Abbruchkriterium:• „1. Ordnung“: Angestrebte Genauigkeit e

• z.B.: Relative Reisezeitdifferenz zwischen Routen ≤ 1% pro QZ-Beziehung

∞

Wie findet man die schnellste Route? → Dijkstra

0

∞1

∞4

0: Initialisierung

•Startknoten als Arbeitsknoten und als definitiv markieren

•Restliche Knoten als unerreichbar markieren (d=∞)

I:

•Trage in allen Nachbarknoten des aktuellen Arbeitsknotens die Distanz zum Startknoten ein, falls diese kleiner ist, als der eingetragene Wert.

•Merke mir in diesem Fall in den Nachbarknoten den aktuellen Arbeitsknoten als Vorgänger.

II:

Aus allen Knoten, die noch nicht als definitiv markiert sind, wird derjenige mit dem kleinsten Wert im Distanzfeld ausgesucht, als definitiv markiert und zum neuen Arbeitsknoten gemacht.

III:

Verfolge die Route beginnend beim Zielknoten zurück

∞

-

A

A

5

C8 D

ED - B - A - Route:

Distanz zum Startkknoten

Vorgänger definitiv

A

B

C

D

E

x

x

x

B

9

x

x

Übung C

• 3 Aufgaben• Dijkstra• 1 Quell-Zielbeziehung, 3 Routen• 2 Quell-Zielbeziehungen (2 + 1) Routen

• XLS

• In 4er Gruppen

• Ortuzar/Willumsen Umlegungskapitel PDFs

• Korrektur r/f → häufigste Probleme & Fragen in ML

Befragung

• freiwillig!• Aber bitte NICHT als Gruppe ausfüllen, sondern einzeln• www.andreashorni.ch/vpl

R = 2 * Dmax