Grundlagen der Tourenoptimierung: Die Herausforderung die optimale Route zu finden

Tourenplanung ist ein wichtiger Teil der Einsatzplanung von Servicetechnikern, die ein größeres Gebiet abdecken. Durch eine möglichst optimale Reiseroute und Reihenfolge der Termine lässt sich viel Zeit und somit auch Geld sparen. Doch je mehr Einsätze pro Tag einzuplanen sind und je mehr Techniker ein Disponent in seinem Team hat, desto komplexer wird die Erstellung einer effizienten Route.

Das, was landläufig als optimale Tourenplanung oder Tourenoptimierung bezeichnet wird, ist in der Mathematik bzw. Informatik als Vehicle Routing Problem (VRP) bekannt.
Eine etwas bekanntere Ableitung ist als "Problem des Handlungsreisenden" bekannt. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass

  • keine Station außer der Ersten mehr als einmal besucht wird
  • die erste Station gleich der letzten Station ist
  • die gesamte Reisestrecke möglichst kurz ist

Acht Städte - 40.320 mögliche Routen

Am Beispiel einer Reise durch acht Städte in Deutschland lässt sich das Problem veranschaulichen. Ausgangs- und Zielort ist München, bereist werden die Städte:

● München (Ausgangs- und Zielort)● Erfurt
● Berlin● Hamburg
● Dresden● Hannover
● Düsseldorf● Stuttgart

Es gibt über 40.000 verschiedene Möglichkeiten (Reihenfolgen) die sieben Städte zu bereisen - aber welche ist die kürzeste?

Rein mathematisch lässt sich das Problem durch die Fakultät von 8 (als Mathematischer Ausdruck 8!) beschreiben. Das heißt um acht Städte zu bereisen gibt es 40.032 mögliche Reihenfolgen.

Planungsvorschlag 1 - Immer zur nächstgelegenen Stadt

Ein relativ einfacher Ansatz zur Lösung ist, von jeder Stadt aus zur unmittelbar nächstliegenden Stadt, die noch nicht besucht wurde, zu reisen.

Ein einfacher Ansatz zur Berechnung der optimalen Route: Von jedem Ziel zum nächstgelegenen Ziel fahren, das noch nicht besucht wurde.

Im Bild wird dieser Ansatz durch Umkreissuche illustriert, um den jeweils nächsten Zielort zu finden.

Das Ergebnis der Planung – nicht optimal!

Führt man diese Methode fort, erhält man am Ende diese Route:

Sich kreuzende Routen sind häufig ein Indikator für eine nicht optimale Planung.

Dass dieses Ergebnis nicht optimal ist, sieht man auf den ersten Blick – vor allem anhand der sich überschneidenden Routen. Die für dieses Szenario optimale Route sieht folgendermaßen aus:

Die optimale Tour für den Techniker ist um etwa 17% kürzer als der erste Vorschlag.

In Summe ergibt sich eine Effizienzsteigerung von 17% durch die optimale Route.

Vergleich der Fahrleistung zwischen dem ersten Planvorschlag und der optimalen Route.

Mehr Servicetechniker - mehr Optionen

Fügen wir dem Ausgangsproblem nun zwei weitere Kollegen in Magdeburg und Bielefeld hinzu, steigt die Anzahl der möglichen Kombinationen um ein Vielfaches. Mathematisch ist dieses Problem als „Tourenplanungs-Problem mit mehreren Standorten und fixierten Zeitfenstern“ bekannt, bzw. auf Englisch Multi-Depot Vehicle Routing Problem with Time Windows, abgekürzt MDVRPTW.

In der Erweiterung des Problems werden zusätzliche Techniker in Bielefeld und Magedeburg ergänzt.

Löst man das Problem analog zum ersten Vorgehen – Reise zum nächstgelegenen Zielort, der noch nicht besucht wurde, ergibt sich spätestens nach dem zweiten Einsatz die Frage, welcher der drei Techniker drei Aufträge übernehmen muss, während seine Kollegen nur zwei Vorgänge zu erledigen haben. Wir gehen an dieser Stelle der Einfachheit halber davon aus, dass alle Aufträge gleich lang dauern und inklusive Fahrtstrecke an einem Arbeitstag erledigt werden können.

Durch diese Erweiterung wird die Aufgabenstellung komplexer. Wir nähern uns wieder mit dem gleichen Ansatz wie zuvor.

Wer muss mehr arbeiten?

Die Entscheidung, wer den dritten Auftrag übernehmen muss, wird in diesem Szenario zwischen den Monteuren aus Bielefeld und Magdeburg getroffen, wenn sie jeweils bei ihrem zweiten Auftrag in Erfurt bzw. Hamburg sind. Da die Fahrtstrecke von Erfurt nach Berlin kürzer ist, als von Hamburg nach Berlin, muss der Kollege aus Magdeburg den Auftrag übernehmen.

