Forschung : Automatisierte Tourenplanung und 3D-Belade-Optimierung für den Lebensmittelhandel

Aktuell arbeiten Witron und die TU Dresden an einer Automatisierung der Tourenplanung mit integrierter 3D-Beladeoptimierung im Rahmen eines Entwicklungsprojektes. „Wir hatten dazu schon eine innovative Lösung, die damals Anfang der 2000er Jahre basierend auf einem Savings-Algorithmus viel Aufmerksamkeit in den Branchen erfuhr und hochgelobt wurde“, erklärt Stefan Bauer, bei Witron verantwortlich für das CPMS-Wellpappengeschäft. Das Problem: Über die Jahre bauten die Entwickler und Entwicklerinnen immer mehr Restriktionen ein. Die Laufzeiten waren bei den großen Lieferpools nicht mehr zufriedenstellend und der Codeumfang wuchs.

„Die Wartung wurde immer schwieriger“, erinnert sich Bauer. „Sowohl Technologien als auch die Wissenschaft haben sich weiterentwickelt, uns war klar, wir müssen auf eine neue Technik gehen.“ Externe Unterstützung erhielten Bauer und von Leopold Kuttner, wissenschaftlicher Mitarbeiter am Lehrstuhl industrielles Management an der TU Dresden.

Das Ziel des Projektes war also, die bestehende Tourenplanungslösung von Witron zu verbessern, wobei komplexe Transporttarife und verschiedene praxisrelevante Restriktionen berücksichtigt werden mussten. Zum Beispiel zählen zu den Restriktionen für die Tourenplanung mehrere Zeitfenster, Auftragssplitting und ein heterogener Fuhrpark, und für das Packproblem Restriktionen wie Stapelbarkeit und LIFO-Entladung. Zum Lösen des Packproblems werden ein Beladeoptimierungstool von Witron und ein vom Lehrstuhl entwickelter Packalgorithmus verwendet.

„Um zulässige Lösungen von guter Qualität zu erreichen, muss das Tourenplanungs- und das Packproblem integriert gelöst werden. In der Kombination dieser zwei anspruchsvollen Optimierungsprobleme liegt die Schwierigkeit der Aufgabenstellung. Als zusätzliche Herausforderung müssen zahlreiche, praxisrelevante Restriktionen berücksichtigt werden“, erklärt Kuttner, der das Projekt TU-seitig betreute.

Um das Problem der Tourenplanung und vor allem der Geschwindigkeit zu lösen, werden klassische Konstruktions- und Verbesserungsverfahren implementiert. Bei der integrierten Planung stellen die häufigen Aufrufe an das Beladeoptimierungstool den Flaschenhals bzgl. der Rechenzeit dar. Um diese Aufrufe möglichst gering zu halten, wird ein innovativer Pack-First Route-Second-Ansatz verfolgt. Hierbei ist die Grundidee das zeitintensive, dreidimensionale Problem durch eine eindimensionale Größe, die Lademeter, zu approximieren und somit Rechenzeit zu sparen. In Ergänzung dazu wird eine moderne Metaheuristik implementiert, heißt es am Lehrstuhl.

Durch das Projekt ist eine algorithmische Lösung zur Entscheidungsunterstützung entstanden, welche alternative Planungsvorschläge generiert, um Disponenten in der operativen Planung besser unterstützen zu können. So wird die Einhaltung aller Planungsvorgaben für die Touren- und Beladeplanung gewährleistet. Über eine parametrisierbare Kostenfunktion können Disponenten ihre Planungspräferenzen angeben und sich in Sekundenschnelle mehrere kostengünstige Vorschläge zu Tourenplänen generieren lassen. Durch die Zeitersparnis in der Planung können Disponenten anderen wertschöpfenden Aufgaben mehr Aufmerksamkeit schenken.

Bauer lobt die Geschwindigkeit der neuen Lösung. „Wir haben uns ganz neue Methoden angeschaut, viel aus dem E-Commerce gelernt und das dann um unsere Heuristik ergänzt.“ Validiert wurden die Teilabschnitte des Projekts mit Live-Daten aus der Produktion. „Wir müssen den Algorithmus jetzt weiter pflegen, weiterentwickeln. Das ist nicht immer leicht. Wir sind voll auf das Projektgeschäft ausgerichtet“, so Bauer. „Der nächste Schritt ist die Implementierung der Lösung in den Lebensmitteleinzelhandel, denn in einer End-to-End-Plattform ist das ein entscheidender Baustein.“