Optimale Tourenplanung auf Knopfdruck

Optimale Tourenplanung auf Knopfdruck

Einfach umsetzen bereits mit mathematischen Basics

Aktuell wird sehr viel darüber gesprochen, dass wir alle viel mehr, vor allem fossile Energie einsparen müssen. Und auch wenn es natürlich die großen Betriebe sind, deren Anstrengungen am meisten ausmachen, können auch Maßnahmen im kleinen Rahmen mit ihren Einsparungen ihren Teil beitragen. An einem (zugegeben stark vereinfachten) Beispiel zeigen wir, wie beispielsweise im Bereich der Tourenplanung auch in kleinen Betrieben mit mathematischer Optimierung gespart werden kann.

Touren werden vielfach noch auf Basis von Erfahrungswerten, also wie man so schön sagt, aus dem Bauch heraus geplant. Am Beispiel eines innerstädtischen Lieferservices wollen wir zeigen, wie man bereits mit einem einfachen mathematischen Modell Touren optimieren, Benzinkosten und CO2-Emissionen senken und strategische Entscheidungen simulieren kann (Szenarien). Fangen wir jedoch bei der Tourenoptimierung an.

Unser Beispiel

Unser Lieferservice beliefert seine Kunden täglich und nutzt dafür eine Flotte von Motorrollern, um im innerstädtischen Verkehr schnell voran zu kommen. Die Fahrer sind allesamt langjährig beim Unternehmen beschäftigt und verfügen über große Erfahrung. Daher planen Sie ihre Touren weitgehend selbstständig. Allerdings zeigt die monatliche Abrechnung der Tankquittungen und Fahrtenbücher, dass die Benzinkosten des Lieferdienstes enorm hoch sind. Die Touren sollen daher künftig zentral geplant werden. Eine manuelle Planung ist jedoch nicht nur zeitaufwändig, sondern man kann auch nicht sicher sein, dass die Planung auch ein optimales Ergebnis liefert.

Mit mathemathischer Optimierung kann man das jeweils beste Ergebnis in kurzer Zeit finden. Unser Lieferservice lässt sich auf das Experiment ein und testet die automatische Planung der Touren.

Viel gespart mit wenig Aufwand

Schon mit einem einfachen Optimierungsmodell lassen sich sehr schnell Erfolge erzielen, ganz im Sinne des sprichwörtlichen Pareto-Prinzips, laut dem man mit 20% des Aufwands bereits 80% des Erfolgs generieren kann. Das trifft insbesondere auf das aktuelle Beispiel der Tourenplanung zu, denn die Fragestellung ist recht übersichtlich und kann daher mit einer sehr einfachen Modellierung dargestellt werden.

Die Grafik zeigt beispielhaft die Routen eines Tages, wie sie bisher beim Lieferservice gefahren wurden.

Das Problem der Tourenplanung erfüllt die beiden zentralen Voraussetzungen, um durch eine mathematische Optimierung lösbar zu sein:

  1. Punkt: Man kann für einen konkreten Tourenplan ausrechnen, wie teuer er ist;
  2. Punkt: Man kann alle wichtigen Zusammenhänge, die einen Tourenplan ausmachen, aufschreiben.

 

Eine mathematische Optimierung geht, allgemein gesprochen, immer wie folgt vor:

  • sie entwickelt eine beliebige gültige Lösung, in diesem Fall einen Tourenplan;
  • sie rechnet aus, wie teuer die Lösung ist;
  • sie sucht eine andere Lösung, die günstiger ist.

 

Leider gibt es derart viele mögliche Lösungen, dass man sie unmöglich alle durchzählen kann. Glücklicherweise übernimmt diese Aufgabe Spezialsoftware, ein sogenannter Solver, der mit allen Tricks aus Wissenschaft und Praxis arbeitet, um möglichst geschickt und zielgerichtet nach den besten Lösungen zu suchen.

Interessieren Sie sich für unser Factsheet?

Mathematische Optimierung
für bessere Entscheiungen

Die Suche übernimmt der Solver

Das Ziel der Routenplanung ist klar: die Länge aller Touren des Tages sollen so klein wie möglich gehalten werden. Das Ziel der Optimierung ist also:

Dazu benötigt man insbesondere die Entscheidung darüber, was eine Route überhaupt ausmacht.

Ein echtes Optimierungsmodell beschreibt diesen Zusammenhang mathematisch. Dazu werden natürlich ein paar Daten als Parameter benötigt.

Als erstes gilt es, für jede mögliche Verbindung zwischen den Orten auf der Karte herauszufinden, ob sie Teil einer Tour sind oder nicht. Mathematisch entspricht das einer binären Variable, die also entweder den Wert „ja, das ist so“ (numerisch 1) oder „nein, so ist das nicht“ (numerisch 0) annehmen kann.

