54
Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen Algorithmen Algorithmen - - Kruskal & Co. Kruskal & Co.

Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Embed Size (px)

Citation preview

Page 1: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 1Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Page 2: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 2Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Inhalt1. Einleitung

1.1 Aufgabe – Netzentwurf1.2 Optimierungsproblem1.3 Optimierungsverfahren

2. Kruskal - Spannende Bäume 2.1 Problem 2.2 Algorithmen

3. Steiner Bäume 3.1 Problem 3.2 Algorithmen 

4. Reduktionsverfahren nach Heck 4.1 Verfahren 4.2 Beispiele

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 3: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 3Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Aufgabe von Verkehrsnetzen

Verkehrsnetze verbinden Räume und erschließen sie.

Sie dienen dem Transport von Personen und Gütern.

Verkehrsnetze bilden das Rückgrat eines jeden Verkehrssystems.

Der Entwurf von Verkehrsnetzen ist eine wichtige Aufgabe der Verkehrsplanung.

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 4: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 4Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Planung von Verkehrsnetzen

Wir betrachten hier Straßennetze und Netze des öffentlichen Verkehrs.

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Hannover : Straßennetz Region Liniennetz der Stadtbahn - ÜSTRA

Page 5: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 5Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Wirkungsgefüge: Raum und Verkehr

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Wechsel der Aktivitäten

Ortswechsel - Wege

Verkehrsnachfrage

Raum Verkehrsnachfrage

Verkehrsnetz

VerkehrsnetzDie Raumstruktur bestimmt die Verkehrsnachfrage und damit die

Struktur der Verkehrsnetze.

Page 6: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 6Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Wirkungsgefüge: Raum und Verkehr

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Zentrale Orte Verkehrsnachfrage - Pendler

Raumstruktur - Verkehrsnachfrage - Struktur der Verkehrsnetze

Page 7: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 7Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Anforderungen an Verkehrsnetze Verkehrsqualität

das Verkehrsnetz hat die vorhandene Verkehrsnachfrage

bei einem Mindestangebot an Verkehrsqualität aufzunehmen.

Wirtschaftlichkeit Sicht des Betreibers:• minimale Bau- und Unterhaltungskosten

und der Nutzer:• minimale Betriebs- und Zeitkosten

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 8: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 8Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Anforderungen an Verkehrsnetze Sicht der Allgemeinheit:

• geringe Beeinträchtigung der Umweltqualität durch • Lärm, Abgase und • Unfälle sowie • die Schonung der Ressourcen:

– Energie und – Flächen

>>> komplexes multikriterielles Optimierungsproblem

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 9: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 9Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Zielkonflikt: Netzlänge - Fahrtweiten

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 10: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 10Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Zielkonflikt: Netzlänge - Fahrtweiten

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

N.-Länge F.-Weite

A 2,74 8,64

B 2,83 8,49

C 3,42 8,25

D 4 8

E 6,83 6,83

Page 11: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 11Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Zielkonflikt: Netzlänge - Fahrtweiten

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

0123456789

10

A B C D E

Netzfall

Sei

ten

län

ge

a

Netzlänge

Fahrtweite

N.-Länge F.-Weite

A 2,74 8,64

B 2,83 8,49

C 3,42 8,25

D 4 8

E 6,83 6,83

Page 12: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 12Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Zielkonflikt: Netzlänge - Fahrtweiten

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

0123456789

10

A B C D E

Netzfall

Sei

ten

län

ge

a

Netzlänge

Fahrtweite

N.-Länge F.-Weite

A 2,74 8,64

B 2,83 8,49

C 3,42 8,25

D 4 8

E 6,83 6,83

Gesamtkosten

0

5

10

1520

25

30

35

A B C D E

Netzfall

Sei

ten

län

ge

a

Weiten: 1

Weiten: 3

Page 13: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 13Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Netzentwurf – Aufgaben Aufgaben Verkehrsnetzplanung

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Entwicklung von ideellen Netzkonzepten (RIN*) Entwicklung von Planfällen in realen Netzen

aus Maßnahmenkatalog

neue Verbindungen

Ausbau/Rückbau

Betrieb

Formale Aufgaben Strukturoptimierung Netzdimensionierung

*Rahmenrichtlinie für die integrierte Netzgestaltung

Page 14: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 14Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Optimierungsproblem: Netzentwurf

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Entwicklung von Planfällen aus Maßnahmen-katalog

Netzhierarchie!

Problem:

hohe

Kombinatorik !!!

Page 15: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 15Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Netzentwurf – Methodisches Vorgehen Konstruktionsprinzipien:

RAS-N*

• Alternativverfahren

• Reduktionsverfahren*

• Progressivverfahren*

*rechnergestützt

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

