Optimale Tourenplanung auf Knopfdruck
bereits mit mathematischen Basics

Wie hilft mathematische Optimierung bei der Planung von Touren und für welche zusätzlichen Benefits kann sie verwendet werden? Damit beschäftigen wir uns in unserer neuen Miniserie zur Tourenplanung.

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.

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.

Interessiert an allen Formeln dieses mathematischen Modells?

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

  • Punkt 1: Man kann für einen konkreten Tourenplan ausrechnen, wie teuer er ist;
  • Punkt 2: 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.

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:

  • (T1) Die Summe der Länge aller Routen soll so klein wie möglich sein.

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.

  • (D1) Die Verbindung zweier Orte auf der Karte ist entweder Teil einer Tour oder sie ist es nicht.

Mit der Distanz zwischen zwei Orten kann man die Zielfunktion auch mathematisch formulieren:

  • (T1) Die Summe der Länge aller Routen soll so klein wie möglich sein. Es werden also alle Distanzen genau dann aufsummiert, wenn die Verbindung zwischen den Orten Teil der Route ist (die Entscheidungsvariable also den Wert 1 hat).

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:

  • (C1) Jeder Kunde wird von genau einem Fahrer angefahren
  • (C2) Der Fahrer verlässt den Kunden auch wieder
  • (C3) Alle Fahrer, die eingesetzt werden, beginnen ihre Tour in der Zentrale
  • (C4) Alle Fahrer, die eingesetzt werden, beenden ihre Tour in der Zentrale
  • (C5) Es können nicht mehr Fahrer gleichzeitig eingesetzt werden, als Motorroller zur Verfügung stehen
  • (C6) Jede beliebige Auswahl an Kunden wird von genug Fahrern angesteuert, um den Bedarf der ausgewählten Gruppe zu decken

Den Punkt C5 – eine dieser Selbstverständlichkeiten – kann man noch um ein weiteres Ziel ergänzen: Muss man wirklich immer alle Roller einsetzen?

  • (D2) Wie viele Fahrer müssen tatsächlich eingesetzt werden

Mathematisch betrachtet mag es bessere Formulierungen geben, doch für einen Testlauf des aktuellen Problems ist das erst einmal ausreichend.

Das Modell ist mehr als nur 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.

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.

  • Anzahl der Touren
  • Keine Planung
  • Basisplanung
  • Differenz
  • Anzahl der Touren
  • 14
  • 9
  • 5
  • Tourlänge
  • 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 €