Die Forschungsarbeiten im Bereich Tourenplanung werden im Projekt Optimale Linienführung und Routenplanung in Verkehrssystemen (kurz: OptiLRV) vom BMBF gefördert. Es handelt sich hierbei um ein Teilvorhaben des Förderprogrammes Anwendungsorientierte Verbundvorhaben auf dem Gebiet der Mathematik.
In diesem Projekt wurden u.a. neue Verfahren für die Tourenplanung bei einem Frischwarenlieferanten für Restaurants und Feinkostläden, entwickelt. Das dort zu lösende Vehicle-Routing-Problem hat folgende Ausprägungen: ein Depot (Meckenheim), inhomogener Fuhrpark (50 Fahrzeuge) und Bedienzeitfenster bei den Kunden. Diese Zeitfensterrestriktionen machen das Problem schwierig, da für viele Liefertage keine gültige Lösung existiert, bei der jeder Kunde während seiner Öffnungszeiten beliefert werden kann.
Abbildung: Ergebnis einer Tourenplanung mit Zeitfenstern
Ein gängiges Mittel, in solchen Fällen möglichst nah an eine zulässige Lösung zu gelangen, ist die Bewertung von Verspätungen mit Strafkosten. Dieser Ansatz führt bei dem hier vorliegenden Problem nicht zum Ziel, da Kunden ihre ,,Wertigkeit`` ändern können. Damit wird der Aufwand, alle 700-1000 Kunden vor jeder Planung in verschiedene Kategorien zu sortieren, zu hoch. Statt dessen wird der Ansatz verfolgt, möglichst viele Kunden ,,in time`` einzuplanen. Die nicht zulässig zu bedienenden Kunden werden vom Disponenten nachträglich manuell eingeplant. Die Entscheidung darüber, bei welchen Kunden dabei Verspätungen in Kauf genommen werden, trifft der Disponent in telefonischer Absprache mit den Betroffenen.
Folgende aus der Praxis motivierten Vorgaben haben das Design des Verfahrens beeinflußt: Es sollen regional beschränkte Touren geplant werden, um die Gebietskenntnis der Fahrer auszunutzen. Außerdem dürfen sich die Touren nicht kreuzen. Eine weitere Einschränkung ist der Einsatz von PCs, auf denen die Planung in wenigen Minuten durchgeführt werden soll.
Dazu wurde ein spezielles Verfahren entwickelt, das zunächst eine Clusterung der zu verplanenden Aufträge vornimmt. In einem zweiten Schritt werden später in jedem so entstandenen Cluster die Kunden mit Hilfe eines Insert-Verfahrens zu einer zulässigen Tour zusammengestellt (Cluster first - Route second). Zur Clusterung berechnet man einen minimalen aufspannenden Baum auf allen zu verplanenden Kunden, wobei die Kantengewichte durch die Distanzen im Straßennetz gegeben sind. Durch Entfernen einer Teilmenge der Kanten wird der Baum in mehrere Teile geteilt. Die Kunden in jedem Teilbaum sollen in einer Tour verplant werden. Für die so entstandenen Kundenmengen (Cluster) wird die Einhaltung von Restriktionen auf folgende Größen überprüft:
Die Anzahl von Kunden mit kritischen Zeitfenstern (z.B. weniger als drei Stunden Lieferzeit oder Lieferung bis 12.00 h) werden begrenzt, um ein zulässiges Routing zu ermöglichen. Es wird jeweils ein den obigen Restriktionen genügender Teilbaum mit möglichst vielen Kunden abgetrennt und für den Restbaum die Iteration erneut durchgeführt. Innerhalb dieses Clusterverfahrens ist ein sogenanntes Tree-Partitioning-Problem mit mehreren Knotengewichtsfunktionen zu lösen. Die Gewichte modellieren dabei die Restriktionen 1-4. Es konnte gezeigt werden, daß dieses Problem im allgemeinen NP-schwer ist. Wir haben daher eine Greedy-Heuristik entwickelt, die für die bei dem Frischwarenlieferanten vorliegenden Tourenplanungs-Instanzen gute Ergebnisse liefert.
Das anschließende Routing innerhalb jedes Clusters geschieht durch eine Einfügeheuristik. Dazu werden die Kunden nach Länge und Anfangszeitpunkt der Zeitfenster sortiert. Man sucht nun eine Menge von Kunden mit disjunkten Zeitfenstern, für die ihre Bedienreihenfolge durch die Abfolge der entsprechenden Fenster vorgegeben ist. Die übrigen Kunden werden in der sortierten Reihenfolge nacheinander an die günstigste gültige Position eingefügt. Existiert keine solche, so versucht man, durch Löschen eines schon geplanten Stops aus der Tour und Einfügen des aktuellen Stops eine kürzere Tour zu generieren. Nach einer festen Anzahl von Einfügeoperationen wird mit Hilfe eines 3-Opt-Verbesserungsverfahrens versucht, mögliche Schleifen, die sich durch eine ungünstige Einfügereihenfolge ergeben können, zu eliminieren.
Uns liegen Praxisinstanzen mit Kundenmengen zwischen 743 und 942 vor,
die auf maximal 50 Fahrzeuge zu verteilen sind. Für diese Instanzen
bleiben zwischen 20 und 48 Kunden als nicht verplanbar übrig, diese
werden dann manuell ohne Generierung von zusätzlichen Touren
eingeplant. Die Anzahl der Fahrzeuge wurde im Vergleich zu dem
tatsächlich gefahrenen Tourenplan durchschnittlich um 3 reduziert. Bei
Instanzen mit wenigen Kunden waren sogar Einsparungen von bis zu 8
Fahrzeugen möglich. Abbildung 
zeigt eine solche
Planung, bei der 983 Kunden auf 41 Touren verteilt wurden. Dabei
mußten nur 43 Kunden vom Disponenten manuell eingeplant werden. Die
Überschneidungen im Verlauf einiger Touren ergeben sich durch die
Zeitrestriktionen.
Abbildung: Verladung von Containern auf LKWs
Im Rahmen der seit 1991 bestehenden Kooperation mit der Profi.S GmbH Remscheid wurde die Entwicklung des von uns konzipierten Tourenplanungsprogrammes ProfiTour++ vorangetrieben. Seit kurzem ist bei der Spedition Internationale Möbellogistik GmbH (IML) in Nordwalde eine Version des Programmes im operativen Einsatz.
In unserer Arbeitsgruppe wurde die Rohversion des Simulated Trading Algorithmus zu einem in der Praxis einsetzbaren Verfahren zur Disposition des IML-Fuhrparks weiterentwickelt und in das Programmpaket integriert. Hierbei lag die Hauptschwierigkeit in der Erstellung einer geeigneten Kostenfunktion. Die Berechnung eines Kostenwertes, der unstetige Parameter wie Fahrerpausen und Übernachtungen berücksichtigt, stellte sich als sehr rechenintensiv heraus. Es mußte daher ein geeigneter Kompromiß zwischen den Effizienzanforderungen des Verfahrens und der vom Anwender geforderten Realitätsnähe der Lösung gefunden werden.
Für die Zukunft ist geplant, weitere mathematische Verfahren in dieser Weise für die Praxis zu erschließen. Dabei untersuchen wir zum einen Algorithmen, bei denen eine geschickte regionale Clusterung vorgenommen wird, zum anderen werden Ansätze der sogenannten Column-Generation-Methode für exakte Lösungen analysiert. Die Kontakte zur Profi.S und ihren Partnern helfen uns, immer neue praktische Fragestellungen aus dem Bereich des Vehicle Routings und der Logistik kennenzulernen.