TSP Solver

Software zur Routenoptimierung für das Problem des Handlungsreisenden

1.000 Zufallspunkte in der kostenlosen Online-Demo ausprobierenErzeugen Sie zufällige AIR-Punkte und vergleichen Sie die Algorithmen. Für zufällig erzeugte AIR-Punkte gilt die Demo-Grenze von 100 Punkten nicht. Öffnen Sie Daten → Zufallsgenerierung, um die Anzahl der Punkte festzulegen. Algorithmen online ausprobieren

Was ist TSP Solver?

TSP Solver ist ein Programm zur Routenoptimierung für das Problem des Handlungsreisenden (Travelling Salesman Problem, TSP). Es zählt zu den bekanntesten Problemen der kombinatorischen Optimierung. Gesucht wird eine möglichst kurze, praktisch nutzbare Rundreise, die jeden vorgegebenen Punkt beziehungsweise jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Das Programm unterstützt 2D- und 3D-Koordinaten (x, y, z) mit interaktiver 3D-Darstellung. Es eignet sich für Logistik und Routenplanung sowie für Flugroutenplanung für Drohnen, Robotik und industrielle Anwendungen wie Lasergravur, Leiterplattenbohren (PCB) sowie 3D-Druck und CNC-Maschinen, bei denen die Routenoptimierung die Produktionszeit deutlich verkürzen kann.

TSP Solver 3.05 bietet eine neu gestaltete Oberfläche und einen aktualisierten Robopol-Refined-Kern. Unterstützt werden AIR 2D/3D, Straßenrouten und mehrere Fahrzeuge über LKH. Die Profile Fast, Balanced und Heavy bestimmen den Suchaufwand.

Balanced ist das Standardprofil für ein ausgewogenes Verhältnis von Laufzeit und Qualität. Bei 30 modifizierten Tetraederinstanzen lieferte es in 27 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum wurde 24-mal erreicht, gegenüber 3-mal mit LKH. Heavy untersucht mehr Alternativen und Fast priorisiert eine kurze Laufzeit. Die Ergebnisse hängen von den Daten und Einstellungen ab.

Testen Sie die Leistungsfähigkeit der Algorithmen mit zufällig erzeugten Punkten in der Online-Version von TSP Solver. Diese Funktion steht auch in der kostenlosen Demoversion zur Verfügung.

Die Online-Anwendung sowie die Windows- und Linux-Versionen enthalten Oberflächen, Meldungen und Benutzerhandbücher auf Englisch, Deutsch, Spanisch und vereinfachtem Chinesisch. Beim Sprachwechsel bleibt Ihre begonnene Route erhalten.

Balanced findet in 27 von 30 Fällen kürzere Rundreisen

Balanced ist das Standardprofil für ein ausgewogenes Verhältnis von Laufzeit und Qualität. Bei 30 modifizierten Tetraederinstanzen lieferte es in 27 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum wurde 24-mal erreicht, gegenüber 3-mal mit LKH. Heavy untersucht mehr Alternativen und Fast priorisiert eine kurze Laufzeit. Die Ergebnisse hängen von den Daten und Einstellungen ab.

Die neue Oberfläche von TSP Solver 3.05 mit einer berechneten Route.

Die neue Oberfläche von TSP Solver 3.05 mit einer berechneten Route.

Routenoptimierung

Suchen Sie eine möglichst kurze optimierte Rundreise durch die ausgewählten Punkte. Mit den Profilen Fast, Balanced und Heavy bestimmen Sie das Verhältnis zwischen Geschwindigkeit und Suchumfang.

Unterstützung für 3D-Punkte

Arbeiten Sie mit 3D-Koordinaten (x, y, z) für räumliche Optimierungsaufgaben. Geeignet für die Flugroutenplanung für Drohnen, zur Optimierung der Bewegungen von Roboterarmen, zur Navigation in mehrstöckigen Lagerhallen oder zur Pfadoptimierung für 3D-Druck und CNC-Maschinen. Die interaktive 3D-Darstellung ermöglicht das Drehen und Vergrößern der berechneten Route.

TSP Art

Erstellen Sie Kunstwerke aus einer einzigen durchgehenden Linie, die durch Tausende von Punkten verläuft.

Fortgeschrittene Algorithmen

Balanced ist das Standardprofil für ein ausgewogenes Verhältnis von Laufzeit und Qualität. Bei 30 modifizierten Tetraederinstanzen lieferte es in 27 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum wurde 24-mal erreicht, gegenüber 3-mal mit LKH. Heavy untersucht mehr Alternativen und Fast priorisiert eine kurze Laufzeit. Die Ergebnisse hängen von den Daten und Einstellungen ab.

Import und Export

Importieren Sie Punkte aus Textdateien, exportieren Sie Routen, speichern Sie Projekte und erstellen Sie Bilder Ihrer Ergebnisse.

Straßenentfernungen & Google Maps

Berechnen Sie eine optimierte Route anhand des tatsächlichen Straßennetzes. Öffnen Sie das Ergebnis direkt in Google Maps und senden Sie es zur Navigation an Ihr Smartphone.

