Wie der Weihnachtsmann seine Route (umweltbewusst) plant

Ihr werdet es nicht glauben! Der Weihnachtsmann war gerade in unserem Büro. Ja, der echte Weihnachtsmann. Und ich kann euch sagen, er sieht wirklich so aus, wie man ihn sich vorstellt: ein rundlicher, freundlicher alter Mann mit weißem Rauschebart und in rot-weißem Gewand.

Wie sich herausstellte, hat auch er die Zeichen der Zeit erkannt: Der Weihnachtsmann möchte seinen CO2-Fußabdruck verbessern. Der Futterverbrauch seiner Rentiere und deren Überstunden machen ihm auch zu schaffen. Und genau deswegen ist er zu adesso gekommen – davon erzähle ich euch nun!

So lachte uns der Weihnachtsmann entgegen: „Hohoho! Wie ihr wisst, fliege ich jedes Weihnachten rund um die Welt und verteile Unmengen an Geschenken.“ Und klagte im gleichen Zuge: „Das ist ein Aufwand, sage ich euch … und es frisst auch einiges an Ressourcen. Das Rentierfutter wird immer teurer, mein Schlitten ist auch nicht mehr der Jüngste. Die Abgase sind da nicht ohne, müsst ihr wissen. Es muss sich einfach etwas ändern!“

Das kannten wir aus unserem Beratungsalltag nur allzu gut und sofort war die Neugierde geweckt: „Oh ja, die Sorgen haben gerade viele. Was siehst du für Möglichkeiten?“, fragten wir den Weihnachtsmann.

Den Weihnachtsmann schien seine Situation schon länger zu beschäftigen, denn er antwortete geschwind und ausführlich: „Das Problem ist, dass ich effizienter reisen muss. Einfach kostengünstiger! Denn sonst müssen die Geschenke kleiner ausfallen – und das geht doch nicht. Jedes Jahr denke ich mir: Ist das wirklich die beste Route? Gibt es keine kürzere mit weniger Strecke? Dabei ist klar: Eine Stadt auslassen und somit weniger Menschen zu beschenken, das ist keine Option!“

Unser Team wurde hellhörig, denn das klang nach einem Planungsproblem, bei dem wir mit unseren Analytikmethoden helfen können: „Okay, wir kommen der Sache näher. Wie genau sieht deine Planungsaufgabe in der Weihnachtsnacht aus?“

Seinen Arbeitsalltag zu erläutern, fiel dem Weihnachtsmann nicht schwer: „Ausgehend von meiner Basis am Nordpol habe ich mehrere hundert Orte anzufliegen, quer über den Globus verteilt. Dort entlade ich jeweils ein paar Säcke an Geschenken, die dann von meinen Elfen vor Ort verteilt werden“, erläuterte er uns. „Ich frage mich: In welcher Reihenfolge sollte ich meine Ortsliste abfliegen, sodass meine Rundtour so kurz wie möglich ausfällt? Jede eingesparte Flugmeile ist da wertvoll für meinen Geldbeutel und das Klima. Und meinen Rentieren täten weniger Überstunden auch mal gut.“

Für uns stand die Sache fest: Das klang nach einem unserer Lieblingsprobleme – nein, nicht „Problem“ im Sinne von Sorgen oder Unannehmlichkeiten. Ganz im Gegenteil – im Sinne von Aufgabenstellung, die wir mit der richtigen KI-Technologie meistern können: „Weihnachtsmann, damit beschreibst du ein sehr bekanntes Optimierungsproblem! Wir nennen es das Travelling Salesman Problem (TSP).“

„Nur dass ich nichts verkaufe, sondern die Menschen beschenke ...“, fügte der Weihnachtsmann bestimmt hinzu, denn er schien sich nicht verstanden zu fühlen.

