Travelling-Salesman-Problem in der Logistik – das Unmögliche berechnen

Es ist bekannt, dass Unternehmen dank der Entwicklung der Informationstechnologie (IT) immer bessere Verkaufsergebnisse erzielen, ganz zu schweigen davon, dass sie dank Softwarelösungen überhaupt funktionieren können. Darüber hinaus können Menschen immer mehr Angelegenheiten über das Internet erledigen oder arbeiten. Allerdings weiß nicht jeder, dass auch die Informatik ihre Grenzen hat und nicht auf alles eine genaue Antwort geben kann, selbst chatGPT nicht :).

Im Bereich der Informatik gibt es seit Jahren Fragestellungen und Probleme, für die es noch keine effizienten und grundlegenden Lösungen gibt. Eines davon ist das Optimierungsproblem namens Travelling-Salesman-Problem, das eng mit der TSL-Branche (Transport Spedition Logistics) verbunden ist. Lesen Sie weiter, um mehr darüber zu erfahren. Vielleicht haben Sie das Glück, dieses Problem zu lösen.

Wie kam es zum “Traveling Salesman Problem”?

Es ist schwierig, die Person zu bestimmen, die als Erster die Schwierigkeit angesprochen hat, eine Reihe von Anweisungen zur Lösung des Problems des Handlungsreisenden (Travelling Salesman Problem, TSP) anzugeben. Die ersten Erwähnungen stammen aus den 1830er Jahren und die ersten Versuche, es zu lösen, wurden etwa 100 Jahre später unternommen, als versucht wurde, die optimale Route für einen Schulbus zu finden. Die Analyse des Problems auf der Grundlage komplexer mathematischer Gesetze und Ausdrücke überlassen wir den Wissenschaftlern. Deshalb werde ich mich auf das Wesentliche konzentrieren und es auf leicht verständliche Weise darstellen.

Was ist das TSP Problem?

Nehmen wir an, es gibt einen Kurier, der seine Arbeit in Boston beginnt und beendet. Eines Tages muss er Pakete an Adressen in New York, Denver, Los Angeles, Austin, Portland und Chicago liefern. Das Problem des Handlungsreisenden besteht darin, den kürzesten Weg zu finden, der es dem Kurier ermöglicht, alle diese Städte zu besuchen. Dabei muss es nicht nur um die Länge der Strecke gehen, sondern es kann auch darum gehen, den günstigsten oder schnellsten Weg zu finden. In unserem Beispiel beträgt die Anzahl der möglichen Routen 5040.

Wie gehen Unternehmen mit der TSP-Problematik um?

Wenn wir für mehrere Städte nach der kürzesten Route suchen, kann die Suche nach der optimalen Lösung auf einem normalen Computer Sekunden oder einige Minuten dauern. Wenn wir jedoch beispielsweise über 52 Städte sprechen, werden verschiedene Algorithmen sowie paralleles und verteiltes Rechnen verwenden, um Näherungslösungen zu finden, die für die Logistik ausreichend sind, da die Überprüfung aller möglichen Routen praktisch unmöglich ist. Es wird Sie wahrscheinlich nicht überraschen, dass künstliche Intelligenz (KI) dabei eine Rolle spielt.

Anwendungen des Traveling Salesman Problems

Das Problem des Handlungsreisenden hat viele praktische Anwendungen. Der Hauptgrund und der Grund für das Schreiben dieses Artikels ist die Optimierung der Routen für Fahrzeug-, Schiffs- oder Flugzeugflotten, wodurch Kosten und Lieferzeiten minimiert werden. Eine weitere Anwendung ist die Planung von Routen für Roboter in Lagerhallen oder Logistikzentren. TSP wird auch beim Entwurf von Telekommunikationsnetzen eingesetzt, um eine optimale Signalqualität sicherzustellen und die Kosten zu minimieren.

Wir helfen Ihnen, Ihre Ladung zu optimieren

Auch wenn wir das Traveling Salesman Problem möglicherweise nicht lösen und für beliebig viele Städte die optimale Route finden können, haben wir ein Programm zur Frachtverladungsplanung namens EasyCargo. Neben der Erstellung eines optimalen Plans für die Warenanordnung (Sie können sie nach Entladeorten gruppieren) und die Ladungsverteilung können Sie damit Berichte im Excel- oder PDF-Format erstellen. Sogar ein öffentlicher Link für die Zusammenarbeit mit Kollegen bei Frachtladungen ist verfügbar.

Darüber hinaus können Sie EasyCargo über unsere API in Ihre Unternehmenssoftware oder andere Programme wie das FleetUp-Telemetriesystem integrieren. Weitere Einzelheiten dazu erfahren Sie unter diesem Link.

Quelle: https://developer-blogs.nvidia.com/wp-content/uploads/2023/01/cuopt-featured.jpg

Man könnte tatsächlich sagen, dass das Traveling Salesman Problem für die TSL-Branche dank der Entwicklung von künstlicher Intelligenz und Big Data langsam weniger ein Problem darstellt. Alle Arten von Software zur Lieferroutenoptimierung bieten eine Route, die nicht wesentlich von der günstigsten abweicht, und passen diese dynamisch in Echtzeit an die Straßenverhältnisse an.

Viel Glück beim Vorschlagen eines Algorithmus, der in polynomieller Zeit die optimale Route für eine beliebige Anzahl von Städten finden kann!