mTSP für mehrere Fahrzeuge

Verteilen Sie Routen mithilfe des LKH-Algorithmus auf mehrere Fahrzeuge. Unterstützt werden vor allem AIR 2D und Straßenentfernungen. Größere AIR-3D-Aufgaben sollten zunächst mit kleineren Datensätzen geprüft werden. Legen Sie Fahrzeuganzahl, Depot, Optimierungsziel (MINSUM/MINMAX) und die zulässige Anzahl von Stopps je Fahrzeug fest. Mit der Professional-Lizenz verfügbar.

Für Mobilgeräte optimiert

Die Anwendung ist responsiv und lässt sich bequem auf Tablets und Smartphones bedienen. Sie ist außerdem online unter tspsolver.robopol.sk ohne Installation verfügbar.

Programmbeispiele

TSP Solver 3.05 – John-Wick-Motiv als TSP Art unter Windows

TSP Art unter Windows – John Wick, 100.000 Punkte

TSP Solver – Hauptfenster

TSP Solver – Hauptfenster

TSP Solver – Routendarstellung für Städte in Tschechien

Optimierte Route durch Städte in Tschechien

AIR 3D – Drachenmodell, 12.000 Punkte, Refined Balanced

AIR 3D – Drachenmodell, 12.000 Punkte, Refined Balanced

Optimierte Straßenroute durch Paris

Optimierte Straßenroute durch Paris

Optimierte Straßenroute durch Finnland

Optimierte Straßenroute durch Finnland

Straßenadressen und Navigation mit Google Maps

Straßenadressen und Navigation mit Google Maps

TSP Solver – 3D-mTSP für mehrere Fahrzeuge

mTSP für mehrere Fahrzeuge – 3D-Routen (x, y, z)

TSP Solver – Straßen-mTSP für mehrere Fahrzeuge

mTSP für mehrere Fahrzeuge – Straßenentfernungen

So funktioniert es

1

Punkte eingeben

Geben Sie Punkte beziehungsweise Städte durch Klicken auf die Zeichenfläche, durch Dateiimport oder durch Eingabe von Adressen zur Geokodierung für Straßenrouten ein.

2

Algorithmus auswählen

Wählen Sie einen Algorithmus und passende Parameter anhand der Problemgröße und der gewünschten Genauigkeit.

3

Berechnung

Das Programm berechnet mit dem ausgewählten Algorithmus eine optimierte Route.

4

Ergebnisse

Prüfen Sie die Ergebnisse einschließlich Routendarstellung und Statistiken.

Technische Details

Verwendete Algorithmen

TSP Solver Desktop 3.05 bietet diese Methoden.

  • LKH + Robopol Refined – kombinierter Modus für AIR-2D/3D-TSP. Er beginnt mit einer hochwertigen LKH-Rundreise und nutzt während der Refined-Optimierung gezielt weitere LKH-Verbesserungen.
  • Robopol Refined – aktualisierter Kern mit den Profilen Fast, Balanced und Heavy. Im folgenden Benchmark fand Balanced in 27 von 30 Fällen kürzere Rundreisen als eigenständiges LKH (DELAUNAY).
  • LKH-3.0.10 – eigenständige AIR-Optimierung sowie die Berechnungsmethode für Straßenrouten und mTSP.

Balanced ist das Standardprofil für ein ausgewogenes Verhältnis von Laufzeit und Qualität. Bei 30 modifizierten Tetraederinstanzen lieferte es in 27 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum wurde 24-mal erreicht, gegenüber 3-mal mit LKH. Heavy untersucht mehr Alternativen und Fast priorisiert eine kurze Laufzeit. Die Ergebnisse hängen von den Daten und Einstellungen ab.

Leistung

Balanced ist das Standardprofil für ein ausgewogenes Verhältnis von Laufzeit und Qualität. Bei 30 modifizierten Tetraederinstanzen lieferte es in 27 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum wurde 24-mal erreicht, gegenüber 3-mal mit LKH. Heavy untersucht mehr Alternativen und Fast priorisiert eine kurze Laufzeit. Die Ergebnisse hängen von den Daten und Einstellungen ab.

Auf einer CPU mit 8 Kernen getestet

AMD Ryzen 7 5700X3D

8 physische Kerne / 16 Hardware-Threads

Benchmark 3.05 – Übersicht und Einstellungen

Der Benchmark von TSP Solver 3.05 umfasst 30 modifizierte Tetraederinstanzen T′n,m mit 157 bis 4.396 Punkten und 120 Ergebnissen. Die Messungen wurden am 7. September 2026 durchgeführt. Jede Methode erhielt dieselben Punkte. Das Optimum ergibt sich aus der für diese Familie mathematisch bewiesenen Rundreise.

Balanced fand in 27 von 30 Fällen kürzere Rundreisen als LKH (DELAUNAY) und in 3 Fällen gleich lange Rundreisen. Das Optimum erreichte Balanced 24-mal, Heavy 27-mal, der Hybrid 28-mal und eigenständiges LKH 3-mal. Diese Ergebnisse gelten für diese Instanzfamilie und die angegebenen Einstellungen.

