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

Aktuálny TSP Solver Desktop 3.0.0

Current TSP Solver Desktop 3.0.0

Aktuálna desktop verzia 3.0.0 používa nové kompilované jadro Robopol Refined v jazyku Rust a automatické paralelné spracovanie podľa dostupného procesora. Samostatné staršie voľby boli zlúčené do troch profilov Fast, Balanced a Heavy. Úplný produktový popis je na stránke TSP Solver; samostatne je dostupná aj online verzia.

The current desktop version 3.0.0 uses a new compiled Robopol Refined core written in Rust and automatic parallel execution based on the available CPU. Legacy standalone choices were consolidated into the Fast, Balanced, and Heavy profiles. The complete product description is available on the TSP Solver page, with a separate online version.

Praktické odporúčanie: pre maximálnu presnosť použi LKH + Robopol Refined. Druhou voľbou je Robopol Refined / Heavy, Balanced ponúka rýchlejší kompromis a Fast uprednostňuje čas. Samostatný LKH zostáva potrebný pre cestné trasy a mTSP.

Practical recommendation: use LKH + Robopol Refined for maximum accuracy. The second choice is Robopol Refined / Heavy; Balanced offers a faster compromise and Fast prioritizes runtime. Standalone LKH remains required for road routes and mTSP.

Robopol Refined ako univerzálny optimalizačný engine

Robopol Refined as a Universal Optimization Engine

Robopol Refined už nie je iba algoritmus pre TSP. Je to univerzálne guided search jadro pre kombinatorickú optimalizáciu, kde jadro rieši beam/frontier search, viacnásobné behy, perturbácie, lokálne zlepšovanie, paralelizáciu a diagnostiku, zatiaľ čo konkrétny problém dodáva vlastný stav, skóre, ťahy a guidance edges.

Robopol Refined is no longer only a TSP algorithm. It is a universal guided search core for combinatorial optimization, where the core handles beam/frontier search, multiple runs, perturbation, local improvement, parallel execution and diagnostics, while each concrete problem provides its own state, score, moves and guidance edges.

Rovnaké jadro môže byť napojené na rôzne triedy úloh: TSP a routing, JSSP a scheduling, set cover, knapsack, bin packing, graph coloring, max-cut alebo assignment problémy. Dôležitá je adapter vrstva: čím lepšie problem-specific edges a lokálne ťahy adapter poskytne, tým viac sa univerzálne jadro správa ako špecializovaný solver pre danú doménu.

The same core can be connected to different problem classes: TSP and routing, JSSP and scheduling, set cover, knapsack, bin packing, graph coloring, max-cut or assignment problems. The adapter layer is essential: the better the problem-specific edges and local moves supplied by the adapter, the more the universal core behaves like a specialized solver for that domain.

V samostatnom Rust jadre refined_engine už boli skúšané rozdielne typy úloh: Max-Cut, set cover, graph coloring, knapsack, bin packing, partition, QAP, Golomb ruler, Costas array a aj matematické black-box funkcie typu Rastrigin, Ackley, Rosenbrock alebo členité rugged landscape testy. To je dôležité, lebo nejde iba o ďalší TSP trik, ale o opakovateľný spôsob, ako preniesť silné prehľadávanie medzi doménami.

The standalone Rust refined_engine core has already been tested on different task types: Max-Cut, set cover, graph coloring, knapsack, bin packing, partition, QAP, Golomb ruler, Costas array and mathematical black-box functions such as Rastrigin, Ackley, Rosenbrock and rugged landscape tests. That matters because this is not only another TSP trick, but a repeatable way to move strong search across domains.

Pri TSP ukázal benchmark verzie 3.0.0, že hybrid LKH + Robopol Refined našiel kratšiu EXACT_2D trasu vo všetkých 10 z 10 prípadoch, v ktorých samostatný LKH netrafil publikované optimum. Pri JSSP sa v aktuálnych experimentoch vie držať blízko CP-SAT aj na ťažších inštanciách. Cieľom nie je tvrdiť, že jeden engine automaticky porazí každý špecializovaný solver, ale ukázať, že univerzálne jadro s kvalitným adapterom môže byť reálne konkurencieschopné.

For TSP, the version 3.0.0 benchmark showed that LKH + Robopol Refined found a shorter EXACT_2D route in all 10 out of 10 cases where standalone LKH missed the published optimum. For JSSP, current experiments can stay close to CP-SAT even on harder instances. The point is not to claim that one engine automatically beats every specialized solver, but to show that a universal core with a strong adapter can be genuinely competitive.

