nach oben

2007 | Buch

Kapitel lesen Erstes Kapitel lesen

Algorithmic Methods for Railway Optimization

International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, Norway, September 16-17, 2004, Revised Selected Papers

herausgegeben von: Frank Geraets, Leo Kroon, Anita Schoebel, Dorothea Wagner, Christos D. Zaroliagis

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Inhaltsverzeichnis

Frontmatter

State of the Art

Frontmatter

The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables — and Beyond

Abstract

In the planning process of railway companies, we propose to integrate important decisions of network planning, line planning, and vehicle scheduling into the task of periodic timetabling. From such an integration, we expect to achieve an additional potential for optimization.

Models for periodic timetabling are commonly based on the Periodic Event Scheduling Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended by only two features, namely a linear objective function and a symmetry requirement. These extensions of the PESP do not really impose new types of constraints. Indeed, practitioners have already required them even when only planning timetables autonomously without interaction with other planning steps. Even more important, we only suggest extensions that can be formulated by mixed integer linear programs.

Moreover, in a selfcontained presentation we summarize the traditional PESP modeling capabilities for railway timetabling. For the first time, also special practical requirements are considered that we proove not being expressible in terms of the PESP.

Christian Liebchen, Rolf H. Möhring

Cyclic Railway Timetabling: A Stochastic Optimization Approach

Abstract

Real-time railway operations are subject to stochastic disturbances. However, a railway timetable is a deterministic plan. Thus a timetable should be designed in such a way that it can absorb the stochastic disturbances as well as possible. To that end, a timetable contains buffer times between trains and supplements in running times and dwell times. This paper first describes a stochastic optimization model that can be used to find an optimal allocation of the running time supplements of a single train on a number of consecutive trips along the same line. The aim of this model is to minimize the average delay of the train. The model is then extended such that it can be used to improve a given cyclic timetable for a number of trains on a common railway infrastructure. Computational results show that the average delay of the trains can be reduced substantially by applying relatively small modifications to the timetable. In particular, allocating the running time supplements in a different way than what is usual in practice can be useful.

Leo G. Kroon, Rommert Dekker, Michiel J. C. M. Vromans

Timetable Information: Models and Algorithms

Abstract

We give an overview of models and efficient algorithms for optimally solving timetable information problems like “given a departure and an arrival station as well as a departure time, which is the connection that arrives as early as possible at the arrival station?” Two main approaches that transform the problems into shortest path problems are reviewed, including issues like the modeling of realistic details (e.g., train transfers) and further optimization criteria (e.g., the number of transfers). An important topic is also multi-criteria optimization, where in general all attractive connections with respect to several criteria shall be determined. Finally, we discuss the performance of the described algorithms, which is crucial for their application in a real system.

Matthias Müller-Hannemann, Frank Schulz, Dorothea Wagner, Christos Zaroliagis

Estimates on Rolling Stock and Crew in DSB S-tog Based on Timetables

Abstract

Reliable evaluation of the efficiency of timetables is very important for transportation companies today, because of increased competition on the market in Europe. Two major contributions to the cost of a timetable are the rolling stock (RS) and crew. Especially when the service level is increased, it is necessary to evaluate the need for new RS and hiring of crew in advance. In this paper we describe two models, one for evaluating the amount of RS, and one for evaluating the crew needed for a given timetable. The decision makers use the models as tools to choose between different timetables, to dimension the workforce, and to decide on the optimal fleet composition before buying new RS.

Michael Folkmann, Julie Jespersen, Morten N. Nielsen

A Capacity Test for Shunting Movements

Abstract

One of the bottlenecks in the logistic planning process at Netherlands Railways is the capacity of the infrastructure at the larger railway stations. To provide passenger trains with the right composition of rolling stock, many shunting movements between platform tracks and shunting areas are necessary, especially just before and after the peak hours. These shunting movements use the same infrastructure as the timetabled passenger and cargo trains.

In this paper we describe a capacity test that has been developed to test at any moment during the planning process, whether the capacity of the infrastructure between the platform tracks and the shunting areas is sufficient for facilitating all the shunting movements that have to be planned in between the already timetabled train movements. With this test it is not necessary anymore to plan every detail of the shunting movements far before the actual operations.

The capacity test is based on a mixed integer programming model. The running time of the Branch-and-Bound algorithm of CPLEX 9.0 is sufficiently small, as was observed in computational experiments related to three stations in the Netherlands.

John van den Broek, Leo Kroon

Railway Crew Pairing Optimization

Abstract

The use of automatic crew planning tools within the railway industry is now becoming wide-spread, thanks to new algorithm development and faster computers. An example is the large European railway Deutsche Bahn, which is using a commercial crew planning system developed by Jeppesen (formerly Carmen Systems). This paper focuses on the crew pairing problem that arises at major railways. Even though it is similar to the well-studied airline crew pairing problem, the size and complexity of the railway operation necessitates tailored optimization techniques. We show that a column generation approach to the pairing problem, which combines resource constraints, k-shortest path enumeration and label merging techniques, is able to heuristically solve a 7,000 leg pairing problem in less than a day.

