Refine
Year of publication
Document Type
- ZIB-Report (50)
- In Proceedings (38)
- Article (22)
- Book chapter (3)
- Book (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
- Other (1)
Language
- English (117)
Is part of the Bibliography
- no (117) (remove)
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
We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
This paper provides a generic formulation for rolling stock planning
problems in the context of intercity passenger traffic. The main contributions
are a graph theoretical model and a Mixed-Integer-Programming
formulation that integrate all main requirements of the considered
Vehicle-Rotation-Planning problem (VRPP). We show that it is
possible to solve this model for real-world instances provided by our
industrial partner DB Fernverkehr AG using modern algorithms and
computers.
This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers.
We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis.
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.
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 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 introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.
We introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
We introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
We consider the following freight train routing problem (FTRP).
Given is a transportation network with fixed routes for passenger
trains and a set of freight trains (requests), each defined by an
origin and destination station pair. The objective is to
calculate a feasible route for each freight train such that the
sum of all expected delays and all running times is minimal.
Previous research concentrated on microscopic train routings for
junctions or inside major stations. Only recently approaches were
developed to tackle larger corridors or even networks. We
investigate the routing problem from a strategic perspective,
calculating the routes in a macroscopic transportation network of
Deutsche Bahn AG. In this context, macroscopic refers to an
aggregation of complex and large real-world structures into fewer
network elements. Moreover, the departure and arrival times of
freight trains are approximated. The problem has a strategic
character since it asks only for a coarse routing through the
network without the precise timings. We provide a mixed-integer
nonlinear programming (MINLP) formulation for the FTRP, which is
a multicommodity flow model on a time-expanded graph with
additional routing constraints. The model’s nonlinearities
originate from an algebraic approximation of the delays of the
trains on the arcs of the network by capacity restraint
functions. The MINLP is reduced to a mixed-integer linear
model (MILP) by piecewise linear approximation. The latter is
solved by a state-of-the art MILP solver for various real-world
test instances.
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
The Cycle Embedding Problem
(2016)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
The Cycle Embedding Problem
(2014)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in
the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT.
Rolling stock, i.e., the set of railway vehicles, is among the most
expensive and limited assets of a railway company and must be used
efficiently. We consider in this paper the re-optimization
problem to recover from unforeseen disruptions. We propose a
template concept that allows to recover cost minimal rolling
stock rotations from reference rotations under a large variety of
operational requirements. To this end, connection templates as
well as rotation templates are introduced and their
application within a rolling stock rotation planning model is
discussed. We present an implementation within the rolling stock rotation
optimization framework rotor and computational results for
scenarios provided by DB Fernverkehr AG, one of the
leading railway operators in Europe.
Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented.
We consider the problem of pattern detection in large scale
railway timetables. This problem arises in rolling stock optimization planning
in order to identify invariant sections of the timetable for
which a cyclic rotation plan is adequate.
We propose a dual reduction technique which leads to an decomposition
and enumeration method. Computational results for real
world instances demonstrate that the method is able to
produce optimal solutions as fast as standard MIP solvers.
We consider the problem of pattern detection in large scale
railway timetables. This problem arises in rolling stock optimization planning
in order to identify invariant sections of the timetable for
which a cyclic rotation plan is adequate.
We propose a dual reduction technique which leads to an decomposition
and enumeration method. Computational results for real
world instances demonstrate that the method is able to
produce optimal solutions as fast as standard MIP solvers.
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
Since railway companies have to apply for long-term public contracts to operate railway lines in public tenders, the question how they can estimate the operating cost for long-term periods adequately arises naturally. We consider a rolling stock rotation problem for a time period of ten years, which is based on a real world instance provided by an industry partner. We use a two stage approach for the cost estimation of the required rolling stock. In the first stage, we determine a weekly rotation plan. In the second stage, we roll out this weekly rotation plan for a longer time period and incorporate scheduled maintenance treatments. We present a heuristic approach and a mixed integer programming model to implement the process of the second stage. Finally, we discuss computational results for a real world tendering scenario.
We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.
The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.
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.
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. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) 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 (Schaus et al., Constraints 16:125–147, 2010). 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.
The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.
Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.
Planning and operating railway transportation systems is an extremely
hard task due to the combinatorial complexity of the underlying discrete
optimization problems, the technical intricacies, and the immense size of
the problem instances. Because of that, however, mathematical models
and optimization techniques can result in large gains for both railway cus-
tomers and operators, e.g., in terms of cost reductions or service quality
improvements. In the last years a large and growing group of researchers
in the OR community have devoted their attention to this domain devel-
oping mathematical models and optimization approaches to tackle many
of the relevant problems in the railway planning process. However, there
is still a gap to bridge between theory and practice, with
a few notable exceptions. In this paper we address three success stories,
namely, long-term freight train routing (part I), mid-term rolling stock
rotation planning (part II), and real-time train dispatching (part III). In
each case, we describe real-life, successful implementations. We will dis-
cuss the individual problem setting, survey the optimization literature,
and focus on particular aspects addressed by the mathematical models.
We demonstrate on concrete applications how mathematical optimization
can support railway planning and operations. This gives proof that math-
ematical optimization can support the planning of rolling stock resources.
Thus, mathematical models and optimization can lead to a greater effi-
ciency of railway operations and will serve as a powerful and innovative
tool to meet recent challenges of the railway industry.
Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.
Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.
Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects.
In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites.
We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
Rapid Branching
(2012)
We propose rapid branching (RB) as a general branch-and-bound heuristic
for solving large scale optimization problems in traffic and transport.
The key idea is to combine a special branching rule and a greedy node selection
strategy in order to produce solutions of controlled quality rapidly
and efficiently. We report on three successful applications of the method
for integrated vehicle and crew scheduling, railway track allocation, and
railway vehicle rotation planning.
Rapid Branching
(2013)
We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.
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.
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
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.
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.
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.
Railway Track Allocation
(2012)
Railway Track Allocation
(2018)
This chapter addresses the classical task to decide which train runs on which track in a railway network. In this context a track allocation defines the precise routing of trains through a railway network, which usually has only a limited capacity.
Moreover, the departure and arrival times at the visited stations of each train must simultaneously meet several operational and safety requirements.
The problem to find the 'best possible' allocation for all trains
is called the track allocation problem (TTP).
Railway systems can be modeled on a very detailed scale covering the behavior of individual trains and the safety system to a large extent. However, those microscopic models are too big and not scalable to large networks, which make them inappropriate for mathematical optimization on a network wide level. Hence, most network optimization approaches consider simplified, so called macroscopic, models. In the first part we take a look at the challenge to construct a reliable and condensed macroscopic model for the associated microscopic model and to facilitate the transition between both models of different scale.
In the main part we focus on the optimization problem for macroscopic models of the railway system. Based on classical graph-theoretical tools the track allocation problem is formulated to determine conflict-free paths in corresponding time-expanded graphs. We present standard integer programming model formulations for the track allocation problem that model resource or block conflicts in terms of packing constraints. In addition, we discuss the role of maximal clique inequalities and the concept of configuration networks. We will also present classical decomposition approaches like Lagrangian relaxation and bundle methods. Furthermore, we will discuss recently developed techniques, e.g., dynamic graph generation.
Finally, we will discuss the status quo and show a vision of mathematical optimization to support real world track allocation, i.e. integrated train routing and scheduling, in a data-dominated
and digitized railway future.