Invited Session Mon.1.H 3013

Monday, 10:30 - 12:00 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization in railways I


Chair: Ralf Borndörfer



Monday, 10:30 - 10:55 h, Room: H 3013, Talk 1

Jun Imaizumi
A column generation approach for crew rostering problem in a freight railway company in Japan

Coauthors: Kosuke Hasuike, Susumu Morito, Eiki Shigeta


We consider the Crew Rostering Problem (CRP) in a freight railway company in Japan, "Japan Freight Railway Company'' (JR-F). JR-F belongs to "JR Group'' including six passenger railway companies and operates freight trains on the lines owned by these passenger railway companies. JR-F covers most of main lines of the passenger railway companies and has to manage their depots of the drivers all over Japan. CRP in this paper is to find rosters of a certain depot provided a set of "pairing'', which is a sequence of minimum job units called "trip'', is given for the depot. The pairings are sequenced into rosters satisfying various constraints. The objective function is to minimize the number of drivers for performing the pairings. We formulate this problem into the Set Partitioning Problem and demonstrate an application of the column generation method to it. As the exact approach to column generation sub-problems needs much computation effort, we employ an alternative approach consisting of four steps. We show results of numerical experiments for instances based on the timetable.



Monday, 11:00 - 11:25 h, Room: H 3013, Talk 2

Thomas Schlechte
Recent developments in railway track allocation

Coauthors: Ralf Borndörfer, Steven Harrod


This talk is about mathematical optimization for the efficient use of
railway infrastructure. We address the optimal allocation of the available
railway track capacity. This track allocation problem is a major challenge for any railway company. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances.
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. We present two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements. Finally, we provide computational studies for real world instances, i.e., the Simplon corridor in Switzerland, and various instances from the literature.



Monday, 11:30 - 11:55 h, Room: H 3013, Talk 3

Steffen Weider
A rapid branching method for the vehicle rotation planning problem

Coauthors: Ralf Borndörfer, Markus Reuther, Thomas Schlechte


The Vehicle Rotation Planning Problem is to schedule rail vehicles in order to cover the trips of a given timetable by a cost optimal set of vehicle rotations.
The Problem integrates several facets of railway optimization: train composition, fleet management, maintenance planning, and regularity aspects. We model this problem as a multi-commodity min-cost-flow hypergraph problem and solve it by integer programming based heuristics.
The core of our algorithm is the Rapid Branching method which also was successfully used to solve track allocation problems and integrated vehicle and duty scheduling problems. The Rapid Branching method can be seen as a very fast heuristical traversal of a branch-and-bound search tree.
We also present computational results on very large instances of the vehicle rotation planning problem given by our industrial partner DB Fernverkehr AG, which is the largest intercity railway operator in Germany.


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Order Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.