Refine
Year of publication
Document Type
- ZIB-Report (52)
- In Proceedings (38)
- Article (22)
- Book chapter (3)
- Book (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
- Other (1)
Language
- English (119)
Keywords
- column generation (4)
- integer programming (4)
- network aggregation (4)
- rapid branching (4)
- Railway Track Allocation (3)
- railway track allocation (3)
- Column Generation (2)
- Fahrplanung (2)
- Netzwerkaggregation (2)
- Optimization (2)
Institute
Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.
We present a heuristic based on linear programming (LP) for the
integrated tour and crew roster planning of toll enforcement inspectors. Their
task is to enforce the proper paying of a distance-based toll on German motorways. This leads to an integrated tour planning and duty rostering problem; it
is called Toll Enforcement Problem (TEP). We tackle the TEP by a standard
multi-commodity flow model with some extensions in order to incorporate the
control tours.
The heuristic consists of two variants. The first, called Price & Branch, is
a column generation approach to solve the model’s LP relaxation by pricing
tour and roster arc variables. Then, we compute an integer feasible solution
by restricting to all variables that were priced. The second is a coarse-to-fine approach. Its basic idea is projecting variables to an aggregated variable
space, which is much smaller. The aim is to spend as much algorithmic effort
in this coarse model as possible. For both heuristic procedures we will show
that feasible solutions of high quality can be computed even for large scale industrial instances.
We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.
We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.
We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
This paper provides a highly integrated solution approach for rolling stock
planning problems in the context of intercity passenger traffic. The main
contributions are a generic hypergraph based mixed integer programming
model and an integrated algorithm for the considered rolling stock rotation
planning problem. The new developed approach is able to handle a very large
set of industrial railway requirements, such as vehicle composition,
maintenance constraints, infrastructure capacity, and regularity aspects.
By the integration of this large bundle of technical railway aspects, we show
that our approach has the power to produce implementable rolling stock
rotations for our industrial cooperation partner DB Fernverkehr.
This is the first time that the rolling stock rotations at DB Fernverkehr
could be optimized by an automated system utilizing advanced mathematical
programming techniques.
We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.
This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the
optimal allocation of the available railway track capacity - the track allocation problem.
This track allocation problem is a major challenge for a railway company, independent of
whether a free market, a private monopoly, or a public monopoly is given.
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. Mathematical models and optimization
techniques can result in huge gains for both railway customers and operators, e.g.,
in terms of cost reductions or service quality improvements.
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic
solution methods for large scale instances. This allows us to produce for the first time reliable
solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
The opening chapter gives a comprehensive overview on railway planning problems.
This provides insights into the regulatory and technical framework,
it discusses the interaction of several planning steps, and identifies optimization potentials in
railway transportation. The remainder of the thesis is comprised of two major parts.
The first part is concerned with modeling railway systems to allow for resource and capacity analysis.
Railway capacity has basically two dimensions, a space dimension which are the physical
infrastructure elements as well as a time dimension that refers to the train movements, i.e.,
occupation or blocking times, on the physical infrastructure. Railway safety systems operate
on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through.
Two trains reserving the same block of the infrastructure within the same point in time is called block conflict.
Therefore, models for railway capacity involve the definition
and calculation of reasonable running and associated reservation and
blocking times to allow for a conflict free allocation.
In the second and main part of the thesis, the optimal track
allocation problem for macroscopic models of the railway system is considered.
The literature for related problems is surveyed.
A graph-theoretic model for the track allocation problem is
developed. In that model optimal track allocations correspond to
conflict-free paths in special time-expanded graphs.
Furthermore, we made considerable progress on solving track allocation problems by two
main features - a novel modeling approach for the macroscopic track
allocation problem and algorithmic improvements based on the
utilization of the bundle method.
Finally, we go back to practice and present in the last chapter several case
studies using the tools netcast and tsopt.
We provide a computational comparison of
our new models and standard packing models used in the literature.
Our computational experience indicates that our approach, i.e.,
``configuration models'', outperforms other models. Moreover, the rapid branching
heuristic and the bundle method enable us to produce high quality solutions for very large scale
instances, which has not been possible before.
In addition, we present results for a theoretical and rather visionary auction framework
for track allocation. We discuss several auction design questions and analyze experiments of
various auction simulations.
The highlights are results for the Simplon corridor in Switzerland.
We optimized the train traffic through this tunnel using our models and
software tools.
To the best knowledge of the author and confirmed by several railway
practitioners this was the first time that fully automatically produced
track allocations on a macroscopic scale fulfill the requirements
of the originating microscopic model, withstand the evaluation in the
microscopic simulation tool OpenTrack, and exploit the infrastructure capacity.
This documents the success of our approach in practice and the usefulness
and applicability of mathematical optimization to railway track 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.