ISBN 9783843904681

978-3-8439-0468-1, Reihe Mathematik

Henning Homfeld
Consolidating Car Routes in Rail Freight Service by Discrete Optimization

184 Seiten, Dissertation Universität Erlangen-Nürnberg (2012), Softcover, A5

Zusammenfassung / Abstract

This thesis is concerned with finding optimal car routes in a logical network. Motivated by a joint research project with Europe's largest railway company Deutsche Bahn AG, heuristic as well as exact solution methods for this tactical planning problem arising in the area of rail freight service are developed.

A car route is a sequence of shunting yards, at which these cars are disassembled and regrouped to form new trains. When determining the routes of all cars in a given network system, the aim is to consolidate the cars such that foremost the number of necessary train-kilometers, that is the number of trains multiplied by their travel distances, is minimized. Modeling the given problem in different variants results in very large, mixed integer programs. We use tailor-made preprocessing methods in advance in order to reduce this size significantly. To solve the programs we analyze their underlying polyhedral structure and strengthen the formulation in order to obtain improved lower bounds. We adapt cutting planes from a larger class of network design problems and show that corresponding theoretical results do not hold in the framework of the considered problem. Furthermore, we describe a column generation approach that enables us to quickly determine dual bounds even for very large problem instances. In order to support the solution process we develop several heuristics. In addition to two MIP based approaches, we introduce a combinatorial heuristic which allows us to reliably generate feasible solutions of high quality. Moreover, we study a nonlinear model expansion which we linearize in two different ways. In this context we give a convex hull description of the set of feasible points for this expansion.

The solution methods are evaluated by a detailed analysis of computational results. It turns out that the developed methods and algorithms are very useful when solving given problem instances - especially for very large scale real life data sets.