TSP Solver

Problém obchodného cestujúceho (TSP) je úloha nájsť najkratšiu možnú trasu, ktorá prechádza všetkými zadanými bodmi (mestami) práve raz a vráti sa do východiskového bodu. Tento problém patrí medzi NP-ťažké problémy, čo znamená, že pre veľké inštancie neexistuje efektívny algoritmus, ktorý by našiel presné riešenie v rozumnom čase.

The traveling salesman problem (TSP) is the task of finding the shortest possible route that passes through all given points (cities) exactly once and returns to the starting point. This problem belongs to the NP-hard problems, which means that for large instances there is no efficient algorithm that would find an exact solution in a reasonable time.

Základná verzia je obmedzená na maximálne 5000 bodov. Profesionálna verzia nemá žiadne obmedzenia počtu bodov, obsahuje všetky algoritmy vrátane pokročilých, ponúka rozšírené možnosti importu/exportu a prioritnú technickú podporu.

The basic version is limited to a maximum of 5000 points. The professional version has no limitations on the number of points, includes all algorithms including advanced ones, offers extended import/export options, and priority technical support.

Doba výpočtu závisí od počtu bodov a zvoleného algoritmu. Všetky algoritmy sú vysoko optimalizované:

Calculation time depends on the number of points and the selected algorithm. All algorithms are highly optimized:

• Prvé spustenie algoritmov je pomalšie z technických dôvodov: Robopol algoritmus využíva knižnicu NUMBA, ktorá pri prvom spustení prekladá Python kód do optimalizovaného strojového kódu (JIT kompilácia), čo výrazne zrýchľuje následné výpočty. Všetky ďalšie výpočty už prebiehajú plnou rýchlosťou.
• Pre malé inštancie (do 100 bodov) je výpočet takmer okamžitý
• Pre stredné inštancie (100-1000 bodov) Robopol algoritmus zvláda výpočet v milisekundách, LKH algoritmus tiež zvláda výpočet do 1000 bodov v milisekundách. robopol refined zvláda výpočet do 1000 bodov v desiatkach sekúnd, závisí od nastavenia a výkonu procesora
• Pre veľké inštancie (1000-10000 bodov) Robopol Fast algoritmus potrebuje len sekundy na výpočet
• Pre veľmi veľké inštancie (státisíce až milióny bodov) je Robopol Fast s turbo režimom určený práve pre takéto obrovské inštancie - zvládne milióny bodov v rozumnom čase (100 000 bodov za cca 1 minútu) s kvalitou ~2,4% nad optimom. LKH na takéto veľké inštancie nie je použiteľný.

• The first run of algorithms is slower for technical reasons: The Robopol algorithm uses the NUMBA library, which translates Python code into optimized machine code (JIT compilation) on first run, significantly speeding up subsequent calculations. Similarly, the LKH algorithm, which is implemented as a wrapper around native code, needs to initialize the environment and load necessary libraries on first run. All subsequent calculations already run at full speed.
• For small instances (up to 100 points), the calculation is almost instantaneous
• For medium instances (100-1000 points), the Robopol algorithm handles calculation in milliseconds, the LKH algorithm also handles calculation up to 1000 points in milliseconds. Robopol Refined handles calculation up to 1000 points in tens of seconds, depending on settings and processor performance
• For large instances (1000-10000 points), the Robopol Fast algorithm needs only seconds for calculation
• For very large instances (hundreds of thousands to millions of points), Robopol Fast with turbo mode is designed specifically for such huge instances - handles millions of points in reasonable time (100,000 points in ~1 minute) with quality ~2.4% above optimum. LKH is not usable for such large instances.

Áno, TSP Solver podporuje import bodov z TXT formátov. Presnejšie informácie nájde užívateľ v dokumentácii - help.

Yes, TSP Solver supports importing points from TXT formats. More precise information can be found in the documentation - help.

TSP Solver používa niekoľko špičkových algoritmov. Medzi najlepšie patria:

TSP Solver uses several cutting-edge algorithms. Among the best are:

