Einführung
TSP Solver sucht eine möglichst kurze Rundreise, die jeden Punkt genau einmal besucht und zum Start zurückkehrt. Dieses Optimierungsproblem heißt Problem des Handlungsreisenden (Traveling Salesman Problem, TSP). Beispiele sind Logistik, Tourenplanung, Leiterplattenbohrungen, CNC- und Laserbearbeitung, Robotik sowie Drohnenrouten in 2D und 3D.
Die Anwendung bietet LKH, Robopol Refined und ein Hybridverfahren. Sie arbeitet sowohl mit Luftlinienabständen als auch mit Entfernungen im Straßennetz.
Schnellstart
- Wählen Sie Luftlinie (AIR) für Koordinaten oder Straße (ROAD) für Adressen.
- Fügen Sie Punkte auf der Zeichenfläche hinzu oder importieren Sie Koordinaten aus einer
.txt-Datei. Geben Sie im Straßenmodus die Adressen zeilenweise ein und geokodieren Sie sie. - Wählen Sie einen Algorithmus und ein Profil für den gewünschten Kompromiss zwischen Laufzeit und Qualität.
- Starten Sie die Berechnung. Der Solver zeichnet die berechnete Route.
- Exportieren Sie die Punkte, ein Bild oder eine SVG-Datei. Speichern Sie das gesamte Projekt als
.json.
Arbeitsoberfläche
Links finden Sie Projekt-, Datensatz- und Systemwerkzeuge. Die Zeichenfläche liegt in der Mitte. Rechts wählen Sie den Algorithmus, starten die Berechnung und öffnen die Zusammenfassung und Routendetails.

Der Punktzähler meldet eindeutige Koordinaten. Die goldene Markierung zeigt vor der Berechnung den ersten eingegebenen Punkt und danach den Start- und Endpunkt der Route oder das gemeinsame Depot bei mTSP. In den Routendetails sehen Sie Koordinaten, entfernte Duplikate und Berechnungszeit. Den Inhalt können Sie kopieren, löschen oder exportieren.
Doppelte Eingabezeilen erhöhen die Anzahl eindeutiger Punkte nicht.
Layout und Vollbild
Auf schmalen Bildschirmen stehen die Ergebnisse unter der Zeichenfläche. Das Menü öffnen Sie über die Menüschaltfläche. Das Symbol oben rechts auf der Zeichenfläche wechselt zwischen Vollbild und der normalen Ansicht. Die Werkzeuge stehen auch im Vollbildmenü zur Verfügung.
Bei großen Datensätzen können Sie in den Darstellungseinstellungen der Zeichenfläche das Zeichnen überspringen. Die Berechnung läuft dabei weiter.
AIR 3D (x, y, z)
Aktivieren Sie Air 3D, damit der Solver mit räumlichen Entfernungen rechnet. Für manuell gesetzte Punkte wählen Sie die Höhe z am Regler zwischen −1000 und 1000. Sie können auch x y z importieren oder Zufallspunkte mit fester Höhe oder aus einem gleichverteilten Höhenbereich erzeugen.
Öffnen Sie nach der Berechnung die 3D-Ansicht. Ziehen Sie zum Drehen und verwenden Sie das Mausrad zum Zoomen. Das Schließen der Ansicht ändert den Berechnungsmodus nicht. Der TXT-Export enthält Z im 3D-Modus oder wenn mindestens ein Punkt eine Höhe ungleich null hat. Die Import- und Exportformate beschreiben die zulässigen Trennzeichen.