Lennart Bengtsson, Rastislav Galia, Tomas Gustafsson, Curt Hjorring, Niklas Kohl

Integer Programming Approaches for Solving the Delay Management Problem

Abstract

The delay management problem deals with reactions in case of delays in public transportation. More specifically, the aim is to decide if connecting vehicles should wait for delayed feeder vehicles or if it is better to depart on time. As objective we consider the convenience over all customers, expressed as the average delay of a customer when arriving at his or her destination.

We present path-based and activity-based integer programming models for the delay management problem and show the equivalence of these formulations. Based on these, we present a simplification of the (cubic) activity-based model which results in an integer linear program. We identify cases in which this linearization is correct, namely if the so-called never-meet property holds. We analyze this property using real-world railway data. Finally, we show how to find an optimal solution in linear time if the never-meet property holds.

Anita Schöbel

Decision Support Tools for Customer-Oriented Dispatching

Abstract

Unavoidable disturbances induce the necessity of operations control and dispatching tasks in the timetable-driven rail traffic. Therefore, dispatching becomes one of the most relevant challenges for the economic success, since it directly affects the timeliness of passengers, which is a core indicator of customer satisfaction. Thus, the integration of passenger preferences into dispatching strategies is a reasonable extension of conventional dispatching algorithms. In this paper we discuss decision support tools to be used by dispatchers in order to achieve customer orientation. The tools are based on an agent-based simulation system modelling the complete German railway network with about 30000 trains and millions of passengers per day. We report tests of various dispatching strategies considering passenger information and aiming to reduce passenger waiting times. We show that even simple heuristics produce better results than the rule based dispatching strategies currently in use.

Claus Biederbick, Leena Suhl

Proceedings of ATMOS 2004

Frontmatter

An Integrated Methodology for the Rapid Transit Network Design Problem

Abstract

The Rapid Transit System Network Design Problem consists of two intertwined location problems: the determination of alignments and that of the stations. The underlying space, a network or a region of the plane, mainly depends on the place in which the system is being constructed, at grade or elevated, or underground, respectively. For solving the problem some relevant criteria, among them cost and future utilisation, are applied. Urban planners and engineering consulting usually select a small number of corridors to be combined and then analysed. The way of selecting and comparing these alternatives is performed by the application of the four-stage transit planning model. Due to the complexity of the overall problem, during last ten years some efforts have been dedicated to modelling some aspects as optimisation problems and to provide Operations Research methods for solving them. This approach leads to the consideration of a higher number of candidates than that of the classic corridor analysis. The main aim of this paper is to integrate the steps of the transit planning model (trip attraction and generation, trip distribution, mode choice and traffic equilibrium) into an optimisation process.

Gilbert Laporte, Ángel Marín, Juan A. Mesa, Francisco A. Ortega

A Simulation Approach of Fare Integration in Regional Transit Services

Abstract

The paper presents a general procedure, supported by a system of simulation models, to estimate the effects due to the implementation of an integrated fare system in regional transit services. The effects on users (demand level variations) and on transit companies (management revenues) are considered. In particular, the demand is assumed to be elastic with respect to the fare at the modal and path choice dimensions. The general procedure is applied to the transit system of an Italian regional area.

Domenico Gattuso, Giuseppe Musolino

Intelligent Train Scheduling on a High-Loaded Railway Network

Abstract

We present an interactive application to assist planners in adding new trains on a complex railway network. It includes many trains with different characteristics, whose timetables cannot be modified because they are already in circulation. The application builds the timetable for new trains linking the available time slots to trains to be scheduled. A very flexible interface allows the user to specify the parameters of the problem. The resulting problem is formulated as a CSP and efficiently solved. The solving method carries out the search assigning values to variables in a given order verifying the satisfaction of constraints where these are involved. When a constraint is not satisfied, a guided backtracking is done. Finally, the resulting timetable is delivered to the user who can interact with it, guaranteeing the traffic constraint satisfaction.

Antonio Lova, Pilar Tormos, Federico Barber, Laura Ingolotti, Miguel A. Salido, Monsterrat Abril

Platform Assignment

Abstract

We consider a station in which several trains might stop at the same platform at the same time. The trains might enter and leave the station to both sides, but the arrival and departure times and directions are fixed according to a given time table. The problem is to assign platforms to the trains such that they can enter and leave the station in time without being blocked by any other train. We consider some variation of the problem on linear time tables as well as on cyclic time tables and show how to solve them as a graph coloring problem on special graph classes. One of these classes are the so called circular arc containment graphs for which we give an \(\mathcal O(n \log n)\) coloring algorithm.

Sabine Cornelsen, Gabriele Di Stefano

Finding All Attractive Train Connections by Multi-criteria Pareto Search

Abstract

We consider efficient algorithms for timetable information in public transportation systems under multiple objectives like, for example, travel time, ticket costs, and number of interchanges between different means of transport. In this paper we focus on a fully realistic scenario in public railroad transport as it appears in practice while most previous work studied only simplified models.

