Obsah 1 ÚVOD CÍL PRÁCE A METODIKA TEORETICKO METODOLOGICKÁ ČÁST PRAKTICKÁ ČÁST CÍL PRÁCE METODIKA

Obsah 1

ÚVOD ....................................................................................................8

2

CÍL PRÁCE A METODIKA ..............................................................9

3

2.1

CÍL PRÁCE ........................................................................................................ 9

2.2

METODIKA ....................................................................................................... 9

TEORETICKO – METODOLOGICKÁ ČÁST .............................11 3.1 3.1.1

Definice Logistiky.................................................................................. 11

3.1.2

Historický vývoj..................................................................................... 13

3.1.3

Funkce dopravy v logistice .................................................................... 14

3.1.4

Oběhové procesy v logistice .................................................................. 15

3.2

DOPRAVNÍ PROBLÉM ..................................................................................... 18

3.2.1

Zařazení dopravního problému .............................................................. 18

3.2.2

Formulace dopravní úlohy ..................................................................... 18

3.2.3

Vybrané typy dopravních úloh............................................................... 21

3.3

4

LOGISTIKA ..................................................................................................... 11

OKRUŽNÍ DOPRAVNÍ PROBLÉM ..................................................................... 22

3.3.1

Matematická formulace okružní dopravní úlohy ................................... 23

3.3.2

Kritéria optimalizace.............................................................................. 24

3.3.3

Omezující problémy............................................................................... 24

3.3.4

Metody řešení okružního dopravního problému .................................... 25

3.3.5

Littlova metoda ...................................................................................... 26

3.3.6

Program STORM ................................................................................... 27

PRAKTICKÁ ČÁST..........................................................................31 4.1

MANUÁLNÍ VÝPOČET ILUSTRATIVNÍHO PŘÍKLADU LITTLOVOU METODOU 31

4.2

CHARAKTERISTIKA SPOLEČNOSTI ................................................................ 36

4.2.1 4.3

Dopravní situace ve firmě DDPNEU..................................................... 37 PODKLADOVÉ ÚDAJE ..................................................................................... 38

4.4

VLASTNÍ VÝPOČET ......................................................................................... 39

4.4.1

Trasa č. 1 ................................................................................................ 40

4.4.2

Trasa č. 2 ................................................................................................ 42

4.4.3

Trasa č. 3 ................................................................................................ 44

4.4.4

Trasa č. 4 ................................................................................................ 46

4.4.5

Trasa č. 5 ................................................................................................ 48

4.4.6

Trasa č. 6 ................................................................................................ 50

4.5

VYHODNOCENÍ VÝSLEDKŮ ............................................................................ 52

4.5.1

Vyhodnocení vzdáleností mezi původními a optimálními trasami........ 52

4.5.2

Náklady na pohonné hmoty ................................................................... 53

4.5.3

Průměrné náklady na jednotku vzdálenosti............................................ 54

5

DISKUSE A ZÁVĚR .........................................................................55

6

POUŽITÁ LITERATURA A PRAMENY ......................................57

7

PŘÍLOHY ...........................................................................................58

7

1 Úvod Význam logistiky neustále roste spolu s narůstající globalizací. Firmy jsou vystavovány silným konkurenčním tlakům a logistika zaujímá v této situaci strategické postavení. Napomáhá zdokonalení zákaznického servisu, na který je od počátku devadesátých let kladen důraz. Umožňuje snižování nákladů a tím dosahování vyšších zisků. Účinnost logistiky se zvyšuje s rozvojem informačních technologií. Pro úspěšnost logistiky je zcela nezbytný systémový přístup. Pochopení vzájemných souvislostí hraje klíčovou úlohu při zvyšování efektivnosti systému jako celku. Důvodů k uplatnění logistiky v hospodářské sféře je celá řada. Především je nutné řešit stále složitější výrobní a distribuční procesy. Je třeba zajistit návaznost jednotlivých dílčích procesů tak, aby byly efektivně využity všechny kapacity. Stále náročnější jsou požadavky na dopravu a její řízení. Optimalizace zásobování může snížit prostředky vázané v zásobách. Optimalizace dopravních tras může vést ke snížení nákladů na pohonné hmoty a také k úspoře času, která vede k zefektivnění dopravy. Tento čas může být využit k zlepšení služeb poskytovaným zákazníkům či jiným konkurenčním výhodám, když ostatní podniky tuto optimalizaci zavedenou nemají. Problematiku distribuce a optimalizace jsem se rozhodl prozkoumat ve své diplomové práci. Doprava a distribuce je jednou z hlavních činností vedoucích k tvorbě zisku ve firmě DDPNEU s.r.o., jejíž distribuční cesty se budu snažit optimalizovat. Jedná se o podnik zabývající se distribucí spotřebního zboží, nástrojů a strojů pro pneuservisy.

8

2 Cíl práce a metodika 2.1 Cíl práce Hlavním cílem této práce je optimalizace dopravy v konkrétním podniku. Kritériem hodnocení úspěšnosti by mělo být posouzení z hlediska nákladů na dopravu a časové náročnosti výpočtu. S použitím softwaru STORM téměř jistě dojde k úspoře času potřebného k výpočtu optimálních dopravních cest. Bylo by vhodné porovnat rychlost a kvalitu řešení se způsobem výpočtu s použitím jiného softwaru. Proto použiji zabudovaného modulu pro optimalizaci trasy v programu Infomapa verze 13 od společnosti PJsoft. Výpočet optimalizace bez použití výpočetní techniky není z důvodu velké časové náročnosti a složitosti modelu podobného rozsahu možný. Dílčí cíle, které vedou k naplnění cíle hlavního, jsou: •

seznámit se s problematikou distribuce v podniku DDPNEU, s.r.o.

•

uvést některé metody, které se nejčastěji používají při optimalizaci distribučních cest

•

přiblížit vybranou metodu a její řešení na jednom ilustrativním příkladě

•

optimalizovat současné dopravní trasy pomocí programu STORM s využitím metody Traveling salesperson's tour (Úloha obchodního cestujícího) a pomocí programu Infomapa

•

zhodnotit zjištěné výsledky

2.2 Metodika K tomu, aby bylo dosaženo cíl této práce, bylo potřeba se seznámit s danou problematikou a prostudovat dostupné literární prameny. Dalšími zdroji informací byly konzultace s pracovníky podniku DDPNEU s. r. o., kteří mi potřebné informace rádi poskytli a vznesli požadavky, které budou od této práce očekávat. Celá práce je rozčleněna na dvě hlavní části. V první teoretické části byla použita metoda kompilační. V prvé řadě bylo potřeba nashromáždit informace, které vycházely z různých odborných publikací a jiných zdrojů, které jsou uvedeny

9

v přehledu literatury. Tato teoretická část se věnuje logistice a teorii s ní spojenou a dále ekonomicko – matematickým optimalizačním metodám a modelům. Ke zpracování praktické části byla použita metoda aplikační, kdy jsou využívány získané znalosti z první části, které jsem se snažil uplatnit v konkrétním podniku. Abych mohl dostát stanoveným cílům, musel jsem se seznámit s problematikou distribuce dané firmy a aplikovat na ni poznatky z teoretické části. Dále je zde použita analýza, která se zabývá pohonnými hmotami a ujetými vzdálenostmi v průběhu roku. Pro optimalizaci dopravních tras byl použit program STORM, který bude více popsán ve vlastní práci. K vyhledávání vzdáleností byl použit program Infomapa verze 13 od společnosti PJsoft, který rovněž obsahuje optimalizační modul, který se pokusím použít a srovnat výsledky s programem STORM.

10

3 Teoreticko – metodologická část 3.1 Logistika 3.1.1

Definice Logistiky

Drahotský, Řezníček (2): Existuje celá řada definic vztahujících se k pojmu logistika. Stručně lze říci, že se logistika zabývá pohybem zboží a materiálů z místa vzniku do místa spotřeby a s tím souvisejícím informačním tokem. Týká se všech komponent oběhového procesu, tzn. především dopravy, řízení zásob, manipulace s materiálem, balení, distribuce a skladování. Zahrnuje také komunikační, informační a řídící systémy. Jejím úkolem je zajistit správné materiály na správném místě, ve správném čase, v požadované kvalitě, s příslušnými informacemi a s odpovídajícím finančním dopadem. Pernica (3): První skutečná definice logistiky vznikla v USA v roce 1964 na půdě CLM (Council oj Logistics Management): logistika je „proces plánování, realizace a kontroly účinného nákladově úspěšného toku a skladování surovin, zásob ve výrobě, hotových výrobků a příslušných informací z místa vzniku do místa spotřeby. Tyto činnosti mohou, ale nemusí, zahrnovat služby zákazníkům, předvídání poptávky, distribuci informací, kontrolu zásob, manipulaci s materiálem, balení, manipulaci s vráceným zbožím, dopravu, přepravu, skladování a prodej“. Logistika byla různými autory teoreticky definována jako: •

„...řízení všech činností, které zajišťují pohyb a koordinaci zásobování a spotřeby při tvorbě časové a místní užitnosti zboží.“ (Haskelt, Ivie, 1964)

•

„...souhrn všech technických a organizačních činností, pomocí nichž se plánují operace související s materiálovým tokem. Zahrnuje nejen tok materiálu, ale i tok informací mezi všemi objekty a časově překlenuje nejrůznější procesy v průmyslu i v obchodě.“ (Kirsch, 1971)

•

„...systém tvorby, řízení, regulace a vlastního průběhu materiálového toku, energie, informací a přemísťování osob.“ (Ihde, 1972)

11

•

„...souhrn všech činností, jimiž se vytvářejí, řídí nebo kontrolují pohybové a akumulační procesy v síti. Jejich vzájemnou souhrou se má uvést do chodu tok objektů v síti tak, aby prosto~ a čas byly překlenuty co nejefektivněji.“ (Pfohl, 1972)

•

„...systém hmotných a nehmotných řetězců tvořený následujícími komponenty, které jsou navzájem propojeny hmotnými a informačními vazbami: doprava, manipulace s materiálem, skladování, balení, územní rozmístění, kontrola zásob, dokumentace, informace, služby.“ (Rose, 1974)

•

„...soubor činností zaměřených na dodání určitého množství zboží s minimálními náklady do místa, v němž v dané době existuje poptávka.“ (Association des Logisticiens ď enterprise, 1980)

•

„...projekt a provoz fyzického, řídicího a informačního systému, který má za cíl, aby výrobky překonávaly čas a prostor.“ (Daskin, 1985)

•

„...soubor všech činností, sloužících k poskytování potřebného množství prostředků s nejmenšími náklady tam a tehdy, kde a kdy je po nich poptávka. Zabývá se všemi operacemi, určujícími pohyb zboží (alokace výroby a skladů, zásob, řízení pohybu zboží ve výrobě, balení, skladování, dodávání odběratelům).“ (International Institut Applied Systems Analyses, 1986)

•

„...technika řízení fyzického pohybu zboží na synchronizované bázi.“ (Wandel, 1988)

•

„...soubor komplexních úloh a z nich odvozených opatření k optimálnímu zajištění toku materiálu, informací a hodnot v transformačním procesu podniku.“ (Rupper, 1990)

•

„... veškerá opatření týkající se toku materiálu, informací a hodnot od vývoje přes plánování a organizaci výroby, zásobování, produkci a distribuci až po zpracování informací.“ (Rupper, 1990)

12

•

„...tvorba, řízení a regulace fyzického toku zboží a jemu odpovídajícího toku informací ke splnění určitého cíle.“ (Kruliš-Randa, 1991)

•

„... věda o koordinaci aktivních a pasivních prvků podniku, směřující k nejnižším nákladům v čase, ke zlepšení flexibility a přizpůsobivosti podniku na měnící se obecné hospodářské podmínky a měnící se trh.“ (Kortschak, 1991)

•

