Der optimale Weg ist das Ziel

Immer mehr Supermärkte bieten Lieferservices an – und brauchen dafür eine Technologie, die die optimale Route für die Zustellung errechnet. Mathematiker*innen der Universität Klagenfurt haben für eine englische Supermarktkette Algorithmen entwickelt, die deutlich optimierte Lieferpläne errechnet. So werden Waren an mehr Kund*innen schneller und mit geringerem Kohlendioxidausstoß ausgeliefert. 

Handelt man mit Lebensmitteln, sind die Wachstumschancen eher gering: Der jährliche Umsatz steigt in der westlichen Welt im niedrigen einstelligen Bereich. Einzig der Online-Lebensmittelhandel lässt die Kassen gehörig lauter klingeln, da immer mehr Kund*innen den Komfort der mobilen Dienste des Supermarkts nutzen. Um die Heimzustellung von Lebensmitteln und anderen Waren jedoch gewinnträchtig anbieten zu können, müssen Supermarktketten vorab in die Planung der Logistik investieren.

Christian Truden, Nachwuchswissenschaftler am Institut für Mathematik, hat sich in seiner Dissertation mit den realen Anwendungsproblemen einer großen englischen Supermarktkette beschäftigt. Die Dimensionen müssen wir uns deutlich größer vorstellen, als sie derzeit im deutschsprachigen Raum gegeben sind: Beispielsweise bilden bei dieser englischen Supermarktkette bis zu 200 Fahrzeuge eine Flotte, die pro Tag rund 3.500 Kund*innen in einem Teil Londons beliefern. Durch die mathematische Brille ergibt sich daraus eine reizvolle wissenschaftliche Herausforderung, nach einem möglichst optimalen Lieferplan zu suchen, nach dem die Kundenbestellungen abgearbeitet werden.

Die mathematische Basis meiner Arbeit ist das so genannte „Problem des Handlungsreisenden“, ein kombinatorisches Optimierungsproblem. Bei der Herausforderung der Supermarktkette kommt hinzu, dass die einzelnen Stationen nicht zu beliebigen Zeitpunkten angefahren werden können, sondern dass die Kund*innen zuhause anwesend sein müssen, um die Waren entgegen zu nehmen. In der Fachliteratur wird diese Herausforderung als „Attended Home Delivery Problem“ beschrieben. Ähnliche praktische Anwendungsfelder finden wir beispielsweise bei Reparaturen, Pflegedienstleistungen oder Lieferservices, die Möbel oder große Elektrogeräte zustellen.

Um das Problem zu beschreiben, möchte ich Ihnen John vorstellen. John lebt in der Chaplin Road im Stadtteil Wembley im Westen Londons. John ist ein vielbeschäftigter Mann, der seine alltäglichen Wege durchwegs mit öffentlichen Verkehrsmitteln beschreitet und sich Supermarkteinkäufe nach Hause liefern lässt. Es ist der 22. Dezember und die Weihnachtsfeiertage nahen mit großen Schritten. Abends, es ist 20:30 Uhr, nimmt John sein Tablet zur Hand, loggt sich auf der Website des Online-Supermarkts ein und stellt seinen großen Weihnachtseinkauf zusammen. John ist bereits registriert und hat seine Wohnadresse dabei angegeben. Wenige Augenblicke muss John warten, bis sich eine Auswahl an Zeitfenstern öffnet, in denen die Zustellung erfolgen kann. Darunter sind Zeiten, die zum Lebensalltag von John passen, und solche, die für ihn ungünstig sind. John entscheidet sich dafür, die Waren am 23. Dezember zwischen 19 Uhr und 20 Uhr zugestellt zu bekommen. Kommen die Waren tatsächlich am nächsten Tag in diesem Zeitraum bei ihm an, ist John zufrieden und kann sich an die Zubereitung des Weihnachtsmahls machen. Ein zufriedener John wird das Service des Zustelldienstes auch das nächste Mal wieder in Anspruch nehmen.

Damit dies alles für John so problemlos und zufriedenstellend funktioniert und damit für die Supermarktkette auch ein wirtschaftlicher Erfolg ist, läuft im Hintergrund ein komplexer technischer Prozess ab. Das Team hat diesen Bestellprozess in vier Phasen eingeteilt: In der ersten Phase erfolgt die taktische Planung des Online-Supermarkts. Die Planenden fragen sich also: Wie viele Fahrzeuge und wie viele Fahrer*innen teile ich wann zum Dienst ein? In der nächsten Phase werden die Zeitfenster ausgewählt, die den Kund*innen zur Verfügung gestellt werden. In der Regel sind dies ein- bis zweistündige Zeiträume.

Danach erfolgt die dritte, für die Mathematiker*innen spannendste Phase: Die Bestellphase. Schon während des Bestellvorgangs soll das System möglichst schnell eine Auswahl von Zeitfenstern errechnen, die der Kund*in angeboten werden können. Sind viele Kund*innen gleichzeitig online, stößt das System an seine Kapazitätsgrenzen. Bei jedem Klick auf den Bestell-Button wird im Hintergrund der Lieferplan so optimiert, dass er immer möglichst viele Bestellungen aufnehmen kann. Dementsprechend stellen sich auch die Optionen auf Lieferzeiten zusammen.