Od optimalizácie k vedeckému nástroju

From Optimization to a Scientific Tool

Najdôležitejší posun je, že rovnaký model nemusí zostať iba pri TSP alebo klasickej kombinatorike. Ak problém vieme zapísať ako priestor kandidátnych hypotéz a máme externý verifier, ktorý vie kandidáta rigorózne prijať alebo zamietnuť, Refined sa dá použiť ako generátor hypotéz. Jadro nehľadá dôkaz namiesto matematiky; hľadá sľubné objekty, konfigurácie alebo proti-príklady a verifier potom rozhodne, čo je skutočne platné.

The most important shift is that the same model does not have to remain only inside TSP or classical combinatorics. If a problem can be expressed as a space of candidate hypotheses and we have an external verifier that can rigorously accept or reject a candidate, Refined can act as a hypothesis generator. The core does not replace mathematical proof; it searches for promising objects, configurations or counterexample candidates, and the verifier decides what is actually valid.

V aktuálnych validačných experimentoch boli takto pridané úlohy typu Ramsey edge coloring a Hadamard matrix repair. Pri Ramsey hľadá engine zafarbenie hrán grafu bez zakázanej monochromatickej kliky; pri Hadamard probléme hľadá ±1 maticu s nulovou ortogonálnou chybou. V oboch prípadoch je skóre len vodiaci signál a konečný verdikt dáva presný verifier. Quick testy pre menšie prípady skončili v 60/60 behoch overeným výsledkom a ťažšie sanity behy našli aj Ramsey K17/K4 a Hadamard 16.

Current validation experiments add tasks such as Ramsey edge coloring and Hadamard matrix repair. In Ramsey coloring, the engine searches for an edge coloring without a forbidden monochromatic clique; in the Hadamard task, it searches for a ±1 matrix with zero orthogonality error. In both cases, the score is only a guiding signal and the final verdict comes from an exact verifier. Quick tests on smaller cases ended with verified results in 60/60 runs, and harder sanity runs also found Ramsey K17/K4 and Hadamard 16 solutions.

Nová dimenzia: 3D TSP a Reálne Cesty

New Dimension: 3D TSP and Real Roads

TSPLIB benchmark TSP Solver 3.0.0

TSP Solver 3.0.0 TSPLIB Benchmark

Benchmark z 15. júla 2026 obsahuje 21 podporovaných TSPLIB EUC_2D inštancií a 63/63 platných behov bez timeoutov alebo zlyhaní. Všetky metódy optimalizovali rovnaké súradnice pomocou EXACT_2D a výsledné trasy boli nezávisle vyhodnotené oficiálnym TSPLIB EUC_2D pravidlom proti publikovaným optimám.

The July 15, 2026 benchmark covers 21 supported TSPLIB EUC_2D instances and 63/63 valid runs with no timeouts or failures. Every method optimized the same coordinates using EXACT_2D, and resulting tours were independently scored with the official TSPLIB EUC_2D rule against published optima.

• LKH + Robopol Refined / Balanced: optimum 14/21, priemerný gap 0,015325 %, priemerný čas 3,572 s.
• Robopol Refined / Balanced: optimum 11/21, priemerný gap 0,045982 %, priemerný čas 2,689 s.
• LKH-3.0.10 / 10 behov: optimum 11/21, priemerný gap 0,032443 %, priemerný čas 0,800 s.
• Hybrid proti LKH: v 10/10 prípadoch, kde LKH netrafil optimum, našiel hybrid kratšiu trasu v skutočnej optimalizačnej metrike EXACT_2D.

• LKH + Robopol Refined / Balanced: optimum 14/21, mean gap 0.015325%, mean runtime 3.572 s.
• Robopol Refined / Balanced: optimum 11/21, mean gap 0.045982%, mean runtime 2.689 s.
• LKH-3.0.10 / 10 runs: optimum 11/21, mean gap 0.032443%, mean runtime 0.800 s.
• Hybrid versus LKH: in 10/10 cases where LKH missed the optimum, the hybrid found a shorter route in the actual EXACT_2D optimization metric.

Úplný súhrn, všetkých 63 výsledkov, metodika a vysvetlenie rozdielu medzi EXACT_2D a celočíselným TSPLIB EUC_2D skóre sú na produktovej stránke TSP Solver. Profil Heavy nebol súčasťou tohto benchmarku.

The full summary, all 63 results, methodology, and the distinction between EXACT_2D and integer TSPLIB EUC_2D scoring are available on the TSP Solver product page. The Heavy profile was not part of this benchmark.

Publikácie a zdroje

