Optimizing the Cargo Express Service of Swiss Federal Railways

Project director: Dr. Marco Lübbecke
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 25735
e-mail: m.luebbecke[at]math.tu-berlin.de
Researchers: Dr. Alberto Ceselli
Dr. Michel Gatto
Dr. Marco Lübbecke
Dr. Marc Nunkesser
Dr. Heiko Schilling
Cooperation partner:

Problem Description

The Cargo Express service of Swiss Federal Railways (SBB Cargo) offers fast overnight transportation of goods between selected train stations in Switzerland and is operated as a hub-and-spoke system. For each shipment there are guaranteed pickup and latest delivery times. On their journay, cars usually need to be reclassified in two central hump yards, the hubs. Each train can be composed by a limited number of cars, and each hub can handle only a limited number of cars at the same time. The total operation cost (per locomotive cost plus a cost per traveled distance) is to be minimized.

Large-Scale Mixed Integer Programs

We present three different models for planning the operation of this service as a whole. All models capture the underlying optimization problem with a high level of detail: Traffic routing, train routing, make-up, scheduling, and locomotive assignment are all addressed. At the same time we respect hard constraints like tight service time windows and train capacities, and we avoid hub overloading.

The most elaborate of these models is a side-constrained set partitioning problem, the variables of which represent routes of locomotives (together with schedule and shipment pickup/delivery). To the best of our knowledge, this model is the first to integrate all planning steps of the tactical level. Although we tailored the solution approach to our specific problem, the model itself is applicable with minor modifications to any non-blocking freight system of larger scale.

It is interesting to note that our problem has a distinct flavor of flows over time (or dynamic flows). In fact, our model is an example where flow conservation of time is assured in particular nodes (the hubs).

Solution Techniques

Our algorithmic techniques involve branch-and-cut, branch-and-price as well as problem specific exact and heuristic acceleration methods. To solve the model with an exponential number of variables we apply column generation; integer solutions are obtained from a dive-and-fix heuristic which is based again on column generation and problem specific rounding.


References

[1] A.Ceselli, M.J.Gatto, M.E.Lübbecke, M.Nunkesser, and H.Schilling.
Optimizing the cargo express service of Swiss Federal Railways
TU Berlin, Institut für Mathematik, Preprint 2006/28
Under revision for Transportation Science