VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY
DIPLOMOVÁ PRÁCE
2014
Bc. Filip Uhlíř
VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY
Název diplomové práce:
Optimalizace logistických procesů ve firmě Kingspan, a. s.
Autor:
Bc. Filip Uhlíř
Katedra:
Katedra ekonometrie
Obor:
Ekonometrie a operační výzkum
Vedoucí práce:
Ing. Jan Zouhar, Ph.D.
Prohlášení: Prohlašuji, že jsem diplomovou práci na téma „Optimalizace logistických procesů ve firmě Kingspan, a. s.“ zpracoval samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury. V Hradci Králové dne 22. prosince 2013
................................ Filip Uhlíř
Poděkování: Rád bych poděkoval Ing. Janu Zouharovi, Ph.D. za vedení mé diplomové práce a za podnětné připomínky, které ji velice obohatily. Dále bych chtěl poděkovat Ing. Janu Jačkovi ze společnosti Kingspan, a.s. za podklady k práci a odborné připomínky.
Abstrakt Název práce: Autor: Katedra: Vedoucí práce:
Optimalizace logistických procesů ve firmě Kingspan, a. s. Bc. Filip Uhlíř Katedra ekonometrie Ing. Jan Zouhar, Ph.D.
Cílem této práce je ukázat využití operačního výzkumu na reálném příkladu z praxe a demonstrovat tak praktickou využitelnost této vědní disciplíny. Řešenou úlohou bude rozvozní úloha s dělenou dodávkou. V textu je uveden celý postup řešení této praktické úlohy od zadání datových vstupů, automatizovaného získávání dat z veřejně dostupných zdrojů pro vzdálenostní matici, vytvořený matematický model pro tuto úlohu i s implementací v SW Lingo. Dále jsou v práci popsány klasické distribuční úlohy lineárního programování s vazbou na řešenou úlohu. Mimo to jsou zde ukázány i tři matematické modely zabývající se tímto typem rozvozní úlohy, které však nelze pro řešený problém použít, neboť obsahuje jisté požadavky či podmínky, které dané modely vůbec neuvažují. Klíčová slova: okružní dopravní problém s dělenou dodávkou, využití operačního výzkumu v praxi, distribuční úlohy lineárního programování.
Abstract Title: Author: Department: Supervisor:
Optimization of logistic processes in the company Kingspan, a.s. Bc. Filip Uhlíř Department of Econometrics Ing. Jan Zouhar, Ph.D.
The aim of this work is to show the application of operational research on an example that is put into practise and to show the usabillity of this science field. The problem solved will be the Vehicle routing problem with split delivery. The whole process of solving this issue is described in the text. From the income data and automatised data aquisition from publicly acessible resources for the distance matrix to the created mathemathical model for this issue together with the implementation in SW Lingo. Furthermore, in my work classic distribution problem of linear programming in connection to the solved issue are described. Beside that three mathematical models are shown that are occyupying with this type of delivery. They can not be used for fading the solution to this issue as they include certain requirements or conditions which are not taken into account by the given models.
Keywords: Vehicle routing problem with split delivery, use of operation research in practice, distribution problem of linear programming.
Obsah ÚVOD ..................................................................................................................................................... 6 1 POPIS PROBLÉMU A DATOVÉ VSTUPY ................................................................................. 8 1.1
Výroba a odbyt sendvičových izolačních panelů ve společnosti Kingspan, a.s. ..................... 9
1.2
Aktuální stav řešení nakládky a rozvozu sendvičových izolačních panelů ........................... 11
1.3
Datové vstupy od společnosti Kingspan, a.s. ........................................................................ 13
1.4
Vlastní datové vstupy ............................................................................................................ 15
2 FORMULACE MATEMATICKÉHO MODELU ...................................................................... 23 2.1
Klasické distribuční úlohy lineárního programování ............................................................ 23
2.2
Některé speciální varianty rozvozních úloh .......................................................................... 27
2.3
Matematický model pro optimalizaci expedice sendvičových izolačních panelů pro společnost Kingspan, a.s. ...................................................................................................... 38
2.4
Implementace řešení v SW Lingo ......................................................................................... 43
3 VÝPOČETNÍ EXPERIMENTY ................................................................................................... 45 3.1
Zadání a příprava vstupních dat ............................................................................................ 45
3.2
Výsledek pro ilustrativní příklad ........................................................................................... 50
3.3
Možnosti implementace pro úlohy reálného rozsahu ............................................................ 52
ZÁVĚR ................................................................................................................................................. 56 LITERATURA .................................................................................................................................... 57 PŘÍLOHY ............................................................................................................................................ 59
5
Úvod V dnešní době ekonomické krize, kdy je snaha ohledně minimalizace nákladů asi největší, jsou společnosti kromě nejrůznějších úspor, také nuceny optimalizovat svoje podnikové procesy. Nejčastěji optimalizovanými procesy ve výrobních společnostech jsou Logistické procesy, což je dáno jednak jejich významností, složitostí a finanční nákladností. Diplomová práce se věnuje logistickým procesům ve společnosti Kingspan, a.s., které se bude snažit optimalizovat pomocí metod operačního výzkumu a dále navrhnout systémový způsob řešení daného problému. Kingspan, a.s., je mezinárodní společnost zabývající se výrobou izolačních materiálů, konstrukčních prvků budov, solárních systémů a mnoho dalších produktů. Diplomová práce se zaměřuje na přepravu jedné konkrétní kategorie výrobků, sendvičových izolačních panelů, jež jsou jako jediné vyráběny na území České republiky. Většina odběratelů sendvičových izolačních panelů se nachází na území Spolkové republiky Německo, kam jsou výrobky přepravovány prostřednictvím silniční dopravy. Tematicky spadá uvažovaný problém do široké kategorie rozvozních úloh (vehicle routing problems, VRP); od standardních hojně popsaných modelů VRP se však v několika ohledech odlišuje. V první řadě budeme uvažovat nákladních vozů více typů, kdy se jednotlivé druhy nákladních vozidel budou od sebe lišit různými charakteristikami, které jsou důležité pro formulaci matematického modelu. Tato nestejnorodost vozidel je dána tím, že společnost využívá různé sjednané přepravce. V odborné literatuře zaměřené na VRP se nejčastěji pro zjednodušení předpokládá pouze jeden typ vozidla, který má vždy stejné parametry. Dalším specifikem zkoumaného problému je práce s nehomogenním produktem. Výše jsme zmínili, že expedice se sice týká pouze jednoho druhu výrobku; pro sendvičové izolační panely nicméně neexistují standardní rozměry, jsou tedy vyráběny na míru dle přání každého jednotlivého zákazníka. V odborné literatuře se s přepravou nehomogenních produktů lze setkat jen zřídka; přeprava nehomogenních produktů pomocí více typů vozidel je tedy to, čím se tato práce odlišuje od většiny dostupné literatury. Celkem vzato, uvažovaný logistický proces se tedy skládá ze dvou hlavních částí: naložení výrobků a následný rozvoz nákladu koncovým zákazníkům. Řešená úloha spočívá ve výběru vhodného počtu jednotlivých druhů nákladních vozidel, do kterých lze naložit požadované množství výrobků zákazníky (včetně konkrétního způsobu naložení), a současného určení rozvozních tras. První kapitola se věnuje zejména seznámení s výrobkem a celému popisu reálné úlohy, kterou se tato práce zabývá. Jsou zde i informace, které pomohou vytvořit celý obraz logistického procesu a to nejen věcí, které se přímo dotýkají pouze nákladky a rozvozu sendvičových izolačních panelů. Je uveden popis současného stavu daného problému, kterým 6
se zabývá tato práce. Popsány jsou i jednotlivé datové vstupy, a to nejen přímo získané od společnosti Kingspan, a.s. Zmíněny jsou například potřebné informace, které obsahují jednotlivé reporty od společnosti Kingspan, a.s., jaká je nejnižší úroveň informace v těchto jednotlivých reportech a samozřejmě i logický vztah mezi nimi, dále pak přejdeme k popisu postupu získávání vlastních datových zdrojů. Následující kapitola se zabývá popisem klasických distribučních úloh a některých speciálních variant rozvozních úloh s dělenou dodávkou (SDVRP). Z těchto modelů byly čerpány základní podmínky, které jsou typické pro tento typ úloh. V návaznosti na to je uveden celý vytvořený matematický model pro náš řešený reálný příklad. Po formulaci vlastního matematického modelu se pak bude práce ve třetí kapitole zabývat výpočetními experimenty a všemu, co s nimi souvisí, ať již to jsou datové vstupy či diskuze nad výpočetní efektivností.
7
1 Popis problému a datové vstupy1 V této kapitole se budeme zabývat zejména popisem problému a všech věcí, který s ním souvisí. Uvedeme si zde popis produktu, jehož přepravu budeme optimalizovat. Dále si popíšeme jeho proces výroby, princip balení do větších celků, které jsou nakládány do nákladních automobilů a další věci, který s tímto produktem úzce souvisí. Poté si pak uvedeme stručný popis, jak funguje v současné době řešení nakládky a rozvozu sendvičových panelů k zákazníkům. Zadání této úlohy spočívá v optimalizaci balení izolačních panelů do balíků vhodných rozměrů, které pak lze naložit do několika typů nákladních automobilů s různou sazbou za ujetý kilometr. Ale jelikož je proces balení panelů již optimalizován a naše úloha by se tím značně zkomplikovala, byla tato část zabývající se optimalizací balení sendvičových izolačních panelů vypuštěna. Volba vhodného typu nákladního automobilu je dána velikostí zakázky a případnou možností sdružení více zakázek do jednoho nákladního vozu, pokud se to vyplatí. Celková cena přepravy se skládá z několika složek. Cena k prvnímu zákazníkovi není účtována podle ujetých kilometrů, ale fixně dle oblasti, kde se první zákazník nachází (podle prvního dvojčíslí PSČ). K této částce se pak přičtou ceny jednotlivých přejezdů k dalším zákazníkům dle skutečně ujetých kilometrů a za každou druhou až n-tou zastávku se připočte fixní cena za vykládku, která je stejná pro všechny druhy vozidel. Zjednodušeně můžeme říci, že v naší řešené úloze jde o to, rozhodnout, kdy se vyplatí poslat tři menší nákladní vozidla se třemi různými zakázkami nebo poslat spíše jeden větší nákladní automobil, který uveze všechny tři zakázky a rozveze je postupně těmto třem zákazníkům. Jako poslední si popíšeme jednotlivé datové zdroje, které budeme v praktické části práce využívat. Datové zdroje, které jsou podkladem pro tuto práci a to hlavně pro její výpočetní část, jsou rozděleny na dvě skupiny a to jednak získané datové zdroje od společnosti Kingspan, a.s., a pak vlastní datové vstupy, které byly získány z volně dostupných zdrojů. Tyto získané informace mají vazbu k primárním datovým vstupům získaných od společnosti Kingspan, a.s. Popis vlastních zdrojů obsahuje i způsob získaní dat, který byl automatizován, aby nebyl pouze jednoúčelový, ale šel případně i využít po jistých drobných úpravách i pro jinou úlohu s jinými zdrojovými informacemi.
1
Informace o společnosti Kingspan, a.s. a obrázky k této kapitole byly získány z webových stránek společnosti http://www.panely.kingspan.cz/sendvicove-panely-zatepleni-izolace-oplasteni-1725.html (5.1.2014, 17:30). 8
1.1 Výroba a odbyt sendvičových izolačních panelů ve společnosti Kingspan, a.s. Společnost Kingspan, a.s. patří k předním světovým výrobcům zateplovacích sendvičovým panelům. Její výrobky vynikají nejen vysokou kvalitou, ale vyhovují i nejrůznějším specifickým požadavkům. Mezi velké výhody jejich izolačních systémů patří snadná a rychlá montáž. Využití sendvičových izolačních panelů je velmi široké, stejně tak i jejich výhody. Mezi všeobecně známé využití izolačních panelů patří použití k izolaci fasád. Pro tento účel existuje mnoho typů sendvičových izolačních panelů o různých tloušťkách. Ta je vybírána dle určení pro konkrétní stavbu v návaznosti na její energetické vlastnosti. Zaizolování fasády pak vede k následné úspoře energií na chlazení či vytápění objektu. Menší spotřeba energií vede k menšímu znečištění našeho ovzduší skleníkovými plyny či jinými tuhy látkami znečišťující ovzduší, které vznikají při výrobě energií. V dnešní době, kdy hospodaření s energií upravují různé zákony a normy se tento produkt právě dostává do popředí zájmů a roste po něm poptávka. Existují však i typy sendvičových izolačních panelů, které mají speciální fasádní stranu a ty lze využít k opláštění celých budov a to i včetně střešních ploch, které bývají velmi často namáhaný přírodními podmínkami. V zimě na sendvičový izolační panel působí tíha mokrého sněhu a v létě pak pnutí díky velkým teplotním rozdílům mezi vnitřní a vnější stranou panelu. Všem těmto silným nepříznivým přírodním vlivům je schopný odolat za předpokladu, že je k němu uzpůsobena celá konstrukce budovy. Tyto sendvičové izolační panely se velmi často používají u velkých objektů, díky jejich snadné a rychle montáži na železné konstrukce. Typický příkladem těchto objektů jsou překladiště, skladovací a výrobní haly, velké hypermarkety a supermarkety. Ze sendvičových izolačních panelů lze vytvořit izolační systémy pro řízenou atmosféru, což je hojně využíváno v potravinářském a farmaceutickém průmyslu. Pro chladírenské a mrazírenské prostory existuje norma, která přesně upravuje tepelné izolace chladíren a mrazíren, které tyto sendvičové izolační panely splňují. Sendvičové izolační panely se dělají se třemi typy zateplovacích jader. Prvním typem je jádro z tuhé polyuretanové pěny s uzavřenými buňkami (PUR). Sendvičové izolační panely s jádrem z tuhého polyuretanu se využívají ve stavebnictví od padesátých let dvacátého století. Druhým typem s větší požární odolností je panel s jádrem z polyizokyanurátu (PIR označován též, jako IPN), který byl vynalezen přímo společností Kingspan, a.s.
9
Třetím typem jádra je minerální vlna. Minerální vlákno vzniká tavením diabasové horniny při vysoké teplotě společně s dalšími surovinami. Vniklá tekutá láva se přeměňuje na vlákna v odstředivé komoře, kde se k ní přidávají další příměsi potřebné například pro impregnaci atd., tyto panely vydrží nezměněny nejméně sto let. Sendvičové izolační panely IPN a PUR mají lehčí jádro oproti panelům s jádrem z minerální vlny a nezabírají tolik místa v nákladním prostoru převážejících aut a tudíž je u nich levnější přeprava. Jak již bylo zmíněno výše, sendvičové izolační panely z minerální vlny jsou vyráběny z horniny a tudíž jejich hmotnost je značně vyšší než panelů PUR a IPN a tudíž jejich doprava je dražší. Pro lepší představu o podobě izolačních panelů jsou zde přiloženy dva obrázky. První obrázek (obr. 1-1) znázorňuje střešní izolační panely, druhý (obr. 1-2) pak stěnové izolační panely a jejich profilaci. Obrázek 1-1: Řez střešními panely
Zdroj: [8]
10
Obrázek 1-2: Vnější a vnitřní profilace sendvičových izolačních panelů
Zdroj: [8]
Společnost vyrábí sendvičové izolační panely na třech výrobních linkách. Na první výrobní lince se vyrábějí izolační panely s jádrem z polyuretanu, kdežto na druhé se vyrábějí panely z materiálu, který má větší hustotu a je tudíž těžší. Tímto materiálem je minerální vlna, která tvoří jádro izolačního panelu. Na třetí se pak vyrábějí stropní izolační panely, kde je specifická podmínka, že v balících musí být sudý počet kusů těchto panelů. Tato podmínka je důležitá, je kvůli konstrukci a montáži střešního izolačního panelu. Každý typ izolačního panelu je dělán v několika různých šířkách. Pro tyto šířky a příslušné kategorizované délky panelů, jsou definovány limity počtů panelů v balíku. Tyto limity jsou definovány, aby váha balíku nebyla větší, jak 3,5 tuny a celková výška balíku nepřekročila 125 cm. Tato hodnota 125 cm je logická vzhledem k tomu, že výška nákladového prostoru standardních nákladních automobilů je 250 cm a balíky se dávají dva na sebe.
1.2 Aktuální stav řešení nakládky a rozvozu sendvičových izolačních panelů V současné době jsou logistické procesy ve společnosti Kingspan, a.s. nastaveny tak, že výroba je řízena programem, který přesně řídí jednotlivé dávky výroby podle zadaných kritérií. V praxi to znamená, že se zohledňuje při rozhodování o plánování výroby požadovaný termín dodání výrobků, minimalizace počtu změn nastavení řezacích linek, na
11
kterých se řežou sendvičové izolační panely na požadovanou délku dle objednávky konkrétního zákazníka a také možnost kompletace panelů do balíků. Například pokud se mají řezat panely s levým řezem a s pravým řezem, tak v rámci úspory času se nejprve vyrobí všechny panely s řezem na jedné straně a ty se hned po nařezání balí do balíků, jež se třídí dle zakázky. Pak se vyrobí izolační panely s řezem z druhé strany, protože pokud by na lince bylo nastaveno, že se nejdříve vyrobí vše k jedné zakázce a až pak se vyrobí další zakázka, muselo by se několikrát během dne změnit nastavení výrobní linky. Takto se změní pouze jednou, čímž dochází k značné úspoře času a nedochází k zbytečným časovým prodlevám na výrobní lince. Balení vyrobených sendvičových izolačních panelů do balíku, je dáno jejich pořadím výroby na výrobní lince. Dále balík musí splňovat následující parametry: maximální výška balíku nesmí přesáhnout 125 cm, kvůli manipulaci s vysokozdvižným vozíkem a jeho celková hmotnost nesmí být větší než 3,5 tuny. V ojedinělých případech může dojít k překročení povolené hmotnosti. Pro balíky jsou sestaveny přípustné efektivní konfigurace z jednotlivých izolačních panelů tak, aby byl balík co nejvíce efektivní. Pojmem efektivní se rozumí, složení balíků na sebe nebo vedle sebe, aby vznikal co nejmenší nevyužitý prostor.
Obrázek 1-4: Balík se sendvičovými izolačními panely pohled č. 2
Obrázek 1-3: Balík se sendvičovými izolačními panely – pohled č. 1
Zdroj: [8]
Zdroj: [8]
Na obrázcích je znázorněna podoba balíku vytvořeného ze sendvičových izolačních panelů. Systém rozvozu a hlavně sdružování zakázek je řízen speciálními vyčleněnými pracovníky s dobrou znalostí Spolkové republiky Německo, co se týká zeměpisných poloh 12
měst a jejich vzájemných vzdáleností mezi sebou po nejkratší možné silniční trase, která umožňuje nákladní přepravu. V praxi si skupina pracovníků rozdělí objednávky a dle svého expertního odhadu se pokouší sdružit menší zakázky do větších aut, pokud se vyplatí přejezd mezi místy dodání. Existují pro každý typ nákladního vozidla již předefinované schémata naložení, kterých se využívá pří rozhodování, zda se zakázka do vozu vejde či nikoliv. Jelikož jsou pokaždé sendvičové izolační panely jinak dlouhé podle přání dodavatele, lze se tak rozhodovat pouze aproximativně zda schéma naložení je vhodné. Pokud není, je třeba vytvořit nové.
1.3 Datové vstupy od společnosti Kingspan, a.s. Problémy při zpracování vstupních dat se týkají zejména možností způsobu poskládání panelů do balíků a jejich následné naložení do nákladních automobilů. Problém s panely spočívá v tom, že existuje nekonečně mnoho velikostí panelů. Vyrábějí se totiž v rozmezí od 2 do 22 metrů, kdy velikost je určena od zákazníka přesně na milimetry, takže je potřeba nějakým způsobem vyrobené izolační panely standardizovat do skupin podle jejich délky v přijatelných intervalech, protože počet standardizovaných velikostí má pak dopad na počet typů balíků, které máme doručit. Velikost balíků je určena nejdelším panelem v balíku, na který se dále skládají další panely různé délky, avšak na panel, který je kladen na spodní panel musím mít délku minimálně 70 % délky spodního panelu. Celkový tvar balíku tedy nemusí vždy tvořit pravidelný kvádr, ale jedna stran může mít schodišťovitý tvar. Počet vrstev panelů v balíků je mezi 4 až 27 kusy, ale tato informace je pro nás nepodstatná, neboť mi řešíme pouze rozvoz jednotlivých balíků. Pokud bychom se zabývali i tvorbou možných kombinací složení balíku, nemusíme řešit omezující podmínky týkající se váhy výsledného balíku, jeho šířky a výšky. Šířka je stále stejná u všech typů izolačních panelů. A co se týká výšky panelů, pro naložení do nákladních vozů výsledný balík má stále přibližně stejnou výšku, která povoluje pouze dva balíky na sobě v každém druhu vozidla. Celková váha sestaveného balíku není důležitá, protože plně naložené auto izolačními panely má stále rezervu do své nosnosti, kromě jedné málo časté výjimky, kterou bychom pro zjednodušení naší úlohy mohli zanedbat. Co se týká výšky balíku, ta musí být maximálně 1,25 metru kvůli manipulaci. Jelikož těchto možností, jak sestavit balíky je nekonečno a tento proces je již optimalizován, nebudeme ho dále v našem problému řešit. Dále existují předepsané nějaké standardy, jak by měl balík vypadat, jakési předdefinované vzory, aby byl balík co nejvíce efektivní.
13
Vstupní informace pro diplomovou práci jsou získány z několika reportů společností Kingspan, a.s. První report ukazuje informace o složení balíků, které jsou poskládány z vyrobených a nařezaných izolačních panelů. Mezi důležité informace patří číslo zakázky, číslo výrobní dávky zakázky, číslo balíku, typ izolačního panelu, počet kusů jednotlivých délek a v neposlední řadě linka, na které se izolační panel vyráběl. Pro každou výrobní linku jsou totiž definovány jiné parametry, které by měl složený balík splňovat. Vše je odvislé od toho, že na každé lince se vyrábějí jiné typy izolačních panelů. Z prvního reportu známe však jen informace o výrobě a nás zajímá informace o požadavcích na přepravu v daném časovém termínu. Pro tuto informaci si musíme „sáhnout“ do druhého reportu, který obsahuje data o naložení jednotlivých nákladních aut. V reportu je uvedeno kolik balíků, které zakázky a jaké výrobní dávky bylo naloženo do konkrétního nákladního automobilu. Celá výrobní zakázka nemusí být expedována přímo najednou. Vše je závislé na požadavcích zákazníka, který si klade požadavky, na termín dodávky na stavbu. Z třetího reportu pak lze vypozorovat, jak byla zakázka expedována, zda nákladní automobil jel jen k jednomu zákazníkovi nebo k více zákazníkům. A samozřejmě lze z něj zjistit i informace, kolik a jakých automobilů jelo k danému zákazníkovi. Pokud bychom chtěli zjistit informaci, jaké jsou celkové náklady na dopravu pro jednoho zákazníka, museli bychom použít informace z třetího reportu a z druhého reportu o naložení jednotlivých zakázek do nákladních aut. Výše celkové ceny přepravy jednoho automobilu je vypočtena jako fixní sazba podle oblasti, kde se nachází první zákazník plus suma cen přejezdů k dalším zákazníkům. K tomuto se připočte za každou zastávku fixní sazba 1000 Kč. Tato sazba se neúčtuje za první zastávku. Z této celkové ceny pak lze pomocí vah vypočítat také výslednou cenu pro jednotlivého zákazníka. Cena se rozpočítává jednak za skutečně ujeté kilometry k zákazníkovi a také podle toho, kolik jeho náklad zaujímal z celkem naloženého materiálu. Váhy pro ujeté kilometry a objem naloženého materiálu mají stejnou důležitost. Z dílčích vah vypočteme agregované váhy: wi 0,5vi 0,5ui
wi - celková váha pro výpočet ceny přepravy pro zákazníka i vi - dílčí váha pro ujeté kilometry k zákazníkovi i
u i - dílčí váha pro naložený náklad pro zákazníka i
14
1.4 Vlastní datové vstupy Mezi datové vstupy, které nemáme k dispozici a je potřeba je získat, patří informace o vzdálenostech mezi jednotlivými městy, kam je potřeba zákazníkům doručit jejich objednané zboží. Tyto jednotlivé vzdálenosti nám poslouží k vytvoření vzdálenostní matice, z které si vypočteme nákladové matice pro každý typ nákladního vozu. Jako vstup by nám teoreticky stačila zjistit pouze horní trojúhelníková matice vzdáleností mezi dvěma různými městy, ale existuje zde riziko, že matice nebude ve skutečnosti symetrická a výsledky tím budou zkresleny. Problém tedy je, jaký je nejvhodnější způsob pro získání jednotlivých vzdáleností mezi městy. První možností je výpočet pomocí euklidovské vzdálenosti. Tento postup bude rychlejší, než vyčíslování vzdálenostní matice pomocí plánovačů tras volně dostupných z webu pro větší rozsah zadání. Tato metoda nám nezaručí přesnou vzdálenost, kterou nákladní vozidlo ujede po silnici, ale dostaneme díky ní rychle výsledky. Metoda pracuje pouze se vzdušnou vzdáleností. Co však nezohledňuje, je výškový profil trasy a přímost cesty. Klasickým příkladem jsou horské silnice. Při použití této metody můžeme dostat výrazně zkreslené vstupy, které nelze úplně použít pro nějaké relevantní výsledky, jež bychom rádi dostali. Jak již bylo zmíněno, ani vyčíslování pomocí klasických vyhledávačů tras není úplně efektivní způsob, byť dostáváme tímto způsobem relevantnější výsledky. Jak tedy tento problém s vyčíslením vzdálenostní matice vyřešit? Jako vhodný nástroj se jeví aplikace The Google Distance Matrix API2.
1.4.1
Aplikace The Google Distance Matrix API
Tato aplikace umožňuje strukturované dotazování na vzdálenosti mezi jednotlivými městy v různých státech světa, která uživatel potřebuje zjistit. Odpovědí na dotaz je vyčíslená vzdáleností matice požadovaných měst. Avšak i tato volně dostupná aplikace má svá úskalí, ale pro korporátního uživatele tato úskalí odpadávají. Tato aplikace má dvě provedení. První verze je bezplatná s nízkými limity a druhá placená verze s výrazně vyššími limity pro dotazovaní na server. Existuje pět základních omezení pro dotazování na The Google Distance Matrix API. 1) Volně dostupná verze a) Délka URL adresy nesmí být delší než 2 000 znaků, což je dostatečné pro volně dostupnou verzi. 2
Informace o aplikaci The Google Distance Matrix API byly získány z webových stránek: https://developers.google.com/maps/documentation/distancematrix/ (5.1.2014, 17:30). 15
b) c) d) e)
Maximální počet výchozích nebo cílových měst je 25. Na jeden dotaz na server je limit 100 prvků, což odpovídá matici 10x10. Během 10 vteřin se nesmíte zeptat na více než 100 prvků. A limit na 24 hodin je 2 500 prvků.
2) Placená verze (Google Maps API for Business) a) Délka URL adresy nesmí být delší než 2 000 znaků, což je dostatečné pro volně dostupnou verzi. b) Maximální počet výchozích nebo cílových měst je 25 c) Na jeden dotaz na server je limit 625 prvků, což odpovídá matici 25x25. d) Během 10 vteřin se nesmíte zeptat na více než 1 000 prvků. e) A limit na 24 hodin je 100 000 prvků. Tato omezení představují v praktických aplikacích poměrně značný problém. Například pro 100 měst je potřeba minimálně 100 dotazů, v případě, že využijeme volně dostupnou verzi. Omezení a problémy, které mohou přinést praktické aplikace jsou popsány v podkapitole 1.4.3. Aplikace má zabudovanou ochranu proti DDoS útoku a pokud je uživatel, který zasílá dotazy vyhodnocen, jako potenciální hrozba, je mu snížen limit na jeden dotaz, denní limit a v krajním případě mu může být odepřen i přístup na server a to vše bez varování. Proměnné v dotazu je možné zadávat ve více jazycích mimo běžné angličtiny a němčiny je lze zadávat i v češtině. Pokud požadované město není v daném jazyce správně napsané, aplikace jej nemusí správně dohledat. Vytvořený dotaz pro získání vzdáleností matice má například následující podobu: http://maps.googleapis.com/maps/api/distancematrix/xml?origins=Aglasterhausen+Germa ny|Berlin+Germany&destinations=Bad Berneck+Germany|Bad Fallingbostel+Germany &mode=car&language=en-EN&sensor=false Výhoda této aplikace je, že zohledňuje i cyklistické nebo pěší trasy, takže pokud místo mode=car dáme mode=walking vzdálenosti se nám budou vyčíslovat podle peších tras nikoliv podle silniční sítě. Ke každému městu je potřeba napsat i stát, kde se nachází. Jednotlivá města se oddělují symbolem „|“. Výchozí města jsou zadávána jako origins. Naproti tomu cílová města jsou zadávána jako destinations. Získaný výstup má následující podobu, jak je patrné obsahuje i údaje o době přejezdu mezi vyhledávanými městy.
16
<status>OKAglasterhausen, NěmeckoBerlín, Německo<destination_address>Bad Berneck, Německo<destination_address>Bad Fallingbostel, Německo<element><status>OK98922 hod, 45 min285921286 km<element><status>OK 174354 hod, 51 min529748530 km
<element><status>OK117093 hod, 15 min344764345 km<element><status>OK 110843 hod, 5 min327098327 km
Odpověď na odeslaný dotaz do aplikace The Google Distance Matrix API lze z webové stránky stáhnout a uložit do formátu xml a pak soubor importovat do MS Excelu nebo výsledek můžeme uložit rovnou přímo do MS Excelu. V obou případech je potřeba upravit strukturu dat. Pro naši úlohu budou data rovnou ukládána přímo do MS Excelu. Celý vlastní automatizovaný návrh pro získávání datových vstupů je uveden v následující podkapitole.
1.4.2
Automatizace získávání dat o vzdálenostech pomocí Microsoft VBA
Pomocí jednoduchého skriptu napsaného ve VBA lze vytvořit celý seznam url adres pro dotazování na vyčíslení potřebné vzdáleností. Makro pouze rozkopíruje funkci CONCATENATE, kterou jsme vytvořili pro první url dotaz v matici vzdáleností. Funkce je napsána pro 5 výchozích a 5 cílových měst, pro jiný rozsah je jí třeba analogicky upravit. =CONCATENATE("http://maps.googleapis.com/maps/api/distancematrix/xml?origins="; city!$A2;"|";city!$A3;"|";city!$A4;"|";city!$A5;"|";city!$A6;"&destinations=";city!B$1;"| ";city!C$1;"|";city!D$1;"|";city!E$1;"|";city!F$1;"&mode=car&language=czCZ&sensor=false") Zde jsou uvedeny scripty VBA, s jejíž pomocí byla získána výsledná vzdálenostní matice pro náš řešený příklad. Jednotlivé dílčí vzdálenosti do vzdálenostní matice z aplikace Google Maps API byly staženy pomocí prvního makra data_web_page. Toto makro stáhlo obsah z dotazované webové stránky a vložilo ho do nového souboru MS Excel, který byl následně uložen pod číslem, které určovalo pořadí dotazované url adresy. V makru byla nastavena časové
17
prodleva, aby nedošlo k překročení limitu vyčíslení 100 vzdálenosti za 10 vteřin, což by vrátilo pouze text, že jsme překročili limit. Sub data_web_page() Application.ScreenUpdating = False Dim Dim Dim Dim Dim
wb As Workbook sourceWb As Workbook ws As Worksheet strURL As String Name As String
For i = 1 To 1369 'for cyklus pro vsechny URL Set wb = Workbooks.Add(xlWBATWorksheet) Set ws = wb.Sheets(1) ws.Name = "Data" strURL = Cells(i, 2).Value Name = Cells(i, 1).Value With ws.QueryTables.Add(Connection:="URL;" & strURL, Destination:=ws.Cells(1, 1)) .BackgroundQuery = False .TablesOnlyFromHTML = False .Refresh BackgroundQuery:=False End With wb.SaveAs Filename:= _ "E:\data_dp_api\" & Name _ , FileFormat:=xlOpenXMLWorkbook wb.Close Application.Wait DateAdd("s", 10, Now)'limit 100 elements per 10s and 1 query Next i Application.ScreenUpdating = True End Sub
Druhý skript sloužil k úpravě stažené webové stránky do MS Excelu, tak aby se s ní dalo dále pracovat, jako s datovým vstupem. Makro je navrženo, tak aby upravovalo strukturu pro výsledek dotazu s počtem až 10 výchozích a 10 cílových měst. A s minimálním počtem 2 výchozích a 2 cílových měst. Pokud by dotaz měl strukturu 1 výchozí město a 10 cílových či 10 výchozích a 1 cílové město, bylo by třeba makro upravit, protože výstup stažené webové stránky do MS Excelu je v jiné podobě. Maximální rozsah 10 výchozích měst a 10 cílových měst byl zvolen, protože maximální rozsah povolený na jeden dotaz je 100 prvku, které jsou požadovaný k vyčíslení. Není problém makro upravit tak, aby bez problému samo zvládalo rozsah matice 5 výchozích a 20 cílových měst nebo opačně. Jediné co je potřeba přidat, jsou další příkazy Case. Pokud bychom měli napsanou modifikaci pro matici 20 výchozích a 20 cílových měst a toto makro by upravovalo pouze workbook, kde by byl pouze rozsah dotazu 2 výchozí a 2 cílová města, makro bude fungovat bez problému a příkazy case, které jsou navíc, se nepoužijí. 18
Sub data_modify() Application.DisplayAlerts = False Application.ScreenUpdating = False Dim Dim Dim Dim Dim
wbk As Variant last_row_dest As Integer destination_last_row As Integer last_row_orig As Integer origin_last_row As Integer ChDir "E:\data_dp_api" wbk = Dir("E:\data_dp_api\")
While (wbk <> "") Application.Workbooks.Open (wbk) ActiveSheet.Range("A1").EntireRow.Delete ActiveSheet.Cells(1, 12).Value = "/column/#id" ActiveSheet.Cells(1, 13).Value = "/origin_address" ActiveSheet.Cells(1, 14).Value = "/destination_address" last_row_dest = 2 Do While ActiveSheet.Cells(last_row_dest, 1) <> "" 'cyklus pro nalezeni posledniho radku last_row_dest = last_row_dest + 1 Loop destination_last_row = last_row_dest - 1 last_row_orig = last_row_dest Do While ActiveSheet.Cells(last_row_orig, 2) <> "" 'cyklus pro nalezeni posledniho radku last_row_orig = last_row_orig + 1 Loop origin_last_row = last_row_orig - 1 end_for = origin_last_row + (destination_last_row - 1) * (origin_last_row - destination_last_row) Cells(origin_last_row + 1, 12) = 1 For k = origin_last_row + 1 To end_for If ActiveSheet.Cells(k, 3).Value = ActiveSheet.Cells(k - 1, 3).Value Then ActiveSheet.Cells(k, 12).Value = ActiveSheet.Cells(k - 1, 12).Value + 1 Else: ActiveSheet.Cells(k, 12) = 1 End If Next k For i = origin_last_row + 1 To end_for Select Case ActiveSheet.Cells(i, 3) Case "1" ActiveSheet.Cells(i, 13) = ActiveSheet.Cells(destination_last_row + 1, 2).Value Case "2" ActiveSheet.Cells(i, 13) = ActiveSheet.Cells(destination_last_row + 2, 2).Value
19
+ + + + + + + +
Case "3" ActiveSheet.Cells(i, 3, 2).Value Case "4" ActiveSheet.Cells(i, 4, 2).Value Case "5" ActiveSheet.Cells(i, 5, 2).Value Case "6" ActiveSheet.Cells(i, 6, 2).Value Case "7" ActiveSheet.Cells(i, 7, 2).Value Case "8" ActiveSheet.Cells(i, 8, 2).Value Case "9" ActiveSheet.Cells(i, 9, 2).Value Case "10" ActiveSheet.Cells(i, 10, 2).Value End Select
13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row 13) = ActiveSheet.Cells(destination_last_row
Select Case ActiveSheet.Cells(i, 12) Case "1" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(2, 1).Value Case "2" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(3, 1).Value Case "3" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(4, 1).Value Case "4" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(5, 1).Value Case "5" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(6, 1).Value Case "6" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(7, 1).Value Case "7" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(8, 1).Value Case "8" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(9, 1).Value Case "9" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(10, 1).Value Case "10" ActiveSheet.Cells(i, 14) = ActiveSheet.Cells(11, 1).Value End Select Next i ActiveSheet.Range("A1:B1").EntireColumn.Delete ActiveSheet.Range("A2", "A" & origin_last_row).EntireRow.Delete ActiveWorkbook.Save ActiveWorkbook.Close wbk = Dir Wend
20
Application.ScreenUpdating = True Application.DisplayAlerts = True End Sub
Třetí skript slouží k tomu, aby se data pro jednotlivé dílčí vzdálenostní matice dostaly z jednotlivých workbooku do jedné záložky v jednom Excelu. Každý MS Excel se otevře, najde se poslední řádek, kde končí data a rozsah se zkopíruje a vloží do cílové záložky v jiném souboru. Poté dostaneme data pro naši vzdálenostní matici, kde jeden řádek je vyčíslení jednoho prvku vzdálenostní matice. Výsledná data dostaneme už do matice pomocí funkce vlookup. Sub data_all() Application.DisplayAlerts = False Application.ScreenUpdating = False Dim wbk As Variant Dim last_row As Integer Dim lr As Integer ChDir "E:\data_dp_api" wbk = Dir("E:\data_dp_api\") While (wbk <> "") Application.Workbooks.Open (wbk) last_row = 1 Do While ActiveSheet.Cells(last_row, 1) <> "" 'cyklus pro nalezeni posledniho radku last_row = last_row + 1 Loop lr = last_row - 1 ActiveSheet.Range("A2", "N" & lr).Copy Windows("diplomka_DM_vs02_5x5_matice.xlsm").Activate Call get_last_row_fce(dm_lr) ActiveSheet.Cells(dm_lr, 1).Select ActiveSheet.Paste Windows(wbk).Activate ActiveWindow.Close wbk = Dir Wend Application.ScreenUpdating = True Application.DisplayAlerts = True End Sub Function get_last_row_fce(get_last_row) get_last_row = 2
21
Do While Workbooks("diplomka_DM_vs02_5x5_matice").Sheets("data").Cells(get_last_row, 1) <> "" 'cyklus pro nalezeni posledniho radku get_last_row = get_last_row + 1 Loop End Function
1.4.3
Limitace při použití pro úlohu reálného rozsahu
Pro volně dostupnou verzi aplikace The Google Distance Matrix API se limity pro dotazování inzerované na internetových stránkách aplikace značně liší oproti realitě. Ve skutečnosti je celkový denní limit pro dotazování poloviční oproti inzerovaným 2 500 prvkům, které jsou uvedeny na webu aplikace. Aby se uživatel vyhnul podezření z toho, že chce zatížit server dotazy, je volba menšího rozměru matice pro dotazování vhodná, možná i nezbytná. Toto se týká omezení 100 prvků na 10 vteřin. V realitě se jedná spíše o minuty než vteřiny. Takže pokud bychom měli automatizované dotazování na aplikaci The Google Distance Matrix API jako máme v našem případě a jeden dotaz by právě obsahoval 100 prvků a my takových dotazů chtěli za sebou odeslat třeba 10, stane se to, že se nám stáhnou jen některé dotazy a to i při nastavení velkých časových prodlev např. 10 minut. Provádět poté následnou validaci a doplňkové dotazování je poměrně zdlouhavé a málo uživatelsky přívětivé, je proto vhodné se dotazovat na menší matice než je velikost 100 prvků.
22
2 Formulace matematického modelu V této kapitole, než přejdeme k vlastnímu matematickému modelu pro naši řešenou úlohu, si uvedeme několik matematických modelů pro klasické distribuční úlohy, kterými se zabývá lineární programování. Modely si popíšeme a vysvětlíme souvislosti s úlohou, kterou se zabývá tato práce. Dále si představíme i některé matematické modely pro speciální varianty rozvozních úloh. Tyto speciální varianty řeší rozvozní úlohu s dělenou dodávkou. Níže uvedené modely posloužily k porozumění daného problému a jeho možné formulaci. Z některých společných podmínek pak bylo vycházeno pro formulaci vlastního matematického modelu. Jako poslední si uvedeme matematický model s popisem sestavený přímo pro naši řešenou úlohu.
2.1 Klasické distribuční úlohy lineárního programování 2.1.1
Dopravní problém
Dopravní problém formulovaný v [1] je základní úlohou již výše zmíněných distribučních úloh, kterými se budeme v této kapitole zabývat. V dopravním problému se nejčastěji řeší rozvržení rozvozu od dodavatele k odběrateli, tak aby celkové náklady na tento rozvoz byly minimální. Náklady na přepravu se odvozují od počtu přepravovaných jednotek mezi dodavatelem a odběratelem. Existují dva typy dopravního problému, vyrovnaný a nevyrovnaný. Pokud dopravní problém není vyrovnaný, lze ho jednoduše převést na vyrovnaný problém a to tak, že zavedeme fiktivního odběratele či dodavatele. V naší distribuční úloze, kterou se v práci zabýváme, se kapacitou rozumí pouze kapacita určitého typu vozu daná délkou jeho nákladového prostoru. Ale všech typů nákladních vozů máme neomezený počet kusů, protože k přepravě balíků jsou využíváni specializovaní přepravci, takže celkovou možnost kapacity dodavatelů nemusíme vůbec řešit. A kromě toho máme fakticky pouze jednoho dodavatele, i když si pro převoz najímá spediční společnosti, které převážejí jeho výrobky zákazníkům. Nejprve si tedy uvedeme matematický model dopravního problému, který posléze rozebereme a vysvětlíme. Minimalizovat m
n
z cij xij
(2.1)
i 1 j 1
23
za podmínek n
xij ai ,
i 1,2,..., m,
(2.2)
j 1,2,..., n,
(2.3)
j 1
m
xij b j , i 1
xij 0, i 1,2,..., m, j 1,2,..., n.
(2.4)
Nyní přejde ke krátkému popisu matematického modelu. V modelu máme m dodavatelů a n odběratelů. Index i nám označuje, o jakého dodavatele se jedná. Index j označuje odběratele. Každý dodavatel má omezenou kapacitu a ta je značena ai. Na druhé straně bj pak označuje velikost požadavku odběratele. Proměnná xij vyjadřuje, kolik jednotek se přepraví mezi dodavatelem i a odběratelem j. Koeficient cij vyjadřuje cenu přepravy nákladu mezi dodavatelem i a odběratelem j. Účelová funkce (2.1) minimalizuje náklady na přepravu mezi dodavatelem a odběratelem. První podmínka (2.2) slouží k tomu, aby žádný dodavatel neměl dodávat více, než jsou jeho kapacitní možnosti. Druhá (2.3) podmínka zajišťuje, aby se každému odběratelovi dostal objem zboží, který požaduje. Poslední podmínka (2.4) je podmínkou nezápornosti pro proměnnou xij.
2.1.2
Kontejnerový dopravní problém
Kontejnerový dopravní problém v [1] modifikuje klasický dopravní problém tak, že zboží se od dodavatele k zákazníkovi přepravuje pomocí kontejnerů s danou kapacitou, za které se účtuje cena. Ať jede kontejner plný či poloprázdný, vždy za něj bude účtována stejná cena a to u předchozí formulace nebylo, tam se cena účtovala ze převážené jednotky. V našem případě by se dal každý typ vozu chápat jako jistý druh kontejneru, ale problém je, že se pro tento typ úlohy předpokládá homogenní produkt, což naše palety se sendvičovými izolačními panely rozhodně nejsou. A navíc musíme řešit i umístění jednotlivých balíku ve voze, abychom mohli zajistit správné pořadí vyložení. O tom se více zmíníme dále v textu. Opět si nejdříve předvedeme matematický model pro kontejnerový dopravní problém a pak si jej celý vysvětlíme. Minimalizovat m
n
z cij yij
(2.5)
i 1 j 1
24
za podmínek n
xij ai , i 1,2,..., m,
(2.6)
j 1
m
xij b j ,
j 1,2,..., n,
(2.7)
xij Kyij , i 1,2,..., m, j 1,2,..., n,
(2.8)
xij 0, i 1,2,..., m, j 1,2,..., n,
(2.9)
i 1
yij Z 0 , i 1,2,..., m, j 1,2,..., n.
(2.10)
Nyní si opět uděláme krátký popis matematického modelu pro kontejnerový dopravní problém, jelikož jsou některé části modelu totožné s předchozím modelem, nebudeme je zde už uvádět a pouze si popíšeme věci, které jsou navíc nebo se odlišují. Konstanta K vyjadřuje kapacitu kontejneru. Novou proměnnou, která v tomto modelu přibyla oproti předchozímu, je proměnná yij. Tato proměnná vyjadřuje, kolik kontejnerů o kapacitě K jede mezi dodavatelem i a odběratelem j. Dále se pak k této proměnné vztahuje pátá podmínka (2.10), která říká, že tato proměnná musí být celočíselná. Třetí podmínka (2.8) zajišťuje to, aby kapacita všech kontejnerů, které jedou od dodavatele i k odběrateli j bude menší nebo rovna objemu zboží, které má právě od toho dodavatele i k odběrateli j jet. Účelová funkce (2.5), pak minimalizuje celkové náklady na přepravu všech kontejnerů mezi dodavateli a odběrateli. Podmínky (2.6), (2.7) a (2.9) jsou stejné, jako v předešlém modelu.
2.1.3
Okružní dopravní problém
Okružní dopravní problém uvedený v [2] je označován též jako úloha obchodního cestujícího. Spočívá v tom, že je potřeba najít trasu z daného místa, navštívit všechny další místa právě jednou, vrátit se zpět do výchozího místa a urazit přitom nejkratší vzdálenost. Z níže uvedeného modelu můžeme využít do vlastního matematického modelu upravenou podmínku proti parciálním cyklům. Nejdříve si uvedeme samotný matematický model a pak si jej popíšeme. Minimalizovat n
n
z cij xij
(2.11)
i 1 j 1
25
za podmínek n
xij 1, i 1,2,..., n,
(2.12)
j 1
n
xij 1,
j 1,2,..., n,
(2.13)
i 1
i j nxij n 1, i 1,2,..., n, j 2,3,..., n,
(2.14)
xij 0,1, i 1,2,..., n, j 1,2,..., n.
(2.15)
Matematický model obsahuje tři proměnné xij, i a j. Proměnná xij nabývá hodnot nula a jedna, což vyjadřuje poslední podmínka (2.15). Hodnoty jedna nabývá, pokud povede cesta mezi místem i a j v navrhovaném okruhu. Proměnné i a j pak nabývají libovolných hodnot. Cenový koeficient je opět vyjádřen cij. Model je formulován jako klasický přiřazovací. První dvě podmínky (2.12) a (2.13) říkají, že jedna hrana z cyklu v uzlu končí a z druhého vychází. Problém je doplněný o třetí podmínku (2.14), takzvanou smyčkovou podmínku zamezující parciálním cyklům. Účelová funkce (2.11) minimalizuje celkovou ujetou vzdálenost, celkovou dobu přejezdů či náklady na ujetou trasu.
2.1.4
Rozvozní úloha
Rozvozní úloha v [3] je rozšířenou úlohou obchodního cestujícího v tom smyslu, že místo jednoho cyklu jich můžeme mít více. První uzel je brán, jako výchozí místo a tak je třeba ho zahrnout ve všech cyklech. Podmínky modelu zajišťují, aby všechny okruhy pokryly všechny uzly, které je třeba navštívit. Úloha navíc obsahuje kapacitní omezení pro každé vozidlo, které je vypravováno k obsluze zákazníků. Kapacitní podmínky spočívají v tom, že by suma všech požadavků odběratelů neměla překročit kapacitu vozidla, které je má za úkol obsloužit. Jinými slovy suma požadavků odběratelů na vytvořeném okruhu, který má obsloužit dané vozidlo, nesmí být větší než jeho kapacita. V naší řešené úloze však může nastat situace, že jedno vozidlo obslouží několik zákazníků a jeden zákazník bude tedy obsloužen několika automobily. Jinak řečeno jeho požadavek bude rozdělen do několika cyklů, což tento níže uvedený model neřeší. A navíc se často stane, že jedno vozidlo ani nepokryje požadavky jednoho konkrétního zákazníka. O modelu rozvozní úlohy s dělenou poptávkou se zmíníme až po vysvětlení modelu klasické Rozvozní úlohy.
26
Minimalizovat n
n
z cij xij
(2.16)
i 1 j 1
za podmínek n
xij 1, i 2,3,..., n,
(2.17)
j 1
n
xij 1,
j 2,3,..., n,
(2.18)
i 1
ui a j 2V (1 xij ) u j , i 1,2,..., n., j 2,3,..., n,
(2.19)
ai ui V , i 1,2,..., n,
(2.20)
u1 0
(2.21)
xij 0,1, i 1,2,..., n, j 1,2,..., n.
(2.22)
Nyní opět popíšeme odlišnosti či věci, které jsou navíc oproti předchozím modelům, abychom zbytečně neopakovali věci, které jsou již vysvětleny výše. Cenový koeficient je vyjádřen cij a proměnná xij je opět bivalentní. Hodnoty jedna nabývá, pokud povede cesta mezi místem i a místem j. Kapacitu vozidla označujeme V. V modelu přibyly proměnné ai a aj, proměnné ui a uj nahrazují proměnné i a j z minulého modelu. Proměnné ai a aj vyjadřují velikost nákladu naloženého v uzlu i respektive v uzlu j. Naproti tomu proměnné ui a uj jsou velikosti nákladu naloženého ve vozidle po návštěvě uzlu i respektive uzlu j. Místo smyčkových podmínek použijeme třetí podmínku (2.19). Čtvrtá podmínka (2.20) zajišťuje, aby objem naloženého nákladu v uzlu i a velikost celkového nákladu po navštívení daného uzlu i nepřesáhla kapacitu vozidla o velikosti V. Účelová funkce (2.16) opět minimalizuje celkovou ujetou vzdálenost či ujetý čas. Pátá podmínka (2.21) zajišťuje, že první uzel nemá žádné kapacitní požadavky neboť je to výchozí stanice, kam se všechny vozy vrátí.
2.2 Některé speciální varianty rozvozních úloh V této podkapitole si představíme tři matematické modely, které řeší rozvozní úlohu s dělenou poptávkou. Jeden z těchto modelu dokonce řeší přepravu nehomogenních produktů, což je rozdíl oproti většině konstruovaných matematických modelů. Modely sice řeší stejný typ úlohy, jako je ta naše, ale nelze je využít pro náš typ úlohy.
27
Rozvozní úloha s dělenou dodávkou (SDVRP) je rozvozní úloha s omezenou kapacitou vozidla (CVRP), kde každý zákazník může být navštíven více než jednou. Důvod, proč se poptávka zákazníků dělí mezi více vozů, je jednoduchý. Tímto rozdělením lze snížit počet využívaných vozidel a také snížit přejezdové vzdálenosti mezi jednotlivými zákazníky a to vše pak vede k úspoře nákladů.
2.2.1
Model 1 (podle[4])
Tento matematický model, kromě podmínek podstatných pro zachování úlohy obsahuje i doplňující podmínky, které posilují formulaci úlohy, ale na její charakter nemají vliv. Autoři v textu [4] definují úlohu SDVRP takto: Nechť G = (N, A) je úplný a orientovaný graf, kde N je množina všech uzlů N = {1,2,…,n } a A je množina všech hran A = {(i,j), i,j ∈ N, i ≠j}. Uzel jedna značí pochopitelně depo, které je výchozím a cílovým místem všech okruhů a uzly 2 až n, pak jednotlivé zákazníky, které je potřeba obsloužit. Následná formulace matematického modelu je vytvořena kombinací orientovaného a neorientovaného grafu. Formulace nepředpokládá symetrickou vzdálenostní matici. Minimalizovat n
n
m
z cij xijk i 1 j 1 i j
(2.23)
k 1
za podmínek m
vik di , i 2,..., n,
(2.24)
k 1 n
vik Q, k 1,..., m,
(2.25)
i 2
n
n
i 1 i p
j 1 j p
xipk x pjk 0, k 1,..., m, p 1,..., n,
(2.26)
uik u jk nxijk n 1, i 2,..., n, i j, k 1,..., m,
(2.27)
di yik vik , k 1,..., m, i 2,..., n,
(2.28)
28
n
xijk yik , k 1,..., m, i 2,..., n,
(2.29)
j 1 j i n
( x1 jk x j1k ) 2, k 1,..., m,
(2.30)
xijk 0,1, i 1,..., n, j 1,..., n, i j, k 1,..., m,
(2.31)
yik 0,1, i 2,..., n, k 1,..., m,
(2.32)
vik 0, i 2,..., n, k 1,..., m.
(2.33)
j 2
doplňující zesilující podmínky yik vik , k 1,..., m, i 2,..., n,
(2.34)
n
di xijk vik , k 1,..., m, i 2,..., n,
(2.35)
j 1 j i n
yik 1, k 1,..., m,
(2.36)
i 2 m
yik 1, i 2,..., n,
(2.37)
xijk x jik 1, i 2,..., n, j 2,..., n, i j, k 1,..., m,
(2.38)
k 1
n
n
m
xijk n 2m 2,
(2.39)
i 1 j 1 k 1 j i n
m
yik n m 2,
(2.40)
i 1 k 1
n
xijk x jpk , k 1,..., m, i 2,..., n, j 2,..., n,
(2.41)
p 1 p i
n
n
n
n
cij xijk cij xijk 1, k 1,..., m 1, i 1 j 1 j i
(2.42)
i 1 j 1 j i
29
n
n
j 2
i 2
c1 j x1 jk ci1xi1k , k 1,..., m,
(2.43)
yik yip y jk y jp 3, i 2,..., n, j 2,..., n, i j, k 1,..., m, p 1,..., m, p k.
(2.44)
Nyní si popíšeme matematický model. Náklady přejezdu po hraně (i,j) jsou označeny cij a požadavky každého zákazníka jsou di a pro platí d1 = 0. Celková poptávka všech zákazníků je pak označena jako D. Tento model předpokládá, že všechny vozy mají stejnou kapacitu Q. Podle celkové poptávky D a kapacity Q je odvozen minimální počet okruhů K, který je potřeba vytvořit pro uspokojení všech zákazníků. Indexem i a indexem j označujeme zákazníky. Index k vyjadřuje, o jakou trasu se jedná. Jak jsme již popsali dříve, počet uzlů (počet zákazníků + depo) je n a počet všech tras vozidel je pak m. V modelu jsou použity čtyři proměnné. První proměnnou je bivalentní proměnná xijk, která nabývá hodnoty jedna, pokud vede trasa mezi uzly i a j na okruhu k, jinak nabývá hodnoty nula. Volné proměnná uik a ujk slouží k zamezení vzniku parciálních cyklů, které jsou nežádoucí. Třetí proměnnou je binární proměnná yik, která nabývá hodnoty jedna, pokud je uzel i navštíven na trase k, jinak nabývá hodnoty nula. Poslední proměnná pak vyjadřuje množství, které je doručeno do uzlu i na trase k. Poslední dvě proměnné nejsou definovány pro i = 1, protože se jedná o depo a to nemá žádné požadavky. Účelová funkce (2.23) minimalizuje celkovou ujetou vzdálenost, která je potřeba k obsloužení všech zákazníků a uspokojení jejich požadavků. Podmínka (2.24) sčítá přes všechny trasy k množství zboží, které je dodáváno zákazníkovi i na každé trase. Tím je zajištěno, že každý zákazník dostane vše, co požaduje. Podmínka (2.25) pak zamezuje tomu, aby součet naloženého množství zboží ve voze, jenž jede po trase k, nepřekročil jeho kapacitu o velikosti Q. Podmínka (2.26) vyjadřuje, že pokud se dostaneme do uzlu p, pak z něj také musíme odjet. Podmínka (2.27) zamezuje tvorbě parciálních cyklů. Podmínka (2.28) zajišťuje, že pokud se veze na trase k zboží zákazníkovi i, tak proměnná yik musí nabývat hodnoty jedna. S tím souvisí i podmínka (2.29), která vyjadřuje, že pokud se dostaneme k zákazníkovi i musí existovat jedno spojení z toho uzlu na trase k do uzlu j. Podmínka (2.30) zajišťuje, aby depo bylo výchozí a cílové místo pro každé vozidlo jedoucí na trase k. 30
Podmínka (2.31) a podmínka (2.32) zajišťuje, že proměnné xijk a yik jsou binární a podmínka (2.33) vyjadřují nezápornost proměnné vik. Po vysvětlení podstatných podmínek matematického modelu si ještě ozřejmíme doplňující podmínky, které nemají vliv na základní podstatu matematického model pro rozvozní úlohu s dělenou dodávkou. Podmínka (2.34) vyjadřuje, že pokud je zákazník i navštíven, tak je mu také zboží doručeno. Podmínka (2.35) zajišťuje, že zboží může být doručeno zákazníkovi i, pouze pokud je také navštíven. Podmínka (2.36) zajišťuje, aby byl každý zákazník navštíven aspoň jednou, stejně pak podmínka (2.37) hlídá, aby každá trasa byla použita. Podmínka (2.38) zamezuje vzniku duplicitě spojení dvou míst na jedné trase. Duplicitou je myšleno, aby trasa k neobsahovala spojení z uzlu i do uzlu j a zároveň neexistovalo i spojení z uzlu j do uzlu i na tom samém okruhu. Podmínka (2.39) omezuje horní mezí počet všech spojení mezi jednotlivými zákazníky a tím omezuje tvorbu některých dílčích cyklů. Horní mezí se rozumí počet hran, který je potřeba v optimálním řešení. Podmínka (2.40) vyplývající z předešlé podmínky omezuje horní mezí celkový počet návštěv všech zákazníků. Tato horní mez je odvozena dle optimálního řešení. Podmínka (2.41) zamezuje vzniku některých parciálních cyklů vzniklých uvolněním podmínek pro xijk. Podmínka (2.42) eliminuje alternativní optimální řešení alternativních řešení dochází pomocí řazení tras od nejkratší po nejdelší.
cyklů.
Zamezení
Alternativní optimální řešení jsou zrušeny podmínkou (2.43). Tato podmínka zajišťuje vybrání nejkratší hrany ve směru cyklu a také se zároveň pomocí této hrany dostaneme nejblíže zpět k depu. Poslední podmínka (2.42) zakazuje rozdělení dodávky pro zákazníka i a zákazníka j do dvou cyklů k a p. Tento model pro naši úlohu nelze aplikovat z několika důvodů. Jednak díky předpokladu dopravy pouze homogenního produktu a také kvůli jednomu typu vozidla. Vzhledem k tomu, že pro určité typy vozidel v naší úloze platí speciální podmínky. A mimo to my musíme rozdělit vůz i na jednotlivé sektory, pro které jsou stanoveny podmínky, které je třeba dodržet. 31
Autor sice nepředpokládá symetrickou vzdáleností matici stejně, jako my v naší úloze, ale řeší i cestu zpět což je vidět na zesilující podmínce (2.43). Tuto skutečnost nemusíme vůbec řešit, neboť pro cestu zpět do depa od jakéhokoliv zákazníka jsou náklady v naší úloze nulové. Je to kvůli tomu, že ve skutečnosti si dopravce po doručení zboží shání zákazníky sám, aby se mu rentovala cesta zpět a vůz do depa nejel prázdný. Co se týká tvorby cyklů v našem případě, musíme také řešit pořadí vykládky balíků pro jeden typ vozidla. Tato podmínka je nezbytná pro nadrozměrný typ vozidla, neboť spodní paleta určuje celkovou možnou kapacitu pro horní sektory, ale o tom již více v kapitole 2.3, kde je popsán vytvořený model pro naši úlohu.
2.2.2
Model 2 (podle [5])
Autoři v textu [5] definují úlohu k - SDVRP , kde k představuje množství zboží dodaného zákazníkovi takto: Máme graf G = (V, E), kde vrchol V = {0,1,…,n }, kde vrcholem nula je označeno depo, a ostatní vrcholy představují zákazníky, které je potřeba obsloužit. Sadu hran pak pochopitelně značíme E a tedy (i,j) ∈ E. Požadavky na dodání zboží jsou definovány pro všechny vrcholy V-{0}, což je logické, neboť se opět jedná o depo. Minimalizovat n
n
m
z cij xijv
(2.45)
i 0 j 0 v 1
za podmínek n
m
xijv 1,
j 0,..., n,
(2.46)
i 0 v 1 n
n
i 0
j 0
xipv xvpj 0, p 0,..., n, v 1,..., m,
(2.47)
xijv S 1, v 1,..., m, S V 0,
(2.48)
iS jS
n
yiv d i xijv , i 1,..., n, v 1,..., m,
(2.49)
j 0
m
yiv di , i 1,..., n,
(2.50)
v 1
32
n
yiv k , v 1,..., m, i 1
(2.51) xijv 0,1, i 0,..., n, j 0,..., n, v 1,..., m,
(2.52)
yiv 0, i 1,..., n, v 1,..., m.
(2.53)
Nyní opět přejdeme k popisu a vysvětlení výše uvedeného matematického modelu pro k - SDVRP. Indexem i a indexem j jsou označovány vrcholy, které představují jednotlivé zákazníky. Indexem v je označeno konkrétní vozidlo, které obsluhuje na vytvořeném cyklu zákazníky i a j. Stejně jako u předchozí úlohy i zde jsou oceněny jednotlivé spojení dvou vrcholů v grafu. Toto ocenění představuje koeficient cij, který může představovat jednat cenové náklady na přejezd nebo vzdálenost mezi oběma vrcholy. Velikost požadavku zákazníka i představuje di. Od sumy požadavků všech zákazníků je odvozen celkový počet vozidel, který je potřeba k jejich obsloužení. Počet těchto vozidel je roven m. Vozidel je k dispozici nekonečný počet a kapacita každého vozidla je k. V modelu jsou použity dvě proměnné yiv a xijv. Proměnná xijv je binární a nabývá hodnoty jedna, když vozidlo v jede mezi zákazníky i a j, jinak má hodnotu nula. Naproti tomu proměnná yiv je pouze nezáporná a vyjadřuje množství zboží naložené ve vozidle v a doručené zákazníkovi i. Účelová funkce (2.45) minimalizuje celkové ujeté vzdálenosti všemi vozidly či celkové náklady na přejezdy mezi zákazníky. Je to odvislé od toho co vyjadřuje koeficient cij, jestli vzdálenosti nebo cenové náklady. Podmínka (2.46) zajišťuje, že každý zákazník je navštíven alespoň jednou. Podmínka (2.47) vyjadřuje, že pokud dostanu do vrcholu p, pak z něj také musím odjet. Podmínka (2.48) zamezuje tvorbě parciálních cyklů a S je podmnožinou V-{0}. Podmínka (2.49) vyjadřuje, že zboží je zákazníkovi i doručeno tehdy pokud je vozidlem v navštíven. Podmínka (2.50) zajišťuje, že bude splněn požadavek zákazníka i. Podmínka je konstruována tak, že suma množství zboží, které vezou vozidla v k zákazníkovi i, se rovná právě velikosti jeho požadavku. 33
Podmínka (2.51) zabraňuje překročení kapacitě vozidla k. Čili objem zboží naložený v autě v pro všechny zákazníky nesmí přesáhnout kapacitu vozu. Podmínka (2.52) zaručuje, že proměnná xijv je binární. Osmá podmínka (2.53), pak zajišťuje nezápornost proměnné yiv. Tento model předpokládá, že požadavek každého zákazníka je menší než kapacita vozidla, který je k dispozici. Což v naší řešené úloze neplatí. V naší úloze je často potřeba více aut s jejich celou kapacitou, aby obsloužily jednoho zákazníka. Autoři předpokládají počet aut m, kdy jejich kapacita se rovná celkovému požadavku všech zákazníků. Toto v našem příkladě nemusí platit, neboť se může stát, že bude výhodnější poslat dva menší nákladní automobily ne úplně plné, protože vypravení jednoho velkého s přejezdem by se z finančních důvodů vůbec nevyplatilo. Čili v naší řešené úloze musí být k dispozici dostatečně velký počet všech typů aut. Další důvody proč tento model není vhodný pro naši úlohu, jsou stejné či obdobné, jako u předešlého modelu. Např.: pořadí vykládky, podmínky pro jednotlivé druhy nákladních automobilů, které jsou k dispozici nebo podmínky pro jednotlivé sektory vozu.
2.2.3
Model 3 (podle [6])
Autoři v článku [6] představují málo vídaný typ Rozvozní úlohy, která obsahuje i rozdělení vozidla na jednotlivé části. Tento typ přepravy se často objevuje v petrochemickém či potravinářském průmyslu. Tato úloha řeší problém přepravy nehomogenních produktů, kterým je bezesporu přeprava benzínu a nafty, protože tyto dvě pohonné hmoty nelze přepravovat společně v jedné nádobě. Ale pokud bychom měli vůz rozdělený do sektorů, už je lze přepravovat společně v jedné cisterně. Obdobně je tomu například i s přepravou jídla, kdy je potřeba některé potraviny převážet v chladu jiné zase v suchu. V matematickém modelu pro Rozvozní problém s rozdělením vozidla na jednotlivé části (Vehicle routing with compartments = VRPC) jde o přiřazení jednotlivých objednávek do příslušných nákladních prostorů vozidel a všechny objednávky jsou každému vozidlu přiřazeny po částech. Tento způsob pak stanovuje trasu, kterou má dané vozidlo jet a jaké zákazníky, tak obsloužit. Všechny trasy začínají a končí v depu. Následný matematický model by měl řešit úlohy, které se nezabývají řešením rozvozu pohonných hmot.
34
Minimalizovat z cost ij bijv
(2.54)
vV iL jL
za podmínek
b0 jv 1, v V ,
(2.55)
jLc
bikv bkjv , v V , k L, iL
jL
(2.56) uiv u jv L bijv Lc , v V , i L, j Lc
(2.57)
ul0v 1, v V ,
(2.58)
quantity (o) xovc compCapa(c), v V , c C
(2.59)
quantity (o) xovc vehCapa, v V
(2.60)
xovc 1, o O
(2.61)
oO
oO cC
vV cC
xovc O bijv , v V , j Lc
(2.62)
O y pvc , p P, v V , c C
(2.63)
oordCust ( j ) cC
xovc oord Pr od ( p )
iL
y pvc 0, ( p, c) IncProdComp, v V
(2.64)
y pvc yqvc 1, ( p, q) IncProd , v V , c C
(2.65)
bijv 0,1, i, j L, v V
(2.66)
uiv 1,..., L , i L, v V
(2.67)
xovc 0,1, o O, v V , c C
(2.68)
y pvc 0,1, p P, v V , c C
(2.69)
K dispozici máme pevný počet vozidel V, každé vozidlo má C jednotlivých nákladních prostorů. Počet produktů je P, počet objednávek je označen jako O a cílových míst je celkem L. Všechny vozy mají stejnou kapacitu vehCapa. Jednotlivé nákladní prostory pak mají kapacitu o velikosti compCapa(c). Dále předpokládají symetrickou vzdáleností matici. 35
Depo je v tom případě opět označeno, jako L= 0 místo, které je potřeba obsloužit je definováno Lc = L - {0}. V jednom místě, pak může být i více objednávek a pro ně tedy platí o ∈ O, customer(o) ∈ Lc, definuje místo, kam je zakázka určena, product(o) ∈ P určuje poptávku zákazníka po produktu o velikosti quantity(o). Zákazník může dostat tedy několik dodávek z různých objednávek. Předpokládá se tedy, že každý zákazník l ∈ Lc, má alespoň jednu objednávku na každý produkt p ∈ P. A dodávka alespoň jedné objednávky nesmí být rozdělena. Dále je v modelu zaveden pojem nekompatibilní produkt, jenž je definovaný takto IncPrd ⊂ P X P, např.: (p,q) ∈ IncPrd, kde nestejnorodé produkty nemohou být přepravovány ve společném nákladním prostoru. Nekompatibilita mezi produktem a nákladní prostorem je definována jako IncPrdComp ⊂ P X C, kde (p,c) ∈ IncPrdComp, což znamená, že produkt p nemůže být přepravována v prostoru c. Indexy i a j slouží k označení míst. Index v vyjadřuje konkrétní automobil a index c, pak určuje nákladní prostor ve vozidle. Index o jsou značeny jednotlivé objednávky zákazníků. Proměnná bijv je binární proměnnou a hodnoty jedna nabývá v případě, že vozidlo v jede z místa i do místa j, jinak nabývá hodnoty nula. Přirozené proměnné uiv a ujv zamezují vzniku parciálních cyklů. Binární proměnná xovc vyjadřuje, že objednávka o je vezena ve vozidle v a je uložena v nákladním prostoru c, pokud toto platí nabývá hodnoty jedna jinak je proměnná rovna nule. Bivalentní proměnná ypvc nabývá hodnoty jedna, pokud produkt p je naložený v nákladním prostoru c vozidla v, jinak nabývá hodnoty nula. Koeficient costij vyjadřuje náklady na dopravu z místa i do místa j. Koeficient quantity(o), vyjadřuje velikost objednávky o. Účelová funkce (2.54) minimalizuje celkové přepravní náklady na rozvoz všech objednávek pomocí vozidel s rozděleným nákladním prostorem na jednotlivé nákladní prostory. První omezující podmínka (2.55) zajišťuje, že každé vozidlo v vyjede z depa nejvýše jednou. Podmínka (2.56) znamená, že pokud vozidlo přijelo do místa k, musí také z místa k odjet. Podmínka (2.57) slouží k zamezení vzniku parciálních cyklů. Omezující podmínka (2.58) zajišťuje, aby depo bylo vždy výchozím místem pro všechna vozidla.
36
Podmínka (2.59) slouží k tomu, aby objednávka o naložená ve vozidle v, přesněji v jeho úložném prostoru c nepřekročila kapacitu tohoto nákladového prostoru. Obdobný význam má i omezující podmínka (2.60), která zajišťuje, aby objem všech naložených objednávek ve všech nákladních prostorech c ve vozidle v, nepřesáhl kapacitu toho daného vozidla. Omezující podmínka (2.61) vyjadřuje, že každá objednávka musí být přiřazena právě jednomu nákladovému prostoru ve vozidle. Podmínka (2.62) zajišťuje, aby byl navštíven zákazník j vozidlem v, pokud je v tomto vozidle pro nějaká objednávka o naložená. Omezující podmínka (2.63) vyjadřuje, zda produkt p je přiřazen nákladovému prostoru c ve vozidle v. Podmínka (2.64) zařizuje, aby se do nákladového prostoru c vozidla v nenaložil produkt p, který do tohoto nákladového prostoru nesmí být naložen. Omezující podmínka (2.65) zajišťuje, aby nebyly spolu naloženy do stejného nákladového prostoru vozidla dva nekompatibilní produkty. Podmínka (2.66) zaručuje, že proměnná bijv je binární proměnnou. Třináctá podmínka (2.67) říká, že proměnná uiv je přirozenou proměnnou. Podmínky (2.68) a (2.69) zajišťují, že proměnné xovc a ypvc jsou bivalentní . Tento matematický model je formulován tak, aby v každém nákladním prostoru vozidla byla pouze jedna objednávka, což u naší úlohy by bylo nežádoucí. To si ostatně můžeme demonstrovat na příkladě. Dejme tomu, že budeme mít nákladní automobil, který musí obsloužit tři zákazníky. K této obsluze máme k dispozici nákladní vůz a jeho nákladní prostor rozdělíme na dvě symetrické části levou a pravou. Celková ložná délka nákladního prostoru vozidla je osm metrů. Třem zákazníků máme dodat tři palety s izolačními panely, délky palet jsou tři, pět a sedm metrů. Je tedy evidentní, že dvě objednávky by se nám vešly do jedné části, ale při aplikaci tohoto modelu bychom museli použít více než jedno vozidlo anebo vozidlo s větší kapacitou, které má však větší přejezdové náklady. V našem příkladě nemusíme řešit, zda balíky mohou být spolu naloženy ve stejném nákladovém prostoru nebo ne. A to i přesto, když se jedná o jiný typ produktu, protože tato podmínka je irelevantní, neboť i v jednom balíku může být více typů sendvičových izolačních panelů. Mimo to v jedné polovině vozidla můžeme vést jeden balík stěnových panelů a jeden střešních, pokud by to bylo výhodné.
37
Dále autoři předpokládají jeden typ vozidla a my jich máme více, ale to je stejný rozdíl jako u předchozích modelů. Máme sice stejně jako autoři nehomogenní produkt (balíky různých délek), ale všechny tyto balíky můžeme dávat bez problému spolu do jedné části nákladového prostu. Tento matematický model neumožňuje, aby jednotlivé objednávky byly dodány více vozidly, což u naší úlohy je potřeba.
2.3 Matematický model pro optimalizaci expedice sendvičových izolačních panelů pro společnost Kingspan, a.s. Nyní si ukáže matematický model sestavený přímo pro naši řešenou úlohu. Model sice obsahuje drobná zjednodušení oproti skutečnosti, ale ty nemají vliv na logickou správnost a slouží pouze k tomu, aby zjednodušily výpočet ukázkového příkladu. Model nepředpokládá symetrickou vzdálenostní matici. Aby orientace v zapsaném modelu byla co možná nejsnazší jsou všechny sumace vyjádřeny pomocí množin či podmnožin, které jsou pojmenovány podle prvního či prvních dvou písmen příslušeného prvku. Indexy jsou pak značeny podle příslušné množiny. První použitou množinou je množina A, která obsahuje počet typů aut. V našem případě auty rozumíme nákladní vozy. Z množiny A jsou pak odvozeny čtyři podmnožiny AS, AN, AT a AP. Podmnožina AN (AN ⊂ A), znamená auta, která jsou definována, jako nadrozměrný vůz. Nadrozměrným se rozumí vůz, který může převážet panel dlouhý až 22 metrů. V našem případě do této podmnožiny spadají dva typy vozů. Podmnožina AS (AS ⊂ A) obsahuje v naší úloze tři typy standardních vozů. Tyto typy nákladních vozů mají různé délky a lze u nich naložit paletu, která bude délku vozu překračovat maximálně o půl metru. Ve třetí kapitole je pak uveden popis, jaké jsou délky vozů a jaký je u nich povolený přesah, který je už zakomponován do datového vstupu pro zjednodušení modelu. Poslední dva typy vozů z množiny A tvoří dohromady ve skutečnosti jeden nákladní automobil. Jedná se o nákladní automobil s vlekem. Tahač s nákladním prostorem tvoří podmnožinu AT (AT ⊂ A) a přívěs tvoří podmnožinu AP (AP ⊂ A). Mezi množinou AT a AP existuje vztah, že pokud je k určitému zákazníkovi vypraven tahač dané instance, je k němu přiřazen i přívěs s nulovými náklady na přejezd a i nulovými náklady k prvnímu zákazníkovi. Tento nákladní vůz byl rozdělen na dva vozy z důvodu zjednodušení podmínek, která pracují s naložením panelů do jednotlivých sektorů. Místo abychom měli jeden typ vozu s dvojnásobným počtem sektorů, máme o jeden typ vozu více a všechny typy nákladních automobilů mají stejný počet sektorů, kam lze naložit panely. Více o definování a chápání sektoru ve vozech bude popsáno v souvislosti s množinou S. Všechny tyto podmnožiny jsme
38
definovali, protože pro některé typy nákladních automobilů je potřeba zavést speciální podmínky, které jsou pro ostatní druhy vozů zbytečné. Další množinou je množina I, která představuje počet instancí od každého typu vozidla. Tato hodnota je v našem případě pro všechny druhy vozidel stejná. Počet instancí je zvolen dostatečně velký tak, aby se daly případně všechny balíky s izolačními panely odvést případně pouze jedním typem vozidla, pokud by toto řešení bylo optimální. Pokud bychom chtěli tedy mluvit o konkrétním voze daného typu, zavedli bychom pro něj odvozenou množinu DV (AxI). Označení DV znamená daný vůz. V našem příkladě lze chápat pod pojmem panel a paleta popřípadě balík totožnou věc, neboť parametry palety (balíku) se odvíjejí od nejdelšího panelu v ní. Šířka všech panelů je stejná. Tloušťka panelů je sice různá, ale pokud se dají sendvičové izolační panely do balíku, vždy vytvoří přibližně stejně vysoký balík asi 1,25 m. Jediný rozměr, s kterým budeme tedy pracovat, je délka palety. Jelikož délka balíku je spojitá veličina je třeba tyto délky kategorizovat, aby se s nimi lépe pracovalo. V našem případě jsme všechny délky rozdělily do intervalů po 0,1 metru. Tyto standardizované délky nám pak tvoří typy palet. Typy palet pak označujeme množinou P. Množinu zákazníků, ke kterým je třeba doručit balíky s izolačními panely, značíme jako Z. Pokud bychom měli doručit dvě zakázky do stejného místa, budeme chápat toto místo, jako dva různé zákazníky. Minimalizovat
z czz 'a xzz 'ai
(2.70)
zZ z 'Z aA iI
za podmínek
y pzais požadavekpz , p P, z Z
(2.71)
y pzais d p kapacitaa , a A, i I , s 1
(2.72)
y pzais 1, a AN , i I , s 1
(2.73)
y pzais d p y pzais 'd p , a AN , i I , s 1, s' 2
(2.74)
xzz 'ai xzz 'a 'i , z Z , z' Z , a AT , a' AP, i I
(2.75)
y pzais M xz 'zai , z Z , a A, i I , s S
(2.76)
aA iI sS
zZ pP
zZ pP
zZ pP
pP
zZ pP
z 'Z
39
xzz 'ai xz 'zai , z Z , a A, i I
(2.77)
u zai 1 M (1 xzz 'ai ) u z 'ai , a A, i I , z Z , z' 2,3,...
(2.78)
u zai M (1 y pzais ) u z 'ai , a AN , i I , z Z , z' Z , s 1
(2.79)
xzz 'ai 0,1, z Z , z' Z , a A, i I
(2.80)
y pzais Z 0 , p P, z Z , a A, i I , s S
(2.81)
u zai Z 0 , z Z , a A, i I
(2.82)
z 'Z
z 'Z
pP
U každého typu vozidla můžeme rozdělit nákladový prostor na jednotlivé sektory. Těmito sektory rozumíme horní a dolní. V našem řešeném příkladě představuje sektory v každém daném voze (množině DV) množina S. Pokud bychom chtěli tedy mluvit o konkrétním sektoru v konkrétním voze daného typu, zavedli bychom pro něj odvozenou množinu SV (DVxS nebo AxIxS). Označení SV znamená sektor vozu. Výraz M lze definovat, jako libovolné dostatečně velké číslo, které nám zajistí platnost podmínky, pokud určitá proměnná nabývá dané hodnoty. Po definování množin přejdeme k vysvětlení významu jednotlivých proměnných, koeficientů a hodnot pravých stran, které jsou v našem vytvořeném matematickém modelu použity. V našem matematickém modelu využíváme dva typy koeficientů. Prvním je cenový koeficient czz’a, který označuje cenu přejezdu od zákazníka z k zákazníkovi z’ typem nákladního vozu a. Tato hodnota koeficientu platí pro všechny instance i daného nákladního vozu. Dalším koeficient v našem vytvořeném matematickém modelu je koeficient dp, jenž představuje délku palety, která je odvozena od nejdelšího sendvičového izolačního panelu zabaleného v ní. Dále do našeho matematického modelu vstupují dvě definované hodnoty pravých stran. První hodnotou pravé strany je požadavekpz. Tato hodnota udává, kolik zákazník z požaduje palet p. Druhou definovanou hodnotou je kapacitaa, která představuje kapacitu daného typu nákladního auta. Kapacitou rozumí maximální ložnou délku dolního sektoru v autě a s přičtením maximálně možného přesahu nákladu pokud je u daného typu vozidla povolen.
40
V naformulovaném matematickém modelu se používají tři proměnné. Dvě jsou celočíselné a jedna je binární. První proměnnou v našem vytvořeném matematickém modelu je proměnná ypzais. Tato proměnná je celočíselná a udává kolik palet typu p (jak jsme již dříve popsali p je kategorie délky balíku) pro zákazníka z se nachází v daném typu nákladního auta a a jeho příslušné instanci i a v jakém konkrétním sektoru s v daném voze. Další užívanou proměnnou je binární proměnná xzz’ai, která vyjadřuje, zda daný vůz (nákladní automobil typu a a instance i) pojede od zákazníka z k zákazníkovi z’. Poslední užívanou proměnnou v našem matematickém modelu je pomocná proměnná uzai, která zamezuje vzniku parciálních cyklů. Nyní můžeme přejít k vysvětlení jednotlivých podmínek našeho matematického modelu a účelové funkce. Účelová funkce (2.70) se snaží minimalizovat celkové náklady, které stojí rozvoz všech kusů palet ke všem zákazníkům. První podmínka (2.71) nám říká, že pokud sečteme proměnnou ypzais pro každého zákazníka z a typ palety p přes všechny nákladní automobily typu a, jejich příslušné instance i a jejich sektory s všichni zákazníci z dostanou minimálně všechny palety p, které požadují. Velikost požadavku zákazníka z na příslušný typ palety p je pak vyjádřen hodnotou požadavekpz. Podmínka (2.72) zajišťuje, aby v každém typu vozidla a, instanci i a prvním sektoru s = 1 (dolní sektor nákladového prostoru) nebyly naloženy balíky, které by v součtu délek překračovaly kapacitu kapacitaa příslušného typu nákladního vozu a. Podmínka funguje tak, že se sčítá proměnná ypzais vynásobená příslušnou délkou balíku dp pro typ palety p přes všechny zákazníky z a palety typu p, které jsou naloženy právě v daném voze v jeho dolním sektoru. Podmínka (2.73) platí pouze pro typy aut a ∈ AN, tedy pouze pro nadrozměrné nákladní vozy a jejich příslušné instance i. Podmínka nám říká, že v dolním sektoru s = 1 u nadrozměrného nákladního automobilu může být pouze jedna paleta p. Aby se do nadrozměrného vozu nedostaly krátké palety, které by se vešly i do menších nákladních aut hlídá účelová funkce, která toto řešení vyhodnotí jako příliš nákladné. Tato podmínka je zavedena z důvodu, že nadrozměrný nákladní automobil má stejné parametry, jako jeden z běžných typů nákladních automobilů, ale umožňuje díky své konstrukci přepravovat předměty výrazně delší než je délka jeho nákladového prostoru a proto byla nadrozměrným vozidlům stanovena kapacita délky nákladu 22 metrů. Pro nadrozměrný nákladní automobil pak logicky plyne podmínka, že ve spodním sektoru vozu může být jeden balík, který je delší než 14 metrů.
41
Podmínka (2.74) zajišťuje, aby součet délek všech naložených palet p v dolním sektoru daného vozu byla delší nebo rovna v součtu délek všech naložených palet p v horním sektoru. Tato podmínka je logická, protože byť je auto rozděleno na dolní a horní sektor balíky z horního sektoru jsou postaveny na balících umístěných v dolním sektoru. A pak je tedy jasné, že v dolním sektoru nemůže být jedna dvoumetrová paleta a v horním jeden sedmimetrový. Tato podmínka je obdobou druhé podmínky, která platila pouze pro první sektor. Platí i pro nadrozměrné vozy a všechny jejich instance i a v tom druhém sektoru může být i více kusů balíků, jejichž suma délek dp nepřesáhne délku spodního panelu p. Podmínka (2.75) platí pro všechny a ∈ AT a a’ ∈ AP a zajišťuje, aby se ke každému tahači dané instance i přiřadil jeho návěs, který pojede stejnou trasu, tím se dostaneme na skutečnou kapacitu daného nákladního automobilu. Návěs má vždy nulový cenový koeficient, protože skutečné náklady vozu na cestu od zákazníka z k zákazníkovi z’ jsou vztaženy na tahač. Jak již bylo popsáno výše k rozdělení složeného nákladního na dvě části tahač a přívěs bylo provedeno, aby všechny vozy měly stejný počet sektorů a tím se ulehčilo psaní matematického modelu. Podmínka (2.76) ošetřuje to, že pokud vezu zákazníkovi z paletu p v sektoru daného vozu, pak k tomuto zákazníkovi také musím jet. Tato podmínka platí pro všechny typy nákladních vozů a jejich instance i a všechny sektory s v nich. Podmínka (2.77) zajišťuje, že pokud k zákazníkovi z s daným vozem přijedu musím také od něj odjed. Podmínka (2.78) slouží k vyloučení parciálních cyklů. Pokud typ vozu a instance i nejede k zákazníkovi z, tak proměnná uzai nabývá hodnoty nula. Podmínka (2.79) zajišťuje to, že pokud se zákazníkovi z veze paleta typu p v sektoru s = 1 v instanci i v nákladním vozidle a ∈ AN, tak tento zákazník musí být na trase daného vozu až poslední. Podmínky (2.80), (2.81) a (2.82) definují, jakého typu jsou námi používané proměnné, které jsme si definovali již výše pro náš vytvořený matematický model.
42
2.4 Implementace řešení v SW Lingo V následující kapitole je uvedený přepis matematického modelu do SW Lingo, v kterém byly řešeny výpočetní experimenty. model: sets: paleta/@ole('diplomka_vs_final.xlsx','paleta')/:delka; zakaznik/@ole('diplomka_vs_final.xlsx','zakaznik')/:; sektor/1..2/:; auto/avia,solo,set_truck,mega_standard,flat_bed,oversized,naves/:kap_pa; nadrozmer(auto)/flat_bed,oversized/; bezne(auto)/avia,solo,mega_standard/; tahac(auto)/set_truck/; prives(auto)/naves/; int/1..4/:; danyvuz(auto,int):; danyvuznadrozmer(nadrozmer,int):; sektorvozu(auto,int,sektor):; matice_ZZA(zakaznik,zakaznik,auto):c; matice_ZZDV(zakaznik,zakaznik,danyvuz):x; matice_PZ(paleta,zakaznik): poz; matice_NS(nadrozmer,int,sektor):; matice_ZDV(zakaznik,danyvuz):u; matice_PZA(paleta,zakaznik,sektorvozu):y; endsets data: c = @ole('diplomka_vs_final.xlsx','naklady_auto'); kap_pa = @ole('diplomka_vs_final.xlsx','kapacita_auto'); poz = @ole('diplomka_vs_final.xlsx','pozadavek_zakaznik'); delka = @ole('diplomka_vs_final.xlsx','delka'); M=100; enddata [ucel_fce]
min=@sum(matice_ZZDV(z,z2,a,i):c(z,z2,a)*x(z,z2,a,i));
@for(zakaznik(z):@for(paleta(p):@sum(danyvuz(a,i):@sum(sektor(s): y(p,z,a,i,s)))>=poz(p,z))); @for(danyvuz(a,i):@sum(zakaznik(z):@sum(paleta(p):y(p,z,a,i,1)*delka(p))) <= kap_pa(a)); @for(danyvuznadrozmer(a,i):@sum(zakaznik(z):@sum(paleta(p):y(p,z,a,i,1))) <= 1); @for(danyvuz(a,i):@sum(zakaznik(z):@sum(paleta(p):y(p,z,a,i,1)*delka(p))) >=@sum(zakaznik(z):@sum(paleta(p): y(p,z,a,i,2)*delka(p)))); @for(zakaznik(z):@for(zakaznik(z2):@for(int(i):@sum(tahac(a):x(z,z2,a,i)) = @sum(prives(b): x(z,z2,b,i))))); @for(zakaznik(z):@for(sektorvozu(a,i,s):@sum(paleta(p):y(p,z,a,i,s)) <=M*@sum(zakaznik(z2):x(z2,z,a,i))));
43
@for(danyvuz(a,i):@for(zakaznik(z):@sum(zakaznik(z2):x(z,z2,a,i)) =@sum(zakaznik(z2):x(z2,z,a,i)))); @for(matice_ZZDV(z,z2,a,i)|z2#gt#1:u(z,a,i) + 1 - M*(1-x(z,z2,a,i)) <=u(z2,a,i)); @for(danyvuznadrozmer(a,i):@for(zakaznik(z):@for(zakaznik(z2):u(z,a,i) -M*(1-@sum(paleta(p): y(p,z2,a,i,1)))<= u(z2,a,i)))); @for(matice_PZA:@gin(y)); @for(matice_ZZDV:@bin(x)); @for(matice_ZDV:@gin(u)); data: @ole('diplomka_vs_final.xlsx','xko') = x; @ole('diplomka_vs_final.xlsx','yko') = y; @ole('diplomka_vs_final.xlsx','ucko') = u; @ole('diplomka_vs_final.xlsx','zko') = ucel_fce; @text()='TABLE_X'; @text()=@table(x); @text()='TABLE_Y'; @text()=@table(y); @text()='TABLE_U'; @text()=@table(u); enddata end
44
3 Výpočetní experimenty V této kapitole si ukážeme výpočetní experimenty. Uvedeme si zde datové vstupy pro každý experiment, jak je bylo třeba připravit a upravit. Dále si uvedeme výsledek ilustrativního příkladu a budeme se zabývat výpočetní efektivnosti námi řešené úlohy, kterou se zabývá tato práce.
3.1 Zadání a příprava vstupních dat Vstupem pro výpočetní část našeho příkladu bude sloužit několik tabulek. Některé už máme připravené, jiné bude nutné dopočítat. 3.1.1
Kapacita vozidla a počet instancí vozidla
Jak jsme již naznačili v druhé kapitole, máme k dispozici několik typů nákladních automobilů. Rozdíl mezi nimi spočívá v kapacitě nákladového prostoru, který je vyjádřen délkou ložné plochy nákladového prostoru daného typu vozu. Automobily mají samozřejmě i rozdílnou sazbou za ujetý kilometr. Všechny charakteristiky k typu vozidla plátí pro jeho všechny instance v předešlé kapitole. Jelikož je u třech druhů vozidel možný přesah až půlmetru, navýšíme touto hodnotou kapacitu těchto nákladních automobilů, abychom si nekomplikovali matematický model a nemuseli řešit, ke kterému typu vozidla lze přičíst povolený přesah. A mimo to u dvou typů vozidla není přesah vůbec možný z technického důvodu, protože se jedná o nákladní vůz s přívěsem. Tento typ nákladního vozu, jak jsme již popsali v podkapitole 2.3 je rozdělen na dva typy automobilů (tahač a přívěs). A u dvou nákladních automobilů, které mají charakter nadrozměrného vozu, je přesah dokonce vyžadován. Zde bychom si měli i ozřejmit, proč máme dva druhy nákladního vozidla typu nadrozměr, když oba mají stejnou možnou kapacitu nákladového prostoru a přitom mají rozdílnou cenu, která je účtována za jeden kilometr přejezdu. Důvod je prostý ve skutečnosti se jedná o jiné typy automobilů, jež se liší svými technickými parametry a samozřejmě tím pádem i spotřebou. Nadrozměrný nákladní automobil má stejné parametry, jako jeden z běžných typů nákladních automobilu. Umožňuje, ale díky konstrukci přepravovat předměty výrazně delší než je ložná plocha jeho nákladového prostoru. Pro nadrozměrný typ automobilu platí pravidlo, že spodní balík s izolačními panely v nákladovém prostoru musí být delší než 14 metrů. Z tohoto pravidla je patrné, že na tento typ vozu nelze naložit za sebou dva osmimetrové balíky. Pro lepší představu si zde uvedeme tabulku s parametry jednotlivých typů vozů.
45
Typ nákladního vozu
Skutečná délka Využitelná délka nákladového prostoru v nákladového prostoru v metrech metrech
small (avia) Solo set truck - tahač set truck - návěs standard/mega flat bed Oversized
6,5 7,5 7,5 7,5 13,6 13,6 13,6
7 8 7,5 7,5 14 22 22
Cena za jeden ujetý km v Kč
20 25 30 0 30 40 45
Tabulka 3-1
Od každého nákladního vozidla budeme mít k dispozici tři instance, což je dostatečný počet pro rozvoz všech požadavku zákazníků. 3.1.2
Požadavky zákazníků
Informace o požadavcích zákazníků byly získány z reportů od společnosti Kingspan, a.s. Původní informace obsahovala, kolik sendvičových izolačních panelů daného typu a určité délky je zabaleno v balíku. Pro naši úlohu nám stačí informace, jaký je nejdelší panel v paletě, protože ten určuje velikost balíku. Toto zjednodušení můžeme provést, neboť všechny panely, které se mají dovést k zákazníkovi, jsou již zabaleny v balících a to tak, že v balíku jsou pouze panely pro jednoho zákazníka. Avšak balíky je třeba ještě kategorizovat dle délky, abychom neměli zbytečně příliš mnoho typů balíku a ulehčili si tím výpočetní experiment. Kategorizaci provedeme jednoduchým způsobem, délku balíku zaokrouhlíme klasickým způsobem na metry s jedním desetinným místem a tím například ze dvou kategorií 7,44 m a 7,42 m dostaneme pouze jednu kategorii 7,4 m. Pro náš výpočetní experiment byli vybráni pouze tři zákazníci, kterým se má doručit celkem 12 palet. Celkový počet palet je složen ze 4 různých typů (délek) palet. Čtvrté město Hradec Králové (HK) označuje výchozí depo a požadavky v depu jsou rovny nule pro všechny typy balíků. Takto malý rozsah úlohy byl zvolen z technických důvodů. Těmito důvody jsou vybavenost HW a SW, které si podrobněji rozebereme v podkapitole 3.3. Tabulka 3-2 ukazuje kolik balíků, jaké délky je třeba doručit do daného města ve Spolkové republice Německo.
46
Délka palety
HK
Aglasterhausen
v metrech 4,8 5 6,4 16
0 0 0 0
0 1 0 0
Ahlbeck
Ahrensburg
0 1 1 1
5 0 0 0
Tabulka 3-2
3.1.3
Nákladová matice
Získání výsledné nákladové matice je poněkud složitější proces než získání předešlých vstupů. Jak jsme popsali v první kapitole, přesněji v podkapitole 1.4, získání vzdálenostní matice bylo provedeno z aplikace The Google Distance Matrix API. Abychom získali z této vzdálenostní matice nákladovou matici, musíme si nejdřív uvědomit, počítá celkovou cenu za jeden nákladní automobil. Cena k prvnímu zákazníkovi je určena fixně dle oblasti (prvního dvojčíslí PSČ), kde se zákazník nachází, tato fixní sazba platí pro všechny typy nákladních vozů. Cena účtována za návštěvu každého dalšího zákazníka má dvě složky fixní 1000 Kč a variabilní, která je odvislá podle ujetých kilometrů daným typem nákladního vozu. Pokud by bylo více zákazníku v jednom městě, je jim účtována pouze fixní složka. Nákladovou matici stačí spočítat pouze pro každý druh nákladního automobilu a není třeba ji replikovat pro každou instanci daného typu vozu. Tabulka ukazuje, jaké jsou náklady na dopravu mezi depem (HK) a cílovými městy (první zákazník) a mezi jednotlivými zákazníky tyto náklady na přepravu jsou rozděleny podle jednotlivých druhů nákladních vozidel, které máme k dispozici. Jak je patrné z tabulky náklady na druh vozidla „set truck – návěs“ jsou náklady nulové, protože už jsou započítaný u typu vozidla „set truck – tahač“. Jak jsme již zmínili výše, obě vozidla tvoří ve skutečnosti jeden celek a byly rozděleny pouze z důvodu usnadnění formulace matematického modelu. Ceny uvedené v tabulce 3-3 jsou Kč. Z města
Do města
small
Solo
set set standard/ truck - truck mega tahač návěs
0 19 987 19 374 20 549 0
0 19 987 19 374 20 549 0
(avia) HK HK HK HK Aglasterhausen
HK 0 Aglasterhausen 19 987 Ahlbeck 19 374 Ahrensburg 20 549 HK 0
47
0 0 0 0 0
flat bed
0 0 19 987 19 987 19 374 19 374 20 549 20 549 0 0
Oversized
0 19 987 19 374 20 549 0
Aglasterhausen Aglasterhausen Aglasterhausen Ahlbeck Ahlbeck Ahlbeck Ahlbeck Ahrensburg Ahrensburg Ahrensburg Ahrensburg
Aglasterhausen Ahlbeck Ahrensburg HK Aglasterhausen Ahlbeck Ahrensburg HK Aglasterhausen Ahlbeck Ahrensburg
0 18 772 13 850 0 18 789 0 7 383 0 13 871 7 379 0
0 23 215 17 062 0 23 236 0 8 979 0 17 088 8 974 0
0 27 658 20 274 0 27 683 0 10 575 0 20 306 10 569 0
0 0 0 0 0 0 0 0 0 0 0
0 27 658 20 274 0 27 683 0 10 575 0 20 306 10 569 0
0 36 544 26 699 0 36 577 0 13 766 0 26 741 13 759 0
0 40 987 29 911 0 41 024 0 15 362 0 29 959 15 353 0
Tabulka 3-3
Tabulka 3-3 bude pro reálné rozsahy úloh nabývat velkých rozměrů i když se nemusí sestavovat pro každou instanci každého druhu vozidla. Pro její sestavení je důležité udržet provázanost informace o PSČ, které náleží danému městu, aby šla přiřadit fixní sazba, pokud se město nachází jako první na vytvořené trase pro daný vůz. Pokud bychom měli v úloze navštívit dva a více různých zákazníků v jednom městě, přistupovali bychom k nim, jako by se jednalo o dvě odlišná města a k zákazníkům bychom začali přidávat číslovky pro rozlišení. Hodnoty pro přejezdy k dalším městům by měly totožné stejně tak, jako náklady za příjezd z depa. A náklady na přejezd mezi sebou by byly pouze ve výši fixní sazby za další vykládku. Nevýhoda způsobu vyčíslování vzdáleností matice spočívá v tom, že se zjišťuje vzdálenost pro konkrétní město nikoliv pro přesnou adresu, kde se nachází zákazník. Tato nevýhoda se projeví u více zákazníků v jednom velkém městě, kdy každý může být na druhém konci města a přejezd z jednoho konce na druhý by znamenal přejezd třeba 60 km. Nevýhoda spočívá v tom, že pokud bychom měli s jedním vozem obsloužit dva zákazníky v témže městě a vzdálenost přejezdu mezi nimi by byla 60 km a dále obsloužit třetího zákazníka, ke kterému je to z jednoho konce blíže než z druhého, budeme obě místa považovat za stejně výhodná co pořadí na trase. S tímto se však nedá nic dělat, protože vstupem byl pouze údaj o městě, kde se zákazník nachází nikoliv o přesné adrese a ne vždy je více zákazníků v jednom a tom samém městě. 3.1.4
Upravené vstupy
Tento ukázkový příklad nám neukazuje funkčnost podmínky pro nadrozměrné vozy, že nejdelší naložený balík musí být vyložený, jako poslední. Proto si upravíme zadaní. Tato podmínka je pro nadrozměrný vůz velice důležitá, protože zajišťuje správné pořadí zákazníků na trase. Zadání nebude odpovídat realitě, ale bude sloužit k dokázání funkčnosti modelu. Upravíme si zadání tak abychom, donutili na trasu vyjet nadrozměrný vůz a umožnili mu
48
přejezd k dalšímu zákazníkovi. Umožnění přejezdu je myšleno to, aby místo přejezdu nebyl na trasu vyslán menší levnější nákladní automobil. Vezměme si tabulku 3-3, kde jsou uvedené ceny přesunů mezi městy a upravme náklady na přejezd mezi městy Ahrensburg a Ahlbeck, tak aby náklady na přejezd mezi městy byly stejné a dostatečně nízké na to, aby mohl být povolený přejezd mezi těmito městy. Povoleným přejezdem je myšleno, že přejezd je výhodnější než zapojení malého nákladního vozu. Nebudeme uvažovat ani o fixní sazbě za další zastávku. Upravené náklady v tabulce 3-4 vyznačíme tučně a kurzívou. Z města
Do města
small
Solo
set set standard/ truck - truck mega tahač návěs
0 19 987 19 374 20 549 0 0 23 215 17 062 0 23 236 0 8 979 0 17 088 8 974 0
0 19 987 19 374 20 549 0 0 27 658 20 274 0 27 683 0 10 575 0 20 306 10 569 0
(avia) HK HK HK HK Aglasterhausen Aglasterhausen Aglasterhausen Aglasterhausen Ahlbeck Ahlbeck Ahlbeck Ahlbeck Ahrensburg Ahrensburg Ahrensburg Ahrensburg
HK Aglasterhausen Ahlbeck Ahrensburg HK Aglasterhausen Ahlbeck Ahrensburg HK Aglasterhausen Ahlbeck Ahrensburg HK Aglasterhausen Ahlbeck Ahrensburg
0 19 987 19 374 20 549 0 0 18 772 13 850 0 18 789 0 7 383 0 13 871 7 379 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 19 987 19 374 20 549 0 0 27 658 20 274 0 27 683 0 10 575 0 20 306 10 569 0
flat bed
0 19 987 19 374 20 549 0 0 36 544 26 699 0 36 577 0 2 0 26 741 2 0
Oversized
0 19 987 19 374 20 549 0 0 40 987 29 911 0 41 024 0 2 0 29 959 2 0
Tabulka 3-4
Dále si stanovme nové požadavky zákazníku, které jsou uvedeny v tabulce 3-2, aby mělo vůbec smysl vypravit nadrozměrný nákladní automobil na trasu mezi městy Ahrensburg a Ahlbeck. Délka palety
HK
Aglasterhausen
v metrech 4,8 5 6,4 16
0 0 0 0
0 0 0 1 Tabulka 3-5
49
Ahlbeck 0 0 0 1
Ahrensburg 3 0 0 0
3.2 Výsledek pro ilustrativní příklad Pro naší řešenou ilustrativní úlohu jsme měli celkem k dispozici 18 nákladních vozidel šesti různých typů odvozených od jejich kapacity (délky nákladního prostoru) a ceny za jeden ujetý kilometr. Toto platí i pro upravené zadání ukázkového příkladu. 3.2.1
Výsledek původního zadání ukázkového příkladu
Na rozvoz všech požadavků, který činil 12 balíků, budeme potřebovat celkem tři nákladní automobily, jak je vidět z tabulky 3-4. A to konkrétně jednu Avii, jeden vůz typu oversized a jedno vozidlo standard/mega. Celkové náklady (hodnota účelové funkce) na rozvod všech objednávek jsou 73 759.04 Kč. Z města
Do města
Typ vozu
1
2
3
HK
AGLASTERHAUSEN
AVIA
1
0
0
AGLASTERHAUSEN AHRENSBURG HK AHLBECK HK AHRENSBURG
AHRENSBURG HK AHLBECK HK AHRENSBURG HK
AVIA AVIA OVERSIZED OVERSIZED MEGA_STANDARD MEGA_STANDARD
1 1 0 0 0 0
0 0 0 0 0 0
0 0 1 1 1 1
Tabulka 3-6
Vozidlo typu oversized pojede pouze k zákazníkovi do Ahlbecku, kam mu poveze celou jeho objednávku a poté se vrátí do depa. Nákladní automobil typu standard/mega poveze část zakázky k zákazníkovi do Ahrensburgu a poté se vrátí zpět do výchozího místa. Poslední vypravený vůz, kterým je Avia, nejdříve pojede k zákazníkovi do Aglasterhausenu, kde vyloží celou zásilku a poté přejede k zákazníkovi do Ahrensburgu, kde doručí zbytek jeho objednávky, kterou nedoručilo vozidlo standard/mega. Obrázek 3-1: Schéma rozvozu č. 1:
M2 Depo
M3 M1
50
Depo – Hradec Králové M1 – Ahlbeck M2 – Aglasterhausen M3 – Ahrensburg Rozmístění jednotlivých palet pro každého zákazníka v jednotlivých nákladních vozech je pak následující: Délka palety Zákazník v metrech
Typ vozu
Instance Sektor 1 Sektor 2
4,8 AHRENSBURG
AVIA MEGA_STANDARD 4,8 AHRENSBURG 5 AGLASTERHAUSEN AVIA OVERSIZED 5 AHLBECK OVERSIZED 6,4 AHLBECK OVERSIZED 16 AHLBECK
1 3 1 3 3 3
0 2 1 0 0 1
1 2 0 1 1 0
Tabulka 3-7
Výstup ze SW Lingo s hodnotou o účelové funkce a proměnných x a y je uvedený v příloze č.1. 3.2.2
Výsledek upraveného zadání ukázkového příkladu Z města
Do města
Typ vozu
HK AGLASTERHAUSEN HK AHLBECK AHRENSBURG
AGLASTERHAUSEN HK AHLBECK AHRENSBURG HK
OVERSIZED OVERSIZED OVERSIZED OVERSIZED OVERSIZED
Tabulka 3-8
Obrázek 3-2: Schéma rozvozu č. 2:
M2 Depo
M3 M1
51
1 2 3 1 1 0 0 0
0 0 0 0 0
0 0 1 1 1
V tabulce 3-8 jsou uvedeny dvě výsledné trasy pro upravené zadání ukázkové úlohy, kdy je vypnutá podmínka (2.79) ve vytvořeném modelu pro tuto řešenou úlohu. Hodnota účelové funkce je 39 362.50 Kč. Z města HK AGLASTERHAUSEN HK AHRENSBURG AHLBECK
Do města
Typ vozu
AGLASTERHAUSEN HK AHRENSBURG AHLBECK HK
OVERSIZED OVERSIZED OVERSIZED OVERSIZED OVERSIZED
1 2 3 0 0 0 0 0
0 0 1 1 1
1 1 0 0 0
Tabulka 3-9 Obrázek 3-3: Schéma rozvozu č. 3:
M2 Depo
M3 M1
V tabulce 3-9 jsou pak uvedeny opět dvě výsledné trasy pro upravené zadání ukázkové úlohy, kdy je naopak zapnutá podmínka (2.79) vytvořeného modelu. Hodnota účelové funkce je v tom případu větší a je 40537.50 Kč. Tato hodnota je naprosto v pořádku, protože musí být dodržena podmínka, že se jako poslední vyloží paleta umístěná v dolním sektoru, která fyzicky zvětšuje kapacitu nadrozměrného vozu. Nákladní vůz typu Flat bed hodnotu účelové funkce nijak neovlivňuje, protože jede pouze k jednomu zákazníkovi a zpět do depa. A jak je patrné z tabulky 3-3 cena účtovaná k prvnímu zákazníkovi je pro všechny vozy stejná bez ohledu na jejich kapacitu či náklady na jeden ujetý kilometr.
3.3 Možnosti implementace pro úlohy reálného rozsahu Původní rozměr našeho ukázkového příkladu měl být větší a měl být řešen pomocí SW Gurobi instalovaného v SW MPL, který je vhodnější k výpočtu celočíselných úloh lineárního programování oproti SW Lingo.
52
Původně řešený ukázkový příklad měl za cíl nalézt optimální řešení pro rozvoz 40 balíků k sedmi zákazníkům ve Spolkové republice Německo, ale ani po několika pokusech se tento výpočet zdárně nezdařil. Tento neúspěch byl způsobem nedostatečnou vybavenosti počítače, na kterém se výpočetní experiment měl provádět. Tímto nedostatek byla nedostatečná kapacita operační paměti počítače. Proto tedy byl zvolen menší rozsah úlohy, jenž lze vypočítat i v SW Lingo, který není tak vhodný k výpočtu celočíselných úloh jako SW Gurobi. Rozhodnutí, které poměrně dost ovlivňuje dobu výpočtu, je vhodná volba počtu instancí vozidel, které budeme mít k dispozici. Pro výpočet je důležité mít k dispozici dostatečný počet vozidel od každého druhu vozidla, protože dopředu nevíme, zda bude vhodné vozit balíky pouze jedním typem nákladního automobilu, nebo rozvoz palet bude rovnoměrně rozložen do všech druhů nákladních vozidel. Jak jsme již zmínili dříve společnost Kingspan, a.s. si přepravce sjednává a tudíž nemusí řešit počet automobilů, které má k dispozici pro jednotlivé typy vozů. Uveďme si příklad, jak se doba výpočtu prodlužuje v závislosti na volbě počtu instancí, při použití SW Lingo. Máme zadání původní úlohy našeho ukázkového příkladu. Pokud zvolíme, že od každého druhu vozidla máme k dispozici pouze tři instance, tak se výpočtu optimálního řešení dočkáme asi za 5,5 minuty. Více o počtu iteracích v příloze č. 1. Pokud však zvolíme, že máme k dispozici každý druh nákladního automobilu čtyřikrát, pak až po devíti hodinách výpočtu dostaneme optimální řešení. Nejlepší nalezené celočíselné řešení, které je vypočteno asi po 10 minutách, má stejnou hodnotu jako účelová funkce, která by nám měla vyjít tedy 73 759 Kč. Problém tedy spočívá v procházení jednotlivých větví, kdy jsou postupně procházeny jednotlivé větve a jsou pomalu odřezávány, jak se výpočet zespoda blíží k hodnotě účelové funkce. Například větev, jejíž hodnota účelové funkce je 65 157,7 Kč, se počítala z devíti hodin výpočtu minimálně 8,5 hodiny. Právě díky zvýšení počtu instancí roste počet možných permutací umístění jednotlivých balíků a tím se prodlužuje čas výpočtu. Otázkou je, jak by si se změnou zadání poradil SW, který umí lépe řešit celočíselné úlohy lineárního programování. Bohužel v době změny vstupu (zvýšení počtu instancí) nebyl SW Gurobi z licenčních důvodů k dispozici.
53
Na obrazku 3-4 je konečné výpočetní okno ze SW Lingo pro ukázkový příklad, když máme k dispozici tři instance od každého typu vozidla. Na obrázku 3-5 je pak konečné výpočetní okno, když máme od každého vozu čtyři instance. Jak je vidět z obrázku počet výpočetních kroků a jednotlivých iterací se diametrálně liší.
Obrázek 3-4: Výpočetní SW Lingo okno č. 1
Obrázek 3-5: Výpočetní SW Lingo okno č. 2
Bylo by proto výhodné zajistit, aby SW dostával informaci, že pokud vyhodnotil nějakou kombinaci naložení jako neefektivní, její permutace budou též neefektivní a není důvod je počítat. Další možností je pro každý druh vozidla vytvořit speciální instanci tak, abychom mohli mít různý počet jednotlivých druhů vozidel. Tímto však bohužel dojde ke ztrátě obecnosti modelu. Počet typů vozidel by šel snížit za cenu snížení přesnosti výpočtu. Pokud bychom obě vozidla, která spadají do kategorie nadrozměrného vozu, zrušili a vytvořili pouze jeden nový nadrozměrný vůz, který by měl samozřejmě stejnou kapacitu a cenu přejezdu k prvnímu zákazníkovi, ale cena přejezdů k dalším zákazníkům by byla vyjádřena jako aritmetický průměr přejezdů vozidel oversized a flat_bed, snížili bychom tak celkový počet vozidel. Pokud bychom měli jeden druh vozu nadrozměr nemuseli bychom pak zkoumat, zda použít typ oversized či flat_bed na obsloužení dané trasy, ale rovnou by byl přiřazen jeden typ vozu, který bychom vytvořili.
54
Dva nadrozměrné vozy máme, protože oba nákladní automobily mají jiné parametry, jako je celkové přípustné zatížení a celkové přípustné zatížení na nápravu, případná výška nákladu a tak podobně. Proto je třeba obě vozidla rozlišovat, protože některé zakázky mohou být naloženy pouze na typ vozu oversized. V našem ukázkovém případě to však nebylo potřeba rozlišovat. Ani v datových vstupech nebyla informace, která by vyžadovala naložení konkrétní zakázky na oversized. Tímto zjednodušením bychom tedy dostali přibližný výsledek, který by bylo nutné ručně zkontrolovat, zda bude nutné použít dražší oversized nebo flat_bed.
55
Závěr Cílem této diplomové práce bylo optimalizovat logistické procesy ve společnosti Kingspan, a.s., pomocí metod operačního výzkumu a navrhnout systémové řešení daného problému. Po prostudování odborné literatury, která posloužila k pochopení různých přístupů k řešení rozvozních úloh s dělenou dodávkou, a formulaci základních podmínek pro tento typ úloh, byl naformulován vlastní funkční matematický model, pomocí kterého lze úlohu řešit. Obtížnost formulace modelu spočívala především v tom, že v uvažovaném problému (a) řešíme rozvoz nehomogenního produktu, (b) připouštíme možnost dělit objednávku do více dodávek a (c) existuje více druhů nákladních vozidel. Pro účely sběru dat byla vytvořena makra (viz. kapitola 1.4), kterými lze automaticky stahovat datové vstupy potřebné pro řešení úlohy z volně dostupných zdrojů na internetu. Tvorba těchto skriptů byla nezbytná pro možnou implementaci řešení do praxe tak, aby jej bylo možné aplikovat na úlohy reálného rozsahu. Navržená automatizace získávání datových vstupů výrazně snižuje časovou náročnost na získávání potřebných vstupních dat. Řešení daného problému pro reálný rozsah vstupů s sebou nese komplikaci v podobě výpočetní efektivnosti, jak nastiňuje kapitola 3.3, zabývají se výpočetní efektivností. Proto by bylo vhodné toto navrhované řešení rozšířit o heuristickou metodu, která by nám mohla pomoci výrazně zvýšit výpočetní efektivnost. Heuristická metoda by měla za cíl najít dobré přípustné řešení, které by sloužilo jako výchozí řešení pro výpočetní SW při hledání optimálního řešení. Tímto by došlo k rychlejšímu odřezávání jednotlivých neefektivních větví v typicky používaném algoritmu větvení a mezí. Navrhovaný způsob řešení problému popsaný v této práci, doplněný o heuristickou metodu pro nalezení dobrého výchozího řešení, by snad již mohl být vhodný pro řešení úloh reálného rozsahu. Pokud bychom chtěli dosahovat ještě lepší úrovně organizace logistického procesu, bylo by možné řešenou úlohu dále rozšířit o problém balení jednotlivých sendvičových izolačních panelů na palety. V současné době je tato činnost řešena pomocí algoritmu, který zohledňuje přípustnost jednotlivých sendvičových izolačních panelů v balíku. Avšak už neexistuje provázanost informací mezi balením jednotlivých panelů a informací o navržených trasách a schématech naložení jednotlivých vozů. Taková provázanost informací by mohla vést k jinému způsobu sdružování sendvičových izolačních panelů do balíku, který by byl též přípustný dle současných kritérií. Tyto palety by bylo možné rozvést koncovým zákazníkům jiným způsobem, který by znamenal lepší výsledné řešení úlohy, než jak ho dostáváme nyní.
56
Literatura [1]
LAGOVÁ, M. - JABLONSKÝ, J. Lineární modely. 1. vyd. Praha: Oeconomica, 2004. 287 s. ISBN 80-245-0816-8.
[2]
JABLONSKÝ, J. Programy pro matematické modelování. Praha: Oeconomica, ISBN 978-80-245-1178-8.
[3]
PELIKÁN, J. Diskrétní modely v operačním výzkumu. 1.vyd. Praha: Professional Publishing, 2001, 163 s. ISBN 80-864-1917-7.
[4]
WILCK IV, Joseph Hubert, M. G. SPERANZA, A. HERTZ, Michael PIESCHE, Franz ROTHLAUF a Ulrich VOGEL. A Construction Heuristic for the Split Delivery Vehicle Routing Problem. American Journal of Operations Research. 2012, vol. 02, issue 02, s. 153-162. DOI: 10.4236/ajor.2012.22018. Dostupné z: http://www.scirp.org/journal/PaperDownload.aspx?DOI=10.4236/ajor.2012.22018
[5]
ARCHETTI, C., M. G. SPERANZA, A. HERTZ, Michael PIESCHE, Franz ROTHLAUF a Ulrich VOGEL. A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem: applications, modelling and heuristics. Transportation Science. 2006, vol. 40, issue 1, s. 64-73. DOI: 10.1287/trsc.1040.0103. Dostupné z: http://pubsonline.informs.org/doi/abs/10.1287/trsc.1040.0103
[6]
DERIGS, Ulrich, Jens GOTTLIEB, Jochen KALKOFF, Michael PIESCHE, Franz ROTHLAUF a Ulrich VOGEL. Vehicle routing with compartments: applications, modelling and heuristics. OR Spectrum. 2011, vol. 33, issue 4, s. 885-914. DOI: 10.1007/s00291-010-0194-3. Dostupné z: http://link.springer.com/10.1007/s00291-0100194-3
[7]
DROR, Moshe, Gilbert LAPORTE, Pierre TRUDEAU, Michael PIESCHE, Franz ROTHLAUF a Ulrich VOGEL. Vehicle routing with split deliveries. Discrete Applied Mathematics. 1994, vol. 50, issue 3, s. 239-254. DOI: 10.1016/0166-218X(92)00172-I. Dostupné z: http://linkinghub.elsevier.com/retrieve/pii/0166218X9200172I
2007.
Internetové Zdroje a odkazy: [8]
Kingspan. KINGSPAN - Sendvičové panely - Česká republika [online]. 2013 [cit. 2014-01-05]. Dostupné z: http://panely.kingspan.cz/sendvicove-panely-zatepleniizolace-oplasteni-1725.html
[9]
The Google Distance Matrix API. Google Developers [online]. 2013 [cit. 2014-01-05]. Dostupné z: https://developers.google.com/maps/documentation/distancematrix
[10] LINDO Systems Inc. [online]. 2014 [cit. 2014-01-05]. Dostupné z: http://www.lindo.com/
57
[11] GUROBI Optimization [online]. 2014 [cit. 2014-01-05]. Dostupné z: http://www.gurobi.com/ [12] Maximal Software: Optimizing Business Applications [online]. 2013 [cit. 2014-01-05]. Dostupné z: http://www.maximalsoftware.com/download/
58
Přílohy Příloha č. 1 Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations:
73759.04 73759.04 0.000000 43015 3281342
TABLE_X HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN
HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK
AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO
59
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG
AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK
SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES
60
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG
AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG
AVIA SOLO SET_TRUCK MEGA_STANDARD FLAT_BED OVERSIZED NAVES
0 0 0 0 0 0 0
HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK
AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
TABLE_Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
61
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN
SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO
62
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3
AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK
SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA
63
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG
SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA
64
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK HK AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN AGLASTERHAUSEN
AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES
65
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
AGLASTERHAUSEN AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHLBECK AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG AHRENSBURG
NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES AVIA AVIA AVIA SOLO SOLO SOLO SET_TRUCK SET_TRUCK SET_TRUCK MEGA_STANDARD MEGA_STANDARD MEGA_STANDARD FLAT_BED FLAT_BED FLAT_BED OVERSIZED OVERSIZED OVERSIZED NAVES NAVES NAVES
66
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