Unbeirrt erwiderten wir: „Ja klar! Aber die Problemstellung ist dieselbe: Gesucht wird die kürzeste Rundreise durch eine Menge von Orten auf der Landkarte.“ Schnell kramten wir unsere Laptops heraus und modellierten ein kleines Rundreiseproblem über die sieben Kontinente zur Veranschaulichung. Bei 7 Kontinenten ergeben sich 360 mögliche verschiedene Routenkombinationen für die Routenplanung! Da kann man schon den Überblick verlieren und weiß gar nicht so recht, ob die gerade gewählte Route auch die beste ist. Wir kamen mit unserer Methode jedoch recht genau auf eine Lösung und wussten, dass das die beste Lösung ist! „Schau, lieber Weihnachtsmann! Bei dieser Beispielroute, bestehend aus jeweils nur einem Anflugspunkt auf den 7 Kontinenten, ist genau diese Route die kürzeste und damit sparsamste für deine Ressourcen! Die kürzeste Gesamtstrecke hat somit nur 53.377,43 Flugmeilen!“

„Ja! Genau das!“ Der Weihnachtsmann war wieder mit uns auf einer Wellenlänge und fügte hinzu: „Heißt das, ihr könnt mir sagen, wie effizient ich gerade fliege, oder noch besser, wie ich tatsächlich wirtschaftlicher und so umweltfreundlich wie möglich die Geschenke verteile?“

„Wie planst du denn bisher deine Route? Sagen wir, du hast diese 50 Orte abzufliegen.“ Wir malten ein paar Punkte auf das Whiteboard. „Und du startest hier oben rechts an dem roten Punkt. Wie wäre dann deine Route?“ Wir reichten dem Weihnachtsmann den Stift an und deuteten auf die Punkte am Whiteboard.

Der Weihnachtsmann nahm den Stift und begann zu malen. „Eigentlich optimiere ich schon so gut es geht – glaube ich zumindest. Haben wir an einem Ort die Geschenke abgeladen, machen sich meine Rentiere wieder abflugbereit. In der Zeit schaue ich nach, welcher Ort uns am nächsten liegt, d. h., zu dem wir also den kürzesten Flugweg haben. Und genau den steuern wir dann an.“

Da haben wir es: Optimierungspotenzial! Wir erklärten: „Oh, das ist ein heuristisches Vorgehen. Wir nennen es ein simples Greedy-Verfahren. Gierig nimmst du jeweils den nächstgelegenen Standort. Das mag in dem Moment sinnvoll erscheinen, aber in der Gesamtsicht ist es alles andere als optimal. Du siehst zum Beispiel auch, dass die Flüge gegen Ende der Tour länger werden.“

„Da habt ihr allerdings recht!“, seufzte der Weihnachtsmann. „Gegen Ende der Tour murrt die Schlittenmannschaft immer ganz schön aufgrund von teilweise sehr langen Flugstrecken. Aber was soll ich auch machen? Es sind mit der Zeit immer weniger Orte noch anzufliegen, da werden die Strecken automatisch länger, oder etwa nicht?“ Der Weihnachtsmann wirkte resigniert, schöpfte dann wieder Hoffnung: „Wie sieht eure Lösung aus? Um wie viel besser kann ich werden, wie viel Ressourcen kann ich einsparen?“

Wir empfahlen dem Weihnachtsmann, sich kurz einen Kakao zu holen. In der Zeit übertrug unser Team die Punkte vom Whiteboard in Geokoordinaten und wir starteten unseren Algorithmus zur optimalen Routenplanung. Mithilfe von Gapzero dauerte es nur wenige Sekunden zur Formulierung und Berechnung der Lösung: „Weihnachtsmann, wir haben die beste Route!“, riefen wir in Richtung Lounge. Der Mann mit dem weißen Bart kam herbeigeeilt und hörte uns gespannt zu.

„16 % – das kannst du an Strecke einsparen.“ Wir präsentierten die Ergebnisse:

Nearest-Neighbor-Heuristik: 82.541 Flugmeilen (links) und eine um 16 % effizientere Optimallösung mit 69.417 Flugmeilen (rechts)

