Jörg Rambau Version 0.1.0 vom 15. März 2005...kalender 2004 [MATHEON04] des DFG-ForschungszentrumsMATHEON, Berlin, gestaltet: Am Beispiel des ASSIGNMENT PROBLEMS (AP) werden untere

Diskrete Optimierung in

Telekommunikation,

Logistik und Verkehr

Jörg Rambau

Version 0.1.0 vom 15. März 2005

Inhaltsverzeichnis

1 Einleitung 11

1.1 Aspekte der Diskreten Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1.1 Gelbe Engel, ein Handlungsreisender und die Sprache der Mathematik (Vortrag). . . . . 11

1.1.2 Untere Schranken am Beispiel desASSIGNMENTPROBLEMS (AP) . . . . . . . . . . . . 11

1.1.3 Graphentheoretische Modellierung desAPs . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1.4 Modellierung desAPs durch ein Ganzzahliges Lineares Programm (ILP) . . . . . . . . . 11

1.2 Optimierungsprobleme und Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1 Optimierungsprobleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.2 Optimierungsalgorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.3 Laufzeitkomplexität von Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.4 Polynomialzeitalgorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.5 Schwere und leichte Probleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.6 Das OptimierungsproblemINTEGERL INEAR PROGRAMMING (ILP) . . . . . . . . . . . 12

1.2.7 ∗Totale Unimodularität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Ein Kantenauswahl-Modell für dasAP . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

I Telekommunikation 15

2 Netzdimensionierung bei E-Plus (Dienstag) 17

2.1 Hintergrund: Aufbau und Planung eines GSM-Netzes. . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.1 Logische Architektur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.2 Ein logischer Kommunikationsweg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.3 Physikalische Architektur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Optimierungsprobleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Inhaltsverzeichnis

2.2.1 Hierarchie der Planungsaufgaben. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.2 Transportnetzplanung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.1 Standardmodelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.2 Standardmodelle mit Ausfallsicherheit. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.3 Beispiel: EinILP-Modell für dasM INIMUM SPANNING TREE PROBLEM (MST) . . . . 18

2.3.4 Das DiscNet-Modell (ohne Ausfallsicherheit). . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.1 DasM INIMUM SPANNING TREE PROBLEM (MST) ist in P . . . . . . . . . . . . . . . . 18

2.4.2 DasM INIMUM STEINER TREE PROBLEM (STP)ist NP-schwer. . . . . . . . . . . . . . 18

2.4.3 ∗Matroide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.1 Ein Kantenauswahl-Modell für dasMST . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 UMTS (Mittwoch) 21

3.1 Hintergrund: UMTS-Technologie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.1 Architektur der Funkschnittstelle eines UMTS-Netzes. . . . . . . . . . . . . . . . . . . 21

3.1.2 Wide Code Division Multiple Access (WCDMA). . . . . . . . . . . . . . . . . . . . . . 21

3.1.3 Die CIR-Target-Bedingungen für erfolgreiche Übertragung. . . . . . . . . . . . . . . . . 21


