Stellen Sie sich ein geschäftiges Vertriebszentrum vor, in dem sich Maschinen und Mitarbeiter optimal zwischen den einzelnen Arbeits- und Lagerplätzen bewegen. Die Routen müssen gut geplant werden, um strenge Zeitvorgaben einzuhalten und Kosten und andere Faktoren niedrig zu halten. Diese Herausforderung steht im Mittelpunkt des historisch so genannten Traveling-Salesman-Problems (TSP). Es findet nicht nur in der Logistik Anwendung. In diesem Beitrag wird untersucht, wie das Traveling-Salesman-Problem im realen Leben und in der Produktion eingesetzt werden kann. Es wird untersucht, wie man die Routenplanung in der gesamten Industrie verbessern kann.
Während dieses Problem ein Klassiker der reinen Mathematik und der Algorithmik ist und auch in der Logistik mit einem eher praktischen Ansatz untersucht wird, ist es in anderen Branchen und Produktionsbereichen fast unbekannt.
Dieser Beitrag konzentriert sich speziell auf einen Algorithmus aus unserem Beitrag "Die 10 wichtigsten Algorithmen und Methoden, die man im Ingenieurwesen kennen sollte".
Die wichtigsten Erkenntnisse
- Beim Traveling-Salesman-Problem (TSP) geht es darum, die optimalste Route zwischen mehreren Punkten zu finden.
- Dieses Problem begann in den Jahren 1930-1940 an Interesse zu gewinnen
- Sie hilft Unternehmen, die Effizienz ihrer Abläufe zu steigern und Kosten zu senken, Ressourcen zu begrenzen und die Bereitstellung von Dienstleistungen zu verbessern.
- Das Problem ist in verschiedenen Sektoren und Branchen weit verbreitet, nicht nur in der Logistik und im Transportwesen.
- Sobald es mehr als 12-20 Punkte gibt, wird das Problem zu komplex, um eine perfekte Lösung zu berechnen
- Es wurden mehrere Algorithmen entwickelt, um gute Annäherungen zu finden, also nicht die perfekte Annäherung
Was ist das Traveling-Salesman-Problem?
Das Problem des Handelsreisenden: Suche nach dem effizientesten Weg für einen Verkäufer, verschiedene Städte zu besuchen und zum Ausgangspunkt zurückzukehren. Er darf jede Stadt nur einmal anfahren und muss versuchen, die Gesamtstrecke so kurz wie möglich zu halten.
Um die TSP-Definition zu verstehen, muss man wissen, dass die Anzahl der Strecken mit der Anzahl der Städte wächst. Bei vier Städten gibt es zum Beispiel 24 mögliche Wege. Wenn man weitere Städte hinzufügt, erhöht sich die Herausforderung, da dann zu viele potenzielle Routen in Betracht kommen.
Viele Unternehmen, z. B. in den Bereichen Logistik, Telekommunikation und Fertigung, stehen häufig vor diesem Problem. Eine gute Lösung für das Problem der Handelsreisenden könnte Geld sparen und die Effizienz steigern. Es wird gezeigt, wie die theoretische mathematische Forschung zur Lösung von Problemen im wirklichen Leben beiträgt.
Warum ist das aber ein Problem?
Wenn es n Städte gibt, gibt es (n-1)!/2 eindeutige Touren (das /2 kommt, wenn die Tour ein Zyklus ist und die Richtung keine Rolle spielt).
Außerdem verändern geringfügige Änderungen der Eingaben (z. B. Entfernungen oder neue Städte) die optimale Route vollständig, was das Problem sehr empfindlich und komplex macht. |
Besuchte Städte | Mögliche Routen / Kombinationen |
| 3 | 6 | |
| 4 | 24 | |
| 5 | 120 | |
| 6 | 720 | |
| 7 | 5040 | |
| … | … | |
| 20 | 6 × 1016 (fast 2 Jahrtausende, wenn jede Routenberechnung eine Mikrosekunde benötigen würde) | |
| 25 | mehr als das Alter unseres Universums, wenn jede Routenberechnung eine Mikrosekunde benötigen würde |
Geschichte des Problems des Handelsreisenden