„Das sind über 13.000 Flugmeilen weniger – Wahnsinn!“, staunte der Weihnachtsmann nicht schlecht. Wir entgegneten: „Wir können dir sogar versichern, dass keine bessere Route als diese hier existiert. Und es gibt eine Menge möglicher Rundreisen durch 50 Orte. Das Stichwort lautet ganzheitliche Optimierung.“

Der Weihnachtsmann war etwas überfordert: „Heilige Nacht, das hört sich kompliziert an! Könnt ihr mir auch meine Route für alle Städte und Orte der Welt optimal planen?“

Unsere Antwort viel einstimmig aus: „Na klar, das ist kein Problem.“

Fazit

Das Planungsproblem vom Weihnachtsmann – unter Berücksichtigung von verschiedenen weiteren Bedingungen, die wir vorher angeschaut haben – ist nur eins von vielen Optimierungsproblemen, die wir mit intelligenten Lösungen meistern können. Dieses spezielle Feld, in dem es um die Lösung von Optimierungsproblemen geht, ist die sogenannte Präskriptive Analytik. In der Präskriptiven Analytik streben wir die Ermittlung von optimalen Handlungsempfehlungen für komplexe Realsituationen an. Anders ausgedrückt: Wir wollen die optimalen nächsten Schritte für ein schwieriges bzw. komplexes Entscheidungs- oder Planungsproblem ermitteln und konkret aufzeigen, sodass wir direkt in die Umsetzung gehen können. Dabei möchten wir wissen, ob wir unsere Zielstellung, inklusive der Nebenbedingungen, die wir dabei beachten müssen, erreichen werden.

Durch eine Übertragung unseres Realproblems in ein mathematisches Modell ist es uns möglich, komplexe Problemstellungen zu lösen. Denn mit einem mathematischen Modell können wir unsere Problemstellung konkret quantifizieren und verschiedene Handlungsalternativen vergleichen bzw. überhaupt erst einen Einblick gewinnen, welche Möglichkeiten uns zur Verfügung stehen. Der Wissenszweig, der sich konkret mit solchen mathematischen Problemlösungsmodellen beschäftigt, nennt sich Operations Research oder auch Management Science. Hier setzt man sich mit der mathematischen Formulierung von Realproblemen hinsichtlich Entscheidungs- oder Planungsproblemen auseinander. Darüber hinaus werden auch Computerprogramme (Algorithmen) entwickelt, die die Berechnung von komplexen Modellen ermöglichen.

Die Präskriptive Analytik unterscheidet sich von der Prädiktiven Analytik insofern, als dass Letztere sich mit der Datenanalyse zu Prognosezwecken befasst. Also zum Beispiel hinsichtlich der Frage nach „Was wird morgen sein?“ (zeitbezogene Abfrage) oder „Welches Tier sehe ich gerade auf dem Bild?“ (sensomotorische Abfrage) mit dem Ziel, solche Fragen so gut wie möglich quantifiziert zu beantworten.

Außer der Routenplanung für den Weihnachtsmann gibt es viele weitere Anwendungsfälle. Um noch ein paar Beispiele zu nennen: Gepäcksteuerung an Flughäfen, Produktionsplanung in der Stahlindustrie, Stundenplanung, Seeweglogistik in der Automobilindustrie, Kraftwerkseinsatzplanung, Synthese dezentraler Energiesysteme oder sogar die Wahlkreiseinteilung in Deutschland.

Ich hoffe, ich konnte euch mit dem Beispiel vom Weihnachtsmann die Besonderheiten dieser analytischen Lösung etwas näherbringen!

Diese Blog-Beitrag wurde in Zusammenarbeit mit der gapzero mathematical decision support GmbH verfasst.

Weitere spannende Themen aus der adesso-Welt findet ihr in unseren bisher erschienenen Blog-Beiträgen.