3.2.1 Standortplanung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2.2 Antennenkonfiguration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3.1 Standardmodelle der Standortplanung. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3.2 Modelle zur Lastmessung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3.3 ∗Modelle zur Antennenkonfiguration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4.1 ∗Invertierbarkeit von Matrizen(I −C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4.2 CAPACITATED FACILITY LOCATION PROBLEM (CFLP) ist NP-schwer. . . . . . . . . . 22

3.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Inhaltsverzeichnis 5

3.5.1 Ein Standortplanungsmodell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Frequenzzuweisung bei E-Plus (Donnerstag) 25

4.1 Hintergrund: Die GSM-Funkschnittstelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1.1 Architektur des GSM-Funknetzes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1.2 Das Beispielnetz TINY. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25


4.2.1 Frequenzzuweisung mit möglichst wenig Frequenzen. . . . . . . . . . . . . . . . . . . . 25

4.2.2 Frequenzzuweisung mit möglichst wenig Interferenz. . . . . . . . . . . . . . . . . . . . 25

4.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3.1 Standardmodelle aus der Graphenfärbung. . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3.2 Ein Modell für dasGRAPH COLORING DECISION PROBLEM (GCP-D) . . . . . . . . . . 26

4.3.3 Ein Modell für dasFREQUENCYASSIGNMENTPROBLEM (FAP) . . . . . . . . . . . . . 26

4.3.4 ∗Ein Frequenzzuweisungsmodell für Separation Eins ohne Nachbarkanal-Interferenz. . . . 26

4.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.4.1 Gültige Ungleichungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.4.2 Cliquen-Ungleichungen für Graphenfärbung. . . . . . . . . . . . . . . . . . . . . . . . 26

4.4.3 Perfekte Graphen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.4.4 Kurzvorstellung: Branch & Bound, Branch & Cut, Cut & Branch. . . . . . . . . . . . . 26

4.4.5 Facettendefinierende Ungleichungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.5.1 Stabile-Mengen-Modelle fürFAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.5.2 Stabile-Mengen-Modelle fürFAP mit Cliquen-Ungleichungen. . . . . . . . . . . . . . . 28

4.5.3 Berechnung mit und ohne automatische Cuts. . . . . . . . . . . . . . . . . . . . . . . . 28

4.5.4 ∗Ein ILP für 6-PARTITION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Konfiguration optischer Netze bei T-Systems Nova (Freitag) 31

5.1 Hintergrund: Optische Netze. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.1.1 Optische Netze erster Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31


5.1.2 Optische Netze zweiter Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.1.3 Hardware-Komponenten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31


5.2.1 Transportnetzplanung mit Routing und Wellenlängenzuordnung. . . . . . . . . . . . . . 31

5.2.2 Wellenlängenzuordnung mit möglichst wenig Konversion. . . . . . . . . . . . . . . . . 32

5.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.3.1 Standardmodelle für Bedarf Eins pro Verbindung. . . . . . . . . . . . . . . . . . . . . . 32

5.3.2 Standardmodelle für sequentielles Routen und Färben. . . . . . . . . . . . . . . . . . . 32

5.3.3 Mehrgüterfluss-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.3.4 Ein Assignment-Modell für dasMCWAP . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.3.5 Ein Packing-Modell für dasMCWAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.4.1 DasSHORTESTPATH PROBLEM (SPP)ist in P . . . . . . . . . . . . . . . . . . . . . . . 32

5.4.2 ∗DasRESOURCECONSTRAINED SHORTESTPATH PROBLEM (RCSPP)ist NP-schwer. . 33

5.4.3 ∗DasEDGE DISJOINT PATH PROBLEM (EDP) ist NP-schwer. . . . . . . . . . . . . . . . 33

5.4.4 ∗DasM INIMUM COST MULTI -COMMODITY FLOW PROBLEM (MCMCF) ist NP-schwer 33

5.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.5.1 Ein Bogenauswahl-Modell für dasSPP . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.5.2 Ein Bogenauswahl-Modell für dasLONGESTPATH PLUS CYCLES PROBLEM (LPPCP) . 34

5.5.3 Ein Bogenauswahl-Modell für dasLONGESTPATH PROBLEM (LPP) . . . . . . . . . . . 35

II Logistik 37

6 Regalbediengerätsteuerung bei der Siemens Nixdorf Informationssysteme GmbH (Montag) 39

6.1 Hintergrund: Hochregallagertechnik. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.1.1 Matrialfluss im betrachteten Hochregallager. . . . . . . . . . . . . . . . . . . . . . . . . 39

6.1.2 Führerlose Regalbediengeräte (RBGs). . . . . . . . . . . . . . . . . . . . . . . . . . . . 39


6.2.1 Der Online-/Echtzeit-Aspekt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.2.2 Grundlegende Online-Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39


6.2.3 Reoptimierung: Finde beste Reihenfolge für bekannte Aufträge. . . . . . . . . . . . . . 40

6.2.4 Reihenfolgeplanung für ein RBG mit möglichst wenigen Leerbewegungen. . . . . . . . 40

6.2.5 Reihenfolgeplanung für ein RBG mit Präzedenzen. . . . . . . . . . . . . . . . . . . . . 40

6.2.6 Reihenfolgeplanung für ein RBG mit Zeitfenstern. . . . . . . . . . . . . . . . . . . . . . 40

6.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.3.1 DasASYMMETRIC TRAVELING SALESMAN PROBLEM (ATSP) . . . . . . . . . . . . . 40

6.3.2 DasATSP MIT PRÄZEDENZEN (ATSPPC). . . . . . . . . . . . . . . . . . . . . . . . . 40

6.3.3 DasATSP MIT ZEITFENSTERN(ATSPTW) . . . . . . . . . . . . . . . . . . . . . . . . 41

6.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.4.1 Die Christofides-Heuristik für dasTSPmit Dreiecksungleichung . . . . . . . . . . . . . 41

6.4.2 Kompetitive Analyse von Online-Algorithmen. . . . . . . . . . . . . . . . . . . . . . . 41

6.4.3 Es gibt keinen kompetitiven Online-Algorithmus für die Minimierung der Leerbewegungen41

6.4.4 Reoptimierung des Makespan ist5/2-kompetitiv für die Online-Minimierung des Makespan41

6.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.5.1 Ein Bogenauswahl-Modell für dasATSP . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Lastenfahrstuhlsteuerung bei der Herlitz PBS AG (Dienstag) 45

7.1 Hintergrund: Paletten-Fördertechnik. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7.1.1 Das Versandlager Falkensee. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7.1.2 Die Vertikalfördertürme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45


7.2.1 Der Online-/Echtzeitaspekt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7.2.2 Where is the Elevator? (Vortrag mit Simulationen). . . . . . . . . . . . . . . . . . . . . 45

7.2.3 VFS-Reihenfolgeplanung mit wenig Leerfahrten. . . . . . . . . . . . . . . . . . . . . . 45

7.2.4 VFS-Reihenfolgeplanung mit wenig Wartezeit. . . . . . . . . . . . . . . . . . . . . . . 46

7.2.5 VFS-Reihenfolgeplanung mit beschränkter Wartezeit. . . . . . . . . . . . . . . . . . . . 46

7.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.3.1 DasONLINE-DIAL -A-RIDE PROBLEM (ONLINEDARP) . . . . . . . . . . . . . . . . . 46

7.3.2 EinATSP-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.3.3 DasM IXED CHINESE POSTMAN PROBLEM (M IXEDCPP) . . . . . . . . . . . . . . . . 46


7.3.4 DasM IXEDCPPauf der Linie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.4.1 Auf der Linie istM IXEDCPPin P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.4.2 Kein kompetitiver Online-Algorithmus für die Minimierung der Wartezeit. . . . . . . . . 46

7.4.3 IGNORE: beschränkte Flusszeiten unter vertretbarer Belastung. . . . . . . . . . . . . . 47

7.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

7.5.1 EinATSP-Modell für das Fahrstuhlproblem. . . . . . . . . . . . . . . . . . . . . . . . . 47

7.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

8 Optimierte Laserquellenauslastung (Mittwoch) 49

8.1 Hintergrund: Laserschweißen im Karosseriebau. . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.1.1 Eine Laserschweißstation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.1.2 Energieversorgung der Schweißroboter. . . . . . . . . . . . . . . . . . . . . . . . . . . 49


8.2.1 Robotersteuerung mit minimalen Leerverfahrzeiten. . . . . . . . . . . . . . . . . . . . . 49

8.2.2 Robotersteuerung mit minimaler Fertigstellungszeit. . . . . . . . . . . . . . . . . . . . . 49

8.2.3 Robotersteuerung mit minimaler Anzahl von Laserquellen. . . . . . . . . . . . . . . . . 49

8.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.3.1 Ein ATSP-Modell zur Industrierobotereinsatzplanung. . . . . . . . . . . . . . . . . . . . 50

8.3.2 Ein Matching-Modell zur Industrierobotereinsatzplanung. . . . . . . . . . . . . . . . . . 50

8.3.3 Ein Modell zur Minimierung der Laserquellen bei gegebenem Einsatzplan. . . . . . . . . 50

8.3.4 ∗Ein integriertes Modell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.4.1 Branch & Bound:NODE SELECTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.4.2 Branch & Bound:VARIABLE SELECTION . . . . . . . . . . . . . . . . . . . . . . . . . . 50

8.4.3 Modellierung bedingter Nebenbedingungen. . . . . . . . . . . . . . . . . . . . . . . . . 51

8.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

8.5.1 Ein Zeitauswahl-Modell für optimierte Laserquellenauslastung. . . . . . . . . . . . . . . 51

8.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52


III Verkehr 53

9 Fahrzeugeinsatzplanung beim ADAC (Donnerstag) 55

9.1 Hintergrund: Der ADAC-Hilfeservice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.1.1 Hilfezentralen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.1.2 Die Aufgabe der Dispatcher. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55


9.2.1 Online-/Echtzeit-Aspekt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.2.2 Die Reoptimierungsaufgabe beim ADAC. . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.3.1 Ein bogenbasiertes Modell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.3.2 Ein tourbasiertes Modell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

9.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.4.1 Dualität in Linearer Programmierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.4.2 Dynamische Spaltengenerierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.5 ZIMPL-Modelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

9.5.1 Ein Bogenauswahl-Modell für Fahrzeugeinsatzplanung. . . . . . . . . . . . . . . . . . . 56

9.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

10 Umlaufplanung bei der BVG (Freitag) 61

10.1 Hintergrund: Der ÖPNV-Planungsprozess. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.1.1 Die Planungshierarchie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.1.2 Fahrzeugumläufe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61


10.2.1 Das Ein-Depot-Fahrzeugumlaufplanungsproblem. . . . . . . . . . . . . . . . . . . . . . 61

10.2.2 Das Mehr-Depot-Fahrzeugumlaufplanungsproblem. . . . . . . . . . . . . . . . . . . . . 61

10.3 Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

10.3.1 Ein Zirkulationsmodell für die Ein-Depot-Aufgabe. . . . . . . . . . . . . . . . . . . . . 61

10.3.2 Ein Zirkulationsmodell für die Mehr-Depot-Aufgabe. . . . . . . . . . . . . . . . . . . . 62

10.4 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.4.1 Das ganzzahligeM INIMUM COST FLOW PROBLEM (MCFP) ist in P . . . . . . . . . . . 62


10.4.2 Das ganzzahligeM INIMUM COST MULTI -COMMODITY FLOW PROBLEM (MCMCFP)ist NP-schwer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.4.3 Lagrange-Relaxierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.5 ZIMPL-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

10.5.1 EinMCMCF-Modell für Mehr-Depot-Umlaufplanung. . . . . . . . . . . . . . . . . . . 62

Einleitung 1Grundlegendes Material über Graphentheorie, Komplexität und kombinato-rische Optimierung findet sich z. B. in dem Lehrbuch von Korte und Vygen[KV02].

1.1 Aspekte der Diskreten Optimierung bei der Fahr-zeugeinsatzplanung des ADAC

1.1.1 Gelbe Engel, ein Handlungsreisender und die Spracheder Mathematik (Vortrag)

Dieser Vortrag [Ram04b] führt in die Problematik der Einsatzplanung beimADAC ein und beschreibt mathematische Modellierung in der diskretenOptimierung exemplarisch.

1.1.2 Untere Schranken am Beispiel des ASSIGNMENT PROBLEMS

(AP)

Dieser Abschnitt wurde nach einer Aufgabe aus dem Digitalen Advents-kalender 2004 [MATHEON04] des DFG-ForschungszentrumsMATHEON,Berlin, gestaltet: Am Beispiel desASSIGNMENTPROBLEMS (AP) werdenuntere Schranken (= unvermeidbare Kosten) eingeführt.

1.1.3 Graphentheoretische Modellierung des APs

Abstraktion durch Graphentheoretische Formulierung am Beispiel der Zu-ordnung von Fahrzeugen zu Havaristen in der ADAC-Einsatzplanung.

1.1.4 Modellierung des APs durch ein Ganzzahliges LinearesProgramm ( ILP)

Ein mathematisches Modell mit linearer Zielfunktion und linearen Glei-chungen und Ungleichungen sowie Ganzzahligkeitsbedingungen.

1.2 Optimierungsprobleme und Algorithmen

1.2.1 Optimierungsprobleme

Was ist ein Optimierungsproblem?

12 Einleitung

1.2.2 Optimierungsalgorithmen

Was ist ein Optimierungsalgorithmus?

1.2.3 Laufzeitkomplexität von Algorithmen

Wie misst man die Laufzeit eines (Optimierungs-)Algorithmus?

1.2.4 Polynomialzeitalgorithmen

Algorithmen, die als „schnell“ angesehen werden.

1.2.5 Schwere und leichte Probleme

Polynomial lösbare und NP-schwere (Entscheidungs-)Probleme.

1.2.6 Das Optimierungsproblem INTEGER L INEAR PROGRAMMING

(ILP)

Die allgemeine Form eines Ganzzahligen Linearen Programms. Für Mini-mierung z. B.:

min{cTx|x∈ Zn,Ax≤ b}, c∈ Zn, A∈ Zm×n, b∈ Zm.

1.2.7 ∗Totale Unimodularität

Ganzzahligkeitsbedingungen sind (bei Benutzung des Simplex-Algorithmusfür Lineare Programmierung) überflüssig, wenn die Koeffizientenmatrixto-tal unimodular ist, d. h. jeder quadratische Untermatrix hat Determinante1, 0 oder−1. Wichiges Beispiel: Die Inzidenzmatrix eines gerichteten Gra-phen ist immer total unimodular. Die Inzidenzmatrix eines ungerichtetenGraphen ist genau dann total unimodular, wenn der Graph bipartit ist (sie-he z. B. [KV02]).

1.3 ZIMPL-Modelle

1.3.1 Ein Kantenauswahl-Modell für das AP

############################################################################ ZIMPL-Modell fuer das Assignment Problem# Joerg Rambau###########################################################################

#--------------------------------------------------------------------------# Abschnitt Parameter:#--------------------------------------------------------------------------

param n := 6; # Anzahl der Fahrzeugeparam m := 6; # Anzahl der Havaristen

set U := { 1 to n }; # Menge der Fahrzeugeset R := { 1 to m }; # Menge der Havaristen

param d[U * R] := | 1, 2, 3, 4, 5, 6|

1.4. Aufgaben 13

|1|15,23,37,13, 5,47||2|63,18,73,88, 8,11||3|20,21,40, 7,91,19||4|29,25,60,77,12,33||5|67,14, 3,26,98,51||6|31,27,28,12,53,44|;

#-------------------------------------------------------------------------# Abschnitt Variablen:#-------------------------------------------------------------------------

var x[U * R] binary;

#-------------------------------------------------------------------------# Abschnitt Ziel#-------------------------------------------------------------------------

minimize cost:sum <u, r> in U * R:

d[u, r] * x[u, r];

#-------------------------------------------------------------------------# Nebenbedingungen:#-------------------------------------------------------------------------

subto assignment_units:forall in U:

sum <u, r> in U * R:x[u, r] == 1;

subto assignment_requests:forall <r> in R:

sum <u, r> in U * R:x[u, r] == 1;

# eof

1.4 Aufgaben

Schreiben Sie einzimpl -Programm für das dasEUKLIDISCHE TRAVE-LING SALESMAN PROBLEM (TSP)und lösen Sie die BeispielinstanzTSP.datmit cplex . Zur Erinnerung: Das TSP ist das folgende Optimierungspro-blem:

TRAVELING SALESMAN PROBLEM (TSP)

Instanz: Ein vollständiger, ungerichteter GraphKn = (V,En) auf|V|=: n Knoten, Gewichtec : En → R+.

Aufgabe: Finde eine RundreiseT in G (d. h. einen Kreis inG, derjeden Knoten inV genau einmal enthält), so dassc(T) :=∑e∈T c(e) minimal ist.

Die Instanz imzimpl -Handbuch ist durch den euklidischen Abstandder Knotenkoordinaten gegeben und dahereuklidisch:

EUKLIDISCHES TSP

Instanz: Ein vollständiger, ungerichteter GraphKn = (V,En) auf|V| =: n Knoten, Koordinatenx,y : V → R, Gewichtec :

En→R+ mit c(v,w) :=√(

x(v)−x(w))2 +

(y(v)−y(w)

)2.

Aufgabe: Finde eine RundreiseT in G, so dassc(T) := ∑e∈E(T) c(e)minimal ist.

14 Einleitung

Einen weiteren Satz Beispieldaten fürEUKLIDISCHE TSPfinden Sie inder DateiTSP.dat auf der Materialien-Webseite.

Gehen Sie bei der Bearbeitung z. B. wie folgt vor:

1. Implementieren und lösen Sie das TSP-Modell aus demzimpl -Handbuch.

2. Ersetzen Sie die Beispieldaten durchTSP.dat (mit den notwendi-gen syntaktischen Modifikationen) und lösen Sie erneut.

3. Lösen Sie jeweils auch die LP-Relaxierung, indem sie die Spezifika-tion <var> binary; durch<var> real >= 0 <= 1; erset-zen (>= 0 können Sie auch weglassen).

4. Kopieren Sie als Kommentar an das Ende Ihrer Modelldatei die Va-riablenbelegung einer Optimallösung und die Rechenzeitstatistik.

5. Denken Sie über andere Modelle nach und probieren Sie aus.

6. Führen Sie Ihr Lieblings-Modell vor. Beurteilen Sie die Qualität desModells anhand der Optimalwerte desILPs und der LP-Relaxierungsowie anhand der Anzahl Variablen/Nebenbedingungen.

Teil I

Telekommunikation

Netzdimensionierung beiE-Plus (Dienstag) 2Das Material wurde hauptsächlich der Dissertation von Roland Wessäly[Wes00] entnommen.

2.1 Hintergrund: Aufbau und Planung eines GSM-Netzes

2.1.1 Logische Architektur

Die Netzschichten eines GSM-Netzes.

2.1.2 Ein logischer Kommunikationsweg

Ein Beispiel, wie die Kommunikation von Handy zu Handy durch diesesNetz verläuft.

2.1.3 Physikalische Architektur

Wie verläuft dieser Kommunikationsweg physikalisch?

2.2 Optimierungsprobleme

2.2.1 Hierarchie der Planungsaufgaben

Was muss alles geplant werden?

2.2.2 Transportnetzplanung

Wieviel Kapazität auf welchen Leitungen sollte man sich besorgen, so dassalle Kommunikationsbedarfe auf diesen Leitungen geroutet werden könnenund die Investitions- bzw. Anmietungskosten minimal sind?

2.3 Modelle

2.3.1 Standardmodelle

Modelle zur Kantenauswahl, wieM INIMUM SPANNING TREE PROBLEM

(MST), STEINER TREE PROBLEM (STP).

18 Netzdimensionierung bei E-Plus (Dienstag)

2.3.2 Standardmodelle mit Ausfallsicherheit

Modelle zur Kantenauswahl mit Ausfallsicherheit, wie geforderter Zweizu-sammenhang oder, allgemeiner, dasSURVIVABLE NETWORK PROBLEM

(SNP)

2.3.3 Beispiel: Ein ILP-Modell für das MINIMUM SPANNING TREE

PROBLEM (MST)

DiesesILP hat sehr viele Ungleichungen, ist aber in bestimmter Hinsichtbestmöglich (es liefert eine sogenannte vollständige Beschreibung).

Man würde es auf keinen Fall verwenden, sonder kombinatorische Al-gorithmen, wie den von Kruskal oder den von Prim (beides sogenannteGREEDY-Algorithmen, siehe2.4.1).

2.3.4 Das DiscNet-Modell (ohne Ausfallsicherheit)

Das komplette DiscNet-Modell alsILP, allerdings ohne die Nebenbedin-gungen zur Ausfallsicherheit; die können in diesem Modell aber leicht lo-gisch integriert werden. Die Berechnung wird natürlich schwerer.

2.4 Theorie

2.4.1 Das MINIMUM SPANNING TREE PROBLEM (MST) ist in P

Der GREEDY-Algorithmus von Kruskal.

2.4.2 Das MINIMUM STEINER TREE PROBLEM (STP) ist NP-schwer

Siehe z. B. [KV02].

2.4.3 ∗Matroide

Eine Verallgemeinerung desMST. Siehe z. B. [KV02].

2.5 ZIMPL-Modelle

2.5.1 Ein Kantenauswahl-Modell für das MST

############################################################################ ZIMPL-Modell fuer das Minimum Spanning Tree Problem# Joerg Rambau############################################################################--------------------------------------------------------------------------# Abschnitt Parameter:#--------------------------------------------------------------------------

param n := 16;

set V := { 1 to 16 };

set Pow[] := powerset(V);

2.6. Aufgaben 19

set Ind := indexset(Pow);

set E := { <v, w> in V * V with v < w };

param x_coord[V] := read "TSP.dat" as "<1n> 2n" skip 7 use 16;param y_coord[V] := read "TSP.dat" as "<1n> 3n" skip 7 use 16;

#--------------------------------------------------------------------------# Abschnitt Funktionen:#--------------------------------------------------------------------------

defnumb dist(v, w) := sqrt((x_coord[v] - x_coord[w])^2 + (y_coord[v] - y_coord[w])^2);

#--------------------------------------------------------------------------# Abschnitt Parameter:#--------------------------------------------------------------------------

param weight[<v, w> in E] := dist(v, w);

#-------------------------------------------------------------------------# Abschnitt Variablen:#-------------------------------------------------------------------------

var x[E] binary;

#-------------------------------------------------------------------------# Abschnitt Ziel#-------------------------------------------------------------------------

minimize cost:sum <v, w> in E:

weight[v, w] * x[v, w];

#-------------------------------------------------------------------------# Nebenbedingungen:#-------------------------------------------------------------------------

subto cardinality:sum <v, w> in E:

x[v, w] == n - 1;

subto subtour_elimination:forall in Ind:

sum <v, w> in E with <v> in Pow[I] and <w> in Pow[I]:x[v, w] <= card (Pow[I]) - 1;

# eof

2.6 Aufgaben

Schreiben Sie einzimpl -Modell für dasM INIMUM COST FLOW PRO-BLEM (MCFP) und lösen Sie die BeispielinstanzDiscNet_MCF.datmit cplex .

Zur Erinnerung: Eins-t-Fluss für zwei Knotens und t in einem ge-richteten GraphenD ist eine Funktionf , die jedem Bogen vonD einennicht-negativen Flusswertf (a) zuweist, so dass die Summe aller Flusswer-te an jedem Knoten außers und t stets Null ist. Der Wert des Flusses istf := ∑a∈δin(t) f (a)−∑a∈δout(t) f (a).

Das (ganzzahlige)MCFPist gegeben durch:

M INIMUM COST FLOW PROBLEM (MCFP)

Instanz: Ein gerichteter GraphD = (V,A) aufnKnoten undmBögen,Quelle und Senkes, t ∈V, Kapazitätenu : A→ Z+, Kostenc : A→ R+, ein Bedarff ∈ Z+

Aufgabe: Finde einens-t-Flussf : A→R+ mit Wert mindestensf undf (a)≤ u(a) für allea∈ A.

20 Netzdimensionierung bei E-Plus (Dienstag)

Untersuchen Sie dabei folgende Fragen:

1. Wie nah ist der erste Optimalwert der LP-Relaxierung amILP-Optimum?

2. Wie groß ist dasILP in Abhängigkeit vonn undm?

3. Finden Sie mit Ihrem Modell nur durch Modifikationen der Dateneinen bzgl.c kürzesten Weg vonsnacht.

4. Können Sie so auch einen längsten Weg vonsnacht finden?

UMTS (Mittwoch) 3Das Material wurde hauptsächlich dem Artikel [EGK+04] entnommen.

3.1 Hintergrund: UMTS-Technologie

3.1.1 Architektur der Funkschnittstelle eines UMTS-Netzes

Wie kommuniziert ein UMTS-Handy mit der UMTS-Antenne?

3.1.2 Wide Code Division Multiple Access (WCDMA)

Wie können sich UMTS-Handys das gesamte Frequenzband teilen?

3.1.3 Die CIR-Target-Bedingungen für erfolgreiche Übertragung

Welche Signalbedingung muss gelten, damit ein UMTS-Handy mit seinerAntenne noch kommunizieren kann?


3.2.1 Standortplanung

Wohin mit den Antennen, wenn man möglichst wenig Standorte oder mög-lichst wenig Interferenz haben möchte bei gegebener Abdeckung?

3.2.2 Antennenkonfiguration

Wie richtet man die Antennen aus?

3.3 Modelle

3.3.1 Standardmodelle der Standortplanung

DasFACILITY LOCATION PROBLEM (FLP) mit und ohne Kapazitäten.

3.3.2 Modelle zur Lastmessung

Auflösung der CIR-Targets zu einem Linearen Gleichungssystem mit einerVariable pro Zelle.

22 UMTS (Mittwoch)

3.3.3 ∗Modelle zur Antennenkonfiguration

Zur Tilt-Optimierung siehe die Dissertation von Thorsten Koch [Koc04].

3.4 Theorie

3.4.1 ∗Invertierbarkeit von Matrizen (I −C)

WennC Spektralradius kleiner als Eins hat, so ist(I −C) invertierbar. Inder Praxis muss der Spektralradius aber deutlich kleiner als Eins sein.

3.4.2 CAPACITATED FACILITY LOCATION PROBLEM (CFLP) ist NP-schwer

Siehe z. B. das Lehrbuch von Nemhauser und Wolsey [NW98].

3.5 ZIMPL-Modelle

3.5.1 Ein Standortplanungsmodell

############################################################################### ZIMPL file for the UMTS location problem# (location by a standard facility location model)# Joerg Rambau# 2005##############################################################################

############################################################################### functions section:##############################################################################

# distance between pixels v = <vx, vy> and w = <wx, wy>:defnumb dist(vx, vy, wx, wy) := sqrt((vx - wx)^2 + (vy - wy)^2);

############################################################################### parameters section:##############################################################################

# size of the area to cover in terms of pixels:param px_range := 100;param py_range := 100;

# maximal pixel distance with coverage:param coverage_dist := 30;

# grid size of potential sites:param grid_px_size := 10;param grid_py_size := 10;

# shift of potential sites:param grid_px_shift := 0;param grid_py_shift := 0;

# default costs:param default_opening_c := coverage_dist;

# pixels are given by their coordinates:set px_Coords := { 0 .. px_range - 1 };set py_Coords := { 0 .. py_range - 1 };

# all possible pixels:set P := px_Coords * py_Coords;

# we can have sites at all possible pixels:set S := {

<a, b> in P with(a mod grid_px_size == grid_px_shift)and(b mod grid_py_size == grid_py_shift)

};

