Problém obchodného cestujúceho – jeden z najťažších počítačových problémov na svete. Každý deň ho riešia tisíce kuriérskych algoritmov po celom Slovensku.
Prečo nestačí „vyskúšať všetky možnosti"? Pretože ich počet rastie faktoriálovo – rýchlejšie ako akákoľvek výpočtová sila na svete.
Predstav si, že máš navštíviť N miest a vrátiť sa späť. Koľko rôznych poradia existuje? Odpoveď je (N-1)! – faktoriál.
Pre 4 mestá: 3! = 6 možností. Pre 10 miest: 362 880 možností. Pre 20 miest: číslo s 18 ciframi.
Logistické firmy nemôžu prepočítať všetky trasy, pretože aj najrýchlejší superpočítač by pri 25 zastávkach pracoval dlhšie, než je vek vesmíru. Preto potrebujeme chytré heuristiky.
Vedci vymysleli štyri hlavné prístupy. Každý má iné silné stránky – od exaktného optima po biologickú inšpiráciu.
Systematicky prechádza každú možnú permutáciu trasy a vyberie tú najkratšiu. Garantuje 100% optimálny výsledok, ale je použiteľná len pre malý počet miest (do ~12).
Začni kdekoľvek a vždy choď na najbližšiu nenavštívenú zastávku. Jednoduchá a bleskurýchla stratégia. Nevýhoda: myslí len „krok dopredu" a môže skončiť s nevhodným poradím na konci trasy – typicky 20–25 % od optima.
Inšpirovaný mravcami: stovky virtuálnych mravcov prehľadávajú trasy a zanechávajú feromóny. Kratšie trasy sa obnovujú rýchlejšie → feromóny sa hromadia. Ostatní mravce nasledujú silnejšie stopy. Kolónia sa postupne konverguje na vynikajúce riešenie.
Napodobňuje Darwinovu evolúciu. Populácia náhodných trás sa krížia (crossover) a mutujú (náhodná zmena poradia). Lepšie trasy prežijú a odovzdajú vlastnosti potomkom. Po stovkách generácií vznikne výborná trasa – podobne ako v prírode.
Moderné systémy kombinujú základný algoritmus s lokálnym zlepšovaním. 2-opt preberie trasu a hľadá dvojice hrán, ktoré sa kríža – ak ich prehodí, trasa sa skráti. Opakuje sa, kým nie je žiadne ďalšie zlepšenie. Používa sa ako finálny "leštič" po mravčej kolónii alebo genetickom algoritme a zlepší výsledok o ďalšie 2–5 %. Moderné navigácie ako Google Maps kombinujú všetky tieto prístupy súčasne.
Štyri prístupy head-to-head – rýchlosť, presnosť, škálovateľnosť a reálna použiteľnosť v logistike.
| Kritérium | 🔬 Hrubá sila | 📍 Najbližší sused | 🐜 Mravčia kolónia | 🧬 Genetický algoritmus |
|---|---|---|---|---|
| Rýchlosť výpočtu | Extrémne pomalá O(n!) – faktoriálová |
Bleskurýchla O(n²) – kvadratická |
Stredná O(iter × ants × n²) |
Stredná O(gen × pop × n) |
| Presnosť výsledku | 100% optimum Garantované |
~75–80% kvality Priemer 20–25% od optima |
~95–99% kvality Veľmi blízko optima |
~94–98% kvality Záleží od parametrov |
| Max. počet miest | ≤ 12 miest | Tisíce miest | Stovky – tisíce | Stovky – tisíce |
| Pamäťová náročnosť | Astronomická | Minimálna | Stredná (feromóny) | Stredná (populácia) |
| Biologická inšpirácia | Žiadna | Žiadna | Správanie mravcov | Darwinova evolúcia |
| Použiteľnosť v praxi | Len akademicky Hračkárske príklady |
Jednoduché systémy Rýchle hrubé odhady |
Reálna logistika DHL, sieťové smerovania |
Reálna logistika Google Maps, UPS ORION |
| Zaručuje optimum? | ✓ Áno – vždy | ✗ Nie | Pravdepodobne blízko | Pravdepodobne blízko |
Dnešné navigácie neriešia len geometriu. V reálnom čase musia zohľadňovať desiatky faktorov.
Live dáta z GPS senzorov menia čas cesty v reálnom čase. Bratislavská špička môže strojnásobiť čas prejazdu centrom.
Zákazník je doma len 9:00–12:00. Algoritmus musí rešpektovať tieto tvrdé obmedzenia bez ohľadu na optimálnu trasu.
Obmedzený objem a nosnosť. Ťažké balíky sa nakladajú ako posledné – musia byť doručené ako prvé. Poradie nakládky = matematický problém.
Pešie zóny historických centier, zákazy vjazdu nákladných vozidiel v určitých hodinách, hmotnostné obmedzenia na mostoch.
Ak nie je kde zaparkovať, kuriér obchádza – to predlžuje trasu. Pokročilé systémy mapujú pravdepodobnosť nájdenia parkovania pri každej adrese.
Expresné zásielky (Same Day, Next Day) majú vyššiu prioritu. Algoritmus dynamicky preraďuje zastávky podľa SLA zmluvy.
Snehová kalamita, záplavy, poľadovica. Chladený tovar vyžaduje kratšie trasy bez dlhého státia. Algoritmus berie do úvahy prognózy počasia.
Zákazník zrušil objednávku, pribudol nový balík. Systém musí preplánovať trasu v reálnom čase počas jazdy kuriéra.
Klikni na Slovensko a pridaj zastávky. Všetky algoritmy počítajú súčasne – môžeš porovnať ich výsledky, čas aj kvalitu.