Abweichung (%) = (Routenlänge − Optimum) / Optimum × 100. Die Längen ergeben sich aus der Summe der euklidischen Entfernungen einschließlich der Rückkehr zum ersten Punkt. Einzelne Kanten werden bei der Auswertung nicht auf ganze Zahlen gerundet. Gerundet werden ausschließlich die angezeigten Tabellenwerte.

Methode / ProfilErreichtes OptimumMittlere AbweichungGrößte AbweichungMittlere Laufzeit
Robopol Refined — Balanced24/300.00002968 %0.00083493 %2.060 s
Robopol Refined — Heavy27/302.160785E-9 %0.00000004 %4.327 s
LKH + Robopol Refined — Balanced28/301.245357E-9 %0.00000002 %5.696 s
LKH-3.0.10 (DELAUNAY)3/300.11724559 %0.46287393 %2.399 s

LKH (DELAUNAY): RUNS=10, MAX_TRIALS=1, MAX_CANDIDATES=5, MOVE_TYPE=5, PATCHING_C=1, PATCHING_A=1, INITIAL_PERIOD=100. Die Solver verwenden die Metrik EXACT_2D. Refined verwendet die bestehenden Profile Balanced und Heavy, der Hybrid das Profil Balanced.

Die Laufzeiten umfassen den Aufruf der lokalen Anwendung und die Berechnung mit jeweils einem erfolgreichen Lauf pro Kombination aus Instanz und Profil. Die Zeitbudgets unterscheiden sich zwischen den Methoden. Zwei fehlgeschlagene Initialisierungen des Hybrids wurden wiederholt. Die Zeit der fehlgeschlagenen Versuche ist aus den Mittelwerten ausgenommen.