• LKH algoritmus - jeden z najlepších algoritmov pre riešenie TSP, založený na Lin-Kernighan heuristike, ktorý dosáhuje takmer optimálne výsledky aj pre veľké inštancie. Pre inštancie 1000+ bodov je LKH najlepšia voľba vzhľadom na pomer času a kvality trasy, ak užívateľ potrebuje optimálne alebo blízko optima riešenia.
• Robopol Fast algoritmus - extrémne rýchly originálny algoritmus vyvinutý autorom Ing. Robertom Polákom, určený práve pre obrovské inštancie s miliónmi bodov. Obsahuje turbo režim (100 000 bodov za cca 1 minútu na bežnom PC s dobrým procesorom). Kvalita trasy sa udržuje na ~2,4% nad optimom aj pri miliónoch bodov, pri symetrických bodoch (TSP Art) ~0,5% nad optimom. Superboost režim je ~3x rýchlejší ako turbo s kvalitou ~2,5% a šetrí RAM pamäť pre veľa bodov - oplatí sa pre inštancie > 40 000 bodov. Omnoho rýchlejší ako LKH, ktorý na takéto veľké inštancie nie je použiteľný.
• Robopol algoritmus Precise - vylepšená verzia s vyššou presnosťou, ktorá dosáhne takmer optimálne výsledky porovnateľné s LKH algoritmom.
• Robopol Refined - Pokročilá metóda využívajúca Iterated Local Search (ILS) na vylepšenie riešení z Robopol Precise. Je pomalší ako ostatné heuristiky, ale omnoho rýchlejší ako exaktné algoritmy. Slúži na hľadanie optimálnych riešení pre malé a stredne veľké inštancie (testované). Pre n > 2000 sa čas stáva veľmi obmedzujúcim faktorom. Ak LKH nenájde optimum, Refined ho môže nájsť. Pre dosiahnutie lepšieho výsledku ako LKH (pre n < 1000): Num Runs > 1, Beam Width > 3, ILS Iterations ≥ 2000, Perturbation Candidates = 16, Candidate Edges/Node = 10.

• LKH algorithm - one of the best algorithms for solving TSP, based on the Lin-Kernighan heuristic, which achieves near-optimal results even for large instances. For instances with 1000+ points, LKH is the best choice in terms of time-to-quality ratio when the user needs optimal or near-optimal solutions.
• Robopol Fast algorithm - extremely fast original algorithm developed by the author Ing. Robert Polák, designed specifically for huge instances with millions of points. Includes turbo mode (100,000 points in ~1 minute on a regular PC with a good processor). Route quality is maintained at ~2.4% above optimum even for millions of points, for symmetric points (TSP Art) ~0.5% above optimum. Superboost mode is ~3x faster than turbo with quality ~2.5% and saves RAM memory for large instances - recommended for instances > 40,000 points. Much faster than LKH, which is not usable for such large instances.
• Robopol Precise algorithm - improved version with higher accuracy that achieves near-optimal results comparable to the LKH algorithm.
• Robopol Refined - Advanced method utilizing Iterated Local Search (ILS) to improve solutions from Robopol Precise. It is slower than other heuristics, but much faster than exact algorithms. Designed for finding optimal solutions for small and medium-sized instances (tested). For n > 2000, time becomes a very limiting factor. If LKH doesn't find the optimum, Refined can find it. For better results than LKH (for n < 1000): Num Runs > 1, Beam Width > 3, ILS Iterations ≥ 2000, Perturbation Candidates = 16, Candidate Edges/Node = 10.

Tieto algoritmy sú implementované s dôrazom na výkon a efektivitu, čo umožňuje riešiť aj veľmi veľké inštancie TSP problému vrátane TSP Art s miliónmi bodov.

These algorithms are implemented with an emphasis on performance and efficiency, which allows solving very large instances of the TSP problem including TSP Art with millions of points.

Po stiahnutí inštalačného súboru Vám Windows môže zobraziť okno, že nepozná vydavateľa programu. TSP Solver nie je malware, ide len o bezpečnostné opatrenie Windows pre menších vývojárov. Postupujte nasledovne:

After downloading the installation file, Windows may display a window stating that it doesn't recognize the program publisher. TSP Solver is not malware, this is just a Windows security measure for smaller developers. Proceed as follows:

1. Kliknite na odkaz "Ďalšie informácie" v bezpečnostnom okne
2. Potom kliknite na tlačidlo "Napriek tomu spustiť"
3. Program sa spustí a môžete pokračovať v inštalácii

1. Click on the "More info" link in the security window
2. Then click on the "Run anyway" button
3. The program will start and you can continue with the installation

Toto upozornenie sa zobrazuje, pretože program nie je digitálne podpísaný certifikátom od Microsoft, čo je bežné pre menšie aplikácie.

This warning appears because the program is not digitally signed with a Microsoft certificate, which is common for smaller applications.

Áno, TSP Solver je navrhnutý pre praktické použitie v logistike, plánovaní trás a optimalizácii doručovania. Okrem toho je vhodný aj pre priemyselné aplikácie ako laserové gravírovanie alebo vŕtanie DPS (plošných spojov), kde sú často tisíce až milióny bodov a optimalizácia trasy výrazne skracuje čas výroby.

Yes, TSP Solver is designed for practical use in logistics, route planning, and delivery optimization. Additionally, it is suitable for industrial applications such as laser engraving or PCB drilling (printed circuit boards), where there are often thousands to millions of points and route optimization significantly reduces production time.