 |
|
||||||||||
Stability of Timetables and Train Routings through Station Regions
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 | Thomas Herrmann |
| Abstract |
During the last few years, railway traffic has increased considerably; moreover, it is expected that railroad transportation will further grow for both, passenger and freight transportation. These developments create needs to optimize both the utilization of the existing infrastructure and the coordination tasks inside the railroad company. Thanks to developments in computer science, optimization techniques, and intelligent resource management, railway schedules with increased frequencies can be generated nowadays. Especially near main stations railway operators expect the capacity bottlenecks of the railway system, since there main train lines are intersecting. Tight timetables, however, are exposed to train delays to a greater extent than less dense schedules. The thesis at hand describes stability measures of timetables and the highly related topic of the search for train routings within station regions. As the quality of service should not suffer when introducing new train services, the question of the stability of a timetable is of crucial interest while designing denser timetables. Unforeseen events may require partial modifications of the plans in real-time and therefore re-scheduling procedures should be already taken into account when designing a new timetable. Moreover, re-scheduling procedures should be as easy to implement as possible. Fundamentally, the timetable's ability to absorb some disturbances trades off against full exploitation of available capacity. With the help of evaluation functions, timetables can be examined regarding their likelihood to fail, their sensitivity against disruptions of the schedule, or their efficiency to recover from deviations. Separating the problem of train routings in exact topologies from the saturation of the available capacity and the generation of a timetable in an aggregated topology results in a two level approach. On the upper level a timetable for an intended train service is generated using an aggregated topology. The task on this level is to develop a timetable whose periodicity is as small as possible in order to use the network to full capacity while respecting safety restrictions and the intention of the train service. On the lower level, exact topologies are used in order to decide feasibility of the previously generated, tentative timetables and to analyze the derived schedules. As this thesis mainly deals with stability of timetables, it is consistently assumed that a timetable for the aggregated topology is available. By examining the routing alternatives, which are tremendously high in station regions, the feasibility problem is modeled as an independent set problem. The node set corresponds to all possible routes of the trains and two nodes are connected by an edge, if their corresponding routes are mutually exclusive. The independent set problem is then solved by applying a fixed point heuristic. The probability that the routes of two different trains are incompatible, can be calculated by assuming certain delay patterns for arriving and departing trains. The previous model is then extended by the introduction of additional edges whose weights are set to the probability that the corresponding routes are incompatible. Stability measures are then expressed as certain properties of the extended graph. Moreover, a stability measure that is independent of any delay distributions is also introduced. In a second step, these stability measure functions are used to state different optimization problems that are then solved by a random restart local search heuristic. In order to test the methodology, the Bern station region has been used. Depending on the applied optimization problem and the underlying delay patterns, the trains are scheduled to travel on different routes through the network. Results show that the tighter the timetable becomes the more important is the design of the railway system and the coordination of suitable track topologies, meaningful train service intentions, the dense schedules, elaborate routings, and actively managed train delays. |
| Download | pdf, ps (zipped) |
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
