Refine
Year of publication
- 2011 (7) (remove)
Document Type
- ZIB-Report (4)
- Article (3)
Language
- English (7)
Is part of the Bibliography
- no (7)
Keywords
- Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching (1)
- binpacking with side constraints (1)
- integer programming (1)
- multiple knapsack problem with color constraints (1)
- railway capacity (1)
- railway models (1)
- railway models, railway capacity, track allocation framework (1)
- set partitioning (1)
- steel mill slab design problem (1)
- track allocation framework (1)
Institute
Today the railway timetabling process and the track allocation
is one of the most challenging problems to solve by a railway company.
Especially due to the deregulation of the transport market in the recent years several
suppliers of railway traffic have entered the market in Europe. This leads to more
potential conflicts between trains caused by an increasing demand of train paths.
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 size of the problem instances.
In order to make best use of the infrastructure and to ensure economic operation,
efficient planning of the railway operation is indispensable.
Mathematical optimization models and algorithms can help
to automatize and tackle these challenges.
Our contribution in this paper is to present a renewed planning process
due to the liberalization in Europe and an associated concept for track allocation, that consists
of three important parts, simulation, aggregation, and optimization.
Furthermore, we present results of our general framework for real world data.
We propose a model for the integrated optimization of vehicle
rotations and vehicle compositions in long distance railway passenger
transport. The main contribution of the paper is a hypergraph model
that is able to handle the challenging technical requirements as
well as very general stipulations with respect to the ``regularity''
of a schedule. The hypergraph model directly generalizes network
flow models, replacing arcs with hyperarcs. Although NP-hard in
general, the model is computationally well-behaved in practice. High
quality solutions can be produced in reasonable time using high
performance Integer Programming techniques, in particular, column
generation and rapid branching. We show that, in this way,
large-scale real world instances of our cooperation partner DB
Fernverkehr can be solved.
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and a general framework to support the integration of simulation and optimization for railway capacity allocation.
Today the railway timetabling process and the track allocation
is one of the most challenging problems to solve by a railway infrastructure provider.
Especially due to the deregulation of the transport market in the recent years several
suppliers of railway traffic have entered the market. This leads to an increase of slot requests
and then it is natural that conflicts occur among them.
Furthermore, railway infrastructure networks consist of very expensive assets, even more
they are rigid due to the long-term upgrade process.
In order to make best use of these valuable infrastructure and to ensure economic operation,
efficient planning of the railway operation is indispensable.
Mathematical optimization models and algorithmic methodology can help
to automatize and tackle these challenges.
Our contribution in this paper is to present a renewed planning process
due to the liberalization in Europe and a general framework to
support the integration of simulation and optimization for
railway capacity allocation.