Die Lösung des Handlungsreisendenproblems für Liefer- und Serviceunternehmen

Die Berechnung der effizientesten Route zwischen mehreren Städten ist eine große Herausforderung. Es gibt Hunderte von möglichen Optionen, die sich basierend auf Hunderten von verschiedenen Variablen ändern.

Zum Beispiel gibt es in nur 15 Städten über 87 Milliarden mögliche Rundreisen. 

Dies ist das Problem des Handlungsreisenden. 

Und es ist ein unglaublich kostspieliges Problem für jedes Liefer-, Service- oder Transportunternehmen.

Um das Problem des Handlungsreisenden zu lösen, benötigen Sie robuste Algorithmen und erhebliche Rechenleistung.

Wenn Sie kein Geld in ein internes Team von Experten für Mathematik und Ingenieurwesen investieren möchten, benötigen Sie eine Drittanbieter-Lösung.

In diesem Artikel werden wir untersuchen, warum das Problem des Handlungsreisenden (TSP) so schwierig ist und wie Geschäftsinhaber intelligente Softwarelösungen nutzen können, um es zu lösen, die Fahrstrecke zu reduzieren und die Flotteneffizienz zu verbessern.

Um zu dem Abschnitt zu navigieren, der Sie am meisten interessiert, klicken Sie unten:

• Was ist das Problem des Handlungsreisenden?
• Warum das Problem des Handlungsreisenden im Jahr 2020 immer noch schwer zu lösen ist
• Wie The Little Posy Co. Routen für 1.000 Ziele in Minuten plant

Was ist das Problem des Handlungsreisenden?

Das Problem des Handlungsreisenden (TSP) ist ein Problem, das fragt, mit einer Liste von Stopps und den Entfernungen zwischen ihnen, was der kürzeste Weg/mögliche Route ist, die jeden Ort besucht und zum Ausgangspunkt zurückkehrt?

Seit Jahrzehnten ist das TSP eine Herausforderung für viele Unternehmen, die auf Routenplanung angewiesen sind – zum Beispiel für Außendienst-, Versand- und Lieferunternehmen.

Mit nur einem Ausgangspunkt und ein paar Stopps kann die Routenplanung schon kompliziert genug erscheinen.

Aber sobald Sie beginnen, Routen im ganzen Land zu planen, erreicht es ein fast unvorstellbares Maß an Komplexität. Mit endlosen Permutationen potenzieller Routen zwischen verschiedenen Stopps (typischerweise Knoten genannt) ist die Identifizierung der kürzesten und effizientesten Route eine enorme Herausforderung.

So würde eine Route aussehen, wenn sie für jede Stadt in den USA mit über 500 Einwohnern geplant würde:

(Bildquelle)

Stellen Sie sich nur die Anzahl der möglichen Routen vor, die Sie nehmen könnten, wenn eine einzige mögliche Lösung so komplex ist.

Warum das Problem des Handlungsreisenden im Jahr 2021 immer noch schwer zu lösen ist

Der Mathematiker Karl Menger entdeckte das TSP im Jahr 1930, vor über 90 Jahren.

Seitdem wurden viele Lösungsvorschläge und Algorithmen entwickelt. Aber sie kämpfen oft mit dem schieren Umfang, da die Anzahl der möglichen Verkaufsrouten mit jedem neuen Stopp exponentiell zunimmt.

Und die Wahrheit ist, dass die reale Routenplanung im Jahr 2021 für reale Unternehmen komplexer ist als nur eine Liste von Stopps – was die Dinge noch komplizierter macht.

In der realen Welt ist es nicht so einfach, einfach die kürzeste Route zu finden.

Es geht nicht nur um Ziele und Entfernungen, es gibt viele andere Faktoren, die eine Rolle spielen.

Es ist nicht so einfach, einfach eine Liste von Adressen zu nehmen und eine Route zu erstellen. 

Eine Außendienst Ein Vertreter, Lieferfahrer oder Techniker muss auch viele andere Faktoren berücksichtigen, wie Zeitfenster, Fahrzeugkapazitäten und mehr.

Lieferzeitfenster und geplante Verkaufsgespräche

Was, wenn Ihre Lieferfahrer oder Verkäufer geplante Lieferzeiten oder Verkaufsgespräche haben? Dann reicht es nicht aus, nur die Entfernung zu berücksichtigen, Sie müssen auch einplanen, wann sie an jedem Standort sein sollten.

