TSP Solver

Program na hľadanie optimalizovanej trasy pre problém obchodného cestujúceho

Vyskúšajte 1 000 náhodných bodov v bezplatnej online demo verzii Vygenerujte si náhodné AIR body a porovnajte algoritmy. Na náhodne generované AIR body sa nevzťahuje limit 100 bodov demo verzie. Počet bodov si zvolíte v ponuke Dáta → Náhodné generovanie (Data → Random Gen). Vyskúšať algoritmy online

Čo je TSP Solver?

TSP Solver je program určený na hľadanie optimalizovanej trasy tzv. problému obchodného cestujúceho (TSP- Travelling Salesman Problem). Tento problém patrí medzi najznámejšie problémy kombinatorickej optimalizácie. Úlohou je hľadať čo najkratšiu praktickú trasu, ktorá prechádza všetkými zadanými bodmi (mestami) práve raz a vráti sa do východiskového bodu. Program podporuje 2D aj 3D súradnice (x, y, z) s interaktívnou 3D vizualizáciou. Je vhodný nielen pre logistiku a plánovanie trás, ale aj pre plánovanie trás pre drony, robotiku, a priemyselné aplikácie ako laserové gravírovanie, vŕtanie DPS (plošných spojov) či 3D tlač a CNC stroje, kde optimalizácia trasy výrazne skracuje čas výroby.

TSP Solver 3.05 prináša nové prehľadné rozhranie a aktualizované jadro Robopol Refined. Podporuje AIR 2D/3D, cestné trasy a viac vozidiel cez LKH. Profily Fast, Balanced a Heavy umožňujú zvoliť rozsah vyhľadávania.

Balanced je predvolený profil pre pomer času a kvality. V benchmarku 30 upravených tetrahedrálnych inštancií našiel kratšiu trasu než LKH (DELAUNAY) v 27 prípadoch a v 3 dosiahol rovnakú dĺžku; optimum dosiahol 24-krát oproti 3 zásahom LKH. Heavy rozširuje vyhľadávanie a Fast uprednostňuje kratší výpočet. Výsledky závisia od dát a nastavení.

Silu algoritmov si môžete vyskúšať na náhodne generovaných bodoch v online verzii TSP Solver. Táto možnosť je dostupná aj v bezplatnej demo verzii.

Online aplikácia aj verzie pre Windows a Linux obsahujú rozhranie, hlásenia a príručky v angličtine, nemčine, španielčine a zjednodušenej čínštine. Pri prepnutí jazyka sa zachová rozpracovaná trasa.

Balanced: kratšia trasa v 27 z 30 prípadov

Balanced je predvolený profil pre pomer času a kvality. V benchmarku 30 upravených tetrahedrálnych inštancií našiel kratšiu trasu než LKH (DELAUNAY) v 27 prípadoch a v 3 dosiahol rovnakú dĺžku; optimum dosiahol 24-krát oproti 3 zásahom LKH. Heavy rozširuje vyhľadávanie a Fast uprednostňuje kratší výpočet. Výsledky závisia od dát a nastavení.

Nové rozhranie TSP Solver 3.05 s vypočítanou trasou.

Nové rozhranie TSP Solver 3.05 s vypočítanou trasou.

Optimalizácia trasy

Hľadajte veľmi krátku optimalizovanú trasu medzi zadanými bodmi. Profily Fast, Balanced a Heavy umožňujú zvoliť pomer rýchlosti a rozsahu vyhľadávania.

Podpora 3D bodov

Pracujte s 3D súradnicami (x, y, z) pre priestorové optimalizácie. Ideálne pre plánovanie letových trás pre drony, optimalizáciu pohybu robotických ramien, navigáciu v viacposchodových skladoch či optimalizáciu dráhy pre 3D tlač a CNC stroje. Interaktívna 3D vizualizácia umožňuje rotáciu a priblíženie výslednej trasy.

TSP Art

Vytvárajte umelecké diela pomocou jednej spojitej čiary prechádzajúcej cez tisíce bodov.

Pokročilé algoritmy

