printlogo
http://www.ethz.ch/
Institut für Verkehrsplanung und Transportsysteme, ETH Zürich
 
print
  

e-citations

 

, Herriegel-Wiedersheim, Sabrina, 2015 >>
Autor(en): Herriegel-Wiedersheim, Sabrina
Titel: Algorithmic decision support for the construction of periodic railway timetables
Kurzbeschreibung: This thesis addresses the problem of solving large railway timetabling problems using algorithmic methods. With the increasing demand for better and more frequent services, for higher capacity utilization and for improved reliability, railway timetabling problems become more and more complex. Algorithmic decision support is one promising way to cope with this increasing complexity, and the continuous progress of operations research methods offers a significant potential for the railway industry. The approach of this thesis concentrates on algorithms for the construction of periodic railway timetables during long- and mid-term planning. As an input, functional requirements and restrictions of the infrastructure have to be described at a model granularity suitable for the given planning stage. The algorithmic approach then creates a periodic timetable with the same model granularity and optimizes the timetable according to a given objective. Compared to a manual timetable construction, the algorithmic approach allows to compare different timetable scenarios in a shorter time. Possible modifications of the infrastructure or the service intention and their influence on the overall timetable can therefore be tested and evaluated more efficiently and also in more detail.
The algorithms studied in this thesis are based on the so called Periodic Event Scheduling Problem (PESP), a mathematical model which proved to be suitable to automate the construction of periodic railway timetables already several times in research and practice. To solve the model there exist different mathematical methods. This thesis summarizes them and shows advantages of a method based on Mixed Integer Linear Programming (MILP). Compared to other solution methods it allows a direct optimization and with this several further advantages concerning a more efficient automation and a better solution quality. However there exists no practical experience of the method for larger timetabling problems and there even can be found the conjecture that the solution method is not suitable for large scale problems.
The algorithms developed in this thesis are based on the so-called Periodic Event Scheduling Problem (PESP), a mathematical model which has become the standard approach for algorithmic construction of periodic railway timetables and has been used successfully already several times in research and practice. Different mathematical methods have been proposed to solve timetabling problems formulated as a PESP. This thesis summarizes the different solution approaches and shows advantages of a method based on Mixed Integer Linear Programming (MILP). Compared to other solution methods, the MILP approach allows a direct optimization, and with this several further advantages concerning a more efficient automation and a better solution quality. However, there exists no practical experience of the method for larger timetabling problems and it has been an open question so far whether and to what extent it is suitable for large-scale problems.
In this thesis this gap is filled by providing the missing experience of applying the MILP solution approach for a set of increasingly large timetabling problems for parts of the Swiss railway network. To profit from the method's advantages also for large-scale problems, an adaptation of the solution method is introduced. It allows to reduce computational complexity considerably, but still ensures good solution quality. To this end, the thesis provides three main contributions:
• Implementation of the defined algorithms including an automated model construction out of real data provided by Swiss Federal Railways (SBB).
• Extension of the models until a limit of computation time for the used algorithms is reached.
• Development of new methods for the acceleration of the given algorithms to solve and optimize also larger models.
To ensure operational feasibility for the given model granularity and a certain degree of timetable quality for our models, the resulting timetables are evaluated by the software OnTime. This way it can be ensured that the level of detail of our models is rich enough to represent realistic timetable scenarios. However, the models in this thesis are not constructed to study and evaluate a concrete timetable scenario but rather to represent different model sizes to study the computational performance of the proposed algorithms. After an evaluation of different parameters for the algorithm and the used MILP solver, the best parameter setting is used to determine a computational limit of the given solution strategy for larger model sizes. Although using strong computer servers and state-of-the-art commercial MILP solvers, this limit can be reached for our largest models.
To accelerate the algorithms, two decomposition methods are proposed and studied. The first one is motivated from optimization theory. The PESP-graph corresponding to a PESP model is split into different subgraphs and used to define independent MILPs. Two iterative methods are introduced to coordinate the subproblems in order to find feasible global solutions of sufficient quality. The decomposition approach is successfully applied to a smaller test model splitting it into two subproblems. However, the generalization of the method for a larger number of subproblems or larger model sizes leads to several difficulties.
2
Publikationsdatum / Empfangsdatum: 2015-01-01
Publikations-Status: Zürich
Publikations-Status: Published
Sprache: English
ETH Dissertationsnummer: 22548
DBID Quelle: FORM-1426250941
DOI: 10.3929/ethz-a-010412035
Nebis System Nummer: 010412035
, Weidmann, Ulrich A., Herriegel-Wiedersheim, Sabrina, Rieder, Markus, 2013 >>
Autor(en): Weidmann, Ulrich A., Herriegel-Wiedersheim, Sabrina, Rieder, Markus
Titel: Concept des transports et de mobilité dans des communes de Clos du Doubs et Soubey
Publiziert in: Schriftenreihe / Institut für Verkehrsplanung und Transportsysteme
Band: 161
Publikationsdatum / Empfangsdatum: 2013-01-01
Publikations-Status: Zürich
Publikations-Status: Accepted
Sprache: French
DBID Quelle: FORM-1361371109
Nebis System Nummer: 005022139
, Herriegel-Wiedersheim, Sabrina, Laumanns, Marco, Nash, Andrew, Weidmann, Ulrich, 2013 >>
Autor(en): Herriegel-Wiedersheim, Sabrina, Laumanns, Marco, Nash, Andrew, Weidmann, Ulrich
Titel: Hierarchical Decomposition Methods for Periodic Railway Timetabling Problems
Kurzbeschreibung: Today many European railway networks are operating near capacity. Developing timetables for these dense and often highly congested networks is becoming increasingly difficult. Several algorithmic approaches for solving timetabling problems have been developed in recent years, but the problem size, computational complexity, and lack of transparent interfaces for planners slow down adoption of these approaches in practice. This research proposed an iterative method based on train hierarchies to solve large periodic timetabling problems. The proposed method added a new group of trains to the schedule in each step of the process while holding trains added in previous steps fixed within a specified time interval. A case study with real-world data was used to analyze the influence of the number of decomposition steps and time interval on computation time and timetable quality. The results showed that setting parameters to a compromise between the extremes of a purely sequential or a purely simultaneous timetable planning approach was very effective at reducing computation time while still providing optimal or close-to-optimal timetables.
Publiziert in: Transportation research record
Band: 2374
Seiten: 73 - 82
ISSN: 0361-1981
Publikationsdatum / Empfangsdatum: 2013-01-01
Publikations-Status: Washington, D.C.
Publikations-Status: Published
Sprache: English
DBID Quelle: FORM-1389014037, WOS-000329561700009
DOI: 10.3141/2374-09
Nebis System Nummer: 000024408

 

 

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2016 ETH Zürich | Impressum | Disclaimer | 15.7.2014
top