„... věda o koordinaci aktivních a pasivních prvků za účelem zvýšení pružnosti a adaptability subjektu vůči měnícím se rámcovým podmínkám na trhu s minimální potřebou času.“ (Kortschak, 1991)

•

„.. .organizace, plánování, řízení a uskutečňování toku zboží, počínaje vývojem a nákupem a konče výrobou a distribucí podle objednávky finálního zákazníka tak, aby byly splněny všechny požadavky trhu při minimálních nákladech a minimálních kapitálových výdajích.“ (European Logistics Association, 1991)

•

„...časově vztažené umísťování zdrojů nebo, jinými slovy, logistika uvádí do vztahů zboží, lidi, výrobní kapacity a informace, aby byly na správném místě ve správném čase, ve správném množství, ve správné kvalitě za správnou cenu.“ (Institute of Logistics, 1995)

Při pozornějším pročítání uvedených definic nám neunikne, že ačkoliv se někteří jejich autoři snažili o co nejobecnější vyjádření, většina definic neopouští rámec podnikové logistiky. Ta je přirozeně nejčastější aplikační sférou hospodářské logistiky. 3.1.2

Historický vývoj

Drahotský, Řezníček (2): V historii používali pojem logistika nejdříve řečtí filozofové, později se vyskytoval v aritmetice a znamenal praktické počítání s čísly. Již od 9 st. je pak možné setkat se s tímto pojmem ve vojenství. Logistika zajišťovala veškeré potřeby vojska, zásobování potravou, zbraněmi, municí, logističtí důstojníci připravovali vojenské akce, kontrolovali pohyby vojenských jednotek apod.

13

Jako předmět zkoumání se logistika objevuje až na počátku dvacátého století, a to v souvislosti s podporou obchodní strategie podniku a dosahováním užitné hodnoty času a místa. Výrazná pozornost se začala věnovat logistice po druhé světové válce, zpočátku především v USA. Efektivní distribuce a zásobování významně přispěly k úspěchu spojenců. Zásobovací problémy vedly k širokému používání matematických metod pro řešení procesů se zásobováním spjatých. Tyto metody našly své uplatnění po válce v podnikové logistice, ať už se jedná o určení optimálního množství produkce, rozmístění skladů, či problémy spojené s dopravou a jejími náklady atd. Kortschak (1): Rozhodujícím článkem v současném tržním hospodářství se stává zákazník, jehož požadavky určují celý proces výroby. Zákazník (ne zřídka ovlivněn agresivní reklamou) diktuje, co se bude vyrábět, v jakém množství a kdy se to bude vyrábět, Tím ovlivní proces získávání materiálu a surovin, kdy se suroviny nenakupují na sklad, ale pouze v potřebném množství, které bude při výrobě spotřebováno, Nastává proces výroby, jehož výsledkem je výrobek, který musí být dopraven k zákazníkovi rychle, spolehlivě, v požadovaném množství a prvotřídní kvalitě na určené místo. Jelikož zákazník požaduje časté dodávky v malém množství a výborné kvalitě, stává se tento proces velmi krátkým a rychlým, v němž velmi významnou roli sehrává doprava, Právě doprava zajistí dovoz surovin a následnou distribuci hotových výrobků, A protože to, zda se zboží dostane k zákazníkovi včas a v požadovaném množství, ovlivňuje úspěšnost a konkurenceschopnost firmy, bude úloha dopravy v podnicích stále růst, podnik působící v prostředí vyspělého tržního hospodářství, který by neměl vyvinutý logistický systém, není konkurenceschopný. 3.1.3

Funkce dopravy v logistice

Drahotský, Řezníček (2): Dopravní a přepravní systémy mají v logistice, která představuje integrální řízení materiálového toku od dodavatele přes distribuční organizace až ke konečnému spotřebiteli, důležitou roli. Doprava nejen umožňuje propojení jednotlivých částí logistického procesu, tj. vytváření logistických řetězců, ale může také napomoci logistice při řešení míst styku mezi jednotlivými subsystémy

14

logistického procesu. Tento úkol je pro dopravu podstatně jednodušší, pokud přepravní prostředky mohou plnit i určité funkce manipulační, skladovací a obalové jednotky. Cílem logistiky na všech úrovních je maximalizovat efektivnost oběhových procesů a k tomu je nutné, aby byl vytvořen řídící systém, který vedle řízení technologických procesů v jednotlivých činnostech oběhového procesu za pomoci všech s

tím

spojených

informačních

procesů

optimalizuje,

s

využitím

exaktních

a heuristických metod, celkový efekt oběhového procesu. Takový systém je označován jako logistický. Dopravní systém, který vyhovuje logistickému řízení oběhových procesů, označujeme jako logistickou dopravu. Doprava je páteřním systémem logistických procesů, je s nimi funkčně spjatá, ovlivňuje je a je jimi ovlivňována. Proto je nutné hodnotit kvalitu dopravy také jako funkční prvek optimalizace logistického procesu. Kvalita dopravy totiž může optimalizovat podnikové i společenské náklady na oběhové procesy. Je všeobecně známo, že čím kvalitnější dopravu lze poskytnout, tím více lze omezit rozsah skladování a tím i manipulaci s materiálem. 3.1.4

Oběhové procesy v logistice

Drahotský, Řezníček (2): Náplní logistiky oběhových procesů je integrální řízení všech komponent tohoto oběhového procesu. Je tím myšlena doprava, řízení zásob, manipulace s materiálem, balení, distribuce, skladování a také komunikační, informační a řídící systémy. Dále se budeme zabývat pouze dopravou která je náplní této práce. V oblasti dopravy začala logistika nabývat na významu na přelomu 70. a 80. let, kdy došlo k deregulaci dopravního průmyslu. Nastal nárůst konkurence v rámci jednotlivých druhů doprav i mezi druhy navzájem. Přepravci získali více možností dopravy, stali se pružnější a konkurenceschopnější. Doprava jako taková zajišťuje přesun výrobků v prostoru, z místa výroby do místa spotřeby, a zvyšuje tak jejich hodnotu. Dále pak ovlivňuje rychlost a spolehlivost, s jakou se tento přesun uskuteční. Včasné a kvalitní dodání výrobků zvyšuje přidanou hodnotu pro zákazníka a tím i úroveň zákaznického servisu. Náklady spojené s přepravou jsou ale jedny z největších v logistice a často se významnou měrou podílejí na ceně výrobků.

15

Zajišťování požadované úrovně zákaznického servisu je významnou součástí logistického řízení. Dopady přepravy na zákaznický servis jsou jedny z nejdůležitějších. Přepravní servis musí být především spolehlivý, významnou úlohu hraje doba přepravy a pokrytí trhu. Pro zákazníky je též významná pružnost v poskytování přepravních služeb a řešení ztrát či poškození. Využití logistiky ve výrobních a obchodních organizacích klade na dopravní firmy, které chtějí logistické služby poskytovat, mnohé požadavky. Jestliže tyto firmy chtějí být na trhu úspěšné, musí se orientovat na logistické potřeby svých zákazníků, jejich výrobní proces, směnnost, charakter vyráběné produkce apod. Základním posláním nákladní dopravy je uspokojování přepravních potřeb zákazníků. Hlavními předpoklady spolehlivého fungování dopravy je vytvoření a usměrňování fungujících dopravních systémů v rámci jednotlivých oborů dopravy a koordinovaný rozvoj dopravního systému jako celku. Silniční doprava umožňuje nejširší pokrytí trhu. Její flexibilita je do značné míry dána hustotou silniční sítě. Pro svou univerzálnost většinou nejlépe vyhovuje požadavkům zákazníků, a proto se objem zboží přepraveného autodopravci stále zvyšuje. Železniční síť není zdaleka tak hustá jako síť silniční, železniční doprava je omezena na pevně dané tratě, a proto nedosahuje pružnosti dopravy silniční. Jednou z výhod železniční dopravy je skutečnost, že je levnější než doprava silniční či letecká. Bývá s ní však spojeno větší procento ztrát a poškození. Letecká doprava je stále ještě považována za nadstandardní způsob přepravy. Je schopna realizovat nejkratší dobu přepravy, ale s vysokými náklady. Bývá využívána pro produkty s vysokou hodnotou, a to právě z důvodu vysoké ceny za přepravu. Poskytovaný servis je relativně spolehlivý. Pod pojem lodní doprava je možné zahrnout dopravu po vnitrozemských vodních cestách, lodní dopravu po jezerech, přípobřežní námořní dopravu a mezinárodní námořní dopravu. Na rozdíl od letecké dopravy, vodní doprava je využívána především pro produkty s nízkou hodnotou, zejména pro hromadné substráty.

16

Uplatňuje se v případech, kdy rychlost přepravy není určující. Ze všech druhů dopravy je patrně nejlevnější. Potrubní doprava je vhodná pro přepravu látek kapalných, plynných, případně takových, které lze zkapalnit. Nejčastěji se přepravuje zemní plyn, ropné produkty, chemikálie či voda. Tok uvnitř potrubí je sledován a řízen počítači, potrubí minimalizuje vliv klimatických podmínek na přepravu, téměř nedochází ke ztrátám a poškození. Tento způsob přepravy je spolehlivý a z hlediska nákladů výhodný. Významné postavení v dopravě jakožto jedné z komponent oběhového procesu zaujímá kombinovaná doprava. Tento způsob dopravy umožňuje využití výhod jednotlivých dopravních oborů. Základním prvkem kombinované dopravy jsou unifikované přepravní jednotky, kterými jsou v našich podmínkách kontejnery a výměnné nástavby. lntermodální doprava je založena na přepravě zboží v jedné a téže nákladové jednotce nebo vozidle postupným použitím různých druhů dopravy bez manipulace se samotným zbožím při změně druhu dopravy. Kombinovanou dopravu podle použité ložné jednotky členíme na: •

přepravu na paletách

•

přepravu v kontejnerech

•

přepravu ve výměnných nástavbách

•

přepravu silničních návěsů na železničních vozech

•

přepravu celých silničních jízdních souprav na železničním voze

•

přepravu pomocí podvojných návěsů.

Technologie přepravního procesu v kombinované dopravě a specializované parametry technických prostředků včetně přepravních jednotek umožňují účelnější řešení míst styku jednotlivých druhů dopravy. Současně zajišťují i vyšší kvalitu propojení dopravních systémů s manipulací s materiálem a skladováním. Kombinovaná doprava je vhodná pro přepravu prakticky všeho zboží, které se přepravuje v kterémkoliv dopravním prostředku. S vlastní přepravou jsou spojeny další logistické služby, které jsou zajišťovány operátory kombinované dopravy a v překladištích.

17

Kombinovaná doprava představuje kvalitativní posun v uspokojování požadavků zákazníků a je současně příkladem řešení komplexního dopravně-logistického problému. V určitém slova smyslu můžeme říci, že kombinovaná doprava představuje základ dopravní logistiky. K těžišti logistiky bezesporu patří spediční služby. Zasílatelé mají široké možnosti při logistickém řízení. V současné době představuje spedice neboli zasílatelství určitý spojovací článek mezi dodavatelem nebo odběratelem a dopravcem. Jde vlastně o organizování, řízení a koordinování celého průběhu přepravy, o zajištění dodání zboží v pravý čas na správné místo. Zasílatel organizuje dopravu zboží pro obchod a průmysl na základě logistických principů a tím minimalizuje dopravní náklady a rizika, dále radí příkazci ve všech dopravních otázkách, pomáhá při přepravě, zajišťuje přepravu a provádí účelná opatření, aby zásilka došla k příjemci včas a řádně. Pro přepravu je zvolena nejvýhodnější trasa a dopravní prostředky.

3.2 Dopravní problém 3.2.1

Zařazení dopravního problému