3.6. Aufgaben 23

# all cover sites of a pixel:set S_P[<px, py> in P] := { <a, b> in S with dist(px, py, a, b) < coverage_dist };

# opening costs for each site:param opening_c[S] := default_opening_c;

# site connection cost are proportional to distance,# which may be justified by power issues:param connection_c[ <px, py, a, b> in P * S with <a, b> in S_P[px, py] ] := (dist(px, py, a, b) / coverage_dist)^3;

############################################################################### variables section:##############################################################################

# one indicator variable for each site:var x[S] binary;

# one indicator variable for each connection:var z[P * S] binary;

############################################################################### objective section:##############################################################################

# minimze the number of opening costs plus connection costs:minimize cost:

sum <a, b> in S: opening_c[a, b] * x[a, b]+sum <px, py, a, b> in P * S with <a, b> in S_P[px, py]:

connection_c[px, py, a, b] * z[px, py, a, b];

############################################################################### constraints section:##############################################################################

# cover each pixel at least once:subto cover_condition:

forall <px, py> in P:sum <a, b> in S_P[px, py] :

z[px, py, a, b] >= 1;

# if a pixel is connected to a site, this site must be opened:subto opening_condition:

forall <a, b> in S:forall <px, py> in P with <a, b> in S_P[px, py]:

x[a, b] - z[px, py, a, b] >= 0;

############################################################################### end of file.

3.6 Aufgaben

Ergänzen Sie die unfertigezimpl -DateiUMTS_MILP.zpl zu einemzimpl -Modell für dasUMTS MINIMUM INTERFERENCELOCATION PROBLEM

(UMTS-MILP).

Dabei handelt es sich um das folgende Problem:

UMTS MINIMUM INTERFERENCELOCATION PROBLEM (UMTS-MILP)

Instanz: Eine MengeP von Pixeln mit Koordinatenx,y : P→ Z, ei-ne TeilmengeS⊆ P von möglichen Standorten, eine Ab-deckungsrelation, die jedem Pixelp ∈ P alle StandorteS(p)⊆Szuordnet, diepabdecken können, Interferenzschät-zungenc : S×S→ R+.

Aufgabe: Finde TeilmengeR⊆ S, so dassS(p)∩R 6= /0 für alle p∈ Pund so dass die geschätzte Gesamtinterferenz∑s,s′∈Rc(s,s′)minimal ist.

24 UMTS (Mittwoch)


1. Skizzieren Sie die Karte mit den möglichen Standorten.

2. Wie gut war die erste LP-Relaxierung?

3. Skizzieren Sie die Karte mit den Standorten einer optimalen Lösung.

Frequenzzuweisung beiE-Plus (Donnerstag) 4Das Material wurde hauptsächlich der Dissertation von Andreas Eisenblät-ter [Eis01] entnommen.

4.1 Hintergrund: Die GSM-Funkschnittstelle

4.1.1 Architektur des GSM-Funknetzes

Wie kommuniziert ein GSM-Handy mit einer GSM-Antenne?

4.1.2 Das Beispielnetz TINY

Ein Beispielnetz mit drei Standorten und insgesamt zwölf Transceivern unddie zugehörigen Daten zur Separation, Gleichkanal- und Nachbarkanalin-terferenz.


4.2.1 Frequenzzuweisung mit möglichst wenig Frequenzen

Weise den Transceivern Frequenzen so zu, dass keine Interferenz entstehtund so dass die Anzahl/die Spannweite benötigter Frequenzen möglichstklein ist.

4.2.2 Frequenzzuweisung mit möglichst wenig Interferenz

Weise den Transceivern Frequenzen aus einem gegebenen Spektrum so zu,dass möglichst wenig Gleichkanal- und Nachbarkanalinterferenz induziertwird.

4.3 Modelle

4.3.1 Standardmodelle aus der Graphenfärbung

Einige Graphenfärbungsprobleme als Modelle für Frequenzzuweisung, meistdurch Schwellwerte für akzeptable Interferenz gegeben.

26 Frequenzzuweisung bei E-Plus (Donnerstag)

4.3.2 Ein Modell für das GRAPH COLORING DECISION PROBLEM

(GCP-D)

Kann man einen Graphen mitk Farben färben? Das naheliegendeILP lie-fert in der LP-Relaxierung fürk≥ 2 immer „ja“!

4.3.3 Ein Modell für das FREQUENCY ASSIGNMENT PROBLEM

(FAP)

Ein ILP, das wirklich die Gesamtinterferenz minimiert.

4.3.4 ∗Ein Frequenzzuweisungsmodell für Separation Eins oh-ne Nachbarkanal-Interferenz

Falls nur Separation Eins oder Null und keine Nachbarkanalinterferenz vor-handen sind, ist ein sogenanntesk-PARTITION-Modell stärker als dasFAP-Modell im vorigen Abschnitt.

4.4 Theorie

4.4.1 Gültige Ungleichungen

Extra-Ungleichungen können die Ganzzahligkeitslücke reduzieren.

4.4.2 Cliquen-Ungleichungen für Graphenfärbung

Gültige Ungleichungen für dasGCP-D entstehen z. B. dadurch, dass in je-derk-Clique des Graphenk Farben gebraucht werden.

4.4.3 Perfekte Graphen

Über Graphen, deren maximale Cliquen schon die Färbungszahl bestim-men. Siehe das Buch von Grötschel, Lovász und Schrijver [GL93].

4.4.4 Kurzvorstellung: Branch & Bound, Branch & Cut, Cut &Branch

Wie manILPs in Teilprobleme zerlegt und dabei obere und untere Schran-ken benutzt, um sich Arbeit zu erparen. Siehe das Buch von Nemhauserund Wolsey [NW98].

4.4.5 Facettendefinierende Ungleichungen

Gültige ungleichungen, die erfahrungsgemäß am effektivsten sind. Siehedas Buch von Nemhauser und Wolsey [NW98].

4.5. ZIMPL-Modelle 27

4.5 ZIMPL-Modelle

4.5.1 Stabile-Mengen-Modelle für FAP

############################################################################### ZIMPL file for the FAP model based on stable sets for instance TINY# Joerg Rambau# (from Eisenblaetter’s PhD. Thesis)# 2005##############################################################################


param n := 11; # number of available frequencies (originally: 13)

param min_f := 711;param max_f := min_f + n - 1;

set C := { min_f to max_f };

# do print C;

set V := { "A10", "A20", "A21", "A22", "A30", "A31", # site A"B10", "B11", "B20", # site B"C10", "C20", "C21" # site C

}; # node set

# the following are the locally blocked channels:set B[V] := <"A10"> {},

<"A20"> {},<"A21"> {},<"A22"> {},<"A30"> {},<"A31"> {},<"B10"> {},<"B11"> {},<"B20"> { 711, 712 },<"C10"> { 719 },<"C20"> {},<"C21"> {}; # blocked channels

# forall <trx> in V do print B[trx];

# do print V;

