This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Fügenschuh, A. Articles by Yuan, Z. Search for Related Content

Scheduling Locomotives and Car Transfers in Freight Transport

Technische Universität Darmstadt, Arbeitsgruppe Optimierung, 64289 Darmstadt, Germany
Technische Universität Darmstadt, Arbeitsgruppe Optimierung, 64289 Darmstadt, Germany
Deutsche Bahn AG, Konzernentwicklung, 60326 Frankfurt, Germany
Technische Universität Darmstadt, Arbeitsgruppe Optimierung, 64289 Darmstadt, Germany
Technische Universität Darmstadt, Arbeitsgruppe Optimierung, 64289 Darmstadt, Germany
fuegenschuh{at}mathematik.tu-darmstadt.de
homfeld{at}mathematik.tu-darmstadt.de
andreas.huck{at}bahn.de
martin{at}mathematik.tu-darmstadt.de
yuan{at}mathematik.tu-darmstadt.de

We present a new model for a strategic locomotive scheduling problem arising at the Deutsche Bahn AG. The model is based on a multicommodity minimum cost flow formulation that is also used for public bus scheduling problems. However, several new aspects have to be additionally taken into account such as cyclic departures of the trains, time windows on starting and arrival times, network load-dependent travel times, and a transfer of cars between trains. The model is formulated as an integer linear programming problem (ILP). The formulation is improved by preprocessing and additional cutting planes. Solutions are obtained using a randomized greedy heuristic in combination with commercial ILP solvers. Computational results are presented for several real-world test instances.

Key Words: railroad freight transport; cyclic vehicle scheduling; time windows; integer linear programming; heuristics; cutting planes
History: Received: November 2006; revised: November 2007; accepted: May 2008.