Rašovský, Šišláková (4): Dopravní úlohy patří do kategorie distribučních úloh, která je částí úloh lineárního programování. Při zkoumání distribučních úloh aplikujeme teorii lineárního programování; k jejich řešení na samočinném počítači často používáme simplexovou metodu, jako universální metodu řešení úloh lineárního programování. Při řešení simplexovou metodou v její původní formě však mohou vzniknout potíže spojené s velkými rozměry simplexové tabulky. Již malé distribuční úlohy vedou k rozsáhlým simplexovým tabulkám. Specifický tvar omezujících podmínek distribučních úloh dovoluje použít pro jejich řešení speciální algoritmy, které jsou jednodušší, i když v zásadě vycházejí ze simplexové metody. 3.2.2

Formulace dopravní úlohy

Korda, Bukovský, Eichler (8): Dopravní úlohy patří k nejjednodušším úlohám lineárního programováni, a proto také, z historického hlediska, k úlohám nejdříve formulovaným a řešeným. Přes svou jednoduchost mají tyto úlohy poměrně široké

18

možnosti uplatněni v hospodářské praxi. Dají se především použít při hledáni nejefektivnějšího programu (plánu) rozvozu určitého stejnorodého zboží. Ale, jak ukážeme později, lze modelu dopravní úlohy použít i k řešení jiných praktických problémů. Jablonský (9): V dopravním problému se v typickém případě jedná o rozvržení rozvozu nějakého zboží či materiálu z dodavatelských míst (zdroje) odběratelům (cílová místa) tak, aby byly minimalizovány celkové náklady související s tímto rozvozem. Rašovský, Šišláková (4): Dopravní úlohu formulujeme za těchto předpokladů: •

přepravujeme stejnorodý produkt od dodavatelů k odběratelům;

•

je uvažována mezi každým dodavatelem a odběratelem pouze jedna dopravní cesta;

•

po každé dopravní cestě lze převážet libovolné množství produktu;

•

náklady spojené s přepravou jsou přímo úměrné přepravovanému množství produktu.

Předpokládáme, že je dáno m dodavatelů D1 , D2 ,......... , Dm , kteří mají k dispozici al, a2,..., am jednotek produktu. Tento produkt je třeba přepravit k n odběratelům S1, S2 , ..., Sn jejichž požadavky jsou bl, b2, ..., bn jednotek produktu. Veličiny ai (i = 1,2, ..., m) a bj (j = 1,2, ..., n) jsou vyjádřeny nezápornými reálnými čísly ve stejných měrných jednotkách. Dále jsou zadány náklady na přepravu jednotky produktu od i-tého dodavatele k j-tému odběrateli, které označíme symbolem cij. Přepravované množství produktu od i-tého dodavatele k j - tému odběrateli označíme xij. Veličiny cij nejčastěji představují vzdálenost mezi dodavateli a odběrateli v km. Hledané proměnné xij jsou vyjádřeny ve stejných měrných jednotkách jako veličiny ai a bj . Chceme organizovat přepravu produktu od dodavatelů k odběratelům tak, abychom plně uspokojili požadavky odběratelů na daný produkt a přitom aby celkové náklady na přepravu byly minimální. Matematicky můžeme všechny uvedené požadavky formulovat následujícím způsobem:

19

Máme nalézt taková čísla xij při kterých bude m

n

Z min = ∑∑ cij xij

(3.1)

i =1 j =1

při omezeních n

∑x i =1

ij

≤ ai

(i = 1, 2, ... , m)

(3.2)

ij

= bj

(j = 1, 2, ... , n)

(3.3)

(i = 1, 2, ..., m ; j = 1, 2, ... , n)

(3.4)

m

∑x j =1

xij ≥ 0

Účelová funkce (3.1) vyjadřuje závislost mezi strukturou přepravy a celkovými náklady. Soustava omezujících podmínek (3.2) říká, že součet přepravovaného množství jednotek produktu od i-tého dodavatele (i = 1,2, ..., m) ke všem odběratelům musí být menší nebo roven kapacitě tohoto i-tého dodavatele. Soustava omezujících podmínek (3.3) udává, že součet přepravovaného množství jednotek produktu k j-tému odběrateli (j = 1, 2, ..., n) od všech dodavatelů se musí rovnat požadavku tohoto j-tého odběratele. Soustava omezujících podmínek (3.4) zaručuje nezápornost přepravovaného množství jednotek produktu od i-tého dodavatele (i = 1, 2, ..., m) k j-tému odběrateli (j = 1,2, ...,n).

Jablonský (9): Při řešení dopravního problému je třeba uvažovat vztah celkové kapacity všech zdrojů míst

∑b j

j

∑a i

i

(součet všech dílčích kapacit) a všech požadavků cílových

(součet požadavků).

Případ, ve kterém

∑a i

i

=

∑b j

j

, označujeme jako vyrovnaný dopravní

problém (také úloha ve standardním tvaru), tzn. všechny požadavky budou přesně

uspokojeny a všechny kapacity budou vyčerpány. Dopravní problém, ve kterém

∑a ≠∑ b i

i

j

j

, označujeme jako nevyrovnaný

dopravní problém. Při převisu na straně nabídky zůstane část kapacity nevyužita,

při převisu na straně poptávky nebudou uspokojeny všechny požadavky.

20

Nevyrovnaný problém lze snadno převést na vyrovnaný následujícím způsobem: •

při převisu nabídky doplněním fiktivního odběratele, jehož požadavek

∑ a −∑ b

bude roven

i

i

j

j

, tj. rozdílu mezi celkovými kapacitami

a požadavky. •

při převisu poptávky doplněním fiktivního dodavatele, jehož kapacita bude

∑ b −∑ a

rovna

j

j

i

i

, tj. rozdílu mezi sumou požadavků a kapacit.

Ocenění takto nabytých fiktivních článků modeluje nulové (cij = 0). V případě, že omezující podmínky (3.2) se splňují jako rovnice pro všechna i = 1,2, ..., m pak hovoříme o dopravní úloze ve standardním tvaru, kterou zapíšeme

takto: m

n

Z min = ∑∑ cij xij

(3.5)

i =1 j =1

n

∑x i =1

ij

= ai

(i = 1, 2, ... , m)

(3.6)

ij

= bj

(j = 1, 2, ... , n)

(3.7)

m

∑x j =1

xij ≥ 0

(i = 1, 2, ... , m ; j = 1, 2, ... , n)

(3.8)

V dopravní úloze zapsané ve standardním tvaru se splňují oba typy omezujících podmínek (3.6) a (3.7) současně, tj. musí nevyhnutelně platit: m

n

∑∑ x i =1 j =1

n

ij

m

m

n

i =1

j =1

= ∑∑ xij =∑ ai =∑ b j j =1 i =1

(3.9)

Vztah (3.9) udává, že sečteme-li všechny veličiny xij v řádcích (sloupcích) pak se musí tento

součet rovnat součtu kapacit dodavatelů (odběratelů). Platnost vztahu (3.9) je podmínkou řešitelnosti dopravní úlohy. 3.2.3

Vybrané typy dopravních úloh

Dopravní model s tranzitem Korda (5): V reálných dopravních problémech se často setkáváme s tranzitními stanicemi, tj. se stanicemi, které dané zboží i přijímají i odesílají. Přitom se může stát,

21

že je výhodnější z jedné stanice posílat zboží do druhé přes třetí stanici, než je poslat přímo. Můžeme tedy dopravní úlohu zobecnit tak, že předpokládáme, že všechny stanice dopravují také tranzitní zboží. Jsou-li známy dopravní sazby mezi všemi stanicemi, vzniká otázka, jak rozvrhnout dopravu daného zboží, skladovaného v m prvních stanicích a požadovaného v daných množstvích v ostatních stanicích, aby celkové náklady na přepravu byly minimální. Získal (10): Modely těchto dopravních problémů lze z hlediska složitosti dopravních podmínek rozlišovat podle počtu stupňů a podle rozměru modelu. Stupně přepravy jsou definovány podle počtu tranzitů, míst, přes která doprava probíhá a která mají být optimálně vybírána k jednotlivým trasám. Rozměr dopravní úlohy představuje typ dopravního prostředku, druh přepravovaného materiálu, čas potřebný k přepravě apod., takže vícerozměrný dopravní systém umožňuje optimalizovat i způsob dopravy. Modely optimalizace přímých dopravních tras Získal (10): Do této skupiny se řadí především dva modely teorie grafů. Prvním z nich je problém nalezení nejkratší cesty mezi libovolnými dvěma místy v dané dopravní síti s délkově ohodnocenými komunikacemi. Problém se řeší vyhledáním nejkratší cesty v ohodnoceném grafu. V případě, že jsou jednotlivé komunikace ohodnoceny svojí propustností, která umožňuje za časovou jednotku projetí jen určitého počtu vozidel, jde o problém teorie toků v sítích a účelem je nalézt maximální tok, tj. maximální propustnost ze všech cest

spojujících uvažované dva uzly (stanice). Okružní dopravní problém Tomuto tématu je věnována samostatná podkapitola, protože představuje významnou část této práce.

3.3 Okružní dopravní problém Pelikán (6): Distribuční úlohy, ve kterých se doprava realizuje okružními jízdami, patří mezi nejčastěji řešené úlohy operačního výzkumu. Navazují na úlohy alokační, ve kterých se rozmisťují sklady, závody apod., na úlohy rajonizační, které optimalizují tvorbu zásobovacích rajonů, přiřazených určitému centru, skladu apod. Úlohy alokační

22

a rajonizační i okružní jsou spolu těsně svázány, komplexní řešení všech tří úloh najednou je ale nerealizovatelné, proto se úlohy řeší většinou odděleně. Okružní úlohy jsou úlohy hledání optimální trasy pro vozidla realizující přepravu okružním způsobem, kdy uzly distribuční sítě jsou obsluhovány (zásobovány apod.) během jedné jízdy, nebo několika jízd, které většinou začínají a končí ve výchozím uzlu sítě. Účelem je minimalizovat celkovou délku tras vozidel s respektováním požadavků odběratelů i technologických omezení dopravních prostředků. Hledání optimálních okružních tras většinou vychází z určité komunikační sítě (například silniční sítě se zadanými kilometrovými vzdálenostmi), u sítě uvnitř městské zástavby z plánu ulic a dopravních omezení (zákazy vjezdu, jednosměrný provoz, ...). Pokud nejsou k dispozici vzdálenosti mezi komunikačními uzly, je možné tuto vzdálenost přibližně určit na základě euklidovské vzdálenosti bodů na mapě (daných souřadnicemi) nebo na základě „obdélníkové“ vzdálenosti v případě městské sítě, kde vzdálenost musí respektovat většinou pravoúhle se křížící městské komunikace. 3.3.1

Matematická formulace okružní dopravní úlohy

Rašovský, Šišláková (4): Nechť máme: •

n návštěvních míst, přičemž vyjíždíme z i-tého místa a jedeme do j-tého místa;

•

n kroků trasy (např. 1 krok je přejezd z výchozího stanoviště do prvního

návštěvního místa, poslední krok je přejezd z předposledního návštěvního místa do výchozího stanoviště); (k= 1,2, ...,n) a nechť •

cij je vzdálenost mezi i-tým a j-tým návštěvním místem;

•

xijk je uskutečněná (xijk=l) nebo neuskutečněná (xijk=0) cesta mezi i-tým a j-tým návštěvním místem v k-tém kroku. Při daném označení zformulujeme úlohu takto. Máme nalézt taková čísla xijk,

při kterých n

n

n

Z min = ∑∑∑ cij xijk i =1 j =1 k =1

23

při omezeních m

n

∑∑ x i =1 j =1 m

=1

(k = 1, 2, ... , n)

ijk

=1

(i = 1, 2, ... , n)

ijk

=1

(j = 1, 2, ... , n)

n

∑∑ x j =1 k =1 m

ijk

n

∑∑ x i =1 k =1

při k = n je k + 1= 1

 0 xijk =  1 3.3.2

(i,j,k = 1, 2, ... , n)