set E := { <v, w> in V * V with v < w }; # edge set

# do print E;

# we read the data from data files# *_TINY.dat (original: solution with sero interference possible)# *_DENSE.dat (dense interference matrix, no zero interference possible),# *_RELAXED.dat (separation at most one, only co-channel interference, for comparison with k-partitioning), resp.:param separation [E] := read "FAP_StableSets_DENSE.dat" as "<1s, 2s> 3n" comment "#" default 0;

param co_interference [E] := read "FAP_StableSets_DENSE.dat" as "<1s, 2s> 4n" comment "#" default 0;

param ad_interference [E] := read "FAP_StableSets_DENSE.dat" as "<1s, 2s> 5n" comment "#" default 0;

set E_sep := { <v, w> in E with separation[v, w] > 0 };

set E_co := { <v, w> in E with co_interference[v, w] > 0 };

set E_ad := { <v, w> in E with ad_interference[v, w] > 0 };



var y[V * C] binary;

var z_co[E] binary;var z_ad[E] binary;


minimize interference:sum <v, w> in E_co: co_interference[v, w] * z_co[v, w] # co-channel


+sum <v, w> in E_ad: ad_interference[v, w] * z_ad[v, w]; # adjacent-channel


subto unique_frequency:forall <v> in V:

sum <f> in C without B[v]:y[v, f] == 1;

subto separation:forall <v, w> in E_sep:

forall <f, g> in (C without B[v]) * (C without B[w])with abs(f - g) < separation[v, w]:

y[v, f] + y[w, g] <= 1;

subto co_interference:forall <v, w> in E_co:

forall <f> in C without (B[v] union B[w]):y[v, f] + y[w, f] - z_co[v, w] <= 1;

subto ad_interference:forall <v, w> in E_ad:

forall <f> in C without B[v] with <f - 1> in C without B[w]:y[v, f] + y[w, f - 1] - z_ad[v, w] <= 1;

# end of file.

4.5.2 Stabile-Mengen-Modelle für FAP mit Cliquen-Ungleichungen

Wie oben, nur mit Cliquenungleichungen.

4.5.3 Berechnung mit und ohne automatische Cuts

Benutzung dercplex -Einstellungen zur automatischen Generierung vongültigen Ungleichungen.

4.5.4 ∗Ein ILP für 6-PARTITION

############################################################################### ZIMPL file for the FAP relaxation based on k-partition for instance TINY# assumptions: separation requirements are at most 1# no adjacent channel interference# no blocked channels# Joerg Rambau# (from Eisenblaetter’s PhD. Thesis pp. 123ff.)# 2005##############################################################################


param n := 6; # number of available frequencies

# this time we are given only six frequencies# (otherwise, interference zero is possible trivially# since there are 13 frequencies and only 12 transceivers):param min_f := 711;param max_f := min_f + n - 1;

# the spectrum:set C := { min_f to max_f };

do print C;

# the transceivers:set V := { "A10", "A20", "A21", "A22", "A30", "A31", # site A

"B10", "B11", "B20", # site B"C10", "C20", "C21" # site C

}; # node set

set E := { <v, w> in V * V with v < w }; # edge set

# the 7 elm subsets of V:set K_n_plus_1[] := subsets(V, n + 1);set I_n_plus_1 := indexset(K_n_plus_1);

4.6. Aufgaben 29

param separation [E] := read "FAP_StableSets_RELAXED.dat" as "<1s, 2s> 3n" comment "#" default 0;

param co_interference [E] := read "FAP_StableSets_RELAXED.dat" as "<1s, 2s> 4n" comment "#" default 0;

set E_sep := { <v, w> in E with separation[v, w] > 0 };

set E_co := { <v, w> in E with co_interference[v, w] > 0 };

# a big-M making violations of separation requirements more important than any interference:param M := sum <v, w> in E_co: co_interference[v, w] + 1;

# the following set is the set of edges that have to be considered in k-partitioning:set E_p := E_sep union E_co;

param edge_weight [ <v, w> in E_p ] := if separation[v, w] > 0 then Melse co_interference[v, w]end;



# just one variable specifying which adjacent nodes are in the same color classvar z[E_p] binary;


minimize interference:sum <v, w> in E_p: edge_weight[v, w] * z[v, w];


subto transitivity:forall <u, v, w> in V * V * V with u < v and v < w:

z[u, v] + z[v, w] - z[u, w] <= 1;

# in every 7-clique, there must be at least one monochromatic edge:subto seven_clique_condition:

forall in I_n_plus_1 with ((K_n_plus_1[I] * K_n_plus_1[I]) inter E) without E_p == {} :sum <v, w> in K_n_plus_1[I] * K_n_plus_1[I] with v < w:

z[v, w] >= 1;

# end of file.

4.6 Aufgaben

Entwickeln Sie einzimpl -Modell für dasGRAPH COLORING PROBLEM

(GCP)und lösen Sie die Testinstanz inFAP_GCP.dat .

Zur Erinnerung:

GRAPH COLORING PROBLEM (GCP)

Instanz: Ein ungerichteter GraphG = (V,E).Aufgabe: Finde eine zulässigek-Färbung vonG (d. h. eine Abblidung

c : V → {1,2, . . . ,k} mit c(v) 6= c(w) für alle v,w ∈ E) mitminimalemk∈ N.

Das FREQUENCY ASSIGNMENT PROBLEM (FAP) wird gelegentlichalsGCP„modelliert“: für einen festen Schwellwert für die geduldete Inter-ferenz sucht man einek-Färbung für denjenigen Graphen, der nur diejeni-gen möglichen Kanten enthält, deren Gleichkanal-Interferenz größer als der


Schwellwert ist (k ist die Anzahl der Frequenzen). Der Schwellwert wirddann so lange verkleinert, bis der Graph so gerade nochk-färbbar ist. DieFrequenzen werden schließlich entsprechend derk-Färbung zum kleinst-möglichen Schwellwert zugewiesen.

Untersuchen Sie folgende Fragen:

1. Wie gut war die erste LP-Relaxierung?

2. Wieviele unterschiedliche Variablenbelegungen in Ihrem Modell er-reichen das Optimum?

3. Ist Symmetrie im Modell vorteilhaft oder nicht für die Lösungsme-thode Branch-and-Bound?

4. Minimiert das oben beschriebene Frequenzzuweisungs-Verfahren überGraphenfärbung stets die Gesamt-Gleichkanal-Interferenz?

Konfiguration optischerNetze bei T-SystemsNova (Freitag)

5Das Material wurde hauptsächlich dem Artikel [KZ04] entnommen.

5.1 Hintergrund: Optische Netze

5.1.1 Optische Netze erster Generation

Hier sind nur die Links zwischen Knoten aus Glasfaser. An jedem Knotenmuss opto-elektronisch konvertiert werden.

5.1.2 Optische Netze zweiter Generation

Hier sind auch Routing-Geräte in den Knoten voll-optisch. SogenannteLichtwege können an jedem Knoten ohne Konversion auf den richtigenFolgelink weitergeleitet werden.

5.1.3 Hardware-Komponenten

Hauptsächlich sind

• Glasfaser

• WDM-Multiplexer/Demultiplexer

• Opto-elektronische Konverter

• Optische Cross Connects (OXCs)

• Wellenlängenkonverter (noch nicht marktreif, teuer)

wichtig.


5.2.1 Transportnetzplanung mit Routing und Wellenlängenzu-ordnung

Ein umfassendes Modell zur Konfiguration. Siehe den Artikel [ZKW02].

32 Konfiguration optischer Netze bei T-Systems Nova (Freitag)

5.2.2 Wellenlängenzuordnung mit möglichst wenig Konversi-on

Ein Modell, um bei gegebenen Routings und Linkkapazitäten eine Wellen-längenzuordnung zu finden, die die Anzahl notwendiger Wellenlängenkon-verter minimiert. Siehe den Artikel [KZ04].

5.3 Modelle

5.3.1 Standardmodelle für Bedarf Eins pro Verbindung

Dies führt auf dasEDGE-DISJOINT PATH PROBLEM (EDP). Siehe dasLehrbuch von Korte und Vygen [KV02].

5.3.2 Standardmodelle für sequentielles Routen und Färben

Man routet die Anfragen eine nach der anderen entlang kürzester Wege.Siehe die Diplomarbeit von Andreas Tuchscherer [Tuc03].

5.3.3 Mehrgüterfluss-Modelle

Jeder Kommunikationsbedarf wird als ein Gut angesehen, dass durch dasTransportnetz vom Sender zum Empfänger fließen soll. ZumMULTI -COMMODITY

FLOW PROBLEM siehe wieder das Lehrbuch von Korte und Vygen [KV02].

5.3.4 Ein Assignment-Modell für das MCWAP

In diesemILP wird jedem benutzten Link eines Bedarfes eine Wellenlän-ge zugeordnet. Ein kompaktes Modell, allerdings ist die LP-Relaxierungschwach.

5.3.5 Ein Packing-Modell für das MCWAP

In diesemILP werden Teilwege einer Wellenlänge in das Transportnetzgepackt. Das ergibt viele Variablen aber eine starke LP-Relaxierung.

5.4 Theorie

Alle Aspekte z. B. im Lehrbuch von Korte und Vygen [KV02].

5.4.1 Das SHORTEST PATH PROBLEM (SPP) ist in P

Dies ist wichtig für „gieriges“ sequentielles Routing mit Wellenlängenzu-ordnung.


5.4.2 ∗Das RESOURCE CONSTRAINED SHORTEST PATH PROBLEM

(RCSPP) ist NP-schwer

Falls z. B. Längenbeschränkungen auf den Lichtwegen gefordert sind, soist schon „gieriges“ sequentielles Routing mit Wellenlängenzuordnung keinpolynomialer Algorithmus mehr.

5.4.3 ∗Das EDGE DISJOINT PATH PROBLEM (EDP) ist NP-schwer

Auch bei Bedarf Eins pro Verbindung ohne Konversion ist Routing undWellenlängenzuordnung schon schwer.

5.4.4 ∗Das MINIMUM COST MULTI-COMMODITY FLOW PROBLEM

(MCMCF) ist NP-schwer

Dies ist noch allgemeiner und daher nicht leichter.

5.5 ZIMPL-Modelle

5.5.1 Ein Bogenauswahl-Modell für das SPP

############################################################################### ZIMPL file for the shortest path problem# Joerg Rambau# 2005##############################################################################


param n := 16; # number of nodes

param s := 1; # origin node of wanted pathparam t := 9; # destination node of wanted path

param max_dist := 5; # maximal length of an arc

set V := { 1 to n }; # the node set

set A_c := { <v, w> in V * V with v != w } ; # the complete arc set

param x_coord [V] := read "TSP.dat" as "<1n> 2n" skip 7 use 16;param y_coord [V] := read "TSP.dat" as "<1n> 3n" skip 7 use 16;

# the following number is the distance between two nodes:defnumb dist (v, w) := sqrt((x_coord[v] - x_coord[w])^2 + (y_coord[v] - y_coord[w])^2);

# include all arcs that are not too long:set A := { <v, w> in A_c with dist(v, w) <= max_dist };

param cost [<v, w> in A] := dist (v, w);


# one variable for each arc:var x[A] binary;


minimize cost:


sum <v, w> in A:cost[v, w] * x[v, w];


subto flow_at_source:sum <s, v> in A:

x[s, v] == 1;

subto flow_at_sink:sum <v, t> in A:

x[v, t] == 1;

subto flow_conservation:forall <v> in V without {s, t}:

sum <v, w> in A:x[v, w]

-sum <w, v> in A:

x[w, v]== 0;

############################################################################### end of file.

5.5.2 Ein Bogenauswahl-Modell für das LONGEST PATH PLUS

CYCLES PROBLEM (LPPCP)

############################################################################### ZIMPL file for the longest path plus cycle problem# Joerg Rambau# 2005##############################################################################










param cost [<v, w> in A] := -dist (v, w);




minimize cost:sum <v, w> in A:

cost[v, w] * x[v, w];



x[s, v]-


sum <v, s> in A:x[v, s]

== 1;


x[v, t]-sum <t, v> in A:

x[t, v]== 1;

subto out_capacity:forall <v> in V without {t}:

sum <v, w> in A:x[v, w] <= 1;

subto in_capacity:forall <w> in V without {s}:

sum <v, w> in A:x[v, w] <= 1;



-sum <w, v> in A:

x[w, v]== 0;

############################################################################### end of file.

5.5.3 Ein Bogenauswahl-Modell für das LONGEST PATH PRO-BLEM (LPP)

