Rail transport plays a key role in the mobility of passengers and goods. It is expected to grow the decarbonization of society. In that context, it is important to use the railway network efficiently, and jointly planning trains and network maintenance allows for better use of resources. This master thesis focuses on the integration of regular maintenance slots in a timetable while minimizing the impact on rail traffic and maintenance costs. The problem has been modeled as a mixed-integer linear programming formulation. First, we study the modeling of the interactions between trains, and we focus on the possible conflicts due to maintenance slots. Two approaches are compared: an aggregated one and a detailed one close to maintenance slots. We analyze the computation time and the quality of the solution on a real-life timetable with different maintenance scenarios. The results show while the aggregated approach is useful for finding reasonable slots, the detailed one is necessary to achieve high quality solutions with minimal traffic impact. In the second step, we reduce the computation time by using construction heuristics. We use a greedy algorithm to find realistic maintenance slots combined with a train-fixing heuristic. Our experiments have shown that theses heuristics reduces significantly the computation time (with more than 50% on the considered test instances) for solutions of equivalent quality. Limitations of the model and improvements are discussed. / Järnvägstransporter spelar en nyckelroll för passagerar- och godstransporter. Den väntas öka koldioxidminskningen i samhället. I det sammanhanget är det viktigt att använda järnvägsnätet effektivt och en gemensam planering av tåg och underhåll av nätet gör det möjligt att utnyttja resurserna bättre. Den här masteruppsatsen fokuserar på integrering av regelbundna underhållsfönster i en tidtabell samtidigt som man minimerar effekterna på järnvägstrafiken och underhållskostnaderna. Problemet har modellerats som ett linjärt optimeringsproblem med blandade heltal. Först studerar vi hur interaktioner mellan tåg kan modelleras med fokus på konflikter som uppstår vid underhållsfönster. Två tillvägagångssätt jämförs: ett aggregerat tillvägagångssätt och ett detaljerat tillvägagångssätt nära underhållstidpunkterna. Vi analyserar beräkningstiden och lösningens kvalitet på en verklig tidtabell med olika underhållsscenarier. Resultaten visar att medan det aggregerade tillvägagångssättet är användbart för att hitta rimliga tidsluckor, så är det detaljerade tillvägagångssättet nödvändigt för att hitta lösningar med hög kvalitet och minsta möjliga trafikpåverkan. I det andra steget minskar vi beräkningstiden med hjälp av konstruktionsheuristik. Vi använder en algoritm för att hitta realistiska underhållstidpunkter kombinerat med en fixeringsheuristik för tågen. Våra experiment visar att dessa heuristiker avsevärt minskar beräkningstiden (med mer än 50% för de studerade testfallen) för lösningar av likvärdig kvalitet. Begränsningar av modellen och förbättringar diskuteras.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-325586 |
| Date | January 2023 |
| Creators | Vaillant, Pauline |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2023:45 |
Page generated in 0.0019 seconds