90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Document Type
- ZIB-Report (12)
- Doctoral Thesis (1)
Language
- English (13)
Keywords
- Mixed Integer Programming (1)
- Moving Block (1)
- Railway Optimization (1)
- Railway Timetabling (1)
- Railway Track Allocation (1)
- Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching (1)
- Rolling Stock Rostering (1)
- Train Routing (1)
- capacity optimization (1)
- coarse-to-fine approach (1)
Institute
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 show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts.
(A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP.
(B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications.
(C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs.
In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany.
The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the
timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.
We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.
Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and
airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.
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.
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an
opportunity for high-achieving graduate-level students to work in teams on a
real-world research project proposed by a sponsor from industry or the public
sector. Each G-RIPS team consists of four international students (two from
the US and two from European universities), an academic mentor, and an industrial sponsor.
This is the report of the Rail-Lab project on the definition and integration of
robustness aspects into optimizing rolling stock schedules. In general, there is
a trade-off for complex systems between robustness and efficiency. The ambitious
goal was to explore this trade-off by implementing numerical simulations and
developing analytic models.
In rolling stock planning a very large set of industrial railway requirements,
such as vehicle composition, maintenance constraints, infrastructure capacity,
and regularity aspects, have to be considered in an integrated model. General
hypergraphs provide the modeling power to tackle those requirements.
Furthermore, integer programming approaches are able to produce high quality
solutions for the deterministic problem.
When stochastic time delays are considered, the mathematical programming problem
is much more complex and presents additional challenges. Thus, we started with a
basic variant of the deterministic case, i.e., we are only considering
hypergraphs representing vehicle composition and regularity.
We transfered solution approaches for robust optimization
from the airline industry to the setting of railways and attained a
reasonable measure of robustness. Finally, we present and discuss different
methods to optimize this robustness measure.
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.
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.
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.
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 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.