############################################################################### ZIMPL file for the longest path problem with a flow plus subtour elimination# Joerg Rambau# 2005##############################################################################






# the following sets are used for subtour elimination constraints:set P[] := powerset(V without {s, t});set IP := indexset(P);





param cost [<v, w> in A] := -dist (v, w);




minimize cost:


sum <v, w> in A:cost[v, w] * x[v, w];



x[s, v]-sum <v, s> in A:

x[v, s]== 1;


x[v, t]-sum <t, v> in A:

x[t, v]== 1;

subto out_capacity:forall <v> in V without {t}:

sum <v, w> in A:x[v, w] <= 1;

subto in_capacity:forall <w> in V without {s}:

sum <v, w> in A:x[v, w] <= 1;



-sum <w, v> in A:

x[w, v]== 0;

subto subtour_elimination:forall in IP with card(P[I]) > 1 and card(P[I]) <= n:

sum <v, w> in A with <v> in P[I] and <w> in P[I]:x[v, w] <= card (P[I]) - 1;

############################################################################### end of file.

Teil II

Logistik

Regalbediengerätsteuerungbei der Siemens NixdorfInformationssystemeGmbH (Montag)

6Das Material wurde hauptsächlich der Dissertation von Norbert Ascheuer[Asc95] entnommen.

6.1 Hintergrund: Hochregallagertechnik

6.1.1 Matrialfluss im betrachteten Hochregallager

Ein- und Auslagern, Umlagern, aber auch direktes Auslagern in eine Pro-duktionsstraße.

6.1.2 Führerlose Regalbediengeräte (RBGs)

Zweidimensionale Bewegung auf zwei orthogonalen Schienen möglich. Eskann jeweils nur eine Palette geladen werden.


6.2.1 Der Online-/Echtzeit-Aspekt

Die Aufträge sind nicht im Vorhinein bekannt: insbesondere die Nachfragein der Produktionsstraße wird im Tagesverlauf generiert. Daher: Steuerungohne Wissen über zukünftige Ereignisse (Online-Aspekt) notwendig, wo-bei Berechnungszeiten den Ablauf verzögern (Echtzeit-Aspekt), Optimie-rungsverfahren also sehr schnell (eine Sekunde) antworten müssen.

6.2.2 Grundlegende Online-Algorithmen

Einige wichtige grundlegende Online-Algorithmen:

• FIFO: Wer zuerst kommt, mahlt zuerst

• PRIORITY: Aufträge mit höherer Priorität zuerst, sonstFIFO

• NEAREST-NEIGHBOR: immer den nahesten Auftrag zuerst.

40 Regalbediengerätsteuerung bei der Siemens Nixdorf Informationssysteme GmbH (Montag)

• REOPT: Immer nach einem Plan arbeiten, der bei jedem relevanteEreignis durch Lösung eines (Offline-)Reoptimierungsproblems ak-tualisiert wird.

6.2.3 Reoptimierung: Finde beste Reihenfolge für bekannte Auf-träge

Zwei Fälle:

1. Nur Ein- und Auslagern:AP.

2. Auch Umlagern und Bedienung der Produktionsstraße:ATSP

6.2.4 Reihenfolgeplanung für ein RBG mit möglichst wenigenLeerbewegungen

Produktivität eines Transportgerätes wird oft als das Verhältnis von belade-nen Bewegungen zu allen Bewegungen angesehen. Daher ist das Ziel häu-fig die Minimierung der Gesamt-Leerbewegungen, um die Produktivität zuerhöhen.

6.2.5 Reihenfolgeplanung für ein RBG mit Präzedenzen

Aufträge können unterschiedliche Prioritäten haben. Aufträge gleicher Prio-rität sollen aber mit minimalen Leerbewegungen abgearbeitet werden.

6.2.6 Reihenfolgeplanung für ein RBG mit Zeitfenstern

Zu hohen Wartezeiten für einzelne Aufträge sind unerwünscht. Zusätzlichkönnen Aufträge erst abgearbeitet werden, wenn sie bekannt sind. Das lässtsich mit harten Zeitfenstern für alle Aufträge modellieren.

6.3 Modelle

6.3.1 Das ASYMMETRIC TRAVELING SALESMAN PROBLEM (ATSP)

Ein Knoten für jeden Auftrag; Bögen, die den Verbindungsfahrten ent-sprechen. Eine kürzeste Rundreise durch alle Knoten entspricht dann einerAbarbeitungsreihenfolge mit minimaler Gesamtleerfahrtstrecke. DieILP-Formulierung entspricht der desTSP.

6.3.2 Das ATSP MIT PRÄZEDENZEN (ATSPPC)

Präzedenzen können durch zusätzlichen Ungleichungen modelliert werden(exponentiell viele).

6.4. Theorie 41

6.3.3 Das ATSP MIT ZEITFENSTERN (ATSPTW)

Zeitfenster können durch eine Formulierung mit Zeitvariablen (schwach)oder durch Ungleichungen für unzulässige Pfade (stärker) modelliert wer-den.

6.4 Theorie

6.4.1 Die Christofides-Heuristik für das TSP mit Dreiecksun-gleichung

Gilt die Dreiecksungleichung, so kann man durch eineMST-Berechnungund eineM INIMUM WEIGHT PERFECTMATCHING-Berechnung in Poly-nomialzeit eine Lösung konstruieren, die höchstens3/2 mal so viel kostetwie eine optimale.

6.4.2 Kompetitive Analyse von Online-Algorithmen

Man vergleicht die Kosten eines Online-Algorithmus mit den Kosten einerim Nachhinein berechneten optimalen Offline-Lösung im schlimmsten Fall.Kompetitive Analyse ist die Antwort auf die Frage „Um welchen Faktor istein Hellseher im schlimmsten Fall besser als der Online-Algorithmus?“

6.4.3 Es gibt keinen kompetitiven Online-Algorithmus für dieMinimierung der Leerbewegungen

Man trifft auf die Triviality Barrier: alle Online-Algorithmen sind gleichschlecht vom Standpunkt der kompetitiven Analyse.

6.4.4 Reoptimierung des Makespan ist 5/2-kompetitiv für dieOnline-Minimierung des Makespan

Für die im Offline-Fall äquivalente Zielfunktion Makespan gibt es sogareinen2-kompetitiven Algorithmus. Der Online-AlgorithmusREPLAN (REOPT

bzgl. Makespan) ist immerhin5/2-kompetitiv.

6.5 ZIMPL-Modelle

6.5.1 Ein Bogenauswahl-Modell für das ATSP

############################################################################### ZIMPL file for the directed ATSP model of the stacker crane problem# (from Ascheuer’s PhD. Thesis)# Joerg Rambau# 2005##############################################################################


42 Regalbediengerätsteuerung bei der Siemens Nixdorf Informationssysteme GmbH (Montag)


set V := { 1 to n }; # the node set (1 is the server position)set P [] := powerset(V);set IP := indexset(P);

set A := { <v, w> in V * V with v != w } ; # the complete edge set

param orig_x [V] := read "RBG.dat" as "<1n> 2n" skip 15 use n;param orig_y [V] := read "RBG.dat" as "<1n> 3n" skip 15 use n;param dest_x [V] := read "RBG.dat" as "<1n> 4n" skip 15 use n;param dest_y [V] := read "RBG.dat" as "<1n> 5n" skip 15 use n;

# the following number is the distance between two nodes:defnumb dist (v, w) := sqrt((dest_x[v] - orig_x[w])^2 + (dest_y[v] - orig_y[w])^2);








subto outdegree:forall <v> in V:

sum <v, w> in A:x[v, w] == 1;

subto indegree:forall <v> in V:

sum <w, v> in A:x[w, v] == 1;

subto subtour_elimination:forall in IP with card(P[I]) >= 2 and card(P[I]) <= n / 2:


############################################################################### end of file.

6.6 Aufgaben

Schreiben Sie einzimpl -Modell für dasASYMETRIC TRAVELING SA-LESMAN PROBLEM WITH TIME WINDOWS (ATSPTW)und lösen Sie dieBeispielinstanzRBG.dat mit cplex , die durch die Ein-, Um- und Aus-lageraufträge für ein Regalbediengerät gegeben ist. Fangen Sie dabei mitfünf Aufträgen an; wenn Sie die kleine Instanz in einer Minute lösen kön-nen, nehmen Sie einen Auftrag hinzu.

Zur Erinnerung: DasATSPTWist gegeben durch:

6.6. Aufgaben 43

ATSP WITH TIME WINDOWS (ATSPTW)

Instanz: Ein vollständiger gerichteter GraphD = (V,A) aufn Knoten,ein Depoto∈V, Kostenc : A→ R+, Zeitfenster[rv,dv] fürallev∈V.

Aufgabe: Finde eine RundreiseT ⊆ D mit Start und Ende ino, diealle Knoten ausV genau einmal besucht, so dass jedesv∈Vfrühestens zur Zeitrv und spätestens zur Zeitdv besucht wirdund so dassc(T) := ∑a∈A(T) c(a) minimal ist.


1. Wie nah ist der Optimalwert der LP-Relaxierung am ILP-Optimum?

2. Benötigen Sie Teiltour-Eliminations-Bedingungen?

3. Wie wirkt sich die Hinzunahme von Teiltour-Eliminations-Bedingungenauf den Wert der LP-Relaxierung aus?

Lastenfahrstuhlsteuerungbei der Herlitz PBS AG(Dienstag)

7Das Material wurde hauptsächlich den Artikeln [GKR01, HKRW01, HKR00]entnommen.

7.1 Hintergrund: Paletten-Fördertechnik

7.1.1 Das Versandlager Falkensee

Warenfluss zwischen Wareneingang, Warenausgang, Kommisionierung, Pro-duktion und Lager.

7.1.2 Die Vertikalfördertürme

Vertikalfördersysteme verbinden die acht Ebenen des Versandzentrums. Injedem der beiden Türme (zu beiden Seiten des Lagers je einer) fahren fünfVertikalförderer (Aufzüge), die jeweils eine Palette transportieren können.


7.2.1 Der Online-/Echtzeitaspekt

Wieder werden Aufträge erst bekannt, wenn Sie in das Subsystem der Ver-tikalfördertürme eintreten, also Online-Optimierung in Echtzeit ist erfor-derlich.

7.2.2 Where is the Elevator? (Vortrag mit Simulationen)

Dieser Vortrag [Ram04a] beschreibt mit Simulationen verschiedene Aspek-te des Problems.

7.2.3 VFS-Reihenfolgeplanung mit wenig Leerfahrten

Dies wäre der gleiche Ansatz wie im RBG-Problem in Kapitel6.

46 Lastenfahrstuhlsteuerung bei der Herlitz PBS AG (Dienstag)

7.2.4 VFS-Reihenfolgeplanung mit wenig Wartezeit

Dies ist ein Ansatz, der die Produktivität der Transportgüter (Paletten) imAuge hat (QoS=Quality of Service).

7.2.5 VFS-Reihenfolgeplanung mit beschränkter Wartezeit

Da beim vorigen Ansatz einzelne Paletten evt. unendlich lange warten, zieltman hier auf eine Beschränkung der individuellen Wartezeiten.

7.3 Modelle

7.3.1 Das ONLINE-DIAL -A-RIDE PROBLEM (ONLINEDARP)

Ein allgemeineres Online-Optimierungsproblem aus dem Ruf-Taxi-Bereich.

7.3.2 Ein ATSP-Modell

Mit diesem Modell kann man wieder die Leerfahrten (offline) minimieren.Der Preis ist, dass man sich ein NP-schweres Modell einhandelt.

7.3.3 Das MIXED CHINESE POSTMAN PROBLEM (MIXEDCPP)

Dies ist das zugehörige Standardmodell aus der Literatur, das i. A. auchNP-schwer ist.

7.3.4 Das MIXEDCPP auf der Linie

Der Fahrstuhl bewegt sich nur in einer Dimension, daher kann man dieseEinschränkung machen, sofern man Start- und Stop sowie Be- und Entla-dezeiten vernachlässigt.

7.4 Theorie

7.4.1 Auf der Linie ist MIXEDCPP in P

Hier gibt es einen polynomialen Algorithmus [FG93], der in [HKRW01]sogar fürFIFO-Präzedenzen unter den Aufträgen gleicher Ursprungsetageverallgemeinert wurde.

7.4.2 Kein kompetitiver Online-Algorithmus für die Minimie-rung der Wartezeit

Die Triviality Barrier ist wieder da.


7.4.3 IGNORE: beschränkte Flusszeiten unter vertretbarer Be-lastung