Kritéria optimalizace

Pelikán (6): I když ve většině případů se hledají nejkratší cesty a okruhy, mohou se kriteriem optimalizace stát i náklady, do kterých se promítá kromě kilometrové vzdálenosti také spotřeba, pronájem vozidla, náklady na prostoje vozidla, které se u různých typů vozidel mohou lišit. V některých specifických případech je omezujícím faktorem i čas nutný k rozvozu zboží, zejména jde-li o časově limitované služby, kde okružní trasy musí být takové, aby rozvoz zakázek byl splněn do určitého termínu u všech uzlů sítě.

3.3.3

Omezující problémy

Pelikán (6): Základním omezujícím faktorem tvorby tras je množství převáženého materiálu. Je tedy nutné znát požadavky odběratelů u rozvozů a svozů (případně množství zboží pro zásobování a množství obalů na odvoz). Toto množství může být udáváno váhově, ale i objemově (pokud je pro naplnění vozidla rozhodující objem a váha zboží není limitujícím faktorem). Existují případy, kdy množství zboží vůbec není omezujícím faktorem (svoz pošty z poštovních schránek, rozvoz a svoz fotografických zakázek apod.). V jiných případech jsou rozhodující pro přepravované zboží rozsah nosné plochy vozidla, které toto zboží zabírá (nábytek, kontejnery, bedny, přepravky, plynové láhve…).

24

3.3.4

Metody řešení okružního dopravního problému

Existuje celá řada metod vedoucích k řešení okružního dopravního problému. Vyjmenujme si zde některé z nich.

Dantzigova, Fulkersonova a Johnsonova metoda Rašovský, Šišláková (4): Tato metoda převádí řešení okružního problému na úlohu celočíselného programování řešenou simplexovou metodou. Postup je značně komplikovaný. V podstatě využívají přiřazovací problém s maximální degenerací.

Croesova metoda V tomto případě řeší problém postupným zlepšováním počátečního řešení určitými změnami v pořadí vrcholů tak dlouho, dokud je to možné. Nalezené řešení ovšem obecně není optimální. K nalezení optima se používá dalšího značně složitého postupu.

Habrova přibližná metoda Další metoda řeší okružní dopravní problém tak, že vytváří okruh ze všech možných spojení mezi jednotlivými místy, vybírá a do okruhu zařazuje takové spoje, které jsou co nejvýhodnější z hlediska celé uvažované dopravní soustavy (dopravní sítě). Tento globální pohled na okružní úlohu zajišťují „Habrovy frekvence“, které jsou známé z klasické dopravní úlohy. Obecně lze říci, že ze všech možných spojení mezi jednotlivými místy se vybere a do okruhu zařadí nejprve to spojení míst (i, j), které odpovídá nejvýhodnější frekvenci (fij). Pak se hledá nejvýhodnější frekvence (fjk) pro navazující spojení a příslušný úsek se zařadí do okruhu. Takto se pokračuje v návaznostech (fkl, flm, ...), až se celý okruh uzavře.

Littlova metoda Poslední metoda, která je zde uvedena, je založena na metodě větvení a mezí. Množina všech přípustných řešení (cyklů) se dělí na stále se zmenšující podmnožiny. Pro každou podmnožinu se vypočte hranice minimální dosažitelné délky cyklu. Postup končí, je-li nalezeno řešení s nejmenší hodnotou spojení rovnou nejnižší určené hranici. Metoda je vhodná pro stanovení okružní trasy při neomezené kapacitě vozidel. Vzhledem k tomu, že je touto metodou řešen praktický příklad, jí bude věnována samostatná podkapitola.

25

3.3.5

Littlova metoda

Rašovský, Šišláková (4): Zjednodušený algoritmus řešení okružního problému lze popsat takto: 1. Redukujeme výchozí matici vzdáleností mezi jednotlivými návštěvními místy, tj. od každého řádku a každého sloupce matice odečteme nejnižší sazbu (transformační konstantu) nacházející se v příslušném řádku a sloupci. Touto redukcí získáme v každém řádku a sloupci alespoň jednu nulovou sazbu. Řešení úlohy s takto redukovanou maticí je ekvivalentní s řešením původní úlohy. 2. Vypočteme hodnotu Z0 o kterou se sníží hodnota účelové funkce libovolného přípustného řešení při odpočtu příslušných transformačních konstant. n

n

i =1

j =1

Z 0 = ∑ ai + ∑ b j ai .... transformační konstanta odpovídající i-tému řádku (i = 1,2, ..., n) bj .... transformační konstanta odpovídající j-tému sloupci (j= 1,2,..., n)

3. Pro všechny redukované vzdálenosti rovné nule (cij = 0) stanovíme hodnoty

φij = ci′, min + c ′j ,min , kde ci′, min ........nejmenší redukovaná vzdálenost v i-tém řádku c ′j ,min ........nejmenší redukovaná vzdálenost v j-tém sloupci

4. Vyhledáme max φi , j = φ max , jenž nám určuje zařazení cesty z i-tého místa i, j

do j-tého místa do okruhu. Je-li více φ max pak je lhostejné, které cestě dáme přednost. 5. Vypočítáme hodnotu účelové funkce Z i j při nezařazení cesty z i-tého místa do j-tého místa do okruhu.

Z i j = Z 0 + φmax

26

6. Vynecháme i-tý řádek a j-tý sloupec redukované matice vzdáleností a současně vyloučíme vratnou cestu (tj. jízdu z j-tého místa do i-tého místa) tím, že příslušné pole v matici označíme symbolem ∞. 7. V případě, že v každém řádku a každém sloupci redukované matice vzdáleností po provedení bodu 6 není ani jedno cij = 0, pak provedeme další redukci vzdáleností pomocí nových transformačních konstant (jako v bodu 1) 8. Byla-li do okruhu správně zařazena cesta z i-tého místa do j-tého místa, pak musí platit

Z ij ≤ Z i j , kde Zij = hodnota předcházející účelové funkce +

n

n

i =1

j =1

∑ ai + ∑ b j

Transformační konstanty ai , bj odpovídají bodu 7. 9. Získáme-li redukovanou matici vzdáleností (viz bod 6 a 7) typu 2 x 2, pak uzavřeme okruh po zbývajících cestách a výpočet je ukončen. V opačném případě opakujeme celý postup počínaje bodem 3.

3.3.6

Program STORM

Jablonský (5): STORM je programový prostředek pro řešení a analýzu v praxi nejčastěji používaných úloh z oblasti operačního výzkumu a statistiky. Je to modulový systém, jehož jednotlivé části umožňují řešit úlohy lineárního programování, řízení projektů, teorie zásob, teorie hromadné obsluhy, provádět investiční analýzy atd. Rašovský, Šišláková (4): Optimalizační program STORM je produktem americké firmy Storm Software, Inc., komunikuje v anglickém Jazyce: Je velmi nenáročný na hardwarové vybavení počítače, Je poměrně rychlý a jednoduchý na ovládání. Tento systém pracuje pod MS DOS a tak v tomto systému není možné používat počítačovou myš. Přesto je program lehce ovladatelný pomocí směrových šipek a pomocnými klávesami, jejichž význam je vysvětlen v informačním řádku v dolní části obrazovky. Aktuální volba je barevně zvýrazněna a lze ji měnit i stisknutím pořadového čísla volby (select option).

27

Ovládání programu STORM Rašovský, Šišláková (4): Po spuštění STORMu je uživateli zobrazena úvodní obrazovka a poté hlavní menu (MAIN MENU) celého systému, které obsahuje 18 položek. Každá z těchto položek je samostatným modulem pro řešení konkrétního typu úloh. Úplný přehled MAIN MENU s překladem českého ekvivalentu: 1. Linear & Integer Programming (Lineární a celočíselné programováni) 2. Assignment (Přiřazovací problém) 3. Transportation (Dopravní problém) 4. Distance Networks - Paths, Tours, Trees (Grafické optimalizační úlohy) 5. Flow Networks - MaxFlow, Transshipment (Optimální toky sífl) 6. Project Management - PERT/CMP (Řízení projektů) 7. Queueing Analysis (Modely hromadné obsluhy) 8. Inventory Management (Řízení zásob) 9. Facility Layout (Úlohy optimálního rozmístěni) 10. Assembly Line Balancing (Optimalizace výrobních linek) 11. Investment Analysis (Analýza investic) 12. Forecasting (Prognózování) 13. Production Scheduling (Rozvrhování výroby) 14. Material Requirements Planning (Plánování potřeb materiálu) 15. Statistical Process Control (Statistické řízení procesů) 16. Statistics (Statistika) 17. Delicion Analysis - Single Level (Rozhodovací analýza) 18. Delicion Trees - Multiple Levels (Rozhodovací stromy) Práci s programem STORM lze rozčlenit do následujících kroků, mezi kterými uživatel postupně přechází: 1. Hlavní menu (MAIN MENU) – volba některého z výše uvedených 18 modulů, volbu potvrdíme stisknutím klávesy Enter.

28

2. Vstupní režim (INPUT) – uživatel má na výběr ze dvou možností, potvrzení volby provede stiskem klávesy Enter: a) načíst data z existujícího datového souboru (Read an existing datafile) uloženého na disku či disketě – tuto možnost zvolíme, pokud máme již data vytvořena a uložena. Při načítání datového souboru je nutné specifikovat disk (písmeno bez dvojtečky), adresář a název souboru. b) vytvořit nový datový soubor (Create a new data set) – použijeme, chceme-li vytvořit novou soustavu dat. Soubory vytvořené v určitém modulu programu nelze otevřít v modulu jiném. 3. Editační režim (EDIT) – slouží k vkládání dat, po naplnění editoru potřebnými daty stiskneme klávesu F7, která nás přepne do režimu zpracování (PROCESS). 4. Režim zpracování (PROCESS) – do režimu zpracování se dostaneme po načtení datového souboru z disku nebo po ukončení editace v režimu EDIT. Volby režimu PROCESS: a) Edit the current data set – návrat do STORM EDITORu. b) Save the current data set – uložení naeditovaných dat. c) Print the current data set – tisk dat ze STORM EDITORu. d) Execute the module with the current data set – zpracování úlohy. Můžeme spustit výpočet optimálního řešení. 5. Prohlížení a interpretace získaných výsledků. 6. Ukončení práce se systémem STORM – stiskem klávesy F10. Mezi jednotlivými režimy práce může uživatel libovolně přecházet, k tomu má k dispozici funkční klávesy F6 až F10 se stejnými funkcemi ve všech režimech práce (s výjimkou režimu EDIT).

Optimalizace okružní jízdy Pro řešení problému obchodního cestujícího zvolíme v hlavním menu (MAIN MENU) volbu 4 – Distance networks, tím se dostaneme do editoru modulu okružních úloh.

29

Dostaneme se do nabídky INPUT, kde se nám zobrazí volba, zda budeme podkladové údaje vkládat ručně nebo je načteme z již vytvořeného souboru. Po výběru jedné z možností se zobrazí STORM EDITOR, do kterého pro řešení okružní jízdy vložíme data v následujícím pořadí:

•

Title – krátké označení či popis úlohy

•

Number of nodes – počet uzlů grafu. STORM je schopen řešit úlohy, ve kterých počet uzlů grafu nepřesahuje 50.

•

Distance matrix type (SYM/ASYM) – volíme možnost, zda se jedná o symetrickou matici (vzdálenosti jednotlivých uzlů jsou shodné i v opačném směru) nebo asymetrickou matici (vzdálenosti se liší – např. v důsledku uzavírek silnic, jednosměrných tras,objížděk, apod.)

