Heute müssen sich die Engel die Routenplanung vornehmen. Schließlich hat das Christkind nur wenige Stunden Zeit. Nimmt es auf dem Weg von Familie Minstrel zu Familie Spillner lieber die Mozart-oder doch lieber die Beethovenstraße? Fährt es überhaupt direkt nach Familie Mustermann zu Familie Spillner oder ist es vielleicht sinnvoll, zwischendrin die Geschenke bei Familie Fuchser abzugeben? Es gibt bei 7 Millionen Haushalten unendlich viele Kombinationsmöglichkeiten.
Unsere bisherigen Themen: Business Analytics allgemein (1), Vergangenes analysieren – Künftiges prognostizieren (2), Assoziationsanalyse (3), Text Analytics / Net Promoter Scores (4), Clusteranalysen (5), Lineare Regression (6), Master Data Management (7), Forecasting (8), Optimierung (9), Textanalyse (10), Entscheidungsbäume (11), Trendanalyse (12), Zusammenfassung des Gelernten (13), Netzwerkanalysen (14), Data Quality Steward (15), Optimierung 2 (16), Prozesskontrolle (17), Predictive Maintenance (18), Scoring (19), Basteln mit SAS9.4 (20), Simulation (21).
Gott sei Dank sind die Auslieferungs- und seine Hilfsengel sehr sehr schlau. Sie wissen schon seit Jahren, dass sie bei der Anzahl an Haushalten und der kurzen Zeit niemals von alleine die perfekte Route für das Christkind aufstellen könnten. Daher verwenden sie einen analytischen Algorithmus.
Routenplanung wie auf der Erde
Die sich ihnen stellende Aufgabe ist das klassische Traveling-Salesman-Problem aus der Optimierung. Klar, hier soll ja eine optimale Route gefunden werden! Ähnlich wie bei der Netzwerkanalyse in Türchen 14, modellieren die Engel zuerst die vorliegende Situation mit einem Graphen. Jeder Haushalt ist dabei ein Knoten. Der Weg des Christkinds von einem zum anderen Haushalt, d.h. die Verbindung dieser beiden Knoten wird in dem Graphen als Kante dargestellt.
Es geht hier aber nicht darum, ob das Christkind von dem einen zum anderen Haushalt gelangen kann – natürlich kann es das – sondern es geht um die Zeit, die es dafür benötigt. Also wird jeder Kante noch ein Gewicht zugeordnet. Dieses Gewicht zeigt an, wie „weit“ die beiden Haushalte voneinander entfernt sind.
Das Ziel der Optimierungsaufgabe ist es nun, mit diesen Informationen den kürzesten Weg für das Christkind zu finden, bei dem es alle Haushalte mindestens einmal besucht. Das Ergebnis einer solchen Optimierung sehen wir im rechten Bild.
Natürlich ist das eine riesige Karte, die die Engel dem Christkind mit auf den Weg geben. Aber die Technik hat auch schon im Himmel Einzug gehalten. Natürlich kann diese Route auch auf ein Navi gespielt werden, das das Christkind dann an seinen Schlitten spannt. Ob das als Vorbereitung genügt, um die Geschenke auf die Erde zu bringen? Das sehen wir morgen.
