Plánování rozvozu je dnes atraktivní téma, už jen z toho důvodu, že cena pohonných hmot neustále stoupá, zavádí se mýtné, které se následně zdražuje atd. Firmy se proto všemožně snaží minimalizovat náklady spojené s dopravou, například pomocí optimálního modelu s minimem ujetých kilometrů.

Problém pro matematiky

S plánováním trasy se setkáváme denně, ať již prostřednictvím mapových portálů nebo systémů GPS. Případně i my sami nad mapou spekulujeme, jak se nejsnáze dostat z bodu A do bodu B. V tomto případě se jedná o vcelku banální úlohu. Komplikace nastávají, pokud nám v pomyslné mapce přibývají body (uzly), přes které chceme projet. Vše si ještě zkomplikujme tzv. časovými okny, neboli vymezeným časovým úsekem, kdy v daném bodě musíme být. A aby toho nebylo málo, přidejme k tomu zboží, které v daných místech musíme složit, nadto máme omezenou kapacitu nákladního automobilu a zároveň musíme nalézt to nejlepší možné řešení. V praxi vše funguje tak, že se z jednoho distribučního centra snažíme obsloužit maximum odběrných míst s minimálními náklady na vozový park (počet automobilů) a s minimálními výdaji za pohonné hmoty. Pokud si někdo myslí, že v této chvíli vstupuje na scénu softwarové řešení, neboli program, kam lidově řečeno nasypu data, a výsledkem bude optimální trasa, tak je bohužel na omylu. Software představuje už jen jakousi třešničku na pomyslném dortu, protože na scénu nastupují kombinatorici a tvůrci algoritmů. Musíme si totiž uvědomit, že se jedná o úlohu s mnoha proměnnými, matematici hovoří o tzv. Hamiltonově cyklu v obecně neorientovaném grafu. Řečí srozumitelnou, snaží se nalézt minimální hodnotu pro předdefinovanou rovnici.

Nejednoznačné řešení

Zastavme se u nenápadného, ale pro celou naši problematiku klíčového slova – minimální hodnota. Jinými slovy, nevíme jaké je ono jediné řešení kombinatorické úlohy, protože se snažíme nalézt „minimální hodnotu“. Čili náš výsledek, jakkoli uspokojivý, nemusí být tím nejlepším. A toho bychom si měli být vždy vědomi. Nejrůznější softwary, které řeší tzv. síťové úlohy, okružní modely, modely obsluhy atp., totiž pracují na základě programátorsky předdefinovaného algoritmu, který dle určitého postupu vypracuje návrh řešení. Jenomže jakkoli se nám zpracované řešení zdá perfektní, nemusí se nutně jednat o řešení optimální. Může se zcela reálně stát, že na základě jiného algoritmického postupu vznikne výsledek zcela jiný a lepší. Tvůrci softwarových řešení mají pochopitelně tuto alternativu na paměti, ovšem vždy disponují neotřesitelnou vírou, že právě oni našli tu nejnižší ze všech minimálních hodnot.

Příklad z Nošovic

Abychom se nebavili pouze v rovině teoretické, uveďme si jeden praktický příklad. Převod algoritmů pro dopravní úlohy do softwarové podoby není záležitostí pouze developerů pracujících v nadnárodních korporacích. Věnují se mu i univerzity a výzkumná pracoviště po celém světě. Téma je to totiž atraktivní, příkladů je nespočet a jak jsme již uvedli, minimálních řešení může být vícero. Náplní jednoho z vědeckých experimentů se stala reálná situace rozvozu piva z distribučního střediska v Nošovicích. Matematici spojili síly a pomocí algoritmů převedených do počítačového řešení se snažili najít optimální schéma rozvozu s tzv. časovými okny. Sami k tomu dodávají, že použitý software potřeboval k výpočtu více než pět tisíc sekund (zhruba jeden a půl hodiny), přičemž se nepodařilo s dostupným množstvím operační paměti prohledat celou množinu přípustných řešení. Nicméně se jim podařilo získat 21 řešení a optimální z nich prezentovali ve vědeckém článku. Pracovali se skupinou šesti vozidel o různé kapacitě přepravek (80 až 150), dále měli stanovena časová okna v jednotlivých uzlech, požadavek na množství doručeného zboží, pochopitelně nechyběly vzdálenosti mezi jednotlivými uzly. Pro úplnost dodejme, že prezentovali výsledek s dosaženou hodnotou 330 najetých kilometrů, nepočítali ovšem s dojezdem od koncového zákazníka do výchozího bodu, čili reálná výsledná hodnota by byla 380 km. Sami na závěr uvádí: „Vzhledem ke skutečnosti, že čas výpočtu vzorového příkladu prezentovaného v tomto příspěvku byl velmi vysoký, a navíc nebylo dosaženo optimálního řešení, bude další pozornost směřována k hledání dalších matematických modelů, na základě kterých je možné obdobné úlohy řešit v kratším výpočetním čase, případně hledání takových úprav, které povedou k nalezení optimálního řešení.“ (Perner’s Contacts, roč. 6, č. 4, str. 166) Jakoby již autoři sami tušili, že lze celou úlohu zpracovat ještě lépe – a nemýlili se. Celá úloha se stejným zadáním byla podrobena analýze pomocí odlišného algoritmu, na jehož konci (i s dojezdem do výdejního skladu) figuroval výsledek 330 km (tzn. o třináct procent lepší výsledek).

Potulný vědec a nečekané úspory

Závěr celé problematiky je vcelku jednoznačný, můžeme vlastnit sebedokonalejší software, přesto jeho výsledky nemusí být, a pravděpodobně ani nebudou optimální. Nicméně se můžou optimálnímu řešení různě přibližovat. V žádném případě bychom ale neměli žít v iluzi, že „lépe už to nejde“, i když na základě vynaložených investic do systémového řešení nás tato myšlenka bude svádět. Může se totiž reálně stát, že u bran podniku zastaví vědec-matematik a bude tvrdit, že našel svoje optimální řešení. S největší pravděpodobností bude mít pravdu. Ostatně i výše uvedený příklad je důkazem, že řešení je vícero. Bylo by tedy chybným manažerským krokem, pokud bychom takovémuto vědci přibouchli dveře, protože spolu s ním může podnik ušetřit nemalé prostředky. Silně však záleží na hodnotě výsledku a množství uspořených prostředků, může se totiž jednat jen o pár kilometrů, nebo se lze naopak dopracovat k řešení, které obslouží stejný počet míst s nižším počtem nákladních automobilů. Podnik si pak může odškrtnout provozní náklady za vůz i mzdové náklady za řidiče.

V příspěvku jsme hlavní pozornost věnovali rozvážce zboží. Trochu odlišné postupy (algoritmy) pak řeší další oblast logistiky, a to „obslužné modely“, neboli jak například realizovat svoz komunálního odpadu po co nejkratší trase

Robin Rašín, Libor Hladiš
Robin Rašín je obchodním ředitelem společnosti MDP Geo. Libor Hladiš působí tamtéž jako GIS konzultant.