Logistický modul pro optimalizaci rozvozových tras

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Logistický modul pro optimalizaci rozvozových tras DIPLOMOVÁ PRÁCE Jan Chodúr

Brno, květen 2013

Prohl{šení Prohlašuji, že tato pr{ce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracov{ní používal nebo z nich čerpal, v pr{ci ř{dně cituji s uvedením úplného odkazu na příslušný zdroj.

Vedoucí pr{ce: RNDr. Svatopluk Kalužík

Poděkov{ní Na tomto místě bych chtěl velmi poděkovat vedoucímu mé pr{ce RNDr. Svatoplukovi Kalužíkovi za jeho cenné rady a pozn{mky k této pr{ci a za vstřícnost při konzultacích.

Shrnutí Tato pr{ce se zabýv{ analýzou, n{vrhem a implementací samostatného logistického modulu pro optimalizaci rozvozových tras. V první č{stí uv{dí procesy a úlohy spojené s distribucí zboží a analyzuje a porovn{v{ existující metody a algoritmy pro automatickou optimalizaci přepravních tras. Druh{ č{st pr{ce se věnuje n{vrhu modulu, výběru vhodné optimalizační metody na z{kladě analýzy a jejímu upravení pro praktické využití. Popisuje také použité technologie a samotnou implementaci modulu. Implementace vytvořeného modulu je spolu s analýzou k dispozici na přiloženém CD.

Klíčov{ slova Informační systém, pl{nov{ní logistiky, distribuce, modul, trasa, heuristika, metaheuristika

Obsah 1.

Úvod ....................................................................................................................... 1 1.1. Předmět pr{ce ................................................................................................ 1 1.2. Cíle pr{ce ........................................................................................................ 1 2. Analýza a požadavky .......................................................................................... 3 2.1. Informační systémy podniků....................................................................... 3 2.1.1. Architektura systémů ............................................................................ 3 2.1.2. Příklady podnikových systémů ........................................................... 4 2.2. Logistika ......................................................................................................... 4 2.2.1. Logistické moduly .................................................................................. 4 2.3. Analýza procesů a úloh v r{mci distribuce zboží .................................... 5 2.3.1. Typy pl{nov{ní distribuce .................................................................... 5 2.3.2. Distribuční depa ..................................................................................... 6 2.3.3. Odběratelé ............................................................................................... 6 2.3.4. Vozový park ............................................................................................ 7 2.3.5. Dod{vky a balíky ................................................................................. 10 2.3.6. Vratné obaly .......................................................................................... 11 2.3.7. Reklamace a vr{cení zboží .................................................................. 13 2.3.8. Optimalizace rozvozu.......................................................................... 13 2.4. Porovn{ní systémů pro pl{nov{ní logistiky ........................................... 15 2.5. Optimalizační metody ................................................................................ 17 2.5.1. Problém obchodního cestujícího ........................................................ 18 2.5.2. Problém plnění z{sobníků .................................................................. 18 2.5.3. Problém okružních jízd ....................................................................... 19 2.5.4. Zn{mé metody pro řešení VRP .......................................................... 22 2.5.5. Srovn{ní metod .................................................................................... 27 2.6. Požadavky na modul .................................................................................. 30 2.6.1. Funkční požadavky.............................................................................. 30 2.6.2. Nefunkční požadavky ......................................................................... 31 2.7. Případy užití................................................................................................. 32 2.7.1. Řidič........................................................................................................ 32 2.7.2. Dispečer ................................................................................................. 32 3. N{vrh a implementace....................................................................................... 34 3.1. Použití technologií ...................................................................................... 34 3.1.1. Vývojové n{stroje ................................................................................. 34 3.1.2. Jazyk a vývojové prostředí.................................................................. 35 3.1.3. Datab{ze ................................................................................................ 36 3.1.4. Grafické uživatelské prostředí ........................................................... 36 3.1.5. Geografick{ data a mapy .................................................................... 37

3.2. Volba a implementace algoritmu pro optimalizaci ................................ 37 3.2.1. Úpravy pro heterogenní vozový park............................................... 38 3.2.2. Úpravy pro kapacitní a jin{ omezení tras ......................................... 39 3.2.3. Úpravy pro svoz materi{lů ................................................................. 40 3.2.4. Úpravy pro prioritu dod{vek ............................................................. 41 3.2.5. Úpravy pro minimalizaci počtu tras ................................................. 42 3.2.6. Implementace algoritmu ..................................................................... 43 3.3. Implementace rozhraní na existující IS .................................................... 46 3.3.1. Data dod{vek ........................................................................................ 46 3.3.2. Data položek dod{vek ......................................................................... 48 3.3.3. Data obalových materi{lů ................................................................... 48 3.3.4. Nemožnost napojení na nekompletní systém .................................. 49 3.3.5. Datový model simulované č{sti informačního systému ................ 49 3.4. Implementace doplňujících údajů ............................................................ 50 3.4.1. Data uživatelů ....................................................................................... 50 3.4.2. Data vozového parku .......................................................................... 51 3.4.3. Data odběrných míst ............................................................................ 52 3.4.4. Vzd{lenosti mezi odběrnými místy ................................................... 53 3.4.5. Vratné obaly na adres{ch .................................................................... 54 3.4.6. Data pl{nů a tras................................................................................... 54 3.4.7. Datový model ....................................................................................... 56 3.4.8. Diagram tříd .......................................................................................... 58 3.5. Implementace grafického rozhraní ........................................................... 58 3.5.1. Zobrazení podle rolí uživatelů ........................................................... 58 3.5.2. Výpočty v aplikaci ................................................................................ 59 3.5.3. Jednotlivé obrazovky ........................................................................... 59 4. Z{věr..................................................................................................................... 65 Literatura ....................................................................................................................... 67 Přílohy ........................................................................................................................... 71

Seznam obr{zků Obr. 1 – Diagram užití role řidič ................................................................................ 32 Obr. 2 – Diagram užití role dispečer ......................................................................... 33 Obr. 3 – Diagram inici{lní f{ze algoritmu ................................................................ 43 Obr. 4 – Diagram slučovací f{ze algoritmu .............................................................. 44 Obr. 5 – Diagram konečné f{ze algoritmu ............................................................... 45 Obr. 6 – Datový model simulované č{sti informačního systému ......................... 50 Obr. 7 – Datový model celého modulu ..................................................................... 57 Obr. 8 – Spr{va odběrných míst ................................................................................ 60 Obr. 9 – Spr{va přepravních pl{nů ........................................................................... 61 Obr. 10 – Spr{va tras pl{nu ........................................................................................ 62 Obr. 11 – Generov{ní přepravy ................................................................................. 63 Obr. 12 – Upravení místa dod{vky ........................................................................... 64

Seznam tabulek Tab. 1 - Porovn{ní efektivity heuristických metod pro CVRP .............................. 29

1.

Úvod Dnešní doba s sebou přin{ší neust{lý tlak na zvyšov{ní konkurence-

schopnosti. Menší i velké firmy jsou nuceny zlepšovat efektivitu svých procesů a snižovat n{klady. K tomu jim může dopomoct použití vhodného informačního systému. Díky rychlému rozvoji informačních technologií jsou takové systémy schopné optimalizovat firemní procesy a velkou č{st z nich i automatizovat. Jejich spr{vné nasazení přin{ší i zvýšení kvality dat a jejich centralizaci, spr{vu a optimalizaci toku dokumentů a vyšší bezpečnost. Často také poskytují n{stroje pro vyhodnocov{ní a pl{nov{ní činnosti podniku a pro podporu rozhodov{ní. Mohou tak firmě na trhu poskytnout potřebnou výhodu.

1.1.

Předmět pr{ce Předmětem této pr{ce je oblast logistiky a distribuce zboží. Tato oblast

navazuje na skladové hospod{řství a řeší veškeré problémy spjaté s distribucí zboží od dodavatele k odběrateli. Informační systémy, které podporují a automatizují pl{nov{ní logistiky, přin{šejí podniku nezanedbatelné úspory při distribuci jeho zboží (snížení n{kladů na pohonné hmoty a mzdy) a mohou tak být další cestou pro zvýšení jeho konkurenceschopnosti.

1.2.

Cíle pr{ce Hlavním cílem této pr{ce je: -

Analyzovat procesy spojené s distribucí zboží a jejich napojení na podnikový informační systém, porovnat st{vající dostupné n{stroje pro řízení logistiky.

-

Analyzovat metody pro optimalizaci a operativní pl{nov{ní rozvozových tras a n{sledně je porovnat s ohledem na jejich efektivitu, časovou n{ročnost a rozšiřitelnost.

-

Na z{kladě analýzy zvolit vhodnou metodu pro optimalizaci a tu poté upravit a rozšířit pro praktické využití v r{mci informačního systému pro řízení obchodů a skladů.

1

-

Navrhnout samostatný logistický modul, který rozšíří informační systém pro řízení obchodů a skladů a který pomocí zvolené metody umožní automatickou optimalizaci denních rozvozových tras.

-

Zvolit vhodné technologie pro realizaci, implementovat navržený modul a potvrdit jeho funkčnost na testovacích datech.

2

2.

Analýza a požadavky N{sledující kapitola představí n{stroje pro optimalizaci distribuce

v kontextu podnikových informačních systémů a nastíní požadavky, které mohou být na běžný systém pro pl{nov{ní rozvozu zboží kladeny. D{le se podrobněji věnuje automatizované optimalizaci tras, metod{m využitelným pro řešení tohoto úkolu a jejich porovn{ní. Na konci definuje konkrétní požadavky na realizovaný modul, který je předmětem této pr{ce, a uv{dí případy jeho užití.

2.1.

Informační systémy podniků Informační systém je systém sběru, uchov{v{ní, analýzy a prezentace dat

určený pro poskytov{ní informací mnoha uživatelům různých profesí *1]. V širším pojetí zahrnuje všechny zapojené metody, technologické prostředky a pracovníky. Informační systémy, které integrují a automatizují firemní procesy související s produkčními činnostmi firmy, se nazývají podnikové informační systémy. Často se pro ně použív{ také termín ERP systémy (Enterprise Resource Planning) [2], který m{ podobný význam. 2.1.1. Architektura systémů Podnikové informační systémy bývají velmi rozs{hlé a pokrývají většinu firemních procesů, z toho důvodu mívají modulovou architekturu. Ta umožňuje nasazení pouze firmou požadované funkcionality, je snadno rozšiřiteln{ a jednoduše propojiteln{ s dalšími externími systémy. Mezi hlavní moduly takovýchto systémů zpravidla patří: -

finance a účetnictví

-

řízení a pl{nov{ní výroby

-

řízení obchodu skladov{ní a distribuce

-

spr{va lidských zdrojů

-

spr{va majetku

-

podpora rozhodov{ní

3

Nasazení podnikového systému většinou předch{zí rozs{hl{ analýza firemních procesů a jejich revize a standardizace. Na z{kladě analýzy je vybr{no nejvhodnější dostupné řešení, které poté proch{zí customizací (úprava a přizpůsobení hotového řešení pro potřeby konkrétního podniku) a migrací data z původního systému (pokud jsou k dispozici). 2.1.2. Příklady podnikových systémů V dnešní době je na trhu k dispozici velké množství podnikových systémů. Mezi nejčastěji využívané v oblasti středních a větších firem patří produkty na platformě SAP [3]. Dalším rozšířeným ERP systémem je Dynamics NAV od společnosti Microsoft (dříve zn{mý pod n{zvem Navision) [4]. Ze systémů vyvíjených v České republice lze zmínit například komplexní podnikové řešení Abra G4 [5] nebo ERP systémy z řady Helios *6].

2.2.

Logistika Velk{ č{st společností, které se zabývají výrobou a obchodem, řeší

v r{mci své činnosti i distribuci zboží odběratelům. Procesy s tím spojené spadají do oboru logistiky [7]. Logistika se obecně zabýv{ toky zboží, peněz a informací mezi dodavateli a odběrateli (případně v r{mci podniku) a jejím cílem je optimalizovat tyto toky tak, aby byly n{klady na jejich realizaci co nejnižší. 2.2.1. Logistické moduly Pl{nov{ní rozvozu lze z velké č{sti automatizovat. Systémy vyvíjené pro tento účel bývají dod{v{ny ve formě samostatných modulů a aplikací, případně bývají integrov{ny přímo do informačního systému podniku. Jejich úkolem je komunikovat s podnikovým systémem a na z{kladě přijatých objedn{vek zajišťovat pl{nov{ní rozvozu tak, aby bylo požadované zboží doručeno odběrateli v ř{dném termínu s co nejnižšími n{klady. Většina společností, které se jejich vývojem zabývají, dnes uv{dí, že může automatick{ optimalizace rozvozu dlouhodobě ušetřit 5 až 15 procent z n{kladů na přepravu. Existující moduly pro pl{nov{ní a řízení logistiky většinou zajišťují pl{nov{ní přepravních tras, sledov{ní průběhu přepravy, spr{vu vozového

4

parku, integraci digit{lních mapových podkladů, případně i komunikaci s mobilními zařízeními a systémem GPS.

2.3.

Analýza procesů a úloh v r{mci distribuce zboží Pl{nov{ní logistiky s sebou nese několik netrivi{lních úkolů, jejichž

popis a význam pro optimalizaci rozvozu je uveden níže. Ne každý logistický systém však pokrýv{ všechny tyto problémy. Automatizace některých z nich není pro mnoho menších podniků nutn{ ani přínosn{. 2.3.1. Typy pl{nov{ní distribuce Jakékoliv pl{nov{ní lze rozdělit podle časového horizontu na několik úrovní. Standardně se použív{ dělení na strategické, taktické a operativní pl{nov{ní. 2.3.1.1.

Strategické pl{nov{ní

Při pl{nov{ní distribuce spad{ do strategického rozhodov{ní problém určení optim{lního počtu rozvozových dep a jejich vhodného rozmístění v distribuční síti. Řešení této úlohy se realizuje v horizontu měsíců až let a významné úspory může přinést zejména při sestavov{ní a restrukturalizaci distribuční sítě. Při pl{nov{ní počtu a rozmístění dep se většinou využív{ úlohy o hled{ní p-medi{nu [8]. Odběratelé v síti jsou v{hově ohodnoceni a cílem úlohy je nalézt takové umístění depa (nebo více dep), které minimalizuje součet v{žených vzd{leností všech obsluhovaných odběratelů od nejbližšího depa. 2.3.1.2.

Taktické pl{nov{ní

Změny provedené na této úrovni je možné realizovat v r{mci týdnů až měsíců. Hlavním problémem taktického pl{nov{ní distribuce zboží je přiřazení jednotlivých odběratelů v síti k depům, kter{ je budou obsluhovat. Tato úloha je běžně nazýv{na úlohou rajonizace a její řešení býv{ vhodné při změn{ch topologie odběratelů nebo jejich požadavků. V oblasti taktického rozhodov{ní se také řeší změny způsobu obsluhy z{kazníků a změny metod pro pl{nov{ní rozvozových tras.

5

2.3.1.3.

Operativní pl{nov{ní

Do oblasti operativního pl{nov{ní spad{ vlastní sestavov{ní vhodných tras vozidel pro obsluhu zadaných odběrných míst. Každý den se na z{kladě přijatých objedn{vek sestaví dod{vky pro jednotlivé odběratele. Odběrn{ místa jsou podle zadaných kritérií co nejvhodněji sdružena do jedné nebo několika okružních tras. Tento problém řeší úloha okružních jízd (Vehicle Routing Problem). Jelikož je úloha důležitou souč{stí této pr{ce, bude podrobněji rozebr{na v dalších kapitol{ch. 2.3.2. Distribuční depa Jak již bylo řečeno, pro obsluhu rozs{hlejší distribuční sítě může existovat více dep a každé z nich může disponovat odlišným vozovým parkem, skladovými kapacitami i sortimentem zboží, které m{ k dispozici. Rozdíly v dispozicích distribučních center mohou výrazně zvýšit obtížnost pl{nov{ní. Tento problém lze ale zmírnit nebo eliminovat alokací odběratelů na depa ve f{zi taktického pl{nov{ní (operativní pl{nov{ní lze poté řešit v r{mci jednotlivých dep). 2.3.3. Odběratelé Různí odběratelé v distribuční síti mohou mít různé požadavky jak na sortiment zboží, tak na způsob a podmínky jeho dod{ní. 2.3.3.1.

Doba doručení

V mnoha případech je odběratel ochoten přijmout zboží jen v určitém časovém úseku. Důvodem může být například omezen{ pracovní doba nebo n{vaznost technologických procesů. Odběratelé tak mohou být ochotni přijímat dod{vky kdykoliv v r{mci standardní pracovní doby, pouze v jimi určených časových oknech nebo pouze v jimi určeném konkrétním čase. Další situací může být doručení mimo standardní pracovní dobu (například v nočních hodin{ch). 2.3.3.2.

Platby a fakturace

Při platbě za objednané zboží využívají odběratelé různé druhy platebních metod. Jedním z používaných typů je platba při dod{ní (na dobírku nebo COD). Ta může být realizov{na hotovostně nebo bezhotovostně pomocí

6

platební karty a přenosných platebních termin{lů. Při převzetí a zaplacení zboží je odběrateli před{na také faktura za dod{vku. Další používanou platební metodou je platba před dod{ním realizovan{ zpravidla

bezhotovostně

(např.

bankovním

převodem).

Po

vytvoření

objedn{vky je dodavatelem odběrateli vystavena z{lohov{ faktura (případně pouze údaje o požadované platbě). Po přips{ní smluvené č{stky na účet dodavatele je odběrateli vystavena faktura, kter{ může být odesl{na v elektronické formě nebo doručena spolu s dod{vkou. Jiné metody platby za doručované zboží se v praxi tolik nevyužívají. Může jít například o pravidelné pauš{lní platby nebo souhrnné platby za určené časové období. 2.3.3.3.

Ostatní požadavky odběratelů

Mezi další časté požadavky odběratelů patří například dod{ní zboží o víkendu nebo ve dnech st{tem uznaných sv{tků (podniky s nepřetržitou výrobou). Často je také vyžadov{n zpětný odběr staršího spotřebiče nebo svoz vratných obalů. Jiné požadavky se mohou týkat telefonické avizace času dod{ní nebo možnosti změnit v průběhu dne čas dod{ní. 2.3.4. Vozový park Každ{ společnost, kter{ zajišťuje distribuci zboží odběratelům vlastními prostředky, potřebuje udržovat dostatečnou flotilu dopravních prostředků pro realizaci přepravy. 2.3.4.1.

Složení vozového parku

Distribuční flotila býv{ nejčastěji složena z jednostopých a dvoustopých silničních vozidel. Méně často se v ní vyskytují i kolejov{ vozidla, různé druhy letadel nebo plavidel. Z pohledu optimalizace rozvozových tras je důležité rozlišit, jestli podnik použív{ k distribuci zboží homogenní nebo heterogenní flotilu vozidel. Homogenní vozový park představuje z pohledu optimalizace jednodušší variantu, kter{ předpokl{d{, že všechna využívan{ vozidla jsou stejného typu, mají stejnou užitečnou hmotnost (nosnost), objem a rozměry n{kladového prostoru i průměrnou přepravní rychlost.

7

Varianta heterogenního vozového parku je pro optimalizaci tras složitější, v praxi se však vyskytuje častěji. Flotila je v tomto případě složena z více typů vozidel s odlišnými parametry. To může výrazným způsobem ovlivnit složení optim{lních přepravních tras. 2.3.4.2.

Kapacitní a jin{ omezení

Vozidla využívan{ k přepravě mohou mít pro přepravu různ{ omezení. Jedním z nejdůležitějších parametrů je nosnost (maxim{lní přípustn{ hmotnost přepravovaného n{kladu). Objem n{kladového prostoru pak určuje maxim{lní objem n{kladu, který je vozidlo schopné pojmout. Při jeho určov{ní je nutné br{t v úvahu rezervní volný prostor pro manipulaci s balíky a paletami. Také je možné definovat rozměry přepravního prostoru a zajistit u rozměrnějších dod{vek, že budou umístěny na vozidlo, na které se opravdu vejdou. Dalším omezením vozidla mohou být jeho možnosti nakl{d{ní a vykl{d{ní. U vozidel lze evidovat čas potřebný k naložení nebo vyložení jednoho balíku případně konkrétního druhu zboží. Vozy mohou být také vyhrazené pro přepravu určitého druhu zboží (chladící a mrazícími vozy, cisternové vozy pro převoz sypkých a tekutých materi{lů, vozy pro transport živých zvířat, vozy pro přepravu odpadních, chemických a hořlavých l{tek). Dalšími limitujícími parametry mohou být dojezd vozidla na plnou n{drž a průměrn{ přepravní rychlost naloženého vozidla. Ta ovlivňuje dojezdové časy k jednotlivým odběratelům i dobu nutnou pro dokončení trasy. 2.3.4.3.

Optimalizace naložení vozidla

Při operativním pl{nov{ní distribuce zboží lze mimo jiné ušetřit č{st n{kladů spr{vným naložením dod{vek na vozidlo. Při nakl{d{ní zboží je nutné respektovat rovnoměrné rozložení hmotnosti n{kladu na jednotlivé osy n{kladního vozu nebo přívěsu. Pokud je vozidlo využív{no k obsluze tras s více odběrnými místy, je vhodné naložit vozidlo tak, aby bylo možné na jednotlivých zast{vk{ch vyložit příslušnou dod{vku bez potřeby vyložení celého n{kladu. Pokud je v odběrných místech realizov{na pouze vykl{dka a nedoch{zí k vyzved{v{ní zboží, je možné využít metodu z{sobníku (dod{vky naložíme v obr{ceném pořadí, než v jakém jsou seřazeny na trase) [9].

8

Pokud se v některých odběrných místech uskutečňuje i nakl{d{ní zboží (které m{ být svezeno zpět do depa), doch{zí ke zhoršení přístupu k n{sledujícím dod{vk{m. V takovém případě je nutné při pl{nov{ní počítat s rezervním prostorem pro manipulaci uvnitř n{kladového prostoru. Balené a kusové zboží je pro potřeby přepravy možné (v r{mci jedné dod{vky) shlukovat do větších celků. Níže jsou vyjmenov{ny nejběžnější metody takového shlukov{ní. -

Paletizace [10]: menší balíky jsou umístěny na palety, se kterými se manipuluje

pomocí

vysokozdvižných

a

paletových

vozíků.

Z různých druhů palet jsou v oblasti přepravy a skladov{ní nejpoužívanější tzv. europalety. Kromě europalet je možné využít i palety jiných materi{lů (např. lisované a plastové) nebo jiných konstrukcí (ohradové, speci{lní). -

Kartonizace [11]: menší druhy zboží a kusový materi{l mohou být sdruženy a zabaleny do souhrnných balíků (kartonů). Metoda je vhodn{ pro vytv{ření přepravních jednotek, které jsou menší a lehčí než palety a jsou určené přev{žně pro ruční manipulaci. V případě menších dod{vek lze kartony rovnou naložit na vozidlo, v případě větších dod{vek je možné je ještě umístit na palety.

-

Kontejnerizace [12]: metoda nakl{d{ní do standardizovaných přepravních kontejnerů, které je možné využít při intermod{lní dopravě [13] (většinou kombinace lodní, železniční a silniční dopravy). Je vhodn{ pro transport na velké vzd{lenosti a při distribuci zboží přímým odběratelům se využív{ jen vz{cně. Existuje mnoho typů kontejnerů, běžně jsou použív{ny například ISO kontejnery.

-

Smíšen{ nakl{dka: při plnění vozidel se často použív{ kombinace balících metod. Podle velikosti dod{vek může být vhodné č{st zboží

9

naložit na palet{ch, č{st v kartonových balících a některé materi{ly uložit po kusech pouze v jejich vlastním obalu. V mnoha menších i středních podnicích je optimalizace naložení vozidla st{le ponech{v{na na zkušenostech a uv{žení řidiče nebo dalšího person{lu. Pro rozs{hlé distribuční sítě lze využít automatizovanou optimalizaci využití n{kladového prostoru. Pro tento účel existují softwarové n{stroje, které využívají komplexní algoritmy k navržení co nejefektivnějšího využití trojrozměrného prostoru. 2.3.5. Dod{vky a balíky Každ{ dod{vka, kter{ m{ být realizov{na, může obsahovat několik položek dod{vky (samostatných balíků). Jednotlivé balíky dané dod{vky musejí být spr{vně označeny a naloženy na stejné vozidlo. 2.3.5.1.

Přepravní etikety

K jednoznačné identifikaci balíků se většinou využívají přepravní etikety. Etiketa by měla obsahovat adresu a telefonní kontakt příjemce (odběratele), identifikaci dod{vky, do které balík patří, informace o hmotnosti balíku a případné výši dobírky (pokud je platba realizov{na touto metodou) a datum odesl{ní. Lze na ni také umístit jedno nebo dvourozměrný č{rový kód, který v kombinaci s přenosným čtecím zařízením výrazně urychlí identifikaci balíků.

Etiketa

by

také

měla

obsahovat

informace

s manipulačními

a bezpečnostními pokyny (například křehké zboží, nepřet{čet, chr{nit před vlhkem, nestohovat, hořlavé, toxické). V případě rozvozu menšího sortimentu zboží v jednotném balení je možné jednoznačnou identifikaci balíků vynechat a příslušný počet kusů daného zboží vyložit u odběratele podle dopravního nebo dod{vkového dokladu. 2.3.5.2.

Stavy dod{vek

Po dokončení denní přepravy nebo během ní je třeba aktualizovat stavy jednotlivých dod{vek. Pojmenov{ní a počet stavů se může systém od systému lišit podle konkrétních požadavků podniku, níže uvedené se však využívají nejčastěji:

10

-

Založena do systému: dod{vka byla na z{kladě objedn{vky založena do systému. Před jejím uvolněním je nutné zkontrolovat vykrytí objedn{vky skladovými z{sobami. Pokud je platba realizov{na bankovním převodem předem, ček{ se na potvrzení o přijetí platby.

-

Uvolněna pro přepravu: dod{vka byla potvrzena a uvolněna do přepravního procesu, zabalena a označena

-

Označena k expedici: bylo stanoveno datum expedice, dod{vka byla zařazena do přepravní trasy na příslušné vozidlo.

-

Probíh{ přeprava: ve stanovené datum dojde k naložení zabalené dod{vky na vozidlo a doručení na adresu odběratele.

-

Doručena: dod{vka byla bez výhrad převzata odběratelem a byla před{na faktura za dodané zboží (pokud nebyla dříve doručena elektronicky).

-

Č{stečně doručena: odběratel převzal pouze č{st položek dod{vky. Důvodem pro nepřevzetí balíku může být jeho poškození při přepravě (seps{n protokol o poškození č{sti z{silky), platební neschopnost odběratele nebo nenahl{šen{ změna objedn{vky. Všechny situace musejí být evidov{ny a d{le řešeny, nedoručené položky jsou svezeny zpět do depa.

-

Nedoručena: odběratele se nepodařilo zastihnout nebo odmítl celou dod{vku převzít. V takovém případě je dod{vka svezena zpět do depa.

Změny stavů dod{vek a jejich položek musejí být zaznamen{ny do informačního systému. Pokud m{ řidič k dispozici přenosný termin{l se vzd{leným přístupem, může informace zadat do systému přímo na adrese odběratele. Jinak jsou stavy dod{vek zaznamen{ny do přepravního listu a po n{vratu do depa se zajistí jejich přeps{ní do systému. 2.3.6. Vratné obaly Většina zboží je dod{v{na v nějaké formě obalu. Podle Z{kona o obalech [14] musejí používané obaly splňovat určit{ kritéria a osoba, kter{ je uv{dí na trh nebo do oběhu je povinna vést jejich evidenci.

11

2.3.6.1.

Typy obalů

Obaly se d{le z pohledu z{kona dělí na několik typů, podle kterých se také liší povinnosti při jejich spr{vě a evidenci: -

Nevratné (jednocestné) obaly nejsou určeny k opakovanému použití, není stanoven způsob, jakým mají být vraceny. Osoba, kter{ je uvedla na trh nebo do oběhu, je však povinn{ zajistit jejich zpětný odběr (bez n{roku na úplatu).

-

Opakovaně použitelné obaly jsou určeny pro opětovné plnění nebo použití ke stejnému účelu. Osoba, kter{ je uvedla do na trh nebo do oběhu, je povinna učinit opatření, kter{ umožní opakované použití obalu. o Vratné obaly jsou opakovaně použitelné obaly, u kterých je stanoven specifický způsob vr{cení osobě, kter{ je uvedla do oběhu. 

Vratné z{lohované obaly jsou vratné obaly, při jejichž uvedení na trh a opětovném použití je účtov{na peněžní č{stka jako z{loha.

Kvůli z{konným povinnostem by měl podnikový informační systém umožnit evidenci obalových materi{lů (a jejich vlastností) a u každého typu baleného zboží uv{dět množství a typ obalových materi{lů, které jsou se zbožím dod{v{ny. D{le by měl umožnit evidenci zpětného odběru obalů a způsobu jejich zpracov{ní. Výkup a zpětný odběr obalů může podnik realizovat v provozovně (pokud nějakou vlastní), případně i prostřednictvím zpětného svozu vozovým parkem (který je využív{n k rozvozu zboží). Pro účely řízení distribuce zboží k odběratelům je nutné vzít v úvahu pouze druhou možnost. 2.3.6.2.

Pl{nov{ní zpětného odběru

V případě, že odběratel objedn{v{ zboží, jehož souč{stí je vratný obal, platí dodavateli z{lohu za obal spolu s platbou za samotné zboží. Při některé z dalších dod{vek danému odběrateli od něj může řidič vykoupit určitý objem vratných obalových materi{lů.

12

Objem materi{lu, který je možné zpětně odebrat, býv{ omezen volnou kapacitou vozidla. Pokud není možné vykoupit od odběratele požadované množství obalů, je možné realizovat zbylou č{st výkupu při další n{vštěvě. Pro lepší pl{nov{ní zpětného svozu vratných obalů je možné v systému evidovat u jednotlivých odběratelů počty dodaných a ještě nesvezených obalů. Při pl{nov{ní využití kapacity vozidel lze poté zohlednit svoz všech nesvezených obalů od daného odběratele, pouze obalů dodaných mu v předchozí dod{vce nebo svoz obalů nezohlednit vůbec. Ještě efektivnějšího pl{nov{ní lze dos{hnout hl{šením (avizací) objemu obalů, který odběratel požaduje svézt. Takov{ informace může být zahrnuta například přímo v objedn{vce zboží nebo může být sdělena elektronickou nebo telefonickou komunikací. Při svozu vratných obalů je také nutné vyplatit odběrateli z{lohy za zpětný odběr. Na ty dodavatel vystaví odběrateli opravný daňový doklad (dobropis) a peníze jsou před{ny buď v hotovosti řidičem, nebo převodem na účet odběratele. 2.3.7. Reklamace a vr{cení zboží Při pl{nov{ní svozu a rozvozu v distribuční síti je také nutné počítat s možností reklamace dodaného zboží. Pokud odběratel nahl{sí reklamaci, je obvykle nutné dané zboží svézt zpět dodavateli, který reklamaci posoudí a zajistí dod{ní nového nebo opraveného zboží. Odběratel také může zboží odeslat dodavateli na vlastní n{klady. V případě nahl{šení reklamace lze objem reklamovaného zboží zohlednit při pl{nov{ní kapacity vozidla, které m{ uskutečnit další dod{vku. Pokud je reklamace přijata a vyřízena formou výměny nebo opravy zboží, je toto dod{no odběrateli ve formě standardní dod{vky (kter{ ale není fakturov{na a placena). V případě vr{cení peněz dodavatel vystaví opravný daňový doklad a příslušnou č{stku uhradí odběrateli bankovním převodem nebo hotově při další n{vštěvě rozvozového vozidla u odběratele. 2.3.8. Optimalizace rozvozu Všechny výše uvedené procesy a úlohy, jejich varianty a omezující podmínky ovlivňují řešení klíčového úkolu logistiky a distribuce zboží. Tím je

13

optimalizace rozvozu a svozu zboží pro jednotliv{ odběrn{ místa v distribuční síti. Cílem takové optimalizace je snížení n{kladů na přepravu. Rozvozy v r{mci operativního pl{nov{ní jsou většinou organizované do denních přepravních pl{nů. Pro každý pracovní den se zpracují dod{vky, které je třeba rozvézt, odpovídající odběrn{ místa se sdruží do přepravních tras a tras{m se přiřadí vozidla, kter{ je budou realizovat. Optimalizace denních přepravních pl{nů pak spočív{ ve spr{vném rozdělení a seřazení dod{vek do přepravních tras tak, aby byla minimalizov{na celkov{ délka všech tras (úspory na pohonných hmot{ch) a minimalizov{n počet použitých vozidel (úspory na mzd{ch řidičů a údržbě vozidel). Z{roveň musejí být splněny všechny omezující podmínky (dané odběrateli, vlastnostmi vozového parku, vlastnostmi dod{vaných balíků). Oba parametry jsou spolu sv{z{ny a snížení počtu vozidel většinou vede ke snížení délky tras (eliminace úseků vedoucích z depa a do depa). Tato souvislost se projevuje v distribuční síti, ve které platí pravidlo trojúhelníkové nerovnosti [15]. Při optimalizaci denního pl{nu podle požadovaných kritérií může dojít k situaci, kdy podnik nem{ dostatek vozidel pro vykrytí napl{novaných tras. Tu lze řešit různými způsoby: -

Některé dod{vky lze z přepravy vypustit a realizovat je v nejbližším možném termínu. Jejich výběr může být proveden manu{lně nebo může pomocí pl{novacího n{stroje. Ten z pl{nu vypustí nejméně výhodné dod{vky (z pohledu minimalizace délky tras), případně může zohlednit priority jednotlivých dod{vek.

-

Transport některých dod{vek lze zajistit externí transportní firmou.

-

Pokud se situace opakuje častěji, je možné zv{žit rozšíření vozového parku.

Optimalizaci denních pl{nů je možné pro menší distribuční sítě zajišťovat manu{lně (v dlouhodobém provozu mohou rozvozové trasy konvergovat k ust{leným řešením jen s menšími odchylkami). Pro co největší úsporu n{kladů je však vhodné použít softwarové n{stroje, které optimalizaci prov{dějí automatizovaně.

14

2.4.

Porovn{ní systémů pro pl{nov{ní logistiky N{sledující kapitola se věnuje porovn{ní existujících systémů pro

optimalizaci rozvozových tras. Z provedených průzkumů [16] vyplýv{, že většina těchto n{strojů je vyvíjena pro platformu MS Windows. Často se také prosazují řešení ve formě webových služeb a aplikací. Optimalizaci nejčastěji zajišťují modifikované verze zn{mých algoritmů. Jejich autoři však většinou odmítají sdělit další podrobnosti o nasazených metod{ch. Uv{děné přibližné časy výpočtů (pro ř{dově desítky tras a stovky až tisíce odběratelů) se většinou pohybují do 15 minut. Některé vyspělejší n{stroje poskytují také tzv. trasov{ní po úsecích. Tato varianta pl{nov{ní je určena pro obsluhu celých úseků tras a využív{ se například při rozvozu pošty (úseky odpovídají jednotlivým ulicím). V n{sledujících odstavcích je uveden seznam často používaných řešení a jejich porovn{ní na z{kladě jednoho z m{la dostupných průzkumů [17]. U všech uvedených produktů jejich výrobci uv{dějí teoreticky neomezený maxim{lní počet zpracov{vaných odběratelů a možnost přepočít{ní tras v průběhu

přepravy.

Většina

také

podporuje

komunikaci

s mobilními

zařízeními (tablety a chytrými telefony) a navigačními přístroji. Standardní hardwarové n{roky desktopových verzí umožňují jejich použití na běžných stolních počítačích. ORTEC Routing & Scheduling Optimization Software Tento n{stroj od firmy Ortec [18] je jedním z nejvíce rozšířených. K optimalizaci rozvozu jej využívají například společnosti Coca-Cola, Procter & Gamble a Tesco. Poskytuje všechny z{kladní i rozšířené funkce (operativní pl{nov{ní pro heterogenní vozový park, časov{ okna odběratelů, pl{nov{ní současného svozu i rozvozu). Podle srovn{ní provedeného pro nizozemskou firmu NEA [19] vypočít{v{ nejefektivnější a nejvhodnější přepravní trasy (ze sedmi testovaných produktů). Firma Ortec také dod{v{ řešení integrovan{ do platformy SAP a software pro optimalizaci využití n{kladového prostoru. ArcLogistics Route Software vyvinutý firmou ESRI [20] je dostupný pro platformu Windows nebo jako webov{ služba. Využív{ knihovnu propriet{rních algoritmů (pro

15

pl{nov{ní lze využít různé metody) a pro 1000 z{kazníků a 50 vozidel ud{v{ přibližnou dobu výpočtu méně než 5 minut. Při tvorbě tras využív{ i údajů o realizaci předešlých tras, poskytuje možnost přepl{nov{ní v průběhu přepravy, podporuje heterogenní vozový park i zpětný svoz obalů, ale neposkytuje možnost trasov{ní po úsecích. V řešení jsou integrov{ny mapové podklady Navteq [21]. Licence pro jedno rozvozní depo do 50 vozidel se pohybuje okolo 450 dolarů za měsíc. TruckStops VRS N{stroj od MapMechanics [22] je jedním ze starších využívaných systémů. Aplikace pro operační systém Windows m{ oproti ostatním řešením velmi nízké hardwarové požadavky. Výrobce ud{v{ minim{lní konfiguraci 1,4 GHz pro procesor a 256 KB operační paměti. Modul uživateli poskytuje možnost nastavit maxim{lní čas výpočtu a úlohu s 1000 uzly by mě vyřešit do 5 minut. Podporuje mapové podklady Navteq a nasazení čtecích zařízení RFID [23]. Zajišťuje operativní pl{nov{ní heterogenní flotily s možností určit maxim{lní dobu realizace trasy i definovat pro odběratele časov{ okna, neposkytuje ale n{stroj pro optimalizaci využití n{kladního prostoru a nepodporuje avizaci zpětného svozu obalů a zboží. WebSTARS 5.4 Novější software vyvinutý v roce 2009 společností Saitech [24] se od výše uvedených liší. Implementuje všechny standardní i pokročilé funkce pro taktické a operativní pl{nov{ní a řízení logistiky v distribuovaném prostředí přístupném přes internet (využív{ model zvaný cloud computing [25]). Aplikaci tak není třeba složitě instalovat, na straně uživatele m{ minim{lní hardwarové n{roky, je vysoce šk{lovateln{ a lze ji účtovat za jednotliv{ použití. Podle dostupných údajů je schopn{ napl{novat obsluhu 1000 z{kazníků během 1 až 3 minut a podporuje nasazení heterogenní flotily i časových oken. Ostatní řešení Mezi další využívané n{stroje lze zařadit například produkt iFacto TMS+, který je určený pro integraci do ERP systému MS Dynamics NAV. Ze

16

samostatných modulů jsou využív{ny také Tour Solver,

Plantour

nebo

RouteSmart pro platformu ArcGIS. Shrnutí Uveden{ komerční řešení podporují většinu procesů a úloh uvedených v č{sti analýzy. Ž{dný z nich však neposkytuje n{stroje pro optimalizaci využití n{kladového prostoru vozidel. Některé z uvedených firem (například Ortec) tyto n{stroje nabízejí jako samostatný produkt, který je možné použít v kombinaci s modulem pro pl{nov{ní tras, ale je nutné na něj zakoupit samostatnou licenci. Z pohledu

poskytované

funkcionality

a

možností

nastavení

se

z uvedených aplikací jeví jako nejvhodnější software Ortec. Jím vypočítané trasy byly také podle dostupných tesů nejkratší. Jeho nevýhodou je vyšší pořizovací cena, kter{ je určov{na individu{lně, ale pohybuje se okolo 15 tisíc dolarů a výše. Pro všechna uveden{ řešení obecně platí, že poskytují veškerou důležitou funkcionalitu a využívají efektivních algoritmů, jejich vysok{ cena však znesnadňuje jejich nasazení v menších a středních podnicích.

2.5.

Optimalizační metody Jak již bylo naznačeno výše, optimalizace distribuce zboží probíh{ ve

třech f{zích. Úlohy strategického a taktického pl{nov{ní lze řešit s velkými časovými odstupy pomocí zn{mých metod mimo r{mec informačního systému podniku. Z toho důvodu se tato pr{ce zaměří na třetí f{zi (operativní pl{nov{ní). Při operativním pl{nov{ní distribuce probíh{ optimalizace rozvozových a svozových tras pro jednotliv{ depa. Jejím cílem je minimalizovat celkovou délku všech tras a z{roveň minimalizovat jejich počet (a tím i počet vozidel nutných k jejich obsluze). Matematick{ úloha, kterou je pro minimalizaci délky tras nutné řešit, spad{ do třídy dopravních úloh. Ta zahrnuje širokou šk{lu kombinatorických optimalizačních problémů, které se odvíjejí od problému obchodního cestujícího (TSP) a obecně jsou považov{ny za NP-těžké [26]. Minimalizace počtu tras je pak variantou NP-těžkého problému plnění z{sobníků (BPP), který spad{ do třídy balících úloh.

17

Kombinace TSP a BPP je řešena v r{mci problému okružních jízd (VRP) a jeho variant. V n{sledujících odstavcích budou pops{ny všechny tři tyto úlohy, které hrají významnou roli při optimalizaci distribuce zboží. 2.5.1. Problém obchodního cestujícího Problém obchodního cestujícího [27] je diskrétní optimalizační problém, který řeší nalezení nejkratší cesty mezi body zadanými na mapě. Zad{ní lze form{lně definovat jako grafový problém. Jednotliv{ místa odpovídají uzlům grafu, hrany představují dostupné cesty mezi místy a jejich ohodnocení určuje délku cesty (případně čas nebo cenu). Graf musí být úplný (musí existovat ohodnocen{ cesta mezi každou dvojicí uzlů). Řešení úlohy pak probíh{ jako hled{ní hamiltonovské kružnice [28] v zadaném grafu. Problém m{ mnoho dalších variant ale pro dopravní úlohy je relevantní jeho optimalizační verze, kter{ je definov{na n{sledovně: V daném úplném ohodnoceném grafu nalezněte minim{lní (nejkratší) hamiltonovskou kružnici. Vzhledem k tomu, že je optimalizační verze problému obchodního cestujícího NP-těžk{, není pro ni zn{m algoritmus, který by zaručil nalezení optim{lního výsledku v polynomi{lním čase [29]. Proto se při jeho řešení v praxi využívají heuristiky [30]. Jsou obdobou standardních algoritmů, ale na rozdíl od nich nezaručují nalezení optim{lního řešení. Poskytují však možnost nalezení suboptim{lního řešení (blízkého tomu optim{lnímu) v polynomi{lním čase, a tedy v praxi použitelnou metodu pro řešení úloh ze složitostní třídy NP. 2.5.2. Problém plnění z{sobníků Cílem dopravních úloh býv{ i minimalizace počtu použitých vozidel a co nejefektivnější využití jejich kapacity. Tento problém řeší úloha plnění z{sobníků [31]. Plnění z{sobníků je NP-těžký kombinatorický problém. Jeho obecn{ varianta je vhodn{ pro homogenní vozový park, pro heterogenní park ji lze rozšířit. Neform{lně býv{ zad{v{na takto:

18

Je d{no n objektů o různém objemu a neomezený počet z{sobníků (n{dob) s určenou kapacitou. Cílem je naplnit všech n objektů do co nejmenšího počtu z{sobníků, tak aby obsah ž{dného z{sobníku nepřekročil zadanou kapacitu. Úloha m{ mnoho variant a rozšíření. Plnění může probíhat podle rozměrů a tvaru objektů (ve 2D nebo 3D prostoru), podle jejich v{hy, ceny a dalších parametrů. Pro heterogenní vozový park je nutné uvažovat omezenou sadu z{sobníků, z nichž každý může mít odlišnou kapacitu. Jelikož je problém NP-těžký, bývají k jeho řešení využív{ny heuristiky. Z těch nejzn{mějších lze jmenovat například First-Fit, ve které pr{vě zpracov{vaný objekt vložíme do prvního z{sobníku, který m{ ještě dostatečnou kapacitu, aby objekt pojmul. Z First-Fit je odvozena efektivnější metoda First-Fit Decreasing, kter{ objekty před zpracov{ním nejdříve sestupně seřadí podle objemu a objekty pak do z{sobníků naplňuje od nejobjemnějšího. Obdobou těchto heuristik jsou metody Best-Fit a Best-Fit Decreasing, které při plnění uvažují i zbývající volnou kapacitu z{sobníků. 2.5.3. Problém okružních jízd Problém obchodního cestujícího představuje z{klad většiny dopravních úloh. S{m o sobě však řeší pouze rozvoz zboží odběratelům v r{mci jediné trasy. Pro praktické využití je třeba pl{novat rozvoz ve více tras{ch. Tím se zabýv{ problém okružních jízd a jeho různé varianty [32]. Problém okružních jízd (VRP, někdy také úloha optim{lního trasov{ní) je definov{n pro distribuční síť zadanou grafem S = (V, H), kde V je množina uzlů a H je množina hran. Uzel V0 představuje rozvozové depo, uzly V1 … Vn představují odběrn{ místa. Přeprava zboží z depa do odběrných míst je realizov{na vozidly, kter{ obsluhují okružní trasy začínající a končící depu (uzlu V0). Úlohou je sestavit trasy vozidel tak, aby každé odběrné místo bylo obslouženo pr{vě jedním vozidlem a aby celkové n{klady na přepravu byly minim{lní. Zde n{klady mohou být vyj{dřeny součtem délek všech tras nebo času potřebného pro jejich realizaci.

19

2.5.3.1.

Varianty okružních jízd

Problém okružních jízd m{ velké množství variant a omezujících podmínek, které lze br{t při řešení v úvahu. Ty zapříčiňují rozpad výsledného řešení na více tras (bez dalších omezení by řešení vedlo k jediné trase proch{zející všemi vrcholy a tudíž by se jednalo o klasický problém obchodního cestujícího). V praxi mají úlohy (pro optimalizaci rozvozových tras) nejčastěji podobu kapacitně omezeného problému okružních tras (CVRP) kombinovaného s některými dalšími omezujícími podmínkami. V dalších odstavcích budou pops{ny nejvýznamnější varianty tohoto problému. Kapacitní omezení (CVRP) Nejčastěji využívan{ varianta, ve které mají dod{vky do jednotlivých odběrných míst určenou v{hu (případně objem, počet jednotek nebo jinou veličinu určující kapacitu potřebnou pro přepravu daného zboží). Každé vozidlo m{ pak definov{nu vlastní kapacitu, kter{ určuje, kolik jakých dod{vek je schopné pojmout (zde je viditeln{ souvislost s problémem plnění z{sobníku). Jelikož je kapacitně omezen{ úloha významn{ pro tuto pr{ci, je níže uvedena i její form{lní definice [33]. Nechť jsou d{ny n{sledující vstupy: s … místo v distribuční síti označující centr{lní depo J … množina odběrných míst (z{kazníků) bj … kapacitní požadavky (na odběr zboží) jednotlivých z{kazníků dij … vzd{lenost mezi místy v distribuční síti (včetně depa) R … množina dostupných vozidel Kr … kapacity jednotlivých vozidel Nechť proměnn{ xijr označuje pro všechny dvojice míst a pro všechna vozidla rozhodnutí, jestli dané vozidlo pojede po trase mezi dvěma místy: xijr = 1, pokud vozidlo r pojede po trase mezi místy i a j. xijr = 0, pokud vozidlo r po trase mezi místy i a j nepojede. Cílem je minimalizovat n{sledující účelovou funkci, kter{ vyjadřuje celkovou ujetou vzd{lenost všech vozidel.

20

∑ ∑ ∑ Při minimalizaci však musejí být splněny n{sledující podmínky: ∑ ∑ (každý z{kazník bude obsloužen pr{vě jednou) ∑

∑

(vozidlo, které do místa vjede, z něj i vyjede) ∑

∑

(kapacitní požadavky z{kazníků přiřazených k vozidlu nepřes{hnou jeho kapacitu) ∑ ∑

| |

| |

(sada podmínek, které zajišťují, že trasy vozidel proch{zejí depem a tvoří uzavřené sledy míst, z nichž se ž{dné neopakuje) Časov{ okna (VRPTW) Každé odběrné místo v síti m{ definov{no časové okno, kdy je možné jej obsloužit. Okna jsou určena časovým intervalem (v r{mci jednoho dne). Trasy je nutné pl{novat tak, aby dané vozidlo dorazilo do každého odběrného místa v průběhu jeho časového okna. V praxi se aplikuje v situacích, kdy někteří z{kazníci nemohou nebo nejsou ochotni přijmout zboží během celé pracovní doby. Heterogenní vozový park (HFVRP) V této verzi je k dispozici omezený počet vozidel, které mohou mít odlišné parametry (ve většině případů kapacitu, ale i další omezení relevantní pro přepravu zboží). V praxi se tento případ velmi často kombinuje s kapacitním omezením.

21

Omezen{ doba trv{ní trasy Je d{na podmínka omezující maxim{lní čas pro realizaci jedné trasy (například z důvodu omezené pracovní doby rozvozní společnosti). Současný svoz a rozvoz (VRPPD) Během zast{vky v odběrném místě je možné realizovat vykl{d{ní i nakl{d{ní zboží. Při pl{nov{ní kapacit je nutné br{t v úvahu také zboží, které bude v jednotlivých místech vyzvednuto. 2.5.4. Zn{mé metody pro řešení VRP Pro řešení problému okružních jízd jsou nejčastěji využív{ny klasické heuristiky. V posledních letech se také začínají využívat metody nazývané jako metaheuristiky [34]. 2.5.4.1.

Metaheuristiky

Na rozdíl od klasických (deterministických) heuristik, jsou tyto optimalizační metody většinou stochastické (využívají n{hodného chov{ní) a snaží se přiblížit optim{lnímu řešení pomocí lok{lních změn. Jejich efektivita při řešení dopravních problémů však zatím nebyla plně prok{z{na. Z některých provedených srovn{ní metaheuristik s klasickými heuristickými metodami lze usoudit, že časov{ n{ročnost jejich výpočtu roste neúměrně (v porovn{ní s heuristikami) v z{vislosti na velikosti instance dopravního problému (počtu míst). Přitom metaheuristiky ve většině případů poskytly pouze horší nebo srovnatelně kvalitní řešení. Pokud některé úzce specializované metaheuristiky poskytly kvalitnější řešení, jednalo se o zanedbatelný rozdíl v rozmezí 0 až 2 procent (podle parametru optimalizace). Na

n{sledujících

ř{dcích

budou

uvedeny

popisy

metaheuristik

využívaných k řešení kapacitně omezeného problému okružních jízd: -

Mravenčí

kolonie

[35]:

inspirov{na

chov{ním

mravenčích

společenství při hled{ní cest za potravou. Cesty jsou konstruov{ny n{hodně a hladově v jednotlivých cyklech pomocí virtu{lních „mravenců“. Projitím po hraně je zvýšeno její ohodnocení (mravenec na ní zanech{ svůj feromon, který na ni s určitou pravděpodobností

22

přit{hne další mravence). Tímto kumulov{ním feromonu jsou identifikov{ny nejkratší (nejvýhodnější) cesty. -

Genetický algoritmus [35]: je souč{stí evolučních algoritmů, které napodobují přizpůsobov{ní organizmů podle Darwinova principu přírodního výběru. Populace jednotlivých řešení je generov{na po cyklech (generacích). Při tvoření nové generace vznikají nov{ řešení křížením z nejvhodnějších starších řešení. Přitom se využív{ přírodních principů (výběr nejsilnějších, mutace, genetický crossingover).

-

Simulované žíh{ní [35]: je analogií k fyzik{lnímu procesu, při kterém se pevné l{tky při vysokých teplot{ch roztaví a poté se postupně ochlazují, čímž doch{zí k vytvoření pravidelnější struktury (nižší energetický stav). V aplikaci na problém okružních jízd reprezentuje aktu{lní sestava tras jeden stav l{tky a cena aktu{lního řešení představuje energetickou hladinu l{tky.

Z roztaveného

stavu

(inici{lní trasy) se řešení „ochlazuje“ (kles{ cena aktu{lního řešení). Nové řešení je tvořeno n{hodnými modifikacemi z toho původního a je přijato s určitou pravděpodobností z{visející na „teplotě l{tky“. -

Tabu prohled{v{ní [35]: metoda založen{ na postupném lok{lním prohled{v{ní možných řešení. V aktu{lním řešení (s jeho zn{mou cenou) se vybír{ to n{sledující pouze z množiny přímo sousedících. Vybr{n je soused s nejmenší cenou (i když je vyšší, než cena st{vajícího řešení). V paměti je uchov{v{n také tzv. tabu seznam několika posledních řešení, kter{ jsou při výběru zak{z{na (eliminace kr{tkodobého cyklení). Metoda vr{tí vyhledané řešení po určeném počtu iterací nebo v případě, že po několik kroků nedošlo ke zlepšení ceny nalezených řešení.

23

2.5.4.2.

Heuristiky

Nejčastěji jsou pro řešení problému okružních jízd využív{ny klasické deterministické heuristiky. D{le budou pops{ny a porovn{ny (z pohledu časové n{ročnosti a optimality nalezeného řešení) ty nejčastěji používané. Mayerova metoda Tato metoda [36] je vhodn{ pro distribuční sítě s vysokou excentricitou (vysokým poměrem mezi největší a průměrnou vzd{leností míst od rozvozního depa). Je souč{stí dvouf{zových postupů, které pro problém okružních jízd využívají princip cluster-first route-second [37] (v první f{zi jsou uzly rozděleny do skupin, ve druhé f{zi jsou uzly v jednotlivých skupin{ch seřazeny do tras). Mayerova metoda řeší pouze první f{zi úlohy a snaží se uzly v distribuční síti roztřídit do několika skupin, které odpovídají jednotlivým tras{m. Pro druhou f{zi (seřazení uzlů v r{mci každé trasy) kter{ už odpovíd{ standardnímu problému obchodního cestujícího, je nutné použít nějaký jiný zn{mý algoritmus nebo heuristiku. Skupiny (trasy) jsou vytv{řeny postupně. Do nové skupiny je jako první zařazen zatím nepřiřazený uzel, který je nejvzd{lenější od centr{lního depa. D{le je do skupiny přid{v{n vždy uzel nejbližší některému uzlu, který už ve skupině je. Pokud se metoda pokusí do skupiny přidat uzel, který už překročí její kapacitu, st{vající skupina se uzavře a začne se tvořit nov{. Metodu lze také upravit z minimalizace délky tras na minimalizaci jejich počtu. Pokud se algoritmus pokusí přidat do skupiny uzel, který překročí její kapacitu, neuzavře ji automaticky, ale nejdříve se ještě snaží najít další co nejbližší uzly, které by se kapacitně do skupiny vešly. Tím lze za cenu vytvoření delších tras minimalizovat jejich počet. Fernandez de la Vega - Luekerova metoda Stejně jako Mayerova, zabýv{ se tato metoda [36] pouze rozdělením uzlů do skupin (tras), ale už neřeší jejich pořadí v trase. Původně se jedn{ o aproximační schéma s polynomi{lní časovou složitostí (PTAS) [38] pro řešení problému plnění z{sobníků (BPP), které je však aplikov{no na kapacitně omezený problém okružních jízd.

24

Princip tkví v rozdělení uzlů podle jejich kapacitního požadavku (např. v{hy) na velké a malé. Hranice pro toto rozdělení je d{na parametrem určujícím požadovanou přesnost schématu. Velké uzly jsou do skupin umisťov{ny optim{lně a malé pak metodou first-fit. Metodu lze rozdělit na kapacitní a vzd{lenostní verzi, které se liší přístupem k rozdělov{ní „malých“ uzlů. Ve vzd{lenostní variantě jsou z malých uzlů vybír{ny nejdříve ty nejvzd{lenější od centr{lního depa a jsou zařazov{ny do skupiny (pokud m{ dostatečnou kapacitu), kter{ již obsahuje uzel nejbližší tomu zpracov{vanému. Kapacitně zaměřen{ metoda nejdříve setřídí okruhy vystavěné z velkých uzlů sestupně podle sumy kapacit. Pak setřídí sestupně podle kapacit i všechny malé uzly. Ty jsou potom zpracov{v{ny a v daném pořadí zatřiďov{ny vždy do první skupiny (podle daného pořadí), kter{ m{ dostatečnou volnou kapacitu. Metoda Clarke-Wright Někdy také označovan{ jako metoda výhodnostních koeficientů nebo výhodnostních čísel [39]. Na rozdíl od Mayerovy a Luekerovy metody nepatří mezi dvouf{zové postupy, ale řeší obě č{sti problému okružních jízd současně a vrací již kompletní seznam vytvořených tras. Principem algoritmu je slučovat kratší trasy do delších podle výhodnosti takových spojení (a za splnění omezujících podmínek). Postup je n{sledující: -

Sestavíme matici vzd{leností D pro všechny uzly v síti (depo a odběrn{ místa), kde dij = vzd{lenost uzlů i a j.

-

Vytvoříme inici{lní řešení, které obsahuje samostatnou okružní trasu (začínající a končící v depu) pro každý uzel, který m{ být obsloužen.

-

Z matice vzd{leností odvodíme matici výhodnostních koeficientů Z. Pro každou dvojici uzlů i a j je koeficient zij = d0i + d0j - dij a určuje tak vzd{lenost, kter{ by mohla být ušetřena, pokud by se dané trasy sloučily do jedné v bodech i a j.

-

Opakovaně vybír{me z matice výhodnostních koeficientů ten s nejvyšší kladnou hodnotou. Pokud už matice takovou hodnotu neobsahuje, ukončíme algoritmus a vr{tíme doposud vypočítané trasy jako výsledné řešení. Pokud takov{ hodnota existuje:

25

o

Pokusíme se spojit trasy, jejichž souč{stí jsou uzly určující pr{vě zpracov{vaný koeficient. Pokud nevznikne přípustn{ trasa (zde probíh{ kontrola všech omezujících podmínek včetně kapacity), nastavíme pr{vě zpracov{vaný koeficient na nepřípustnou hodnotu, přeskočíme n{sledující krok a pokračujeme výběrem dalšího koeficientu. Pokud spojením vznikne přípustn{ trasa, pokračujeme n{sledujícím bodem.

o

Vyjmeme z množiny uzlů ty, které určují zpracov{vaný koeficient (pokud po sloučení tras přestaly být krajními uzly). Nastavíme pr{vě zpracov{vaný výhodnostní koeficient na nepřípustnou hodnotu, vyjmeme z řešení pr{vě slučované trasy a vložíme místo nich novou trasu. Aktualizujeme ostatní sledované parametry (délka a čas trasy, využit{ kapacita…).

Metoda Clarke-Wright se dočkala během doby své existence mnoha modifikací. Díky konstrukci algoritmu je vhodný pro začlenění omezujících podmínek a dalších úprav. Pro řešení kapacitně omezeného problému okružních jízd je většinou použív{na neomezen{ paralelně postupující varianta. Při výpočtu doch{zí prim{rně k minimalizaci délky tras, ale současně doch{zí i k minimalizaci jejich počtu (pokud by to neprodloužilo výsledné řešení). Habrovy frekvence Český profesor ekonomie Jaroslav Habr se pokusil vylepšit ClarkeWrightovu metodu zavedením tzv. frekvencí [36]. Jsou obdobou výhodnostních koeficientů, ale na rozdíl od nich neberou v úvahu pouze vzd{lenosti mezi dvěma počítanými body. Při výpočtu výhodnosti sloučení tras obsahujících body i a j hrají roli také vzd{lenosti mezi ostatními uzly v distribuční síti. Habrova frekvence přímé cesty mezi uzly i a j se počít{ podle n{sledujícího vzorce: ∑ ∑ Vzorec lze také modifikovat na jeho výpočtový tvar:

26

Zde ri a sj zastupuje aritmetický průměr vzd{leností v i-tém ř{dku a j-tém sloupci matice vzd{leností mezi uzly. 2.5.5. Srovn{ní metod Pro účely této pr{ce je nutné porovnat vhodné metody pro řešení kapacitně omezeného problému okružních jízd. Efektivita praktického využití uvedených metaheuristik pro řešení této úlohy ještě nebyla prok{z{na tak jako u klasických heuristik. 2.5.5.1.

Heuristiky a metaheuristiky

Jedna z prací [40] uv{dí například srovn{ní genetického algoritmu s klasickou heuristikou při řešení n{sobného problému obchodního cestujícího (ten se definicí velmi blíží VRP). Standardní genetický algoritmus je zde postaven vedle dvouf{zové heuristiky využívající v první f{zi metodu k-průměrů pro shlukovou analýzu (k-means clustering) a ve druhé f{zi algoritmus nejbližšího souseda (NNA) pro řešení problému obchodního cestujícího. Z výsledků získaných aplikací obou metod na 10 testovacích příkladů (vždy po 30 uzlech) vyplýv{, že délky tras vypočítaných genetickým algoritmem byly vždy o zhruba 20 až 40 procent vyšší a čas jeho výpočtu byl 15 kr{t delší než u klasické heuristiky. Další série testů zkoumala vliv růstu počtu uzlů na vhodnost nalezeného řešení a čas výpočtu obou metod. Výsledky zpracov{ní deseti příkladů s počty uzlů od 10 do 100 uk{zaly, že se zvyšujícím se počtem zpracov{vaných uzlů se zvyšuje čas výpočtu genetického algoritmu až na 2 minuty (zatímco čas výpočtu klasické heuristiky zůstal i při 100 uzlech v rozsahu 2 až 3 sekund). D{le je vidět, že celkov{ délka tras vypočítaných genetickým algoritmem je pro 10 uzlů srovnateln{ s řešením klasické heuristiky. Se zvyšujícím se počtem uzlů však efektivita metaheuristiky výrazně kles{ a při 100 uzlech je nalezen{ sestava tras téměř třikr{t delší než řešení dvouf{zové heuristiky. Další z dostupných prací [41] se zabývala porovn{ním širší palety heuristik a metaheuristik na instanci standardního problému obchodního cestujícího s 20 uzly. Díky tomu, že byla distribuční síť testovacího příkladu modelov{na podle re{lných dat na území Prahy, jsou získané výsledky blízké re{lnému nasazení daných metod.

27

Z

výsledků vyplýv{, že standardní verze genetického algoritmu

vyk{zala o 35 procent delší řešení, než bylo to optim{lní. Ze z{stupců klasických heuristik lze uvést metodu nejbližšího souseda (optimum + 16%), metodu pro hled{ní minim{lní kostry (optimum + 14%) a metodu výhodnostních čísel (optimum + 2%). Je ale třeba pouk{zat i na to, že hybridní verze genetického algoritmu modifikovan{ pro zadaný příklad dos{hla v uvedené pr{ci srovnatelných výsledků jako nejefektivnější klasické heuristiky. Z analýzy výsledků uvedených a dalších prací je patrné, že využití metaheuristik při řešení různých variant dopravních problémů je časově n{ročnější. Oproti klasickým heuristik{m také zatím nepřin{ší výrazné zlepšení v délce generovaných tras. Z toho důvodu budou v n{sledujících odstavcích srovn{v{ny pouze deterministické (klasické) heuristické metody. 2.5.5.2.

Srovn{ní klasických heuristik

Důležitými aspekty, které je třeba u jednotlivých metod sledovat, jsou hlavně efektivita minimalizace celkové délky tras (v poměru k optim{lnímu řešení), jejich počtu, doba běhu výpočtu a možnost začlenění glob{lních i lok{lních omezujících podmínek. Nejdůležitějším parametrem z pohledu této pr{ce je délka výsledných tras. Testov{ní

klasických

heuristických

metod

pro

řešení

problému

okružních jízd se věnuje například disertační pr{ce RNDr. Petra Kučery Ph.D. [36], kter{ vybrané metody aplikuje na několik variant daného problému. Pro kapacitně omezenou verzi úlohy bylo v uvedené pr{ci vygenerov{no 10 n{hodných příkladů, které byly řešeny Mayerovou metodou (MM), Mayerovou metodou pro minimalizaci okruhů (MMMO), kapacitně (KFLV) i vzd{lenostně (VFLV) zaměřenou metodou Fernandez de la Vega, metodou výhodnostních čísel (Clarke-Wright, CW) a aplikací Habrových frekvencí (HF). Pro jednotlivé příklady a metody byly poté sledov{ny součty výsledných tras a počty potřebných vozidel. Z údajů o provedených testech uvedených ve zmíněné pr{ci lze odvodit n{sledující přehledovou tabulku průměrných výsledků jednotlivých metod:

28

Tab. 1 - Porovn{ní efektivity heuristických metod pro CVRP Celková délka tras Počet tras

Optimum 100% 4

MM 108,4% 5,1

MMMO 112,5% 4,7

KFLV 119,8% 4,2

VFLV 110,1% 4,3

CW 101,5% 4,9

HF 101,8% 4,7

Z tabulky je patrné, že nejlepšího výsledu při optimalizaci délky tras dos{hla metoda Clarke-Wright. Trasy vypočtené tímto postupem byly v průměru pouze o 1,5 procenta delší než trasy obsažené v optim{lním řešení. Další velmi efektivní metodou byla aplikace Habrových frekvencí. Ostatní postupy již z pohledu délky tras nebyly tak úspěšné. V minimalizaci počtu tras se projevily jako nejvhodnější obě verze metody Fernandez de la Vega. Jimi vypočítané trasy však byly jedněmi z nejdelších. V oblasti rozšiřitelnosti a možnosti modifikace je nejvhodnějším kandid{tem pro využití v praxi metoda Clarke-Wright. Díky konstrukci algoritmu je možné jej jednoduše upravit pro konkrétní požadavky a začlenit do něj kontrolu různých omezujících podmínek. Vzhledem k zanedbatelným rozdílům v rychlosti výpočtu jednotlivých metod (na příkladech s rozsahem do 100 uzlů se všechny pohybují v ř{du maxim{lně desítek vteřin) je třeba posuzovat vhodnost analyzovaných heuristik pro účely této pr{ce podle výše uvedených údajů. Díky nejefektivnější optimalizaci délky tras a snadné rozšiřitelnosti se jeví jako nejvhodnější metoda Clarke-Wright. Tento algoritmus je pro řešení rozvozních

úloh

v praxi

využív{n

nejčastěji

(jak

v experiment{lních

a nekomerčních projektech, tak i v mnoha placených sofistikovaných řešeních), jeho nasazení je tedy prověřeno re{lnými aplikacemi.

29

2.6.

Požadavky na modul V n{sledující č{sti budou uvedeny požadavky na modul realizovaný

v praktické č{sti této pr{ce. Ty definují jednotlivé funkce a vlastnosti, které by měl vyvíjený n{stroj z pohledu uživatele poskytovat. Vzhledem k omezení rozsahu pr{ce nebude realizovaný modul plně pokrývat všechny procesy a úlohy uvedené v kapitole Analýza procesů a úloh v r{mci distribuce zboží. 2.6.1. Funkční požadavky Definují požadovanou funkcionalitu systému (funkce, které bude systém poskytovat jeho uživatelům). -

Autentizace a autorizace uživatelů na z{kladě rolí v systému

-

Evidence a spr{va uživatelů v systému

-

Evidence a spr{va vozového parku

-

Evidence a spr{va odběrných míst

-

Evidence a spr{va údajů o rozvozovém depu

-

Evidence a spr{va vratných obalů pro potřeby pl{nov{ní distribuce

-

Evidence a spr{va vygenerovaných a realizovaných přepravních pl{nů

-

Přiřazení řidičů k evidovaným vozidlům

-

Zařazení nezpracovaných dod{vek do přepravního pl{nu

-

Upravení priority dod{vek v r{mci přepravy

-

Automatické generov{ní přepravního pl{nu pro zadaný den dle zadaných kritérií (operativní pl{nov{ní distribuce)

-

Zobrazení přepravního pl{nu a jeho tras na statickém mapovém podkladu

-

Manu{lní úprava vygenerovaných pl{nů

-

Export tras do form{tu GPX pro použití v navigačních zařízeních

-

Realizov{ní vybraných přepravních pl{nů

30

2.6.2. Nefunkční požadavky Označují požadované vlastnosti a omezení vyvíjeného

systému

(například hardwarové n{roky nebo garantovanou efektivitu a spolehlivost). -

Modul bude kompatibilní s nejrozšířenějšími operačními systémy

-

Pro uchov{ní vlastních dat bude využív{n neplacený datab{zový systém

-

Uživatelé budou modul využívat přes vytvořené grafické rozhraní

-

Data o dod{vk{ch budou získ{v{na z datab{ze informačního systému pro řízení obchodů a skladů

-

Geografické informace pro optimalizaci tras bude modul získ{vat z volně dostupné webové služby

-

Výpočet optimalizace přepravních pl{nů (v ř{du do stovek odběratelů) bude probíhat v rozumném čase (do 10 minut)

-

Použitý algoritmus bude prim{rně minimalizovat délku tras a sekund{rně jejich počet

-

Použitý algoritmus bude při přiřazov{ní dod{vek na vozidla respektovat dostupnost vozidel, jejich nosnost, objem n{kladového prostoru a maxim{lní rozměry zboží, které je do n{kladového prostoru možné naložit

-

Použitý algoritmus bude při generov{ní tras respektovat maxim{lní čas pro obsloužení trasy (v z{vislosti na průměrné rychlosti přiřazeného vozidla, délce trasy a době nutné pro vyložení dod{vek u odběratelů)

-

Použitý algoritmus bude při řazení dod{vek do tras zohledňovat prioritu dod{vek

-

Použitý algoritmus bude při pl{nov{ní využití kapacit vozidel br{t v úvahu množství vratných obalů, jejichž zpětný odvoz by odběratelé mohli požadovat

31

2.7.

Případy užití Tato podkapitola se věnuje případům užití realizovaného modulu. Ty

definují interakci uživatelů se systémem a jsou zde zachyceny ve formě use case diagramů [42]. Níže jsou uvedeny diagramy pro obě uživatelské role. 2.7.1. Řidič Tato role slouží pro řidiče podniku a po přihl{šení do modulu jim umožňuje zobrazit trasu, kterou mají v aktu{lní datum realizovat (pokud takov{ je), zobrazit její mapu a exportovat si trasu do navigačního zařízení.

Obr. 1 – Diagram užití role řidič 2.7.2. Dispečer Role dispečera je určena pro celkovou spr{vu a obsluhu modulu a jím evidovaných dat. Umožňuje zakl{dat, editovat a archivovat uživatele a vozidla, editovat údaje o rozvozovém depu a odběrných místech a generovat a spravovat přepravní pl{ny a jejich trasy.

32

Obr. 2 – Diagram užití role dispečer

33

3.

N{vrh a implementace Hlavním cílem praktické č{sti této pr{ce je navrhnout a realizovat modul

pro automatickou optimalizaci rozvozových tras. V analytické č{sti byly rozebr{ny všechny důležité logistické procesy a situace, se kterými je možné se při pl{nov{ní rozvozu setkat. Vzhledem k omezenému rozsahu pr{ce se bude navržený n{stroj soustředit na podporu a optimalizaci těch procesů, které se mohou výrazným způsobem projevit na snížení n{kladů na přepravu zboží. Modul bude určen pro nasazení do jednoho rozvozového depa s vlastním heterogenním vozovým parkem, který bude složen pouze ze silničních vozidel. V případě nasazení do podniku, který disponuje více rozvozovými depy, by bylo třeba provést rozdělení distribuční sítě mezi jednotliv{ depa. Poté lze modul nasadit do každého depa a použít jej pro pl{nov{ní přepravy v relevantní č{sti distribuční sítě. Modul také nebude poskytovat n{stroje pro detailní optimalizaci naložení n{kladního prostoru jednotlivých vozidel. Při optimalizaci bude trasy rozvrhovat tak, aby celkový n{klad (s určitou prostorovou rezervou) bylo možné na vozidlo umístit a aby nebyla překročena nosnost vozidla ani rozměry n{kladového prostoru. Určení pořadí nakl{d{ní dod{vek a jejich umístění na vozidlo už však přenech{ na uv{žení person{lu. Pro tento úkol je také možné využít jiný dostupný software, ale úspora n{kladů v tomto případě není výrazn{. V n{sledujících podkapitol{ch budou uvedeny detaily n{vrhu a implementace jednotlivých č{stí modulu.

3.1.

Použití technologií Pro realizaci zadaného modulu bylo nutné vybrat vhodné softwarové

n{stroje a technologie. Těm je věnov{na tato kapitola. Kromě popisu uv{dí také důvody k jejich výběru a jiné použitelné varianty. 3.1.1. Vývojové n{stroje Pro analýzu a n{vrh softwaru jsou nejčastěji využív{ny CASE n{stroje, které umožňují zachytit modelovaný systém nebo aplikaci v různých úrovních abstrakce ve formě diagramů. J{drem těchto n{strojů býv{ jednotný

34

modelovací jazyk UML [43] pro vytv{ření vývojových diagramů. Podporuje objektově orientovaný vývoj a poskytuje širokou šk{lu diagramů, z nichž nejpoužívanější jsou: -

Diagram tříd

-

Diagram komponent

-

Diagram aktivit

-

Diagram užití

-

Sekvenční diagram Kromě UML poskytuje většina CASE n{strojů také prostředky pro

datové modelov{ní ve formě ERD [44] a další specializované modelovací standardy. Existuje velké množství placených i neplacených CASE n{strojů. Z těch nejvyužívanějších lze jmenovat Enterprise Architect nebo MS Visio. Dalším z používaných produktů je Visual Paradigm for UML [45]. Ten v aktu{lní verzi 10.1 podporuje modelovací standardy UML 2.4, ERD, BPMN 2.0, SysML a další. Ve variantě Community Edition je bezplatně dostupný pro nekomerční využití. Z těchto důvodů byl Visual Paradigm zvolen pro analýzu a n{vrh modulu, který je předmětem této pr{ce. 3.1.2. Jazyk a vývojové prostředí Pro implementaci modulu bylo nutné zvolit také vhodný programovací jazyk. Vzhledem k mnoha výhod{m je pro implementaci informačních systémů v dnešní době nejčastěji použív{no objektově orientované programov{ní. Z tohoto konceptu vych{zí velké množství programovacích jazyků. Jmenovat lze například C++ nebo Java. Vzhledem k požadavku, aby byl modul použitelný na hlavních používaných operačních systémech, je nejvhodnější volbou objektový jazyk Java [46] vyvinutý firmou Sun Microsystems. V něm napsané aplikace jsou díky způsobu interpretace kódu multiplatformní. Pro implementaci modulu byl proto zvolen pr{vě tento jazyk. I když je možné samotný kód ps{t v jakémkoliv textovém editoru, volba spr{vného vývojového prostředí dok{že výrazně urychlit tvorbu jakékoliv

35

aplikace. Vývojové prostředí (IDE) většinou poskytuje editor kódu, kompil{tor, debugger a někdy i další n{stroje usnadňující například n{vrh grafického prostředí. Z vývojových prostředí pro jazyk Java bylo použito bezplatně dostupné prostředí NetBeans IDE ve verzi 7.1.2 [47]. 3.1.3. Datab{ze Jelikož modul uchov{v{ a spravuje vlastní data (o uživatelích, vozovém parku, přepravních tras{ch…), potřebuje pro svou činnost datab{zový systém. Vzhledem k zaměření modulu na využití v menších a středně velkých firm{ch je požadov{na volba neplaceného datab{zového systému. Mezi těmi jsou nejčastěji využívané datab{ze MySQL, PostgreSQL, Apache Derby a Firebird SQL. Všechny uvedené technologie jsou dostupné i v neplacené verzi. Pro účely této pr{ce byla zvolena datab{ze MySQL [48] ve verzi 5.5. Ta je k dispozici pod licencí GPL [49], a lze ji bezplatně využít i pro komerční účely. MySQL je určena pro použití v prostředí Windows, Linux a dalších operačních systémů. Jazyk Java využitý při implementaci však poskytuje jednotné rozhraní JDBC pro připojení k datab{zi pomocí ovladačů (konektorů). Díky tomu je možné Java aplikace jednoduše upravit pro použití jiné datab{zové technologie než zvoleného MySQL. 3.1.4. Grafické uživatelské prostředí Pro vytvoření grafického prostředí na platformě Java slouží různé druhy knihoven a frameworků. Jedním z nejstarších n{strojů pro tvorbu GUI v Javě je AWT, v porovn{ní s novějšími knihovnami však postr{d{ složitější komponenty. Kvůli tomu byl na z{kladě AWT vyvinut pokročilejší n{stroj Swing. Ten již obsahuje i většinu složitějších komponent a je vhodný pro vytv{ření plnohodnotných grafických prostředí. Novějším a ještě ne zcela rozšířeným n{strojem je JavaFX. Pro vytvoření grafického prostředí navrženého logistického modulu byla použita knihovna Swing [50]. Použité vývojové prostředí NetBeans IDE obsahuje také designérský n{stroj pro tvorbu grafického prostředí pr{vě pomocí této knihovny.

36

3.1.5. Geografick{ data a mapy Pro automatickou optimalizaci rozvozových tras je nutné zn{t vzd{lenosti mezi jednotlivými místi v distribuční síti. Pro menší množství st{lých odběrných míst je možné vzd{lenosti zad{vat a udržovat ručně. V případě většího množství odběratelů nebo jejich časté obměny by už ruční údržba nebyla re{ln{. Proto je vhodné vzd{lenosti jednotlivých míst v rozvozové síti doplňovat automaticky z veřejně dostupných zdrojů. Místa v distribuční síti je také vhodné zobrazit na mapovém podkladu pro vizu{lní kontrolu jejich polohy. Stejným způsobem lze zobrazit také vypočítané trasy. Podle požadavků bylo třeba vybrat jednu z dostupných mapových technologií, které poskytují neplacenou službu pro určov{ní vzd{leností (v silniční síti) a také možnost zobrazit tato místa na mapových podkladech pro uživatele navrženého modulu. Jedním z nejrozšířenějších řešení v této oblasti je kolekce služeb Google Maps [51]. Poskytuje velké množství n{strojů pro pr{ci s mapovými podklady, geografickým kódov{ním a výpočtem jednoduchých tras. Službou zvolenou pro určení vzd{leností je Google Directions API, ta na z{kladě HTTP požadavku počít{ trasu mezi dvěma místy v silniční síti (včetně její délky). V bezplatné licenci je možné provést denně 2500 dotazů, což odpovíd{ vypočít{ní vzd{leností mezi 50 místy v odběrné síti. Zmenšení počtu dotazů na službu lze dos{hnout ukl{d{ním vypočítaných vzd{leností pro další použití. V případě, že by limit nevyhovoval, je možné jej navýšit na sto tisíc dotazů denně zakoupením licence Google Maps API for Business. Pro zobrazení tras a míst na mapových podkladech byla zvolena služba Google Static Maps API. Ta pro HTTP požadavek vr{tí statickou mapu ve formě rastrového obr{zku. Do mapy lze při zad{v{ní dotazu vložit značky míst a spojnice mezi místy (představující trasy). Limit bezplatné verze činí 25000 zobrazení mapy pro aplikaci a 1000 zobrazení mapy pro uživatele za jeden den. Tyto limity jsou pro účely modulu dostačující.

3.2.

Volba a implementace algoritmu pro optimalizaci Ze srovn{ní uvedeného kapitole Optimalizační metody vyplýv{, že pro

potřeby navrženého modulu je nejvhodnější optimalizační metoda Clarke-

37

Wright. Ta se uk{zala jako nejefektivnější při minimalizaci celkové délky vypočítaných tras. Rychlost jejího výpočtu vzhledem k počtu míst v distribuční síti je také velmi dobr{ a počet tras minimalizovala ve srovn{ní s ostatními metodami průměrně. Z výše uvedených důvodů byla pro navržený modul použita pr{vě optimalizační metoda Clarke-Wright. Algoritmus pro optimalizaci tras je pro potřeby tohoto modulu nutné upravit. Modifikace se týkají heterogenního vozového parku, omezujících podmínek pro trasy a dod{vky, priorit dod{vek a pl{nov{ní svozu vratných obalů. Provedené modifikace budou pops{ny v n{sledujících odstavcích. 3.2.1. Úpravy pro heterogenní vozový park Vybraný algoritmus je původně určen pro pl{nov{ní rozvozu pomocí homogenního

vozového

parku.

Vzhledem

k požadavku,

aby

modul

optimalizoval rozvozové trasy heterogenního vozového parku, bylo nutné provést n{sledující úpravy. Při vytv{ření inici{lních tras jsou jim přiřazena imagin{rní vozidla (pro potřeby algoritmu) takov{, aby dostačovala pro realizaci jednotlivých dod{vek. Všechna dostupn{ re{ln{ vozidla (z udržovaného vozového parku) jsou označena jako nepoužit{. Při slučov{ní dvojic tras (podle Clarke-Wrightovy metody) se postupuje n{sledně: -

Vozidla obou původních tras jsou označena jako nepoužit{ a trasy jsou sloučeny do jedné nové trasy.

-

Nové trase je přiřazeno vozidlo z množiny re{lných nepoužitých vozů, které splňuje podmínky pro naložení všech dod{vek nové trasy (dodržena maxim{lní nosnost, objem, rozměry, doba přepravy) a které m{ z této množiny nejmenší nosnost. To je označeno jako použité. Vzhledem ke slučov{ní tras od nejvýhodnějších spojení bude zaručeno, že nejvýhodnější trase bude přijatelné vozidlo přiřazeno jako první. Výběrem vyhovujícího vozidla s nejmenší nosností je zaručeno, že pro tvorbu n{sledujících tras zůstanou k dispozici vozy s co největší kapacitou a vypočítané řešení tak bude nejlepší možné.

38

Po dokončení slučovací č{sti algoritmu je k dispozici množina výsledných tras, které mají přiřazeny re{ln{ vyhovující vozidla. V případě vyčerp{ní kapacity vozidel se může st{t, že je vr{cena také množina několika inici{lních tras, které mají st{le přiřazena imagin{rní vozidla. Ty nebylo možné sloučit se ž{dnou jinou trasou tak, aby vytvořily okruh realizovatelný dostupným re{lným vozidlem. Jelikož však přiřazov{ní re{lných vozů probíh{ až při f{zi prvního slučov{ní, je možné, že v tomto momentu st{le existují nevyužit{ re{ln{ vozidla, kter{ jsou vhodn{ pro obsloužení některé ze zbylých inici{lních tras (ale neměla dostatečnou kapacitu pro obsloužení sloučených tras). Kvůli tomu po slučovací f{zi algoritmus pokračuje n{sledujícím krokem: -

Pokud byly vr{ceny nějaké trasy, které mají přiřazeno imagin{rní vozidlo a pokud ještě existují nějak{ re{ln{ nevyužit{ vozidla, pokusí se tras{m postupně přiřadit nevyužit{ re{ln{ vozidla. Po tomto kroku obsahuje množina tras s re{lnými vozidly ty okruhy,

které bude možné realizovat. Množina zbylých inici{lních tras s imagin{rními vozidly představuje dod{vky, které z kapacitních důvodů není možné v r{mci dané přepravy rozvézt. 3.2.2. Úpravy pro kapacitní a jin{ omezení tras Podle požadavků na vyvinutý modul m{ vybraný algoritmus tvořit rozvozové trasy, které budou dodržovat uvedené omezující podmínky. Ty se týkají v{hových, objemových a rozměrových omezení jednotlivých vozidel. U každého vozidla je v systému evidov{na jeho maxim{lní nosnost, maxim{lní využitelný objem n{kladového prostoru (musí respektovat určité rezervy pro manipulaci s n{kladem) a jeho rozměry. U jednotlivých balíků (položek dod{vky) pak systém umožňuje převzít jejich v{hu, objem i rozměry (z informačního systému rozvozní společnosti). Ne každý podnik však disponuje informačním systémem, který by při procesu balení evidoval všechny tyto údaje. Pokud některý z nich není u položek dod{vek k dispozici, lze jej pro potřeby modulu vynechat (nastavit

39

na nulovou hodnotu). Algoritmus bude kontrolovat pouze ty omezující podmínky, které jsou nenulové. Dalším omezením tras vyplývajícím z požadavků na modul je maxim{lní doba pro jejich obsloužení. Ta býv{ většinou určena pracovní dobou přepravní společnosti. Předpokl{dan{ doba obsluhy dané trasy je určena několika údaji. V první řadě jde o délku celé trasy a průměrnou rychlost vozidla, které je k trase přiřazeno. D{le jsou do této doby započít{ny přest{vky v jízdě. Během nich je vykon{v{na vykl{dka a nakl{dka v jednotlivých odběrných místech. Délka vykl{dky je d{na počtem položek dané dod{vky a průměrnou dobou potřebnou pro naložení nebo vyložení jednoho balíku (pro dané vozidlo). Podle legislativy platné v ČR [52] je řidič povinen dodržovat také bezpečností přest{vky (během nichž nesmí vykon{vat ž{dnou pracovní činnost) v délce 45 minut vždy po 4,5 hodin{ch jízdy. Vyvinutý modul tedy započít{ přest{vku v délce 45 minut za každé 4 a půl hodiny trv{ní trasy. Všechny výše uvedené omezující podmínky jsou kontrolov{ny vždy při vytv{ření nových tras. K tomu doch{zí ve slučovací f{zi algoritmu, když jsou nové trasy vytv{řeny spojením dvou st{vajících a je jim přiřazeno vhodné vozidlo, a také v ukončovací f{zi při přiřazov{ní nepoužitých vozidel zbylým inici{lním tras{m (viz. Úpravy pro heterogenní vozový park). Suma hmotností a objemů všech balíků je porovn{na s v{hovou a objemovou kapacitou přiřazeného vozidla, rozměry každého balíku jsou porovn{ny s rozměry n{kladového prostoru (aby ž{dný rozměr nepřesahoval) a vypočítaný předpokl{daný čas trasy je porovn{n s maxim{lní dobou trv{ní trasy zadanou při spouštění algoritmu. Pokud je někter{ z podmínek porušena, je trasa vyhodnocena jako neplatn{. 3.2.3. Úpravy pro svoz materi{lů Podle požadavků m{ modul pl{novat kromě rozvozu dod{vek také svoz vratných obalů. Původní metoda Clarke-Wright pro takové pl{nov{ní není přizpůsobena, a proto bylo nutné algoritmus upravit. Pro spr{vné vyhodnocení si modul ukl{d{ množství a typy vratných obalů, které dodal do evidovaných odběrných míst. V případě, že dané odběrné

40

místo některé obaly vr{tí, jsou z evidence odečteny. Modul tak m{ k dispozici počet a druhy vratných obalů, které m{ každý odběratel aktu{lně u sebe uschov{ny. Jelikož nebude systém podporovat (vzhledem k rozsahu pr{ce) avizaci požadavků na zpětný svoz, nebude při pl{nov{ní přepravy předem zn{mé množství obalů, které budou odběratelé chtít vr{tit. Tento problém řeší navržený modul zavedením několika úrovní nastavení pro zpětný svoz: -

Neprioritizovat svoz obalů: algoritmus nebude se svozem obalů vůbec počítat a řidič tak bude moct v odběrném místě přijmout pouze množství vratných obalů, které nepřekročí v{hu a objem pr{vě vyložené dod{vky.

-

Svézt obaly z minulé dod{vky: systém předpokl{d{, že budou chtít odběratelé vr{tit pr{vě ty vratné obaly, které přijal jako souč{st minulé dod{vky. Modul při pl{nov{ní sečte v{hy a objem obalů, které byly souč{stí poslední dod{vky danému odběrateli. Pokud je některý z těchto součtů větší než celkov{ v{ha nebo objem balíků aktu{lní dod{vky, bere algoritmus při ověření překročení kapacity vozidla v úvahu hodnotu součtu z vratných obalů.

-

Svézt všechny obaly: tato volba předpokl{d{, že budou chtít odběratelé vr{tit všechny obaly, které mají aktu{lně ve svém držení. Úprava kontroly pro překročení kapacity vozidel je stejn{ jako u předchozí varianty, ale místo součtu objemu a v{hy obalů z minulé dod{vky je použit součet všech vratných obalů, které jsou v danou chvíli u odběratele evidov{ny. Tyto volby při pl{nov{ní zajišťují, že ve vozidle bude dostatečn{ voln{

kapacita pro příjem vratných obalů. Řidič pak na místě může přijmout tolik obalů, kolik mu volné místo dovolí. Při příjezdu zpět do depa nahl{sí počty a druh obalů svezených od jednotlivých odběratelů přítomnému dispečerovi, který je zad{ do modulu (aby evidence obalů odpovídala skutečnosti). 3.2.4. Úpravy pro prioritu dod{vek Modul poskytuje možnost prioritizovat některé dod{vky v přepravě. Při přiřazení do přepravy m{ dod{vka standardně nastavenu střední prioritu. Tu

41

lze v případě potřeby buď snížit, nebo zvýšit. Celkem je k dispozici 5 prioritních stupňů, které mohou ovlivnit zařazení dod{vek do jednotlivých tras. Jejich využití je vhodné pouze v případě, že dostupn{ vozidla nemají dostatečnou kapacitu pro realizaci pl{nované přepravy. Pokud mají některé dod{vky zůstat neobslouženy, mohou jejich priority výrazně ovlivnit, které to budou. V případě, že mají vozidla dostatečnou kapacitu pro obsloužení všech tras, nepovede změna priorit k ž{dnému kladnému efektu, naopak může způsobit přeskupení a prodloužení některých tras. V případě použití rozdílných priorit doch{zí k úpravě ve výpočtu výhodnostních koeficientů, proto téměř vždy povede k určitému prodloužení celkové délky tras. Každ{ priorita m{ přiřazený koeficient, který určuje, jakou měrou ovlivní výpočet. Výhodnostní koeficient zij pro odběrn{ místa i a j je pak vyn{soben průměrem prioritních hodnot obou odběratelů. Označme prioritní koeficient dod{vky i jako pi a obdobně pro dod{vku j. Výhodnostní funkce je pak upraven{ n{sledovně: zij = (d0i + d0j - dij) * (pi + pj) / 2 Použití norm{lní priority výpočet výhodnostních koeficientů neovlivní. Použité priority Nejnižší, Nižší, Norm{lní, Vyšší a Nejvyšší mají n{sledující hodnoty (v uvedeném pořadí): {1/5; 1/3; 1; 3; 5 }. Jak je vidět z použitého vzorce výhodnostní koeficient je ovlivněn prioritou dod{vek pro obě počítan{ místa. Vyšší priorita pouze upravuje výhodnostní koeficienty pro sloučení s dalšími trasami. Negarantuje však obsloužení dod{vky přednostně před dod{vkami s nižší prioritou. 3.2.5. Úpravy pro minimalizaci počtu tras Navržený algoritmus při tvorbě tras minimalizuje jejich celkovou délku i počet. Slučuje trasy, dokud existuje nějaké spojení s kladným výhodnostním koeficientem (které zmenší délku výsledného řešení). V určitých případech však může dojít k tomu, že jsou výhodnostní koeficienty některých dvojic odběrných míst z{porné. Tato situace nast{v{, pokud je v č{sti distribuční (silniční) sítě porušena trojúhelníkov{ nerovnost,

42

a představuje takov{ sloučení tras, kter{ mohou vést ke snížení počtu tras, ale zcela jistě povedou ke zvýšení délky výsledného řešení. Velikost z{porných koeficientů nebýv{ v poměru k délce tras významn{. V některých případech je tedy vhodné se za cenu mírného prodloužení tras pokusit snížit počet potřebných vozidel. Vytvořený algoritmus proto umožňuje na vstupu určit, jestli se mají zpracov{vat pouze kladné výhodnostní koeficienty (optimalizace podle délky tras) nebo m{ slučov{ní pokračovat i přes nulové a z{porné hodnoty (optimalizace podle počtu vozidel). Podle tohoto nastavení pak metoda určuje chvíli, ve které ukončí slučovací f{zi. 3.2.6. Implementace algoritmu Všechny uvedené úpravy byly integrov{ny do původní verze metody Clarke-Wright a jejich funkčnost byla otestov{na na sadě relevantních dat přiložených k materi{lům na CD. Výsledný modifikovaný algoritmus splňuje veškeré požadavky kladené na optimalizaci tras pomocí modulu. Průběh algoritmu včetně všech úprav je shrnut na n{sledujícím diagramu, ten je rozdělen na tři navazující č{sti:

Obr. 3 – Diagram inici{lní f{ze algoritmu

43

Obr. 4 – Diagram slučovací f{ze algoritmu

44

Obr. 5 – Diagram konečné f{ze algoritmu V samotné aplikaci reprezentuje algoritmus třída Optimizer zařazen{ do stejnojmenného balíku. Je realizov{na pomocí n{vrhového vzoru singleton, což zajistí, že bude v aplikaci vytvořena vždy pouze jedna její instance. Třída obsahuje metodu calculateAdvantages, kter{ na z{kladě matice vzd{leností počít{ matici výhodnostních koeficientů podle vzorce uvedeného výše (včetně zohlednění priority). Pro výběr nejvyššího výhodnostního koeficientu z vypočítané matice je použita metoda getBiggestAdvantage. Metoda combineTraces dostane na vstup dvě trasy a pokusí se je sloučit do nové. Star{ se také o kontrolu, jestli je trasa přípustn{ (včetně zahrnutí svozu vratných obalů a ostatních kapacitních a časových omezení). Metoda getVehicleForTrace m{ na starosti přiřazení vhodného vozidla trase, kter{ je d{na na vstupu (zajišťuje i vhodné využití heterogenního vozového parku). Pro přiřazení imagin{rního vozidla trase slouží metoda

45

getFakeVehicle. Hlavní metodou celé třídy je optimizeDistance. Ta řídí celý výpočet, zajišťuje vytvoření inici{lních tras, kroky konečné f{ze algoritmu i vol{ní výše uvedených metod pro samotnou slučovací f{zi. Ostatní metody jsou spíše pomocného r{zu a jejich popis lze najít v dokumentaci přiložené na CD.

3.3.

Implementace rozhraní na existující IS Pro pl{nov{ní denních přeprav na z{kladě objedn{vek a z nich

vytvořených dod{vek potřebuje modul získ{vat data o dod{vk{ch, které jsou již zabaleny a určeny k expedici. Tyto údaje musí být k dispozici v informačním systému podniku, na který m{ být modul napojen. Pro svou funkci potřebuje navržený modul data o jednotlivých dod{vk{ch, položk{ch dod{vek (balících) a v nich obsažených obalových materi{lech. Při získ{v{ní a editaci těchto dat modul přistupuje přímo k centr{lní datab{zi informačního systému. Instrukce pro instalaci modulu obsahují i n{vod, jak nastavit údaje pro připojení k externí datab{zi informačního systému. 3.3.1. Data dod{vek Při pl{nov{ní denní přepravy je nutné do této přepravy zařadit požadované dod{vky. Vytvořený modul předpokl{d{, že podnikový systém je schopný ze své datab{ze poskytnout k jednotlivé dod{vce její unik{tní identifikační klíč, kompletní adresu odběratele a také status dod{vky. Adresa odběratele označuje místo, kam m{ být dod{vka přepravena. Měla by obsahovat n{zev země, přesný n{zev obce, označení ulice včetně orientačního čísla, poštovní směrovací číslo, případně i telefonní kontakt na odběratele. Tato adresa bude automatizovaně zpracov{na modulem, aby bylo možné vypočítat přesnou polohu odběrného místa a jeho vzd{lenost od ostatních odběrných míst v přepravě. Status dod{vky by měl určovat, v jakém stavu se cel{ dod{vka pr{vě nach{zí. Používané stavy se mohou lišit systém od systému, pro potřeby modulu by však podnikový systém měl být schopný rozlišit stav, kdy je dod{vka schv{lena, zabalena a připravena k expedici. V tomto stavu ji totiž převezme vyvinutý modul a napl{nuje její přepravu k odběrateli.

46

Modul je také navržen tak, aby byl schopný evidovat průběh přepravy. Pro tento účel použív{ u dod{vky další stavy. Pokud m{ být přeprava dod{vky tímto způsobem sledov{na a zpětně zaznamen{na i do datab{ze podnikového systému, musí jeho data o dod{vk{ch podporovat i hodnoty pro modulem používané stavy dod{vek. Ty jsou n{sledující: -

Nezařazena do přepravy: dod{vka je zabalena a připravena k expedici, ale zatím nebyla zařazena do ž{dného přepravního pl{nu, který je označen k expedici

-

Označena k expedici: dod{vka byla přiřazena do denní přepravy, kter{ byla označena k expedici

-

Probíh{ přeprava: dod{vka byla naložena na příslušné vozidlo a probíh{ její přeprava po napl{nované trase

-

Přeprava dokončena: dod{vka byla úspěšně doručena odběrateli

-

Přeprava č{stečně dokončena: č{st dod{vky byla úspěšně doručena odběrateli, některé položky dod{vky nebyly doručeny nebo převzaty

-

Přeprava zrušena: dod{vku nebylo možné doručit odběrateli Dod{vku ve vytvořeném modulu reprezentuje třída Delivery z balíku

data. Ta obsahuje metodu getDeliveriesReadyForExpedition, kter{ z datab{ze podnikového informačního systému načte data všech dod{vek, které jsou uvolněné pro přepravu, ale ještě nebyly označeny k expedici. D{le obsahuje metody getDeliveryVolume a getDeliveryWeight pro vypočít{ní v{hy a objemu celé dod{vky a metodu getDeliveryNumberOfPackages, kter{ vrací počet balíků v dod{vce. Metoda sendToStatus slouží ke změně statusu dod{vky. Zbylé metody slouží pro manipulaci s dod{vkami v r{mci přepravních tras, změnu priority a načtení položek dané dod{vky. Třída Delivery tak zajišťuje mapov{ní objektů dod{vek do odpovídající tabulky v centr{lní datab{zi podnikového systému a také další podpůrné funkce využité pro potřeby modulu a samotné optimalizace. Její datový model je uveden níže.

47

3.3.2. Data položek dod{vek Každ{ dod{vka se skl{d{ z jedné nebo několika položek (balíků). Ty představují fyzické zabalené manipulační jednotky, které jsou nakl{d{ny na vozidla. Jejich parametry jsou z hlediska logistického modul důležité pro kontrolu omezujících podmínek na vytvořených tras{ch. Při načtení dod{vky z centr{lní datab{ze také doch{zí k načtení dat o všech jejích položk{ch. Manipulační jednotka musí obsahovat vlastní unik{tní identifik{tor a identifikační klíč dod{vky, do které patří. Dalšímu parametry, které modul využív{, jsou v{ha položky, objem položky a její rozměry (vše už zahrnuje i obsažené vratné obaly). Položka také může obsahovat vlastní textový popis a status položky. Status položky modul během přepravy eviduje podobně jako status dod{vky. Navržené řešení využív{ n{sledujících stavů: -

Připraveno k expedici

-

Expedov{no

-

Doručeno

-

Nedoručeno Položka dod{vky je v logistickém modulu reprezentov{na třídou

DeliveryUnit. Ta je umístěna do balíku data a mapuje objekty položek dod{vky na z{znamy tabulky v centr{lní datab{zi. Obsahuje metody, pomocí kterých lze zjistit jednotlivé parametry položky, další pomocné metody a také metodu getReturnablesForUnitDB, kter{ pro danou položku dod{vky načte z datab{ze všechny vratné obaly, které jsou k ní přiřazeny. 3.3.3. Data obalových materi{lů Ke každé položce dod{vky může n{ležet až několik přidružených vratných obalů. Jejich v{ha, objem i rozměry jsou pro potřeby rozvozu již obsaženy v parametrech položky dod{vky, do které patří. Pro potřeby zpětného svozu obalů však modul potřebuje zn{t tyto parametry samostatně pro každý vratný obal. U vratného obalu je evidov{na jeho v{ha, objem, rozměry, popis a unik{tní identifik{tor obalu. U položky dod{vky je pak uložen seznam identifik{torů obalů, které jsou v ní zahrnuty, a jejich počet.

48

Pro vratný obal je v implementovaném modulu použita třída PackingUnit z balíku data. Její objekty jsou mapov{ny na z{znamy v tabulce centr{lní datab{ze obsahující data o obalech. Obsahuje z{kladní metody pro načtení dat z datab{ze a pro získ{ní jednotlivých parametrů obalu. 3.3.4. Nemožnost napojení na nekompletní systém Vytvořený modul měl být napojen na informační systém pro řízení obchodů a skladů vyvíjený týmem studentů v r{mci jejich diplomové pr{ce. V době realizace této pr{ce (podzim 2012) byl bohužel vyvíjený informační systém ještě nekompletní a neposkytoval potřebnou funkcionalitu a data pro napojení logistického modulu. Z toho důvodu bylo nutné přikročit k n{hradnímu řešení a č{st systému a dat potřebných pro tuto pr{ci nasimulovat, aby bylo možné ověřit a demonstrovat funkčnost vyvinutého modulu. Simulace potřebné č{sti systému zahrnuje vytvoření datab{zové struktury pro data o dod{vk{ch, položk{ch dod{vek, vratných obalech a jejich přiřazení k položk{m dod{vek. Tu popisuje níže uvedený datový model. Další údaje, které nebyly relevantní pro tuto pr{ci, byly vynech{ny. Skript pro vytvoření simulované datab{zové struktury (včetně postupu) je přiřazen k instalačním souborům na přiloženém CD. Pro demonstraci funkčnosti vyvinutého modulu je také potřeba naplnit simulovaný systém daty dod{vek. Pro tento účel byla sestavena sada testovacích dat, kter{ lze pomocí SQL skriptu importovat do simulované datab{ze. Jednotlivé varianty testovacích dat jsou i se stručným popisem a n{vodem pro jejich nahr{ní do datab{ze umístěny na přiloženém CD. 3.3.5. Datový model simulované č{sti informačního systému Níže je ve formě entitně relačního diagramu uveden datový model zn{zorňující tu č{st podnikového informačního systému, kterou využív{ vytvořený modul.

49

Obr. 6 – Datový model simulované č{sti informačního systému

3.4.

Implementace doplňujících údajů Kromě dat, kter{ získ{v{ z centr{lní datab{ze podnikového systému,

potřebuje modul evidovat a spravovat také další data. Ta jsou udržov{na ve vlastní datab{zi modulu. Postup a materi{ly nutné pro instalaci a spr{vné nastavení této datab{ze jsou přiloženy na CD. V n{sledujících odstavcích budou pops{ny všechny údaje, které jsou pro použití modulu potřebné a také způsoby pro jejich získ{ní a údržbu a použití. 3.4.1. Data uživatelů Navržený modul potřebuje evidovat údaje o jednotlivých řidičích, dispečerech a případném dalším person{lu, který bude s modulem pracovat. Uložené informace jsou využív{ny pro řízení přístupu k jednotlivým funkcím modulu, pro přiřazov{ní řidičů na jednotliv{ vozidla a pro evidenci změn provedených v přepravních pl{nech. Každý uživatel (evidovaný v r{mci vytvořeného modulu) m{ přiřazeno unik{tní identifikační číslo a roli, kter{ určuje jeho přístupov{ opr{vnění. Ve vytvořené aplikaci jsou k dispozici dvě role:

50

-

Dispečer: m{ přístup ke všem funkcím, které modul nabízí, m{ na starosti spr{vu veškerých dat modulu, pl{nov{ní a sledov{ní přeprav.

-

Řidič: m{ přístup pouze pro zobrazení jemu přiřazené trasy, kterou m{ v daný den realizovat (a jejích detailů). Nem{ možnost zasahovat do datab{ze modulu a veškeré změnové požadavky hl{sí dispečerům. D{le je u každého uživatele evidov{no jeho jméno, příjmení a jím

zvolené přístupové heslo šifrované pomocí SHA-256. U uživatele je také uveden příznak určující, jestli je uživatel platný nebo už byl archivov{n. Uživatel je v aplikaci reprezentov{n třídou User z balíku data. Ta obsahuje metody pro načtení, přid{ní, editaci a archivaci uživatele v datab{zi (mapov{ní objektu na z{znam v relační datab{zi). D{le obsahuje metodu getUsersFromDB, kter{ vrací seznam všech nearchivovaných uživatelů modulu a také metody pro kontrolu spr{vnosti údajů při přihlašov{ní. 3.4.2. Data vozového parku Při pl{nov{ní přepravy jsou vytv{řeny rozvozové trasy pro dostupn{ vozidla. Ta jsou evidov{na v datab{zi vytvořeného modulu. U každého vozidla je uloženo jeho unik{tní číslo v r{mci vozového parku, slovní popis, barva a st{tní pozn{vací značka. Další sada údajů definuje kapacitu vozidla pro přepravu zboží. Její souč{stí je maxim{lní povolen{ hmotnost n{kladu (nosnost), využitelný objem n{kladového prostoru a jeho výška, šířka a délka. Pro vozidlo je také uložen dojezd na plnou n{drž (bez nutnosti doplnit palivo), průměrn{ rychlost vozidla (při realizaci přepravy) a průměrn{ doba pro naložení nebo vyložení jednoho balíku v odběrném místě. K dispozici je i příznak určující, jestli je vozidlo schopné provozu a identifik{tor řidiče, který je k vozidlu aktu{lně přiřazen. Vozidlo ve vytvořeném modulu představuje třída Vehicle z balíku data. Tato třída obsahuje metody a parametry nutné pro mapov{ní dat z datab{ze na konkrétní objekty. Mezi další důležité metody patří setUnavailable, kter{ nastavuje zadané vozidlo na nedostupné (případně zpět na provozuschopné), metoda pro hromadné načtení vozidel, getAvailableVehicles a také metody, které vracejí nebo nastavují důležité parametry pro dané vozidlo (getWeightCapacity, getVolumeCapacity, getAverageSpeed, setDriver, setAverageTimeToLoadUnit a další).

51

3.4.3. Data odběrných míst Podle požadavků m{ navržený modul získ{vat potřebné geografické informace (vzd{lenosti mezi odběrnými místy v silniční síti) prostřednictvím webové služby. Vzhledem k omezenému počtu dotazů, které je možné pomocí zvolené služby Google Maps denně zpracovat, je vhodné získan{ data ukl{dat do datab{ze modulu. Tím se (v případě opakovaných dod{vek do některých odběrných míst) omezí počet dotazů a dojde i ke zrychlení běhu algoritmu. Kvůli tomu je nutné evidovat všechna odběrn{ místa, kter{ byla modulem v minulosti obsloužena. Při načtení nové dod{vky z datab{ze informačního systému jsou z ní vybr{na data určující adresu odběratele a jsou uložena mezi ostatní evidované adresy do datab{ze modulu. U každé adresy je zaznamen{na země, obec, ulice, poštovní směrovací číslo a kontaktní telefon. D{le jsou u adresy připravena také pole GPS latitude a GPS longitude, kter{ jsou určena pro uložení přesných geografických souřadnic ve form{tu GPS. Tyto údaje jsou k jednotlivým adres{m doplňov{ny spolu se získ{v{ním vzd{leností v silniční síti před spuštěním samotného algoritmu. Adresa také obsahuje unik{tní identifikační číslo. Odběrné místo je v aplikaci reprezentov{no třídou Address z balíku data. Ta obsahuje běžné metody pro načít{ní, zakl{d{ní, editaci a výmaz míst z datab{ze modulu. D{le zahrnuje metodu tryDistanceFromDB, kter{ se pro dvě zadan{ místa pokusí v datab{zi modulu vyhledat jejich vz{jemnou vzd{lenost. Metoda saveCoordinatesDB zajišťuje doplnění souřadnic k již uloženému místu, saveDistanceDB slouží k uložení získané vzd{lenosti pro dvě zadan{ místa. Metoda getPackingUnitsToReturnDB vrací všechny vratné obaly, které modul eviduje pro zadané odběrné místo. Metoda returnPackingUnit je využív{na při zpětném svezení určitého množství vratného obalu od odběratele. Pro vratný obal metoda odebere jeho požadované množství z evidence obalů daného odběrného místa. Speci{lním případem evidované adresy je adresa rozvozového depa, pro které je modul nasazen. Ta je v datab{zi uvedena vždy na první pozici a třída Address pro její editaci využív{ metody saveAsDepot a getDepotAddress. Další metody slouží jako pomocné a neobsahují významnou aplikační logiku.

52

3.4.4. Vzd{lenosti mezi odběrnými místy Jak již bylo uvedeno výše, modul pro potřeby optimalizace získ{v{ a ukl{d{ vzd{lenosti mezi odběrnými místy v silniční síti. Pro tento úkon (a pro zobrazov{ní tras na mapových podkladech) musí být modul připojen k internetu. Ještě před spuštěním samotného optimalizačního algoritmu musí dispečer v modulu označit dod{vky, které chce v r{mci pl{nované přepravy realizovat. Po nastavení parametrů pro optimalizaci je spuštěn samotný optimalizační proces. V jeho prvním kroku doch{zí k doplnění vzd{leností a ve druhém kroku už je spuštěn výše popsaný algoritmus. Pro doplnění geografických dat v modulu slouží třída DataRetriever z balíku optimizer. V té je vol{na metoda getDistances, kter{ na vstupu přijme seznam všech dod{vek zařazených do pl{nované přepravy (včetně přepravního depa) a vr{tí dvourozměrné pole obsahující vzd{lenost mezi každou dvojicí míst ze vstupního seznamu. Postupuje tak, že pro každou dvojici míst vol{ metodu getPlacesDistance ze stejné třídy a její výsledek uloží na určené místo do výstupní matice. V datab{zi modulu je udržov{na také tabulka vzd{leností (její schéma je patrné na níže uvedeném datovém modelu). Do té jsou ukl{d{ny získané vzd{lenosti mezi dvojicemi odběrných míst. Metoda getPlacesDistance pro každ{ dvě místa zkontroluje datab{zi modulu a zjistí, jestli už jejich vz{jemnou vzd{lenost nem{ uloženu. Pokud ano tak ji vr{tí jako výsledek, pokud ne, sestaví požadavek na webovou službu Google Directions API. Služba přijím{ HTTP požadavky ve formě URL adresy, kter{ obsahuje síťovou adresu služby, form{t výstupu a adresu obou míst, mezi kterými chceme naleznout vzd{lenost v silniční síti. Metoda getPlacesDistance využív{ XML formu výstupu [53] a adresy obou dod{vek doplňuje do požadavku v doporučeném form{tu (pro co největší pravděpodobnost nalezení spr{vného místa). Po sestavení je požadavek metodou odesl{n na určenou adresu. Využívan{ služba by měla vyhledat obě zadané adresy, cestu mezi nimi a všechny tyto informace ve formě XML dokumentu vr{tit zpět modulu. Pro získ{ní dat z dokumentu je využit sekvenční parser SAX, který je souč{stí rozhraní Java API for XML Processing (JAXP) [54]. Tento n{stroj umožňuje efektivně proch{zet XML dokumenty a získ{vat z nich informace

53

uložené v jednotlivých uzlech. Parseru je nutné poskytnout obslužní objekt, který určuje jeho chov{ní pro jednotlivé uzly. O to se star{ vytvořen{ třída XMLHandler z balíku xmlparser. Těmito prostředky získ{ metoda getPlacesDistance z dokumentu délku cesty mezi zadanými adresami (v kilometrech) a přesné GPS souřadnice pro obě místa (zeměpisnou šířku a délku ve stupních). Získané souřadnice metoda uloží do datab{ze modulu k oběma adres{m. D{le metodou saveDistanceDB uloží získanou vzd{lenost do datab{ze modulu a vr{tí ji metodě getDistances, kter{ ji doplní na určené místo do matice vzd{leností. Po doplnění všech vzd{leností a souřadnic modul zobrazí uživateli odběrn{ místa na mapovém podkladu získaném pomocí rozhraní Google Static Maps API. Uživatel m{ v této f{zi možnost zkontrolovat polohu míst a v případě, že by některé bylo umístěno chybně nebo nebylo umístěno vůbec (chybn{ identifikace adresy webovou službou), je možné jeho souřadnice ručně doplnit nebo opravit. Pokud je poloha místa manu{lně změněna, zajistí modul i přepočít{ní všech vzd{leností, které jsou s daným místem spojeny. Po potvrzení spr{vnosti všech adres jsou vzd{lenosti před{ny algoritmu, který optimalizuje zadanou přepravu. 3.4.5. Vratné obaly na adres{ch U jednotlivých odběrných míst jsou v modulu evidov{ny také vratné obaly, které byly v minulosti na adresu podnikem dod{ny a ještě nebyly svezeny zpět. Ty jsou využív{ny při optimalizaci přepravy s upřednostněním svozu vratných obalů. Jak již bylo řečeno výše, vratný obal je reprezentov{n třídou PackingUnit. Evidence obalů přítomných na jednotlivých adres{ch je zajišťov{na metodami getPackingUnitsToReturnDB, deliverPackingUnit a returnPackingUnit patřícími do třídy Address. Datab{zov{ tabulka obalů na adres{ch určuje množství daného obalu na dané adrese a její schéma je zn{zorněno na datovém modelu níže. 3.4.6. Data pl{nů a tras Poté co optimalizační algoritmus vygeneruje přepravní pl{n, je nutné jej uložit, aby ho bylo možné vyhodnotit a řídit jeho realizaci. Jednotlivé přepravní pl{ny se skl{dají z několika tras, do kterých už jsou zařazeny vybrané dod{vky.

54

3.4.6.1.

Přepravní pl{ny

Pro každý pl{n přepravy je v datab{zi modulu udržov{n jednoznačný identifik{tor, datum pl{novaného uskutečnění přepravy a status celé přepravy. D{le je u něj uloženo datum a čas vygenerov{ní nebo poslední změny, uživatel, který pl{n naposledy uložil, textové pole pro pozn{mku k pl{nu a hodnota určující maxim{lní dobu pro provedení jednotlivých tras. V modulu představuje přepravní pl{n třída Plan z balíku data. Ta obsahuje metody pro načít{ní pl{nů z datab{ze modulu, ukl{d{ní nových pl{nů, editaci již vytvořených pl{nů a jejich vymaz{ní (pouze pl{ny, které ještě nejsou ve stavu „Probíh{ přeprava“). Mezi další metody patří checkIfNoExpedition, kter{ pro daný pl{n kontroluje, jestli je ve dni jeho přepravy už nějaký jiný pl{n zařazen do expedice (v daný den může být zařazen do expedice maxim{lně jeden pl{n). Metoda getRealizedPlanForToday vrací pl{n, který byl zařazen do expedice pro aktu{lní datum. Pro získ{ní počtu tras zařazených do přepravního pl{nu slouží metoda getNumberOfTraces, getTotalLength vrací součet délek všech přiřazených tras. Upravit status celého pl{nu lze metodou sendToStatus. Přepravní pl{n se může nach{zet v n{sledujících stavech: -

Vygenerovaný: pl{n byl vygenerov{n a je uchov{v{n pro porovn{ní s jinými vygenerovanými pl{ny případně pro označení k expedici

-

Ručně upravený: jedn{ se o vygenerovaný pl{n, jehož trasy byly manu{lně upraveny některým dispečerem

-

Označen k expedici: v tomto stavu (a všech n{sledujících) může být pro jeden den pouze jediný pl{n, lze jej buď vymazat, nebo zah{jit jeho expedici

-

Probíh{ přeprava: všechny dod{vky byly expedov{ny a vozidla obsluhují přiřazené trasy

-

Přeprava dokončena: všechny dod{vky byly v poř{dku doručeny

-

Přeprava č{stečně dokončena: některé dod{vky se nepodařilo dodat, ale ostatní byly v poř{dku doručeny odběratelům

-

Přeprava zrušena: cel{ přeprava byla zrušena a ž{dn{ z dod{vek nebyla doručena

55

Metoda getImage slouží k vytvoření požadavku na rozhraní Google Static Maps API a k získ{ní statické mapy přepravního pl{nu s vyznačeným depem a naznačenými trasami, které k němu n{leží. Třída obsahuje ještě další podpůrné metody, jejichž popis lze nalézt v dokumentaci. 3.4.6.2.

Trasy

Každ{ vygenerovan{ trasa je uložena do datab{ze modulu. Zde je u ní evidov{no unik{tní identifikační číslo, textový popis trasy, pozn{mka k trase a identifikace přepravního pl{nu, do kterého trasa patří. Mezi údaje trasy také patří identifikace vozidla, které je k trase přiřazeno, a její status. Ten využív{ stejné hodnoty jako status přepravního pl{nu. Trasa je v aplikaci zastoupena třídou Trace z balíku data. Kromě metod mapujících objekty do datab{ze modulu obsahuje getLength, kter{ vrací délku celé trasy, getEstimatedTime, kter{ vypočít{v{ odhadovanou dobu pro realizaci trasy. D{le obsahuje metody pro kontrolu, jestli je trasu možné obsloužit daným vozidlem

(getTraceWeight,

getTraceVolume,

isValid,

doPackagesFitInVehicle).

K ručnímu přesouv{ní dod{vek mezi trasami slouží manuallyDeleteDelivery a manuallyAddDelivery. Metoda sendToStatus mění status dané trasy. Modul také pro trasy poskytuje funkci, kter{ generuje soubor ve form{tu GPX [55]. Jedn{ se o standardizovaný strukturovaný dokument určený mimo jiné pro použití v GPS navigacích. Obsahuje souřadnice průjezdních bodů trasy a po importu do navigačního zařízení je schopen navrhnout a řídit trasu jízdy. O vytvoření GPX souboru se star{ třída GPXGenerator z balíku xmlparser. Její metoda writeGpxFile rozdělí trasu na jednotliv{ odběrn{ místa a jejich souřadnice v určeném pořadí zapíše do strukturovaného dokumentu, který poté uloží do složky GPX_files v adres{ři modulu. 3.4.7. Datový model Na diagramu níže je zn{zorněn datový model celého modulu. Model obsahuje pro každou entitu její atributy a označení prim{rních a cizích klíčů. D{le obsahuje vazby mezi entitami včetně n{sobností. Žlutou barvou je odlišena č{st modelu, kter{ odpovíd{ datům v centr{lní datab{zi informačního systému, a růžově je označena lok{lní datab{ze modulu. Celý model je také spolu s dalšími diagramy přiložen na CD, které je souč{stí této pr{ce.

56

Obr. 7 – Datový model celého modulu

57

3.4.8. Diagram tříd Navržen{ aplikace je rozdělena do několika balíků. Balík data obsahuje třídy mapované na relační datab{zi. Jejich atributy a vazby jsou obrazem uvedeného datového modelu. Balík exceptions obsahuje několik výjimek vytvořených pro potřeby aplikace. Ty však neobsahují ž{dnou aplikační logiku ani důležité atributy. Balík optimizer obsahuje dvě třídy zajišťující doplnění geografických dat o odběrných místech a samotnou optimalizaci přepravy. V balíku xmlparser jsou umístěny třídy pro pr{ci se strukturovanými dokumenty (GPX a XML). Balík gui pak reprezentuje celé grafické uživatelské rozhraní. Vzhledem k tomu, že je diagram tříd navrženého modulu rozs{hlejší, jeho struktura z velké č{sti odpovíd{ uvedenému datovému modelu a některé jeho č{sti neobsahují ž{dné důležité údaje (z hlediska implementované funkcionality), byl diagram zařazen pouze na přiložené CD do složky Vývojové diagramy.

3.5.

Implementace grafického rozhraní Modul byl navržen jako samostatn{ desktopov{ aplikace s přístupem

k internetu, kterou budou uživatelé ovl{dat pomocí grafického uživatelského prostředí. Pro vytvoření prostředí byl využit designérský n{stroj pro knihovnu Swing integrovaný do platformy NetBeans. 3.5.1. Zobrazení podle rolí uživatelů V modulu jsou vytvořeny dvě uživatelské role (dispečer a řidič). Ty ovlivňují přístup k jednotlivým funkcím a výstupům aplikace. Role dispečera je určena k ovl{d{ní celého modulu, údržbu jeho dat a pl{nov{ní samotných přeprav. Z toho důvodu m{ přístup ke všem obrazovk{m a funkcím, které modul nabízí. Řidič m{ do modulu přístup pro případ, kdy není dispečer k dispozici (například víkendov{ expedice), role ho opravňuje pouze zobrazit informace o trase, kterou m{ v daný realizovat (včetně podrobností o dod{vk{ch a jejím exportu do souboru GPX).

58

3.5.2. Výpočty v aplikaci Aplikace vytvořen{ s pomocí knihovny Swing využív{ pro běh grafického prostředí vl{kno Event Dispatch Thread. V tom jsou obsluhov{ny všechny ud{losti zabezpečující komunikaci s uživatelem. V tomto vl{kně by neměla být spouštěna ž{dn{ n{ročnější aplikační logika (kvůli zamrznutím grafického prostředí). Z toho důvodu jsou n{ročnější operace spouštěny ve vlastních vl{knech. Během výpočtu v samostatném vl{kně zůstane Event Dispatch Thread nevytížené a uživatel tak s aplikací může nad{le komunikovat. Nejn{ročnějšími operacemi, které vytvořený modul realizuje, jsou hlavně doplnění vzd{leností mezi místy z rozhraní Google Directions API a běh samotného optimalizačního algoritmu. Z toho důvodu jsou tyto funkce prov{děny v samostatných vl{knech, aby nepřerušily komunikaci s modulem. 3.5.3. Jednotlivé obrazovky Níže budou uvedeny jednotlivé obrazovky modulu a pops{n jejich význam a možnosti, které poskytují. Vzhledem k tomu, že grafické prostředí není stěžejní č{stí této pr{ce, byly obrazovky a jejich komponenty navrženy jednoduše s použitím z{kladních ovl{dacích prvků. Celé grafické prostředí je v aplikaci implementov{no ve tříd{ch z balíku gui. 3.5.3.1.

Přihlašovací obrazovka

Přihlašovací obrazovka je vstupní br{nou do celé aplikace. Obsahuje pole pro zad{ní unik{tního čísla, pod kterým je uživatel v modulu evidov{n a pole pro přístupové heslo. Při přihl{šení proběhne ověření hesla a načtení aplikace modulu podle přiřazené uživatelské role. 3.5.3.2.

Z{kladní obrazovka modulu

Po přihl{šení je zobrazena z{kladní obrazovka modulu. Ta obsahuje hlavní nabídku (v případě řidiče značně omezenou) a souhrnné zpr{vy modulu (vozidla k dispozici, počty vygenerovaných pl{nů…). Zavřením tohoto okna se ukončí cel{ aplikace. Pokračovat v pr{ci s modulem lze jedním z tlačítek v hlavní nabídce.

59

3.5.3.3.

Spr{va uživatelů

Obrazovka slouží k údržbě uživatelů modulu, poskytuje formul{ř pro založení nového uživatele, archivaci a zneplatnění existujícího uživatele nebo jeho editaci (změna hesla, role a jména). 3.5.3.4.

Spr{va depa

Na této obrazovce může dispečer editovat údaje o rozvozovém depu podniku. Lze zde nastavit kompletní adresu depa, telefonní kontakt a GPS souřadnice depa. Tyto údaje jsou důležité pro výpočet optimalizačního algoritmu. 3.5.3.5.

Spr{va vozidel

Tato obrazovka slouží k zakl{d{ní, editaci a maz{ní vozidel ve vozovém parku. Po výběru vozidla je možné upravit jeho parametry nebo změnit přiřazeného řidiče. Lze také označit vozidlo jako dostupné/nedostupné. 3.5.3.6.

Spr{va odběratelů

V seznamu na levé straně se nach{zejí všechna odběrn{ místa, kter{ byla modulem někdy použita. Po vybr{ní adresy se do střední č{sti načte její detail (adresa, telefon a souřadnice) a do pravé č{sti se načte seznam a množství vratných obalů, které jsou na adrese uschov{ny.

Obr. 8 – Spr{va odběrných míst

60

U adresy lze editovat její GPS souřadnice (což by nemělo být nutné). Po vybr{ní jednoho z obalů přítomných na adrese je možné zaevidovat do modulu jeho vr{cení (poté, co řidič nahl{sí, kolik daného obalu z adresy svezl). To probíh{ v samostatném okně, kam dispečer zad{ množství vybraného obalu, které bylo svezeno zpět do depa. 3.5.3.7.

Spr{va přepravních pl{nů

Tato obrazovka umožňuje zobrazovat a spravovat všechny modulem vygenerované přepravní pl{ny. Pl{ny je možné načíst pro zadané datum jak do minulosti (nerealizované nebo již dokončené přepravy), tak do budoucnosti (pl{nované přepravy). Po výběru pl{nu se v pravé č{sti zobrazí jeho detail. Dalšími tlačítky lze zobrazit pl{n přepravy na mapových podkladech (s barevně odlišenými naznačenými trasami), vymazat pl{n (pokud přeprava ještě neprobíh{) nebo označit pl{n k expedici (případně jej posunout do n{sledujícího stavu) a zobrazit jednotlivé trasy zařazené do pl{nu.

Obr. 9 – Spr{va přepravních pl{nů Trasy přepravního pl{nu V levé č{sti obrazovky jsou načteny všechny trasy patřící k danému pl{nu. Po výběru trasy se načte její detail, který ud{v{ délku trasy, předpokl{daný čas její realizace, přidělené vozidlo, využití jeho kapacity a seznam dod{vek v pořadí, ve kterém jsou do trasy zařazeny.

61

D{le lze zobrazit mapu trasy, exportovat trasu do souboru ve form{tu GPX, editovat trasu (změnit popis trasy a připojenou pozn{mku). Ostatní činnosti jsou z{vislé na statusu trasy. Pokud trasa ještě nebyla označena k expedici, lze některé z dod{vek přesunout manu{lně do jiné trasy (v novém okně je třeba vybrat novou trasu a pozici, na kterou bude dod{vka vložena). Pokud byla přeprava už dokončena, lze některé vybrané dod{vky označit jako nedodané, případně pouze č{stečně dodané (na z{kladě hl{šení řidiče).

Obr. 10 – Spr{va tras pl{nu 3.5.3.8.

Generov{ní přepravy

Tato obrazovka je dispečerem využív{na pro napl{nov{ní nové denní přepravy. Dispečer nejdříve načte do seznamu v pravé č{sti nezpracované dod{vky, které jsou připraveny k rozvozu (z centr{lní datab{ze informačního systému). Po označení některé z nich může v novém okně změnit její zařazení do přepravy (může zobrazit položky dod{vky, změnit prioritu dod{vky nebo dod{vku z pl{nované přepravy úplně vypustit). Poté je nutné určit datum pl{nované přepravy, maxim{lní čas pro realizaci tras a nastavení optimalizace, které ovlivní výsledné trasy. Tyto varianty už byly zmíněny v kapitole věnující se implementaci algoritmu a jedn{ se o minimalizaci délek tras / počtu vozidel a prioritizaci svozu vratných obalů

62

(neprioritizovat / obaly z minulé dod{vky / všechny obaly na adrese). Lze také doplnit textovou pozn{mku k přepravě.

Obr. 11 – Generov{ní přepravy Doplnění geografických údajů Pokud je vše nastaveno podle představy dispečera, lze pokračovat tlačítkem Generovat přepravu. To spustí f{zi doplňov{ní geografických údajů o odběrných místech (aplikace musí být připojena k internetu). Po doplnění všech údajů je zobrazena mapa s označenými odběrnými místy a barevně odlišeným rozvozovým depem. Dispečer m{ možnost zkontrolovat umístění adres na mapě, a pokud nalezne nějakou nesrovnalost, může upravit místa jednotlivých dod{vek. V novém okně pro takové místo zad{ ručně GPS souřadnice a po uložení je mapa překreslena do aktu{lní podoby. Pokud umístění všech adres vyhovuje, lze spustit optimalizaci tlačítkem Potvrdit místa dod{vek a vygenerovat pl{n. Po skončení běhu algoritmu je vygenerovaný pl{n i s jeho trasami zobrazen na mapě a uložen do datab{ze modulu, kde jej lze pomocí spr{vy přepravních pl{nů upravit, smazat nebo označit k expedici.

63

Obr. 12 – Upravení místa dod{vky

64

4.

Z{věr Cílem této pr{ce bylo analyzovat procesy spojené s pl{nov{ním

distribuce zboží, porovnat existující n{stroje a metody pro optimalizaci rozvozových tras, zvolit a modifikovat vhodný optimalizační algoritmus a navrhnout a implementovat logistický modul pro operativní pl{nov{ní dod{vek odběratelům. Aplikace vytvořen{ v této pr{ci poskytuje z{kladní funkcionalitu pro automatizované pl{nov{ní denních rozvozových pl{nů, jejich manu{lní úpravu a sledov{ní přepravy. Umožňuje také zjednodušené zobrazení tras na mapových podkladech a jejich export do form{tu podporovaného palubními GPS navigacemi. Data o dod{vk{ch m{ implementovaný modul získ{vat z informačního systému realizovaného v r{mci diplomové pr{ce Systém řízení obchodů a skladů. Vzhledem k tomu, že zmíněný systém nebyl v době realizace této pr{ce ještě plně v provozu, byla potřebn{ č{st simulov{na a přiložena k této pr{ci, aby bylo možné ověřit funkčnost modulu. Optimalizační algoritmus vytvořený pro potřeby této pr{ce poskytuje několik variant výpočtu a zohledňuje tak kromě kapacitních a časových omezení i pl{nov{ní svozu vratných obalů a dod{vky s odlišnými prioritami. Efektivita optimalizace byla testov{na na několika sad{ch dat (ř{dově desítky dod{vek) na běžné počítačové sestavě s připojením na internet. Běh algoritmu pro 50 až 100 dod{vek trval v z{vislosti na počtu použitých vozidel 1 až 4 minuty, což i s rezervou splňuje uvedené požadavky. Délky tras vypočítaných na re{lné silniční síti byly blízké ide{lnímu trasov{ní za zadaných podmínek. Implementovaný modul tak dok{že efektivně optimalizovat distribuci zboží a ušetřit podniku, ve kterém je nasazen, č{st n{kladů na přepravu. Časově nejn{ročnější je (podle výsledků testov{ní) f{ze doplnění geografických dat odběrných míst z webové služby. Delší trv{ní této operace je ovlivněno nutností zpracovat strukturovaný výstup služby a také aktu{lní propustností využité služby a dostupného internetového připojení. Doplnění vzd{lenosti mezi jednou dvojicí míst trvalo při testov{ní mezi půl vteřinou a vteřinou. Například při pl{nov{ní 50ti dod{vek, z nichž 30 je určeno již dříve

65

obslouženým odběratelům a 20 novým odběratelům, je nutné doplnit zhruba 1000 z{znamů vzd{leností což odpovíd{ přibližně 12 minut{m běhu aplikace. I přes delší dobu trv{ní poskytuje automatizované doplnění vzd{leností velkou úsporu času oproti manu{lnímu vkl{d{ní velkého množství dat. V porovn{ní s drahými komerčními n{stroji pro optimalizaci rozvozu poskytuje vytvořen{ aplikace menší rozsah specializovaných funkcí a nastavení. Není také napojena na plnohodnotné mapové podklady. Použitý algoritmus je však dostatečně efektivní a poskytuje všechny důležité funkce. Představuje tak bezplatné nebo nízkon{kladové řešení pro menší a střední podniky, kterým může ušetřit n{klady i čas. Existuje pouze malé množství neplacených n{strojů pro optimalizaci logistiky a implementovaný modul (s případnými drobnými úpravami) patří z pohledu praktického využití ke vhodným kandid{tům. Vyvinut{ aplikace poskytuje také možnosti pro další rozvoj. Tím může být například HTTP rozhraní pro vzd{lený přístup k modulu s využitím přenosných zařízení (chytrých telefonů, tabletů). Modul by také bylo možné obohatit o další možnosti nastavení optimalizace (například časov{ okna). Jinou možností rozvoje je doplnění avizace požadavků na svoz vratných obalů ze strany odběratelů. Z celkového pohledu splňuje vyvinut{ aplikace zad{ní pr{ce i vytyčené funkční

i

nefunkční

požadavky.

Kvůli

omezenému

rozsahu

nebyla

implementov{na podpora všech procesů popsaných v analytické č{sti, ale realizovan{ funkcionalita plně vyhovuje využití modulu v menších a středně velkých distribučních sítích.

66

Literatura [1]

Kr{l, J.: Informační systémy: specifikace, realizace, provoz. Veletiny, SCIENCE 1998. 360s. ISBN 80–86083–00–4

[2]

Wikipedia: Enterprise_resource_planning [online]. [cit. 4.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Enterprise_resource_planning >

[3]

Sap.com: ERP Software [online]. [cit. 5.3.2013+. Dostupné na: < http://www54.sap.com/pc/bp/erp.html >

[4]

Microsoft.com: Microsoft Dynamics Nav [online]. [cit. 5.3.2013+. Dostupné na: < http://www.microsoft.com/en-us/dynamics/erp-nav-overview.aspx >

[5]

Abra: ERP systém Abra G4 [online]. [cit. 5.3.2013+. Dostupné na: < http://www.abra.eu/produkty/abra-g4/ >

[6]

Helios: Helios Orange: podnikový informační systém pro SMB [online]. [cit. 5.5.2013]. Dostupné na: < http://www.helios.eu/cz/produkty/helios-orange.html >

[7]

Wikipedia: Logistics *online+. *cit. 6.5.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Logistics >

[8]

Optimization-online.org: Alternative Formulation for the p-median Problem [online]. [cit. 5.5.2013]. Dostupné na:

[9]

Wikipedia: LIFO (computing) [online]. [cit. 8.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/LIFO_(computing) >

[10] BMS.co.in: What is palletising [online]. [cit. 8.3.2013+. Dostupné na: < http://www.bms.co.in/what-is-palletising/ > [11] SupplyChainDigest: Cartonization Software Can Reduce Shipping and DC Labor Costs *online+. *cit. 8.3.2013+. Dostupné na: < http://www.scdigest.com/assets/Experts/ Tedford_09-01-29.php > [12] Wikipedia: Containerization *online+. *cit. 8.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Containerization > [13] Wikipedia: Intermodal freight transport *online+. *cit. 8.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Intermodal_freight_transport > [14] Business.center.cz: Z{kon o obalech *online+. *cit. 10.3.2013+. Dostupné na: < http://business.center.cz/business/pravo/zakony/obaly/cast1h2.aspx > [15] Wikipedia: Triangle inequality *online+. *cit. 10.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Triangle_inequality >

67

[16] Informs: Software survey: vehicle routing *online+. *cit. 11.3.2013+. Dostupné na: < https://www.informs.org/ORMS-Today/Public-Articles/February-Volume-39Number-1/Software-Survey-Vehicle-Routing > [17] ORMS today: Vehicle Routing Software Survey [online]. [cit. 11.3.2013]. Dostupné na: < http://www.orms-today.org/surveys/Vehicle_Routing/vrss.html > [18] Ortec.com: Vehicle routing and dispatch products [online]. [cit. 13.3.2013]. Dostupné na: < http://www.ortec.com/products/ortec_vehicle_routing_and_ dispatch.aspx > [19] University of Jyväskylä: Vehicle routing software - a comparison for the Dutch market [online]. [cit. 10.3.2013+. Dostupné na: < http://users.jyu.fi/~antahall/NEA Research - Vehicle Routing.pdf > [20] Esri.com: Logistics and trucking software solutions [online]. [cit. 13.3.2013]. Dostupné na: < http://www.esri.com/software/arclogistics-suite > [21] Navteq.com: What is NAVTEQ Map Data *online+. *cit. 13.3.2013+. Dostupné na: < http://www.navteq.com/products_data_whatis.htm > [22] TruckStopsRouting.com: TruckStops VRS *online+. *cit. 15.3.2013+. Dostupné na: < http://www.truckstopsrouting.com/routing-and-schedulingsoftware/products/truckstops-vrs-routing.php > [23] Wikipedia: RFID [online]. [cit. 15.3.2013+. Dostupné na: < http://cs.wikipedia.org/wiki/RFID > [24] Saitech-inc.com: WebSTARS [online]. [cit. 15.3.2013+. Dostupné na: < http://www.saitech-inc.com/Products/Prod-WebSTARS.asp > [25] Wikipedia: Cloud computing [online]. [cit. 16.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Cloud_computing > [26] Princeton.edu: NP-hard [online]. [cit. 20.3.2013+. Dostupné na: < http://www.princeton.edu/~achaney/tmve/wiki100k/docs/NP-hard.html > [27] Wikipedia: Travelling salesman problem [online]. [cit. 20.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Travelling_salesman_problem > [28] National Institute of Standards and Technology: Hamiltonian cycle [online]. [cit. 20.3.2013+. Dostupné na: < http://xlinux.nist.gov/dads/HTML/hamiltonianCycle.html > [29] Wolfram Mathworld: Polynomial time [online]. [cit. 22.3.2013+. Dostupné na: < http://mathworld.wolfram.com/PolynomialTime.html > [30] Wikipedia: Heuristic (computer science) *online+. *cit. 22.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Heuristic_(computer_science) > [31] Georgia State University: Bin Packing Problem [online]. [cit. 24.3.2013]. Dostupné na: http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html >

68

[32] Wikipedia: Vehicle Routing Problem *online+. *cit. 25.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Vehicle_routing_problem > [33] Univerzita Pardubice: Optimalizace svozu a rozvozu kusových z{silek [online]. [cit. 25.3.2013+. Dostupné na: < http://pernerscontacts.upce.cz/17_2010/Siroky.pdf > [34] Wikipedia: Metaheuristic [online]. [cit. 25.3.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Metaheuristic > [35] CIRRELT.ca: Metaheuristics for the Vehicle Routing Problem and its Extensions : A Categorized Bibliography [online]. [cit. 27.3.2013+. Dostupné na: < https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-27.pdf > [36] Kurčera, P.: Metodologie řešení okružního dopravního problému. Praha, 2009. Disertační pr{ce. Česk{ zemědělsk{ univerzita v Praze, Provozně ekonomick{ fakulta. [37] University of Malaga: Cluster-first route-second method [online]. [cit. 27.3.2013]. Dostupné na: < http://neo.lcc.uma.es/vrp/solution-methods/heuristics/clusterfirst-route-second-method/ > [38] Princeton.edu: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [online]. [cit. 2.4.2013+. Dostupné na: < www.cs.princeton.edu/~arora/pubs/tsp.ps > [39] Clarke,G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., 12, 1964, s-568-581 [40] Sze, S.N., Tiong, W.K.: A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem, World Academy of Science, Engineering and Technology 1, 2007 [41] Burdov{, J.: Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího. Praha, 2011. Diplomov{ pr{ce. Vysok{ škola ekonomick{ v Praze, Fakulta informatiky a statistiky. [42] Wikipedia: Use Case Diagram [online]. [cit. 5.4.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Use_Case_Diagram > [43] Object Management Group: UML [online]. [cit. 7.4.2013+. Dostupné na: < http://www.uml.org/ > [44] Wikipedia: Entity–relationship model [online]. [cit. 8.4.2013+. Dostupné na: < http://en.wikipedia.org/wiki/Entity–relationship_model > [45] Visual-Paradigm: UML CASE tool for software development [online]. [cit. 9.4.2013]. Dostupné na: < http://www.visual-paradigm.com/product/vpuml/ > [46] Java.com: What is Java and why do I need it [online]. [cit. 10.4.2013+. Dostupné na: < http://www.java.com/en/download/faq/whatis_java.xml >

69

[47] NetBeans.org: NetBeans IDE - Overview [online]. [cit. 10.4.2013+. Dostupné na: < https://netbeans.org/features/index.html > [48] MySQL.com: MySQL Community Edition [online]. [cit. 11.4.2013+. Dostupné na: < http://www.mysql.com/products/community/ > [49] GNU.org: The GNU General Public License [online]. [cit. 11.4.2013+. Dostupné na: < http://www.gnu.org/licenses/gpl.html > [50] Oracle.com: JDK 6 Swing[online]. [cit. 21.4.2013+. Dostupné na: < http://docs.oracle.com/javase/6/docs/technotes/guides/swing/ > [51] Google Developers: Google Maps API [online]. [cit. 22.4.2013+. Dostupné na: < https://developers.google.com/maps/ > [52] BOZPinfo.cz: Přest{vky řidičů [online]. [cit. 21.4.2013+. Dostupné na: < http://www.bozpinfo.cz/win/rady/otazky_odpovedi/pracovni_doba/dotaz1770 41017.html > [53] W3C: Extensible Markup Language (XML) [online]. [cit. 23.4.2013+. Dostupné na: < http://www.w3.org/XML/ > [54] Oracle.com: Java API for XML Processing (JAXP) [online]. [cit. 24.4.2013]. Dostupné na: < http://docs.oracle.com/javase/tutorial/jaxp/ > [55] TopoGrafix.com: GPX: the GPS Exchange Format [online]. [cit. 26.4.2013]. Dostupné na: < http://www.topografix.com/gpx.asp >

70

Přílohy Obsah přiloženého CD -

Text pr{ce

-

Vývojové diagramy modulu (use case diagramy, datový model, diagram tříd) obsažené v souboru .VPP pro aplikaci Visual Paradigm.

-

Zdrojové kódy aplikace

-

Soubory a n{vod pro instalaci a spuštění modulu

-

Vygenerovan{ dokumentace Javadoc

-

SQL skripty se sadami testovacích a demonstračních dat

71