Cyclic Railway Timetable Optimization

Door de nog altijd toenemende mobiliteit, de privatisering van de Nederlandse Spoor- wegen in 1995, en de vertragingen en punctualiteitsproblemen op het spoor, zijn de spoorwegen en hun dienstregelingen de laatste jaren een veelbesproken onderwerp ge- weest in Nederland. De verwachting is dat het spoor mede een antwoord kan bieden op voorspelde verdere groei van de mobiliteit. Tegen deze achtergrond bestudeert dit proefschrift wiskundige modellen en oplossingsmethoden voor het ontwikkelen van cyclische dienstregelingen van hoge kwaliteit. De Nederlandse dienstregeling, waar elk uur in principe identiek is, is een voorbeeld van zo'n cyclische dienstregeling. Hoofdstuk 1 van het proefschrift betoogt dat het snel kunnen ontwerpen van dienstregelingen van hoge kwaliteit van groot belang is zowel voor infrastructuurbe- heerders, zoals Railned, als voor vervoerders, zoals NS Reizigers. Een van de taken van Railned is het adviseren van de Nederlandse overheid over investeringen in nieu- we spoorweg infrastructuur. Dergelijke grote infrastructuur investeringen moeten een extra vervoerscapaciteit over een lange tijdshorizon bieden. Railned evalueert daartoe een scala aan infrastructuur-scenario's, door voor elk scenario verschillende dienstregelingen te ontwerpen. Deze dienstregelingen worden vergeleken aan de hand van diverse criteria, zoals vervoersaanbod en robuustheid. Met de invoering van con- currentie op het Nederlandse spoor heeft Railned daarnaast de taak gekregen om uit de dienstregelingsvoorstellen van de diverse vervoerders een gezamenlijke dienstre- geling samen te stellen. Deze gezamenlijk dienstregeling moet het maatschappelijke nut maximaliseren, door bijvoorbeeld korte reistijden te bieden, of door het aantal verwachte vertragingen zoveel mogelijk te beperken. Wat betreft de vervoerder NS Reizigers speelt het snel kunnen ontwerpen van dienstregelingen van hoge kwaliteit een rol bij het uitvoeren van tactische en stra- tegische studies. Tactische studies onderzoeken de haalbaarheid van wijzigingen in de huidige dienstregeling, en strategische studies richten zich op het verkennen van nieuwe dienstregelingsconcepten voor de toekomst. Hoe sneller dergelijke dienstre- gelingsstudies uitgevoerd kunnen worden, des te sneller en beter kan een vervoerder inspelen op veranderingen in de vervoersmarkt. Daarnaast biedt het grote voorde- len als diverse dienstregelingscriteria, zoals kosten of de tevredenheid van passagiers, gekwantificeerd en tegen elkaar afgewogen kunnen worden. Wiskundige modellen en oplossingsmethoden om dienstregelingen te optimaliseren bieden daarom een waar- devolle ondersteuning bij de dienstregelingsplanning van infrastructuurbeheerders en vervoerders. Hoofdstuk 2 van het proefschrift gaat dieper in op de planning van dienstregelin- gen. Bij het ontwerpen van een dienstregeling moeten de diverse afhankelijkheden met andere planningen, zoals de lijnvoering en de personeelsplanning, in acht wor- den genomen, en vice versa. Verder beschrijft het hoofdstuk hoe de dienstregeling door Railned gebruikt wordt als een instrument om de capaciteit van toekomstige infrastructuur uitbreidingen te evalueren. Nadat de sociale en organisatorische achtergrond van het dienstregelingsontwerp uitvoerig behandeld zijn, beschrijft hoofdstuk 3 een geheeltallig programmeringsmo- del voor het optimaliseren van dienstregelingen, genaamd het Cyclic Railway Ti- metabling Problem (CRTP). Het CRTP modelleert een dienstregeling aan de hand van aankomsttijden en vertrektijden van treinen op de diverse knooppunten in het spoorwegnet. Door uitvoerige voorbeeld-restricties wordt duidelijk gemaakt hoe de diverse voorwaarden waaraan een dienstregeling moet voldoen, zoals aansluitingen en veiligheidseisen, kunnen worden gemodelleerd. Het hoofdstuk beschrijft verder li- neaire doelstellingsfuncties die gericht zijn op het minimaliseren van de reistijden, het maximaliseren van de robuustheid van de dienstregeling, en het minimaliseren van de mate waarin de opgelegde eisen moeten worden geschonden, indien deze onhaal- baar blijken te zijn. Ook wordt het benaderen van een kwadratische variant van deze doelstellingsfuncties behandeld. Het CRTP heeft een compacte graaf representatie, en de speciale structuur van deze graaf wordt ook uitvoerig besproken. Hoofdstukken 4 en 5 gaan vervolgens in op de wiskundige aspecten van het CRTP. Hoofdstuk 4 beschrijft het Periodic Event Scheduling Problem (PESP), een bestaand model uit de literatuur dat het CRTP veralgemeniseerd. De wiskundige formulering van het PESP is gebaseerd op de tijdstippen waarop gebeurtenissen plaatsvinden, en op periodieke restricties die het tijdsverschil tussen paren van gebeurtenissen tot een gegeven tijdvenster beperken. De periodiciteit van de restricties wordt gemo- delleerd door geheeltallige variabelen. Ook het PESP heeft een graaf representatie, en aan de hand van deze representatie wordt het verband tussen het PESP en het klassieke kortste pad probleem verduidelijkt. Verder beschrijft hoofdstuk 4 enkele eigenschappen van het PESP, waaruit een nuttig resultaat voor het cyclisch ordenen van gebeurtenissen wordt afgeleid. Tenslotte wordt een kort overzicht van aan het PESP gerelateerde literatuur gepresenteerd. Hoofdstuk 5 generaliseert het bekende concept van tensions in een graaf voor de periodieke situatie. Gebaseerd op deze periodieke tensions wordt het PESP getrans- formeerd naar de zogenaamde Cycle Periodicity Formulation (CPF). De CPF maakt gebruik van procestijden, en vereist dat de procestijden binnen elke cycle in de graaf periodiek zijn. Deze periodiciteit binnen een cycle wordt gemodelleerd door een ge- heeltallige variabele. In principe moet de periodiciteit binnen elke cycle in de graaf afgedwongen worden, maar het proefschrift toont aan dat het volstaat om de cycles te beschouwen in een geheeltallige basis van de cycle ruimte van de graaf. Verder toont een voorbeeld aan dat een niet-geheeltallige cycle basis er toe kan leiden dat het model een foutieve dienstregeling levert. Aan de hand van het cyclisch ordenings- resultaat uit hoofdstuk 4 wordt daarna de relatie aangetoond tussen bepaalde cycles in de graaf, en de volgorde waarin treinen over het spoor rijden. Deze trein-volgordes leiden vervolgens tot een klasse van sneden voor de CPF, die tot de grotere klasse van reeds bekende cycle sneden blijken te behoren. Het resterende deel van hoofdstuk 5 is gewijd aan verschillende aspecten van cycle bases. Zo wordt aangetoond dat de bekende klassen van strikt fundamentele en al- gemeen fundamentele cycle basen geheeltallig zijn, hetgeen betekent dat ze gebruikt kunnen worden om de CPF te formuleren. Vervolgens betoogt het proefschrift dat het voordelig is om de CPF met een smalle cycle basis te formuleren, en dat al- goritmen voor het zogenaamde minimum cycle basis probleem een benadering van zulke smalle cycle bases berekenen. Uitgaande van de speciale structuur van de graaf representatie van het CRTP, worden verder twee gewichtsfuncties voor het bepalen van opspannende bomen voorgesteld, die strikt fundamentele cycle bases met een smalle breedte leveren. Tenslotte beschrijft het hoofdstuk hoe de breedte van een strikt fundamentele cycle basis verder verkleind kan worden door de bijbehorende algemeen fundamentele cycle basis te berekenen. Hoofdstuk 6 is gewijd aan diverse uitbreidingen van het CRTP. Als eerste wordt uitgelegd hoe variabele rijtijden van treinen in het model kunnen worden opgeno- men. Vervolgens wordt de modellering van flexibele aansluitingen beschreven, het- geen inhoudt dat twee verzamelingen van treinen een of meerdere aansluitingen op elkaar moeten bieden. De derde uitbreiding toont hoe de capaciteiten van stati- ons opgenomen kunnen worden in het CRTP, en de vierde uitbreiding beschrijft een alternatieve doelstellingsfunctie die gericht is op het minimaliseren van het aantal trein-composities dat nodig is om de dienstregeling uit te voeren. Tenslotte wordt in hoofdstuk 6 een cycle fixatie heuristiek beschreven. Deze heuristiek is ge??nspireerd door de werkwijze van praktische planners, die vaak eerst de belangrijkste treinen plannen, de dienstregeling voor deze treinen vastprikken. Vervolgens worden iteratief andere klassen van treinen aan de dienstregeling toegevoegd. In hoofdstuk 7 worden de idee??en uit de voorgaande hoofdstukken getest op een drietal testproblemen. Deze tests tonen aan dat het van essentieel belang is om een preprocessing stap uit te voeren teneinde de grootte van de instanties te reduceren. Ook blijkt het te lonen om in een tweede preprocessing stap de breedte van de tijdvensters in de periodieke restricties te verkleinen. Vervolgens wordt duidelijk dat de PESP variant van het CRTP model vrij lange rekentijden vergt, en dat de CPF duidelijk beter presteert bij het optimaliseren van cyclische spoorwegdienstregelingen. Om deze reden is het overige deel van hoofdstuk 7 gewijd aan verdere tests van de CPF. Een tweede factor die van belang is om de CPF snel op te kunnen lossen, blijkt het soort cycle basis te zijn waarmee het model geformuleerd wordt. De tests tonen aan dat de voorgestelde gewichtsfuncties voor opspannende bomen over het algemeen de beste resultaten opleveren voor de reistijd-doelstellingsfunctie. Het blijkt veel meer tijd te kosten om een robuuste dienstregeling te berekenen, terwijl een dienstregeling met een minimaal benodigd aantal trein-composities vrij snel berekend kan worden. Voor instanties met een onhaalbaar eisenpakket blijkt de voorgestelde doelstellings- functie een effectief middel te zijn om een indicatie te verkrijgen van de benodigde aanpassingen. Het toevoegen van sneden aan de model formulering reduceert de rekentijd in de meeste gevallen. Toch voldoen deze technieken niet om binnen een redelijke tijd goede dienstregelingen te berekenen voor het grootste testprobleem. Echter, met de cycle fixatie heuristiek kunnen ook voor dit grootste probleem binnen een redelijke rekentijd goede dienstregelingen worden berekend. Tenslotte conclu- deert het hoofdstuk dat de kwaliteit van de berekende dienstregelingen zodanig is, dat de extra rekentijd die een optimalisatie vergt gerechtvaardigd is. Hoofdstuk 8 vat tenslotte de belangrijkste resultaten van het proefschrift samen, en beantwoordt de onderzoeksvragen die in hoofdstuk 1 zijn geformuleerd. Daar- naast worden kort de beperkingen van het proefschrift beschreven, en worden enkele suggesties voor vervolgonderzoek gedaan.

• View at Worldcat

Free Full Text ( Final Version , 3mb )