Refine
Document Type
- In Proceedings (1)
- Master's Thesis (1)
- ZIB-Report (1)
Language
- English (3)
Keywords
- Coarse (1)
- Coarse-to-Fine (1)
- Rostering (1)
- Scheduling (1)
- Toll Control (1)
- Workforce (1)
- robust optimization, rolling stock planning (1)
Institute
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.
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.