Vergleich aller 30 Instanzen
InstanzPunkteBewiesenes OptimumAbweichung von BalancedAbweichung von HeavyAbweichung des HybridsAbweichung von LKH (DELAUNAY)
Tprime_40_22157192.2128826610 %0 %0 %0 %
Tprime_40_30172194.8478375000 %0 %0 %0 %
Tprime_40_40187192.9627202280 %0 %0 %0.01764535 %
Tprime_40_60223195.0279849940 %0 %0 %0.40535398 %
Tprime_60_30244317.7349128900 %0 %0 %0 %
Tprime_40_80256194.5790792680 %0 %0 %0.41976394 %
Tprime_60_45277320.0106589550 %0 %0 %0.08743262 %
Tprime_60_60307318.0085498000 %0 %0 %0.09902683 %
Tprime_60_90373320.1964660000 %0 %0 %0.44791308 %
Tprime_100_50424569.4680156300 %0 %0 %0.00013950 %
Tprime_60_120436319.7193449270 %0 %0 %0.46287393 %
Tprime_100_75487571.8078312760 %0 %0 %0.02681372 %
Tprime_100_100547569.7488821060 %0 %0 %0.00996326 %
Tprime_100_150673571.9968221090 %0 %0 %0.32110210 %
Tprime_180_907841073.8860050020 %0 %0 %0.00009610 %
Tprime_100_200796571.5058876760 %0 %0 %0.00077966 %
Tprime_180_1359071076.2561503220 %0 %0 %0.16263537 %
Tprime_180_18010271074.1706995840 %0 %0 %0.13688396 %
Tprime_180_27012731076.4468342450 %0 %0 %0.19100221 %
Tprime_300_15013241830.8689210900.00000106 %0 %0 %0.00009747 %
Tprime_180_36015161075.9494208580 %0 %0 %0.19676975 %
Tprime_300_22515371833.2515532630 %0 %0 %0.07704029 %
Tprime_300_30017471831.1553024850 %0 %0 %0.06825336 %
Tprime_300_45021731833.4429849040 %0 %0 %0.11744864 %
Tprime_500_25022243092.6680152350.00000264 %0 %0 %0.00003802 %
Tprime_500_37525873095.0574317930 %0 %0 %0.00114559 %
Tprime_300_60025961832.9429222790.00000002 %0.00000004 %0.00000002 %0.12092710 %
Tprime_500_50029473092.9553460790.00005165 %0 %0 %0.00144848 %
Tprime_500_75036733095.2492847630.00083493 %0.00000001 %0 %0.07134219 %
Tprime_500_100043963094.7477884190.00000002 %0.00000002 %0.00000002 %0.07343120 %
Alle 120 Ergebnisse und Laufzeiten
InstanzPunkteMethode / ProfilOptimumRoutenlängeAbweichungOptimum erreichtLaufzeit
Tprime_40_22157Robopol Refined — Balanced192.212882661192.2128826610 %Ja0.909 s
Tprime_40_22157Robopol Refined — Heavy192.212882661192.2128826610 %Ja1.729 s
Tprime_40_22157LKH + Robopol Refined — Balanced192.212882661192.2128826610 %Ja1.096 s
Tprime_40_22157LKH-3.0.10 (DELAUNAY)192.212882661192.2128826610 %Ja0.224 s
Tprime_40_30172Robopol Refined — Balanced194.847837500194.8478375000 %Ja0.926 s
Tprime_40_30172Robopol Refined — Heavy194.847837500194.8478375000 %Ja1.656 s
Tprime_40_30172LKH + Robopol Refined — Balanced194.847837500194.8478375000 %Ja1.114 s
Tprime_40_30172LKH-3.0.10 (DELAUNAY)194.847837500194.8478375000 %Ja0.172 s
Tprime_40_40187Robopol Refined — Balanced192.962720228192.9627202280 %Ja0.995 s
Tprime_40_40187Robopol Refined — Heavy192.962720228192.9627202280 %Ja2.226 s
Tprime_40_40187LKH + Robopol Refined — Balanced192.962720228192.9627202280 %Ja1.364 s
Tprime_40_40187LKH-3.0.10 (DELAUNAY)192.962720228192.9967691730.01764535 %Nein0.214 s
Tprime_40_60223Robopol Refined — Balanced195.027984994195.0279849940 %Ja0.935 s
Tprime_40_60223Robopol Refined — Heavy195.027984994195.0279849940 %Ja1.934 s
Tprime_40_60223LKH + Robopol Refined — Balanced195.027984994195.0279849940 %Ja1.232 s
Tprime_40_60223LKH-3.0.10 (DELAUNAY)195.027984994195.8185386880.40535398 %Nein0.303 s
Tprime_60_30244Robopol Refined — Balanced317.734912890317.7349128900 %Ja0.947 s
Tprime_60_30244Robopol Refined — Heavy317.734912890317.7349128900 %Ja1.905 s
Tprime_60_30244LKH + Robopol Refined — Balanced317.734912890317.7349128900 %Ja1.263 s
Tprime_60_30244LKH-3.0.10 (DELAUNAY)317.734912890317.7349128900 %Ja0.410 s
Tprime_40_80256Robopol Refined — Balanced194.579079268194.5790792680 %Ja1.184 s
Tprime_40_80256Robopol Refined — Heavy194.579079268194.5790792680 %Ja2.380 s
Tprime_40_80256LKH + Robopol Refined — Balanced194.579079268194.5790792680 %Ja1.327 s
Tprime_40_80256LKH-3.0.10 (DELAUNAY)194.579079268195.3958520770.41976394 %Nein0.326 s
Tprime_60_45277Robopol Refined — Balanced320.010658955320.0106589550 %Ja1.013 s
Tprime_60_45277Robopol Refined — Heavy320.010658955320.0106589550 %Ja2.027 s
Tprime_60_45277LKH + Robopol Refined — Balanced320.010658955320.0106589550 %Ja1.187 s
Tprime_60_45277LKH-3.0.10 (DELAUNAY)320.010658955320.2904526550.08743262 %Nein0.194 s
Tprime_60_60307Robopol Refined — Balanced318.008549800318.0085498000 %Ja1.058 s
Tprime_60_60307Robopol Refined — Heavy318.008549800318.0085498000 %Ja2.182 s
Tprime_60_60307LKH + Robopol Refined — Balanced318.008549800318.0085498000 %Ja1.229 s
Tprime_60_60307LKH-3.0.10 (DELAUNAY)318.008549800318.3234635840.09902683 %Nein0.226 s
Tprime_60_90373Robopol Refined — Balanced320.196466000320.1964660000 %Ja1.155 s
Tprime_60_90373Robopol Refined — Heavy320.196466000320.1964660000 %Ja2.398 s
Tprime_60_90373LKH + Robopol Refined — Balanced320.196466000320.1964660000 %Ja1.367 s
Tprime_60_90373LKH-3.0.10 (DELAUNAY)320.196466000321.6306678520.44791308 %Nein0.550 s
Tprime_100_50424Robopol Refined — Balanced569.468015630569.4680156300 %Ja1.142 s
Tprime_100_50424Robopol Refined — Heavy569.468015630569.4680156300 %Ja2.295 s
Tprime_100_50424LKH + Robopol Refined — Balanced569.468015630569.4680156300 %Ja1.443 s
Tprime_100_50424LKH-3.0.10 (DELAUNAY)569.468015630569.4688100150.00013950 %Nein1.120 s
Tprime_60_120436Robopol Refined — Balanced319.719344927319.7193449270 %Ja1.268 s
Tprime_60_120436Robopol Refined — Heavy319.719344927319.7193449270 %Ja2.682 s
Tprime_60_120436LKH + Robopol Refined — Balanced319.719344927319.7193449270 %Ja1.699 s
Tprime_60_120436LKH-3.0.10 (DELAUNAY)319.719344927321.1992424180.46287393 %Nein1.073 s
Tprime_100_75487Robopol Refined — Balanced571.807831276571.8078312760 %Ja1.211 s
Tprime_100_75487Robopol Refined — Heavy571.807831276571.8078312760 %Ja2.294 s
Tprime_100_75487LKH + Robopol Refined — Balanced571.807831276571.8078312760 %Ja1.458 s
Tprime_100_75487LKH-3.0.10 (DELAUNAY)571.807831276571.9611542140.02681372 %Nein0.193 s
Tprime_100_100547Robopol Refined — Balanced569.748882106569.7488821060 %Ja1.325 s
Tprime_100_100547Robopol Refined — Heavy569.748882106569.7488821060 %Ja2.537 s
Tprime_100_100547LKH + Robopol Refined — Balanced569.748882106569.7488821060 %Ja1.557 s
Tprime_100_100547LKH-3.0.10 (DELAUNAY)569.748882106569.8056476540.00996326 %Nein0.188 s
Tprime_100_150673Robopol Refined — Balanced571.996822109571.9968221090 %Ja1.459 s
Tprime_100_150673Robopol Refined — Heavy571.996822109571.9968221090 %Ja2.710 s
Tprime_100_150673LKH + Robopol Refined — Balanced571.996822109571.9968221090 %Ja1.691 s
Tprime_100_150673LKH-3.0.10 (DELAUNAY)571.996822109573.8335159070.32110210 %Nein0.222 s
Tprime_180_90784Robopol Refined — Balanced1073.8860050021073.8860050020 %Ja1.498 s
Tprime_180_90784Robopol Refined — Heavy1073.8860050021073.8860050020 %Ja3.303 s
Tprime_180_90784LKH + Robopol Refined — Balanced1073.8860050021073.8860050020 %Ja2.426 s
Tprime_180_90784LKH-3.0.10 (DELAUNAY)1073.8860050021073.8870369570.00009610 %Nein1.526 s
Tprime_100_200796Robopol Refined — Balanced571.505887676571.5058876760 %Ja1.692 s
Tprime_100_200796Robopol Refined — Heavy571.505887676571.5058876760 %Ja3.781 s
Tprime_100_200796LKH + Robopol Refined — Balanced571.505887676571.5058876760 %Ja3.620 s
Tprime_100_200796LKH-3.0.10 (DELAUNAY)571.505887676571.5103434900.00077966 %Nein2.003 s
Tprime_180_135907Robopol Refined — Balanced1076.2561503221076.2561503220 %Ja1.301 s
Tprime_180_135907Robopol Refined — Heavy1076.2561503221076.2561503220 %Ja2.676 s
Tprime_180_135907LKH + Robopol Refined — Balanced1076.2561503221076.2561503220 %Ja1.845 s
Tprime_180_135907LKH-3.0.10 (DELAUNAY)1076.2561503221078.0065235330.16263537 %Nein0.208 s
Tprime_180_1801027Robopol Refined — Balanced1074.1706995841074.1706995840 %Ja1.753 s
Tprime_180_1801027Robopol Refined — Heavy1074.1706995841074.1706995840 %Ja3.276 s
Tprime_180_1801027LKH + Robopol Refined — Balanced1074.1706995841074.1706995840 %Ja1.944 s
Tprime_180_1801027LKH-3.0.10 (DELAUNAY)1074.1706995841075.6410669260.13688396 %Nein0.253 s
Tprime_180_2701273Robopol Refined — Balanced1076.4468342451076.4468342450 %Ja2.217 s
Tprime_180_2701273Robopol Refined — Heavy1076.4468342451076.4468342450 %Ja4.296 s
Tprime_180_2701273LKH + Robopol Refined — Balanced1076.4468342451076.4468342450 %Ja7.379 s
Tprime_180_2701273LKH-3.0.10 (DELAUNAY)1076.4468342451078.5028714820.19100221 %Nein0.299 s
Tprime_300_1501324Robopol Refined — Balanced1830.8689210901830.8689405220.00000106 %Nein2.203 s
Tprime_300_1501324Robopol Refined — Heavy1830.8689210901830.8689210900 %Ja5.207 s
Tprime_300_1501324LKH + Robopol Refined — Balanced1830.8689210901830.8689210900 %Ja3.286 s
Tprime_300_1501324LKH-3.0.10 (DELAUNAY)1830.8689210901830.8707056740.00009747 %Nein0.826 s
Tprime_180_3601516Robopol Refined — Balanced1075.9494208581075.9494208580 %Ja2.224 s
Tprime_180_3601516Robopol Refined — Heavy1075.9494208581075.9494208580 %Ja4.691 s
Tprime_180_3601516LKH + Robopol Refined — Balanced1075.9494208581075.9494208580 %Ja3.634 s
Tprime_180_3601516LKH-3.0.10 (DELAUNAY)1075.9494208581078.0665638170.19676975 %Nein3.967 s
Tprime_300_2251537Robopol Refined — Balanced1833.2515532631833.2515532630 %Ja1.819 s
Tprime_300_2251537Robopol Refined — Heavy1833.2515532631833.2515532630 %Ja3.635 s
Tprime_300_2251537LKH + Robopol Refined — Balanced1833.2515532631833.2515532630 %Ja2.767 s
Tprime_300_2251537LKH-3.0.10 (DELAUNAY)1833.2515532631834.6638955230.07704029 %Nein0.285 s
Tprime_300_3001747Robopol Refined — Balanced1831.1553024851831.1553024850 %Ja1.798 s
Tprime_300_3001747Robopol Refined — Heavy1831.1553024851831.1553024850 %Ja5.210 s
Tprime_300_3001747LKH + Robopol Refined — Balanced1831.1553024851831.1553024850 %Ja2.940 s
Tprime_300_3001747LKH-3.0.10 (DELAUNAY)1831.1553024851832.4051275750.06825336 %Nein0.367 s
Tprime_300_4502173Robopol Refined — Balanced1833.4429849041833.4429849040 %Ja2.643 s
Tprime_300_4502173Robopol Refined — Heavy1833.4429849041833.4429849040 %Ja5.356 s
Tprime_300_4502173LKH + Robopol Refined — Balanced1833.4429849041833.4429849040 %Ja10.208 s
Tprime_300_4502173LKH-3.0.10 (DELAUNAY)1833.4429849041835.5963388450.11744864 %Nein4.273 s
Tprime_500_2502224Robopol Refined — Balanced3092.6680152353092.6680967580.00000264 %Nein2.643 s
Tprime_500_2502224Robopol Refined — Heavy3092.6680152353092.6680152350 %Ja5.014 s
Tprime_500_2502224LKH + Robopol Refined — Balanced3092.6680152353092.6680152350 %Ja5.387 s
Tprime_500_2502224LKH-3.0.10 (DELAUNAY)3092.6680152353092.6691911970.00003802 %Nein1.274 s
Tprime_500_3752587Robopol Refined — Balanced3095.0574317933095.0574317930 %Ja2.388 s
Tprime_500_3752587Robopol Refined — Heavy3095.0574317933095.0574317930 %Ja4.948 s
Tprime_500_3752587LKH + Robopol Refined — Balanced3095.0574317933095.0574317930 %Ja4.079 s
Tprime_500_3752587LKH-3.0.10 (DELAUNAY)3095.0574317933095.0928883460.00114559 %Nein0.387 s
Tprime_300_6002596Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %Nein6.203 s
Tprime_300_6002596Robopol Refined — Heavy1832.9429222791832.9429229580.00000004 %Nein11.963 s
Tprime_300_6002596LKH + Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %Nein17.524 s
Tprime_300_6002596LKH-3.0.10 (DELAUNAY)1832.9429222791835.1594469530.12092710 %Nein11.462 s
Tprime_500_5002947Robopol Refined — Balanced3092.9553460793092.9569434580.00005165 %Nein2.437 s
Tprime_500_5002947Robopol Refined — Heavy3092.9553460793092.9553460790 %Ja5.059 s
Tprime_500_5002947LKH + Robopol Refined — Balanced3092.9553460793092.9553460790 %Ja4.988 s
Tprime_500_5002947LKH-3.0.10 (DELAUNAY)3092.9553460793093.0001470560.00144848 %Nein0.479 s
Tprime_500_7503673Robopol Refined — Balanced3095.2492847633095.2751278480.00083493 %Nein6.109 s
Tprime_500_7503673Robopol Refined — Heavy3095.2492847633095.2492850380.00000001 %Nein13.684 s
Tprime_500_7503673LKH + Robopol Refined — Balanced3095.2492847633095.2492847630 %Ja10.741 s
Tprime_500_7503673LKH-3.0.10 (DELAUNAY)3095.2492847633097.4575034130.07134219 %Nein4.530 s
Tprime_500_10004396Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %Nein7.343 s
Tprime_500_10004396Robopol Refined — Heavy3094.7477884193094.7477890030.00000002 %Nein16.750 s
Tprime_500_10004396LKH + Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %Nein69.093 s
Tprime_500_10004396LKH-3.0.10 (DELAUNAY)3094.7477884193097.0202987490.07343120 %Nein34.420 s
Daten herunterladen und Methodik

