Mathematik und Tourenoptimierung auf der letzten Meile: wo Theorie und Praxis aufeinanderprallen
- 30 Mai 2022
- 3 mins
Cédric Hervet ist der wissenschaftliche Leiter des von ihm im Jahr 2015 mitbegründeten Tech-Startups Kardinal, das sich der Transport- und Logistikbranche verschrieben und eine auf innovativen Algorithmen basierende Lösung zur Tourenoptimierung entwickelt hat. Das Unternehmen Kardinal hat sich zum Ziel gesetzt, der technologische Marktführer für intelligente Logistik zu werden.
Einführung
In zahlreichen Unternehmen, deren geschäftliche Tätigkeit die Beförderung von Waren oder Personen voraussetzt, gestaltet sich die Tourenoptimierung als bedeutsame Herausforderung. Von der Paketzustellung über Wartungs- und Reparaturarbeiten bis hin zur ambulanten Pflege und Haushaltshilfe gestaltet sich die Tourenoptimierung in einer Vielzahl von Situationen als Mittel der Wahl.
In diesem Artikel möchte ich Ihnen die verschiedenen Techniken zur Tourenoptimierung vorstellen und veranschaulichen, welche Probleme die klassischen Ansätze mit sich bringen – und wie wir bei Kardinal versuchen, diese Defizite zu beheben.
TEIL I: Tourenoptimierung oder die Suche nach der Nadel im Heuhaufen?
Anhand der folgenden Situation lässt sich die Komplexität der Tourenoptimierung leicht erfassen: Stellen Sie sich vor, dass Sie einen Tourenplan mit 100 anzufahrenden Lieferpunkten erstellen sollen. Ihnen stehen fünf Fahrer zur Verfügung, auf die diese sich allesamt in derselben Stadt befindlichen Lieferpunkte verteilt werden müssen. Ihr Ziel ist es, den „richtigen“ Fahrern die „richtigen“ Lieferpunkte in der „richtigen“ Reihenfolge zuzuweisen und dabei die „optimalen“ Touren zu erhalten.
Intuitiv könnten Sie sich nun zunächst den geografischen Standort des ersten Fahrers ansehen und ihm den nächstliegenden Lieferpunkt zuweisen. Daraufhin ordnen Sie ihm nach und nach die jeweils nächstgelegenen Punkte zu, bis sein Fahrplan vollständig ausgefüllt ist.
Nach dem gleichen Prinzip gehen Sie für die übrigen Fahrer vor, bis schließlich alle Lieferpunkte verplant sind. Wenn Ihnen eine Karte vorliegt, auf der alle zu berücksichtigenden Lieferpunkte angezeigt werden, geht die Planung vermutlich sogar relativ schnell vonstatten. Anschließend müssen vielleicht noch ein paar Anpassungen durchgeführt werden und schon sind Ihre Touren fertig.
War’s das also schon? Sind ein bisschen gesunder Menschenverstand und eine Karte alles, was man für die Tourenoptimierung benötigt?
So einfach ist es leider nicht. Und das hat zwei Gründe:
- Unser Beispiel ist zum einen extrem vereinfacht und vernachlässigt zum anderen einen bedeutungsschweren Parameter bei der Tourenoptimierung: die Einschränkungen. Es gibt keine Branche, die nicht mit spezifischen Einschränkungen und Besonderheiten zu kämpfen hat. Im obigen Beispiel wären das: Fahrzeugkapazitäten, Gewicht und Größe der Sendungen, die einzuhaltenden Lieferzeitfenster, Verkehrsverhältnisse und Staus, abwesende Kunden, die einen zweiten Zustellversuch seitens des Fahrers erfordern etc.
- Die Gesamtzahl der verschiedenen möglichen Touren ist so groß, dass es nahezu unmöglich ist, die optimalen Touren über den oben beschriebenen Prozess zu finden. Es ist sogar überaus wahrscheinlich, dass Ihre Planung mit dieser Technik mehr als suboptimal ausfällt.
Nun könnten Sie natürlich einwenden, dass die Tourenplanung nicht Ihr Job ist und ein erfahrener Planer es weitaus besser machen würde – und Sie hätten recht. Doch auch die von einem Experten manuell ausgearbeitete Lösung wäre noch weit vom Optimum entfernt. Dies ist nicht verwunderlich: Das überaus komplexe mathematische Problem der Tourenoptimierung ist selbst für die leistungsfähigsten Computer nur schwer zu lösen.
Stellen Sie sich einen Fahrer vor, der N Lieferungen durchführen muss. Sämtliche dieser Touren beginnen und enden im Lager. Wenn wir versuchen, die Gesamtzahl der möglichen Touren zu zählen, stellen wir fest: Für den ersten Stopp gibt es N Möglichkeiten, für den zweiten N-1 Möglichkeiten, N-2 für den dritten und so weiter bis zum Ende. Die Gesamtzahl der möglichen Touren beträgt also 1 x 2 x 3 x 4 x … x N.
Und das ist eine ganze Menge.
Die folgende Tabelle zeigt die Anzahl der möglichen Touren in Abhängigkeit von der Anzahl der anzufahrenden Punkte und wie lange ein normaler Computer ungefähr benötigen würde, um alle möglichen Touren zu ermitteln und unter ihnen die beste zu finden:
Anzahl der anzufahrenden Punkte
10
15
20
Anzahl der möglichen Touren
1.31 x 10^12
Rechenzeit
< 1 Sekunde
mehrere Stunden
2.000 Jahre
Um durch einen Fahrer 25 Zustellungen durchführen zu lassen (was an einem Tag vielfach vorkommt), sind so viele verschiedene Touren möglich, wie es Sandkörner auf der Erde gibt. Und wir sind noch weit von unserem Beispiel mit 5 Fahrern und 100 Haltepunkten entfernt, das sich ohne Miteinbeziehung aller bei der Planung zu beachtenden Einschränkungen bereits stark vereinfacht gestaltet.
Die besten Touren zu ermitteln, ist selbst in einfachen Zusammenhängen so schwierig, wie eine winzige Nadel in einem monströs großen Heuhaufen zu finden.
Für ein menschliches Gehirn ist diese Aufgabe nahezu unmöglich zu bewerkstelligen und bleibt selbst für die leistungsfähigsten Computer eine immense Herausforderung.
Der Autor
Cédric Hervet ist der Chief Product Officer Leiter des von ihm im Jahr 2015 mitbegründeten Tech-Startups Kardinal, das sich der Transport- und Logistikbranche verschrieben hat. Als Doktor der Mathematik erforscht und entwickelt er seit über 10 Jahren Systeme der Künstlichen Intelligenz für industrielle Anwendungen in den Bereichen Telekommunikation, digitales Marketing und Transport.
