Projekt MEFISTO

Ein Metaheuristik-Framework für die Transportoptimierung

Tourenplanung ist eine Aufgabe innerhalb der Transportlogistik, der sich viele Transportunternehmen zumeist täglich stellen. Vorliegende Kundenaufträge effizient den vorhandenen Ressourcen, u.a. Fahrzeugen und Fahrern, so zuzuweisen, dass eine kostenminimale Abwicklung gewährleistet wird, ist eine komplexe Aufgabe, die heute oftmals rechnergestützt gelöst wird. Der Einsatz  moderner Planungssysteme bewirkt den effizienten Ressourceneinsatz und sorgt für transparente Prozesse und Kosten.

Wissenschaftlich gesehen ist die Tourenplanung ein sog. kombinatorisches Optimierungsproblem bei dem es darum geht, aus einer großen aber endlichen Menge von Möglichkeiten die gemäß eines gegebenen Gütekriteriums beste auszuwählen. In der Tourenplanung wird beispielsweise darüber entschieden, welches Fahrzeug welchen Auftrag ausführt und in welcher Reihenfolge die zu den Aufträgen gehörenden Stops jeweils von dem entsprechenden Fahrzeug besucht werden. In realen Anwendungen gibt es eine dermaßen große Vielfalt an Kombinationsmöglichkeiten, dass selbst heutige Rechner mit der Suche nach der mathematisch optimalen Lösung in den allermeisten Fällen überfordert sind. Allerdings steht für die operative Planung im täglichen Ablauf nur ein kurzes Zeitfenster zur Verfügung, innerhalb dessen ein kosteneffizienter Transportplan berechnet werden muss - und zwar täglich mit verlässlicher Qualität.

Im Auftrag der PTV AG, einem in Karlsruhe ansässigen und weltweit führenden Anbieter von Logistiklösungen, und in enger Zusammenarbeit mit den erfahrenen Experten des Unternehmens, wurde von Mitarbeitern der Abteilung LSE am FZI das System MEFISTO - MEtaheuristic Framework for Information Systems in Transport Optimization - entwickelt. Dabei handelt es sich um eine C++-basierte softwaretechnische Plattform, die es den Kunden der PTV AG ermöglicht, stets moderne Optimierungsalgorithmen einzusetzen und damit effiziente Transportpläne zu bestimmen. Bewährte und neue Verfahren sind durch MEFISTO flexibel kombinierbar, bspw. lassen sich die bewährten und hocheffizienten Verfahren der Restriktionsprüfung mit innovativen selbststeuernden Suchverfahren verbinden. Im Ergebnis entstehen Optimierungslösungen, die die vom Anwender vorgegebene maximale Rechenzeit effizient nutzen und gegenüber früheren Systemen qualitativ deutlich bessere Transportpläne erstellen.

Die erfolgreiche Zusammenarbeit zwischen PTV AG und FZI erfolgte in sehr enger Abstimmung bspw. durch Verwendung einer gemeinsamen Code-Basis und intensiven Phasen der Vor-Ort-Entwicklung - die nächsten Ziele sind bereits gesteckt.