Aus dem klassischen Stückgutgeschäft haben sich in den vergangenen zwei Jahrzehnten durch die Abgrenzung eines gesonderten Marktes für Kurier-, Express- und Paketsendungen so genannte KEP-Dienste entwickelt. Das bei weitem größte Segment im KEP-Markt bilden dabei die Paketdienste, die sich auf den Transport von Kleinpaketen mit einem Gewicht von bis zu 31,5 kg spezialisiert haben. Aufgrund der von den Paketdienstleistern gegenüber den Kunden zugesagten Laufzeitgarantien (z. B. 24-Stunden-Lieferung bei einem Transport innerhalb Deutschlands) haben Paketdienste leistungsfähige Transportnetze entwickelt, welche sicherstellen, dass die Sendungen in der gewünschten Zeit beim Empfänger ankommen.

Diese Transportnetze verbinden die physischen Standorte der Depots und Umschlagstandorte miteinander. Der typische Transportablauf in diesen Netzen gestaltet sich derart, dass während des so genannten Vorlaufs innerhalb der Depotgebiete Sendungen von Kunden abgeholt werden. Die Sendungen werden dann zu größeren Ladungen gebündelt und im so genannten Hauptlauf zwischen den Depots transportiert. Anschließend werden im Nachlauf die Sendungen innerhalb der Depotgebiete an die Kunden ausgeliefert. Vor- und Nachlauf werden auch unter dem Begriff "Nahverkehr" zusammengefasst, da sie weitgehend zeitgleich im Zeitfenster zwischen 7.00 und 16.00 Uhr in den einzelnen Depotgebieten stattfinden.

Innerhalb dieser Transportnetze ist insbesondere die Organisation und Planung des Nahverkehrs eine zentrale Optimierungsaufgabe für die Paketdienstleister. Bei KEP-Diensten verursacht der Nahverkehr jährliche Kosten von mehreren hundert Millionen Euro. Dabei ist das Bundesgebiet in ca. 100 Depotgebiete aufgeteilt. In jedem dieser Gebiete müssen täglich mehrere Duzend Touren gefahren werden und pro Tour bis zu 200 Pakete ausgeliefert und abgeholt werden.

       

Abbildung 1: Entwicklung der Anzahl an Sendungen und des Umsatzes der KEP-Branche in Deutschland (Quelle: http://www.biek.de/download/gutachten/biek_studie_2008.pdf).

Das Planungsproblem für den Nahverkehr in den einzelnen Depotgebieten lässt sich wie folgt beschreiben: Ausgehend von einem Depot müssen Touren für eine vorgegebene Fahrzeugflotte berechnet werden, sodass der individuelle Güterbedarf einer Menge von Kunden abgedeckt wird. Pro Fahrzeug wird eine separate Route berechnet, deren Start und Zielpunkt an ein und demselben Depot liegen. Daneben muss jeder Kunde mindestens einmal besucht werden. Als Zielsetzung gilt es, ein vorgegebenes Kriterium, z. B. die insgesamt zurückgelegte Fahrstrecke der Flotte oder die Anzahl benötigter Fahrzeuge, zu minimieren. Bei der Optimierung müssen darüber hinaus noch weitere Nebenbedingungen berücksichtigt werden.

Allerdings sind keine Planungsunterstützungssysteme für den Nahverkehr am Markt verfügbar, die die umfangreichen Nebenbedingungen vollständig berücksichtigen und somit sicherstellen, dass die ermittelten Lösungen auch umgesetzt werden können. Daher findet die Planung in der Praxis in der Weise statt, dass die einzelnen Depotgebiete in mehrere Tourengebiete unterteilt werden. Die Planung für die einzelnen Tourengebiete erfolgt dann in der Regel manuell durch die Fahrer.  Dieser Lösungsansatz führt allerdings nur zu suboptimalen Lösungen, da kein Ausgleich zwischen Touren in unterschiedlichen Tourengebieten erfolgen kann. Vielversprechender ist es dagegen, sämtliche Aufträge für ein gesamtes Depotgebiet in einem Pool zusammenzufassen und dann alle Aufträge simultan zu planen.

Ziel des vorliegenden Projekts ist es, Lösungsansätze für die Steigerung der Effizienz im Nahverkehr zu entwickeln. Neben der Analyse der momentan eingesetzten Methoden zur Planung des Nahverkehrs sollen insbesondere auch Algorithmen entwickelt werden, die die Planer bei der Erstellung von Tourenplänen unterstützen.

   

Abbildung
2: Transportnetze von KEP-Diensten.