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 100 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 100 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. Podobne LKH algoritmus, ktorý je implementovaný ako wrapper okolo natívneho kódu, potrebuje pri prvom spustení inicializovať prostredie a načítať potrebné knižnice. 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 sekundách, LKH algoritmus tiež zvláda výpočet do 1000 bodov v sekundách
• Pre veľké inštancie (1000-10000 bodov) Robopol algoritmus potrebuje len sekundy na výpočet
• Pre veľmi veľké inštancie (10000-50000 bodov) ako napríklad TSP Art môže výpočet trvať dlhšie (minuty), ale stále je výrazne rýchlejší ako konkurencia

• 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 seconds, the LKH algorithm also handles calculation up to 1000 points in seconds
• For large instances (1000-10000 points), the Robopol algorithm needs only seconds for calculation
• For very large instances (10000-50000 points) such as TSP Art, the calculation may take longer (minutes), but is still significantly faster than competitors

Á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.
• Robopol algoritmus - originálny algoritmus vyvinutý autorom Ing. Robertom Polákom, ktorý kombinuje rýchlosť a presnosť.
• Robopol algoritmus Precise - vylepšená verzia s vyššou presnosťou, ktorá dosáhne takmer optimálne výsledky porovnateľné s LKH algoritmom.

• 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.
• Robopol algorithm - original algorithm developed by the author Ing. Robert Polák, which combines speed and accuracy.
• Robopol Precise algorithm - improved version with higher accuracy that achieves near-optimal results comparable to the LKH algorithm.

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 desiatkam tisíc 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 tens of thousands 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, optimalizácii doručovania a podobných úlohách.

Yes, TSP Solver is designed for practical use in logistics, route planning, delivery optimization, and similar tasks.