Ein neuer Online-Algorithmus, der seinen Plan immer erst aktualisiert, wenner mit dem alten Plan fertig ist, hat unter∆-vertretbarer Belastungeine ma-ximale Flusszeit, die durch2∆ beschränkt ist.

7.5 ZIMPL-Modelle

7.5.1 Ein ATSP-Modell für das Fahrstuhlproblem

############################################################################### ZIMPL file for the directed flow model of the Dial-a-Ride Problem# Joerg Rambau# 2005##############################################################################



set V := { 1 to n }; # the request node setset P [] := powerset(V);set IP := indexset(P);

set A := { V * V } ; # the complete edge set

param orig [V] := read "VFS.dat" as "<1n> 2n" comment "#";param dest [V] := read "VFS.dat" as "<1n> 3n" comment "#";

# the following number is the distance between two nodes:defnumb dist (v, w) := abs(dest[v] - orig[w]);








subto flow_conservation:forall <v> in V:


-sum <w, v> in A:

x[w, v]== 0;

subto set_partitioning:forall <v> in V:

sum <v, w> in A:x[v, w] == 1;

subto subtour_elimination:forall in IP with card(P[I]) > 2 and card(P[I]) < n - 2:


############################################################################### end of file.

48 Lastenfahrstuhlsteuerung bei der Herlitz PBS AG (Dienstag)

7.6 Aufgaben

Schreiben Sie einzimpl -Modell für dasASYMETRIC TRAVELING SA-LESMAN PROBLEM WITH PRECEDENCECONSTRAINTS (ATSPPC)undlösen Sie die BeispielinstanzVFS.dat mit cplex , die durch die Trans-portaufträge für einen Fahrstuhl gegeben ist. Die Aufträge seien in der Rei-henfolge ihrer Release-Zeiten angekommen, und auf einem Flur könnensich die Aufträge nicht überholen (das liefert die Präzedenzbedingungen).Fangen Sie dabei mit fünf Aufträgen an; wenn Sie die kleine Instanz ineiner Minute lösen können, nehmen Sie einen Auftrag hinzu etc.

Zur Erinnerung: DasATSPPCist gegeben durch:

ATSP WITH PRECEDENCECONSTRAINTS (ATSPPC)

Instanz: Ein vollständiger gerichteter GraphD = (V,A) aufn Knoten,ein Depoto∈V, Kostenc : A→ R+, PräzedenzenP⊆ A

Aufgabe: Finde eine RundreiseT ⊆ D mit Start und Ende ino, diealle Knoten ausV genau einmal besucht, so dass für alle(v,w) ∈ P Knotenv vor Knotenw besucht wird und so dassc(T) := ∑a∈A(T) c(a) minimal ist.

Untersuchen Sie dabei (mal wieder) folgende Fragen:

1. Wie nah ist der Optimalwert der LP-Relaxierung am ILP-Optimum?

2. Benötigen Sie Teiltour-Eliminations-Bedingungen?

3. Wie wirkt sich die Hinzunahme von Teiltour-Eliminations-Bedingungenauf den Wert der LP-Relaxierung aus?

OptimierteLaserquellenauslastung(Mittwoch)

8Hierzu gibt es noch keine Veröffentlichungen, da das Projekt brandneu ist.Es gibt noch Geheimhaltungsvereinbarungen, so dass hier nicht alles be-sprochen werden kann.

8.1 Hintergrund: Laserschweißen im Karosseriebau

8.1.1 Eine Laserschweißstation

In einer großen Box werden Karosserieteile verschweißt.

8.1.2 Energieversorgung der Schweißroboter

Laserquellen speisen vollautomatische Industrieroboter mit Schweißarm.Interessant ist, dass im Prinzip eine Laserquelle zwischen mehreren Robo-tern umgeschaltet werden kann.


8.2.1 Robotersteuerung mit minimalen Leerverfahrzeiten

Traditionell werden Roboter so gesteuert, dass die Summe der Verfahrzei-ten zwischen den Aufträgen minimal ist.

8.2.2 Robotersteuerung mit minimaler Fertigstellungszeit

Hat man mehrere Roboter, ist es manchmal wünschenswert, die gesam-te Prozesszeit zu verkürzen, d. h. die Zeit, bis der letzte Roboter mit demWerkstück fertig ist.

8.2.3 Robotersteuerung mit minimaler Anzahl von Laserquel-len

Ein vollkommen neues Optimierungsproblem ist die Minimierung der be-nötigten Laserquellen bei unveränderter Prozesszeit.

50 Optimierte Laserquellenauslastung (Mittwoch)

8.3 Modelle

8.3.1 Ein ATSP-Modell zur Industrierobotereinsatzplanung

Hier wird mit einer Variable pro Schweißjob festgelegt, ob der Auftrag vor-wärts oder rückwärts geschweißt werden soll.

8.3.2 Ein Matching-Modell zur Industrierobotereinsatzplanung

Hier wird das Problem umgangen durch eine Modellierung alsCPP. DasModell ist dann ein Matching-Modell mit Zusammenhangsbedingungen.

8.3.3 Ein Modell zur Minimierung der Laserquellen bei gege-benem Einsatzplan

Hier werden die Einsatzpläne für alle Roboter vorgegeben, nur die Startzei-ten sind variabel. Durch geschicktes Starten (Scheduling) soll eine Laser-quelle gespart werden.

8.3.4 ∗Ein integriertes Modell

Hier müssen Einsatzplanung und Scheduling in ein Modell integriert wer-den. Das kann z. B. mit einer Variable für jede Tour eines Roboters gesche-hen. Hier gehört zu einer Tour auch die Spezifikation der Startzeiten für allein der Tour bedienten Aufträge.

8.4 Theorie

Dieser Teil wurde durch den Vortrag von Thorsten Koch gestaltet.

8.4.1 Branch & Bound: NODE SELECTION

Welches Teilproblem bearbeite ich als nächstes?

Ziele:

1. Zulässige Lösungen finden

2. Untere Schranke hochtreiben

8.4.2 Branch & Bound: VARIABLE SELECTION

Welche Variable wähle ich für die Teilproblemzerlegung?

Ziele:

1. Möglichst viele Implikationen für andere Variablen


2. Möglichst starker Anstieg der unteren Schranke

8.4.3 Modellierung bedingter Nebenbedingungen

Erweiterte Modellierung mitzimpl vereinfacht Nebenbedingungen, dievon Variablenbelegungen abhängen etc.

8.5 ZIMPL-Modelle

8.5.1 Ein Zeitauswahl-Modell für optimierte Laserquellenaus-lastung

set I := { 1..4 };set T := { 1..300 };set J1 := { 1..10 };set J2 := { 1..10 };set J3 := { 1..10 };set J4 := { 1..10 };

param w1[J1] := <1> 8, <2> 10, <3> 1, <4> 2, <5> 3, <6> 1, <7> 5, <8> 5, <9> 22, <10> 3;param w2[J2] := <1> 2, <2> 5, <3> 20, <4> 2, <5> 2, <6> 1, <7> 3, <8> 1, <9> 14, <10> 10;param w3[J3] := <1> 5, <2> 12, <3> 9, <4> 7, <5> 3, <6> 4, <7> 7, <8> 1, <9> 6, <10> 6;param w4[J4] := <1> 1, <2> 2, <3> 2, <4> 3, <5> 8, <6> 20, <7> 6, <8> 1, <9> 3, <10> 14;param d1[J1] := <1> 2, <2> 47, <3> 24, <4> 16, <5> 5, <6> 5, <7> 8, <8> 10, <9> 16, <10> 7;param d2[J2] := <1> 22, <2> 1, <3> 39, <4> 15, <5> 15, <6> 1, <7> 3, <8> 5, <9> 25, <10> 14;param d3[J3] := <1> 6, <2> 19, <3> 24, <4> 10, <5> 56, <6> 5, <7> 4, <8> 2, <9> 4, <10> 10;param d4[J4] := <1> 17, <2> 6, <3> 5, <4> 1, <5> 21, <6> 15, <7> 41, <8> 4, <9> 27, <10> 3;

var z;

var x1[<j,t> in J1 * T] binary;




minimize cost: z;

subto maximum1:forall <t> in T: (t + w1[10] + d1[10] - 1) * x1[10,t] <= z;




subto job_partitioning1:forall <j> in J1: sum <t> in T: x1[j,t] == 1;




subto job_ordering1:forall <j> in J1 | j < 10:

sum <t> in T: (t + w1[j] + d1[j]) * x1[j,t] <= sum <t> in T: t * x1[j+1,t];







52 Optimierte Laserquellenauslastung (Mittwoch)

subto laser:forall <t> in T:

sum <j> in J1: sum <k> in T | k > t - w1[j] and k <= t: x1[j,k] +sum <j> in J2: sum <k> in T | k > t - w2[j] and k <= t: x2[j,k] +sum <j> in J3: sum <k> in T | k > t - w3[j] and k <= t: x3[j,k] +sum <j> in J4: sum <k> in T | k > t - w4[j] and k <= t: x4[j,k] <= 3;

############################################################################### eof

8.6 Aufgaben

Schreiben Sie einzimpl -Modell für dasn-DAMEN-PROBLEM und lösenes mit cplex für das größten, für das Sie eine Optimallösung in zehnMinuten schaffen.

Zur Erinnerung: Dasn-Damen-Problem besteht darin,n Damen so aufein (n×n)-Schachbrett zu platzieren, dass keine Dame eine andere schla-gen kann.

Im Unterschied zu den vorigen Übungen dürfen Sie nun alle Funktionenzu bedingten Bedingungen inzimpl benutzen.

Das n-Damen-Problem ist imzimpl -Handbuch zusammen mit zweiBeispielmodellen beschrieben. Sie dürfen die dortigen Modelle aber natür-lich auch etwas Eigenes probieren.

Teil III

Verkehr

Fahrzeugeinsatzplanungbeim ADAC (Donnerstag) 9Das Material wurde hauptsächlich den Artikeln [KRT02, GKRT02] ent-nommen. Weitere Aspekte finden sich in den Artikeln [HKR04a, HKR04b].

9.1 Hintergrund: Der ADAC-Hilfeservice

9.1.1 Hilfezentralen

Wie der ADAC seinen Service organisiert.

9.1.2 Die Aufgabe der Dispatcher

Was muss bei einem Anruf organisiert werden?


9.2.1 Online-/Echtzeit-Aspekt

Zukünftige Anrufe sind unbekannt und statistisch schwer vorherzusagen(seltene Ereignisse).

9.2.2 Die Reoptimierungsaufgabe beim ADAC

Um den Online-AlgorithmusREOPTzu verwenden, muss ein Fahrzeugein-satzplanungsproblem mit weichen Zeitfenstern in etwa zehn Sekunden ge-löst werden.

9.3 Modelle

9.3.1 Ein bogenbasiertes Modell

Eine Auswahlvariable für jeden Bogen und Zeitvariablen für jeden Auftragergeben ein schwaches Modell.

9.3.2 Ein tourbasiertes Modell

Eine Auswahlvariable für jede mögliche Tour ergibt ein wesentlich stärke-res Modell.

56 Fahrzeugeinsatzplanung beim ADAC (Donnerstag)

9.4 Theorie

9.4.1 Dualität in Linearer Programmierung

Die Essenz der Dualität in Linearen Programmen.

9.4.2 Dynamische Spaltengenerierung

Wie man sich die Dualinformation zunutze macht, um Optimalität für einTeilproblem mit wenig Variablen zu beweisen oder neue Variablen zu ge-nerieren.

9.5 ZIMPL-Modelle

9.5.1 Ein Bogenauswahl-Modell für Fahrzeugeinsatzplanung

############################################################################### ZIMPL file for the flow based model of the Vehicle Dispatching Problem# Joerg Rambau# 2005##############################################################################


param alpha := 0.1; # weight of drive cost against late costsparam m := 4; # number of serversparam n := 8; # number of genuine requests

set V_o := { 0 .. m - 1 }; # set of server origin requestsset V_d := { m .. 2 * m - 1 }; # set of server destination requestsset V_g := { 2 * m .. 2 * m + n - 1 }; # set of genuine requestsset V := V_o union V_d union V_g; # set of all requests

set U := { 0 .. m - 1 }; # set of serversset A := V * V; # the arc set of all possible server moves

param delta_t := 30; # standard time windowparam shift_t := 480; # standard time windowparam service_t := 15; # standard service timeparam service_c := 0; # default service costparam late_c := 100; # default late cost per hourparam drive_c := 100; # default drive cost per hour at unit speed

param ser_start_x [ in U ] := u; # start x coordinates of serversparam ser_start_y [ in U ] := u; # start y coordinates of servers