Eingabedaten und optimale Rundreisen (JSON) · Alle Ergebnisse (CSV) · Ergebnisse, Rundreisen und Einstellungen (JSON)

Konstruktion und Optimalitätsbeweis aus Hougardy–Zhong: Hard to Solve Instances of the Euclidean Traveling Salesman Problem. Verwendet wurde die modifizierte Familie aus der Veröffentlichung. Die gerundeten EUC_2D-Dateien aus dem Archiv der Autoren wurden hierfür nicht verwendet.

Die Koordinaten werden vor der Übergabe einheitlich um den Faktor 1.000 skaliert. EXACT_2D arbeitet mit endlicher Genauigkeit. Die zurückgegebenen Rundreisen und das Optimum werden unabhängig auf der ursprünglichen Geometrie mit 70-stelliger Genauigkeit ausgewertet und wurden mit 110-stelliger Genauigkeit überprüft. Für die Übereinstimmung mit dem Optimum gilt eine Toleranz von 10−40 ursprünglichen Einheiten. Abweichungen ungleich null bleiben als solche erhalten.

Die veröffentlichten LKH-Ergebnisse verwenden den korrigierten Koordinatenexport mit 17 signifikanten Stellen. Die Eingabe-JSON enthält ideale Koordinaten, die exakt übergebenen Punkte, n und m, Referenzrundreisen und Optima. Die Routenindizes in der JSON beginnen bei null.