Ungefähr zehn bis zwölf Stunden vor Auslieferung ist der dynamische Teil des Bestellprozesses abgeschlossen und das System hat ein paar Stunden Zeit, um den Lieferplan weiter zu optimieren. Dabei geht es uns nun darum, möglichst kostengünstige Routen zu errechnen. Darüber, wie dieser Vorgang zu möglichst guten Ergebnissen kommt, weiß die Wissenschaft mittlerweile schon sehr viel. Schließlich stellen die Fahrer*innen die Waren in der vierten Phase an ihre Kundschaft zu.

Gehen wir zurück zu John: Er gibt seine Bestellung an einem 22. Dezember abends auf, wie dies viele Menschen so knapp vor Weihnachten gleichzeitig tun und wünscht eine Zustellung am Feierabend des 23. Dezember. Während John auf virtuelle Einkaufstour durch den Supermarkt geht, bestellen auch Anne, Claire, Henry, Jeff und viele andere Londoner*innen ihre Weihnachtseinkäufe. Während John ein paar Millisekunden darauf wartet, dass sich seine Auswahl an möglichen Lieferzeiten lädt, warten auch Anne, Claire, Henry und Jeff. Alle haben Pläne für den Folgetag und brauchen eine gute Auswahl an Zeitfenstern, die gleichzeitig auch für die Zusteller „machbar“ sind. Dieser Schritt ist der Kern von Christian Trudens Forschung.

Heute stehen uns deutlich mehr Datenmengen zur Verfügung, die Rechnerleistung ist günstiger denn je und steht über Clouddienste einfacher und jederzeit zur Verfügung. Dennoch fehlen uns nach wie vor die technischen Kräfte, um stets optimierte Routen zu errechnen, wenn hunderte Fahrzeuge tausende Kund*innen beliefern sollen. In diesen Fällen können wir nicht nach jedem Bestellvorgang optimieren, sondern diesen Vorgang nur stapelweise – vielleicht auch nur nach jeder zehnten oder zwanzigsten Bestellung – durchführen.

Der Suche nach dem optimalen Lieferplan begegnet die Mathematik mit Heuristiken. Wenn wir nur wenig Zeit und eingeschränktes Wissen haben, wählen wir als Menschen instinktiv Lösungswege, die trotzdem zu praktikablen Lösungen führen. Einer Maschine müssen wir diese Kompetenz erst beibringen. Wir bauen also Algorithmen, die in einem sinnvollen Suchraum nach Lösungen suchen. In dem Fall tauscht für uns der Algorithmus einzelne Kund*innen zwischen den Routen aus und berechnet, ob sich dadurch eine Verbesserung für den gesamten Lieferplan ergibt. Kann man in Summe mehr Lieferungen anbieten, wenn man zuerst zu Anne und dann zu Claire fährt, um in der Folge Johns Wohnung anzusteuern oder ist es klüger, zuerst Claires, dann Johns und schließlich Annes Waren auszuliefern? Wir nähern uns schrittweise einem immer besseren Weg an, können dabei aber niemals eine sichere Auskunft darüber geben, wie nah am Optimum unsere Lösung ist. Der Mensch wird durch Erfahrung klüger – dementsprechend besser werden auch unsere menschlichen Heuristiken. Damit wir unsere technischen Heuristiken verbessern können, müssen wir auch aus Einzelfällen lernen. Konkret hat Christian Truden für seine Dissertation ein Detailproblem auf einer bestimmten Route unter die Lupe genommen und dafür eine mathematisch exakte optimale Lösung errechnet. Das Wissen daraus hat ihm dabei geholfen, die bis dahin entwickelten Heuristiken noch weiter zu verbessern. Ein Ergebnis aus meinem Forschungsprozess: Das System kann ein Vielfaches an Zeitfenstern anbieten, als dies mit bisherigen Algorithmen der Fall war. Außerdem können die Mathematiker*innen die Effizienz der Auslieferungsrouten um 10 Prozent steigern. Um diese Werte zu erreichen, brauchen sie allerdings auch viel vom kostbarsten Gut bei diesem Problem: Rechenzeit.

Mit Fragen wie diesen beschäftigen sich Mathematik*innen erst seit kurzem. Die Anzahl der Forschungsgruppen, die weltweit an der Verbesserung solcher Systeme arbeitet, lässt sich wohl an einer Hand abzählen. Mit seiner Dissertation konnte Christian Truden einen Beitrag dazu leisten, dass die englische Supermarktkette ihre Waren kosteneffizient zustellen kann. So wird die Arbeitskraft der Fahrer*innen besser genutzt, diese sind genauso wie die Kund*innen zufriedener und die Kohlendioxidemissionen können bei kürzeren Routen verringert werden. Sind alle zufrieden und profitieren, wird der Lieferdienst auch zu einem nachhaltigen wirtschaftlichen Erfolgsmodell. Gleichzeitig zeigte die Arbeit an dem praktischen Beispiel aber noch viele weitere Herausforderungen auf, die in die Berechnungen mit aufgenommen werden können: Wie kann verhindert werden, dass Lieferautos an den Depots bei der Warenausgabe warten müssen? Wie kann eine Flotte aus verschieden großen und verschieden ausgestatteten Fahrzeugen sinnvoll zusammengestellt werden? In einer Welt, in der immer mehr Waren zugestellt werden, werden den Mathematiker*innen die Fragestellungen nicht ausgehen.