Pokud jsme vložili všechny nezbytné parametry, postoupíme do oblasti editace dat, kde vyplníme vytvořenou editační tabulku. Vznikne tzv. vzdálenostní matice, kde jsou zobrazeny vzájemné vzdálenosti v kilometrech. Pokud se jedná o symetrickou matici, je povolen pouze vstup prvků horní trojúhelníkové matice. Jedná-li se o nesymetrickou matici, zadáme všechny prvky matice kromě prvků ležících na hlavní diagonále. Jestliže mezi příslušnou dvojící uzlů neexistuje spojení, vyznačíme to ve vzdálenostní matici tečkou (.). Zadání vstupních dat (vzdáleností) potvrdíme stiskem klávesy F7 (Done). Zobrazí se seznam metod, pomocí kterých může být problém řešen. 1. Shortest paths (Nejkratší cesta). 2. Longest paths (Nejdelší cesta). 3. Traveling salesperson's tour (Úloha obchodního cestujícího). 4. Minimal spanning tree (Minimální spojení míst). 5. Maximal spanning tree (Maximální spojení míst). Pro vyřešení problému obchodního cestujícího vybereme třetí volbu. Na obrazovce se zobrazí optimální řešení – minimální vzdálenost a pořadí míst, v jakém je máme navštívit.

30

4 Praktická část 4.1 Manuální výpočet ilustrativního příkladu Littlovou metodou Pro výpočet ilustrativního příkladu jsem si zvolil část linky číslo 2, s počátečním a koncovým uzlem v Mor. Nové Vsi a velikosti matice 6*6 tzn., že řidič navštíví 6 měst. V tomto případě jde o matici symetrickou, jelikož předpokládáme, že neexistují uzavírky ani jednosměrné silnice. V jednotlivých sídlech může být jeden či více odběratelů. Pořadí návštěv si pak určuje řidič sám podle průjezdnosti daného města

či jiných osobních kritérií. Počet odběratelů v jednotlivých obcích nezohledňujeme. Část této trasy, tak jak je používána firmou DDPNEU, měří 148 km. Samotný výpočet provedu pomocí Littlovy metody, která je popsána v kapitole 3.3.5. Je známo, že tato metoda je pouze aproximativní tzn., nemusí nalézt nejmenší okružní trasu. Ke zjišťování vzdáleností jsem použil program Infomapa. Vzdálenosti mezi jednotlivými obcemi jsou uvedeny v kilometrech a zaokrouhleny na celé číslo. Jednotlivé vzdálenosti jsou znázorněny v tabulce č.1. Tabulka č. 1: Vstupní údaje

Mor. Nová Ves Podivín Hustopeče Slavkov u Brna Vyškov Bučovice Zdroj: Autor

Mor. Nová Ves 15 28 51 65 48

Podivín 15 16 45 63 47

Hustopeče 28 16 33 51 42

Slavkov u Brna 51 45 33 19 10

Vyškov 65 63 51 19 17

Bučovice 48 47 42 10 17 -

Samotný výpočet Při výpočtu optimálního řešení budeme vycházet z postupu popsaného v kapitole 3.3.5. Nejdříve provedeme redukci matice vzdáleností mezi jednotlivými místy. Pro každou nulu vypočítáme φij a nalezneme maximum této hodnoty (podtržené). Následně vyjádříme hodnoty Z 0 a Z i j . Tímto jsme provedli body 1 – 5 z výše zmíněného algoritmu. Pro větší přehlednost při výpočtu nahradíme názvy obcí čísly 1 – 6.

31

Tabulka č. 2: Redukce výchozí matice 1 1

-

2 15 0

2

15 0

3

28 12

16 0

4

51 41

45 35

5

65 48

63 46

6

48 38

47 37

12

12 -

3 28 13 12 16 1 0

12

4 51 36

12

45 30

-

33 17

33 23 22 51 34 33 42 32 31

-

5 65 50 43 63 48 41 51 35 28 19 9 2

19 2 10 0

17 7 0

ai

48 33

15

47 32

15

42 26

16

10 0

19

10

17 0

2

17

2

-

10

7

-

-

2

6

83 bj

-

-

1

-

8

Zdroj: Autor 6

6

i =1

j =1

Z 0 = ∑ ai + ∑ b j = 83 + 8 = 91 Z 4 6 = 91 + 19 = 110 Z tabulky je patrné, že jsme vybrali cestu (4 – 6). Zakázaná cesta je cesta vratná tzn. cesta (6 – 4) a v následující tabulce toto pole označíme symbolem ∞. Následuje bod 6, kdy vynecháme čtvrtý řádek a šestý sloupec a opět provedeme redukci. Hledáme maximální hodnotu φij .

32

Tabulka č. 3: Redukce předchozí matice o 4. řádek a 6. sloupec 1

2 0

1

12

-

12

12

-

ai

43 -

0

30

41 -

0

12

5

36

12

3

5

4

12

0

2

3

17

48 46

46 44

33 31

38

37

31

28 -

2 0

48

2

59

-

0

∞

6

-

2 bj

-

-

-

-

-

0

Zdroj: Autor 5

5

i =1

j =1

Z 46 = Z 0 + ∑ ai + ∑ b j = 91 + 2 = 93 Z 46 ≤ Z 46 ⇒ 93 < 110 Z 6 5 = 93 + 59 = 152 Jako další jsme do výpočtu zařadili cestu (6 – 5). Zakázané cesty jsou (5 – 6), (4 – 5), (5 – 4). V další matici vynecháme 6. řádek a 5. sloupec.

33

Tabulka č. 4: Redukce předchozí matice o 6. řádek a 5. sloupec 1

2 0

1

12

12

-

0

-

12

30 13

-

-

17 0

0

12

46 15

31 0

44 13

ai

36 19

0

3

5

4

12

0

2

3

13

13

∞

-

17

-

31 31

bj

-

-

17

Zdroj: Autor 4

4

i =1

j =1

Z 65 = Z 46 + ∑ ai + ∑ b j = 93 + 31 + 17 = 141 Z 65 ≤ Z 65 ⇒ 141 < 152 Z 5 3 = 141 + 13 = 154 V tomto případě bylo možno zvolit mezi cestou (5 – 3) a (3 – 4). Zvolil jsem první z nich. Zakázané cesty jsou (3 – 5), (3 – 4), (3 – 6). Vratnou cestu (3 – 5) v příští matici opět označíme symbolem ∞. Tabulka č. 5: Redukce matice o 5. řádek a 3. sloupec 1

2 0

1

-

6

19 6

12

-

13 0

0 2

4

-

6

-

12

∞

-

-

13

0

12 3

ai

0 bj

-

13

Zdroj: Autor

34

3

3

i =1

j =1

Z 53 = Z 65 + ∑ ai + ∑ b j = 141 + 13 = 154 Z 53 ≤ Z 53 ⇒ 154 < 155 Z 3 2 = 154 + 12 = 166 Zařadíme cestu (3 – 2). Zakázané cesty jsou (2 – 3), (2 – 4), (4 – 2). Poslední tabulka bude o velikosti 2*2, kdy nám podle bodu 6 zbyly nakonec dvě cesty a to cesta vratná a cesta z bodu 1 do 1, což nemůžeme považovat za spojení dvou rozdílných míst. Tabulka č. 6: Redukce matice o 3. ř. a 2. sl. 1 1

4

ai

6 0

0

6

∞

2

6

bj

-

-

0

Zdroj: Autor 2

2

i =1

j =1

Z 32 = Z 53 + ∑ ai + ∑ b j = 154 + 6 = 160 Z 32 ≤ Z 32 ⇒ 160 < 166 Podle bodu 9 nám okružní cesta končí cestami (1 – 4) a (2 – 1). Délka trasy je 160 km, což může zjistit podle Z32 = 160 nebo dosazením jednotlivých spojení do výchozí matice (10+17+51+16+15+51=160). Jak je uvedeno výše tato metoda nám nenalezla minimální trasu, ale nalezla pouze trasu blízkou této hodnotě. Trasu můžeme znázornit jako: Obr. č. 1: Graf okružní jízdy 4

6

1

5

2

3

Zdroj: Autor

35

Zpětným dosazením názvů obcí za čísla dostaneme tuto optimální trasu: Moravská Nová Ves, Slavkov u Brna, Bučovice, Vyškov, Hustopeče, Podivín a zpět do Moravské Nové Vsi.

4.2 Charakteristika společnosti Firma DDPNEU s. r. o. vznikla v roce 2003 a předmětem podnikání je obchodní činnost a poskytování služeb spojených s touto činností. Historie této společnosti se datuje do roku 1996. Nejdříve šlo o fyzickou osobu Daniela Doricu a jednoho zaměstnance, kdy oba pracovali jako obchodní zástupci. Zabývali se zásobováním pneuservisů výrobky japonské společnosti MARUNI, vyvažovacími

závažími

značky

ROTOBALANCE,

ventily,

dušemi,

chemii

pro pneuservisy, vzduchovým nářadím CHICAGO – PNEUMATIC a spotřebním materiálem. Sídlo firmy bylo v Lužicích. Dalším významným rokem byl rok 2001, kdy se firma Daniel Dorica stává výhradním dovozcem i distributorem společnosti SCHRADER v české i slovenské republice. V roce 2003 se stává z fyzické osoby osoba právnická DDPNEU s. r. o. se sídlem v Moravské Nové Vsi. Od roku 2006 do současnosti je firma DDPNEU výhradním zástupcem společností

SCHRADER,

B.

F.,

ROTOBALANCE,COMPAK,

PNEUTEC

a distributorem značek T – GUM, ATEK MAKINA a VIRAGO. V současné době firma zaměstnává 11 lidí, 6 obchodních zástupců, 3 technicko – hospodářské pracovníky a 2 skladníky. Zákazníků mají celkem kolem 750, z toho 550 objíždějí obchodní zástupci automobily a zbylých 200 je obsluhováno přes internetový obchod nebo telefonicky a zboží je dopravováno pomocí služby PPL. Každý obchodní zástupce má svěřený region a týdně navštíví 80 – 100 stálých zákazníků. To jim dává jistotu, že dostanou vše, co potřebují ke své práci.

36

Posláním firmy je poskytovat co možná nejlepší zboží, služby a vztahy, a to tak, aby název firmy DDPNEU s.r.o. pro ně byl synonymem kvality, spolehlivosti a vzájemné důvěry. S touto firmou je spojeno logo "POČÍTEJTE S KVALITOU" a to je také priorita firmy DDPNEU s.r.o.. Každý zákazník se může spolehnout jak na kvalitu prodávaného sortimentu, tak na kvalitu služeb. Nabízí školení přímo u zákazníka a také následný poradenský servis po telefonu nebo při pravidelných návštěvách obchodních zástupců. Společnost stále pracuje na hledání nových produktů a zavádění nových služeb pro uspokojení všech profesních potřeb svých zákazníků.

4.2.1

Dopravní situace ve firmě DDPNEU

Hlavní náplní dané společnosti, jenž tvoří nejvyšší část obratu, je bezesporu obchodní

činnost prováděná pomocí obchodních zástupců, kteří navštěvují zákazníky zejména z řad pneuservisů, ale i autoservisů. Jednou z podstatných položek při tvorbě nákladů jsou náklady na dopravu. Proto je nutné se pokusit tyto náklady minimalizovat. Distribuci zboží si podnik zajišťuje z velké části sám pravidelnými návštěvami u svých stálých zákazníků. Objednávky přes elektronický obchod či urgentní objednávky řeší pomocí dopravní společnosti PPL, která dodá zákazníkovi zboží do 24 hodin. Sídlo firmy i skladovací prostory se nachází v Moravské Nové Vsi. Pracují zde dva skladníci, kteří zajišťují nakládku a vykládku automobilů. Každé z těchto vozidel tvoří, dalo by se říct, samostatný minisklad, jelikož obsahuje 90% sortimentu umístěného v hlavních skladovacích prostorách. Vozový park firmy obsahuje celkem devět vozidel. THP pracovníci používají dvě osobní vozidla, obchodní zástupci používají šest dodávek plus jedno náhradní. Přehled vozidel a jejich spotřeba, jak mi byla nahlášena, se nachází v tabulce č. 7.