Balanced je predvolený profil pre pomer času a kvality. V benchmarku 30 upravených tetrahedrálnych inštancií našiel kratšiu trasu než LKH (DELAUNAY) v 27 prípadoch a v 3 dosiahol rovnakú dĺžku; optimum dosiahol 24-krát oproti 3 zásahom LKH. Heavy rozširuje vyhľadávanie a Fast uprednostňuje kratší výpočet. Výsledky závisia od dát a nastavení.

Import a Export

Importujte body z textových súborov, exportujte trasy, uložte projekty a vytvárajte obrázky z výsledkov.

Vzdialenosť po cestách & Google Mapy

Vypočítajte optimalizovanú trasu s rešpektovaním cestnej siete. Výslednú trasu môžete otvoriť priamo v Google Mapách a odoslať do navigácie vo vašom telefóne.

Multi-vehicle mTSP

Rozdeľte trasu medzi viac vozidiel pomocou LKH algoritmu. Podporuje najmä AIR 2D a cestné vzdialenosti; väčšie AIR 3D úlohy odporúčame najprv overiť na menších dátach. Nastavte počet vozidiel, depot, cieľ optimalizácie (MINSUM/MINMAX) a limity zastávok na vozidlo. Dostupné v Professional licencii.

Optimalizované pre mobily

Aplikácia je plne responzívna a optimalizovaná pre pohodlné používanie na tabletoch a smartfónoch. Navyše je teraz dostupná aj online na tspsolver.robopol.sk bez nutnosti inštalácie.

Ukážky programu

TSP Solver 3.05 – John Wick TSP Art, Windows

TSP Art vo Windows – John Wick, 100 000 bodov

TSP Solver - hlavné okno programu

TSP Solver - hlavné okno programu

TSP Solver - vizualizácia trasy pre mestá v Českej republike

Vizualizácia optimalizovanej trasy pre mestá v Českej republike

AIR 3D – model draka, 12 000 bodov, Refined Balanced

AIR 3D – model draka, 12 000 bodov, Refined Balanced

Optimalizovaná cestná trasa cez Paríž

Optimalizovaná cestná trasa cez Paríž

Optimalizovaná cestná trasa cez Fínsko

Optimalizovaná cestná trasa cez Fínsko

Cestné adresy a odovzdanie trasy do Google Maps

Cestné adresy a odovzdanie trasy do Google Maps

TSP Solver - Multi-vehicle mTSP 3D

Multi-vehicle mTSP - 3D trasy (x, y, z)

TSP Solver - Multi-vehicle mTSP Road

Multi-vehicle mTSP - cestné vzdialenosti

Ako to funguje

1

Zadanie bodov

Zadajte body (mestá) buď manuálne kliknutím na plátno, importom zo súboru, alebo zadaním adries pre geocoding (cestné vzdialenosti).

2

Výber algoritmu

Zvoľte si algoritmus a jeho parametre podľa veľkosti problému a požadovanej presnosti.

3

Výpočet

Program vypočíta optimalizovanú trasu pomocou vybraného algoritmu.

4

Výsledky

Prehliadnite si výsledky vrátane grafickej vizualizácie trasy a štatistík.

Technické detaily

Použité algoritmy

TSP Solver Desktop 3.05 ponúka tieto metódy:

  • LKH + Robopol Refined - kombinovaný režim pre AIR 2D/3D TSP. Začína zo silnej LKH trasy a počas Refined optimalizácie selektívne využíva ďalšie LKH zlepšenia.
  • Robopol Refined – aktualizované jadro s profilmi Fast, Balanced a Heavy. V uvedenom benchmarku našiel Balanced kratšie trasy než LKH (DELAUNAY) v 27 z 30 prípadov.
  • LKH-3.0.10 – samostatná optimalizácia AIR trás a výpočtová metóda pre cestné trasy a mTSP.

Balanced je predvolený profil pre pomer času a kvality. V benchmarku 30 upravených tetrahedrálnych inštancií našiel kratšiu trasu než LKH (DELAUNAY) v 27 prípadoch a v 3 dosiahol rovnakú dĺžku; optimum dosiahol 24-krát oproti 3 zásahom LKH. Heavy rozširuje vyhľadávanie a Fast uprednostňuje kratší výpočet. Výsledky závisia od dát a nastavení.