Systemanforderungen

  • Windows 10/11 oder Ubuntu 24.04+ (x86_64, glibc 2.39+)
  • Mindestens 2 GB RAM
  • 1 GB freier Speicherplatz
  • Bildschirmauflösung von mindestens 1024 × 768

Neuerungen in Version 3.05

Verfügbarkeit und Lizenzen von TSP Solver

TSP Solver 3.05 bietet eine neu gestaltete Oberfläche und einen aktualisierten Robopol-Refined-Kern. Unterstützt werden AIR 2D/3D, Straßenrouten und mehrere Fahrzeuge über LKH. Die Profile Fast, Balanced und Heavy bestimmen den Suchaufwand.

TSP Solver – Demoversion

Kostenlose Version zum Ausprobieren. Die Desktopversion für Windows und Linux erhalten Sie auf Anfrage bei RoboPol.
Sie können die Anwendung direkt online ausprobieren. TSP Solver Online starten. Testen Sie die Algorithmen in der Demo mit zufällig erzeugten AIR-Punkten. Für diese generierten Punkte gilt keine Grenze von 100 Punkten.

  • AIR-Punkte ohne allgemeine lizenzbedingte Punktgrenze erstellen und testen
  • Route als Bild exportieren
  • Grafikeinstellungen ändern
  • Bis zu 100 manuell gesetzte Punkte auf einem importierten Bild
  • TSP Art auf dem Desktop mit bis zu 20.000 Punkten
  • Straßenrouten mit bis zu 5 Adressen erstellen
  • Bis zu 100 Punkte importieren und exportieren
  • Route an Google Maps senden
  • Route zur mobilen Navigation senden