Mit der Distanz zwischen zwei Orten kann man die Zielfunktion auch mathematisch formulieren:
Die „Kosten“ einer konkreten Entscheidung entsprechen damit der gesamten Länge aller Routen. Ist eine Verbindung zweier Orte nicht Teil einer Route, ist die Entscheidungsvariable für dieses Stück 0 und damit spielt die Distanz zwischen diesen Orten in der Zielfunktion keine Rolle. Nun könnte man schon die kürzeste und damit günstigste Route berechnen lassen. Doch bisher ist erst Punkt 1 bearbeitet: Es können Touren bewertet werden, indem man ihnen Kosten zuordnet. Genauso wichtig ist jedoch Punkt 2: Es müssen alle relevanten Zusammenhänge formuliert werden. Und damit die Frage, was macht eine Tour eigentlich aus? Man könnte meinen, es sei doch ganz klar, was eine Tour ausmacht. Grundsätzlich stimmt das natürlich schon, aber ein mathematisches System tut nur, was man ihm sagt – alle Selbstverständlichkeiten müssen daher präzise erfasst werden. Es sind also folgende Randbedingungen zu beachten:
Den Punkt C5 – eine dieser Selbstverständlichkeiten – kann man noch um ein weiteres Ziel ergänzen: Muss man wirklich immer alle Roller einsetzen?
Mathematisch betrachtet mag es bessere Formulierungen geben, doch für einen Testlauf des aktuellen Problems ist das erst einmal ausreichend.

Weitere interessante Beiträge

Mathematische Optimierung ist ein idealer Ansatz, um innerhalb kürzester Zeit die besten Ergebnisse für eine optimale Standortplanungsstrategie zu erzielen.

Weiterlesen »

Der Trend zur Individualisierung erschwert die Arbeit für Produktionsplaner*innen. Wir zeigen, wie auch in kleinen Losgrößen rentabel produziert werden kann.

Weiterlesen »

Wer denkt, dass Operations Research nur etwas für Mathematiker ist, irrt. Angewandte Mathematik in Form von OR begegnet uns täglich…

Weiterlesen »

Das Modell ist schon die halbe Miete

Ist das Modell erst da, geht der Rest sehr schnell. Die Kunden- und Bestelldaten liegen als Tabellen vor und können einfach übernommen werden. Dank der OPTANO Plattform kann das Modell in Null Komma nichts umgesetzt werden und zum ersten Mal eine automatische Tourenplanung gestartet werden.



manuelle Planung

Basisplanung

Differenz

Anzahl der
Touren

14

9

5

Länge der
Touren

525,50 km

413,47 km

112,04 km

Kosten pro
Tag

17,34 €

13,64 €

3,70 €

Kosten pro
Jahr

6329,70 €

4980,20 €

1349,50 €

Anzahl der Touren

Manuelle Planung

 14

Basisplanung

9

Differenz

5

Länge der Touren

Manuelle Planung

525,50 km

Basisplanung

413,47 km

Differenz

112,04 km

Kosten pro Tag

Manuelle Planung

17,34 €

Basisplanung

13,64 €

Differenz

3,70 €

Kosten pro Jahr

Manuelle Planung

6329,70 €

Basisplanung

4980,20 €

Differenz

1349,50 €

Und nach einigen Monaten zeigt sich auch in der Realität: Die Spritkosten sind deutlich zurückgegangen, seitdem die Touren jeden Morgen automatisch geplant werden.

Natürlich handelt es sich hierbei nur um eine sehr abstraktes und theoretisches Beispiel. Wir haben aber über die Jahre die Erfahrung gemacht, dass durch Optimierung solcher Problemstellungen fast immer erhebliche Einsparungen zu erreichen sind. Zusätzlich kann man bei Bedarf auch noch die Minimierung des CO2-Ausstoßes als Zielsetzung hinzufügen und diese zusätzlich optimieren. Es gibt viele Möglichkeiten Energie sparen, nutzen wir sie! Mit OPTANO lassen sich natürlich auch noch sehr viel komplexere Szenarien und Problemstellungen optimieren. Wir beraten Sie gern, ob sich der Einsatz von mathetischer Optimierung für ihren Betrieb lohnt. Sprechen Sie uns einfach an.

Kennen Sie schon unser Factsheet zum Thema?

Mathematische Optimierung für Tourenplanung ist schon mit einfachen Mitteln umzusetzen und erreicht erstaunliche Einsparungen! Unser Factsheet bietet eine Übersicht über Einsatzmöglichkeiten, inkl. der mathematischen Formeln und möglichen Erweiterungen.

Um dieses Factsheet zu erhalten, müssen Sie nur Ihre Kontaktdaten in das untenstehende Formular eintragen. Es öffnet sich dann ein Pop-up-Fenster zum Downloaden des Whitepapers. Bitte beachten Sie, dass Sie mit der Angabe Ihrer E-Mail-Adresse zustimmen, dass wir Sie zu diesem Thema kontaktieren dürfen. Sie können diese Zustimmung jederzeit widerrufen, indem Sie sich an datenschutz@optano.com wenden.

Sabrina Geismann
Sabrina Geismann

Haben Sie Fragen?

Dr. Sven Flake
Analytics Senior Consultant