Algorithmen
LKH-3.0.10
Eine bewährte Wahl für Luftlinien- und Straßenrouten sowie mehrere Fahrzeuge. Für AIR können Sie verschiedene Werte für CANDIDATE_SET_TYPE vergleichen. Welcher Wert günstiger ist, hängt von der Anordnung der Punkte ab.
EUC_2D / EUC_3D rundet jede euklidische Kantenlänge auf ganze Einheiten. EXACT_2D / EXACT_3D verwendet eine höhere Genauigkeit.
LKH + Robopol Refined
Das Hybridverfahren priorisiert die Qualität anspruchsvoller Luftlinienrouten und kann mehr Rechenzeit benötigen.
Robopol Refined
Der Optimierer von RoboPol bietet die Profile Fast, Balanced und Heavy. Fast priorisiert kurze Laufzeiten, Balanced eignet sich für allgemeine Aufgaben und Heavy priorisiert die Routenqualität.
Wählen Sie EXACT_2D / EXACT_3D, wenn eine genaue Gesamtentfernung wichtig ist. Beginnen Sie mit den mitgelieferten Profilen. Fast eignet sich für kürzere Berechnungen, Balanced für allgemeine Aufgaben und Heavy oder LKH + Robopol Refined für Aufgaben mit Vorrang der Routenqualität. Der erste Lauf kann einmaligen Initialisierungsaufwand enthalten.
Die Profile werden in der deutschen Oberfläche als Schnell (Fast), Ausgewogen (Balanced) und Intensiv (Heavy) bezeichnet.
Leistung
Die Laufzeit hängt von der Anzahl und Anordnung der Punkte, der Methode, dem Profil und der Hardware ab. Vergleichen Sie die Ergebnisse mehrerer Profile, wenn die Route geschäftskritisch ist. Bei sehr vielen Punkten lässt sich die Zeichenfläche ohne laufende Darstellung betreiben.
Fast priorisiert die Reaktionszeit, Balanced den voreingestellten Kompromiss und Heavy die Qualität. Kein Profil ist für jeden Datensatz am besten. Unterstützt werden 2D und 3D mit interaktiver Ansicht sowie Straßenrouten auf realen Straßennetzen mit Export nach Google Maps. Quelle: RoboPol-Produktseite zu TSP Solver.
Methoden und Profile wählen
- Kurze Wartezeit mit Robopol Refined und Fast.
- Allgemeine Aufgaben mit Robopol Refined und Balanced.
- Hohe AIR-Routenqualität mit Heavy oder LKH + Robopol Refined.
- Straßenrouten und mehrere Fahrzeuge mit LKH-3.0.10.
Beginnen Sie mit den mitgelieferten Profilen. Änderungen an einzelnen Expertenwerten können Rechenzeit, Prozessorauslastung und Speicherbedarf erhöhen. Die Wirkung auf die Route hängt vom Datensatz ab.
Die mitgelieferten Profile bieten getestete Geschwindigkeits- und Qualitätsstufen ohne manuelle Abstimmung. Erweiterte Anpassungen richten sich an erfahrene Benutzer. Höhere Werte garantieren für einen konkreten Datensatz keine bessere Route.
Dateifunktionen
Ein neues Projekt leert die Zeichenfläche und die Ausgabe und behält die Einstellungen bei. Speichern Sie Luftlinien- oder Straßenprojekte als tsp_air_data.json beziehungsweise tsp_road_data.json. Die Funktion zum Öffnen von Projekten lädt gespeicherte TSP-Solver-Projekte.
Sie können Bilder als Vorlage importieren und die aktuelle Ansicht als Bild exportieren. Der SVG-Export speichert Route und Punkte als skalierbare Vektorgrafik.
Gespeicherte Projekte haben die Endung .json, Vektorgrafiken die Endung .svg. Speichern unter öffnet einen Dialog zur Wahl des Dateinamens.
Daten importieren und exportieren
Alle unterstützten Koordinatenformate
x yoderx y zx, yoderx, y, zx; yoderx; y; zn) x yodern) x y zn: x yodern: x y zn, x yodern, x y z
Die Nummerierung wird nur mit einem ausdrücklichen Trennzeichen erkannt, also ), : oder ,. So bleibt die erste ganzzahlige Koordinate einer gültigen 3D-Datei erhalten. Dezimalzahlen verwenden einen Punkt (.).
Vor der Berechnung wird die erste Zeile hervorgehoben. Danach folgt die goldene Markierung der tatsächlichen Routenreihenfolge. Wiederholte Koordinaten werden einmal gezählt. Der TXT-Export speichert Routenpunkte. Ohne 3D-Modus und ohne Z-Wert ungleich null verwendet er x y, andernfalls x y z. Nach dem Erzeugen von Zufallspunkten starten Sie die Routenberechnung mit Berechnen.
Der strukturierte mTSP-Export ist für Maschinen und Werkzeuge vorgesehen. Die Metadaten verwenden diese Syntax:
# TSP_SOLVER_TXT 1 # mode: air # depot: 1 # vehicles: k # objective: MINSUM|MINMAX|MINMAX_SIZE POINTS id x y [z] ROUTES V <vehicle_id> cost=<cost> stops: id id id ...
Für ROAD lautet der Modus # mode: road und das Punktformat id lat lon "address". Die IDs sind 1..n in Dateireihenfolge. Jede Route verweist auf diese IDs.
Beim TXT-Export bleiben das Koordinatentrennzeichen (Leerzeichen, Komma oder Semikolon) und die Nummerierung nach Möglichkeit erhalten. Im Zufallspunktgenerator wählen Sie eine Verteilung und starten anschließend die Routenberechnung.
Darstellung und Algorithmuseinstellungen
Darstellungsoptionen im Einzelnen
Öffnen Sie System → Darstellung oder Einstellungen auf der Zeichenfläche. Der Reiter Zeichenfläche enthält das Farbschema, Hintergrund-, Punkt- und Linienfarbe, Punktgröße, Linienbreite, das dezente Raster und Zeichnen überspringen. Der Reiter Oberfläche enthält Farben für Seite, Seitenleiste, Bedienfelder, Akzent, dunklen Akzent, Text, Rahmen und Eingabefelder. Seitenfarben zurücksetzen stellt die Standardfarben wieder her.
Bei sehr großen Datensätzen mit Zehntausenden bis Millionen Punkten kann das Überspringen des Zeichnens die Bedienbarkeit verbessern. Der Solver rechnet weiter, während die Anzeige von Punkten und Route ausgesetzt ist.
Profile und Suchaufwand
Die Algorithmuseinstellungen haben die Reiter Routenplanung, Robopol Refined und LKH. Bestätigen Sie Änderungen mit Einstellungen anwenden. Beginnen Sie mit einem mitgelieferten Profil. Ändern Sie Einzelwerte, wenn Messungen für Ihren Anwendungsfall den Bedarf zeigen. Einige Werte werden von der gewählten Methode automatisch verwaltet.
Robopol Refined stellt vorhersehbare Regler für den Suchaufwand bereit. Empfindliche interne Parameter werden vom Profil verwaltet. Ihre Wechselwirkungen sind nichtlinear, und unabhängige Änderungen können den wirksamen Optimierungsaufwand verringern oder die Routenqualität verschlechtern.
- Profil lädt einen vollständig getesteten Satz von Geschwindigkeits- und Qualitätseinstellungen.
- Durchläufe bestimmt die Anzahl unabhängiger Optimierungsversuche. Das beste Ergebnis wird übernommen.
- Suchbudget pro Durchlauf begrenzt den Suchaufwand jedes Versuchs.
- Suchbreite bestimmt die Anzahl gleichzeitig beibehaltener aussichtsreicher Alternativen.
- Varianten pro Zyklus bestimmt die Anzahl in jedem Suchzyklus bewerteter Alternativen.
- Eigene Werte werden für Fast, Balanced und Heavy getrennt im Browser gespeichert und bei der Rückkehr zum Profil wiederhergestellt.
- Das Zurücksetzen des aktuellen Profils entfernt nur dessen eigene Werte und stellt die eingebauten Werte wieder her.
Ein höherer Aufwand kostet meist mehr Zeit und kann die Ergebniskonsistenz verbessern. Bei stochastischer Optimierung liefert dennoch nicht jeder einzelne Lauf ein besseres Ergebnis als ein weniger aufwendiges Profil.
Alle mTSP-Felder
- Problemtyp wählt TSP mit einer Route oder Mehrfahrzeug-mTSP.
- Fahrzeuge (
vehicles) legt die Anzahl der Fahrzeuge beziehungsweise Teilrouten fest. - Ziel (
mtsp_objective):MINSUMminimiert die Summe aller Entfernungen oder Zeiten.MINMAXminimiert die längste Einzelroute.MINMAX_SIZEminimiert die höchste Stoppanzahl eines Fahrzeugs und optimiert damit die Arbeitsverteilung statt unmittelbar die Entfernung. - Depotindex (1..n) (
depot_index) bestimmt den gemeinsamen Start und das gemeinsame Ende. 1 bezeichnet den ersten Punkt. Bei ROAD zählt die Reihenfolge erfolgreich geokodierter Adressen. Fehlgeschlagene Zeilen werden übersprungen. - Mindeststopps pro Fahrzeug (
mtsp_min_size) verhindern etwa eine Aufteilung von 1 zu 99 Stopps. Das Depot wird nicht mitgezählt. - Höchststopps pro Fahrzeug (
mtsp_max_size) begrenzen die Arbeitslast. Das Depot wird nicht mitgezählt. - Straßenoptimierung nach (
road_objective) wählt Entfernung in Kilometern oder Zeit in Sekunden.
LKH-Expertenoptionen gelten je nach Methode. Unzutreffende Optionen werden automatisch deaktiviert oder verwaltet. Erhöhte Werte für RUNS und MAX_TRIALS erhöhen in der Regel die Laufzeit. Ändern Sie andere Expertenwerte nur aufgrund eines geprüften Benchmarks oder einer Supportempfehlung. Höhere Werte garantieren kein besseres Ergebnis. mTSP benötigt die Professional-Edition. Den TXT-Export je Fahrzeug beschreibt der Abschnitt Daten importieren und exportieren.