37

Tabulka č. 7: Přehled vozidel

Typ vozidla dodávka dodávka dodávka dodávka dodávka dodávka pick – up osobní osobní

Značka vozidla VW LT 2,8Tdi FORD Tranzit 2,0 TDI Citroen Jumper 2,5 TDI Renault Master 2,8 TDI Renault Master 2,2 dci Renault Master 2,5 dci Škoda Felica Pick – up Škoda Octavia 1,9 TDI Škoda Octavia 2,0 TDI

Spotřeba l/100km 10,7 9,2 10,5 11,3 9,4 10 7,4 6,5 6,8

Palivo nafta nafta nafta nafta nafta nafta natural 95 nafta nafta

Zdroj: Autor

Rozvozní plány jsou koncipovány tak, aby pravidelně uspokojovaly požadavky zákazníků. V našem případě to znamená jedenkrát týdně. Jednotliví obchodní zástupci přijíždějí různé dny v týdnu do skladu, aby nebyl sklad zahlcen a nevznikaly zde prostoje. Naloží zde zboží a vyřídí potřebnou administrativu, případně dostanou pokyny od vedení společnosti. Každý obchodní zástupce si plánuje okružní jízdu sám podle vlastních zkušeností či požadavků zákazníků. Neexistuje zde žádná metoda pro minimalizaci ujetých kilometrů, i když se o to prodejci snaží.

4.3 Podkladové údaje Podkladové údaje jednotlivých tras jsem získal od obchodního manažera firmy DDPNEU. Tyto údaje byly získány pomocí systému CCS – MONITOR, který je nainstalován v jednotlivých vozidlech. Tento systém sleduje pohyb, spotřebu, rychlost a ujetou vzdálenost. Údaje se musely z tohoto systému vyexportovat a upravit do podoby, která bude použitelná pro optimalizaci v programu STORM. Touto úpravou jsme získali pořadí zákazníků, tak jak byli navštíveni. Po dohodě s vedením společnosti budeme zanedbávat počet a pořadí zákazníků v jednotlivých obcích. Tento problém si vyřeší samotní obchodní zástupci na základě zkušeností, otvírací doby, jednosměrných ulic, uzavírek, či jiných omezujících podmínek.

38

Jednotlivé vzdálenosti mezi obcemi jsem získal z programu Infomapa verze 13 od společnosti PJsoft, který mi byl neocenitelným pomocníkem. Využil jsem k tomu funkci automobilové spojení. Všech šest vzdálenostních matic je symetrických a jednotlivé vzdálenosti, jsou zaokrouhleny na celé kilometry.

4.4 Vlastní výpočet Vlastní výpočet provedeme pomocí programu STORM. Vybereme funkci Distance

Networks - Paths, Tours, Trees a postupujeme podle návodu uvedeného v kapitole 3.3.6. Musíme brát v úvahu také určité změny trasy. Může se stát, že získáme nového zákazníka. Toto lze řešit dvěma způsoby. Vytvoříme novou vzdálenostní matici,

či jednoduše zeditujeme soubor názevtrasy.dat. V případě, že ztratíme stávajícího zákazníka, zmáčkneme klávesu F6 v potřebném uzlu a tím ho vyřadíme z tabulky (v přílohách budou uvedeny vstupní i výstupní tabulky jednotlivých tras tak jak jsou použity v programu STORM) V následujících podkapitolách (4.4.1 až 4.4.6) bude mít výpočet následující strukturu: 1. Skutečná okružní trasa 2. Vzdálenostní matice č. (1-6) 3. Nová okružní trasa navržena programem STORM 4. Porovnání skutečné vzdálenosti s vypočítanou trasou

39

4.4.1

Trasa č. 1

Skutečná okružní trasa Tabulka č. 8: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Třinec Frýdek-Místek Český Těšín Karviná Bohumín Ostrava Opava Krnov Holešov Hulín Kroměříž Olomouc

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Litovel Svitavy Litomyšl Česká Třebová Nové M. na M. Boskovice Havířov Kopřivnice Jeseník Bruntál Mohelnice Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 1 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 10: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Kroměříž Hulín Holešov Kopřivnice Frýdek-Místek Havířov Český Těšín Třinec Karviná Bohumín Ostrava Opava

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Krnov Bruntál Jeseník Olomouc Litovel Mohelnice Svitavy Česká Třebová Litomyšl Nové M. na M. Boskovice Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1253 km. Optimální trasa navržená programem STORM je 769 km. Rozdíl činí 484 km. Vyjádřeno v procentech je nová trasa kratší o 38,63 %.

40

2 3 4 5 6 7 8 9 10 11 12 13 14 15

41

16 17 18 19 20 21 22 23 24

x

10

11

12

186 160 182 189 181 168 167 181 85

2

79

73 108 117 126 144 146 120 97 175 144 193 160 131

x

3

4

5 23

6 39

7 42

8 71

9

13

14

15

16

17

18

19

20

95 101 110 116 114 133 183 199 193 217 165 26

21

22

23

24

26

9

x

23

30

30

20

49

73

76

x

15

30

33

63

87

98 106 113 110 130 180 195 190 214 162 17

43 140 98 143

x

17

25

54

77 104 113 120 114 130 180 195 189 218 166 15

49 130 89 142

x

14

38

62

96 105 112 104 114 164 179 174 206 156 19

44 115 73 127

x

30

54

84

92

99

92 106 156 171 166 196 144 16

31 107 66 119

x

25

82

91

97

70

77 127 142 137 169 125 46

49

77

36

90

x

106 109 112 74

73 115 130 123 157 122 70

73

56

22

77

x

84

91

88 108 158 173 168 192 140 15

46 107 107 147 21

85

85 121

9

15

42

61 107 124 121 133 81

90

61 125 91

74

x

7

39

58 100 117 116 126 74

99

69 122 88

72

x

42

59

96 113 112 121 70 106 76 125 92

73

x

20

70

34

x

53 x

x

11

45

55 187 158 100 108 52

x

56

57 182 153 89 101 47

x

52 207 177 138 135 79

85

80 104 56 103 73

86

68

63

95

50 122 92

76

51

16

19

21

43

37 172 143 96

93

37

x

53

155 125 116 100 46 x

35 123 81 135 x

125 84 106 x

41

70

x

55 x

Tabulka č. 9: Vzdálenostní matice č. 1

1 1

4.4.2

Trasa č. 2

Skutečná okružní trasa Tabulka č. 11: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Podivín Hustopeče Slavkov u Brna Vyškov Bučovice Kyjov Břeclav Mikulov Brno Jihlava Znojmo Mor. Budějovice

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Hodonín Třebíč Náměšť n.O. Mor. Krumlov Pelhřimov Humpolec Havlíčkův Brod Velké Meziříčí Veverská Bítýška Tišnov Rakvice Velké Pavlovice Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 2 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 13: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Hodonín Kyjov Bučovice Vyškov Slavkov u Brna Brno Veverská Bítýška Tišnov Náměšť n O. Velké Meziříčí Havlíčkův Brod Humpolec

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Pelhřimov Jihlava Třebíč Mor. Budějovice Znojmo Mor. Krumlov Mikulov Hustopeče Velké Pavlovice Rakvice Podivín Břeclav Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1032 km. Optimální trasa navržená programem STORM je 535 km. Rozdíl činí 497 km. Vyjádřeno v procentech je nová trasa kratší o 48,16 %.

42

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

43

17 18 19 20 21 22 23 24 25

1

2

3

4

5

6

7

8

9

10

22

23

24

25

x

15

28

51

65

48

29

12

34

59 139 83 109 11 108 87

11

12

13

68 169 161 152 106 79

82

18

20

x

16

45

63

47

34

11

20

47 127 69

95

24

96

75

55 156 149 140 93

67

70

5

9

x

33

51

42

39

26

22

31 111 60

83

36

80

59

41 141 133 124 78

51

54

12

10

x

19

10

30

53

55

22 106 78

92

44

79

58

52 135 128 119 72

42

45

43

37

x

17

38

71

73

33 117 94 105 55

90

69

68 147 139 128 84

54

53

61

55

x

24

55

63

32 115 87 102 39

89

68

62 145 137 129 82

52

54

47

43

x

41

51

52 136 96 118 20 109 88

77 166 158 149 103 73

75

35

30

x

22

56 135 72

61 163 158 150 103 77

79

15

19

x

48 114 49

76

44

80

66

39 142 139 131 84

63

72

17

21

x

74

60

59

38

38 115 107 99

21

24

43

41

99

14

15

16

23 101 85

17

18

19

20

21

85

65

x

75

46 142 34

55

76

31

24

34

70

68 123 121

x

28

92

47

51

33

96 100 99

67

66

76

66

69

x

118 22

36

44

68

42

68

67

91

92

x

115 94 x

26 71

70

52

77 171 163 155 108 81

21

42

83

27

28

62

59

55

21

52

50

92

90

x

30

83

80

71

24

32

31

71

69

x

104 101 97

53

34

44

51

50

x

17

35

63 100 97 153 151

x

19

56

92

x

47

83

78 136 134

x

36

34

89

87

x

10

63

61

x

66

64

x

6

90 145 143

x

Tabulka č. 12: Vzdálenostní matice č. 2

1

4.4.3

Trasa č. 3

Skutečná okružní trasa Tabulka č. 14: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Kolín Kaňk Praha Hovorčovice Bříství Písková Lhota Jirny Chmeliště Dobřeň Poděbrady Straky Lysá n/L

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Přerov n/L Sadská Klíčany Kralupy nad Vlt. Říčany Kostelec n.Č.L. Kutná Hora Kostelec n/L Neratovice Brandýs n/L Chocerady Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 3 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 16: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Kaňk Kolín Poděbrady Písková Lhota Sadská Straky Lysá n/L Přerov n/L Bříství Jirny Brandýs n/L Kostelec n/L

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Neratovice Kralupy nad Vlt Klíčany Hovorčovice Praha Říčany Kostelec n.Č.L. Chocerady Chmeliště Dobřeň Kutná Hora Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1003 km. Optimální trasa navržená programem STORM je 672 km. Rozdíl činí 331 km. Vyjádřeno v procentech je nová trasa kratší o 33 %.

44

2 3 4 5 6 7 8 9 10 11 12 13 14 15

45

16 17 18 19 20 21 22 23 24

x

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

208 202 260 266 241 227 250 213 210 227 241 247 244 232 270 282 240 232 200 264 271 257 222 x

7

61

60

33

19

42

20

12

19

33

39

37

25

66

78

45

30

11

56

63

49

42

x

68

67

40

26

49

22

13

26

40

46

44

32

73

85

49

x

14

34

43

23

60

62

54

49

38

34

43

15

23

25

35

3

63

70

56

45

38

70

23

24

22

x

30

44

19

62

63

49

39

28

27

38

8

19

43

27

40

70

9

11

13

x

17

12

37

38

23

19

9

5

12

35

46

47

27

18

43

25

31

18

x

28

33

29

5

16

21

19

6

49

36

61

38

28

29

39

45

32

41

x

44

46

33

30

20

13

22

26

38

16

23

52

17

24

9

34

x

12

35

48

44

41

33

66

78

36

27

20

58

65

51

24

x

30

44

45

43

31

69

80

39

24

10

59

66

52

34

x

16

23

24

11

54

66

43

31

29

44

51

37

44

x

11

17

17

44

56

45

37

43

33

40

27

55

x

7

16

34

45

35

27

49

23

30

16

45

x

13

32

44

28

23

47

21

28

14

41

x

43

55

32

23

35

33

40

26

40

x

12

31

44

76

13

11

18

50

x

43

56

88

23

19

29

62

x

15

47

32

37

25

20

x

32

39

46

32

18

x

66

73

59

42

x

7

8

49

x

15

56

x

43 x

Tabulka č. 15: Vzdálenostní matice č. 3