param ser_stop_x [ in U ] := u + m; # stop x coordinates of serversparam ser_stop_y [ in U ] := u + m; # stop y coordinates of servers

param ser_logon_t [ in U ] := 0; # logon times of serversparam ser_avail_t [ in U ] := 0; # earliest availability times of serversparam ser_shift_t [ in U ] := shift_t; # shift length of servers

param req_x [ <v> in V ] := if (<v> in V_o) then ser_start_x[v] # request corresponding to server start positionselse

if (<v> in V_d) then ser_stop_x[v - m] # request corresponding to server stop positionselse v # genuine requestsend

end;param req_y [ <v> in V ] := if (<v> in V_o) then ser_start_y[v] # request corresponding to server start positions

elseif (<v> in V_d) then ser_stop_y[v - m] # request corresponding to server stop positionselse v # genuine requestsend

end;

param req_enter_t [ <v> in V ] := if (<v> in V_o) then ser_avail_t[v] # request corresponding to server start positionselse

if (<v> in V_d) then ser_logon_t[v - m] # enter time of drive-home request is logon timeelse -v # enter times of genuine requestsend

end;param req_service_t [ <v> in V ] := if (<v> in V_o) then 0 # request corresponding to server start positions


elseif (<v> in V_d) then 0 # no service time for drive-home requestselse service_t # estimated service times at genuine requestsend

end;param req_delay_t [ <v> in V ] := if (<v> in V_o) then 0 # request corresponding to server start positions

elseif (<v> in V_d) then ser_shift_t[v - m] # tolerable delay is shift timeelse delta_t # time windows of tolerable delays at genuine requestsend

end;param req_service_c [V] := service_c; # cost coefficient of service timeparam req_late_c [V] := late_c; # cost coefficient of late time (including overtime for drive-home request)

param ser_drive_c [U] := drive_c; # cost coefficient of drive time


# the origin node of server u:defnumb origin (u) := u;

# the destination node of server u:defnumb destination (u) := u + m;

# the following number is the distance between two nodes:defnumb dist (v, w) := sqrt((req_x[v] - req_x[w])^2 + (req_y[v] - req_y[w])^2);

# the following number is the earliest service time at a node:defnumb req_earliest_service (v) := req_enter_t[v];

# the following number is the latest service time at a node:defnumb req_latest_service (v) := req_enter_t[v] + req_delay_t[v];

# the following number is the drive cost of arc a in A:defnumb arc_c (v, w, u) := ser_drive_c[u] * dist (v, w);

# we will need bounds and a big-M:

# maximal arrival time at a node (if req_enter_t is always non-positive):param max_t[<v> in V] := sum <w1> in V without {v}:

max <w2> in V:dist(w1, w2);

# maximal departure time at a node:param max_T[<v> in V] := max_t[v] + req_service_t[v];

# minimal arrival time at a node:param min_t[<v> in V] := max (0, req_enter_t[v]);

# maximal violation of driving time constraint w.r.t. x[v, w, u]:param M [<v, w> in A] := dist(v, w) + max_T[v] - min_t[w];


# variables for each move of a server connecting two requests:var x[A * U] binary;

# variables for the arrival time at a request:var t[V] real;

# variables for the completion time of a request:var T[V] real;

# variables for the excess delays at all requests:var y[V] real;


minimize cost:alpha * # this fraction goes into driving costssum in U: # for all servers

sum <v, w> in A: # account for the drive partarc_c (v, w, u) * x[v, w, u] # if arc a is used by server u

+ (1 - alpha) * # remaining fraction goes into late costssum <v> in V: # for all requests

req_late_c[v] * y [v]; # account for the lateness


58 Fahrzeugeinsatzplanung beim ADAC (Donnerstag)

subto no_loops:forall in U:

forall <v> in V:x[v, v, u] == 0;

subto flow_at_sources:forall in U: # forall servers

sum <u, v> in V_o * (V_g union {destination (u)}): # all arcs from a server origin to a genuine request or the destinationx[u, v, u] == 1;

subto flow_at_sinks:forall in U: # forall servers

sum <v, destination(u)> in (V_g union {origin(u)}) * V_d: # all arcs from a genuine request or the origin to the destination of a serverx[v, destination(u), u] == 1;

subto flow_at_requests:forall in U: # forall servers

forall <v> in V_g: # forall genuine requestssum <v, w> in V_g * (V_g union {destination(u)}): # all arcs to a genuine request or the destination of u

x[v, w, u]-sum <w, v> in (V_g union {origin(u)}) * V_g: # all arcs from a genuine request or the origin of u

x[w, v, u]== 0;

subto start_time_nonnegativity:forall <o> in V_o:

T[o] >= 0;

subto service_times:forall <v> in V_g:

T[v] - t[v] == req_service_t[v];

subto release_times:forall <v> in V_g:

T[v] >= req_earliest_service(v) + req_service_t[v];

subto lateness:forall <v> in V_g:

y[v] >= t[v] - req_latest_service(v);

subto lateness_nonnegativity:forall <v> in V_g:

y[v] >= 0;

subto driving_time:forall in U:

forall <v, w> in A:t[w] - T[v] - dist(v, w) + M[v, w] * (1 - x[v, w, u]) >= 0;

subto set_partitioning:forall <v> in V_g:

sum in U:sum <v, w> in V_g * (V_g union {destination(u)}):

x[v, w, u] == 1;

############################################################################### end of file.

9.6 Aufgaben

Schreiben Sie ein alternativeszimpl -Modell für dasVEHICLE DISPAT-CHING PROBLEM (VDP) beim ADAC, dass für jede Tour eines Hilfefahr-zeugs durch höchstens vier Aufträge eine Variable enthält. Lösen Sie damitdie Beispielinstanz aus der Nachmittags-Vorlesung: Alle Aufträge und alleHilfefahrzeuge stehen auf der Diagonale(x,x) in der Ebene. Daskte Hilfe-fahrzeug steht auf Position(k,k) mit Heimatposition(k+4,k+4) für k =0,1,2,3. Derkte Auftrag steht auf Position(k+8,k+8) für k = 0,1, . . . ,7.

Eine Skelett-Datei dafür finden Sie inVDP_Tours_Skeleton.zpl .Das Modell mit Variablen für alle Verbindungsfahrten und alle Ankunfts-und Abfahrtszeiten aus der Vorlesung finden Sie in der DateiVDP_Flow.zpl .

Zur Erinnerung: DasVDP ist gegeben durch:

9.6. Aufgaben 59

VEHICLE DISPATCHING PROBLEM (VDP)

Instanz: n Hilfefahrzeug mit augenblicklichen Koordinaten, Hei-matkoordinaten, Fahrtkosten pro Zeiteinheit, Schichtstart-zeiten, Schichtlängen und Überstundenkosten;m Aufträgemit augenblicklichen Koordinaten, Eintrittszeiten, Service-Dauern, angestrebter maximaler Wartezeit bis zum Eintref-fen eines Hilfefahrzeugs und Verspätungskosten pro Zeit-einheit für spätere Ankunft eines Hilfefahrzeugs.

Aufgabe: Weise jedem Hilfefahrzeug eine geordnete Menge von Auf-trägen zu (eineTour), so dass jeder Auftrag in genau einerTour liegt und so dass die Gesamtkosten aus Fahrtkosten undÜberstundenkosten für Hilfefahrzeuge und Verspätungsko-sten und Bedienkosten für Aufträge minimal sind.

Vergleichen Sie das neue Modell und das Modell der Vorlesung anhandvon

1. Korrektheit der Modelle für die Instanz/allgemein

2. Optimalwert der LP-Relaxierung/ILP-Optimum

3. Anzahl benötigter Branch-and-Bound-Knoten incplex

4. Anzahl von Variablen und Nebenbedingungen in Abhängigkeit vonder Anzahl der Hilfefahrzeuge und der Anzahl der Aufträge.

Umlaufplanung bei derBVG (Freitag) 10Das Material wurde hauptsächlich der Dissertation von Andreas Löbel [Löb98]und dem Artikel [GLV96] entnommen.

10.1 Hintergrund: Der ÖPNV-Planungsprozess

10.1.1 Die Planungshierarchie

Viele Planungsschritte müssen unabhängig voneinander durchgeführt wer-den, weil das Gesamtplanungsproblem zu kompliziert ist.

10.1.2 Fahrzeugumläufe

Bei gegebenem Fahrplan müssen Fahrzeuge geroutet werden, die die ver-schiedenen Fahrgastfahrten bedienen.


In jedem Fall möchte man Umläufe mit der minimalen Anzahl von Fahrzeu-gen. unter diesen Umläufen möchte man solche mit minimalen Betriebsko-sten.

10.2.1 Das Ein-Depot-Fahrzeugumlaufplanungsproblem

Hier hat man nur Fahrzeugstandort, und alle Fahrzeuge können alle Fahr-gastfahrten bedienen.

10.2.2 Das Mehr-Depot-Fahrzeugumlaufplanungsproblem

Hier hat man mehrere Fahrzeugstandorte und/oder man hat Fahrzeuge, dienicht alle Fahrgastfahrten bedienen können.

10.3 Modelle

10.3.1 Ein Zirkulationsmodell für die Ein-Depot-Aufgabe

Das Ein-Depot-Problem kann alsM INIMUM COST CIRCULATION PRO-BLEM formuliert werden. Wichtig ist, dass die Anzahl der benötigten Fahr-zeuge auf dem Depot-Rückführ-Bogen gemessen werden kann.

62 Umlaufplanung bei der BVG (Freitag)

10.3.2 Ein Zirkulationsmodell für die Mehr-Depot-Aufgabe

Das Mehr-Depot-Problem kann alsM INIMUM COST MULTI -COMMDITY

CIRCULATION PROBLEM formuliert werden. Wichtig ist wieder, dass dieAnzahl der benötigten Fahrzeuge auf den Depot-Rückführ-Bögen gemes-sen werden kann. Hier können auch die Depot-Kapazitäten erzwungen wer-den.

10.4 Theorie

10.4.1 Das ganzzahlige MINIMUM COST FLOW PROBLEM (MCFP)ist in P

Einige Polynomialzeit-Algorithmen finden sich in dem Buch von Korte undVygen [KV02]. Mehr dazu gibt es in dem Buch von Ahuja, Magnanti undOrlin [AMO93].

10.4.2 Das ganzzahlige MINIMUM COST MULTI-COMMODITY FLOW

PROBLEM (MCMCFP) ist NP-schwer

Siehe wieder das Buch von Korte und Vygen [KV02].

10.4.3 Lagrange-Relaxierung

Hier entsteht eine Relaxierung durch Verschiebung von Nebenbedingungenals gewichteter Strafterm in die Zielfunktion.

10.5 ZIMPL-Modell

10.5.1 Ein MCMCF-Modell für Mehr-Depot-Umlaufplanung

############################################################################### ZIMPL file for the multi-commodity flow based model for Vehicle Scheduling# (from Loebel’s PhD. Thesis)# Joerg Rambau# 2005##############################################################################


param n := 100; # number of nodes (= timetabled trips)

param c := 3; # number of commodities (= homogeneous depots)

set V_t := { 1 to n }; # the set of timetabled trips

set D := { 1000 + 1 to 1000 + c }; # the depot set

set V := V_t union D; # nodes for the resulting mutli-commodity flow problem

param delta := 0.01; # minimum change-over time between timetabled trips

param default_driving_c := 10; # driving cost per time unit

# the following matrix indicates compatible depots for trips:param compat [ V * D ] := read "BVG_compat.dat" as "<1n, 2n> 3n" comment "#";

10.5. ZIMPL-Modell 63

# the following set denotes the set of nodes that depot d can traverse:set V_d [ <d> in D ] := { <v> in V_t with compat[v, d] > 0 } union { d };

# the following parameter specifies the start time of each trip:param trip_start_t [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 2n" comment "#";

# the following parameter specifies the end time of each trip:param trip_end_t [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 3n" comment "#";

# the following parameter specifies the start x coordinate of each trip:param trip_start_x [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 4n" comment "#";

# the following parameter specifies the start y coordinate of each trip:param trip_start_y [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 5n" comment "#";

# the following parameter specifies the end x coordinate of each trip:param trip_end_x [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 6n" comment "#";

# the following parameter specifies the end y coordinate of each trip:param trip_end_y [ <v> in V_t ] := read "BVG_trips.dat" as "<1n> 7n" comment "#";

# the following parameter specifies the start time of each depot:param depot_start_t [ <d> in D ] := read "BVG_depots.dat" as "<1n> 2n" comment "#";

