Die Touroptimierer

"Tourenplanung ist eines der Kernprobleme in Unternehmen, die Außendienstmitarbeiter zu Kunden schicken", sagt Srivastav. Die Kosten im Verkehrswesen sind zuletzt stark gestiegen. Wer Umwege vermeiden kann, spart Zeit, Geld und schont die Umwelt. Die mathematische Formulierung ist unter dem Namen »Traveling Salesman Problem« (TSP) bekannt geworden: Ein Handlungsreisender will eine bestimmte Anzahl an Kunden besuchen und danach wieder nach Hause zurückkehren. Doch in welcher Reihenfolge muss er die Kunden aufsuchen, damit die zurückgelegte Strecke möglichst kurz ist?

Effiziente Tourenplaung spart Zeit und Geld. Foto: Photocase.com

Um dennoch zu einem Resultat zu gelangen, entwirft die Mathematik Näherungsverfahren. Dabei wird von vornherein auf eine vollständige Untersuchung des Lösungsraumes verzichtet. Ein Anwender solcher Techniken ist die Heikendorfer Softwarefirma Fuhrpark & Logistik Systeme FLS GmbH. Sie bietet seit 1988 Systeme zur Tourenplanung an und hat mit Gerolsteiner, Danone, Ferrero oder Beiersdorf viele namhafte Referenzkunden.

Kontakt zur Arbeitsgruppe von Professor Srivastav entstand über ein Praktikum von Uni-Mathematiker Dr. Andreas Baltz. "Die in der Praxis verwendeten Algorithmen berücksichtigen pro Kunde bisher maximal zwei Zeitfenster für den Besuch", sagt Baltz. "Tatsächlich wünschenswert sind aber bis zu zehn." Weil mehrere Reisende auf den Weg geschickt würden, stelle sich auch die Frage nach der Gebietsaufteilung. "Bislang lässt sich bei der Zuordnung der Kunden auf die Mitarbeiter deren Fahrzeit nicht vorhersagen."

In einem mit finanzieller Unterstützung von Innovationsstiftung Schleswig-Holstein und Wissenschaftsministerium entstandenem Projekt wollen FLS und Uni Kiel nun gemeinsam ein praktisch besseres Verfahren für die Tourenplanung entwickeln, das die Gebietsplanung mit einbezieht. 200 Reisende, 20.000 Kunden und pro Kunde bis zu zehn Zeitfenster soll der neue Algorithmus berücksichtigen können. Von der Arbeit profitiert auch die Wissenschaft: "In dieser Form ist das Problem bisher weder theoretisch noch experimentell untersucht worden. Doch nur eine theoretisch-mathematische Fundierung wird praktische Fortschritte ermöglichen", sagt Srivastav.

Die Forscher gehen in drei Schritten vor: Zunächst wird die komplexe Aufgabenstellung in geeignete Teilbereiche zerlegt, für die es möglicherweise exakte Lösungen gibt. Dann wird versucht, die Teilbereiche den praktischen Notwendigkeiten anzupassen, so dass die derart erweiterte Lösung der Teilbereiche zu einer zulässigen Lösung des Ausgangsproblems wird. Gelingt dies, muss schließlich die zulässige Lösung gemäß der Zielfunktion optimiert werden.

"Durch dieses Vorgehen kommen wir beweisbar nah an das Optimum, ohne dieses genau zu kennen". Das Potenzial für Verbesserungen sei groß: In anderen Fällen konnten kommerzielle Lösungen um bis zu 30 Prozent optimiert werden. Srivastav: "In unserem Projekt wird Mathematik 1:1 zum wirtschaftlichen Wettbewerbsfaktor."