Optimization of container transportation for fixed-schedule block trains with optional round trips in collaborative logistics

Abstract

Während der Transportsektor in der EU aufgrund steigenden Bedarfs ständig wächst, ist er für einen großen Teil des Energie- und CO2-Verbrauchs verantwortlich. Im Güterzugverkehr, eine der klimafreundlichsten und preisgünstigsten Optionen, werden meist zwei verschiedene Zugverkehrstypen eingesetzt: Der flexiblere Wagenladungsverkehr und der günstigere Ganzzugverkehr.In dieser Arbeit untersuchen wir einen alternativen Ansatz aus Sicht einer Spedition, der die Vorteile beider Zugverkehrstypen kombiniert. Im "Multiple Collaborative Round Trip Problem" (MCRP) optimieren wir den Transport von 20' Standardcontainern und den Einsatz von Ganzzügen, die ähnlich wie Passagierzüge fahren: Sie haben fixe Fahrplänen, wiederholte Fahrten - sogenannte ``Round Trips'' - und mehrfache Stops. Leerfahrten oder schlecht ausgelastete Zugfahrten werden vermieden, indem die geladenen Container auf andere Züge (oder Fahrten) verlagert werden und dadurch gesamte Fahrten weglassen und eingespart werden können.Wir stellen eine formale Problembeschreibung auf, repräsentieren das Problem mit Hilfe eines ``Time-expanded Networks'', lösen es exakt durch die Modellierung eines ``Integer Linear Programs'', und beweisen die Komplexität des MCRP. Wir generieren künstliche Instanzen, um die Performance unseres Ansatzes und die Eigenschaften der Lösungen zu den Instanzen zu untersuchen. Diese beruhen auf einem echten Schienennetzwerk und fundierten Werten aus Literatur und Feedback unseren Projektpartner:innen.Wir untersuchen unseren Algorithmus auf Laufzeit und andere Qualitätskriterien, den Einfluss von Instanz-Parametern auf die Komplexität des Problems und dessen Lösungseigenschaften, und eine einzelne beispielhafte Lösung, um tieferen Einblick in die Lösungsstrukturen unserer Instanzen zu erhalten. Außerdem vergleichen wir die künstlichen Instanzen mit der derzeitigen Praxis und untersuchen die Anwendbarkeit unseres Ansatzes in der Praxis.

In times of globalization and climate change, the freight transportation sector faces increasing demand. At the same time, it is responsible for a major part of the energy consumption and CO2 emissions in the European Union. Rail freight transport appears to be one of the best choices when considering economical and ecological aspects.In current practice, two types of rail freight are common: In so-called "wagonload freight", individual trains are composed of individual wagons, while "block trains" have a fixed set of wagons and directly connect their source to their destination without intermediate stops.Wagon load trains allow more flexibility, but the uncoupling and rearranging operations of wagons are rather costly. In this study, we investigate an alternative approach to combine the advantages of both operation techniques and potentially increase the efficiency of the freight sector.We optimize the shipment of individual 20' containers, which are carried by block trains. These block trains operate on fixed schedules with potentially recurring round trips and multiple stops, similar to passenger trains. The idea is to avoid empty runs and underutilized round trips by shifting the respective containers to other trains or round trips. These empty round trips then do not have to take place, hence costs are saved.The corresponding problem is called "Multiple Collaborative Round Trip Problem"(MCRP). It arises in the context of the research project PhysICAL from the point of view of a freight forwarder in collaborative logistics. If the container paths are optimized from a global point of view, the operational cost of the freight forwarder can be reduced. In return, the operator can then offer better prices to its customers.We formally define the MCRP and represent it with the use of a time-expanded network, state an Integer Linear Program (ILP) to solve it in an exact way, and prove the NP-completeness of its decision variant.To investigate and benchmark the problem, we generate a set of artificial instances. They are based on a real-world rail network and connect a subset of ten relevant cities for current rail freight transport in Europe. The individual instance parameters and values are researched or provided by our project partners.We analyze the performance of our algorithm, the hardness of the problem, and the characteristics of the solutions for a variety of instance parameters. We also investigate a single solution in detail to provide deeper insights into the composition of the solutions. At last, we compare our method to the state of the art and draw managerial insight from our results.