Výkonnosť

Balanced je predvolený profil pre pomer času a kvality. V benchmarku 30 upravených tetrahedrálnych inštancií našiel kratšiu trasu než LKH (DELAUNAY) v 27 prípadoch a v 3 dosiahol rovnakú dĺžku; optimum dosiahol 24-krát oproti 3 zásahom LKH. Heavy rozširuje vyhľadávanie a Fast uprednostňuje kratší výpočet. Výsledky závisia od dát a nastavení.

Testované na 8-jadrovom procesore

AMD Ryzen 7 5700X3D

8 fyzických jadier / 16 vlákien

Benchmark 3.05: súhrn a nastavenia

Benchmark TSP Solver 3.05 obsahuje 30 upravených tetrahedrálnych inštancií T′n,m, 157 až 4 396 bodov a 120 výsledkov. Meranie prebehlo 7. septembra 2026. Každá metóda dostala rovnaké body; optimum vychádza z matematicky dokázanej trasy tejto rodiny.

Balanced našiel kratšiu trasu než LKH (DELAUNAY) v 27 z 30 prípadov a v 3 sa zhodovali. Optimum dosiahol 24-krát, Heavy 27-krát, hybrid 28-krát a samostatný LKH 3-krát. Tieto výsledky platia pre uvedenú rodinu a nastavenia.

Gap (%) = (dĺžka trasy − optimum) / optimum × 100. Dĺžky sú súčtom euklidovských vzdialeností vrátane návratu do prvého bodu; pri vyhodnotení sa hrany nezaokrúhľujú na celé čísla. Zaokrúhľuje sa až zobrazenie v tabuľke.

Metóda / profilZásahy optimaPriemerný gapNajväčší gapPriemerný čas
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. Použitá metrika solverov je EXACT_2D. Profily Refined zostali Balanced a Heavy; hybrid používa Balanced.

Časy zahŕňajú volanie lokálnej aplikácie a výpočet, po jednom úspešnom spustení každej kombinácie inštancie a profilu. Časový rozpočet metód nie je rovnaký. Dva neúspešné štarty hybridu boli zopakované; čas neúspešných pokusov nie je v priemeroch.