Das Problem des Handlungsreisenden entstand in den frühen 1900er Jahren, dank einiger kluger Mathematiker. William Rowan Hamilton und Karl Menger waren große Namen, die uns halfen zu verstehen, wie man auf komplexen Wegen navigiert. Sie konzentrierten sich darauf, die Suche nach der besten Route zu erleichtern.
In den 1930er Jahren begann man, den TSP genauer zu definieren. Gelehrte aus Wien und Harvard arbeiteten gemeinsam daran. Sie begannen zu erkennen, wie sie reale Probleme lösen konnten, z. B. die Verbesserung von Schulbuslinien. Dies führte dazu, dass sich mehr Menschen für die Lösung des TSP interessierten.
Das TSP wurde für Unternehmen, insbesondere in der Schifffahrt und im Transportwesen, sehr nützlich. In den 1950er und 1960er Jahren trat die RAND Corporation auf den Plan. Sie entwickelte intelligente Methoden zur Bewältigung des TSP, die zu einem wichtigen Bestandteil einer reibungsloseren Logistik wurden.
The rest of this article is reserved for members
To limit scraping bots (currently 40,000 hits per day!),
we had to restrict access to full articles and tools to registered members only.
to access all the rest.
Häufig gestellte Fragen
Was ist das Traveling Salesman Problem (TSP)?
Das Traveling Salesman Problem (TSP) ist ein wichtiges Rätsel. Es geht darum, den kürzesten Weg zu finden, der jeden Ort nur einmal besucht und zum Ausgangspunkt zurückführt. Dies ist der Schlüssel für Unternehmen, die ihre Routen effizient planen müssen. Die größte Herausforderung ist die enorme Anzahl möglicher Routen, die mit jedem neuen Standort wächst. Außerdem erschweren reale Probleme wie Verkehr und Fristen die Planung.
Warum ist das TSP ein NP-schweres Problem?
Der TSP ist schwierig, weil die Zahl der möglichen Routen mit jeder zusätzlichen Stadt exponentiell ansteigt. Das macht es sehr schwer, schnell die beste Route zu finden, vor allem, wenn mehr als 20 Orte hinzukommen.
Was sind einige gängige Anwendungen von TSP?
TSP wird in vielen Bereichen eingesetzt, z. B. um Lieferwege effizienter zu gestalten und Lieferketten zu verwalten. Auch im Gesundheitswesen ist es hilfreich für die Planung von Besuchen und in Robotik zur Führung von Bewegungen oder in der Fertigungselektronik zur Positionierung oder Prüfung kleiner Bauteile und Kupferleitungen.
Wie hängen die Graphentheorie und heuristische Algorithmen mit dem TSP zusammen?
Die Graphentheorie ist die mathematische Grundlage des TSP. Sie verwendet Punkte (Vertices) zur Darstellung von Städten und Linien (Edges) für die Wege zwischen ihnen. Dies hilft bei der Entwicklung von Methoden zur effektiven Lösung von TSP-Problemen. Heuristische Algorithmen sind intelligente Abkürzungen für die Lösung von TSP. Sie helfen dabei, schnell ausreichend gute Routen zu finden, auch wenn sie nicht perfekt sind. Methoden wie der Nearest Neighbor- und der Greedy-Algorithmus sind gängige Beispiele. Techniken wie Simulated Annealing und genetische Algorithmen sind ebenfalls besonders hilfreich bei großen Problemen.
Wie wirkt sich die TSP auf die Effizienz der Lieferkette aus?
TSP steigert die Effizienz der Lieferkette durch die Optimierung der Transportwege. Dies führt zu Kostensenkungen, einer besseren Nutzung der Ressourcen und einer besseren Koordination zwischen allen Beteiligten. Im Gesundheitswesen optimiert TSP die Bereitstellung von häuslicher Pflege und Notfalldiensten. Sie stellt sicher, dass medizinische Güter rechtzeitig geliefert werden, was die Patientenversorgung und -zufriedenheit insgesamt verbessert.
Glossar der verwendeten Begriffe
Deoxyribonucleic Acid (DNA): Ein Molekül, das aus zwei Strängen besteht, die eine Doppelhelix bilden. Es besteht aus Nukleotiden, die genetische Informationen durch Sequenzen von vier Basen kodieren: Adenin, Thymin, Cytosin und Guanin. Es dient als Erbmaterial in den meisten lebenden Organismen.
Printed Circuit Board (PCB): Eine flache Platte aus Isoliermaterial, die elektronische Komponenten über leitfähige Bahnen, die üblicherweise aus Kupferblechen geätzt werden, trägt und verbindet. Sie dient als Grundlage für die Schaltungsmontage und ermöglicht die elektrische Verbindung zwischen Komponenten.
Unmanned Aerial Vehicle (UAV): Ein ferngesteuertes oder autonomes Fluggerät, das für verschiedene Anwendungen wie Überwachung, Aufklärung und Transport ohne menschlichen Piloten an Bord konzipiert ist. Es wird über Bodenkontrollstationen oder bordeigene Automatisierungssysteme gesteuert und ist häufig mit Sensoren und Kameras zur Datenerfassung ausgestattet.
Very-large-scale Integration (VLSI): Eine Technologie zur Herstellung integrierter Schaltkreise durch die Kombination von Tausenden bis Millionen von Transistoren auf einem einzigen Chip. Dadurch können komplexe elektronische Systeme miniaturisiert und die Leistung, Energieeffizienz und Funktionalität von Geräten wie Computern und Smartphones verbessert werden.