*RICHTLINIEN FÜR DIE ANLAGE VON LANDSTRASSEN – Teil: Straßennetzgestaltung

Netzhierarchie Konzentration > Auslastung !

Planerisch-intuitiv

Reduktion aus Maximalnetz Aufbau aus Minimalnetz

>>> Optimierung

Page 16: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 16Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Optimierungsproblem: Netzentwurf

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Allgemein

i

i,j

j

n n

i j i,ji=1 j=1

i i i

Optimierungsproblem

Netzentwurf

mit:

f =Entscheidungsvariable

k =Bewertungsgröße

g =

Zielfunktion:(1.1)

f * g *k =Min!

Nebenbedingungen:(1.2)

0 f c ......c =Grenzwer

Gew c t

t

i h e

Page 17: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 17Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Optimierungsproblem: Netzentwurf

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Allgemein

i

i,j

j

n n

i j i,ji=1 j=1

i i i

Optimierungsproblem

Netzentwurf

mit:

f =Entscheidungsvariable

k =Bewertungsgröße

g =

Zielfunktion:(1.1)

f * g *k =Min!

Nebenbedingungen:(1.2)

0 f c ......c =Grenzwer

Gew c t

t

i h e

Netzmodell: Verkehrsnetz > Graph(V,E,c)

Entscheidungsvariable:

Kanten

Bewertungsgrößen:

Längen, Zeiten, Kosten...

Grenzwerte:

Kapazität, Lärm, Abgase...

Page 18: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 18Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Spannende Bäume - Problem

  Gegeben sei ein zusammenhängendergewichteter Graph G = (V,E,c), mit c > 0,wobei c die Länge der Kanten sein kann.

Gesucht ist ein zusammenhängender Untergraph G' = (V,E'), der alle Knoten von G enthält und dessen Gesamtlänge möglichst klein ist. Ergebnis >>> Minimalgerüst in einem bewerteten Graphen

Algorithmen: Prim und Kruskal

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Page 19: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 19Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Spannende Bäume – Algorithmus von Kruskal

Anfang: Sortiere die Kanten aufsteigend nach der Länge in eine Kandidatenliste

1. Wähle die Kante des Graphen G mit der kleinsten Bewertung 2. Für alle Kanten:  Wähle die Kante des Graphen G mit der nächst kleinsten Bewertung,

sofern dadurch kein Kreis entsteht.

Da der Algorithmus insgesamt n Iterationen benötigt,beträgt die gesamte Komplexität O(n*log(n)) .

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Analogie:

Kürzeste Wege

Page 20: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 20Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 23 54 75 76 87 108 119 1210 1511 1712 2013 2714 3215 3316 67

Angewandte Geometrie &Diskrete Mathematik -TUMProf. Dr. Peter GritzmannDr. René Brandenberg

Page 21: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 21Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 54 75 76 87 108 119 1210 1511 1712 2013 2714 3215 3316 67

Page 22: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 22Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 75 76 87 108 119 1210 1511 1712 2013 2714 3215 3316 67

Page 23: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 23Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 87 108 119 1210 1511 1712 2013 2714 3215 3316 67

Page 24: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 24Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 8 x7 108 119 1210 1511 1712 2013 2714 3215 3316 67

Page 25: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 25Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 8 x7 108 119 1210 1511 1712 2013 2714 3215 3316 67

Page 26: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 26Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 8 x7 10 x8 119 1210 1511 1712 2013 2714 3215 3316 67

Page 27: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 27Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 8 x7 10 x8 11 x9 1210 1511 1712 2013 2714 3215 3316 67

Page 28: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 28Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiel - Ablauf des Algorithmus

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Kanten Kandidaten-

liste nach Länge1 1 x2 2 x3 5 x4 7 x5 76 8 x7 10 x8 11 x9 1210 1511 17 x12 2013 2714 3215 3316 67

Angewandte Geometrie &Diskrete Mathematik - TUM Prof. Dr. Peter GritzmannDr. René Brandenberg

Page 29: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 29Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Gibt es noch Verbessungen ? Steiner Bäume

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Steiner Bäume sind

eine Verallgemeinerung

der spannenden Bäume.

Page 30: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 30Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Steiner Bäume

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Problemformulierung:

Gegeben sind n Punkte,

die miteinander zu verbinden sind,

wobei die Lage von m Zwischenpunkten mit ihren Verbindungen untereinander so zu bestimmen sind,

dass die Gesamtlänge ein Minimum annimmt.

Page 31: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 31Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiele: gegeben n = 3, 4, 9 und 25

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Steiner BäumeSpannende Bäume sind

eine obere Schranke für Steiner Bäume.

Komplexität:

n > 4 NP-vollständig