Porovnanie všetkých 30 inštancií
InštanciaBodyDokázané optimumBalanced gapHeavy gapHybrid gapLKH (DELAUNAY) gap
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 %
Všetkých 120 výsledkov a časy
InštanciaBodyMetóda / profilOptimumDĺžka trasyGapZásah optimaČas
Tprime_40_22157Robopol Refined — Balanced192.212882661192.2128826610 %Áno0.909 s
Tprime_40_22157Robopol Refined — Heavy192.212882661192.2128826610 %Áno1.729 s
Tprime_40_22157LKH + Robopol Refined — Balanced192.212882661192.2128826610 %Áno1.096 s
Tprime_40_22157LKH-3.0.10 (DELAUNAY)192.212882661192.2128826610 %Áno0.224 s
Tprime_40_30172Robopol Refined — Balanced194.847837500194.8478375000 %Áno0.926 s
Tprime_40_30172Robopol Refined — Heavy194.847837500194.8478375000 %Áno1.656 s
Tprime_40_30172LKH + Robopol Refined — Balanced194.847837500194.8478375000 %Áno1.114 s
Tprime_40_30172LKH-3.0.10 (DELAUNAY)194.847837500194.8478375000 %Áno0.172 s
Tprime_40_40187Robopol Refined — Balanced192.962720228192.9627202280 %Áno0.995 s
Tprime_40_40187Robopol Refined — Heavy192.962720228192.9627202280 %Áno2.226 s
Tprime_40_40187LKH + Robopol Refined — Balanced192.962720228192.9627202280 %Áno1.364 s
Tprime_40_40187LKH-3.0.10 (DELAUNAY)192.962720228192.9967691730.01764535 %Nie0.214 s
Tprime_40_60223Robopol Refined — Balanced195.027984994195.0279849940 %Áno0.935 s
Tprime_40_60223Robopol Refined — Heavy195.027984994195.0279849940 %Áno1.934 s
Tprime_40_60223LKH + Robopol Refined — Balanced195.027984994195.0279849940 %Áno1.232 s
Tprime_40_60223LKH-3.0.10 (DELAUNAY)195.027984994195.8185386880.40535398 %Nie0.303 s
Tprime_60_30244Robopol Refined — Balanced317.734912890317.7349128900 %Áno0.947 s
Tprime_60_30244Robopol Refined — Heavy317.734912890317.7349128900 %Áno1.905 s
Tprime_60_30244LKH + Robopol Refined — Balanced317.734912890317.7349128900 %Áno1.263 s
Tprime_60_30244LKH-3.0.10 (DELAUNAY)317.734912890317.7349128900 %Áno0.410 s
Tprime_40_80256Robopol Refined — Balanced194.579079268194.5790792680 %Áno1.184 s
Tprime_40_80256Robopol Refined — Heavy194.579079268194.5790792680 %Áno2.380 s
Tprime_40_80256LKH + Robopol Refined — Balanced194.579079268194.5790792680 %Áno1.327 s
Tprime_40_80256LKH-3.0.10 (DELAUNAY)194.579079268195.3958520770.41976394 %Nie0.326 s
Tprime_60_45277Robopol Refined — Balanced320.010658955320.0106589550 %Áno1.013 s
Tprime_60_45277Robopol Refined — Heavy320.010658955320.0106589550 %Áno2.027 s
Tprime_60_45277LKH + Robopol Refined — Balanced320.010658955320.0106589550 %Áno1.187 s
Tprime_60_45277LKH-3.0.10 (DELAUNAY)320.010658955320.2904526550.08743262 %Nie0.194 s
Tprime_60_60307Robopol Refined — Balanced318.008549800318.0085498000 %Áno1.058 s
Tprime_60_60307Robopol Refined — Heavy318.008549800318.0085498000 %Áno2.182 s
Tprime_60_60307LKH + Robopol Refined — Balanced318.008549800318.0085498000 %Áno1.229 s
Tprime_60_60307LKH-3.0.10 (DELAUNAY)318.008549800318.3234635840.09902683 %Nie0.226 s
Tprime_60_90373Robopol Refined — Balanced320.196466000320.1964660000 %Áno1.155 s
Tprime_60_90373Robopol Refined — Heavy320.196466000320.1964660000 %Áno2.398 s
Tprime_60_90373LKH + Robopol Refined — Balanced320.196466000320.1964660000 %Áno1.367 s
Tprime_60_90373LKH-3.0.10 (DELAUNAY)320.196466000321.6306678520.44791308 %Nie0.550 s
Tprime_100_50424Robopol Refined — Balanced569.468015630569.4680156300 %Áno1.142 s
Tprime_100_50424Robopol Refined — Heavy569.468015630569.4680156300 %Áno2.295 s
Tprime_100_50424LKH + Robopol Refined — Balanced569.468015630569.4680156300 %Áno1.443 s
Tprime_100_50424LKH-3.0.10 (DELAUNAY)569.468015630569.4688100150.00013950 %Nie1.120 s
Tprime_60_120436Robopol Refined — Balanced319.719344927319.7193449270 %Áno1.268 s
Tprime_60_120436Robopol Refined — Heavy319.719344927319.7193449270 %Áno2.682 s
Tprime_60_120436LKH + Robopol Refined — Balanced319.719344927319.7193449270 %Áno1.699 s
Tprime_60_120436LKH-3.0.10 (DELAUNAY)319.719344927321.1992424180.46287393 %Nie1.073 s
Tprime_100_75487Robopol Refined — Balanced571.807831276571.8078312760 %Áno1.211 s
Tprime_100_75487Robopol Refined — Heavy571.807831276571.8078312760 %Áno2.294 s
Tprime_100_75487LKH + Robopol Refined — Balanced571.807831276571.8078312760 %Áno1.458 s
Tprime_100_75487LKH-3.0.10 (DELAUNAY)571.807831276571.9611542140.02681372 %Nie0.193 s
Tprime_100_100547Robopol Refined — Balanced569.748882106569.7488821060 %Áno1.325 s
Tprime_100_100547Robopol Refined — Heavy569.748882106569.7488821060 %Áno2.537 s
Tprime_100_100547LKH + Robopol Refined — Balanced569.748882106569.7488821060 %Áno1.557 s
Tprime_100_100547LKH-3.0.10 (DELAUNAY)569.748882106569.8056476540.00996326 %Nie0.188 s
Tprime_100_150673Robopol Refined — Balanced571.996822109571.9968221090 %Áno1.459 s
Tprime_100_150673Robopol Refined — Heavy571.996822109571.9968221090 %Áno2.710 s
Tprime_100_150673LKH + Robopol Refined — Balanced571.996822109571.9968221090 %Áno1.691 s
Tprime_100_150673LKH-3.0.10 (DELAUNAY)571.996822109573.8335159070.32110210 %Nie0.222 s
Tprime_180_90784Robopol Refined — Balanced1073.8860050021073.8860050020 %Áno1.498 s
Tprime_180_90784Robopol Refined — Heavy1073.8860050021073.8860050020 %Áno3.303 s
Tprime_180_90784LKH + Robopol Refined — Balanced1073.8860050021073.8860050020 %Áno2.426 s
Tprime_180_90784LKH-3.0.10 (DELAUNAY)1073.8860050021073.8870369570.00009610 %Nie1.526 s
Tprime_100_200796Robopol Refined — Balanced571.505887676571.5058876760 %Áno1.692 s
Tprime_100_200796Robopol Refined — Heavy571.505887676571.5058876760 %Áno3.781 s
Tprime_100_200796LKH + Robopol Refined — Balanced571.505887676571.5058876760 %Áno3.620 s
Tprime_100_200796LKH-3.0.10 (DELAUNAY)571.505887676571.5103434900.00077966 %Nie2.003 s
Tprime_180_135907Robopol Refined — Balanced1076.2561503221076.2561503220 %Áno1.301 s
Tprime_180_135907Robopol Refined — Heavy1076.2561503221076.2561503220 %Áno2.676 s
Tprime_180_135907LKH + Robopol Refined — Balanced1076.2561503221076.2561503220 %Áno1.845 s
Tprime_180_135907LKH-3.0.10 (DELAUNAY)1076.2561503221078.0065235330.16263537 %Nie0.208 s
Tprime_180_1801027Robopol Refined — Balanced1074.1706995841074.1706995840 %Áno1.753 s
Tprime_180_1801027Robopol Refined — Heavy1074.1706995841074.1706995840 %Áno3.276 s
Tprime_180_1801027LKH + Robopol Refined — Balanced1074.1706995841074.1706995840 %Áno1.944 s
Tprime_180_1801027LKH-3.0.10 (DELAUNAY)1074.1706995841075.6410669260.13688396 %Nie0.253 s
Tprime_180_2701273Robopol Refined — Balanced1076.4468342451076.4468342450 %Áno2.217 s
Tprime_180_2701273Robopol Refined — Heavy1076.4468342451076.4468342450 %Áno4.296 s
Tprime_180_2701273LKH + Robopol Refined — Balanced1076.4468342451076.4468342450 %Áno7.379 s
Tprime_180_2701273LKH-3.0.10 (DELAUNAY)1076.4468342451078.5028714820.19100221 %Nie0.299 s
Tprime_300_1501324Robopol Refined — Balanced1830.8689210901830.8689405220.00000106 %Nie2.203 s
Tprime_300_1501324Robopol Refined — Heavy1830.8689210901830.8689210900 %Áno5.207 s
Tprime_300_1501324LKH + Robopol Refined — Balanced1830.8689210901830.8689210900 %Áno3.286 s
Tprime_300_1501324LKH-3.0.10 (DELAUNAY)1830.8689210901830.8707056740.00009747 %Nie0.826 s
Tprime_180_3601516Robopol Refined — Balanced1075.9494208581075.9494208580 %Áno2.224 s
Tprime_180_3601516Robopol Refined — Heavy1075.9494208581075.9494208580 %Áno4.691 s
Tprime_180_3601516LKH + Robopol Refined — Balanced1075.9494208581075.9494208580 %Áno3.634 s
Tprime_180_3601516LKH-3.0.10 (DELAUNAY)1075.9494208581078.0665638170.19676975 %Nie3.967 s
Tprime_300_2251537Robopol Refined — Balanced1833.2515532631833.2515532630 %Áno1.819 s
Tprime_300_2251537Robopol Refined — Heavy1833.2515532631833.2515532630 %Áno3.635 s
Tprime_300_2251537LKH + Robopol Refined — Balanced1833.2515532631833.2515532630 %Áno2.767 s
Tprime_300_2251537LKH-3.0.10 (DELAUNAY)1833.2515532631834.6638955230.07704029 %Nie0.285 s
Tprime_300_3001747Robopol Refined — Balanced1831.1553024851831.1553024850 %Áno1.798 s
Tprime_300_3001747Robopol Refined — Heavy1831.1553024851831.1553024850 %Áno5.210 s
Tprime_300_3001747LKH + Robopol Refined — Balanced1831.1553024851831.1553024850 %Áno2.940 s
Tprime_300_3001747LKH-3.0.10 (DELAUNAY)1831.1553024851832.4051275750.06825336 %Nie0.367 s
Tprime_300_4502173Robopol Refined — Balanced1833.4429849041833.4429849040 %Áno2.643 s
Tprime_300_4502173Robopol Refined — Heavy1833.4429849041833.4429849040 %Áno5.356 s
Tprime_300_4502173LKH + Robopol Refined — Balanced1833.4429849041833.4429849040 %Áno10.208 s
Tprime_300_4502173LKH-3.0.10 (DELAUNAY)1833.4429849041835.5963388450.11744864 %Nie4.273 s
Tprime_500_2502224Robopol Refined — Balanced3092.6680152353092.6680967580.00000264 %Nie2.643 s
Tprime_500_2502224Robopol Refined — Heavy3092.6680152353092.6680152350 %Áno5.014 s
Tprime_500_2502224LKH + Robopol Refined — Balanced3092.6680152353092.6680152350 %Áno5.387 s
Tprime_500_2502224LKH-3.0.10 (DELAUNAY)3092.6680152353092.6691911970.00003802 %Nie1.274 s
Tprime_500_3752587Robopol Refined — Balanced3095.0574317933095.0574317930 %Áno2.388 s
Tprime_500_3752587Robopol Refined — Heavy3095.0574317933095.0574317930 %Áno4.948 s
Tprime_500_3752587LKH + Robopol Refined — Balanced3095.0574317933095.0574317930 %Áno4.079 s
Tprime_500_3752587LKH-3.0.10 (DELAUNAY)3095.0574317933095.0928883460.00114559 %Nie0.387 s
Tprime_300_6002596Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %Nie6.203 s
Tprime_300_6002596Robopol Refined — Heavy1832.9429222791832.9429229580.00000004 %Nie11.963 s
Tprime_300_6002596LKH + Robopol Refined — Balanced1832.9429222791832.9429226180.00000002 %Nie17.524 s
Tprime_300_6002596LKH-3.0.10 (DELAUNAY)1832.9429222791835.1594469530.12092710 %Nie11.462 s
Tprime_500_5002947Robopol Refined — Balanced3092.9553460793092.9569434580.00005165 %Nie2.437 s
Tprime_500_5002947Robopol Refined — Heavy3092.9553460793092.9553460790 %Áno5.059 s
Tprime_500_5002947LKH + Robopol Refined — Balanced3092.9553460793092.9553460790 %Áno4.988 s
Tprime_500_5002947LKH-3.0.10 (DELAUNAY)3092.9553460793093.0001470560.00144848 %Nie0.479 s
Tprime_500_7503673Robopol Refined — Balanced3095.2492847633095.2751278480.00083493 %Nie6.109 s
Tprime_500_7503673Robopol Refined — Heavy3095.2492847633095.2492850380.00000001 %Nie13.684 s
Tprime_500_7503673LKH + Robopol Refined — Balanced3095.2492847633095.2492847630 %Áno10.741 s
Tprime_500_7503673LKH-3.0.10 (DELAUNAY)3095.2492847633097.4575034130.07134219 %Nie4.530 s
Tprime_500_10004396Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %Nie7.343 s
Tprime_500_10004396Robopol Refined — Heavy3094.7477884193094.7477890030.00000002 %Nie16.750 s
Tprime_500_10004396LKH + Robopol Refined — Balanced3094.7477884193094.7477890030.00000002 %Nie69.093 s
Tprime_500_10004396LKH-3.0.10 (DELAUNAY)3094.7477884193097.0202987490.07343120 %Nie34.420 s
Dáta na stiahnutie a metodika

