Problém obchodního cestujícího v praxi
Hledání nejkratšího pořadí zastávek je klasická úloha známá jako problém obchodního cestujícího. Počet možných pořadí roste faktoriálově: u pěti zastávek jich je 120, u deseti přes tři miliony, u patnácti přes bilion. Přesné řešení je proto pro delší seznamy nepraktické a používají se heuristiky, které najdou velmi dobré, byť ne nutně optimální pořadí.
Pro běžný pracovní den to stačí. Rozdíl mezi optimální a téměř optimální trasou bývá jednotky procent, kdežto rozdíl mezi promyšleným a nahodilým pořadím zastávek klidně třicet i více procent ujeté vzdálenosti. U obchodníka nebo makléře s osmi schůzkami denně to znamená hodinu času navíc.
Vzdálenost vzdušnou čarou versus reálná trasa
Jednodušší plánovače počítají vzdálenosti vzdušnou čarou, tedy po povrchu koule mezi souřadnicemi. To je rychlé a nevyžaduje žádné volání externí služby, ale ignoruje řeku bez mostu, jednosměrky, dálniční nájezdy i uzavírky. V Praze rozdělené Vltavou nebo v členitém terénu může být skutečná trasa výrazně delší než přímá vzdálenost.
Realističtější je pracovat s maticí skutečných dojezdových časů ze silniční sítě. Zásadní je ale zvolit správnou veličinu. Nejkratší trasa v kilometrech není nejrychlejší trasa v čase, a pokud vás zajímá počet schůzek za den, je rozhodující čas, ne vzdálenost.
Časová okna, která plán rozhodnou
Reálné itineráře mají tvrdá omezení, která optimalizace vzdálenosti neřeší. Prohlídka je domluvená na desátou a jinak nejde. Zastávka má otevřeno do čtyř. U některých bodů je nutná rezerva na hledání parkování, což v centrech měst znamená klidně patnáct minut. Ideální geometrická trasa se s těmito okny často vylučuje.
Praktický postup je nejprve zafixovat body s pevným časem, teprve mezi ně dosadit pružné zastávky a k jízdním časům přidat rezervu — ve špičce spíš dvacet procent než deset. Hotovou trasu pak stačí předat mobilní navigaci; ta zvládne přepočítat aktuální dopravní situaci, kterou plánovač den dopředu znát nemůže.