Bei RoboPol anfragen Benutzerhandbuch

TSP Solver – Basic-Lizenz

Geeignet für Reiseplanung und kleinere Projekte.

  • AIR-Berechnungen auf dem Desktop und online ohne allgemeine lizenzbedingte Punktgrenze
  • Auf dem Desktop stehen die Refined-Profile Fast, Balanced und Heavy sowie LKH-Einstellungen ohne gesonderte Lizenzbegrenzungen zur Verfügung
  • Bis zu 5.000 Punkte aus TXT-Dateien importieren und in TXT-Dateien exportieren
  • Straßenrouten mit bis zu 100 Adressen erstellen
  • Bilder importieren und exportieren
  • TSP Art auf dem Desktop ohne lizenzbedingte Punktgrenze
  • Route an Google Maps senden
  • Route zur mobilen Navigation senden
Lizenz kaufen (120 € pro Jahr)
Empfohlen

TSP Solver – Professional-Lizenz

Geeignet für Unternehmen aus Transport und Industrie.

  • AIR-Berechnungen auf dem Desktop und online ohne allgemeine lizenzbedingte Punktgrenze
  • Auf dem Desktop stehen die Refined-Profile Fast, Balanced und Heavy sowie LKH-Einstellungen ohne gesonderte Lizenzbegrenzungen zur Verfügung
  • Punkte ohne Lizenzbegrenzung importieren und exportieren
  • Straßenrouten ohne lizenzbedingte Adressgrenze
  • Routen exportieren
  • Bilder importieren und exportieren
  • TSP Art auf dem Desktop zur Erstellung von Kunstbildern
  • mTSP für mehrere Fahrzeuge – LKH für mehrere Fahrzeuge (2D/3D/Straße)
  • Route an Google Maps senden
  • Route zur mobilen Navigation senden
Lizenz kaufen (390 € pro Jahr)

Lizenzgrenzen der Desktop- und Online-Version

Die Bezeichnung Normal steht für die kostenpflichtige Basic-Lizenz. Die Desktopanwendung rechnet lokal, die Online-Version auf dem Server. Für beide Versionen gelten dieselben Lizenzgrenzen.

Desktopanwendung

Funktion Demo Normal / Basic Professional
AIR-Berechnungen mit Robopol Refined / LKH + Robopol Refined / LKH-3.0.10 Keine allgemeine lizenzbedingte Punktgrenze Keine allgemeine lizenzbedingte Punktgrenze Keine allgemeine lizenzbedingte Punktgrenze
Manuell auf Bildern gesetzte Punkte 100 Punkte Keine Lizenzbegrenzung Keine Lizenzbegrenzung
Punkte importieren und exportieren 100 Punkte 5.000 Punkte Keine Lizenzbegrenzung
Straßenrouten 5 Adressen 100 Adressen Keine Lizenzbegrenzung
mTSP für mehrere Fahrzeuge Nein Nein Ja
Refined-Profile und LKH-Einstellungen Keine lizenzbedingten Einstellungsgrenzen Keine lizenzbedingten Einstellungsgrenzen Keine lizenzbedingten Einstellungsgrenzen

