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.

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.