Vstupné dáta a optimálne trasy (JSON) · Všetky výsledky (CSV) · Výsledky, trasy a nastavenia (JSON)

Zdroj konštrukcie a dôkazu optima: Hougardy–Zhong: Hard to Solve Instances of the Euclidean Traveling Salesman Problem. Použili sme upravenú rodinu z článku, nie zaokrúhlené súbory EUC_2D z autorského archívu.

Súradnice sú pri odovzdaní solverom rovnomerne zväčšené 1 000-krát. EXACT_2D používa konečnú presnosť; výsledné trasy a optimum sa nezávisle vyhodnocujú na pôvodnej geometrii so 70-cifernou presnosťou a boli overené so 110-cifernou presnosťou. Zásah optima používa toleranciu 10−40 pôvodnej jednotky. Nenulový gap sa neprepisuje na optimum.

Zverejnené výsledky LKH používajú opravený export súradníc so 17 platnými číslicami. Vstupný JSON obsahuje ideálne súradnice, presné odovzdané body, parametre n a m, referenčné trasy a optimá. Indexy trás v JSON začínajú nulou.

Systémové požiadavky

  • Windows 10/11 alebo Ubuntu 24.04+ (x86_64, glibc 2.39+)
  • Minimálne 2GB RAM
  • 1 GB voľného miesta na disku
  • Rozlíšenie obrazovky aspoň 1024x768

