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

Vylepšenie metódy najbližšieho suseda

Improvement of the Nearest Neighbor Method

Metóda najbližšieho suseda (Nearest Neighbor) je jedným z najjednoduchších a najrýchlejších algoritmov na riešenie TSP. Algoritmus začína v ľubovoľnom bode a postupne navštevuje najbližší ešte nenavštívený bod, až kým neprejde všetky body.

The Nearest Neighbor method is one of the simplest and fastest algorithms for solving TSP. The algorithm starts at any point and gradually visits the closest not yet visited point until it passes through all points.

Hoci je tento algoritmus veľmi rýchly, jeho výsledky často nie sú optimálne. V rámci môjho výskumu som vyvinul optimalizáciu tejto metódy, ktorá výrazne zlepšuje kvalitu výsledkov bez významného zvýšenia výpočtovej náročnosti.

Although this algorithm is very fast, its results are often not optimal. As part of my research, I developed an optimization of this method that significantly improves the quality of results without significantly increasing computational complexity.

Kľúčové vylepšenia zahŕňajú:

Key improvements include:

• Optimalizáciu výberu počiatočného bodu
• Implementáciu lokálneho vyhľadávania na zlepšenie nájdenej trasy
• Použitie špeciálne heuristiky na identifikáciu a opravu neefektívnych úsekov trasy
• Paralelné spracovanie pre rýchlejšie výpočty

• Optimization of initial point selection
• Implementation of local search to improve the found route
• Use of special heuristics to identify and fix inefficient route sections
• Parallel processing for faster calculations

Tieto vylepšenia vedú k výraznému zlepšeniu kvality výsledkov, pričom zachovávajú rýchlosť a jednoduchosť pôvodného algoritmu.

These improvements lead to a significant improvement in the quality of results while maintaining the speed and simplicity of the original algorithm.

Rodina algoritmov Robopol - Inovatívne riešenia pre TSP

The Robopol Algorithm Family - Innovative Solutions for TSP

V rámci môjho výskumu som sa zameral na vývoj nových a optimalizáciu existujúcich prístupov k riešeniu Problému obchodného cestujúceho (TSP). Výsledkom sú dva kľúčové algoritmy: "Robopol Algorithm - Fast" a "Robopol Refined", každý navrhnutý s iným zameraním na rýchlosť a kvalitu riešenia.

In my research, I have focused on developing new and optimizing existing approaches to solving the Traveling Salesperson Problem (TSP). This has resulted in two key algorithms: "Robopol Algorithm - Fast" and "Robopol Refined", each designed with a different focus on speed and solution quality.

Robopol Algorithm - Fast

Robopol Algorithm - Fast

Tento algoritmus je založený na princípe efektívneho, postupného pridávania bodov do trasy a jej priebežnej optimalizácie. Je navrhnutý pre rýchle získanie kvalitných riešení, najmä pre rozsiahle inštancie problému.

This algorithm is based on the principle of efficiently and gradually adding points to the route while continuously optimizing it. It is designed for rapidly obtaining good-quality solutions, especially for large problem instances.

Kľúčové vlastnosti Robopol Algorithm - Fast:

Key features of Robopol Algorithm - Fast:

• Vynikajúca rýchlosť: Schopnosť spracovať inštancie s desaťtisícami bodov v priebehu sekúnd.
• Efektívnosť: Dosahuje dobrú kvalitu riešenia v krátkom čase.
• Optimalizácia pomocou NUMBA: Využíva funkcie kompilované knižnicou NUMBA, ktoré konvertujú Python kód do strojového kódu pri prvom spustení, čo výrazne zrýchľuje následné výpočty.

• Excellent speed: Capable of processing instances with tens of thousands of points within seconds.
• Efficiency: Achieves good solution quality in a short amount of time.
• NUMBA Optimization: Utilizes functions compiled by the NUMBA library, which convert Python code to machine code during the first run, significantly speeding up subsequent calculations.

Robopol Refined

Robopol Refined

