Problém obchodního cestujícího nespočívá v rozhodnutí, na které pumpě si dát kávu. Jde o jednu z nejstudovanějších matematických úloh všech dob. Poprvé byla formulována v roce 1930. Dnes je její řešení základem programů na plánování tras.
Obchodníkova otázka zní jednoduše: Jestliže mám seznam míst a znám vzájemné vzdálenosti mezi nimi, jak určím nejkratší trasu, po které navštívím každé místo jednou a skončím tam, odkud jsem vyjel?
Řešení je ovšem složité a leží na území kombinatorické optimalizace, kterému se ochotně vyhneme. Důležité je, že složitost exaktního řešení vyvolala potřebu dobrat se výsledku heuristickým přiblížením. To usnadnilo vznik počítačových algoritmů pro praktické plánování dopravy.
Budiž pohyb
Zatímco běžné plánovače usnadňují život řidičům a cestovatelům, sofistikované softwary pro optimalizaci tras v podstatě zajišťují ekonomickou udržitelnost současné logistiky.
Zdaleka si nekladou za cíl jen to, aby se auta na cestách neztrácela. Zohledňují dlouhou řadu okolností, na nichž závisí, zda zásilky dorazí k zákazníkům s přijatelnými náklady.
Do hry tak vstupuje poloha a počet dep, ze kterých vozidla vyjíždějí a do kterých by se měla i vrátit (nechceme-li hromadit příslovečné horníky v dole). Proces optimalizace tras počítá s kapacitou, jízdními vlastnostmi a provozními náklady vozidel i s jízdním stylem konkrétních řidičů. Zapojují se znalosti o vlastnostech silničních úseků, reálných rychlostech v určitou denní dobu nebo výskytu uzavírek. A tak dále.
Dispečer pan Superhero
Ocelové nervy aplikace osvědčují při plánování v režimu okamžitého doručení, jaký je typický např. pro rozvoz jídel. Software rozdělující zásilky na dostupná auta sleduje, jak nový cíl ovlivní aktuálně určenou trasu, a do poslední chvíle neváhá plán změnit, jestliže to přepravu urychlí nebo zlevní.
Neocenitelnou službou pokročilých softwarů pro plánování tras je také pečlivá analýza skutečných dopravních výkonů. Program si sám kontroluje úspěšnost svých instrukcí, sleduje skutečné chování řidičů a zobecňuje okolnosti, které mohou algoritmus vylepšit. Dopravcům dodává množství analytických informací a sám navrhuje změny k lepšímu.
Problém vyřešen
Výkonnost plánovacích aplikací je důvodem, proč pronikají do stále menších firem. Na jedné straně flexibilita a komfort plánování, na druhé straně úspory na investicích, palivech, amortizaci vozidel či mýtném: to jsou jasné benefity, a projeví se hned po nasazení systému.
Problém obchodních cestujících je tak, zdá se, vyřešen. Software pro plánování dopravy dnes používá většina firem. Úspory dopravců rostou s jejich šířením. Dá se očekávat, že v době globálního zdražování bude stále rychlejší.
Zdroj: https://en.wikipedia.org/wiki/Vehicle_routing_problem
Autor: Karel Melecký
TIP NA ČLÁNEK: Povinné ručení – jak snadno sjednat a ještě na něm ušetřit?
