ISBN 9783868539912

978-3-86853-991-2, Reihe Informatik

Birgit Engels
A Generalized Network Model for Freight Car Distribution

190 Seiten, Dissertation Universität Köln (2011), Softcover, A5

Zusammenfassung / Abstract

We consider the empty freight car distribution problem (DP) at DB Schenker Rail Deutschland AG under a wide range of application relevant constraints and real data sets. The (DP) is an online assignment problem between geographically distributed empty freight car supplies and customer demands for such cars in preparation of good transport. The objective is to minimize transport costs for empty cars while distributing them effectively with respect to the constraints. We describe the latter and integrate them into a generalized network flow model for the (DP).

A global optimal distribution is then provided by an integral minimum cost flow in the network. To find such a flow is NP-hard in general. We show that a general substitution scheme for different car types makes our notion of the (DP) also NP-hard. Hence independent of the applied model and with respect to practical runtime requirements, we have to find a compromise between solution time and quality. We do so in designing approximate and heuristic approaches which work well in practice as well as a network-based reoptimization approach which yields solutions for subsequent instances with few changes very fast.

This thesis was inspired and funded by a 2-year research and development project of DB Schenker Rail Deutschland AG in cooperation with the work group Faigle/Schrader of the University of Cologne and the work group of Prof. Dr. Sven O. Krumke at the Technical University of Kaiserslautern. The project included the implementation of the generalized network model and the reoptimization, approximation and heuristic methods. The software is designed as a future optimization kernel for the (DP) at DB Schenker Rail Deutschland AG.