Universität zu Köln

A Generalized Network Model for Freight Car Distribution

Engels, Birgit (2011) A Generalized Network Model for Freight Car Distribution. PhD thesis, Universität zu Köln.

[img]
Preview
PDF - Published Version
Download (2797Kb) | Preview

    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. In our case, one major constraint is given by prescheduled freight trains: obviously a supply can only be assigned to a demand if it reaches the latter in time. Further, the variety of goods (bulk cargo, steel coils, etc.) to be transported requires distinct types of freight cars. Freight cars of a certain type can be exchanged by cars of other types with respect to a given substitution scheme and different 'exchange rates'. Allowed substitutions are therefore another major constraint of the (DP). We describe further `hard' and `soft' constraints and sketch the current work flow at DB Schenker Rail Deutschland AG to find an adequate solution for the (DP) on a daily base in practice. The (DP) is currently solved separately for groups of car types and in several steps. Moreover, some steps contain manual pre- and post-processing to ensure certain constraints. Hence global sub-optimal distributions can occur. We therefore integrate all constraints 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 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 two ways. Instances of the (DP) which correspond to classical flow networks are solved by an integral minimum cost flow, which can be obtained in polynomial time. We use such instances to polynomially obtain minimum cost flows of fixed bounded fractionality for certain general instances. For those instances occurring in the application we obtain half-integral flows, which can be rounded to approximate or heuristic distributions in linear time. Moreover, we develop a network-based reoptimization approach, which yields optimal 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.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    Wir betrachten das Problem der Disposition leerer Güterwagen (DP) bei DB Schenker Rail Deutschland AG unter Berücksichtigung vieler praxisrelevanter Nebenbedingungen und realer Daten(mengen). Das (DP) ist ein ,Online'- Zuordnungsproblem zwischen dezentral verfügbaren Güterwagen (Beständen) und geographisch verteilten Kundenbestellungen (Bedarfen) für zukünftige Gütertransporte. Eine optimale Zuordnung minimiert im Wesentlichen die Transportkosten für leere Güterwagen. Eine grundlegende Nebenbedingung ist die rechtzeitige Erreichbarkeit zwischen Bestand und Bedarf, die durch einen vorgegebenen Güterzug-Fahrplan bestimmt wird. Verschiedene Güter (wie zum Beispiel Schüttgut, Stahl-Coils, etc.) benötigen unterschiedliche Arten von Güterwagen für ihren Transport. Bestände und Bedarfe sind daher typisiert. Andererseits können verschiedene Wagentypen (nach festen Schemata und Anzahlen) gegeneinander ausgetauscht werden. Diese erlaubten Austauschbeziehungen geben eine weitere zentrale Nebenbedingung des (DP) vor. Wir stellen in der vorliegenden Arbeit zahlreiche weitere ,harte' und ,weiche' Nebenbedingungen vor und skizzieren die zur Zeit durchgeführte Disposition bei DB Schenker Rail Deutschland AG. Diese wird nach Gruppen von Wagentypen getrennt und in mehreren, teils manuellen vor- bzw. nachgelagerten Schritten vorgenommen. So kann es zu global suboptimalen Dispositionen kommen. Um dies unter Berücksichtigung aller Nebenbedingungen zu vermeiden, modellieren wir das (DP) als generalisiertes Flussnetzwerk, welches ganzzahlig zu lösen ist. Letzteres ist NP-schwer, ebenso wie das (DP) unter allgemeinen Substitutionsbedingungen. Die Lösung des (DP) erfordert daher einen Kompromiss zwischen praktikabler Laufzeit und Qualität der erzeugten Disposition. Wir erreichen dies einerseits durch Anwendung approximativer und heuristischer Lösungsmethoden für den Fall allgemeiner Substitutionsbedingungen, andererseits durch die Entwicklung einer netzwerkbasierten Reoptimierungsstrategie. Diese berechnet für eine Folge von Instanzen mit wenigen Datenänderungen in kurzer Zeit optimale (bzw. im allgemeinen Fall approximative und heuristische) zulässige Lösungen. Diese Arbeit wurde durch ein 2-jähriges Forschungs- und Entwicklungsprojekt der DB Schenker Rail Deutschland AG in Kooperation mit der Arbeitsgruppe Faigle/Schrader der Universität zu Köln und mit der Arbeitsgruppe von Prof. Dr. Sven O. Krumke (Technische Universität Kaiserslautern) motiviert und finanziert. Das Projekt umfasste ebenfalls die Implementierung des entwickelten generalisierten Netzwerkmodells, der Reoptimierungsstrategie sowie der Approximationsmethoden und Heuristiken. Diese sollen als zukünftiger Optimierungskern für das (DP) bei DB Schenker Rail Deutschland AG genutzt werden.German
    Creators:
    CreatorsEmail
    Engels, Birgitengels@zpr.uni-koeln.de
    URN: urn:nbn:de:hbz:38-42621
    Series Name: Informatik
    Publisher: Dr. Hut Verlag München
    ISBN: 978-3-86853-991-2
    Subjects: Data processing Computer science
    Commerce, communications, transport
    Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    transportation, logistics, dispatching, distribution, railway, empty car, generalized flow, complexity, approximation, heuristicEnglish
    Transport, Logistik, Schienengüterverkehr, Leerwagenverteilung, generalisierter Fluss, Komplexität, Approximation, HeuristikGerman
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: June 2011
    Date Type: Publication
    Date of oral exam: 23 May 2011
    Full Text Status: Public
    Date Deposited: 13 Jul 2011 08:47:02
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    Krumke, Sven O.Prof. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/4262

    Actions (login required)

    View Item