Dies fügt eine ganz neue Ebene der Komplexität hinzu und ist eine Herausforderung, die die meisten Routenplaner einfach nicht bewältigen können.

Dieses spezielle Problem ist auch als das Fahrzeug-Routing-Problem mit Zeitfenstern (VRPTW) bekannt. 

Erforderliche Fahrzeugkapazitäten oder Technikerqualifikationen

Für Lieferungen kann jedes Paket, das Sie planen, spezifische Anforderungen in Bezug auf Versand und Handhabung haben, von Kühlung bis hin zu Entladungsmaßen.

Sie müssen auch die gesamte Ladekapazität jedes Fahrzeugs berücksichtigen.

Aber selbst für Wartungs- und Außendienstunternehmen müssen Sie die einzigartigen Qualifikationen jedes Technikers berücksichtigen und ob sie zu einem Auftrag passen.

Dies ist auch bekannt als das Kapazitätsbeschränkte Fahrzeug-Routing-Problem (CVRP).

Effiziente Routen planen, die sowohl Abholungen als auch Lieferungen umfassen

Wenn Ihr Unternehmen irgendeine Art von wiederverwendbarer Verpackung oder recycelbaren Materialien an Ihre Kunden liefert, ist es wahrscheinlich, dass Rückwärtslogistik eine große Priorität ist.

Um die Effizienz Ihres Unternehmens zu maximieren, möchten Sie sowohl Abholung als auch Lieferung in alle geplanten Routen integrieren.

Dies fügt eine weitere Dimension und eine Ebene der Komplexität hinzu, die die meisten Routenoptimierungs- Tools nicht bewältigen können.

Dies wird auch als das Abhol- und Lieferfahrzeug-Routing-Problem (PDVRP) bezeichnet.

Berücksichtigung der Priorität von Leads, bestehenden Kunden und Lieferungen

Um ein Unternehmen effizient zu führen und VIP-Kunden zufrieden zu stellen, müssen Sie auch sicherstellen, dass Ihr Personal die Dinge richtig priorisiert.

Wenn Ihre Routen die Priorität nicht berücksichtigen, wird jeder Kunde gleich behandelt. So riskieren Sie, loyale Kunden zu entfremden, wenn Sie plötzlich auf eine automatisierte Lösung umstellen, die das nicht bewältigen kann.

Ausgleich der Arbeitslasten zwischen mehreren Fahrern

Natürlich müssen Sie bei der Planung von Routen für mehrere Fahrer auch deren Arbeitslasten berücksichtigen.

Fahrer sind nur Menschen und haben eine maximale Schichtlänge von 14 Stunden und vorgeschriebene Pausen.

Was nützt eine „effiziente Route“, wenn es einem Fahrer nicht möglich ist, sie innerhalb der vorgegebenen Zeit zu bewältigen?

Gute Tools zur Auslastungsbalance helfen Ihnen, Überstunden zu reduzieren und Fahrerkosten zu senken und sicherzustellen, dass alle Fahrer jederzeit HOS-konform sind.

Wie The Little Posy Co. mit OptimoRoute Routen für 1.000 Ziele in Minuten plant

The Little Posy Co. ist ein australisches Blumenlieferunternehmen, das jeden Tag Hunderte von einzigartigen Blumen und Sträußen (Bouquets) anbietet.

Wie jedes Blumenlieferunternehmen oder jeder Florist stehen sie vor großen Nachfrageschwankungen in Bezug auf verschiedene Feiertage.

Am Valentinstag 2019 explodierte das Bestellvolumen auf über 1.000 Bestellungen an einem Tag, das gleiche Volumen wie in einer normalen Woche.

Normalerweise wäre dies eine unmögliche Aufgabe für das kleine Team von Posy, aber der Optimierungsalgorithmus von OptimoRoute half, den gesamten Prozess zu optimieren.

„OptimoRoute hat das Unmögliche am Valentinstag absolut möglich gemacht. Es nimmt den Druck weg – ich konnte mir nicht vorstellen, wie der Arbeitsablauf ohne diese Software so reibungslos funktionieren könnte.“ – Gabby Maynard, The Little Posy Co.

Massenimport von Bestellungen und schnelle automatische Routenplanung

Mit OptimoRoute müssen keine Stopps oder Adressen einzeln hinzugefügt oder Routen für einen einzelnen Fahrer geplant werden.