Online-Server

Funktion Demo Normal / Basic Professional
AIR-Berechnungen Keine allgemeine lizenzbedingte Punktgrenze Keine allgemeine lizenzbedingte Punktgrenze Keine allgemeine lizenzbedingte Punktgrenze
Manuell auf Bildern gesetzte Punkte 100 Punkte Keine Lizenzbegrenzung Keine Lizenzbegrenzung
Punkte importieren und exportieren 100 Punkte 5.000 Punkte Keine Lizenzbegrenzung
Straßenrouten 5 Adressen 100 Adressen Keine Lizenzbegrenzung
mTSP für mehrere Fahrzeuge Nein Nein Ja
Verfügbare Methodeneinstellungen Keine lizenzbedingten Einstellungsgrenzen Keine lizenzbedingten Einstellungsgrenzen Keine lizenzbedingten Einstellungsgrenzen

Für die Online-Version gelten dieselben Lizenzgrenzen wie für die Desktopanwendung. Die Berechnung erfolgt auf dem Server beziehungsweise lokal auf Ihrem Rechner.

Häufig gestellte Fragen

Was ist das Problem des Handlungsreisenden?

Beim Problem des Handlungsreisenden (TSP) wird die kürzestmögliche Rundreise gesucht, die jeden vorgegebenen Punkt beziehungsweise jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Das Problem ist NP-schwer. Für große Instanzen ist kein allgemeiner effizienter Algorithmus bekannt, der die exakte Lösung in praktikabler Zeit liefert.

Worin unterscheiden sich Basic und Professional?

Normal / Basic ist eine kostenpflichtige Lizenz. Für AIR-Berechnungen gilt keine allgemeine lizenzbedingte Punktgrenze. Die Grenze von 5.000 Punkten betrifft den Punktimport und -export. Professional ergänzt mTSP, unbegrenzten Punktimport und -export sowie Straßenrouten ohne lizenzbedingte Adressgrenze. Die praktisch bearbeitbare Größe auf dem Desktop hängt von Hardware, Arbeitsspeicher und gewähltem Modus ab.

Wie lange dauert die Berechnung einer optimierten Route?

Die Berechnungszeit hängt von Punktanzahl, Suchprofil und Hardware ab. Version 3.05 verwendet einen aktualisierten kompilierten Kern und parallele Verarbeitung. Der aktuelle Benchmark mit 30 Instanzen und bewiesenen Optima enthält gemessene Laufzeiten, Parameter und Ergebnisse für jede Instanz.

Kann ich Punkte aus externen Quellen importieren?

Ja. TSP Solver unterstützt den Import von Punkten aus TXT-Dateien. Ausführliche Informationen finden Sie im Benutzerhandbuch.

Welche Algorithmen verwendet das Programm und was zeichnet sie aus?

Desktop 3.05 verwendet drei Hauptmethoden.

  • LKH + Robopol Refined – ein Hybrid mit einer hochwertigen LKH-Ausgangsrundreise und gezielter LKH-Unterstützung während der Refined-Suche. Er erreichte im dargestellten Benchmark in 28 von 30 Fällen das Optimum.
  • Robopol Refined – aktualisierter Kern mit den Profilen Fast, Balanced und Heavy. Im folgenden Benchmark fand Balanced in 27 von 30 Fällen kürzere Rundreisen als eigenständiges LKH (DELAUNAY).
  • LKH-3.0.10 – eigenständige AIR-Optimierung sowie die Berechnungsmethode für Straßenrouten und mTSP.

Was ist zu tun, wenn Windows bei der Installation eine Sicherheitswarnung anzeigt?

Nach dem Herunterladen kann Windows melden, dass der Herausgeber des Programms nicht erkannt wird. Bei TSP Solver hängt diese Meldung mit der fehlenden digitalen Signatur zusammen. Solche Sicherheitsmeldungen können bei Anwendungen kleinerer Entwickler auftreten. So setzen Sie die Installation fort.

  1. Klicken Sie auf den Link „Weitere Informationen“ im Sicherheitsfenster
  2. Klicken Sie anschließend auf die Schaltfläche „Trotzdem ausführen“
  3. Das Programm startet und Sie können die Installation fortsetzen

Die Meldung erscheint, weil für das Programm kein von Windows anerkanntes digitales Herausgeberzertifikat vorliegt. Dies kommt bei kleineren Anwendungen häufig vor.

Eignet sich das Programm für praktische Aufgaben?

Ja. TSP Solver wurde für den praktischen Einsatz in Logistik, Routenplanung und Lieferoptimierung entwickelt. Darüber hinaus eignet es sich für industrielle Anwendungen wie Lasergravur oder Leiterplattenbohren (PCB), bei denen häufig Tausende bis Millionen von Punkten auftreten und die Routenoptimierung die Produktionszeit deutlich verkürzen kann.