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

Robopol algoritmus - nová metóda na riešenie TSP

Robopol Algorithm - A New Method for TSP Solving

Okrem optimalizácie existujúcich algoritmov som vyvinul aj úplne nový algoritmus na riešenie TSP, nazvaný "Robopol algoritmus". Tento algoritmus je založený na princípe postupného pridávania bodov do trasy a jej priebežnej optimalizácie.

In addition to optimizing existing algorithms, I have also developed a completely new algorithm for solving TSP, called the "Robopol algorithm". This algorithm is based on the principle of gradually adding points to the route and continuously optimizing it.

Kľúčové vlastnosti Robopol algoritmu:

Key features of the Robopol algorithm:

• Vysoká presnosť - Algoritmus dosahuje výsledky porovnateľné s najlepšími známymi algoritmami
• Efektívnosť - Spracovanie inštancií s tisíckami bodov v sekundách
• Škálovateľnosť - Algoritmus je efektívny aj pre veľmi veľké inštancie problému
• Adaptabilita - Možnosť prispôsobenia rôznym typom TSP problémov (symetrické, asymetrické, s časovými oknami, atď.)

• High accuracy - The algorithm achieves results comparable to the best known algorithms
• Efficiency - Processing of instances with thousands of points in seconds
• Scalability - The algorithm is efficient even for very large problem instances
• Adaptability - Ability to adapt to different types of TSP problems (symmetric, asymmetric, with time windows, etc.)

Robopol algoritmus využíva NUMBA funkcie, ktoré konvertujú kód do strojového kódu pri prvom spustení, čo výrazne zrýchľuje následné výpočty. Tento prístup umožňuje efektívne spracovanie veľkých inštancií problému.

The Robopol algorithm uses NUMBA functions that convert the code to machine code during the first run, which significantly speeds up subsequent calculations. This approach allows for efficient processing of large problem instances.

Podrobný popis algoritmu a jeho implementácia sú dostupné v článku TSP - metóda postupného pridávania bodov Robopol.

A detailed description of the algorithm and its implementation are available in the article TSP - gradual point addition method Robopol.

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
• Robopol Precise algoritmus (vylepšená verzia s vyššou presnosťou)
• 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
• Robopol Precise algorithm (improved version with higher accuracy)
• 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 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 potrebuje len minúty 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 minutes 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

Podrobné výsledky porovnania sú dostupné v článku Obchodný cestujúci - porovnanie algoritmov TSP.

Detailed comparison results are available in the article Traveling Salesman - comparison of TSP algorithms.

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.