Čo prináša verzia 3.05

Dostupnosť a licencie TSP Solver

TSP Solver 3.05 prináša nové prehľadné rozhranie a aktualizované jadro Robopol Refined. Podporuje AIR 2D/3D, cestné trasy a viac vozidiel cez LKH. Profily Fast, Balanced a Heavy umožňujú zvoliť rozsah vyhľadávania.

TSP Solver - Demo verzia

Bezplatná verzia na vyskúšanie. Desktopovú verziu pre Windows a Linux poskytujeme na vyžiadanie cez RoboPol.
Aplikáciu môžete vyskúšať priamo online: Spustiť TSP Solver Online. Silu algoritmov si môžete vyskúšať na náhodne generovaných bodoch aj v tejto demo verzii.

  • Vytvárať a testovať AIR body bez všeobecného licenčného bodového limitu
  • Exportovať trasu ako obrázok
  • Meniť grafické nastavenia
  • Ručne kliknuté body na importovanom obrázku do 100 bodov
  • Desktop: TSP Art do 20 000 bodov
  • Vytvárať cestné trasy do 5 adries
  • Import/Export bodov do 100 bodov
  • Odoslanie trasy do Google Maps
  • Odoslanie trasy pre navigáciu na mobil
Vyžiadať od RoboPol Používateľská príručka (anglicky)

