Ú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álne TSP Solver algoritmy a režimy Refined

Current TSP Solver Algorithms and Refined Modes

TSP výskum nie je len teória. Aktuálne algoritmy sú dostupné aj v online TSP Solveri a v hlavnej desktop verzii. Implementácia Robopol metód používa NUMBA JIT, takže prvý beh môže byť pomalší pre kompiláciu, ale ďalšie výpočty sú výrazne rýchlejšie.

The TSP research is not only theoretical. The current algorithms are available in the online TSP Solver and in the main desktop version. The Robopol methods use NUMBA JIT, so the first run may be slower because of compilation, while subsequent runs are much faster.

Pri porovnaní s LKH závisí rýchlosť aj kvalita od nastavenia LKH. Oproti LKH s kandidátmi typu ALPHA môže byť Robopol Fast výrazne rýchlejší; pri nastaveniach založených na Delaunay kandidátoch býva čas približne porovnateľný. Pre maximálnu kvalitu je najzaujímavejší režim LKH + Robopol Refined, pretože LKH dodá silnú trasu a Refined potom prehľadáva jej okolie aj úniky z lokálnych miním.

When comparing with LKH, both speed and quality depend on the LKH settings. Compared with LKH using ALPHA candidates, Robopol Fast can be significantly faster; with Delaunay-based candidate settings, runtime is often roughly comparable. For maximum quality, LKH + Robopol Refined is the most interesting mode, because LKH provides a strong route and Refined then explores its neighborhood and escape paths from local minima.

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 môže Robopol Refined so silným edge-guided adapterom dorovnať alebo prekonať LKH na vybraných behoch. 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, Robopol Refined with a strong edge-guided adapter can match or beat LKH on selected runs. 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

Benchmark 2026: orientačné porovnanie

Benchmark 2026: Indicative Comparison

Benchmark tu beriem ako praktické odporúčanie podľa typu úlohy, nie ako jednu univerzálnu tabuľku víťazov. Pri TSP je dôležité rozlišovať rýchly praktický výpočet od režimu, kde sa ide po maximálnej kvalite trasy.

This benchmark is presented as a practical recommendation by problem type, not as a single universal winner table. For TSP, it is important to separate fast practical computation from the mode focused on maximum route quality.

• Do 100 bodov: najzaujímavejšie sú hybridy LKH + Robopol Refined, ktoré v testovaných prípadoch vedia zlepšiť samotný LKH. So zapnutým Enable Edge-Guided Search pritom vedia zostať rýchle.
• 10k - 100k bodov: pre kvalitu odporúčam opäť hybridný prístup LKH + Robopol Refined alebo LKH + Robopol Escape Polish, nie Robopol Fast ako hlavné benchmarkové porovnanie. Pri zapnutom edge-guided režime sa Refined v hybride sústredí na sľubné časti LKH trasy, takže čas výpočtu ostáva praktický.
• Extrémne veľké datasety: Robopol Fast/Turbo ostáva praktický režim, keď je najdôležitejšie dostať veľmi veľkú úlohu do rozumného času a pamäte.
• Black-box a funkčné minimá: Refined adapter bol skúšaný na funkciách ako Rastrigin, Ackley, Rosenbrock a členité rugged landscape testy.
• Hypotézy a verifier úlohy: nové adaptery ukazujú použitie na Ramsey coloring a Hadamard matrix search, kde presný oracle kontroluje, či kandidát naozaj spĺňa matematickú podmienku.
• Grafové, packing a scheduling úlohy: univerzálne jadro dáva dobré výsledky na Max-Cut, set cover, coloring, knapsack, bin packing, JSSP a QAP adapteroch.

• Up to 100 points: the most interesting choice is the LKH + Robopol Refined hybrid, which can improve standalone LKH in tested cases. With Enable Edge-Guided Search enabled, the hybrid can still remain fast.
• 10k - 100k points: for quality, the recommended approach is again LKH + Robopol Refined or LKH + Robopol Escape Polish, not Robopol Fast as the main benchmark comparison. With edge-guided mode enabled, Refined focuses on promising parts of the LKH route, keeping runtime practical.
• Extreme datasets: Robopol Fast/Turbo remains a practical mode when the priority is solving a very large instance within reasonable time and memory.
• Black-box and function minima: the Refined adapter has been tested on functions such as Rastrigin, Ackley, Rosenbrock and rugged landscape tests.
• Hypotheses and verifier tasks: new adapters show its use on Ramsey coloring and Hadamard matrix search, where an exact oracle checks whether a candidate really satisfies the mathematical condition.
• Graph, packing and scheduling tasks: the universal core gives strong results on Max-Cut, set cover, coloring, knapsack, bin packing, JSSP and QAP adapters.

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 sú prakticky dostupné v programe 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 are available in the TSP Solver application. 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.