Nach diesem Ansatz muss einer der Mitarbeiter muss vier Aufträge übernehmen.

Daraus ergeben sich drei in sich abgeschlossene Routen ohne Überschneidungen. Die Lastenverteilung ist relativ gerecht, auch wenn der Münchener Techniker mehr als doppelt so viel fahren muss wie sein Kollege aus Bielefeld:

Eine gerechte Lastenverteilung ist in dieser Konstellation kaum zu erreichen.

Sieht optisch gut aus, aber ist das auch optimal?

In Punkto Gesamtfahrleistung ist dieser Planungsvorschlag allerdings wieder nicht optimal, vor allem, weil der Münchener Techniker die weite Strecke von Stuttgart nach Düsseldorf fahren muss.

Der optimale Planvorschlag für dieses Szenario.

Eine deutlich kürzere Gesamtstrecke ist möglich, wenn der Münchener Techniker nur den Auftrag in Stuttgart erledigt und danach wieder zurückkehrt.

Dieser Planvorschlag ist in Bezug auf die Wirtschaftlichkeit (gemessen an der Fahrtstrecke) um etwa 15% effizienter als der erste Planvorschlag.

Der Planvorschlag ist um ca. 15% effizienter.

Allerdings führt dieser Planvorschlag zu einer noch deutlicheren Ungleichverteilung unter den Ressourcen: So fährt der Münchener Techniker nur die Hälfte der Wegstrecke seiner beiden nördlichen Kollegen.

Nach wie vor ist die Arbeitslast nicht gerecht verteilt.

Dieses theoretische Szenario zeigt grundsätzlich die Komplexität der Herausforderung „optimale Tourenplanung“ auf. Allein schon bei nur acht Aufträgen und drei Technikern ergeben sich mehrere 10-Tausend Kombinationsmöglichkeiten, die kein Mensch im Kopf berechnen kann.

In der Praxis wird die Planung durch viele andere Kriterien zusätzlich erschwert: Hier gibt es zeitlich fixierte Aufträge, festgelegte Reaktionszeiten, Abhängigkeiten und vieles mehr, das es bei der Planung zu berücksichtigen gilt.

Diese Einschränkungen reduzieren zwar die Anzahl der möglichen Reihenfolgen erheblich, gleichzeitig erschweren die zusätzlichen Kriterien die Berechnung der „optimalen“ Tour für einen Menschen.

Unser Beispiel ist stark vereinfacht - in der Praxis kommen viele andere Kriterien hinzu, die die Planung weiter einschränken.

Eine Software zur Einsatzplanung, wie SAP MRS oder alternative Lösungen, unterstützt den Disponenten bei der Einsatzplanung. Eine Software kann in Sekunden Millionen von Tourenkombinationen miteinander vergleichen und so mit hoher Treffsicherheit eine möglichst ideale Route finden.

Mehr zur Herausforderung, die optimale Tour zu planen finden Sie in unserem Ratgeber Tourenplanung im Außendienst.

Kommentar hinterlassen

Weitere Blogeinträge

Veranstaltungen

  • 6. Treffen der mobileX User Group

    Am 16. und 17. Oktober 2019 findet im Courtyard by Marriott München City Ost das 6. Treffen der mobileX User Group statt, zu dem wir Sie gerne einladen möchten.Dieses Jahr widmen wir uns dem Motto:"Field Service Management bei der mobileX: simple.smart.connected"
    München, 16.10. - 17.10.2019 Veranstalter mobileX AG
  • In.Stand - Die Fachmesse für Instandhaltung und Services

    Die Fachmesse für Instandhaltung und Services mit begleitenden Foren findet vom 23. bis 24. Oktober 2019 auf dem Stuttgarter Messegelände statt. Instandhaltung schafft und bewahrt Werte: Auf der In.Stand werden industrielle Dienstleistungen von spezialisierten Serviceunternehmen sowie internen Wartungs- und Instandhaltungsorganisationen abgebildet. Das Portfolio reicht dabei von...
    Messe Stuttgart, 23.10. - 24.10.2019 Veranstalter Landesmesse Stuttgart GmbH
  • KVD Service Congress 2019

    Mit dem 39. KVD Service Congress widmen wir uns der Diskussion, wie effektiver und effizienter Service in der Zukunft gestaltet werden muss. Im Mittelpunkt des Service stehen die Kunden, die Mitarbeiter und das Unternehmen. Und über allem schwebt das Schlagwort SERVICE-ÖKONOMIE: So gelingt der Aufstieg in die 1. Liga.
    München, 07.11. - 08.11.2019 Veranstalter KVD