TSP Solver - Základná licencia

Vhodná pre cestovateľské účely a menšie projekty.

  • AIR výpočty v desktop aj online verzii bez všeobecného licenčného bodového limitu
  • Desktop: Refined profily Fast, Balanced a Heavy aj LKH nastavenia bez osobitných licenčných capov
  • Importovať/Exportovať body z/do .txt súboru do 5 000 bodov
  • Vytvárať cestné trasy do 100 adries
  • Importovať, exportovať obrázky
  • Desktop: TSP Art bez licenčného bodového limitu
  • Odoslanie trasy do Google Maps
  • Odoslanie trasy pre navigáciu na mobil
Kúpiť licenciu (120 € / rok)
Odporúčané

TSP Solver - Profesionál licencia

Vhodná pre firmy v oblasti dopravy a priemyslu.

  • AIR výpočty v desktop aj online verzii bez všeobecného licenčného bodového limitu
  • Desktop: Refined profily Fast, Balanced a Heavy aj LKH nastavenia bez osobitných licenčných capov
  • Import/Export bodov bez licenčného limitu
  • Cestné trasy bez licenčného limitu adries
  • Exportovať trasy
  • Importovať, exportovať obrázky
  • Desktop: TSP Art (generovanie umeleckých obrázkov)
  • Multi-vehicle mTSP - LKH pre viac vozidiel (2D/3D/Road)
  • Odoslanie trasy do Google Maps
  • Odoslanie trasy pre navigáciu na mobil
