Úvod do problému obchodného cestujúceho
Introduction to the Traveling Salesman Problem
Problém obchodného cestujúceho (Traveling Salesman Problem - TSP) je jedným z najznámejších problémov v oblasti kombinatorickej optimalizácie. Problém spočíva v nájdení najkratšej možnej trasy, ktorá prechádza všetkými zadanými bodmi (mestami) práve raz a vracia sa do východiskového bodu.
The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization. The problem consists of finding the shortest possible route that passes through all given points (cities) exactly once and returns to the starting point.
TSP je NP-ťažký problém, čo znamená, že neexistuje známy algoritmus, ktorý by ho riešil v polynomiálnom čase. Pre praktické aplikácie sa preto používajú rôzne heuristické a aproximačné algoritmy, ktoré poskytujú dostatočne dobré riešenia v rozumnom čase.
TSP is an NP-hard problem, which means that there is no known algorithm that would solve it in polynomial time. For practical applications, various heuristic and approximation algorithms are therefore used, which provide sufficiently good solutions in a reasonable time.
Prelomový rok 2026: Turbo režim a Numba optimalizácia
Breakthrough Year 2026: Turbo Mode and Numba Optimization
V roku 2026 sme dosiahli významný míľnik vo vývoji algoritmov pre TSP. Prechodom na plne kompilovaný Python kód pomocou technológie NUMBA (viac ako 7000 riadkov optimalizovaného kódu) sme dosiahli extrémne zrýchlenie výpočtov.
In 2026, we reached a significant milestone in TSP algorithm development. By switching to fully compiled Python code using NUMBA technology (over 7000 lines of optimized code), we achieved extreme acceleration of calculations.
Robopol Algorithm - Fast (Turbo Mode)
Robopol Algorithm - Fast (Turbo Mode)
Nový "Turbo režim" mení pravidlá hry pre veľké inštancie. Zatiaľ čo tradičné heuristiky zlyhávajú pri desiatkach tisíc bodov, Robopol Fast škáluje lineárne:
The new "Turbo Mode" changes the game for large instances. While traditional heuristics fail at tens of thousands of points, Robopol Fast scales linearly:
- 100 000 bodov: Spracovanie za cca 1 minútu.
- Milióny bodov: Algoritmus dokáže nájsť (sub)optimálnu trasu aj pre miliónové inštancie, čo bolo donedávna doménou superpočítačov.
- Porovnanie s LKH: Pri veľkých inštanciách je Robopol Fast až 700x rýchlejší ako algoritmus LKH, pri zachovaní vysokej kvality trasy.
- 100,000 points: Processing in approx. 1 minute.
- Millions of points: The algorithm can find a (sub)optimal route even for million-point instances, which was until recently the domain of supercomputers.
- Comparison with LKH: For large instances, Robopol Fast is up to 700x faster than the LKH algorithm, while maintaining high route quality.
Robopol Refined: Keď musí byť trasa dokonalá
Robopol Refined: When the Route Must Be Perfect
Pre menšie a stredné inštancie, kde je prioritou absolútna presnosť (napr. vŕtanie DPS), sme vyvinuli metódu Robopol Refined. Tento algoritmus v roku 2026 preukázateľne nachádza v niektorých prípadoch lepšie riešenia ako LKH (Lin-Kernighan-Helsgaun), ktorý bol dlhé roky považovaný za neprekonateľný štandard.
For small and medium instances, where absolute precision is a priority (e.g., PCB drilling), we developed the Robopol Refined method. In 2026, this algorithm demonstrably finds better solutions than LKH (Lin-Kernighan-Helsgaun) in some cases, which was considered the unsurpassable standard for many years.
Nová dimenzia: 3D TSP a Reálne Cesty
New Dimension: 3D TSP and Real Roads
Priestorová optimalizácia (3D)
Spatial Optimization (3D)
V roku 2026 sme rozšírili solver o plnú podporu Z-osi (výšky). Algoritmus teraz optimalizuje pohyb v 3D priestore, čo je kritické pre:
In 2026, we expanded the solver with full support for the Z-axis (height). The algorithm now optimizes movement in 3D space, which is critical for:
- Drony: Plánovanie letových hladín a obchádzanie prekážok.
- Robotické ramená: Efektívny pohyb v automobilovom priemysle.
- 3D Tlač: Minimalizácia "travel moves" tlačovej hlavy.
Cestné siete (Google Maps)
Road Networks (Google Maps)
Teoretická vzdialenosť (vzdušnou čiarou) je v logistike nepresná. Náš solver teraz integruje reálne cestné dáta:
Theoretical distance (as the crow flies) is inaccurate in logistics. Our solver now integrates real road data:
- Výpočet matice vzdialeností cez reálnu cestnú sieť.
- Zohľadnenie jednosmeriek a dopravných obmedzení.
- Export priamo do navigácie.
Benchmark 2026: Robopol vs Svet
Benchmark 2026: Robopol vs The World
Vykonal som rozsiahle porovnanie na štandardných datasetoch TSPLIB. Výsledky jasne ukazujú dominanciu Robopol algoritmov v rôznych kategóriách:
I conducted an extensive comparison on standard TSPLIB datasets. The results clearly show the dominance of Robopol algorithms in various categories:
| Kategória | Category | Najlepší Algoritmus | Best Algorithm | Výhoda | Advantage |
|---|---|---|---|---|---|
| Small (< 1000) | Small (< 1000) | Robopol Refined | Robopol Refined | Vyššia presnosť ako LKH | Higher precision than LKH |
| Large (10k - 100k) | Large (10k - 100k) | Robopol Fast (Turbo) | Robopol Fast (Turbo) | 700x rýchlejší výpočet | 700x faster calculation |
| Extreme (> 1M) | Extreme (> 1M) | Robopol Fast (Turbo) | Robopol Fast (Turbo) | Jediný použiteľný na bežnom PC | Only one usable on a standard PC |
Publikácie a zdroje
Publications and Resources
Detailný popis algoritmu Robopol Refined a jeho porovnanie s LKH nájdete v našej najnovšej publikácii:
A detailed description of the Robopol Refined algorithm and its comparison with LKH can be found in our latest publication:
The Robopol Refined Algorithm for the Traveling Salesperson Problem (PDF)Aplikácie výskumu - TSP Art
Research Applications - TSP Art
Jednou z zaujímavých aplikácií výskumu TSP algoritmov je tzv. TSP Art - technika vytvárania umeleckých diel pomocou riešenia problému obchodného cestujúceho. Princíp spočíva v konverzii obrázka na množinu bodov a následnom nájdení optimálnej trasy, ktorá prechádza všetkými bodmi.
One of the interesting applications of TSP algorithm research is the so-called TSP Art - a technique of creating artworks by solving the traveling salesman problem. The principle consists of converting an image into a set of points and then finding the optimal route that passes through all points.
Výsledkom je jediná spojitá čiara, ktorá vytvára vizuálne zaujímavý obraz. Táto technika je obzvlášť pôsobivá pri použití veľkého počtu bodov (desaťtisíce až státisíce).
The result is a single continuous line that creates a visually interesting image. This technique is particularly impressive when using a large number of points (tens to hundreds of thousands).
Vďaka vysokej efektívnosti vyvinutých algoritmov je možné vytvárať TSP Art s veľkým počtom bodov v rozumnom čase.
Thanks to the high efficiency of the developed algorithms, it is possible to create TSP Art with a large number of points in a reasonable time.
Praktické využitie výskumu
Practical Use of Research
Výsledky výskumu TSP algoritmov majú široké praktické využitie v rôznych oblastiach:
The results of TSP algorithm research have a wide practical use in various areas:
- Logistika a doprava - Optimalizácia trás pre doručovanie tovaru, plánovanie trás vozidiel, optimalizácia leteckých trás
- Výroba - Optimalizácia pohybu robotov a strojov, plánovanie výrobných procesov
- Telekomunikácie - Návrh a optimalizácia sieťovej infraštruktúry
- Počítačové videnie - Spracovanie a analýza obrazu, rozpoznávanie vzorov
- Bioinformatika - Sekvenovanie DNA, analýza proteínových štruktúr
- Logistics and transport - Optimization of routes for goods delivery, planning of vehicle routes, optimization of air routes
- Manufacturing - Optimization of robot and machine movement, planning of production processes
- Telecommunications - Design and optimization of network infrastructure
- Computer vision - Image processing and analysis, pattern recognition
- Bioinformatics - DNA sequencing, protein structure analysis
Vyvinuté algoritmy sú implementované v programe TSP Solver, ktorý poskytuje užívateľsky prívetivé rozhranie pre riešenie TSP problémov v praxi.
The developed algorithms are implemented in the TSP Solver program, which provides a user-friendly interface for solving TSP problems in practice.