Hlavní navigace

Obchodní cestující z e-shopu má plné ruce práce

 Autor: 74287
Pavel Houser 7. 11. 2007

Vánoční nákupní horečka je před branami v kamenném světě i na Internetu. Na čase je posílit servery, zákaznické linky i – logistické oddělení. Nebo se místo toho zamyslet nad optimalizací.

Problém obchodního cestujícího – travelling salesman problem – je známým matematickým/in­formatický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.

Salesman

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…

Anketa

Přemýšlíte někdy nad logistickými problémy?

Našli jste v článku chybu?

7. 11. 2007 18:41

Lukas Nevosad (neregistrovaný)
Tento clanek v jedne vete: Vysel odborny clanek ve vedeckem casopise.

Originalni clanek se mi cist nechce, ale jestli je popis zde zhruba odpovidajici originalu, jedna se o dalsi z tisice zbytecnych praci, jejich predmetem je popis common knowledge. Zase o jednoho PhD vic.

DigiZone.cz: Sat novinky: Je tu Sky Sport News HD

Sat novinky: Je tu Sky Sport News HD

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: Vklad na cizí účet je draze zpoplatněn (přehled)

Vklad na cizí účet je draze zpoplatněn (přehled)

Podnikatel.cz: Berňák kvůli EET prodlužuje otevírací dobu

Berňák kvůli EET prodlužuje otevírací dobu

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

DigiZone.cz: Další dva kanály nabídnou HbbTV

Další dva kanály nabídnou HbbTV

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

120na80.cz: 5 přírodních tipů na bolest v krku

5 přírodních tipů na bolest v krku

Vitalia.cz: Děti patří tomu, kdo je porodil?

Děti patří tomu, kdo je porodil?

Podnikatel.cz: Platební brány a EET? Stále s otazníkem

Platební brány a EET? Stále s otazníkem

Root.cz: Mirai má nový cíl 5 milionů routerů

Mirai má nový cíl 5 milionů routerů

DigiZone.cz: Digi CZ výrazně zlevnila balíček HBO

Digi CZ výrazně zlevnila balíček HBO

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání