Jens Opitz Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen GABLER RESEARCH Logistik, Mobilität und Verkehr Herausgegeben von PD Dr. Frank Himpel, Mainz School of Management and Economics Univ.-Prof. Dr.-Ing. Rainer König, Technische Universität Dresden Jens Opitz Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen Mit einem Geleitwort von Prof. Dr. rer. nat. habil. Karl Nachtigall RESEARCH Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über <http://dnb.d-nb.de> abrufbar. Dissertation Technische Universität Dresden, 2009 1. Auflage 2009 Alle Rechte vorbehalten © Gabler | GWV Fachverlage GmbH, Wiesbaden 2009 Lektorat: Claudia Jeske | Sabine Schöller Gabler ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.gabler.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspei- cherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Printed in Germany ISBN 978-3-8349-2128-4 Geleitwort Dierechnergestu¨tzteErstellungvonFahrpla¨nenstelltheuteimRahmenderstrategischenFahr- planungimSchienenverkehrsbereichaufgrundderAnwendungeffizientermathematischerVer- fahren und steigenden Rechnerkapazita¨ten ein immer wichtigeres Element dar. Zum einen dientsiederUnterstu¨tzungdesFahrplaners,indemsiedieEffizienzseinerArbeitdurchAuto- matisierungsteigert.ZumanderenversetztsieVerkehrs-undInfrastrukturunternehmenindie Lage,durchdieErzeugungundBewertungeinerVielzahlverschiedenerFahrplanvariantenei- negenaueAnalysedervorhandenenInfrastruktur,insbesondereauchaufverkehrlichsinnvolle zuku¨nftigeMaßnahmenvorzunehmen.Dabeikommtderschnellen,automatischenundvoral- lemkonfliktfreienErzeugungundOptimierungvonFahrpla¨neneineganzbesondereBedeutung zu. DieDBNetzeuntersuchtdieLeistungsfa¨higkeitderBahnanlagennichtnurmitreinstochas- tischenundanalytischenVerfahren,sondernauchmitHilfevonFahrplanstudienundSimula- tionen.Eingangsgro¨ßensindnebendermikroskopischmodelliertenInfrastrukturdasBetriebs- programminFormzuku¨nftigerAngebotskonzepte.DadieseseitensderEisenbahnverkehrsun- ternehmenundderBestellerorganisationendesSchienenpersonennahverkehrsnurbegrenzt langfristigvorgegebenwerdenko¨nnen,istdieDBNetzealsEisenbahninfrastrukturunterneh- merdaraufangewiesen,hierselbstAnnahmenzutreffen.EinewesentlicheHilfestellendabei mathematischeVerfahrendar,mitdenenFahrpla¨neerzeugtundoptimiertwerdenko¨nnen. DieverkehrswissenschaftlicheBescha¨ftigungzurKonstruktionvonTaktfahrpla¨nenbegannin densechzigerJahrendurchdieDresdenerSchuleumHerrnProf.Dr.S.Ru¨ger.AbMitteder siebzigerJahreerfolgtenweiterfu¨hrendeArbeitenvonDr.WegelundDr.WeigandanderTech- nischenUniversita¨tBraunschweig.DiemathematischeTheoriederTaktfahrpla¨newurdedurch diegrundlegendeArbeitvonSerafiniundUkoviczuperiodischenSchedulingproblememinitiert. DiePolyhedrischeTheoriederTaktfahrpla¨newurdevonProf.Dr.NachtigallundDr.Liebchen (TUBerlin)maßgeblichvorangetrieben.EinweitererMeilenstein-dasProgrammsystemDONS zurautomatischenKonstruktionvonTaktfahrpla¨nen-wurdedurchdieniederla¨ndischeEisen- bahninitiiert. AnderProfessurfu¨rVerkehrsstro¨mungslehre(TechnischeUniversita¨tDresden,Fakulta¨tVer- kehrswissenschaften F´riedrich List´) ist mit dem Programmsystem TAKT ein solches Instru- mentzurstrategischenFahrplanungimSchienenverkehrinjahrelangerZusammenarbeitmit derDeutschenBahnNetzAG(DBNetze)entstanden.DiesesbietetdemNutzerdieMo¨glich- keit, fu¨r eine vorgegebene Infrastruktur und ein zugeho¨riges Betriebsprogramm importierter Musterzu¨gezula¨ssigeTaktfahrlagenpla¨neautomatischzuerzeugenunddiesezuoptimieren. VI Geleitwort DasProgrammsystemTAKTistinPraxisvarianteninNordrhein-Westfalen,imMitteldeutschen Raum,inSu¨dwestdeutschlandundaktuellimRheinkorridormitkomplettem,umliegendemNetz fu¨rdenschienengebundenenPersonennah-und-fernverkehrsowieGu¨terverkehrinZusam- menarbeitmitderDBNetzeerfolgreichgetestetundweiterentwickeltworden. DievorliegendeArbeitlieferteinenwesentlichenBeitragzumMethodengeba¨udederTaktfahrla- genplanungundstellteineumfassendeMonographiezurPraxisundTheoriedar.DerSchwer- punktderArbeitliegtinderEntwicklungundEvaluierungvonVerfahrenundAlgorithmenzur Lo¨sungpraxisrelevanterProbleme.HieristinsbesonderedieMaximierungderAnzahlvonge- takteten Systemtrassen im Gu¨terverkehr zu nennen. Die erzielten Ergebnisse, insbesonde- redieErweiterungvomModulo-Netzwerk-Simplex-Algorithmus,erweiternebensomaßgeblich dasTheoriegeba¨ude. Eswirdgezeigt,wieTaktfahrlagenpla¨nesowohlfu¨rdenschienengebundenenPersonenverkehr alsauchfu¨rdenschienengebundenenGu¨terverkehrautomatischerzeugt,danachebenfallsau- tomatischoptimiertundgegebenenfallsvomNutzerverkehrlichbewertetwerdenko¨nnen.Ent- scheidenddabeiistsowohldieMo¨glichkeitdesFahrplanerszumEingreifenindenPlanungs- prozess,alsauchdieguteHandhabbarkeitderAlgorithmenunddesProgrammsystemsTAKT, was sich vor allem auf den Wunsch nach sehr kurzen Rechenzeiten fokussiert. Die Lo¨sung dieserVielfaltanAnforderungen,wobeimancheauchkontra¨rzueinanderstehen,machtdie Bedeutung dieser Arbeit aus. Das Hauptaugenmerk liegt zusa¨tzlich darauf, dass Fahrpla¨ne fu¨rbesondersgroße,realeundkomplexeSchienenverkehrsnetzezuberechnensind.Darinist zugleichdieAbgrenzungvonanderenwissenschaftlichenAbhandlungenzusehen.Weiterhin istherauszustellen,dasshiererstmalseinVerfahrenentwickeltwurde,mitdemdieMischbe- triebsproblematik,d.h.Reise-undGu¨terzu¨geaufdergleichenStrecke,systematischmodelliert werdenkann.Ha¨ufigsindinderPraxisbestimmteZu¨geschonvorgegebenunddieBearbei- tungweitererZu¨geunddieOptimierungmussdieseRandbedingungbeachten.Esdu¨rfenaber z.B.nochbegrenztezeitlicheVerschiebungenvorgenommenwerden.DieentwickeltenVerfah- renlassenbewussteinderartigesinteraktivesVorgehenzu.Eina¨hnlichesProblemstelltsich beiderGenerierungderTrassenfu¨rdieGu¨terzu¨ge.HierwirdderFahrplaninsgesamterzeugt. Ha¨ufigistdieFahrplanstrukturdesPersonenverkehrsschonweitgehendvorgegeben,kleinere VerschiebungenzugunstendesGu¨terverkehrssindjedochzula¨ssig. DieerreichtenErgebnissestelleneinenwichtigenBeitragzurErweiterungdesEinsatzesma- thematischerVerfahrenzurFahrplanungundBeurteilungundAusscho¨pfungderKapazita¨tvon Infrastrukturen spurgefu¨hrter Verkehrsmittel dar. Die Anforderungen der Praxis wurden voll erfu¨llt. Dresden,imOktober2009 Universita¨tsprofessor Dr.rer.nat.habil.KarlNachtigall Vorwort Dierechnergestu¨tzteErstellungvonFahrpla¨nenstelltheuteimRahmenderstrategischenFahr- planungimSchienenverkehrsbereichaufgrundderAnwendungeffizientermathematischerVer- fahren und steigenden Rechnerkapazita¨ten ein immer wichtigeres Element dar. Zum einen dientsiederUnterstu¨tzungdesFahrplaners,indemsiedieEffizienzseinerArbeitdurchAuto- matisierungsteigert.ZumanderenversetztsieVerkehrs-undInfrastrukturunternehmenindie Lage,durchdieErzeugungundBewertungeinerVielzahlverschiedenerFahrplanvariantenei- negenaueAnalysedervorhandenenInfrastruktur,insbesondereauchaufverkehrlichsinnvolle zuku¨nftigeMaßnahmenvorzunehmen.Dabeikommtderschnellen,automatischenundvoral- lemkonfliktfreienErzeugungundOptimierungvonFahrpla¨neneineganzbesondereBedeutung zu. AnderProfessurfu¨rVerkehrsstro¨mungslehre(TechnischeUniversita¨tDresden)istmitdemPro- grammsystemTAKTeinsolchesInstrumentzurstrategischenFahrplanungimSchienenverkehr entstanden.DiesesbietetdemNutzerdieMo¨glichkeit,fu¨reinevorgegebeneInfrastrukturund einzugeho¨rigesBetriebsprogrammimportierterMusterzu¨gezula¨ssigeTaktfahrlagenpla¨neau- tomatischzuerzeugenunddiesezuoptimieren.DasProgrammsystemTAKTistinPraxisvari- anteninNordrhein-Westfalen,imMitteldeutschenRaum,inSu¨dwestdeutschlandundaktuellim Rheinkorridormitkomplettem,umliegendemNetzfu¨rdenschienengebundenenPersonennah- und-fernverkehrsowieGu¨terverkehrinZusammenarbeitmitderDBNetzAGerfolgreichge- testetundweiterentwickeltworden. Diese Arbeit setzt sich aus fu¨nf Teilen zusammen. Es wird gezeigt, wie Taktfahrlagenpla¨ne sowohlfu¨rdenschienengebundenenPersonenverkehralsauchfu¨rdenschienengebundenen Gu¨terverkehrautomatischerzeugt,danachebenfallsautomatischoptimiertundgegebenenfalls vomNutzerverkehrlichbewertetwerdenko¨nnen.EntscheidenddabeiistsowohldieMo¨glichkeit desFahrplanerszumEingreifenindenPlanungsprozess,alsauchdieguteHandhabbarkeitder AlgorithmenunddesProgrammsystemsTAKT,wassichvorallemaufdenWunschnachsehr kurzenRechenzeitenfokussiert. Die Lo¨sung dieser Vielfalt an Anforderungen, wobei manche auch kontra¨r zueinander sind, macht die Bedeutung dieser Arbeit aus. Das Hauptaugenmerk liegt zusa¨tzlich darauf, dass Fahrpla¨ne fu¨r besonders große, reale und komplexe Schienenverkehrsnetze zu berechnen sind.DarinistzugleichdieAbgrenzungvonanderenwissenschaftlichenAbhandlungenzuse- hen. VIII Vorwort FolgendeFragenwerdenindeneinzelnenKapitelnumfassendbeantwortet: THEMATISCHEGRUNDLAGEN • WasisteinFahrplan? • WelcheFahrpla¨negibtes? • WieistderStandderWissenschaft? AUTOMATISCHESERZEUGENVONTAKTFAHRPLA¨NEN • Wieerstelltmanein PeriodicEventSchedulingProblem“? ” • Wiewirdesgelo¨st? • WelcheRollespielendabeidielokalenKonflikte? • IstdieLo¨sungeinFahrplanundwennja,istdieserverkehrlichsinnvoll? MAXIMIERUNGVONGETAKTETENSYSTEMTRASSEN • KannmanschienengebundenenGu¨terverkehrundPersonenverkehrgleichbehandeln? • WasisteineGu¨terverkehrssystemtrasse? • WasmachtderFlowmastermitdemPESP-Orakel? • WozubrauchtmanMusterzugatomeundwiesehendieseaus? OPTIMIERUNGVONTAKTFAHRPLA¨NEN • WelcheVariantenderOptimierungko¨nneneingesetztwerden? • WasisteinModulo-Netzwerk-Simplex-Algorithmus? • SinddieermitteltenTaktfahrpla¨neoptimal? ZUSAMMENFASSUNGUNDAUSBLICK • WasistneuandieserArbeit? • GibtesVerbesserungspotential? ZuguterLetztseinocherwa¨hnt,dassdieswedereinProgrammhandbuchfu¨rTAKT,nochein ingenieurwissenschaftlicherForschungsbericht,nocheinMathematikbuchist.AberlesenSie selbst. EinFahrplanohneEisenbahnistungefa¨hrsosinnvollwieeinFlirtohne tiefereAbsicht. freinachMarcelloMastroianni Inhaltsverzeichnis Geleitwort III Vorwort V Abbildungsverzeichnis XI Tabellenverzeichnis XV Abku¨rzungsverzeichnis XVII Fachbegriffsverzeichnis XIX Symbolverzeichnis XXI I Einfu¨hrung 1 1 Einfu¨hrungindieProblematik 3 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Umsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 ThematischeGrundlagen 9 2.1 Verkehrsplanungimo¨ffentlichenPersonenverkehr . . . . . . . . . . . . . . . . . 9 2.2 EingliederungvonTaktfahrpla¨nenindenGesamtkontext . . . . . . . . . . . . . . 11 2.2.1 DefinitionFahrplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Taktfahrplan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.3 ErmittlungvonFahrpla¨nen . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.4 ErzeugungvonTaktfahrpla¨nen . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.5 OptimierungvonTaktfahrpla¨nen . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.6 VerkehrsplanerischeHinweise . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Trassenkonstruktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 SchienengebundenerGu¨terverkehr. . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.2 Mischverkehr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.3 TrassengestaltungimGu¨terverkehr. . . . . . . . . . . . . . . . . . . . . . 33 3 Untersuchungsgebiete–realeVerkehrsbeispiele 35 3.1 Su¨dwestdeutschland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 BeschreibungdesUntersuchungsgebietes . . . . . . . . . . . . . . . . . 35 3.1.2 Betriebsprogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 Nordrhein-Westfalen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 X Inhaltsverzeichnis 3.3 MitteldeutscherRaum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 II AutomatischesErzeugenvonTaktfahrpla¨nen 45 4 TheoretischeGrundlagen 47 4.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 Charakteristikanicht-periodischerEreignisse . . . . . . . . . . . . . . . . . . . . 48 4.2.1 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.2 MathematischeProblemformulierung. . . . . . . . . . . . . . . . . . . . . 51 4.2.3 Zula¨ssigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 PeriodischeEreignisse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.1 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.2 MathematischeProblemformulierung. . . . . . . . . . . . . . . . . . . . . 57 4.3.3 Zula¨ssigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4 PeriodischesEreignisnetzwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.1 VereinbarungenimModell. . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.2 TechnikenzurProblemreduktion . . . . . . . . . . . . . . . . . . . . . . . 68 5 PraktischeUmsetzung 71 5.1 U¨berblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 ErstellungdesPESP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.3 PESP-Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4 LokaleKonfliktauflo¨sung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.4.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.4.2 BetrieblicheLo¨sungsmo¨glichkeiten . . . . . . . . . . . . . . . . . . . . . . 80 5.4.3 Lo¨sungdurchRelaxationderoberenSchranke . . . . . . . . . . . . . . . 83 5.5 Verkehrsbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.6 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 III MaximierungvongetaktetenSystemtrassen 93 6 MaximalstrommitdynamischerKapazita¨tsallokation 95 6.1 Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.1.1 Einfu¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.1.2 Gu¨terflussnetzwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.1.3 Modellbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.1.4 Min-CutMax-FlowTheorem. . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.1.5 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.2 PraktischeUmsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2.2 Musterzugatome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.2.3 VerwendeteNetzwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.2.4 Flowmaster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.3 Tradeoff:PVvs.GV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.3.1 MaximaleStreckenkapazita¨t . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3.2 Bu¨ndelungseffekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6.3.3 Angebotsqualita¨t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.3.4 SymmetrischerFahrplan. . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.4 ZusammenfassungundAuswertung . . . . . . . . . . . . . . . . . . . . . . . . . 121