 |
|
||||||||||
Algorithmic decision support for train scheduling in a large and highly utilised railway network
IFOR Events
Seminar:
'Optimization & Applications'
(see information & program)
Feb 20 - May 28, 2012
IFOR Mitteilungen
This booklet informs about ongoing projects and future events at the IFOR and appears once at the end of the year.
| Author | Gabrio Caimi |
| Abstract |
This thesis addresses the general problem of constructing train schedules, in particular for large and highly utilised railway networks. Commercial requirements for the timetable are assumed to be given, and the task is to provide detailed conflict-free track paths for each train that fulfil these requirements. In the thesis, a comprehensive approach from the commercial description of intended train services to a conflict-free detailed schedule for a whole day is developed. The methodology follows a divide-and-conquer strategy based on three description levels: the service intention, the macroscopic timetable, and the microscopic schedule. The levels are interfaced in such a way that planners have the possibility of intervening into the specifications on every level, and enabling a feedback loops for testing different alternative scenarios. Many models and algorithms for train scheduling have already been proposed in the literature, some of them with successful application in practice. However, they are either designed for large-scale problems, considering a simplified topology and safety system, or are detailed approaches, yet applicable only to a restricted area. This thesis combines both approaches for finding detailed schedules for large networks, partially relying known models and algorithms from the literature, adapted or extended, and partially developing totally new ideas and methods. The starting point of the approach is the construction of an appropriate structure for describing the intended train services, including periodicity information. This partial periodic Service Intention (ppSI) contains the commercial offer that a railway company would like to tender to the customers during a day. The purpose of the ppSI is to have a formal framework in which potential commercial offers can be developed and described systematically. An important property of modern railway timetables is their periodic pattern, so that they are easy for the customers to memorise. In addition to this regularity, the introduction of irregular train services is necessary to cope with varying demand over the day. The developed ppSI can describe commercial railway offers with partial periodic structure in a compact form and can exploit these effectively in the train scheduling process. The basic idea to handle the partial periodicity of the service intention is an equivalent projection onto a single period time, resulting in an augmented periodic problem. This augmented periodic timetabling problem is then solved first globally on an aggregated topology with a simplified safety model (macroscopic level), and subsequently, locally refined by considering more details of the railway infrastructure and train dynamics (microscopic level). Finally, the generated periodic conflict-free train schedule is rolled out over the complete day to create a production plan that fulfils all requirements that were initially specified in the service intention. The macroscopic level focuses on global interdependencies over the entire network for generating the most important properties of the timetable and thus has to avoid dealing with large amounts of detailed information that is only locally relevant. According to the simplified topology model, safety constraints and train dynamics are also simplified. A well known model for this description level is the Periodic Event Scheduling Problem (PESP). In this thesis, an extension called Flexible Periodic Event Scheduling Problem (FPESP) is introduced and applied, allowing for time slots for each event instead of fixed times. Moreover, an extension of the FPESP model is proposed, the Flexbox model, which is a further generalisation of the FPESP that allows to make use of natural dependencies among events in the service intention. The resulting (flexible) macroscopic timetable is then used as input for the microscopic level. The existence of an operable production plan for a given draft timetable has to be checked on the microscopic level by taking into account detailed information that is important for ensuring the schedule to be conflict-free, but which are not relevant for the global structure of the timetable and have therefore been neglected on the macroscopic level. The safety model on the microscopic level follows the way the interlocking system works. It computes the blocking times on each infrastructure element based on the signalling system and ensures that these blocking time intervals do not overlap. Moreover, the computed track paths must specify a speed profile that the train driver can follow, given a reasonable tolerance band. As the microscopic scheduling problem might become infeasible, the event time slots of the FPESP solution give more freedom, which is particularly crucial in bottleneck regions with dense traffic, where the solution on the macroscopic level with fixed times is often too restrictive. The requested level of detail, together with dense traffic, leads to a enormous problem size. Therefore, a network separation approach is applied to divide the railway network into zones of manageable size by taking account of the network properties, distinguishing condensation and compensation zones. Condensation zones are usually situated near main stations, where the track topology is complex and many different routes exist. As such an area is expected to have a high traffic density, it is also a capacity bottleneck and trains are required to travel through with maximum allowed speed and thus without time reserves. Collisions are avoided by exploiting the various routing possibilities in the station area. Conversely, a compensation zone connects two or more condensation zones and consists of a simpler topology and less traffic density. Here, time reserves should be introduced to improve timetable stability. The choice of an appropriate speed profile is the most important degree of freedom to exploit in these compensation zones. For both zones, a new model called Resource Tree Conflict Graph (RTCG) is developed for solving the microscopic scheduling problem. In this model, a set of scheduling alternatives for each train is computed first and stored in a compact way using a tree structure. In condensation zones, these alternatives are computed by looking at all routes through the topology as well as a discrete set of starting times for each train. In compensation zones, a reasonable set of alternative speed profiles for the few different routes is computed. Afterwards, constraints are derived that preclude conflicts between the alternatives on the involved resources. Based on a graph model, a resource-constrained integer multicommodity flow problem is formulated as an integer linear program. The model has considerably fewer and stronger constraints compared to previous formulations based on stable sets in conflict graphs, which leads to a much stronger LP relaxation and hence much shorter computation times. The RTCG model enables therefore large problems to be solved quickly. In the case of lack of feasibility in a zone on the microscopic level, a feedback strategy is applied to generate another macroscopic schedule according to the information obtained from the microscopic level. The proposed multi-level approach is validated through some real-world test cases from Switzerland. Computational results are presented for all steps of the timetable generation process, and are compared with previous methods for evaluating their improvements. |
| Download |
pdf This thesis (ISBN: 978-3-8322-8639-2) is also published with Shaker Verlag. |
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