Sie können einfach Ihre Bestellliste in einer Excel-Tabelle oder einer CSV-Datei importieren.

Von dort plant OptimoRoute die Routen automatisch und passt sich an reale Einschränkungen wie Lieferzeiten, Fahrergebiete, Fahrpläne und mehr an.

„Ich konnte mir nicht einmal vorstellen, 1.000 Bestellungen ohne OptimoRoute zu versenden, weil es buchstäblich nur ein paar Mausklicks sind und die Routen perfekt geplant sind.“ Gabby Maynard, The Little Posy Co.

Historische Daten und Analysen helfen bei der Prognose der Nachfrage

Die historischen Routendaten und detaillierten Analysen halfen Maynard, die Nachfrage vorherzusagen und die Flotte entsprechend zu skalieren.

„Wir verlassen uns stark auf historische Daten – zu wissen, wie viele Fahrer ich für den Tag rekrutieren muss, wie viele Bestellungen jeder Fahrer übernehmen kann, wie lange diese Lieferungen dauern würden und wie viele Fahrer entsandt wurden.“ Gabby Maynard, The Little Posy Co.

Abschließende Gedanken

Als Geschäftsinhaber möchten Sie nicht unnötig Zeit damit verschwenden, in Google Maps zu sitzen und Routen zu planen, ohne optimale Lösungen zu erhaltenGoogle Maps Routenoptimierung ist nicht für Unternehmen gedacht).

Das Problem des Handlungsreisenden betrifft Unternehmen, da die manuelle Routenplanung so viel Arbeit erfordert, was die Arbeitsstunden und die Gesamtkosten Ihrer Logistik in die Höhe treibt.

Dies kann oft überdimensionierte Dispositions- und Planungsabteilungen bedeuten und eine Flotte, die langsam auf Stornierungen und Last-Minute-Bestellungen reagiert.

Glücklicherweise müssen Sie keinen Abschluss in Informatik haben, keinen Annäherungsalgorithmus erstellen oder Mathematiker sein, um die beste Lösung für das TSP zu finden.

OptimoRoute bietet ein problemloses Routenplanungserlebnis mit intelligenten Funktionen, die Disponenten helfen, Routen in Minuten zu planen. Es macht auch Ihre Flotte flexibler und hilft Disponenten, sich an Echtzeitänderungen anzupassen.

Um zu sehen, wie OptimoRoute Ihrem Unternehmen helfen kann, das TSP zu überwinden, starten Sie noch heute Ihre 30-tägige kostenlose Testversion.

FAQs zum Problem des Handlungsreisenden

Wie löst man das Problem des Handlungsreisenden? 

Mathematiker und Informatiker haben eine Reihe potenzieller Heuristiken oder Näherungslösungen vorgeschlagen, um das Problem des Handlungsreisenden zu lösen. Eine gängige Lösung, die als Branch-and-Bound-Methode bezeichnet wird, besteht darin, das Problem in eine Reihe kleinerer Teilprobleme zu unterteilen, die mathematisch einfacher zu lösen sind, als zu versuchen, es als ein einziges Problem zu lösen.

Was ist ein Beispiel für das Problem des Handlungsreisenden?

Neben dem Offensichtlichen (nun, einem Handlungsreisenden) nehmen wir das Beispiel eines Lieferdienstes, der an verschiedene Orte in einer Stadt liefert. Der Disponent muss die Reihenfolge bestimmen, in der sie anhalten (außerhalb des Startpunkts). Man könnte denken: einfach am nächstgelegenen Ort zum Startpunkt anhalten und dann am nächstgelegenen zu diesem, usw. 

Aber was, wenn der nächstgelegene Stopp zum Startpunkt Sie weiter von allen anderen Stopps entfernt? Sie müssen berücksichtigen, wie weit die nächsten Orte vom ersten gewählten Stopp entfernt sind. Wie Sie sehen können, vervielfachen sich die Variablen schnell, und die kürzeste Route zu finden, wird enorm komplex, wenn Sie immer mehr Variablen hinzufügen.

Warum wird das Problem des Handlungsreisenden als NP-schwer angesehen?

Das Problem des Handlungsreisenden wird als NP-schwer angesehen, weil es keine einfache oder direkte Lösung gibt und die Schwierigkeit, die optimale Route mit der kürzesten Laufzeit zu berechnen, zunimmt, je mehr Ziele hinzugefügt werden.