Page 32: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 32Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Beispiele: gegeben n = 3, 4, 9 und 25

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Steiner BäumeAlgorithmen:

Exakte Optimierung

Heuristische Optimierung

Anwendungen:

Optimierung der Netzstruktur• Reduktionsverfahren

• Progressivverfahren

Page 33: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 33Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren nach Heck Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Rasternetz 4 x 4 Knoten

Die Umlegungen wurden mit einem

Gleichgewichtsmodell mit AMBOS - TRANSVER durchgeführt.

Page 34: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 34Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

F i,j = const

Umlegung:

Basisnetzmit Belastung

Page 35: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 35Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 36: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 36Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 37: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 37Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 38: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 38Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 39: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 39Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 40: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 40Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Plus Minus

Page 41: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 41Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Reduktionsverfahren Beispiel Rasternetz

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Veränderungen

Page 42: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 42Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Konzept der Reduktion Eingaben: Nachfragematrix

• Maximalnetz entwerfen

Start: Umlegung0

• Kriterium: Reisezeit

• Ergebnis: Netzbelastung0

Iteration: (i=1..x) > Umlegungi

• Kriterium: Gesamtkosten*/Auslastungalpha

*Bau-und Nutzerkosten

• Ergebnis: Netzbelastungi

Stop falls:

• Netzbelastungi = Netzbelastungi+1

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Maximalnetz Schritt 1

Page 43: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 43Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Konzept der Reduktion Eingaben: Nachfragematrix

• Maximalnetz entwerfen

Start: Umlegung0

• Kriterium: Reisezeit

• Ergebnis: Netzbelastung0

Iteration: (i=1..x) : Umlegungi

• Kriterium: Gesamtkosten*/Auslastungalpha

*Bau- und Nutzerkosten

• Ergebnis: Netzbelastungi

Stop falls:

• Netzbelastungi = Netzbelastungi+1

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Maximalnetz Schritt 1

Endergebnis

Page 44: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 44Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Raum- Struktur

Region Hannover

Gemeinden

Ortsteile

REDUKTIONSVERFAHREN nach Heck

Page 45: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 45Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

REDUKTIONSVERFAHREN

Bezirksgrenzen

Ortsteile

Region Hannover

373 Verkehrs-bezirke

Page 46: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 46Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

REDUKTIONSVERFAHREN

Maximalnetz

Anfangslösung

Region Hannover

373 Verkehrs-bezirke

Page 47: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 47Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

REDUKTIONSVERFAHREN

Ergebnis

Region Hannover

373 Verkehrs-bezirke

Page 48: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 48Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

REDUKTIONSVERFAHREN

Ergebnis: ideelles Netz reales Netz ÖV

DB + Stadtbahn

Bus

Page 49: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 49Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Teilmatrix:

Tangential-verbindungen

Stadtgebiet

Hannover

REDUKTIONSVERFAHREN

Page 50: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 50Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

REDUKTIONSVERFAHREN

Ergebnis

Stadtgebiet

Tangential-

verbindungen

Page 51: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 51Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Algorithmische Geometrie

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

373 VerkehrsbezirkeSpiderwebnetz

Aufgabe: Generieren eines Netzmodells

Page 52: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 52Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Algorithmische Geometrie Teilgebiet der Informatik

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Speicherung und Verarbeitung geometrischer Daten

Lösung geometrischer Distanzprobleme Instrumente:

• Voronoi• Diagramm• Delaunay Triangulation• Spannende Bäume

Page 53: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 53Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Algorithmische Geometrie Distanzprobleme

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

Voronoi-

Diagramm

Delaunay Triangulation

AppletsFernUniversität Hagen

Verteilte Systeme

Dr. Christian Iking

Page 54: Folie 1 Workshop: Anwendung von Entscheidungs- und Optimierungsmethoden im Verkehr 09.Dezember 2005, Darmstadt Netzoptimierung mit geometrischen Algorithmen

Folie 54Workshop: Anwendung von Entscheidungs- und

Optimierungsmethoden im Verkehr09.Dezember 2005, Darmstadt

Netzoptimierung mit geometrischen Netzoptimierung mit geometrischen AlgorithmenAlgorithmen - - Kruskal & Co.Kruskal & Co.

Algorithmische Geometrie Minimalstruktur

KruskalKruskalEinleitungEinleitung Steiner BäumeSteiner Bäume ReduktionsverfahrenReduktionsverfahren

1.Generieren eines Netzmodells (Modellierung des Raumes)gegeben: Bezirke

Voronoi Diagramm Delaunay Triangulation

Ergibt: Netzmodell

2. NetzkonzeptKruskal – Spannender BaumSpannender Baum mit KapazitätSteiner BaumReduktionsverfahren