# the following parameter specifies the end time of each depot:param depot_end_t [ <d> in D ] := read "BVG_depots.dat" as "<1n> 3n" comment "#";

# the following parameter specifies the start x coordinate of each depot:param depot_start_x [ <d> in D ] := read "BVG_depots.dat" as "<1n> 4n" comment "#";

# the following parameter specifies the start y coordinate of each depot:param depot_start_y [ <d> in D ] := read "BVG_depots.dat" as "<1n> 5n" comment "#";

# the following parameter specifies the end x coordinate of each depot:param depot_end_x [ <d> in D ] := read "BVG_depots.dat" as "<1n> 4n" comment "#";

# the following parameter specifies the end y coordinate of each depot:param depot_end_y [ <d> in V ] := read "BVG_depots.dat" as "<1n> 5n" comment "#";

# the following parameter specifies the capacity of depot d:param depot_cap [ <d> in D ] := read "BVG_depots.dat" as "<1n> 6n" comment "#";

# the following parameter specifies the minimum no. of buses for depot d:param depot_min [ <d> in D ] := read "BVG_depots.dat" as "<1n> 7n" comment "#";

# the following parameter specifies the start time of each node:param start_t [ <v> in V ] := if <v> in V_t then trip_start_t[v]

else depot_end_t[v]end;

# the following parameter specifies the end time of each node:param end_t [ <v> in V ] := if <v> in V_t then trip_end_t[v]

else depot_start_t[v]end;

# the following parameter specifies the start x coordinate of each node:param start_x [ <v> in V ] := if <v> in V_t then trip_start_x[v]

else depot_start_x[v]end;

# the following parameter specifies the start y coordinate of each node:param start_y [ <v> in V ] := if <v> in V_t then trip_start_y[v]

else depot_start_y[v]end;

# the following parameter specifies the end x coordinate of each node:param end_x [ <v> in V ] := if <v> in V_t then trip_end_x[v]

else depot_end_x[v]end;

# the following parameter specifies the end y coordinate of each node:param end_y [ <v> in V ] := if <v> in V_t then trip_end_y[v]

else depot_end_y[v]end;

# the following number is the assymetric distance between two nodes,# which is the time it takes to drive from the end of one trip v to# the start of the next trip w:defnumb dist (v, w) := sqrt((end_x[v] - start_x[w])^2 + (end_y[v] - start_y[w])^2) / 60;

# the complete set of possible connecting arcs:set A_f := { <v, w> in V * V with end_t[v] + dist(v, w) <= start_t[w] - delta };

# the arc set that can be used by depot d:set A_d [ <d> in D ] := { <v, w> in A_f with <v> in V_d[d] and <w> in V_d[d] };

# the set of all possible depot flow arcs:set A := { <d, v, w> in D * A_f with <v, w> in A_d[d] };

# small operational costs proportional to distance:

64 Umlaufplanung bei der BVG (Freitag)

param operational_cost [<d, v, w> in A ] := dist (v, w) * default_driving_c;

# large costs to buy a bus:param capital_cost := 100000;

# total cost (capital cost is accounted for in an outgoing arc from the depot:param cost [<d, v, w> in A ] := if v == d then capital_cost + operational_cost[d, v, w]

else operational_cost[d, v, w]end;


# one flow variable for each arc and depot:var x[A] binary;


minimize cost:sum <d, v, w> in A:

cost[d, v, w] * x[d, v, w];


subto flow_conservation:forall <d> in D:

forall <v> in V_d[d]:sum <v, w> in A_d[d]:

x[d, v, w]-sum <w, v> in A_d[d]:

x[d, w, v]== 0;

subto set_partitioning:forall <v> in V_t:

sum <d, v, w> in A:x[d, v, w] == 1;

subto depot_capacity:forall <d> in D:

sum <d, v> in A_d[d]:x[d, d, v] <= depot_cap[d];

subto depot_min:forall <d> in D:

sum <d, v> in A_d[d]:x[d, d, v] <= depot_min[d];

############################################################################### end of file.

Literaturverzeichnis

[AMO93] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.Network Flows: Theory, Algo-rithms, and Applications. Prentice Hall, Englewood Cliffs, New Jersey, 1993.

[Asc95] Norbert Ascheuer.Hamiltonian Path Problems in the On-line Optimization of Flexible Manu-facturing Systems. Dissertation, Technische Universität Berlin, 1995. Available from:ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.ps.Z .

[EGK+04] Andreas Eisenblätter, Hans-Florian Geerdes, Thorsten Koch, Alexander Martin, and Roland Wes-säly. UMTS radio network evaluation and optimization beyond snapshots. ZIB-Report 04-15,Konrad-Zuse-Zentrum für Informationstechnik, 2004. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-04-15 .

[Eis01] Andreas Eisenblätter. Frequency Assignment in GSM Networks: Models, Heuristics, andLower Bounds. Cuvillier-Verlag, 2001. Available from:ftp://ftp.zib.de/pub/zib-publications/books/PhD_eisenblaetter.ps.Z .

[FG93] Greg N. Frederickson and D. J. Guan. Nonpreemptive ensemble motion planning on a tree.Jour-nal of Algorithms, 15:29–60, 1993.

[GKR01] Martin Grötschel, Sven O. Krumke, and Jörg Rambau. Online optimization of complex trans-portation systems. In Martin Grötschel, Sven O. Krumke, and Jörg Rambau, editors,On-line Optimization of Large Scale Systems, pages 705–730. Springer, 2001. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-01-17/ .

[GKRT02] Martin Grötschel, Sven O. Krumke, Jörg Rambau, and Luis M. Torres. Online-dispatching ofautomobile service units. In Ulrike Leopold-Wildburger, Farnz Rendl, and Gerhard Wäscher,editors, Operations Research Proceedings, pages 168–173. Springer, 2002. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-02-44/ .

[GL93] Martin Grötschel and László Lovász.Geometric Algorithms and Combinatorial Optimization,volume 2 ofAlgorithms and Combinatorics. Springer-Verlag, 2 edition, 1993.

[GLV96] Martin Grötschel, Andreas Löbel, and Manfred Völker. Optimierung des Fahrzeugumlaufs imÖffentlichen Nahverkehr. Preprint SC 96-8, Konrad-Zuse-Zentrum für Informationstechnik, 1996.Available from:http://www.zib.de/PaperWeb/abstracts/SC-96-08 .

[HKR00] Dietrich Hauptmeier, Sven O. Krumke, and Jörg Rambau. The online dial-a-ride problem underreasonable load. InProceedings of the 4th Italian Conference on Algorithms and Complexity,volume 1767 ofLecture Notes in Computer Science, pages 137–149. Springer, 2000. Availablefrom: http://www.zib.de/PaperWeb/abstracts/SC-99-08/ .

[HKR04a] Benjamin Hiller, Sven O. Krumke, and Jörg Rambau. Reoptimization gaps versus model errors inonline-dispatching of service units for adac.Electronic Notes in Discrete Mathematics, 18:175–163, 2004. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-04-17/ .

ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.ps.Z�

ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.ps.Z�

http://www.zib.de/PaperWeb/abstracts/ZR-04-15�


ftp://ftp.zib.de/pub/zib-publications/books/PhD_eisenblaetter.ps.Z�

ftp://ftp.zib.de/pub/zib-publications/books/PhD_eisenblaetter.ps.Z�

http://www.zib.de/PaperWeb/abstracts/ZR-01-17/�


http://www.zib.de/PaperWeb/abstracts/SC-96-08�

http://www.zib.de/PaperWeb/abstracts/SC-99-08/�


66 Literaturverzeichnis

[HKR04b] Benjamin Hiller, Sven O. Krumke, and Jörg Rambau. Reoptimization gaps versus model er-rors in online-dispatching of service units for adac. ZIB-Report ZR 04-17, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2004. Proceedings of the Latin American Confe-rence on Combinatorics, Graphs and Applications (LACGA 2004), to appear. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-04-17/ .

[HKRW01] Dietrich Hauptmeier, Sven O. Krumke, Jörg Rambau, and Hans C. Wirth. Euler is standingin line—dial-a-ride problems with FIFO-precedence-constraints.Discrete Applied Mathema-tics, 113:87–107, 2001. Available from:http://www.zib.de/PaperWeb/abstracts/SC-99-06/ .

[Koc04] Thorsten Koch.Rapid Mathematical Programming. Dissertation, Technische Universität Berlin,2004. Available from:http://edocs.tu-berlin.de/diss/2004/koch_thorsten.pdf .

[KRT02] Sven O. Krumke, Jörg Rambau, and Luis Miguel Torres. Realtime-dispatching of guided andunguided automobile service units with soft time windows. In Rolf H. Möhring and Rajeev Ra-man, editors,Algorithms – ESA 2002, 10th Annual European Symposium, Rome, Italy, September17–21, 2002, Proceedings, volume 2461 ofLecture Notes in Computer Science. Springer, 2002.Available from:http://www.zib.de/PaperWeb/abstracts/ZR-01-22 .

[KV02] Bernhard Korte and Jens Vygen.Combinatorial Optimization. Springer, Berlin, Heidelberg, NewYork, 2nd edition, 2002.

[KZ04] Arie M. C. A. Koster and Adrian Zymolka. Linear programming lower bounds for minimumconverter wavelength assignment in optical networks. ZIB-Report 04-41, Konrad-Zuse-Zentrumfür Informationstechnik, 2004. To appear in: Proceeding of INOC 2005, International NetworkOptimization Conference, March 20-23, 2005 Lissabon, Portugal. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-04-41 .

[Löb98] Andreas Löbel.Optimal Vehicle Scheduling in Public Transit. Shaker Verlag, 1998. Availablefrom: ftp://ftp.zib.de/pub/zib-publications/books/Loebel.disser.ps .

[MATHEON04] DFG-ForschungszentrumMATHEON. Digitaler Adventskalender 2004 – Lösungsheft, 2004.Available from: http://www.mathekalender.de/MathekalenderLoesungen.pdf .

[NW98] George L. Nemhauser and Laurence A. Wolsey.Integer and Combinatorial Optimization. DiscreteMathematics and Optimization. Wiley-Interscience, 1998.

[Ram04a] Jörg Rambau. Vortrag in der URANIA Berlin, March 2004. Available from:http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/Slides/Schueler_Aufzug_2004-03-16.pdf .

[Ram04b] Jörg Rambau. Gelbe Engel, ein Handlungsreisender und die Sprache der Mathe-matik. Vortrag in der URANIA Berlin, November 2004. Available from:http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/Slides/Schueler_ADAC_2004-11-16.pdf .




http://edocs.tu-berlin.de/diss/2004/koch_thorsten.pdf�

http://edocs.tu-berlin.de/diss/2004/koch_thorsten.pdf�




ftp://ftp.zib.de/pub/zib-publications/books/Loebel.disser.ps�

http://www.mathekalender.de/MathekalenderLoesungen.pdf�

http://www.mathekalender.de/MathekalenderLoesungen.pdf�

http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/Slides/Schueler_Aufzug_2004-03-16.pdf�

http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/Slides/Schueler_Aufzug_2004-03-16.pdf�

http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/Slides/Schueler_ADAC_2004-11-16.pdf�



Literaturverzeichnis 67

[Tuc03] Andreas Tuchscherer. Dynamical configuration of transparent optical telecommunication net-works. Diplomarbeit, Technische Universität Berlin, 2003. Available from:http://www.zib.de/tuchscherer/Publications/tuchscherer_thesis.pdf .

[Wes00] Roland Wessäly. DImensioning Survivable Capacitated NETworks (DISCNET). PhD thesis,Technische Universität Berlin, 2000. Available from:http://www.zib.de/wessaely/postscript/thesis.ps.gz .

[ZKW02] Adrian Zymolka, Arie M. C. A. Koster, and Roland Wessäly. Transparent optical network de-sign with sparse wavelength conversion. ZIB-Report 02-34, Konrad-Zuse-Zentrum für Infor-mationstechnik, 2002. Available from:http://www.zib.de/PaperWeb/abstracts/ZR-02-34 .

http://www.zib.de/tuchscherer/Publications/tuchscherer_thesis.pdf�

http://www.zib.de/tuchscherer/Publications/tuchscherer_thesis.pdf�

http://www.zib.de/wessaely/postscript/thesis.ps.gz�

http://www.zib.de/wessaely/postscript/thesis.ps.gz�

Documents

Jörg Rambau Version 0.1.0 vom 15. März 2005...kalender 2004 [MATHEON04] des DFG-ForschungszentrumsMATHEON, Berlin, gestaltet: Am Beispiel des ASSIGNMENT PROBLEMS (AP) werden untere