mTSP verwendet LKH-3.0.10 und ist vor allem für AIR 2D und ROAD vorgesehen. Prüfen Sie AIR 3D zunächst an kleineren Aufgaben, bevor Sie große Berechnungen starten.
Bearbeiten und berechnen
Klicken Sie auf die Zeichenfläche, um einen Punkt zu setzen. Zum Entfernen einzelner Punkte aktivieren Sie den Löschmodus. Die Funktion zum Entfernen von Linien löscht die gezeichnete Verbindung. Beim Leeren des Projekts werden Punkte, Routen und das Hintergrundbild entfernt. Die Berechnung benötigt mindestens zwei eindeutige Punkte.
Beim Hinzufügen wird der erste Eingabepunkt hervorgehoben. Nach der Berechnung kennzeichnet die Markierung den tatsächlichen Start und das Ende der Route. Im Löschmodus entfernen Sie einen Punkt durch Anklicken.
TSP Art
In der Desktop-App wählen Sie im Datensatzmenü ein Bild und die gewünschte Punktzahl. Beginnen Sie für eine schnelle Vorschau mit einigen Tausend Punkten. Für einen schnellen LKH-Lauf sind DELAUNAY, RUNS = 1, MAX_TRIALS = 1, MOVE_TYPE = 3 und beide Patching-Werte auf 0 mögliche Startwerte. Passen Sie danach Farben und Linienbreite an und exportieren Sie die Grafik.



