Prečo na to nestačí ani 10 rokov praxe

Vodič, ktorý jazdí tú istú trasu 10 rokov, ju pozná naspamäť. Jazdí ju však podľa zvyku. Medzitým pribudli noví zákazníci, iní odišli a zmenili sa časy doručenia. Algoritmus prepočíta poradie pri každej zmene.

20 zastávok, 1 vodič

možných poradí, v ktorých môže vodič zastávky objísť

Keby ste skúšali jedno poradie za sekundu, trvalo by vám to vyše 77 miliárd rokov, teda viac ako päťkrát dlhšie, než existuje vesmír.

Algoritmus ich nemusí skúšať všetky. Nevýhodné kombinácie vylúči hneď na začiatku a k výsledku sa dostane za pár sekúnd. Preto zastávky väčšinou zoradí lepšie ako vodič, ktorý trasu jazdí roky.

20! = 20 × 19 × 18 × … × 2 × 1

200 zastávok, 10 vodičov

možných plánov

Toto číslo má 390 cifier. Atómov v pozorovateľnom vesmíre je približne 1080, teda číslo s 81 ciframi.

Tu už nejde len o poradie. Treba rozhodnúť, ktoré zastávky dostane ktorý vodič, či sa tovar zmestí do auta a či vodič stihne časové okná zákazníkov. Ručne to dispečerovi zaberie hodiny a výsledok je aj tak kompromis. Rinkai prepočíta celý plán na jeden klik.

Výpočet: 200! × C(199, 9), teda počet spôsobov, ako 200 zastávok rozdeliť medzi 10 vodičov tak, aby mal každý aspoň jednu, a zoradiť ich.

Ako to rieši algoritmus

Úloha sa volá problém obchodného cestujúceho: nájsť najkratšiu okružnú trasu, ktorá prejde všetkými zastávkami práve raz. Keď pribudnú autá s rôznou kapacitou, ide o úlohu rozvozu s viacerými vozidlami (Vehicle Routing Problem).

Presné metódy, napríklad lineárne programovanie s rezmi, vedia dokázať, že nájdená trasa je najkratšia. Pri veľkých úlohách s množstvom obmedzení však môžu počítať veľmi dlho.

V praxi sa preto používajú heuristiky. Začnú rýchlym plánom, napríklad podľa pravidla najbližšej zastávky alebo metódou úspor. Samotné pravidlo najbližšej zastávky však pri náhodne rozmiestnených zastávkach dáva trasy v priemere asi o 25 % dlhšie ako optimum. Heuristiky preto plán ďalej vylepšujú: odstraňujú kríženia, presúvajú zastávky medzi autami a vymieňajú celé úseky trás.

Metaheuristiky, ako simulované žíhanie, tabu search alebo opakované „rozbi a poskladaj“, pomáhajú uniknúť z plánov, ktoré sa už malou zmenou zlepšiť nedajú. Takto funguje aj algoritmus v hre.

Problém starý takmer 200 rokov

  1. 1832Nemecká príručka pre obchodných cestujúcich ukazuje vzorové okružné trasy cez Nemecko a Švajčiarsko. Zatiaľ bez matematiky.
  2. 1857William Rowan Hamilton vymyslí hlavolam Icosian: prejsť všetkých 20 vrcholov dvanásťstena a vrátiť sa na začiatok.
  3. 1930Karl Menger vo Viedni opíše úlohu matematicky a všimne si, že pravidlo najbližšieho suseda nedáva najkratšiu trasu.
  4. 1954Dantzig, Fulkerson a Johnson nájdu a dokážu najkratšiu trasu cez 49 miest v USA.
  5. 1959Dantzig a Ramser opíšu plánovanie cisterien, ktoré zásobujú čerpacie stanice. Vzniká úloha rozvozu s viacerými vozidlami.
  6. 1964Clarke a Wright predstavia metódu úspor, na ktorej dodnes stavajú mnohé plánovače.
  7. 1972Richard Karp ukáže, že ide o NP-ťažkú úlohu. Rýchly algoritmus pre všetky prípady nepoznáme dodnes.
  8. 1976Christofidesov algoritmus zaručí trasu najviac o polovicu dlhšiu ako optimum.
  9. 2006Dokázateľne najkratšia trasa cez 85 900 bodov z návrhu čipov. Výpočet zabral vyše 136 rokov procesorového času.
  10. 2025Dokázateľne najkratšia pešia trasa cez 81 998 barov v Južnej Kórei, najväčšia vyriešená úloha na skutočnej cestnej sieti.

Ďalšie témy

Analýza úsporyAko prebieha analýza úspory

Úsporu spočítame na vašich vlastných jazdách. Uvidíte ju ešte predtým, ako systém zavediete.

Zobraziť postup
Rinkai v praxiČo Rinkai robí

Rinkai Routing je systém na plánovanie a optimalizáciu rozvozových a zvozových trás.

Zobraziť funkcie

Zistite, koľko ušetríte

Ozvite sa a dohodneme bezplatnú analýzu na vašich dátach. Odpovedá priamo konateľ Viktor Balog.

Chcem bezplatnú analýzu 0903 287 806