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

  • Materiallogistik in der Einsatzplanung

    Ziel einer Mitarbeitereinsatzplanung ist es eine Planung zu erstellen, die sicherstellt, dass der richtige Mitarbeiter zur richtigen Zeit am richtigen Ort ist. Eine an sich einfache Aufgabe, die jedoch schnell komplex wird, wenn man in die Details geht.Doch ohne die nötigen Ersatzteile ist selbst der richtige Mitarbeiter machtlos. Aus diesem Grund spielt die Planung von Ersatzteilen in der Einsatzplanung eine entscheidende Rolle.
    Kommentare (0)
  • mobileX User Group Treffen 2019: simple – smart - connected

    Die Integration von externen Dienstleistern, Augmented Reality, S4/HANA und das Release 8 der Field Service Management-Suite standen dieses Jahr im Zentrum des Anwendertreffens der mobileX AG.
    Kommentare (0)
  • SAP MRS - 44 Kriterien, die ein Disponent bei der Einsatzplanung berücksichtigen muss - Teil 1: Wer ist der richtige Techniker?

    Ziel einer Mitarbeitereinsatzplanung ist es eine Planung zu erstellen, die sicherstellt, dass der richtige Mitarbeiter zur richtigen Zeit am richtigen Ort ist. Eine an sich einfache Aufgabe, die jedoch schnell komplex wird, wenn man in die Details geht.Dieser Grundlagenartikel beschäftigt sich mit der ersten Aufgabe: Den richtigen Mitarbeiter für einen Serviceeinsatz zu bestimmen.
    Kommentare (0)
  • Grundlagen der Tourenoptimierung

    Die grundlegende Herausforderung der Einsatzplanung ist nicht nur eine tägliche Herausforderung für Disponenten, sondern beschäftigt auch Mathematiker und Informatiker. Anhand eines einfachen Beispiels beschreibt dieser Artikel, wie schnell diese komplex wird.
    Kommentare (0)
  • Digitalisierung im technischen Service und in der Instandhaltung

    Wie Unternehmen im Maschinen -und Anlagenbau Effizienz und Umsatz im After Sales nachhaltig steigern können.
    Kommentare (0)

Veranstaltungen

  • 9. Panasonic IT Solutions Forum 2020

    Am 04.02.2020 findet in der Classic Remise Düsseldorf das 9. Panasonic IT Solutions Forum 2020 statt, zu dem wir Sie gerne einladen möchten.Die Veranstaltung wird 2020 wieder Teilnehmer mehrerer Branchen und Einsatzbereiche zusammenführen. Im Fokus steht neben der Hardware besonders die Prozessoptimierung in den folgenden Bereichen:
    Düsseldorf, 04.02.2020 Veranstalter Panasonic
  • maintenance 2020 - Leitmesse für industrielle Instandhaltung

    Die maintenance Dortmund ist Deutschlands Leitmesse der Instandhaltungsbranche. Mit ihrer umfangreichen Angebotspalette ist die führende Geschäftsplattform unverzichtbar für Unternehmen und Experten aus der Instandhaltung sowie für Anwender aus allen relevanten Industriebranchen.Von Wartungsausrüstung, Ersatzteilen und Antriebstechnik bis zu Predictive Maintenance und innovativen technischen...
    Dortmund, 12.02. - 13.02.2020 Veranstalter Messe Dortmund
  • E-world energy & water 2020

    Vom 11. - 13. Februar findet in Essen die E-world energy & water 2020 statt - Europas Leitmesse für die Energie- und Wasserwirtschaft und der zentrale Treffpunkt für Entscheider.Die Themenschwerpunkte der Messe im nächsten Jahr sind:Smart CityClimate SolutionsBesuchen Sie unseren Messestand in Halle 1 Stand 1-130. Gerne zeigen wir Ihnen...
    Essen, 11.02. - 13.02.2020 Veranstalter Messe Essen