Kúpiť licenciu (390 € / rok)

Licenčné limity: desktop aplikácia a online server

Normal licencia je platená Basic licencia. Desktop aplikácia počíta lokálne a online verzia na serveri; obe verzie majú rovnaké licenčné capy.

Desktop aplikácia

Funkcia Demo Normal / Basic Professional
AIR výpočty: Robopol Refined / LKH + Robopol Refined / LKH-3.0.10 Bez všeobecného licenčného bodového limitu Bez všeobecného licenčného bodového limitu Bez všeobecného licenčného bodového limitu
Ručne kliknuté body na obrázku 100 bodov Bez licenčného limitu Bez licenčného limitu
Import / export bodov 100 bodov 5 000 bodov Bez licenčného limitu
Cestné trasy 5 adries 100 adries Bez licenčného limitu
mTSP viac vozidiel Nie Nie Áno
Refined profily a LKH nastavenia Bez licenčných capov na nastavenia Bez licenčných capov na nastavenia Bez licenčných capov na nastavenia

Online server

Funkcia Demo Normal / Basic Professional
AIR výpočty Bez všeobecného licenčného bodového limitu Bez všeobecného licenčného bodového limitu Bez všeobecného licenčného bodového limitu
Ručne kliknuté body na obrázku 100 bodov Bez licenčného limitu Bez licenčného limitu
Import / export bodov 100 bodov 5 000 bodov Bez licenčného limitu
Cestné trasy 5 adries 100 adries Bez licenčného limitu
mTSP viac vozidiel Nie Nie Áno
Nastavenia dostupných metód Bez licenčných capov na nastavenia Bez licenčných capov na nastavenia Bez licenčných capov na nastavenia

Online verzia má rovnaké licenčné capy ako desktop aplikácia. Rozdiel je iba v tom, kde výpočet beží.

Často kladené otázky

Čo je problém obchodného cestujúceho?

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.

Aký je rozdiel medzi základnou a profesionálnou verziou?

Normal / Basic licencia nie je demo. Pre AIR výpočty nemá všeobecný licenčný limit počtu bodov; 5 000 bodov sa týka importu/exportu bodov. Professional pridáva mTSP, neobmedzený import/export a cestné trasy bez licenčného limitu adries. Praktický rozsah desktop výpočtov závisí od hardvéru, pamäte a zvoleného režimu.

Ako dlho trvá výpočet optimalizovanej trasy?

Doba výpočtu závisí od počtu bodov, profilu a výkonu počítača. Verzia 3.05 používa aktualizované kompilované jadro a paralelné spracovanie. Namerané časy, parametre a výsledky všetkých inštancií nájdeš v aktuálnom benchmarku 30 inštancií s dokázaným optimom.

Môžem importovať body z externých zdrojov?

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

Aké algoritmy program používa a čím sú výnimočné?

Desktop 3.05 používa tri hlavné metódy:

  • LKH + Robopol Refined - hybrid so silnou LKH štartovacou trasou a selektívnou spoluprácou LKH počas Refined vyhľadávania; v uvedenom benchmarku dosiahol optimum v 28 z 30 prípadov.
  • Robopol Refined – aktualizované jadro s profilmi Fast, Balanced a Heavy. V uvedenom benchmarku našiel Balanced kratšie trasy než LKH (DELAUNAY) v 27 z 30 prípadov.
  • LKH-3.0.10 – samostatná optimalizácia AIR trás a výpočtová metóda pre cestné trasy a mTSP.

Čo robiť, keď Windows zobrazí bezpečnostné upozornenie pri inštalácii?

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:

  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

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.

Je program vhodný pre reálne úlohy?

Á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.