Optimale Fahrpläne

ISBN-13: 9783540049449 / Niemiecki / Miękka / 1970 / 165 str.

Gotz Uebe

Spis treści

1 Die Grundstruktur des Fahrplanproblems.- (1) Das geographische Teilproblem (Transportaufgabe).- (2) Das zeitliche Teilproblem (Zeitliche Struktur).- (3) Das Fahrzeug-Teilproblem (Flugzeugeinsatz).- (4) Das Realisierbarkeits-Problem.- (5) Das Problem der Zielfunktion.- (6) Das Problem der zusammenhängenden Lösung des Gesamtproblems.- 2 Das Klassische Transportproblem.- I Das einstufige Transportproblem.- (1) Formulierung.- (2) Interpretation als ein Fahrplanproblem.- II Das klassische Transportproblem mit zweistufiger Bestimmung eines Fahrplans.- (1) Grundgedanke.- (2) Die Lösung durch Inspektion.- (3) Die systematische Lösung.- (4) Die heuristische Lösung (Simulation).- (5) Eine fiberschlagsrechnung für die Zahl der erforderlichen Fahrzeuge.- III Das klassische Transportproblem mit Periodisierung.- IV Das klassische Transportproblem mit Periodisierung und Lagerhaltung.- 3 Das Klassische Ernennungsproblem.- I Formulierung und Interpretation.- (1) Das Ernennungsproblem.- (2) Interpretation als Anschlußproblem.- II Die Bestimmung der Koeffizienten der Zielfunktion.- (1) Verschiedene zeitliche Strukturen.- (2) Die Umwandlung nach Hoernke und Zwahlen.- 1. Allgemeines.- 2. Die Definition der Wartezeiten.- 3. Die Anwendung des Koopmans’schen Preistheorems.- 4. Falldiskussion.- 5. Die Umformung.- 6. Beispiele.- 7. Die „direkte“ Lösung des Anschlußproblems.- III Die Bestimmung der Anschlüsse.- (1) Algorithmen zur Lösung des Anschlußproblems.- 1. Allgemeine Algorithmen.- 2. Die Abzählregel von Wedekind.- (2) Eine Abzählregel zur Lösung.- 1. Die allgemeine Regel.- 2. Die Anwendung auf die einzelnen Fälle.- 3. Die allgemeine Korrektur vollständiger P-Reihen.- 4. Ein Beispiel zum Versagen der P-Reihen-Bestimmung.- 5. Der Abschluß der Lösung mit dem Ungarischen Algorithmus.- 6. Abschluß der Lösung über eine Fortsetzung der P-Reihenkorrektur.- 1) Verschiebung des Periodenbeginns.- 2) Fortsetzung der P-Reihenkorrektur über die Diagonale.- 7. Ausblockieren von Feldern.- 8. Ergebnis.- IV Diskussion der bearbeiteten Beispiele.- (1) Mehrfachlösungen.- 1. Viele Lösungen in den Beispielen.- 2. Eindeutigkceitsbedingungen für einen Fahrplan.- (2) Blocktriangularität.- (3) Verbesserung durch Leerfahrten.- 1. Der allgemeine Gedanke.- 2. Beispiel.- (4) Die Ergänzung des Problems von Larson.- 1. Ergänzung des nichtsymmetrischen Fahrplans über ein Transportproblem.- 2. Der Larson’sche Lösungsvorschlag.- (5) Die Interpretation der P-Reihenkorrektur.- (6) Enumeration der Lösungen.- 4 Der Fahrplan-Graph von Bartlett.- (1) Allgemeines.- (2) Die Abzählregel für die Fahrzeugzahl.- (3) Die Bestimmung der Fahrzeugeinsatzfolgen.- (4) Diskussion.- 5 Veränderungen in Einem Pesteieenden Fahrplan.- I,(1) Die Fragestellung.- (2) Offensichtliche Verbesserungsnäg)ichkeiten.- II Verbesserungsversuch unter Berücksichtigung der Gesamtwartezeiten.- (1) Sonderfall der Wartezeitminimierung.- (2) Herabsetzung der Gesamtwartezeiten.- (3) Ein Folgenkatalog.- (4) Ein Auswahlkriterium für eine zu ändernde Reise.- (5) Beispiel.- (6) Folgerung.- (7) Die Unbrauchbarkeit der von einer Zuordnung getrennten Kriterien.- III Der Einfluß einer Reise auf die erforderliche Fahrzeugzahl über die ganze Periode.- (1) Die Einbettung einer Reise.- (2) Zwei Beispiele.- IV Die Änderung im Zuge der Bestimmung der Lösung.- (1) Der Gesamtzusammenhang des Fahrplans.- (2) Die Einbettung der Reise.- (3) Eine heuristische Suchregel.- (4) Bemerkungen zur Suche.- (5) Ein Beispiel mit Einschränkung der Verschiebung auf die Anschlussbereiche allein.- V Stochastisch bestimmte Fahrpläne.- VI Das Kompressionsverfahren.- VII Die Veränderung eines Fahrplans aus der Bartlett-Anschlußmatrix.- (1) Die zugrundeliegende Information.- (2) Eine Vermutung der Verbesserungsmöglichkeit.- (3) Gegenbeispiel zum Hinreichen der Knotenbedingung.- (4) Notwendigkeit der.Knotenbedingung.- (5) Die Ergänzung zur vollen Zahl der Knoten.- (6) Die Mängel des Knotensuchverfahrens.- 6 Die Direkte Lineare Programmierungs-Formulierung.- I Ein allgemeines LP-Modell.- (1) Die Anwendbarkeit des allgemeinen LP-Modells.- (2) Der Grundansatz.- (3) Die Berücksichtigung der Transportaufgabe.- (4) Der Fahrzeuggesichtspunkt.- (5) Systemgesichtspunkte.- (6) Fehlende Gesichtspunkte der zeitlichen Struktur und Ganzzahligkeit.- (7) EYrpirisches Auftreten nichtganzzahliger Lösungen.- (8) Nichtzu»gsigkeit von Pooldaten.- (9) Die Rechenzeiten im Grundmodell.- II Die Erweiterung des Grundmodells.- (1) Appelgrens Modell.- (2) Die Lösung über zu1Assige Fahrzeugzyklen.- 1. Die Möglichkeiten der Enumeration von Zyklen.- 2. Die Kanten-Zyklus-Inzidenzmatrix.- 3. Der Charnes-Miller-Ansatz.- 4. Der Ansatz von Appelgrens Modell 2.- 5. Der Dekczpositionsansatz von Appelgren.- 6. Der Dekanpositionsansatz von Dantzig-Blattner-Rao.- 7. Das „Potential“-Modell von Menzel-Göttner.- 7 Das „Verallgemeinerte“ Transportproblem.- (1) Ansatz.- (2) Diskussion.- (3) Die Erweiterung des Modells bei stochastischer Nachfrage.- (4) Das verallgemeinerte Transportproblem von Krelle.- (5) Der Vergleich der Ansätze von Dantzig und Krelle.- 8 Der Übergang zur Gruppe der Synthese-Probleme von Hu-Gomory.- (1) Das Problem von Bartlett und Charnes.- (2) Das allgemeine Syntheseproblem.- 9 Modetir der Ganzzahligen Programmierung.- (1) Die Bedeutung der Ganzzahligkeit.- (2) Ein Modell vam Typ des „branch and bound“.- (3) Ein Modell zum Gomory-Algorithmus.- (4) Das Umsteigeproblem von Krelle.- (5) Das Sonderproblem des Sternverkehrs.- (6) Die Formulierung als ein Reihenfolgeproblem.- 10 Das Wartezeitproblem von Tingaud und Jewell.- (1) Die Bedienungshäufigkeit als Entscheidungsgröße.- (2) Die gleichmäßige Nachfrageverteilung.- (3) Der Ansatz.- (4) Diskussion.- 11 Dynamische Programmierungsansätze.- (1) Allgemeines.- (2) Das Dynamische Programm von Bisbee.- 1. Die zugrundeliegende Situation.- 2. Die Wertfunktion.- 3. Beispiel.- 4. Kritik des Ansatzes.- (3) Das Dynamische Program von Larson.- 1. Das Ernennungsproblem plus zusätzliche Beschränkungen.- 2. Die Zustände des Dynamischen Programm.- 3. Beispiel.- 4. Formulierung als ein Kontrollproblem.- (4) Der Dynamische Progranmierungs-Ansatz über eine sukzessive Annäherung.- 1. Nichtkonnektivität und Dimension der Ansätze Bisbee und Larson.- 2. Larsons Problem des längsten Pfades.- 3. Die Konstruktion eines Fahrplans nach Hyman.- (5) Das allgemeine Problem der Flugplanbestimung über ein Dynamisches Program fUr den längsten Pfad.- 1. Der Ansatz der Wertfunktion.- 2. Die Folge periodisierter Ernennungsprobleme.- 3. Die Größe des Problems.- 4. Ausblick.