1 1

4.4.4

Trasa č. 4

Skutečná okružní trasa Tabulka č. 17: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Hradec Králové Hrochův Týnec Chrudim Pardubice Vysoké Mýto České Meziříčí Chlumec n.C. Kladruby Hořice N. Město n.M. Náchod Jaroměř

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Vrchlabí Jičín Turnov Kopidlno Žďár nad S. Hlinsko Kutná Hora Přelouč Nový Bydžov Dvůr Král. n.L Jablonec nad J. Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 4 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 19: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Vysoké Mýto Hradec Králové České Meziříčí Náchod Jaroměř Dvůr Král. n.L Hořice Vrchlabí Jablonec nad J. Turnov Jičín Kopidlno

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25

Název obce Nový Bydžov Chlumec n.C. Kladruby Přelouč Nový Bydžov Pardubice Chrudim Hrochův Týnec Hlinsko Žďár nad S. Jablonec nad J. Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1413 km. Optimální trasa navržená programem STORM je 731 km. Rozdíl činí 682 km. Vyjádřeno v procentech je nová trasa kratší o 48,27 %.

46

2 3 4 5 6 7 8 9 10 11 12 13 14 15

47

16 17 18 19 20 21 22 23 24

x

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

197 173 177 187 159 202 216 215 222 120 213 212 256 245 267 245 127 151 200 198 223 226 270 x

33

32

24

39

20

29

28

24

88

x

9

17

20

44

43

43

57

56

65

51

93

79 102 73

50

25

51

30

51

65 105

x

11

29

49

39

38

54

59

70

50

90

74

98

68

50

27

42

23

46

64 103

x

36

42

29

28

45

69

62

42

81

65

88

59

61

37

39

17

37

55

x

47

63

62

63

56

63

54

68

86 108 88

56

32

71

50

66

68 112

x

49

48

37

98

21

13

57

60

81

67

93

68

76

51

46

27

x

1

30

97

65

44

63

38

61

30

89

66

29

19

10

49

75

x

31

96

65

43

64

40

63

31

88

65

30

18

12

50

76

x

112 45

25

36

24

46

31 104 81

59

42

20

19

49

80 104 119 161

x

38

20

61

48

70

50

82

114 105 149 132 156 126 10 x

57

57

31

28

33

73

93 75

32

83

21

59

67

87

76 113 88

93

68

58

29

78

x

44

47

67

55 100 75

72

47

37

14

61

x

34

41

46 141 117 92

78

53

30

22

x

24

14 125 101 63

57

29

39

43

x

37 148 124 86

80

52

59

37

x

50

49

22

48

56

25

74

72

97 114 153

x

58

48

73

89 129

x

25

39

78 104

x

28

58

90

x

39

65

x

49

119 95 x

x

Tabulka č. 18: Vzdálenostní matice č. 4

1 1

4.4.5

Trasa č. 5

Skutečná okružní trasa Tabulka č. 20: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Plzeň Mariánské Lázně Planá Stříbro Rokycany Tachov Beroun Rožmitál pod T. Příbram Benešov Vlašim Tábor

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Blatná Horažďovice Katovice Strakonice České Budějovice Český Krumlov Prachatice Vlachovo Březí Sušice Domažlice Klatovy Písek Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 5 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 22: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Vlašim Benešov Tábor Písek Blatná Rožmitál pod T. Příbram Beroun Rokycany Plzeň Stříbro Planá

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Mariánské Lázně Tachov Domažlice Klatovy Sušice Horažďovice Katovice Strakonice Vlachovo Březí Prachatice Český Krumlov České Budějovice Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1542 km. Optimální trasa navržená programem STORM je 1028 km. Rozdíl činí 514 km. Vyjádřeno v procentech je nová trasa kratší o 33,33 %.

48

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

49

17 18 19 20 21 22 23 24 25

x

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

325 387 379 355 308 382 284 280 274 221 202 213 275 284 272 267 220 239 262 263 299 348 317 250 x

63

54

30

17

59

x

13

37

79

22 121 107 115 172 190 175 119 121 132 138 193 207 172 161 117 68

60

x

25

71

11 114 100 107 165 182 167 110 109 121 126 182 196 16 149 104 56

78 135

x

47

30

90

75

83 140 158 143 86

85

96 102 157 171 135 125 80

40

54 110

x

75

44

28

36

56

68

68

52

x

118 102 111 168 186 170 111 110 121 127 183 196 160 150 105 53 x

45

53 110 128 113 57

94 111 96

48

59

70

76 131 145 109 99

69 122 138 104 94

68

69

53

42

82

91 144

73

78 136

53

39

65

84

94

73

91

94

94 135 153 125 116 108 111 94

87

x

15

75

90

68

26

39

48

48

95 112 83

73

57

83

56

46

x

60

75

66

34

53

56

57

98 115 88

78

70

95

70

49

x

19

45

87 108 104 99 102 125 118 114 126 155 130 79

x

42

97 117 109 103 97 121 120 117 135 170 145 83

x

66

81

69

64

58

81

78

75

x

21

22

23

74

91

57

47

39

80

49

25

x

11

17

72

86

50

40

18

64

33

37

x

6

61

30

40

30

27

76

45

26

x

56

71

35

25

32

81

50

20

x

24

43

44

88 137 106 48

x

37

46

93 150 120 66

x

10

57 114 84

40

x

47 104 74

36

x

52

96 145 113 44

57

27

x

31 101 x

71 x

Tabulka č. 21: Vzdálenostní matice č. 5

1 1

4.4.6

Trasa č. 6

Skutečná okružní trasa Tabulka č. 23: Pořadí návštěv obcí Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Litoměřice Lovosice Ústí nad Labem Teplice Bílina Litvínov Děčín Most Kladno Slaný Chomutov Stráž nad Ohří

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Sokolov Kynšperk nad O. Karlovy Vary Rakovník Roudnice n/L Štětí Mělník Želízy Česká Lípa Kravaře Rynoltice Liberec Mor. Nová Ves

Zdroj: Autor

Vzdálenostní matice č. 6 Tabulka je na následující straně.

Nová okružní trasa navržena programem STORM Tabulka č. 25: Optimální trasa Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13

Název obce Mor. Nová Ves Mělník Želízy Štětí Roudnice n/L Slaný Kladno Rakovník Karlovy Vary Kynšperk nad O. Sokolov Stráž nad Ohří Chomutov

Pořadí 14 15 16 17 18 19 20 21 22 23 24 25 26

Název obce Most Litvínov Teplice Bílina Lovosice Litoměřice Ústí nad Labem Děčín Kravaře Česká Lípa Rynoltice Liberec Mor. Nová Ves

Zdroj: Autor

Porovnání skutečné vzdálenosti s vypočítanou trasou Skutečná vzdálenost navštívených obcí je 1321 km. Optimální trasa navržená programem STORM je 1089 km. Rozdíl činí 232 km. Vyjádřeno v procentech je nová trasa kratší o 17,56 %.

50

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

51

17 18 19 20 21 22 23 24 25

x

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

316 318 334 339 339 351 336 341 284 290 348 377 398 410 379 314 300 296 280 290 306 311 310 292 x

9

18

33

33

48

33

44

52

40

64

95 130 142 113 69

18

23

37

32

38

24

65

x

22

25

24

40

41

35

50

38

55

86 122 134 105 63

21

30

40

40

46

31

73

92

x

18

29

36

23

42

70

59

60

92 130 142 114 80

36

40

54

49

45

31

70

89

x

13

18

35

26

72

60

43

74 113 125 97

70

44

54

63

64

63

48

83 102

x

17

48

14

60

49

33

65 103 115 87

57

43

54

62

63

70

55

96 115

x

53

14

71

61

25

56

67

59

69

78

79

81

66 101 120

x

61

84

73

77 109 147 159 131 101 48

46

60

55

30

29

x

61

50

22

54

92 104 76

55

51

62

70

71

81

66 108 128

x

13

69

97 118 130 99

33

36

47

42

49

81

66 106 106

x

58

88 114 126 96

33

27

37

34

41

71

57

x

31

70

82

54

53

71

81

88

91 101 86 125 145

x

39

51

23

71 101 111 117 121 132 118 157 176

x

13

18

89 133 144 148 153 167 153 194 214

x

30 101 146 156 160 166 179 165 206 226

95 107 79

x

49

85

69

97 117

71 116 127 130 136 150 136 177 197 x

59

70

67

74 104 89 130 150

x

10

19

20

44

30

71

90

x

15

10

38

26

60

80

x

9

45

38

67

86

x

35

29

57

77

x

14

27

47

x

42

61

x

20 x

Tabulka č. 24: Vzdálenostní matice č. 6

1 1

4.5 Vyhodnocení výsledků Při vyhodnocování výsledků budeme vycházet z výsledků optimalizace získaných pomocí programu STORM. Tento program se mi velmi osvědčil pro svou jednoduchost, rychlost a přehlednost. Výpočet optimální trasy bylo otázkou několika sekund. Dále bych uvedl jednoduchou editovatelnost vstupních matic. Za malé negativum bych označil na dnešní dobu zastaralé grafické rozhraní a nemožnost použít myš. Na druhou stranu je program je dobře ovladatelný pomocí funkčních a kurzorových kláves. Pokusil jsem se provést optimalizaci pomocí programu Infomapa verze 13 funkcí optimalizovat průjezd. Když jsem tuto funkci spustil a ani po dvou hodinách jsem nedostal žádný výsledek, musím tuto funkci hodnotit z časového hlediska jako nepoužitelnou pro optimalizaci okružních tras větších rozměrů (nad 20 uzlů). V následujících podkapitolách 4.5.1 – 4.5.3 provedu vyhodnocení vzdáleností mezi původními a optimálními okružními trasami. Dále zhodnotím náklady na pohonné hmoty, průměrné náklady na jednotku vzdálenosti (1 km) a průměrné náklady na jednotku času týden, měsíc, a rok.

4.5.1

Vyhodnocení vzdáleností mezi původními a optimálními trasami

Vzhledem ke skutečnosti, že firma DDPNEU nepoužívá žádný optimalizační software na své pravidelné linky, se podařilo dosáhnout dobrých optimalizačních výsledků. Absolutní rozdíly mezi stávajícími a optimalizovanými okružními cestami se pohybují v rozmezí od 232 do 682 km, což nejsou zanedbatelná čísla vzhledem k tomu, že relativní úspory se pohybují od 17,56 % do 48,27 %. Přehledné znázornění uvedu v následující tabulce.

52

Tabulka č. 26: Vyhodnocení vzdáleností

Trasa č.

Značka vozidla

1 2 3 4 5 6

VW LT 2,8Tdi FORD Tranzit 2,0 TDI Citroen Jumper 2,5 TDI Renault Master 2,8 TDI Renault Master 2,2 dci Renault Master 2,5 dci

Původní vzdálenost (km)

Celkem

Optimální vzdálenost (km)

Absolutní rozdíl (km)

Relativní rozdíl (%)

1253 1032 1003 1413 1542 1321

769 535 672 731 1028 1089

484 497 331 682 514 232

38,63 48,16 33 48,27 33,33 17,56

7564

4824

2740

36,22

Zdroj: Autor

Jak je patrné z předcházející tabulky, celková ujetá vzdálenost všech původních tras činí 7564 km a celková vzdálenost všech optimálních tras činí 4824 km. Absolutní rozdíl, tedy úspora projetých kilometrů, je 2740 km. Což relativně vyjádřeno je 36,22 %. K vyčíslení nákladů se dostaneme v průběhu dalšího hodnocení.

4.5.2

Náklady na pohonné hmoty

