Refine
Year of publication
Document Type
- In Proceedings (13)
- ZIB-Report (11)
- Article (4)
- Master's Thesis (1)
- Other (1)
Language
- English (30)
Keywords
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.
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.
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.
Network virtualization techniques allow for the coexistence of many virtual networks (VNs) jointly sharing the resources of an underlying substrate network. The Virtual Network Embedding problem (VNE) arises when looking for the most profitable set of VNs to embed onto the substrate. In this paper, we address the offline version of the problem. We propose a Mixed-Integer Linear Programming formulation to solve it to optimality which accounts for acceptance and rejection of virtual network requests, allowing for both splittable and unsplittable (single path) routing schemes. Our formulation also considers a Rent-at-Bulk (RaB) model for the rental of substrate capacities where economies of scale apply. To better emphasize the importance of RaB, we also compare our method to a baseline one which only takes RaB into account a posteriori, once a solution to VNE, oblivious to RaB, has been found. Computational experiments show the viability of our approach, stressing the relevance of addressing RaB directly with an exact formulation.
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.
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.
For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.
For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride
and it is often related to the image of the company itself. Thus, it is highly desired to
have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer
linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Borndörfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios
for the ICE high speed train network in Germany and compared to the approaches
of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.
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.