Bildvorlagen: John Wick · WildCats Conservation Alliance · Liam Nguyen / Unsplash
Der Desktop-Ablauf lautet Datensatz → TSP-Kunst erzeugen, Bild wählen und Punktzahl eingeben. Mehr Punkte erhöhen Detailgrad, Umwandlungszeit und Berechnungszeit. Wählen Sie LKH-3.0.10, öffnen Sie Algorithmuseinstellungen → LKH und setzen Sie die genannten Werte. Klicken Sie auf Einstellungen anwenden und anschließend auf Berechnen. Über Darstellung → Zeichenfläche passen Sie Hintergrund-, Punkt- und Routenfarbe an. Exportieren Sie je nach Bedarf Bild, Punkte oder SVG.
Die vom Autor bereitgestellten Aufnahmen zeigen die vollständige Oberfläche der Version 3.05 mit gewähltem Algorithmus und Ergebnis. John Wick zeigt 100.000 eindeutige Punkte mit LKH, der Tiger 100.000 Punkte in der hellen Oberfläche und die Rose 50.000 Punkte in der dunklen Oberfläche. Die Beispiele dienen der Illustration und enthalten keine Laufzeitgarantie für andere Computer oder Datensätze.
Beispiele und Bildschirmfotos
Jede Aufnahme zeigt das vollständige Fenster der Version 3.05. Klicken Sie auf ein Bild zum Öffnen und wählen Sie 1:1 für die Originalgröße.
Schrittfolge für Bildvorlagen
- Öffnen Sie Datei → Bild importieren.
- Setzen Sie Punkte auf die Vorlage, wählen Sie einen Algorithmus und klicken Sie auf Berechnen.
- Exportieren Sie Bild, Punkte oder SVG und bewahren Sie das Projekt mit Speichern unter auf.
Schrittfolge für TXT-Koordinaten
- Bereiten Sie Koordinaten mit einem unterstützten Trennzeichen vor.
- Öffnen Sie Datensatz → Punkte importieren und berechnen Sie die Route.
- Vergleichen Sie die Anzahl eindeutiger Punkte mit den Routendetails und exportieren Sie das Ergebnis.









