Problém obchodního cestujícího nad Google Maps
Definice říka, že: „Problém obchodního cestujícího (anglicky Travelling Salesman Problem – TSP) je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě.“ Zdroj: Wikipedie.
Pro každého studenta GIS či již pracujícího GISáka se však jedná o noční můru: Mám x měst, mezi nimi silniční síť a musím najít ideální spojení mezi všemi body na liniové síti. Alternativou je také Problém čínského listonoše.
Na internetu je k nalezení bezpočet různých stránek, které se tomuto problému věnují, ale stránka geoweb.net se chlubí „nejrychlejším“ řešením. Sami si jej můžete vyzkoušet zde. Aplikace nabízí volbu mezi autem a chůzí a jednotlivé výsledky se značně liší – viz obrázky pod článkem. Navýhodou však je, že algoritmus hledá vhodnou trasu pouze v pořádí, v jakém uživatel zadá jednotlivá místa. Podobnou stránkou, která však plní kompletní funkci vyhledání ideální trasy včetně změny pořadí bodů, je RouteXL.
Na konec pro Vás máme malou soutěž. V ukázce (dole) jsme nechali našeho cestujícího „navštívit“ 5 míst v Olomouci – Novou budovu PřF, rektorát UP, Starou budovu PřF, Vědeckou knihovnu a McDonald’s. Pošlete nám krátký, vtipný geopříběh (max 300 slov) popisující cestu našeho cestujícího na adresu redakce@gisportal.cz. Nejlepší příběh oceníme (USB FlashDisk) a budeme publikujeme. Uzávěrka příběhů je 1.12.2011.