Publications and Resources

Nový paper opisuje Robopol Refined ako univerzálny guided search engine pre kombinatorickú optimalizáciu. Verejne vysvetľuje architektúru, adapter model a guidance edge koncept, ale zámerne nezverejňuje kompletné interné know-how ako presné ranking vzorce, tuning pravidlá alebo benchmark-specific konfigurácie.

The new paper presents Robopol Refined as a universal guided search engine for combinatorial optimization. It publicly explains the architecture, adapter model and guidance-edge concept, while intentionally not disclosing the full internal know-how such as exact ranking formulas, tuning rules or benchmark-specific configurations.

Robopol Refined: A Universal Guided Search Engine for Combinatorial Optimization (Zenodo)

Starší TSP paper ponechávam ako doplnkový zdroj, pretože podrobnejšie ukazuje, ako sa Robopol Refined správa priamo na probléme obchodného cestujúceho:

The older TSP paper is kept as a supplementary source, because it shows in more detail how Robopol Refined behaves directly on the traveling salesperson problem:

The Robopol Refined Algorithm for the Traveling Salesperson Problem (PDF)

Praktické využitie univerzálneho Robopol Refined

Practical Uses of Universal Robopol Refined

Robopol Refined už nie je iba výskum pre TSP. Je to univerzálne guided search jadro, ktoré sa dá napojiť na rôzne kombinatorické problémy cez problem-specific adapter. Adapter dodá stav úlohy, skóre, povolené ťahy a guidance edges, zatiaľ čo jadro rieši samotné prehľadávanie, viacnásobné behy, lokálne zlepšovanie a paralelizáciu.

Robopol Refined is no longer only TSP research. It is a universal guided search core that can be connected to different combinatorial problems through a problem-specific adapter. The adapter provides the task state, score, allowed moves and guidance edges, while the core handles the search itself, multiple runs, local improvement and parallel execution.

• Routing a plánovanie trás - TSP, varianty vehicle routing, drony, robotické ramená, pohyb strojov a optimalizácia reálnych ciest.
• Scheduling a výroba - JSSP, plánovanie operácií na strojoch, poradie výrobných krokov, CNC, 3D tlač alebo automatizované pracoviská.
• Packing a alokácia zdrojov - Knapsack, bin packing, cutting stock, rozdelenie kapacít a výber kombinácií pod obmedzeniami.
• Covering a výber podmnožín - Set cover, výber funkcií, pokrytie požiadaviek alebo hľadanie malej množiny rozhodnutí s veľkým efektom.
• Grafové a sieťové úlohy - Graph coloring, max-cut, assignment, návrh sietí a hľadanie kvalitných konfigurácií v diskrétnych štruktúrach.
• Vedecké hypotézy a verifikácia - hľadanie konštrukcií, proti-príkladov, štruktúr a kandidátnych objektov, ktoré následne overí presný matematický alebo fyzikálny oracle.
• AI nástroje a rozhodovacia podpora - Univerzálne jadro môže slúžiť ako výpočtový pomocník pre LLM/MCP nástroje, keď používateľ zadá kombinatorický problém v bežnom jazyku.

• Routing and path planning - TSP, vehicle routing variants, drones, robotic arms, machine movement and real-road optimization.
• Scheduling and manufacturing - JSSP, machine operation planning, ordering of production steps, CNC, 3D printing or automated workplaces.
• Packing and resource allocation - Knapsack, bin packing, cutting stock, capacity allocation and selecting combinations under constraints.
• Covering and subset selection - Set cover, feature selection, requirement coverage or finding a small set of decisions with a large effect.
• Graph and network tasks - Graph coloring, max-cut, assignment, network design and searching for strong configurations in discrete structures.
• Scientific hypotheses and verification - searching for constructions, counterexamples, structures and candidate objects that are then checked by an exact mathematical or physical oracle.
• AI tools and decision support - The universal core can act as a computational helper for LLM/MCP tools when a user describes a combinatorial problem in natural language.

TSP algoritmy, desktop balíky a benchmark verzie 3.0.0 sú dostupné na stránke TSP Solver. Univerzálny Robopol Refined ide ďalej: cieľom je použiť rovnaké prehľadávacie jadro aj mimo TSP všade tam, kde problém vie poskytnúť dobrý adapter a doménové guidance edges.

The TSP algorithms, desktop packages, and version 3.0.0 benchmark are available on the TSP Solver page. Universal Robopol Refined goes further: the goal is to use the same search core beyond TSP wherever a problem can provide a good adapter and domain-specific guidance edges.