Cena nafty se v tomto roce pohybovala od 25,40 Kč do 26,90 Kč za litr. Z těchto údajů jsem stanovil průměrnou cenu na 26,20 Kč za 1 litr motorové nafty. V následující tabulce uvedu, jak se tato cena projevila v nákladech na pohonné hmoty. Tabulka č. 27: Náklady na pohonné hmoty Původní Optimální Trasa vzdálenost vzdálenost Značka vozidla č. (km) (km) 1 VW LT 2,8Tdi 1253 769 2 FORD Tranzit 2,0 TDI 1032 535 3 Citroen Jumper 2,5 TDI 1003 672 4 Renault Master 2,8 TDI 1413 731

Náklady na Náklady na Spotřeba původní trasu optimální trasu (l/km) (Kč) (Kč) 0,107 3512,7 2155,8 0,092 2487,5 1289,6 0,105 2759,3 1848,7 0,113 4183,3 2164,2

5

Renault Master 2,2 dci

1542

1028

0,094

3797,6

2531,8

6

Renault Master 2,5 dci

1321

1089

0,1

3461,0

2853,2

20201,4

12843,2

Celkem Zdroj: Autor

V předcházející tabulce jsem vypočítal celkové náklady za PHM na původní trasy, které

činí 20201,40 Kč a na optimální trasy 12843,20 Kč. Z těchto údajů získáme celkovou úsporu na pohonných hmotách po projetí všech tras 7358,20 Kč.

53

4.5.3

Průměrné náklady na jednotku vzdálenosti

Průměrné náklady na 1 kilometr získáme sečtením provozních nákladů na automobil a nákladů na pohonné hmoty. Provozní náklady byly vyčísleny firmou DDPNEU na 6,80 Kč na automobil a kilometr. Průměrné náklady na 1 kilometr uvedu v následující tabulce. Tabulka č. 28:Průměrní náklady na 1 kilometr Původní Optimální Trasa vzdálenost vzdálenost Značka vozidla č. (km) (km) 1 VW LT 2,8Tdi 1253 769 2 FORD Tranzit 2,0 TDI 1032 535 3 Citroen Jumper 2,5 TDI 1003 672 4 Renault Master 2,8 TDI 1413 731

Průměrné Náklady na náklady původní trasu (Kč/km) (Kč) 9,6 12033,1 9,2 9505,1 9,6 9579,7 9,8 13791,7

Náklady na optimální trasu (Kč) 7385,0 4927,6 6418,3 7135,0

5

Renault Master 2,2 dci

1542

1028

9,3

14283,2

9522,2

6

Renault Master 2,5 dci

1321

1089

9,4

12443,8

10258,4

71636,6

45646,4

Celkem Zdroj: Autor

Pomocí průměrných nákladů na 1 kilometr jsem získal průměrné náklady na původní trasy, což činí 71636,60 Kč a náklady na nové optimální trasy 45646,40 Kč. Celková úspora po projetí všech tras je 25990,20 Kč. Tato částka není zanedbatelná, uvážíme-li, že o tuto částku by si firma mohla snížit náklady každý týden. Za měsíc by to bylo již 103960,80 Kč a za rok stanovíme-li si 45 pracovních týdnů ročně, pak dokonce 1169559 Kč.

54

5 Diskuse a závěr Tématem diplomové práce byla optimalizace distribučních cest. Optimalizaci jsem se pokusil provézt pomocí tří metod. Littlova metoda se pro tento případ nehodila z hlediska časové náročnosti a možnosti udělat chybu v tak dlouhém a složitém výpočtu, jelikož jsme řešili vzdálenostní matice o více než dvacet uzlech. Tuto metodu jsem použil na ilustrativním příkladě, kde jsem použil pouze část trasy. Výsledek nebyl moc uspokojivý, jelikož nedošlo k nalezení optimálního řešení. Littlova metoda je metodou aproximativní – to znamená, že nám nalezne řešení blízké optimálnímu. Využitelnost se nám nabízí u matic menších rozměrů, když nemáme možnost využít softwarové vybavení. Funkce optimalizovat průjezd v softwaru Infomapa se jevila jako nejrychlejší, protože bylo nutné znát pouze názvy jednotlivých uzlů a nemuseli jsme znát jednotlivé vzdálenosti mezi těmito uzly. Program si sám tyto vzdálenosti najde. Bohužel se mi nepodařilo ani u jedné trasy dosáhnout nějakého výsledku. Tento program mi posloužil ke zjišťování vzdáleností, které jsem potřeboval pro optimalizaci v programu STORM. V softwaru STORM se mi podařilo zoptimalizovat trasy, které mi byly zadány firmou DDPNEU. Je škoda, že jsem tyto výsledky nemohl porovnat s programem Infomapa a zjistit tak, který software je pro tuto problematiku výhodnější z hlediska minimalizace ujetých kilometrů. Práce s programem, jeho výhody a nevýhody jsou popsány na začátku kapitoly 4.5. Z hlediska časového bylo nejnáročnější získat vzdálenosti mezi jednotlivými uzly a import těchto vzdáleností do programu. Samotný výpočet je otázkou několika sekund. Pokud máme již vzdálenostní matice vytvořeny a vypadne nebo přibude nám nějaký uzel (zákazník), je snadné a časově nenáročné stávající matice zeditovat. Je to otázka minut. Jestliže hodnotíme výsledky z hlediska ekonomického, ať už máme na mysli náklady na pohonné hmoty, průměrné náklady na jednotku vzdálenosti (1 km), celkové náklady na dopravu či průměrné náklady na jednotku času (týden, měsíc, rok), musíme konstatovat, že v tomto případě došlo ke značným úsporám kolem 36 procent. Což při

55

ujetí vzdálenosti 7500 km za týden a celkových nákladech kolem 71500 Kč nám dává úsporu 2700 najetých kilometrů a částku 26000 Kč. Použitím optimalizace získáme nejen úsporu v najetých kilometrech a ve snížení nákladů na dopravu, ale získáme i čas, který můžeme využít např. k získávání nových zákazníku, či zlepšení vztahů se stávajícími tím, že budeme mít více času se jim věnovat. Jelikož firma DDPNEU nepoužívá žádnou optimalizační metodu pro své dopravní trasy, čemuž odpovídají i získané výsledky, měla by v tomto směru učinit kroky, které by vedly k nápravě. Optimalizace neobsahuje všechny zákazníky v dané obci a nezohledňuje další skutečnosti, jako je otvírací doba, urgentní zásilky, nesjízdnost některých tras v různých ročních obdobích, objížďky, jednosměrné ulice a další, ale i tak jsou úspory značné. U jednotlivých tras nalezneme nevyrovnané vzdálenosti, proto by zde byla možná optimalizace tím, že bychom převedli některé zákazníky na jiné prodejce. Zákazníci jsou zvyklí na danou osobu obchodního zástupce a jeho jednání a tímto převodem by mohlo dojít ke snížení tržeb nebo i ke ztrátě zákazníka. Výsledný efekt by nemusel být pozitivní. Další optimalizace ujetých vzdáleností by byla možná změnou sídla firmy. Firma se nachází téměř na jihovýchodním okraji republiky, proto by bylo lepší posunout tuto polohu více do vnitrozemí. Jelikož chce společnost v horizontu několika málo let změnit své sídlo z důvodu nedostatečné skladové kapacity, stála by tato možnost za zvážení. V současné době plné změn a rychle se měnícímu tržnímu prostředí nelze navrhnout optimální trasy, podle kterých by se dalo do detailu postupovat. Měly by se navrhovat takové trasy, z nichž by se dalo vycházet při sestavování okružních cest a také je potřeba zohledňovat aktuální podmínky a požadavky zákazníků, tak aby nám přinesly celkově co nejlepší efekt.

56

6 Použitá literatura a prameny [1]

KORTSCHAK, B. Úvod do logistiky. 2. české vydání 1997. Praha BABTEXT s.r.o., 176 s. ISBN 80-85816-06-7.

[2]

DRAHOTSKÝ, I. – ŘEZNÍČEK, B. Logistika – procesy a jejich řízení. 1. vydání 2003. Brno Computer Press, 334 s. ISBN 80-7226-521-0.

[3]

PERNICA, P. Logistický management. 1. vydání 1998. Praha RADIX, spol. s r.o., 664 s. ISBN 80-86031-13-6.

[4]

RAŠOVSKÝ, M. – ŠIŠLÁKOVÁ, H. Ekonomicko - matematické metody. dotisk 2003. Brno MZLU, 195 s. ISBN 80-7157-412-0.

[5]

KORDA, B. A KOL. Matematické metody v ekonomii. 1. vydání 1967. Praha SNTL, 604 s. ISBN 04-307-67.

[6]

PELIKÁN, J. Praktikum z operačního výzkumu. 1. vydání 1993. Praha VŠE, 86 s. ISBN 80-7079- 135-7.

[7]

KŘIVKOVÁ, M. Operační analýza a modelování. dotisk 1997. Brno MZLU, 153 s. ISBN 80-7157-124-5.

[8]

KORDA, B. – BUKOVSKÝ, K. – EICHLER, B. Lineární programování. 1. vydání 1967. Praha Státní pedagogické nakladatelství, 135 s. ISBN 16-057-68.

[9]

JABLONSKÝ, J. Operační výzkum. 2. vydání 1998. Praha VŠE. ISBN 80-7079597-2.

[10] ZÍSKAL, J. – BROŽOVÁ, H. Ekonomicko matematické metody II. 1. vydání 1998. Praha VŠZ. ISBN 80-7175-315-7.

[11] http://www.ddpneu.cz

57

7 Přílohy SEZNAM PŘÍLOH Příloha č. 1: Vstupní tabulka trasy č. 1 Příloha č. 2: Vstupní tabulka trasy č. 2 Příloha č. 3: Vstupní tabulka trasy č. 3 Příloha č. 4: Vstupní tabulka trasy č. 4 Příloha č. 5: Vstupní tabulka trasy č. 5 Příloha č. 6: Vstupní tabulka trasy č. 6 Příloha č. 7: Výstupní hodnoty trasy č. 1 Příloha č. 8: Výstupní hodnoty trasy č. 2 Příloha č. 9: Výstupní hodnoty trasy č. 3 Příloha č. 10: Výstupní hodnoty trasy č. 4 Příloha č. 11: Výstupní hodnoty trasy č. 5 Příloha č. 12: Výstupní hodnoty trasy č. 6

SEZNAM OBRÁZKŮ A TABULEK Obrázek č. 1: Graf okružní jízdy Tabulka č. 1: Vstupní údaje Tabulka č. 2: Redukce výchozí matice Tabulka č. 3: Redukce předchozí matice o 4. řádek a 6. sloupec Tabulka č. 4: Redukce předchozí matice o 6. řádek a 5. sloupec Tabulka č. 5: Redukce předchozí matice o 5. řádek a 3. sloupec Tabulka č. 6: Redukce předchozí matice o 3. řádek a 2. sloupec Tabulka č. 7: Přehled vozidel Tabulka č. 8: Pořadí návštěv obcí Tabulka č. 9: Vzdálenostní matice č. 1 Tabulka č. 10: Optimální trasa Tabulka č. 11: Pořadí návštěv obcí Tabulka č. 12: Vzdálenostní matice č. 2 Tabulka č. 13: Optimální trasa

58

Tabulka č. 14: Pořadí návštěv obcí Tabulka č. 15: Vzdálenostní matice č. 3 Tabulka č. 16: Optimální trasa Tabulka č. 17: Pořadí návštěv obcí Tabulka č. 18: Vzdálenostní matice č. 4 Tabulka č. 19: Optimální trasa Tabulka č. 20: Pořadí návštěv obcí Tabulka č. 21: Vzdálenostní matice č. 5 Tabulka č. 22: Optimální trasa Tabulka č. 23: Pořadí návštěv obcí Tabulka č. 24: Vzdálenostní matice č. 6 Tabulka č. 25: Optimální trasa Tabulka č. 26: Vyhodnocení vzdáleností Tabulka č. 27: Náklady na pohonné hmoty Tabulka č. 28: Průměrní náklady na 1 kilometr

59