Problém obchodního cestujícího – travelling salesman problem – je známým matematickým/informatickým oříškem. Existuje v celé řadě verzí. Může se třeba jednat o úlohu, jak může obchodní cestující projít všechna místa tak, aby na každé z nich vstoupil pouze jednou (rozumí se, že v tomhle problému vedou spojnice pouze mezi určitými místy). V jiné verzi se zase jedná o nalezení nejkratší cesty, která je potřebná pro obsáhnutí všech zadaných míst. A tak dále.
O problému obchodního cestujícího se podařilo dokázat, že patří do třídy tzv. NP-úplných problémů (Wikipedia). Zhruba řečeno to znamená, že jde o úlohu, kde složitost řešení roste v závislosti na složitosti zadání velmi strmě; jak přidáváme další a další body, které má nešťastník projít, stává se nalezení řešení i na nejvýkonnějších počítačích brzy záležitostí času téměř astronomického. Pro NP-úplné problémy ovšem platí, že pokud už nějaké řešení máme, lze (relativně) snadno ověřit jeho správnost. Výsledkem je, že neznáme žádný optimální algoritmus (nebo o tom, který známe, alespoň neumíme dokázat, že je nejlepší), ale v praxi se používají všemožné heuristiky, kdy řešení spíše hádáme a pak se třeba spokojíme s tím, že skutečné optimum nejspíš zase není o tolik lepší, aby se to vyplatilo počítat další milion let.
Jedna z variant úlohy: jaká je nejkratší cesta, pokud je podmínkou vyrazit z bodu A a opět se do něj vrátit?
Na řešení problému obchodního cestujícího bylo mimochodem demonstrováno první použití DNA počítačů (článek [PDF, 114 kB] Leonarda Adlemana na toto téma, bohužel bez vysvětlujících obrázků, v češtině na Science Worldu (bohužel starší text s již zřejmě značně nefunkčními odkazy a poněkud zmateným výkladem NP-úplných problémů). Objevily se i pokusy poštvat na tuto úlohu počítače kvantové, zde však úspěchů prozatím dosaženo nebylo (míněno úspěchů ve smyslu alespoň teoretických algoritmů – on ani ten DNA počítač nebyl zrovna použitelný pro praktické účely).
Problém obchodního cestujícího je zajímavý sám o sobě, v zobecněné rovině (která je dána tím, že jednotlivé NP-úplné problémy jsou na sebe vzájemně převoditelné) se dočkal dokonce té cti, že by zařazen mezi sedm největších nevyřešených matematických problémů pro 21. století. Není to ovšem zdaleka jen nějaká teoretická hříčka, objevuje se v celé řadě situací, kde bychom to na první pohled nečekali. Tímto směrem se ale v tomto článku nadále ubírat nebudeme.
Pokračovat, nebo vyrazit znovu?
Po suchopárném úvodu tedy konečně přejděme k tomu, jako to všechno souvisí s online nákupy. Pochopitelně nám tady nejde o osamělého obchodního cestujícího, ale o logistiku obecně. Nakonec o úspěchu jednotlivých online obchodů nerozhoduje ani tak vlastní softwarové řešení, ale spíše procesy, které se odehrávají za ním. Je třeba zvládnout distribuci objednaného zboží v reálném čase, na druhé straně to ale nemůžete udělat tak, že si přeplníte sklady veškerým zbožím, které nabízíte. Softwarové systémy pro optimalizaci skladových zásob dnes mají pro velké podniky klíčovou roli (ať už se konkrétně pro to používají jakékoliv z těch marketingově populárních třípísmenných zkratek počínaje ERP přes třeba WMS, což je tzv. Warehouse Management System).
Totéž platí pro internetové obchody. Pokud e-shopy distribuují zboží, které se nerozesílá poštou, ale vlastní dodací službou (což ovšem platí pro pizzu stejně jako pro elektroniku), je pro ně důležité nějak optimalizovat i samotný proces dodávky. Samozřejmě, že na úrovni pár dodávek jde o problém triviální, na světovém i českém Internetu ovšem hrají stále více hlavní úlohu mega-dodavatelé; když nic jiného, tak i proto, že dokáží lépe pracovat se všemožnými slevovými akcemi a slučováním („bundlováním“) nabídek.
Teď k tomu připočtěme rostoucí ceny pohonných hmot a očekávanou předvánoční nákupní horečku a rázem se ukazuje, že teoretický problém obchodního cestujícího může mít značný praktický význam i právě zde. Vše je třeba samozřejmě stihnout levně a rychle, s čímž ovšem souvisí i to, že rychle je třeba provést i vlastní optimalizační výpočet. Evidentně se tedy bude jednat o heuristiky.
Oproti klasickému obchodnímu cestujícímu zde ale existuje ještě jeden rozdíl. V původním zadání úlohy byla situace zadaná dopředu. Z hlediska internetového prodejce to ale tak docela neplatí – objednávky přibývají (alespoň v optimálním případě) každou minutou.
Na univerzitě v indickém Madrásu se Chandra Sunil Kumar zaměřil právě na tuto podobu problému (viz tiskové oznámení a další zdroje). Předpokládal, že obchodní cestující ráno vyrazí, řekněme, s tak nějak optimalizovanou trasou, ovšem v průběhu dne budou přibývat další požadavky. Jak nejlépe zareagovat na měnící se situaci? Řekněme, že ve chvíli, kdy přijde první dodatečná žádost, se úloha začne řešit znovu. Vstupem jsou dosud nesplněné úkoly plus úkol nový, vzdálenosti se počítají od místa, kde se náš cešťák zrovna nachází. Takže co teď? Má se prostě zastavit, dokud neobdrží další optimalizovanou trasu? Nebo má ještě nějaký čas sledovat trasu původní a dodatečné požadavky se budou zpracovávat nějak dávkově? U velké firmy navíc nepůjde ani tak o plán trasy pro konkrétního cestujícího, ale o porovnání všech možných tras, na jejichž základě bude zakázka přidělena konkrétnímu člověku.
Přepočítávání se vyplatí
Nepřekvapí, že když budete muset plán cesty neustále modifikovat, nakonec urazíte větší vzdálenost, než kdyby vše bylo zadáno předem – takže předešlá úloha vlastně jinými slovy znamená „komu zakázku přidělit, aby mu cestu nejméně nabourala“. Výsledek z Madrásu ale říká, že i tak se vyplatí provádět přepočítání úlohy než prostě splnit původní plán a aktuální požadavky řešit až dodatečně.
Samozřejmě – pokud rozvážíte zboží, musíte ho také nějak doplňovat. Lze si ale představit, jak tuto komplikaci obejít nebo ji zahrnout do celého modelu. Nebo můžeme uvažovat, že člověk pracuje pro doručovací službu, takže nic doplňovat nepotřebuje, protože prostě jen sbírá zásilky a pak je odveze do nějakého centra, kde se roztřídí a bude s nimi dále nakládáno. A tak dále.
Konkrétní popis optimalizace problému vychází v časopisu International Journal of Logistics Systems and Management. Většina z nás si ho asi nepřečte, neboť jsme až dosud netušili o samotné existenci tohoto média, a ostatně by nebylo nic divného ani na tom, kdyby si to nejzajímavější autoři nechali pro sebe a prodali svou práci jinak. Příjemné na tom každopádně je, že zabývat se takto abstraktním problémem může dotyčnému rýpalovi dnes podle všeho přinést i slušné peníze…
ČLÁNKY DO MAILU