Algorithmically this leads to multi-criteria shortest path problems in very large graphs. With several objectives the challenge is to find all connections which are potentially attractive for customers. To meet this informal goal we introduce the notion of relaxed Pareto dominance. Another difficulty arises from the fact that due to the complicated fare regulations even the single-criteria optimization problem of finding cheapest connections is intractable. Therefore, we have to work with fare estimations during the search for good connections.

In a cooperation with Deutsche Bahn Systems we realized this scenario in a prototypal implementation called PARETO based on a time-expanded graph model. Computational experiments with our PARETO server demonstrate that the current central server of Deutsche Bahn AG often fails to give optimal recommendations for different user groups. In contrast, an important feature of the PARETO server is its ability to provide many attractive alternatives.

Matthias Müller-Hannemann, Mathias Schnee

The Railway Traveling Salesman Problem

Abstract

We consider the Railway Traveling Salesman Problem (RTSP) in which a salesman using the railway network wishes to visit a certain number of cities to carry out his/her business, starting and ending at the same city, and having as goal to minimize the overall time of the journey. RTSP is an \(\mathcal{NP}\)-hard problem. Although it is related to the Generalized Asymmetric Traveling Salesman Problem, in this paper we follow a direct approach and present a modelling of RTSP as an integer linear program based on the directed graph resulted from the timetable information. Since this graph can be very large, we also show how to reduce its size without sacrificing correctness. Finally, we conduct an experimental study with real-world and synthetic data that demonstrates the superiority of the size reduction approach.

Georgia Hadjicharalambous, Petrica Pop, Evangelia Pyrga, George Tsaggouris, Christos Zaroliagis

Rotation Planning of Locomotive and Carriage Groups with Shared Capacities

Abstract

In a large railway passenger traffic network, a given set of trips or service blocks are to be serviced by equipment consisting of several groups of locomotives/carriages. The allowed groups per service block are predefined as patterns or multisets of locomotives and carriages. A given type of locomotive/carriage may occur with varying numbers in several groups. We search for a cost-minimal assignment of locomotive/carriage groups to rotations taking special restrictions into account, especially, we shall find the optimal mix of groups obeying given capacities on the level of locomotive and carriage units for each type.

Our solution approach is based on a multi-layer (multi-commodity) network flow model where each layer represents a locomotive/carriage group, and the requirement of servicing each trip exactly once is modeled by cover/partitioning constraints. In this paper, we concentrate on railway specific requirements and present special techniques to model and optimize locomotive and carriage groups with shared capacities. These techniques erable us to solve large-scale practical problem instances of German Railways into optimality.

Taïeb Mellouli, Leena Suhl

An Estimate of the Punctuality Benefits of Automatic Operational Train Sequencing

Abstract

In Dutch railway operations, most of the rescheduling decisions in the operational phase, following some disturbance, involve the resequencing of trains. These decisions are being taken using only approximate train information and operational rules. Improvements have been formulated but, since no insight in the potential gain in punctuality exists, lack a convincing business case. In this paper, using only elementary methods, we derive an estimate for this punctuality gain.

Rien Gouweloos, Maarten Bartholomeus

Online Delay Management on a Single Train Line

Abstract

We provide competitive analyses for the online delay management problem on a single train line. The passengers that want to connect to the train line might arrive delayed at the connecting stations, and these delays happen in an online setting. Our objective is to minimize the total passenger delay on the train line.

We relate this problem to the Ski-Rental problem and present a family of 2-competitive online algorithms. Further, we show that no online algorithm for this problem can be better than Golden Ratio competitive, and that no online algorithm can be competitive if the objective accounts only for the optimizable passenger delay.

Michael Gatto, Riko Jacob, Leon Peeters, Peter Widmayer

Backmatter

Titel: Algorithmic Methods for Railway Optimization
herausgegeben von: Frank Geraets
Leo Kroon
Anita Schoebel
Dorothea Wagner
Christos D. Zaroliagis
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-74247-0
Print ISBN: 978-3-540-74245-6
DOI: https://doi.org/10.1007/978-3-540-74247-0

Springer Professional

Inhaltsverzeichnis

Frontmatter

State of the Art

Frontmatter

The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables — and Beyond

Cyclic Railway Timetabling: A Stochastic Optimization Approach

Timetable Information: Models and Algorithms

Estimates on Rolling Stock and Crew in DSB S-tog Based on Timetables

A Capacity Test for Shunting Movements

Railway Crew Pairing Optimization

Integer Programming Approaches for Solving the Delay Management Problem

Decision Support Tools for Customer-Oriented Dispatching

Proceedings of ATMOS 2004

Frontmatter

An Integrated Methodology for the Rapid Transit Network Design Problem

A Simulation Approach of Fare Integration in Regional Transit Services

Intelligent Train Scheduling on a High-Loaded Railway Network

Platform Assignment

Finding All Attractive Train Connections by Multi-criteria Pareto Search

The Railway Traveling Salesman Problem

Rotation Planning of Locomotive and Carriage Groups with Shared Capacities

An Estimate of the Punctuality Benefits of Automatic Operational Train Sequencing

Online Delay Management on a Single Train Line

Backmatter

Premium Partner