Straßenrouten
Bei mTSP starten und enden alle Fahrzeuge am gemeinsamen Depot. depot_index beginnt bei 1 und bezieht sich auf die Reihenfolge der erfolgreich geokodierten Adressen. Fehlgeschlagene Adressen werden übersprungen. Geokodierung und Routenberechnung auf dem Straßennetz nutzen externe Dienste.
Der Straßenmodus kombiniert Geokodierung und Routing auf realen Straßennetzen. Über Algorithmuseinstellungen → Routenplanung aktivieren Sie mTSP und legen Fahrzeuge, Ziel, Depot und Stoppgrenzen fest. Dieselbe Funktion unterstützt AIR 2D. Testen Sie AIR 3D zuerst mit kleinen Aufgaben.
Wählen Sie ROAD, geben Sie eine Adresse pro Zeile ein, geokodieren Sie die Liste und berechnen Sie die Route. Karte anzeigen öffnet eine interaktive Vorschau. Der Google-Maps-Export ermöglicht Navigation und das Senden der Route an ein Telefon. Eine Internetverbindung ist erforderlich. Externe Routinganfragen können die Berechnung verlangsamen.


Lizenz und Editionen
Die Editionen unterscheiden sich in Punktgrenzen, Import- und Exportrechten sowie Straßenroutenfunktionen. Aktivieren Sie erworbene Funktionen unter Info → Lizenzschlüssel. Demo dient der Bewertung mit begrenzten Punkten und Funktionen. Basic eignet sich für kleinere Projekte und Reiseplanung. Professional bietet den vollen Funktionsumfang mit höheren Grenzen. Die praktische Datensatzgröße hängt von Hardware, Arbeitsspeicher und gewähltem Modus ab.
Browseranforderungen
Sie benötigen einen modernen Browser und Internetzugang. Die 3D-Ansicht benötigt WebGL. Die Berechnung läuft auf dem Server.
Für die Online-Berechnung ist keine Installation des Desktop-Solvers erforderlich.
Hinweise und Tipps
- Für zuverlässigere Geokodierung geben Sie Straße, Hausnummer, Postleitzahl, Ort und Land an.
- Beginnen Sie bei großen AIR-Datensätzen mit Fast und deaktivieren Sie bei Bedarf das Zeichnen.
- Verwenden Sie SVG zur Nachbearbeitung in einem Vektorgrafikprogramm und einen Dezimalpunkt in Koordinatendateien.
SVG eignet sich für saubere Skalierung und Vektorbearbeitung, etwa in Inkscape oder Illustrator.
Über die Sprachauswahl wechseln Sie die Sprache direkt im geöffneten Arbeitsbereich. Punkte, Routen, Adressen, offene Dialoge und laufende Berechnungen bleiben dabei erhalten.