"Robopol Refined" je pokročilý metaheuristický algoritmus navrhnutý na dosiahnutie riešení najvyššej kvality. Integruje rámec Iteratívneho lokálneho prehľadávania (ILS) s Lúčovým prehľadávaním (Beam Search) a sofistikovanými perturbačnými stratégiami.

"Robopol Refined" is an advanced metaheuristic algorithm designed to achieve top-quality solutions. It integrates an Iterated Local Search (ILS) framework with Beam Search and sophisticated perturbation strategies.

Kľúčové vlastnosti Robopol Refined:

Key features of Robopol Refined:

• Vysoká presnosť: Cieli na nájdenie riešení blízkych globálnemu optimu, porovnateľných s najlepšími známymi heuristikami.
• Pokročilé techniky: Využíva adaptívne perturbácie, kandidátske zoznamy inšpirované LKH a mechanizmus "Checkout Kick" na prekonávanie lokálnych optim.
• Paralelizácia: Podporuje paralelné vykonávanie viacerých nezávislých behov na dôkladnejšie preskúmanie priestoru riešení.
• Optimalizácia pomocou NUMBA: Jadro algoritmu je tiež optimalizované pomocou NUMBA pre vysoký výkon.

• High accuracy: Aims to find solutions close to the global optimum, comparable to the best-known heuristics.
• Advanced techniques: Employs adaptive perturbations, LKH-inspired candidate lists, and a "Checkout Kick" mechanism to overcome local optima.
• Parallelization: Supports parallel execution of multiple independent runs for a more thorough exploration of the solution space.
• NUMBA Optimization: The core of the algorithm is also optimized using NUMBA for high performance.

Tieto algoritmy predstavujú snahu o poskytnutie flexibilných nástrojov pre rôzne požiadavky pri riešení TSP, od rýchlych odhadov až po vysoko presné riešenia. Podrobný popis algoritmu Robopol Refined a jeho implementácia sú dostupné vo vedeckej práci: The Robopol Refined Algorithm for the Traveling Salesperson Problem.

These algorithms represent an effort to provide flexible tools for various requirements in TSP solving, from quick estimates to highly accurate solutions. A detailed description of the Robopol Refined algorithm and its implementation are available in the research paper: The Robopol Refined Algorithm for the Traveling Salesperson Problem.

Porovnanie algoritmov a výkonnostné testy

Algorithm Comparison and Performance Tests

V rámci výskumu som vykonal rozsiahle porovnanie rôznych algoritmov na riešenie TSP, vrátane:

As part of the research, I conducted an extensive comparison of various algorithms for solving TSP, including:

• Metóda najbližšieho suseda (pôvodná a optimalizovaná verzia)
• Robopol algoritmus (fast)
• Robopol Precise algoritmus (vylepšená verzia s vyššou presnosťou)
• Robopol Refined algoritmus (pokročilý metaheuristický algoritmus)
• LKH algoritmus (Lin-Kernighan-Helsgaun, považovaný za jeden z najlepších heuristických algoritmov)
• Genetické algoritmy
• Simulované žíhanie

• Nearest Neighbor method (original and optimized version)
• Robopol algorithm (fast)
• Robopol Precise algorithm (improved version with higher accuracy)
• Robopol Refined algorithm (advanced metaheuristic algorithm)
• LKH algorithm (Lin-Kernighan-Helsgaun, considered one of the best heuristic algorithms)
• Genetic algorithms
• Simulated annealing

Výkonnostné testy ukázali, že:

Performance tests showed that:

• Pre malé inštancie (do 100 bodov) je výpočet takmer okamžitý pre všetky algoritmy
• Pre stredné inštancie (100-1000 bodov) Robopol algoritmus(fast) 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(fast) potrebuje len niekolko sekúnd 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, ale stále je výrazne rýchlejší ako konkurencia

• For small instances (up to 100 points), the calculation is almost instantaneous for all algorithms
• For medium instances (100-1000 points), the Robopol algorithm handles the calculation in seconds, the LKH algorithm also handles the calculation of up to 1000 points in seconds
• For large instances (1000-10000 points), the Robopol algorithm only takes a few seconds to calculate
• For very large instances (10000-50000 points) such as TSP Art, the calculation may take longer, but it is still significantly faster than the competition

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.