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 má rozšírené limity, obsahuje všetky algoritmy vrátane pokročilých, ponúka rozšírené možnosti importu/exportu a prioritnú technickú podporu. Praktický rozsah závisí od hardvéru, pamäte a zvoleného režimu.

The basic version is limited to a maximum of 5000 points. The professional version has expanded limits, includes all algorithms including advanced ones, offers extended import/export options, and priority technical support. Practical scale depends on hardware, memory, and the selected mode.

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 veľmi rýchly pri veľkých vstupoch - približne 100 000 bodov za cca 1 minútu na bežnom PC. Kvalita a čas výpočtu závisia od dát, nastavení a výkonu počítača.

• 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 very fast on large inputs: about 100,000 points in ~1 minute on a regular PC. Route quality and runtime depend on data, settings, and computer performance.

Á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 výkonných algoritmov. Hlavné režimy sú:

TSP Solver uses several powerful algorithms. The main modes are:

• LKH + Robopol Refined - režim najviac zameraný na kvalitu v TSP Solveri. LKH najprv vytvorí veľmi kvalitnú trasu a Robopol Refined potom spustí plný prieskum podľa nastavených parametrov. Je to vhodná voľba, keď je prioritou kvalita trasy. Keďže vstup od LKH býva kvalitný, často stačia slabšie Refined parametre, napríklad num_runs=1-2 a beam_width <= 5.
• LKH + Robopol Escape Polish - rýchly hybrid zameraný na kvalitu. LKH dodá základnú trasu a Robopol sa sústredí na cielený únik z lokálneho minima a rýchle doleštenie trasy. Je vhodný vtedy, keď používateľ chce veľmi dobrú kvalitu, ale nechce púšťať plný Refined prieskum.
• LKH algoritmus - známa kvalitná heuristika pre riešenie TSP, založená na Lin-Kernighan prístupe. Pre inštancie 1000+ bodov je LKH často veľmi dobrá voľba vzhľadom na pomer času a kvality trasy.
• Robopol Fast algoritmus - veľmi rýchly originálny algoritmus pre veľké datasety. Obsahuje turbo režim (100 000 bodov za cca 1 minútu na bežnom PC s dobrým procesorom). Superboost režim znižuje nároky na RAM pri veľkých vstupoch. Kvalita a čas výpočtu závisia od dát, nastavení a výkonu počítača.
• Robopol algoritmus Precise - vylepšená verzia s vyššou presnosťou, zameraná na kvalitnejšie trasy oproti rýchlemu režimu Fast.
• 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 kvalitnejších riešení pre malé a stredne veľké inštancie (testované). Pre n > 2000 sa čas stáva veľmi obmedzujúcim faktorom. Na vybraných dátach môže zlepšiť výsledok oproti LKH. Pre kvalitnejšie výsledky (pre n < 1000): Num Runs > 1, Beam Width > 3, ILS Iterations ≥ 2000, Perturbation Candidates = 16, Candidate Edges/Node = 10.

• LKH + Robopol Refined - the most quality-focused mode in TSP Solver. LKH first builds a very high-quality route, then Robopol Refined runs the full exploration cycle using the configured parameters. It is useful when route quality is the priority. Because the LKH seed is high quality, lighter Refined settings often work well, for example num_runs=1-2 and beam_width <= 5.
• LKH + Robopol Escape Polish - a fast quality-focused hybrid. LKH provides the baseline route and Robopol focuses on targeted escape from a possible local minimum plus fast route polishing. It is useful when the user wants very strong quality without running the full Refined exploration.
• LKH algorithm - a well-known high-quality heuristic for solving TSP, based on the Lin-Kernighan approach. For instances with 1000+ points, LKH is often a very good choice in terms of time-to-quality ratio.
• Robopol Fast algorithm - a very fast original algorithm for large datasets. Includes turbo mode (100,000 points in ~1 minute on a regular PC with a good processor). Superboost mode lowers RAM requirements for large inputs. Route quality and runtime depend on data, settings, and computer performance.
• Robopol Precise algorithm - improved version with higher accuracy, aimed at better route quality than the fast mode.
• 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. Used for finding higher-quality solutions for small and medium-sized instances (tested). For n > 2000, time becomes a very limiting factor. On selected data, Refined can improve on an LKH result. For quality-focused runs (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 pomáha pracovať aj s veľmi veľkými inštanciami TSP problému vrátane TSP Art. Praktický rozsah závisí od hardvéru, pamäte a zvoleného režimu.

These algorithms are implemented with an emphasis on performance and efficiency, which helps with very large TSP instances including TSP Art. Practical scale depends on hardware, memory, and the selected mode.

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.