ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ

Stanislav Pochop

Dopravní obsluha sběrných míst vybraného území

Bakalářská práce

2015

Poděkování Na tomto místě bych rád poděkoval všem, kteří mi pomohli při přípravě této bakalářské práce. Zvláště pak děkuji doc. Ing. Denise Mockové, Ph.D. za odborné vedení, konzultace a poskytnutí cenných rad. V neposlední řadě bych rád poděkoval rodině a všem svým blízkým, kteří mi poskytli podporu a byli mi ochotni kdykoliv pomoci po celou dobu mého dosavadního studia.

2

Prohlášení Prohlašuji, že jsem předloženou práci vypracoval samostatně a že jsem uvedl veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací. Nemám závažný důvod proti užívání tohoto školního díla ve smyslu § 60 Zákona č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

3

Abstrakt Cílem této práce byla optimalizace a návrh vhodných tras svozu mléka pro mlékárenský závod TPK Pribina v Hesově. Nejdříve byla firma TPK Pribina krátce představena a byl uveden současný stav svozu mléka. Následně byly vybrány vhodné metody z oblasti teorie grafů pro optimalizaci a návrh tras. Poté došlo k aplikaci vybraných metod na stávající situaci a bylo vytvořeno několik variant řešení. V poslední části byla vybrána finální varianta návrhu tras a došlo k porovnání se současným stavem.

Klíčová slova teorie grafů, optimalizace tras, problém obchodního cestujícího, okružní problém, Žravý algoritmus, algoritmus Clarka a Wrighta

4

Abstract The optimalisation and the proposal of suitable routes for milk collection in the company TPK Pribina in Hesov was the main aim of this thesis. At the earliest the company TPK Pribina was shortly introduced, then the currect state of milk collection was described. Right methods from graph theory for optimalisation and route proposal were chosen afterwards. Selected methods were applied on current situation subsequently and some options of solution were created. The final solution for route proposal was chosen in the last part, it was also compared with current situation.

Key words Graph theory, Route optimalisation, Travelling Salesman Problem, Circular problem, Greedy Search, Clark-Wright algorithm

5

Obsah

Obsah ..................................................................................................................................................... 6 1

Úvod ............................................................................................................................................... 8

2

Charakteristika firmy TPK Pribina ............................................................................................ 10

3

4

5

2.1

Vývoj společnosti ................................................................................................................ 10

2.2

Vývoj produktů .................................................................................................................... 11

Současný stav ............................................................................................................................. 12 3.1

Okolí podniku ...................................................................................................................... 12

3.2

Svoz mléka .......................................................................................................................... 12

3.3

Podmínky pro řidiče............................................................................................................ 13

3.4

Současné trasy malého vozidla ........................................................................................ 13

3.5

Současné trasy vozidla s vlekem ..................................................................................... 15

Výběr vhodné metody řešení .................................................................................................... 18 4.1

Problém obchodního cestujícího ...................................................................................... 18

4.2

Okružní jízdy ....................................................................................................................... 18

4.3

Heuristický algoritmus ........................................................................................................ 19

4.4

Clark – Wrightova metoda ................................................................................................. 19

Optimalizace stávajících tras .................................................................................................... 21 5.1

Optimalizace jednotlivých tras .......................................................................................... 21

5.1.1

Malé vozidlo: Trasa I. ................................................................................................. 21

5.1.2

Malé vozidlo: Trasa II. ................................................................................................ 23

5.1.3

Malé vozidlo: Trasa III. ............................................................................................... 25

5.1.4

Vozidlo s vlekem: Trasa III. ....................................................................................... 27

5.2

Optimalizace sloučených tras pro každé vozidlo ........................................................... 29

5.2.1

Vrcholy tras malého vozidla ...................................................................................... 29

5.2.2

Vrcholy tras vozidla s vlekem ................................................................................... 34

5.3

Optimalizace tras pro všechny vrcholy obou vozidel .................................................... 37 6

Srovnání současného stavu a vybraných řešení ................................................................... 43

6

6.1

Vybraná řešení .................................................................................................................... 43

6.2

Finální návrh tras ................................................................................................................ 44

7

Závěr............................................................................................................................................. 46

8

Literatura ...................................................................................................................................... 48

9

Seznam obrázků ......................................................................................................................... 49

10

Seznam tabulek ...................................................................................................................... 50

7

1 Úvod

Každá společnost, která se zabývá výrobou určitých produktů, musí mít zajištěno zásobování surovinami a materiálem a zároveň se musí postarat o rozvoz svých výrobků. Pokud si alespoň jednu z těchto činností organizuje firma sama, musí dbát na její co nejlepší provedení. Odvětví dopravní obsluhy je totiž oblastí, kde se pohybuje velké množství financí, a například zajištění zásobování může hrát v celkových nákladech firmy nemalou roli. Proto je pro výrobní podnik důležité, aby v této oblasti, kterou potřebuje ke svému fungování a není jeho hlavním zájmem, zbytečně nepřicházel o finance. Tato práce se zaměřuje na firmu TPK Pribina a na její trasy svozu mléka. Pribina je mlékárenský závod, který vyrábí nejrůznější mléčné produkty. Každý den proto potřebuje dostatek mléka, které je do závodu sváženo z kravínů v okolí. Jedná se tedy o obsluhu vrcholů, kravínů, která začíná a končí v závodě Pribina. Cílem práce je navrhnout takové trasy svozu mléka, při kterých budou obslouženy všechny vrcholy a zároveň bude ujeta co nejmenší vzdálenost. V této bakalářské práci jsou použity dvě metody z oblasti teorie grafů, které se zabývají obsluhou vrcholů a optimalizací tras. Tyto metody jsou použity na řešení dvou úloh. První úlohou je problém obchodního cestujícího. Rozšířením této úlohy o různé omezující podmínky získáme úlohu druhou, nazvanou problém vícenásobného obchodního cestujícího nebo také okružní problém. Na problém obchodního cestujícího bude použit Heuristický algoritmus, nazývaný také Hladový nebo Žravý. Tímto algoritmem budou určeny minimální Hamiltonovské kružnice, které budou představovat navrhované trasy. Na okružní problém bude použita metoda Clarka a Wrighta. Pomocí této metody zjistíme přesné trasy a kolik jízd, neboli obchodních cestujících, bude třeba na obsloužení vrcholů. V první části práce je krátce představena společnost TPK Pribina. Je zde uvedena charakteristika firmy, její vývoj a současná nabídka produktů, které svým zákazníkům nabízí. Ve druhé části je znázorněna současná situace podniku z hlediska svozu mléka. Je zde popsáno okolí podniku a celý proces, jak svoz mléka probíhá. Uvedeny jsou také podmínky pro řidiče, kterými se musí řídit. Především jsou zde pak podrobně znázorněny současné trasy obou vozidel, které společnost ke svážení mléka z kravínů využívá. Další kapitola se zaměřuje na výběr vhodných metod pro řešení dopravní obsluhy vrcholů sítě. Jsou zde uvedeny dva typy úloh, které se obsluhou vrcholů zabývají a objevují se v práci. Ke každé úloze je vybrána jedna metoda vhodná k jejímu řešení. Obě tyto metody jsou zde popsány a u každé z nich je uveden přesný postup vhodný k jejímu řešení.

8

V následující části práce dochází již k samotné aplikaci vybraných metod a tedy k optimalizaci stávajících tras a vytváření tras nových. Nejprve dochází k optimalizaci jednotlivých tras zvlášť. Poté se přejde k optimalizaci sloučených tras u jednotlivých vozidel. Další variantou návrhu je optimalizace tras pro všechny vrcholy obou vozidel dohromady. V páté kapitole je uvedeno srovnání současného stavu svozu mléka a nových řešení. Vybraná řešení jsou zde představena i se svými klady a zápory. Nakonec je vybráno nejvhodnější z nich a tím je určen finální návrh obsluhy tras. Tento návrh je výsledně se současným stavem porovnán v tabulce, ve které je jasně vidět, jaké výhody a úspory může firmě přinést.

9

2 Charakteristika firmy TPK Pribina

Pribina je mlékárenský výrobní podnik, který se nachází v obci Hesov u města Přibyslav na Vysočině. Jeho výrobky jsou známé po celé České Republice, jedná se například o tavené sýry, plísňové sýry Hermelín a především pak o tvarohovo-smetanový krém Pribináček. Na obrázku 1 je uvedeno logo společnosti.

zdroj: [6]

Obrázek 1: Logo TPK Pribina

2.1 Vývoj společnosti Mlékárenská výroba vznikla v Přibyslavi v roce 1923 pod názvem Mlékárenské a pastevní družstvo. Z důvodů rozrůstání muselo dojít k rozsáhlým rekonstrukcím a v roce 1941 byl spuštěn provoz nového moderního závodu spolu s konzervárnou ovoce. Nový název Pribina, zemědělské výrobní družstvo Českomoravské vysočiny vznikl roku 1948. Zanedlouho, roku 1952, však bylo družstvo znárodněno jako Pribina Přibyslav a od roku 1958 patřilo k závodům národního podniku Posázavské mlékárny, později od roku 1960 k závodům Východočeské mlékárny Pardubice. Po roce 1976 společnost patřila Průmyslu mléčné výživy v Hradci Králové. Pribina se stala nezávislou až v roce 1990 a od roku 1993 patří francouzské mlékárenské společnosti Bongrain. Tato společnost se může chlubit tím, že patří mezi deset největších mlékárenských společností světa, vlastní například také mlékárenský podnik v Hodoníně. V roce 2010 došlo ke spojení těchto dvou závodů pod názvem TKP, spol. s.r.o. Díky novému majiteli došlo k rozsáhlé rekonstrukci a obnově podniku. Byly nakoupeny nové stroje a bylo zmodernizováno téměř veškeré vybavení mlékárny. Firma Bongrain s sebou přinesla také nové technologické postupy a vylepšení výroby. Díky tomu se dnes Pribina může řadit k největším producentům sýrů a smetanových výrobků v republice. Během jednoho roku se v podniku zpracuje kolem 110 milionů litrů mléka. Pro Přibyslav a okolí se stala společnost TKP Pribina také velmi významným

10

zaměstnavatelem, když zde má v současné době práci kolem čtyř set lidí. Mlékárenský závod Pribina můžeme vidět na obrázku 2.

zdroj: [6]

Obrázek 2: Mlékárenský výrobní podnik Pribina

2.2 Vývoj produktů Z počátku se Pribina věnovala pouze výrobě sýrů. Od roku 1947 začala vyrábět také mléčné dezerty pro děti. O rok později se nabízené výrobky rozrostly o konzervované ovoce, ovocná vína, kompoty, džemy do jogurtů a mošty. Vznikla ovocná šťáva Pribinka a sortiment se rozšířil také o plísňové síry Hermelín. V roce 1954 přichází Pribina s výrobkem, který jí zajistil asi největší slávu. Jedná se o tvarohovo - smetanový krém Pribináček, který u nás zná každý a ke kterému se váže známý slogan „Pramen zdraví z Posázaví“. Složení Pribináčku se od té doby nezměnilo, jedná se o stále stejnou originální recepturu. O něco později byl po částech ukončen provoz konzervárny ovoce a Pribina se nejvíce zaměřila na výrobky, jako jsou tavené sýry, Pribináček a Hermelín. V současné době se podnik věnuje hlavně výrobě plísňových sýrů značky Král Sýrů, smetanového krému Pibináček a také různým předsmaženým produktům. Produkty Pribina 

Tavené sýry - Pribina



Předsmažené produkty



Plísňové sýry – Král Sýrů



Dětské dezerty – Pribináček

11

3 Současný stav

V této části práce je popsáno okolí, ve kterém se mlékárna nachází, a je zde také představena současná situace podniku z hlediska svozu mléka.

3.1 Okolí podniku Mlékárna Pribina se nachází v obci Hesov u malého města Přibyslav. Okresním městem je Havlíčkův Brod a krajským Jihlava, nacházíme se tedy v Kraji Vysočina. Silniční síť je v okolí Pribiny poměrně hustá a tvoří ji především silnice I. a II. třídy a ostatní komunikace. Na obrázku 3 je znázorněna poloha mlékárny Pribina v České Republice.

zdroj: [7]

Obrázek 3: Poloha mlékárny Pribina v ČR

3.2 Svoz mléka Pribina získává mléko z kravínů ve svém okolí, téměř všechny tedy leží v okrese Havlíčkův Brod a Žďár nad Sázavou. Ke svozu mléka jsou využívány dva nákladní vozy s cisternami. Jeden vůz pojme objem 15 000 litrů, druhý vůz má navíc ještě vlek o objemu 14 000 litrů, jeho kapacita je celkem 29 000 litrů. V místě zastávky nabírá vůz vždy určitý objem mléka, který je každý den přibližně stejný. Díky těmto vozům se do mlékárny dostane denně přibližně 131 000 litrů mléka. Oba vozy mají určených několik tras, které jezdí každý den. Menší vůz jede denně tři trasy, které vedou okresem Havlíčkův Brod. Vůz s vlekem jezdí každý den trasy čtyři a spíše se pohybuje v okrese Žďár nad Sázavou. Oba vozy vyjíždějí 12

z Hesova už v jednu hodinu ráno. Podnik zaměstnává čtyři řidiče, dva na každé auto. Ti se střídají podle určitého plánu, aby jejich pracovní doba vyhovovala podmínkám pro řízení tohoto typu vozu.

3.3 Podmínky pro řidiče Přeprava vozidly na svoz mléka patří mezi částečné výjimky přepravy. Tyto výjimky přepravy jsou uvedeny v čl. 13 odst. 1 nařízení (ES) č. 561/2006. Řidiči se proto neřídí podle nařízení dohody AETR,což je Evropská dohoda o práci osádek vozidel v mezinárodní silniční dopravě. V této dohodě se totiž částečné výjimky nevyskytují. Státy EU se mohou rozhodnout, zda se budou tyto přepravy řídit dle nařízení (ES) č. 561/2006, nebo zda pro tyto přepravy určí nějaký jiný režim. Česká Republika zvolila možnost stanovit vlastní podmínky pro tyto přepravy a ty se nyní řídí režimem dle § 3 vyhlášky č. 478/2000 Sb. To znamená, že maximální pracovní doba řidičů vozidel na svoz mléka je 15 hodin denně. Poté musí následovat doba odpočinku minimálně 9 hodin. Denní doba řízení je 9 hodin. Během řízení musí mít řidič bezpečnostní přestávku nejdéle po 4,5 hodinách a to alespoň 45 minut. Přestávku je možné rozdělit na 2 části. První část bezpečnostní přestávky musí mít alespoň 15 minut a po ní musí být přestávka v délce nejméně 30 minut. Pokud chce řidič přestávku rozdělit, musí tak učinit během 4,5 hodin řízení. Obě vozidla jsou vybavena tachografem.

3.4 Současné trasy malého vozidla Malé vozidlo, tedy vozidlo o objemu 15 000 litrů, se vydává pravidelně každý den na tři trasy s celkovým počtem 19 zastávek a do Pribiny přiveze postupně kolem 40 000 litrů mléka. Celkem za jeden den urazí vzdálenost 240 km. Jednotlivé trasy vozidla jsou znázorněny v tabulce 1. Jsou zde uvedeny i objemy nabíraného mléka, přibližné časy příjezdů do jednotlivých zastávek a ujetá vzdálenost. Poté jsou trasy i zobrazeny na obrázku 4. Malé vozidlo je znázorněno na obrázku 6.

13

Tabulka 1: Trasy malého vozidla

Trasa I. 0 1 2 3 4 0

Trasa II. 0 1 2 3 4 5 6 7 8 0

Trasa III. 0 1 2 3 4 5 6 7 0

Zastávka Hesov Veselice Humpolec Radňov Úhořilka Hesov

objem [l]

objem celkem [l] vzdálenost [km]

12790 78

Zastávka Hesov Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Hesov

objem [l]


13380 90

Zastávka Hesov Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná Hesov

objem [l]


13720 72

1980 5680 4160 970

1300 120 1340 640 1840 6730 130 1280

350 8720 2540 230 90 800 990

čas 1:00 1:30 2:00 2:50 3:30 4:00

čas 5:00 5:40 6:10 6:25 7:15 7:25 7:45 8:30 8:45 9:00

čas 9:45 9:50 10:30 11:25 12:00 12:15 12:30 12:45 13:30

zdroj: [autor]

14

zdroj: [5, autor]

Obrázek 4: Trasy malého vozidla

3.5 Současné trasy vozidla s vlekem Vozidlo s vlekem, které pojme celkem 29 000 litrů mléka, se vydává pravidelně každý den na čtyři trasy s celkovým počtem 9 zastávek a do Pribiny sveze okolo 92 000 litrů mléka. Během jednoho dne najede 252 km. Trasy vozidla s vlekem jsou znázorněny v tabulce 2. Také jsou zde uvedeny přibližné časy příjezdů do jednotlivých kravínů, objemy nabíraného mléka a ujetá vzdálenost. Na obrázku 5 jsou znázorněny trasy tohoto vozidla.

15

Tabulka 2: Trasy vozidla s vlekem

Trasa I. Zastávka objem [l] 0 Hesov 1 Pavlov 4500 2 Radostín n.Oslavou 23140 0 Hesov

Trasa II. 0 1 0

Trasa III. 0 1 2 3 4 0


27640 68

Zastávka Hesov Pavlov Hesov

objem [l]


17520 64

Zastávka Hesov Hluboká Krucemburk Střížov Pohled Hesov

objem [l]


26080 56

17520

420 17430 2500 5730

Trasa IV. Zastávka objem [l] 0 Hesov 1 Nová Ves u N.M.n.M. 6630 2 Slavkovice 13920 0 Hesov objem celkem [l] vzdálenost [km]

čas 1:00 1:40 2:00 3:45

čas 5:30 6:15 8:00

čas 8:45 9:10 9:25 10:25 10:50 11:25

čas 12:15 12:55 13:25 14:45

20550 64 zdroj: [autor]

16

zdroj: [5, autor]

Obrázek 5: Trasy vozidla s vlekem

zdroj: [autor]

Obrázek 6: Malé vozidlo

17

4 Výběr vhodné metody řešení

Základní pojmy a terminologie řešené problematiky vychází z [1] a [2]. Práce se zabývá dopravní obsluhou vrcholů sítě. Jednotlivé vrcholy představují kravíny, ze kterých mlékárenská auta sváží mléko do závodu Pribina. Cílem je tedy navrhnout takové trasy, na kterých vozidlo nabere mléko ve všech kravínech, doveze ho do mlékárny a najede při tom co nejméně kilometrů. Jedná se tedy o problém obchodního cestujícího. Tuto úlohu můžeme ještě dále rozšířit o úlohu optimálního trasování, tedy okružní problém. Při obsluze vrcholů sítě budeme navíc uvažovat různé omezující podmínky jako například čas, ujetá vzdálenost či kapacita vozidla.

4.1 Problém obchodního cestujícího Z hlediska teorie grafů hledáme minimální hamiltonovskou kružnici HK, která obsahuje všechny vrcholy a součet ohodnocení hran je minimální [1]. Úlohou je nalézt nejkratší trasu, začínající a končící v tomtéž místě, která zahrnuje všechna místa na seznamu. Podmínkou je, že každé místo můžeme navštívit pouze jednou. Existuje více metod na řešení úlohy obchodního cestujícího. Metody lze rozdělit do dvou skupin na metody exaktní a metody heuristické [2].

4.2 Okružní jízdy Jedná se tedy o úlohu optimálního trasování, nazývanou také okružní problém, či problém vícenásobného obchodního cestujícího. O okružní jízdě hovoříme tehdy, je-li kapacita obslužného vozidla dostatečná na postupnou obsluhu více než jednoho požadavku. Hledáme nejmenší počet tras v ohodnocené síti a při řešení předpokládáme využití více vozidel – obchodních cestujících. Možným řešením je heuristická metoda založená na primárních heuristikách, kde dvě možné trasy jsou spojeny do jedné sdružené trasy. Jedná se o algoritmus, který vyvinuli Clarke a Wright. V práci bude využito dvou různých heuristických metod řešení a to na problém obchodního cestujícího a na úlohu okružních jízd. Na stávající stav tedy bude nasazen jak heuristický algoritmus pro nalezení minimální hamiltonovské kružnice, tak i Clark – Wrightova metoda.

18

4.3 Heuristický algoritmus Tato metoda, nazývaná někdy také Hladový nebo Žravý algoritmus, slouží k určení minimální HK v kompletním, hranově ohodnoceném grafu. Heuristika nezaručuje (ale nevylučuje), že nalezená kružnice bude skutečně minimální [2]. Jednotlivé kroky tohoto algoritmu jsou následující: 1. krok: Začneme ve zvoleném vrcholu a vybereme takovou s ním incidující hranu, jejíž ohodnocení bude minimální. Pokud bude hran s nejnižším ohodnocením více, vybereme libovolnou z nich. 2. krok: Ve vrcholu vi є V, ve kterém se aktuálně nacházíme, vybereme a dále zařadíme do HK takovou s ním incidující hranu, jejíž ohodnocení je minimální a jejíž koncový vrchol není do HK ještě vybrán. 3. krok: Postup opakujeme, dokud je možné vybrat aspoň jednu další hranu požadované vlastnosti. Pokud ne, vybereme ještě hranu spojující naposledy vybraný vrchol s vrcholem počátečním [1].

4.4 Clark – Wrightova metoda Vstupním prvkem do tohoto algoritmu je matice minimálních vzdáleností mezi jednotlivými vrcholy, resp. distanční matice. Prvním krokem je tedy zjistit vzdálenosti pro každou dvojici vrcholů, které obsluhujeme. Za vrcholy jsou brány jednotlivé obce a vytvořené distanční matice jsou symetrické. To znamená, že vzdálenosti mezi každými dvěma vrcholy jsou stejné v obou směrech. U distančních matic bude tedy vyplněna vždy jen jedna část, protože druhá část je stejná. Požadovaným cílem je urazit co nejméně kilometrů, neboť jde o optimalizaci kritéria vzdálenosti. Pro zjištění vzdálenosti mezi každými dvěma vrcholy byla použita aplikace Mapy.cz, kde byla vždy vybrána nejkratší nalezená vzdálenost. Za omezující vstupní podmínku byla zvolena kapacita vozů. Jednotlivé iterace a sdružené elementární trasy jsou v každé variantě řešení zobrazeny. Algoritmus řešení popíšeme pomocí následující posloupnosti 6 kroků: 1. Vypočteme matici výhodnostních koeficientů (matici úspor) podle Zij = di0 + d0j - dij pro všechna i, j = 1,2…, n. 2. Inicializačním řešením algoritmu je triviální řešení, které obsahuje celkem n triviálních cyklů: {(v0, v1, v0), (v0, v2, v0),…, (v0, vi, v0), (v0, vj, v0),…,(v0, vn, v0)}. Položíme γi = 1, i = 1,2,…,n. 3. V tabulce úspor zjistíme, existuje-li ještě nějaké Zij > 0, které nebylo dosud vybráno. Mohou nastat dvě možnosti: 19

a. Zij > 0 ještě existuje, pokračujeme krokem 4, b. Žádné Zij > 0 již neexistuje, pokračujeme krokem 6. 4. Určíme max{Zij} > 0, které nebylo dosud vybráno. Pro další postup je rozhodující splnění, resp. nesplnění omezující podmínky. a. Omezující podmínky jsou splněny, označíme příslušné Zij > 0 jako použitelné, pokračujeme krokem 5, b. Alespoň jedna podmínka není splněna, označíme příslušné Zij > 0 jako nepoužitelné, pokračujeme krokem 4. 5. Sjednotíme cykly obsahující vi a vj do jednoho cyklu, určíme znova příslušná γi pro i = 1,2,…,n, pokračujeme krokem 3. 6. Obdržené řešení je (sub)optimálním řešením okružních jízd na síti [2].

20

5 Optimalizace stávajících tras

Optimalizace současných tras bude mít několik variant. Nejdříve bude řešení zaměřeno na jednotlivé trasy každého vozidla a poté dojde k optimalizaci sloučených tras pro každé vozidlo, a to jak podle Hladového algoritmu, tak i podle metody Clarka a Wrighta. Na závěr bude uvedena optimalizace všech vrcholů obou vozidel dohromady podle Clark – Wrightovy metody.

5.1 Optimalizace jednotlivých tras V této části bude použit Žravý algoritmus a Clark – Wrightova metoda na vrcholy každé jednotlivé trasy stávajícího řešení zvlášť. Nejdříve budou řešeny trasy malého vozidla, poté trasy vozidla s vlekem. Není zde nutné prověřovat, zda vozidlo vyhovuje kapacitně, neboť na stejné trasy je nasazeno stejné vozidlo. 5.1.1

Malé vozidlo: Trasa I.

Clark – Wrightova metoda Tabulka 3: Distanční matice (malé vozidlo, trasa I.)

Hesov Veselice Humpolec Radňov Úhořilka

He v0

Ve v1

Hu v2

Ra v3

Úh v4

0

15,4 0

30,2 18,1 0

20,5 8,4 12,6 0

19,7 11,2 16,4 7,8 0

v0 v1 v2 v3 v4

zdroj: [autor]

Tabulka 4: Matice úspor (malé vozidlo, trasa I.)

v1 v2 v3 v4

v1

v2

v3

v4

0

27,5 0

27,5 38,1 0

23,9 33,5 32,4 0 zdroj: [autor]

21

Tabulka 5: Jednotlivé iterace algoritmu (malé vozidlo, trasa I.)

Z 23

1. iterace sdružená trasa 2. iterace sdružená trasa 3. iterace sdružená trasa

0-2-3-0 Z 24 0-4-2-3-0 Z 13 0-1-3-2-4-0

délka [km] 63,3 délka [km] 69,2 délka [km] 72,5 zdroj: [autor]

Oproti původnímu řešení došlo ke změně, vrcholy by měly být navštíveny v jiném pořadí. Konkrétně v pořadí: Veselice – Radňov – Humpolec – Úhořilka. Nejkratší možná trasa takto vychází místo původních 78 km na 72,5 km. Hladový algoritmus Podle této metody jsme nalezli například dvě různá řešení. První trasa je prvním pokusem o nalezení nejkratší HK, druhá trasa pak odpovídá stejnému řešení jako podle předešlé metody. Graf a nalezené trasy jsou znázorněné na obrázku 7. Tabulka 6: HK pro trasu I. malého vozidla

HK 1. trasa 2. trasa

elementární trasy délka [km] 0-1-3-4-2-0 78,2 0-1-3-2-4-0 72,5 zdroj: [autor]

22

zdroj: [autor]

Obrázek 7: Graf a dvě HK pro trasu I. malého vozidla 5.1.2

Malé vozidlo: Trasa II.

Clark – Wrightova metoda Tabulka 7: Distanční matice (malé vozidlo, trasa II.)

Hesov Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek

v0 v1 v2 v3 v4 v5 v6 v7 v8

He v0

Zb v1

Sá v2

Ba v3

MV v4

Št v5

Sm v6

Kn v7

Dv v8

0

29,6 0

33,4 3,8 0

31,7 2,1 4,2 0

12,8 22,3 26,2 24,5 0

16,9 29,4 33,2 31,5 7,5 0

11,9 30,1 33,9 32,2 8,4 5 0

8 29,9 33,7 32 10,4 9,8 4,8 0

3,1 31,2 35 33,3 14,3 13,9 8,9 4,9 0

zdroj: [autor]

23

Tabulka 8: Matice úspor (malé vozidlo, trasa II.)

v1 v2 v3 v4 v5 v6 v7 v8

v1

v2

v3

v4

v5

v6

v7

v8

0

59,2 0

59,2 60,9 0

20,1 20 20 0

17,1 17,1 17,1 22,2 0

11,4 11,4 11,4 16,3 23,8 0

7,7 7,7 7,7 10,4 15,1 15,1 0

1,5 1,5 1,5 1,6 6,1 6,1 6,2 0 zdroj: [autor]

Tabulka 9: Jednotlivé iterace algoritmu (malé vozidlo, trasa II.)

1. iterace sdružená trasa 2. iterace sdružená trasa 3. iterace sdružená trasa 4. iterace sdružená trasa 5. iterace sdružená trasa

Z 23 0-2-3-0 Z 12 0-1-2-3-0 Z 56 0-5-6-0 Z 45 0-4-5-6-0 Z 14 0-3-2-1-4-5-6-0

délka [km] 69,3 délka [km] 69,3 délka [km] 33,8 délka [km] 37,2 délka [km] 86,4

Z 67 6. iterace délka [km] sdružená trasa 0-3-2-1-4-5-6-7-0 87,3 Z 78 7. iterace délka [km] sdružená trasa 0-3-2-1-4-5-6-7-8-0 87,3 zdroj: [autor]

Opět došlo k drobné změně a vrcholy by měly být navštíveny v pořadí: Bačkov – Sázavka – Zboží – Mendlova Ves – Štoky – Smilov – Kněžská – Dvorek. Nejkratší možná trasa činí 87,3 km oproti původním 90 km.

24

Hladový algoritmus Dle žravého algoritmu vyšla stejně dlouhá trasa jako u předchozí metody, přestože jsou dva vrcholy prohozené. Graf a trasa jsou znázorněny na přiloženém obrázku 8. Tabulka 10: HK pro trasu II. malého vozidla

HK 1. trasa

elementární trasy délka [km] 0-8-7-6-5-4-1-3-2-0 87,3 zdroj: [autor]

zdroj: [autor]

Obrázek 8: Graf a HK pro trasu II. malého vozidla 5.1.3

Malé vozidlo: Trasa III.

Clark – Wrightova metoda Tabulka 11: Distanční matice (malé vozidlo, trasa III.)

Hesov Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná

v0 v1 v2 v3 v4 v5 v6 v7

He v0

Ut v1

Ko v2

Kv v3

Ci v4

Mo v5

ŽP v6

DJ v7

0

1,9 0

18,3 16,8 0

19,2 17,7 5,3 0

12,7 10,7 23,8 21,5 0

6,8 8,7 25,1 26 7,6 0

6,4 8,3 24,7 25 7,5 2,9 0

4,9 5 18,7 21,4 15 8 7,5 0 zdroj: [autor]

25

Tabulka 12: Matice úspor (malé vozidlo, trasa III.)

v1 v2 v3 v4 v5 v6 v7

v1

v2

v3

v4

v5

v6

v7

0

3,4 0

3,4 32,2 0

3,9 7,2 10,4 0

0 0 0 11,9 0

0 0 0,6 11,6 10,3 0

1,8 4,5 2,7 2,6 3,7 3,8 0 zdroj: [autor]

Tabulka 13: Jednotlivé iterace algoritmu (malé vozidlo, trasa III.)

1. iterace sdružená trasa

Z 23 0-2-3-0

délka [km] 42,8


Z 45

délka [km] 27,1


0-4-5-0 Z 46 0-6-4-5-0 Z 27 0-7-2-3-0

délka [km] 28,3 délka [km] 48,1

Z 67 délka [km] 0-5-4-6-7-2-3-0 72,6

Z 13 6. iterace délka [km] sdružená trasa 0-5-4-6-7-2-3-1-0 73 zdroj: [autor]

Pořadí obsluhy vrcholů je opět jiné oproti původní situaci, nyní ale trasa vychází na 73 km místo původních 72 km. Pořadí vrcholů je následující: Modlíkov – Cibotín – Žižkovo Pole – Dolní Jablonná – Kochánov – Květinov – Utín. Hladový algoritmus Tímto algoritmem jsme nalezli například dvě různá řešení, přičemž jedno se shoduje se stávající situaci, ale díky využití kratších tras je celková vzdálenost menší. Obě řešení jsou znázorněny v grafu na obrázku 9.

26

Tabulka 14: HK pro trasu III. malého vozidla

HK 1. trasa 2. trasa

elementární trasy délka [km] 0-1-7-6-5-4-3-2-0 70 0-1-2-3-4-5-6-7-0 68,4 zdroj: [autor]

zdroj: [autor]

Obrázek 9: Graf a dvě HK pro trasu III. malého vozidla 5.1.4

Vozidlo s vlekem: Trasa III.

Vzhledem k tomu, že se u vozidla s vlekem na trasách I., II. a IV. vyskytuje malý počet vrcholů, nemá smysl tyto trasy optimalizovat ani jedním ze dvou zmíněných způsobů. Proto je pozornost věnována pouze trase III. Clark – Wrightova metoda Tabulka 15: Distanční matice (vozidlo s vlekem, trasa III.)

Hesov Hluboká Krucemburk Střížov Pohled

v0 v1 v2 v3 v4

He v0

Hl v1

Kr v2

St v3

Po v4

0

18,2

21,8

15,8

7,4

0

3,6

15,4

24,9

0

11,9

22

0

12,7

0 zdroj: [autor]

27

Tabulka 16: Matice úspor (vozidlo s vlekem, trasa III.)

v1 v2 v3 v4

v1

v2

v3

v4

0

36,4 0

18,6 25,7 0

0,7 7,2 10,5 0 zdroj: [autor]

Tabulka 17: Jednotlivé iterace algoritmu (vozidlo s vlekem, trasa III.)


Z 12 0-1-2-0 Z 23 0-1-2-3-0 Z 34 0-1-2-3-4-0

délka [km] 43,6 délka [km] 49,5 délka [km] 53,8 zdroj: [autor]

Pořadí vrcholů zůstalo v tomto případě nezměněné, přesto je nejkratší možná trasa 53,8 km oproti původním 56 km. Hladový algoritmus Pomocí žravého algoritmu jsme dostali stejný výsledek jako u předchozí metody. Graf a HK můžeme opět vidět na obrázku 10. Tabulka 18: HK pro trasu III. vozidla s vlekem

HK 1. trasa

elementární trasy délka [km] 0-4-3-2-1-0 53,8 zdroj: [autor]

28

zdroj: [autor]

Obrázek 10: Graf s HK pro trasu III. vozidla s vlekem

5.2 Optimalizace sloučených tras pro každé vozidlo V této části bude znázorněna optimalizace všech vrcholů dohromady, které leží na trasách pro malé vozidlo. Nejdříve podle metody Clarka a Wrighta a také podle Žravého algoritmu. Stejně tak bude provedeno hledání nejlepších tras pro všechny vrcholy dohromady, které se vyskytují na stávajících trasách vozidla s vlekem, a to opět podle dvou výše zmíněných metod. K dispozici bude pro každou variantu jak malé vozidlo, tak i vozidlo s vlekem.

5.2.1

Vrcholy tras malého vozidla

Pro tuto variantu se zde vyskytuje celkem 20 vrcholů, přičemž jeden z nich představuje mlékárnu Pribina v Hesově.

29

Clark – Wrightova metoda Tabulka 19: Distanční matice (všechny vrcholy tras malého vozidla) HE v0 Hesov Veselice Humpolec Radňov Úhořilka Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná

v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19

0

Ve v1

Hu v2

Ra v3

15,4 30,2 20,5 0 18,1 8,4 0 12,6 0

Úh v4

Zb v5

Sá v6

Ba MV Št v7 v8 v9

Sm Kn Dv Ut Ko Kv Ci Mo ŽP DJ v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19

19,7 11,2 16,4 7,8 0

29,6 20,2 25,3 22,5 27,9 0

33,4 24 25,4 26,4 31,7 3,8 0

31,7 22,3 25,6 24,7 30,1 2,1 4,2 0

11,9 15,9 23,9 15 10,8 30,1 33,9 32,2 8,4 5 0

12,8 7,9 19,9 8,6 7,6 22,3 26,2 24,5 0

16,9 15 18,9 12 6,1 29,4 33,2 31,5 7,5 0

8 15,6 28,7 18,2 15,6 29,9 33,7 32 10,4 9,8 4,8 0

3,1 16,3 31,1 21,3 19,5 31,2 35 33,3 14,3 13,9 8,9 4,9 0

1,9 13,8 28,6 18,9 18,1 28,1 31,9 30,2 11,3 16,6 11,6 7,8 2,8 0

18,3 9,8 17,7 6,5 1,4 26,6 30,4 28,7 6,3 6,5 9,4 14,2 18,2 16,8 0

19,2 7,2 12,4 1,2 6,6 21,3 25,1 23,4 7,5 10,9 13,8 17 20,1 17,7 5,3 0

12,7 17,7 32,5 22,7 25,1 25,2 29 27,3 18,4 25,5 22,3 18,5 13,6 10,7 23,8 21,5 0

6,8 22,2 37 27,2 26,5 30,3 34 32,4 19,6 21,1 16,1 12,2 7,7 8,7 25,1 26 7,6 0

6,4 21,2 36 26,2 26,1 27,9 31,7 30 19,2 20,7 15,7 11,8 7,3 8,3 24,7 25 7,5 2,9 0

4,9 18,4 33,1 22,6 20 32,7 36,5 34,8 14,9 14,3 9,3 5,4 2,1 5 18,7 21,4 15 8 7,5 0

zdroj: [autor]

Tabulka 20: Matice úspor s objemy mléka (všechny vrcholy tras malého vozidla) qi Veselice Humpolec Radňov Úhořilka Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná

1980 5680 4160 970 1300 120 1340 640 1840 6730 130 1280 350 8720 2540 230 90 800 990


0

v2

v3

v4

27,5 27,5 23,9 0 38,1 33,5 0 32,4 0

v5

v6

v7

v8

v9

v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19

24,8 34,5 27,6 21,4 0

24,8 38,2 27,5 21,4 59,2 0

24,8 36,3 27,5 21,3 59,2 60,9 0

20,3 23,1 24,7 24,9 20,1 20 20 0

17,3 28,2 25,4 30,5 17,1 17,1 17,1 22,2 0

11,4 18,2 17,4 20,8 11,4 11,4 11,4 16,3 23,8 0

7,8 9,5 10,3 12,1 7,7 7,7 7,7 10,4 15,1 15,1 0

2,2 2,2 2,3 3,3 1,5 1,5 1,5 1,6 6,1 6,1 6,2 0

3,5 3,5 3,5 3,5 3,4 3,4 3,4 3,4 2,2 2,2 2,1 2,2 0

23,9 30,8 32,3 36,6 21,3 21,3 21,3 24,8 28,7 20,8 12,1 3,2 3,4 0

27,4 37 38,5 32,3 27,5 27,5 27,5 24,5 25,2 17,3 10,2 2,2 3,4 32,2 0

10,4 10,4 10,5 7,3 17,1 17,1 17,1 7,1 4,1 2,3 2,2 2,2 3,9 7,2 10,4 0

0 0 0,1 0 6,1 6,2 6,1 0 2,6 2,6 2,6 2,2 0 0 0 11,9 0

0,6 0,6 0,7 0 8,1 8,1 8,1 0 2,6 2,6 2,6 2,2 0 0 0,6 11,6 10,3 0

1,9 2 2,8 4,6 1,8 1,8 1,8 2,8 7,5 7,5 7,5 5,9 1,8 4,5 2,7 2,6 3,7 3,8 0

zdroj: [autor]

30

Tabulka 21: Jednotlivé iterace algoritmu (všechny vrcholy tras malého vozidla) 1. iterace sdružená trasa

Z 6/7 0-6-7-0

q i kapacita 1460 < 29000

elementární trasy 0-6-7-0

q i délka [km] 1460 69,3

2. iterace Z sdružená trasa

5/6

0-5-6-7-0

qi

kapacita 2760 < 29000

elementární trasy 0-5-6-7-0

qi 2760

délka [km] 69,3


3/15

0-3-15-0

qi

kapacita 6700 < 29000

elementární trasy 0-3-15-0 0-5-6-7-0

qi 6700 2760

délka [km] 40,9 69,3


2/3

0-2-3-15-0

qi

kapacita 12380 < 29000

elementární trasy 0-2-3-15-0 0-5-6-7-0

qi 12380 2760

délka [km] 63,2 69,3


qi

qi

0-4-14-0

kapacita 9690 < 29000

elementární trasy 0-2-3-15-0 0-5-6-7-0 0-4-14-0

délka [km] 12380 63,2 2760 69,3 9690 39,4

Z 2/7 0-5-6-7-2-3-15-0

q i kapacita 15140 < 29000

elementární trasy 0-5-6-7-2-3-15-0 0-4-14-0

q i délka [km] 15140 96,2 9690 39,4

Z 4/15 0-5-6-7-2-3-15-4-14-0

q i kapacita 24830 < 29000

elementární trasy 0-5-6-7-2-3-15-4-14-0

q i délka [km] 24830 103,3

Z 9/14 0-5-6-7-2-3-15-4-14-9-0

q i kapacita 26670 < 29000

elementární trasy 0-5-6-7-2-3-15-4-14-9-0

q i délka [km] 26670 108,4

Z 1/5 0-1-5-6-7-2-3-15-4-14-9-0

q i kapacita 28650 < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0

q i délka [km] 28650 114,4

Z 8/10 0-8-10-0


elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-0

q i délka [km] 28650 114,4 7370 33,1

Z 10/11 0-8-10-11-0


elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-11-0

q i délka [km] 28650 114,4 7500 34

4/14


7. iterace sdružená trasa 8. iterace sdružená trasa 9. iterace sdružená trasa 10. iterace sdružená trasa


31


Z 16/17 0-16-17-0

qi 320

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-11-0 0-16-17-0

q i délka [km] 28650 114,4 7500 34 320 27,1

Z 16/18 0-18-16-17-0


elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-11-0 0-18-16-17-0

q i délka [km] 28650 114,4 7500 34 1120 28,3

Z 11/19 0-8-10-11-19-0


elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-11-19-0 0-18-16-17-0

q i délka [km] 28650 114,4 8490 36,3 1120 28,3

Z 12/19 0-8-10-11-19-12-0


elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-8-10-11-19-12-0 0-18-16-17-0

q i délka [km] 28650 114,4 9770 36,6 1120 28,3

Z 8/13 0-13-8-10-11-19-12-0

q i kapacita 10120 < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-13-8-10-11-19-12-0 0-18-16-17-0

q i délka [km] 28650 114,4 10120 37 1120 28,3





17. iterace Z 12/17 q i kapacita sdružená trasa 0-13-8-10-11-19-12-17-16-18-0 11240 < 29000

q i délka [km] elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 28650 114,4 0-13-8-10-11-19-12-17-16-18-0 11240 63,1

zdroj: [autor]

Touto metodou byly navrženy dvě trasy o celkové délce 177,5 km. Pokud se podíváme na stávající tři trasy malého vozidla, jejich celková délka činí 240 km. První trasa je navržena pro obsluhu vozidlem s vlekem, neboť součet objemů mléka ze všech kravínů na této trase je 28 650 litrů. Délka této trasy je 114,4 km. Na druhou trasu stačí nasadit malé vozidlo, protože celkový objem je 11 240 litrů a délka trasy je 63,1 km. První trasa zahrnuje následující vrcholy: Veselice – Zboží – Sázavka – Bačkov – Humpolec – Radňov – Květinov – Úhořilka – Kochánov – Štoky. Druhá trasa obsahuje vrcholy v tomto pořadí: Utín – Mendlova Ves – Smilov – Kněžská – Dolní Jablonná – Dvorek – Modlíkov – Cibotín – Žižkovo Pole. 32

Hladový algoritmus V tomto případě nemůže jedno vozidlo obsloužit všechny vrcholy. Žravý algoritmus bude tedy použit tak, že až bude kapacita vozidla naplněna, vozidlo pojede do závodu v Hesově všechno mléko vyložit. Poté vyrazí do vrcholu, do kterého by mělo normálně pokračovat. Na obrázku 11 je znázorněn graf s nalezenými HK. Tabulka 22: Distanční matice s objemy mléka (všechny vrcholy tras malého vozidla) HE v0 Hesov Veselice Humpolec Radňov Úhořilka Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná

qi 1980 5680 4160 970 1300 120 1340 640 1840 6730 130 1280 350 8720 2540 230 90 800 990


0

Ve v1

Hu v2

Ra v3

15,4 30,2 20,5 0 18,1 8,4 0 12,6 0

Úh v4

Zb v5

Sá v6

Ba MV Št v7 v8 v9

Sm Kn Dv Ut Ko Kv Ci Mo ŽP DJ v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19

19,7 11,2 16,4 7,8 0

29,6 20,2 25,3 22,5 27,9 0

33,4 24 25,4 26,4 31,7 3,8 0

31,7 22,3 25,6 24,7 30,1 2,1 4,2 0

11,9 15,9 23,9 15 10,8 30,1 33,9 32,2 8,4 5 0

12,8 7,9 19,9 8,6 7,6 22,3 26,2 24,5 0

16,9 15 18,9 12 6,1 29,4 33,2 31,5 7,5 0

8 15,6 28,7 18,2 15,6 29,9 33,7 32 10,4 9,8 4,8 0

3,1 16,3 31,1 21,3 19,5 31,2 35 33,3 14,3 13,9 8,9 4,9 0

1,9 13,8 28,6 18,9 18,1 28,1 31,9 30,2 11,3 16,6 11,6 7,8 2,8 0

18,3 9,8 17,7 6,5 1,4 26,6 30,4 28,7 6,3 6,5 9,4 14,2 18,2 16,8 0

19,2 7,2 12,4 1,2 6,6 21,3 25,1 23,4 7,5 10,9 13,8 17 20,1 17,7 5,3 0

12,7 17,7 32,5 22,7 25,1 25,2 29 27,3 18,4 25,5 22,3 18,5 13,6 10,7 23,8 21,5 0

6,8 22,2 37 27,2 26,5 30,3 34 32,4 19,6 21,1 16,1 12,2 7,7 8,7 25,1 26 7,6 0

6,4 21,2 36 26,2 26,1 27,9 31,7 30 19,2 20,7 15,7 11,8 7,3 8,3 24,7 25 7,5 2,9 0

4,9 18,4 33,1 22,6 20 32,7 36,5 34,8 14,9 14,3 9,3 5,4 2,1 5 18,7 21,4 15 8 7,5 0

zdroj: [autor]

Tabulka 23: HK pro všechny vrcholy tras malého vozidla

HK elementární trasy 1. trasa 0-13-12-19-11-10-9-4-14-15-3-0 2. trasa 0-1-8-16-18-17-5-7-6-2-0

qi 27710 12180

délka [km] 56,5 144,3 zdroj: [autor]

33

zdroj: [autor]

Obrázek 11: Graf se dvěma HK pro obsluhu všech vrcholů tras malého vozidla Jako výsledek nám tato metoda přinesla dvě trasy o celkové délce 200,8 km. První trasa musí být obsloužena vozidlem s vlekem, celkový objem je 27 710 litrů a vzdálenost činí 56,5 km. Druhá trasa může být obsloužena malým vozidlem, neboť celkový objem je 12 180 litrů. Délka druhé trasy je 144,3 km. První trasa se skládá z vrcholů v pořadí: Utín – Dvorek – Dolní Jablonná – Kněžská – Smilov – Štoky – Úhořilka – Kochánov – Květinov – Radňov. Druhou trasu tvoří vrcholy: Veselice – Mendlova Ves – Cibotín – Žižkovo Pole – Modlíkov – Zboží – Bačkov – Sázavka – Humpolec.

5.2.2

Vrcholy tras vozidla s vlekem

V této variantě se vyskytuje celkem 8 vrcholů plus počáteční a koncový vrchol, kterým je závod Pribina v obci Hesov.

34

Clark – Wrightova metoda Tabulka 24: Distanční matice (všechny vrcholy tras vozidla s vlekem)

He v0 Hesov Pavlov Radostín n. O. Hluboká Krucemburk Střížov Pohled Nová Ves Slavkovice

v0 v1 v2 v3 v4 v5 v6 v7 v8

0

Pa RnO Hl v1 v2 v3

Kr v4

St v5

27,1 30,1 18,2 21,8 15,8

0

4,3 31,9 32,7 35,3

0

28,7 29,5 37,3

0

Po v6

NV v7

Sl v8

7,4 30,1 25,7 34

20,7 19,5

37

16,6 15,4

3,6 15,4 24,9 27,2 22,6

0

11,9

0

22

28

23,4

12,7 35,7 31,1

0

37,1 32,5

0

4,6

0 zdroj: [autor]

Tabulka 25: Matice úspor s objemy mléka (všechny vrcholy tras vozidla s vlekem)

qi Pavlov Radostín n. O. Hluboká Krucemburk Střížov Pohled Nová Ves Slavkovice

v1

22020 23140 420 17430 2500 5730 6630 13920

v1 v2 v3 v4 v5 v6 v7 v8

0

v2

v3

v4

v5

v6

7,6

0,5 36,5 33,3

8,6

0,5 43,6 40,4

36,4 18,6

0,7 21,1 21,3

52,9 13,4 16,2

0

19,6 22,4

0

0

v7

v8

25,7

7,2 23,9 24,1

0

10,5 10,2 10,4

0

0,4

0,6

0

51,2

0 zdroj: [autor]

Tabulka 26: Jednotlivé iterace algoritmu (všechny vrcholy tras vozidla s vlekem) 1. iterace Z sdružená trasa

7/8

0-7-8-0

qi 20550

kapacita < 29000

qi elementární trasy 0-7-8-0 20550

kapacita < 29000

qi elementární trasy 0-7-8-0 20550 0-3-4-0 17850


3/4

0-3-4-0

qi 17850

35


qi

0-3-4-5-0

20350

kapacita < 29000

Z 5/6 0-3-4-5-6-0

qi 26080

kapacita < 29000

4/5

qi elementární trasy 0-7-8-0 20550 0-3-4-5-0 20350

qi elementární trasy 0-7-8-0 20550 0-3-4-5-6-0 26080


qi délka [km] 20550 60,4 26080 53,8 22020 54,2 23140 60,2

elementární trasy 0-7-8-0 0-3-4-5-6-0 0-1-0 0-2-0

zdroj: [autor]

Výsledkem jsou čtyři trasy, které se až na jednu neliší od stávajícího řešení. Délka těchto tras dohromady činí 228,6 km oproti původním 252 km. Na všechny trasy je nutno nasadit velké vozidlo. První trasa o délce 60,4 km zahrnuje vrcholy Nová Ves a Slavkovice. Druhá 53,8 km dlouhá trasa obsahuje obce Hluboká – Krucemburk – Střížov – Pohled. Třetí trasa délky 54,2 km vede pouze do Pavlova a trasa čtvrtá o délce 60,2 km zahrnuje pouze obec Radostín nad Oslavou. Hladový algoritmus Jedno vozidlo opět z kapacitních důvodů nemůže obsloužit všechny vrcholy, proto je zde postup stejný jako u všech vrcholů tras malého vozidla. Obrázek 12 znázorňuje graf s nalezenými HK. Tabulka 27: Distanční matice s objemy mléka (všechny vrcholy tras vozidla s vlekem) He v0 Hesov Pavlov Radostín n. O. Hluboká Krucemburk Střížov Pohled Nová Ves Slavkovice

qi 22020 23140 420 17430 2500 5730 6630 13920

v0 v1 v2 v3 v4 v5 v6 v7 v8

0

Pa RnO Hl v1 v2 v3

Kr v4

St v5

27,1 30,1 18,2 21,8 15,8

0

4,3 31,9 32,7 35,3

0

28,7 29,5 37,3

0

Po v6

NV v7

Sl v8

7,4 30,1 25,7 34

20,7 19,5

37

16,6 15,4

3,6 15,4 24,9 27,2 22,6

0

11,9

0

22

28

23,4

12,7 35,7 31,1

0

37,1 32,5

0

4,6

0 zdroj: [autor]

36

Tabulka 28: HK pro všechny vrcholy tras vozidla s vlekem HK 1. trasa 2. trasa 3. trasa 4. trasa

elementární trasy 0-6-5-4-3-0 0-8-7-0 0-1-0 0-2-0

qi 26080 20550 22020 23140

délka [km] 53,8 60,4 54,2 60,2 zdroj: [autor]

zdroj: [autor]

Obrázek 12: Graf se čtyřmi HK pro obsluhu všech vrcholů tras vozidla s vlekem Pomocí Žravého algoritmu jsme dostali stejný výsledek jako u předchozí metody, řešením jsou tedy 4 trasy.

5.3 Optimalizace tras pro všechny vrcholy obou vozidel Nakonec jsou hledány nejlepší trasy pro obsluhu všech vrcholů stávajících tras obou vozidel. Na tento problém je použit algoritmus Clarka a Wrighta. Clark – Wrightova metoda Pomocí této metody se budeme snažit navrhnout optimální trasy pro 28 vrcholů včetně vrcholu počátečního (koncového).

37

Tabulka 29: Distanční matice (všechny vrcholy tras obou vozidel)

Hesov Veselice Humpolec Radňov Úhořilka Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná Pavlov Radostín n. O. Hluboká Krucemburk Střížov Pohled Nová Ves Slavkovice

v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19 v 20 v 21 v 22 v 23 v 24 v 25 v 26 v 27

Sm Kn

Dv

Ut

Ko

Kv

Ci

Mo

ŽP

DJ

Pa RnO Hl

Kr

v 24

St

7,4 30,1 25,7

Po NV Sl v 25 v 26 v 27

Št

v 23

Ba MV

v 22

Sá

v 20

Zb

v 19

Úh

4,9 27,1 30,1 18,2 21,8 15,8

Ra

v 18

Hu

6,4

Ve v 17

HE 6,8

v 21

v 16

v 10

v 15

v9

v 14

v8

v 13

v7 1,9 18,3 19,2 12,7

v6

v 12

v5 3,1

v4

20,6 10,1 45,7 41,1

v 11

v3

7,2 17,7 22,2 21,2 18,4 39,9 43,1 33,5

30

8

v2 9,8

56

15,9 15,6 16,3 13,8

46,2

15

60

7,9

51

50

25,7 15,2

33,1 47,2

35

36

48,3 44,8 35,4 24,9

37

54

45,4

20

34,4 37,6

1,2 22,7 27,2 26,2 22,6 40,3 43,5 38,5

50

58

3,8

6,5

0 0

18,2 21,3 18,9

58

56

15

62

12

37,4 28,1 17,6

60

8,6

36,4 32,9 25,1 23,2

38

27

7,8 22,5 26,4 24,7

57

37

40,2 36,7 28,9

22,3

v1 24

15,4 30,2 20,5 19,7 29,6 33,4 31,7 12,8 16,9 11,9

0

61

12,6 16,4 25,3 25,4 25,6 19,9 18,9 23,9 28,7 31,1 28,6 17,7 12,4 32,5

8,4 11,2 20,2

v0 18,1

0 0 0

54

59

6,6 25,1 26,5 26,1

58

1,4

2,1 22,3 29,4 30,1 29,9 31,2 28,1 26,6 21,3 25,2 30,3 27,9 32,7

56

34

6,1 10,8 15,6 19,5 18,1

34,8

29

7,6

30

31,7 36,5

31,9 30,4 25,1

27,9 31,7 30,1 35

33,5 25,7 25,3

33,3 30,2 28,7 23,4 27,3 32,4

32

9,8 13,9 16,6

8,4 10,4 14,3 11,3

7,5 18,4 19,6 19,2 14,9 34,4 37,7 31,2 30,7 21,3 10,8 43,1 38,5 8,9 11,6

6,3

5

7,8 14,2

2,1 27,4 30,4 19,4 22,9 16,4

5,7 32,2 27,7

8,1 31,2 26,6

31

9,3 27,7 30,9 27,7 31,3 25,2 16,9 39,5 34,9 7,3

29,2 32,2 20,4 22,9 13,5

5,4 27,9 31,1 23,8 27,4 21,3 13,1 35,6 7,7

5

18,5 12,2 11,8 8,3

17

9,4 13,8 22,3 16,1 15,7

6,5 10,9 25,5 21,1 20,7 14,3 28,3 31,6 32,7 36,3 28,1 17,8 44,1 39,5

0

7,5

4,8

2,8 18,2 20,1 13,6

24,5 31,5 32,2

4,2 26,2 33,2 33,9 33,7

0

0 0 0

0

4,9

8,7

44

16,8 17,7 10,7

32,7 34,7 15,8 12,8

10

45 15

21,4 39,1 42,4 37,2 33,7 24,3 13,9 49,5

36,8 35,9 26,6 16,2 48,6 25

38 7,5

5,3 23,8 25,1 24,7 18,7 34,7 26

28,6 30,7 14,6 15,3 10,2 13,4 29,5 24,9

11,7 32,3 27,7

9,7 33,2 28,6

7,6

8

5,9

0

21,5

7,5 29,3 32,3 17,6

4,3 31,9 32,7 35,3

34

20,7 19,5

11,9

22

0

28

23,4

37,1 32,5

12,7 35,7 31,1

0

4,6

38

0

0

0

0

0

2,9

0

16,6 15,4

25,3 28,2 19,5 23,1 17,4 10,3 31,3 26,7

17

0

0

37

0

3,6 15,4 24,9 27,2 22,6

28,7 29,5 37,3

0

0

0

0

zdroj: [autor]

Tabulka 30: Matice úspor s objemy mléka (všechny vrcholy tras obou vozidel) Veselice Humpolec Radňov Úhořilka Zboží Sázavka Bačkov Mendlova Ves Štoky Smilov Kněžská Dvorek Utín Kochánov Květinov Cibotín Modlíkov Žižkovo Pole Dolní Jablonná Pavlov Radostín n. O. Hluboká Krucemburk Střížov Pohled Nová Ves Slavkovice

v1 v2 v3 v4 v5 v6 v7 v8 v9 v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19 v 20 v 21 v 22 v 23 v 24 v 25 v 26 v 27

Ve v2

Hu v3

Ra v4

Úh v5

Zb v6

Sá v7

v8

Ba MV v9

Št v 10

v 11

Sm Kn v 12

Dv v 13

Ut v 14

Ko v 15

Kv v 16

Ci

v 17

Mo

v 18

ŽP

v 19

DJ

v 20

v 22

Pa RnO Hl

v 23

Kr

v 24

St

v 25

Po

v 26

NV

2,2

10,4

3,5 23,9 27,4 10,4

0

0

0,6

0,6

2

1,9

10,1 10,3

2,6

0,1

0,1

7,2 10,6 12,7

7,2 10,6 12,7

0,3

0

0

0

Sl v 27

7,8 3,5 30,8

7,7

21,4 21,4 21,3 24,9 30,5 20,8 12,1

32,4 27,6 27,5 27,5 24,7 25,4 17,4 10,3

1,5

1,5

3,3

2,3

7,1

3,4 21,3 27,5 17,1

3,4 21,3 27,5 17,1

3,4 21,3 27,5 17,1

3,5 36,6 32,3

4,1

7,3

3,5 32,3 38,5 10,5

2,6

2,6

2,6

0

6,1

6,2

6,1

0

0,1

2,6

2,6

2,6

0

8,1

8,1

8,1

0

0,7

7,5

7,5 11,3 11,1

7,5 15,7 15,4

2,8

1,8

1,8

1,8

2,8

2,5

2,7

7,3

5,2

2,4

0

0,2

2,4

2,4

3,9

20

4,1

2,5

2,5

4,6

7,3

2,3

2,4

6,5

9,4

21,8 13,8

2,7 11,4 18,5 20,3 13,8

0

2,4

2,5 11,4 18,5 20,3 13,8

7,1

2,4

2,8 12,9

4,6 12,4 12,2

2,8

5,5

2,4

9,5

7,3 10,6 12,7

2,5

2,5

2,9

0

1,8

1,5

1,7

0

0

2,7

2,7

3,1

0

1,4

1,1

1,3

0

0

2,4

27,5 27,5 23,9 24,8 24,8 24,8 20,3 17,3 11,4 2,2

v 21

v1 0 9,5

7,7

3,4 24,8 24,5

2,3

37

38,1 33,5 34,5 38,2 36,3 23,1 28,2 18,2

0 0

17,1 11,4

1,5

2,2 28,7 25,2

2,2 2,2

3,4

3,2

3,4

2,2

3,9

2,2

0

2,2

0

0

2,2

4,5 10,7 10,4

1,8

5,9

0

2,8

7,2

0

2,8

7

0

0

1,9

4,2

0,8

2

7,5

4,2

2,5

9,5

3,6

2,4

0

0

2

0

0

0

2,2

7,4

20

59,2 59,2 20,1 17,1 11,4 7,7

1,6

2,2 20,8 17,3

0 60,9 17,1 11,4

6,1

2,1 12,1 10,2

0 20 22,2 16,3 10,4

6,1

0 0 0

23,8 15,1

6,2

0

0

15,1

0

0

0

0

9,8

7,2

7,6

32,2

9,6

4,4

0

7,4

3,9

0

8,1 15,1 21,7 22,6 10,4

4,2

7,3 10,7 12,7

0,8

3,7

0,2

6,2 10,4 13,3 12,4

2

2,1

6,9

7,2

11,2 12,2

0,5 36,5 33,3

2,7

3,3

0,6

7,1

7

3,6

0

2,6

5,3

4,2

3,6

10,4

11,9 11,6

3,7

4,2

6,8

0,5 43,6 40,4

0

0

10,3

3,8

6,7

7,6

0

0

0

52,9 13,4 16,2

0,7 21,1 21,3

0

7,2 23,9 24,1

8,6

25,7

0

0,6

36,4 18,6

19,6 22,4

0

0

0,4

10,5 10,2 10,4

0

0

51,2

0

0

39

qi

1980 5680 4160 970 1300 120 1340 640 1840 6730 130 1280 350 8720 2540 230 90 800 990 22020 23140 420 17430 2500 5730 6630 13920

zdroj: [autor]

Tabulka 31: Jednotlivé iterace algoritmu (všechny vrcholy tras obou vozidel) 1. iterace Z sdružená trasa

6/7

0-6-7-0

qi 1460

qi

kapacita < 29000

elementární trasy 0-6-7-0

1460

2760


qi

qi

0-5-6-7-0

2760

kapacita < 29000

elementární trasy 0-5-6-7-0

Z 26/27 0-26-27-0

qi 20550

kapacita < 29000

elementární trasy 0-5-6-7-0 0-26-27-0

2760 20550

qi

kapacita < 29000

elementární trasy 0-5-6-7-0 0-26-27-0 0-3-15-0

2760 20550 6700

kapacita < 29000

elementární trasy 0-5-6-7-0 0-26-27-0 0-2-3-15-0

2760 20550 12380

elementární trasy 0-5-6-7-0 0-26-27-0 0-2-3-15-0 0-4-14-0

2760 20550 12380 9690

5/6


qi


3/15

0-3-15-0

6700

qi


2/3

0-2-3-15-0

qi 12380

qi


qi

qi

0-4-14-0

9690

kapacita < 29000

Z 22/23 0-22-23-0

qi 17850

kapacita < 29000

elementární trasy 0-5-6-7-0 0-26-27-0 0-2-3-15-0 0-4-14-0 0-22-23-0

qi 2760 20550 12380 9690 17850

Z 2/7 0-5-6-7-2-3-15-0

qi 15140

kapacita < 29000

elementární trasy 0-5-6-7-2-3-15-0 0-26-27-0 0-4-14-0 0-22-23-0

qi 15140 20550 9690 17850

Z 4/15 0-5-6-7-2-3-15-4-14-0

qi 24830

kapacita < 29000

elementární trasy 0-5-6-7-2-3-15-4-14-0 0-26-27-0 0-22-23-0

qi 24830 20550 17850

4/14




40


Z 9/14 0-5-6-7-2-3-15-4-14-9-0

qi 26670

kapacita < 29000

elementární trasy 0-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-0

qi 26670 20550 17850

Z 23/24 0-22-23-24-0

qi 20350

kapacita < 29000

elementární trasy 0-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-0

qi 26670 20550 20350

Z 1/5 0-1-5-6-7-2-3-15-4-14-9-0

qi 28650

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-0

qi 28650 20550 20350

Z 16/24 0-22-23-24-16-0

qi 20580

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-0

qi 28650 20550 20580

Z 8/10 0-8-10-0

qi 7370

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-0 0-8-10-0

qi 28650 20550 20580 7370

Z 10/11 0-8-10-11-0

qi 7500

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-0 0-8-10-11-0

qi 28650 20550 20580 7500

Z 16/17 0-22-23-24-16-17-0

qi 20670

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-0 0-8-10-11-0

qi 28650 20550 20670 7500

Z 17/18 0-22-23-24-16-17-18-0

qi 21470

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-8-10-11-0

qi 28650 20550 21470 7500





15. iterace



41

18. iterace Z 8/25 0-25-8-10-11-0

qi 13230

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-25-8-10-11-0

qi 28650 20550 21470 13230

Z 11/19 0-25-8-10-11-19-0

qi 14220

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-25-8-10-11-19-0

qi 28650 20550 21470 14220

Z 13/25 0-13-25-8-10-11-19-0

qi 14570

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-13-25-8-10-11-19-0

qi 28650 20550 21470 14570

Z 12/19 0-13-25-8-10-11-19-12-0

qi 15850

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-13-25-8-10-11-19-12-0 0-20-0 0-21-0

qi 28650 20550 21470 15850 22020 23140

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-13-25-8-10-11-19-12-0 0-20-0 0-21-0

qi 28650 20550 21470 15850 22020 23140

délka [km] 114,4 60,4 56,5 42,2 54,2 60,2

sdružená trasa




zdroj: [autor]

Touto metodou bylo navrženo 6 tras, jejichž celková délka činí 387,9 km. Oproti tomu původní trasy měří celkem 492 km. Všechny trasy je třeba z kapacitních důvodů obsloužit vozidlem s vlekem. 1. trasa měří 114,4 km a zahrnuje vrcholy: Veselice – Zboží – Sázavka – Bačkov – Humpolec – Radňov – Květinov – Úhořilka – Kochánov – Štoky. 2. trasa je dlouhá 60,4 km a tvoří ji vrcholy Nová Ves a Slavkovice. 3. trasa činí 56,5 km a obsahuje následující vrcholy: Hluboká – Krucemburk – Střížov – Cibotín – Modlíkov – Žižkovo Pole. 4. trasa délky 42,2 km je tvořena z těchto vrcholů: Utín – Pohled – Mendlova Ves – Smilov – Kněžská – Dolní Jablonná – Dvorek. 5. trasa o délce 54,2 km zahrnuje pouze vrchol Pavlov. 6. trasa, která měří 60,2 km, zahrnuje pouze Radostín nad Oslavou. 42

6 Srovnání současného stavu a vybraných řešení

V této části je současný stav svozu mléka porovnán s možnými návrhy nových tras. Důraz je kladen na celkové množství kilometrů, které obě auta urazí za jeden den. Jsou zde tedy srovnávány trasy, které vznikly optimalizací všech vrcholů obou vozidel dohromady podle Clark – Wrightovy metody.

6.1 Vybraná řešení Dle algoritmu Clarka a Wrighta bylo vytvořeno celkem 6 tras, které jsou již zmíněny výše. Všechny trasy je nutné obsloužit vozidlem s vlekem, neboť objem sváženého mléka v každé trase převyšuje kapacitu malého vozidla. V takovém případě máme dvě možnosti, jak se rozhodneme: 1. Prodáme malé vozidlo a na všechny trasy budeme využívat pouze jedno vozidlo s vlekem. Výhodou této varianty je, že získáme peníze za malé vozidlo a navíc nebudeme mít žádné další investice. Tato varianta má ovšem jednu velkou nevýhodu. Pokud dojde například k poruše vozidla, nemáme žádný záložní vůz a problém budeme muset složitě a draze řešit například pronajmutím vozidla. Navíc takováto situace vyžaduje okamžité řešení, protože je nutné mléko z kravínů každý den odvézt. Při využívání pouze jednoho vozidla dojde k jeho velkému opotřebení a bude třeba vynaložit více financí na jeho údržbu. 2. Dokoupíme vlek k malému vozidlu a na zmíněných 6 tras budeme využívat dvě vozidla s vlekem. Budeme tedy muset investovat na koupi vleku. Výhodou však je možnost zálohy v případě, že jedno z vozidel nebude schopné provozu a vše zvládneme obsloužit jedním vozidlem. Zátěž bude rozložena mezi dvě vozidla a tím dojde k jejich menšímu opotřebení. Pokud budou využívána dvě vozidla, svoz mléka půjde také časově lépe zorganizovat, protože vozidla jsou na sobě nezávislá. Další, třetí možností by mohla být například situace, že budeme mít k dispozici jak vozidlo s vlekem, tak i malé vozidlo. Obsluha kravínu bude zajišťována vozidlem s vlekem a malé vozidlo bude v záloze pro případ potřeby. Pro tuto situaci by ale bylo vhodné trasy ještě trochu pozměnit. Konkrétně by se změna týkala poslední iterace algoritmu Clarka a Wrighta. Místo této iterace (Z12/19) bychom vybrali další nejlepší možnost z matice výhodnostních koeficientů a následnou iterací algoritmu bychom vrchol č. 12 přesunuli do jiné trasy, jak můžeme vidět v následující tabulce.

43

Tabulka 32: Změna poslední iterace algoritmu (všechny vrcholy tras obou vozidel) 21. iterace sdružená trasa

Z 12/20 0-12-20-0

qi 23300

kapacita < 29000

elementární trasy 0-1-5-6-7-2-3-15-4-14-9-0 0-26-27-0 0-22-23-24-16-17-18-0 0-13-25-8-10-11-19-0 0-12-20-0 0-21-0

qi 28650 20550 21470 14570 23300 23140

zdroj: [autor]

Výsledkem je opět 6 tras, přičemž 4 z nich jsou naprosto shodné s předešlým řešením. Změna proběhla pouze ve 4. a 5. trase. Ve čtvrté trase jeden vrchol ubyl a vypadá takto: Utín – Pohled – Mendlova Ves – Smilov – Kněžská – Dolní Jablonná. Trasa je nyní o 0,3 km kratší a měří 41,9 km. V páté trase je naopak o jeden vrchol více, takže trasa nyní zahrnuje Dvorek a Pavlov. Délka trasy se zvětšila o 3,4 km a číní 57,6 km. Při této změně se celková délka tras zvětší z původních 387,9 km na 391 km. Vidíme tedy, že prodloužení tras je o pouhých 3,1 km. Podstatné ale na změně poslední iterace algoritmu je, že objem sváženého mléka ve 4. trase se zmenšil na 14 570 litrů a je tedy možné tuto trasu obsloužit malým vozidlem. Výhodou této možnosti je, že nemusíme kupovat druhý vlek a investovat tak další peníze a přesto máme jedno záložní malé vozidlo. Toto řešení je zajímavé tím, že malé vozidlo pravidelně využíváme a jsme jím schopni obsloužit jednu trasu. Díky tomu bude svoz mléka časově méně náročný a bude možné ho lépe zorganizovat. Při střídání vozidel dojde také k jejich pomalejšímu opotřebení.

6.2 Finální návrh tras Ze třech zmíněných výsledných řešení bude zvoleno a se současným stavem porovnáno to poslední. Toto řešení se jeví jako nejvýhodnější. U první varianty chybí záložní vozidlo. To může představovat velký problém. U druhé varianty je nutné investovat a koupit vlek. Třetí možné řešení v sobě již zahrnuje záložní malé vozidlo bez dalších investic a navíc obsluhu jedné trasy tímto vozidlem. Vzhledem k tomu, že je tato práce zaměřená na optimalizaci tras, nebude zde uváděna podrobná ekonomická situace pro různá řešení. V následující tabulce bude pouze nastíněno, kolik by mohla firma ušetřit, pokud by pro svoz mléka použila nové trasy. K tomu je také třeba uvést průměrnou spotřebu vozidel, kterými je mléko sváženo, a průměrnou cenu nafty. Průměrná spotřeba činí 34 l / 100 km a průměrná cena nafty za poslední rok se pohybovala okolo 32,87 Kč / l.

44

Tabulka 33: Porovnání současného stavu a vybraného řešení

Současný stav

Finální návrh tras

1 x malé vozidlo 1 x vozidlo s vlekem

Vozidla

Počet tras

7 3 x malé vozidlo 4 x vozidlo s vlekem

6 1 x malé vozidlo 5 x vozidlo s vlekem

Celkem km/den Celkem km/rok

492 179580

391 142715

Cena za naftu/den Cena za naftu/rok

5 498 Kč 2 006 950 Kč

4 370 Kč 1 594 954 Kč

Úspora km/den Úspora km/rok

101 36865

Úspora financí/den

1 129 Kč

Úspora financí/rok

411 996 Kč zdroj: [autor]

Jak z tabulky vyplývá, vozidla by mohla najezdit za rok o 36 865 km méně a celková roční úspora firmy na pohonných hmotách by mohla činit až 411 996 Kč. Vše tedy záleží na společnosti, na jednotlivých kravínech a na tom, zda je v jejich možnostech dohodnout se tak, aby bylo možné finální návrh svozových tras mléka realizovat. Pro firmu TPK Pribina by to jistě byla po finanční stránce vítaná změna.

45

7 Závěr

V dnešní době by už žádná společnost neměla podcenit způsob, jakým si bude nechat dovážet suroviny na výrobu produktů nebo jakým bude hotové produkty rozvážet. Náklady na tyto činnosti jsou totiž často dost vysoké a tvoří významnou část všech nákladů firmy, jak z práce vyplývá. Je zbytečné, aby firma, která se dopravní obsluhou jinak nezabývá, přicházela v této oblasti o finance. Tato práce se zabývala optimalizací a návrhem tras na svoz mléka ve firmě TPK Pribina, což je mlékárenský závod. Tato společnost získává denně mléko z kravínů v okolí. Správná volba tras je tedy důležitá, neboť výdaje za pohonné hmoty nejsou

malé.

Cílem

práce

bylo

navrhnout

trasy

svozu

mléka,

které

začínají

a končí ve stejném vrcholu, zahrnou všechny kravíny a jejichž součet délek bude minimální. Jednalo se tedy o úlohu obchodního cestujícího. S omezující podmínkou, kterou byla kapacita vozu, se úloha změnila na problém vícenásobného obchodního cestujícího resp. okružní problém. Pro optimalizaci a návrh nových tras bylo tudíž využito dvou metod z teorie grafů, které výše zmíněné úlohy mohou řešit. Problém obchodního cestujícího byl řešen Žravým algoritmem, okružní problém potom pomocí Clark – Wrightovy metody. V práci byla nejdříve představena společnost TPK Pribina, byl uveden její vývoj a nabízené produkty. Ve druhé části byla znázorněna současná situace podniku z hlediska svozu mléka. Bylo popsáno okolí podniku, proces, jak svoz mléka probíhá, a byly zde znázorněny a popsány současné trasy obou vozidel, která jsou společností k tomuto účelu využívána. Třetí část práce byla věnována výběru vhodných metod řešení na dané typy úloh. Obě úlohy zde byly popsány. Byl zvolen Žravý algoritmus a algoritmus Clarka a Wrighta. Pro tyto dvě metody řešení byly popsány jednotlivé kroky, jak postupovat. V další části práce byly tyto metody aplikovány na současný stav. Vstupním prvkem do algoritmů byla matice přímých vzdáleností, která byla sestavena dle aplikace Mapy.cz a také objemy mléka nabíraného v jednotlivých kravínech. Nejdříve byla provedena optimalizace jednotlivých tras každého vozidla. Došlo tedy k postupnému optimalizování tří tras malého vozidla a jedné trasy vozidla s vlekem. Poté byly vybrány všechny vrcholy, které ležely na původních trasách malého vozidla, a byly pro ně vytvořeny trasy nové. To stejné bylo provedeno i s vrcholy vozidla s vlekem. Na každou tuto variantu byl použit jak Žravý algoritmus, kterým byly určeny Hamiltonovské kružnice, tak i Clark – Wrightova metoda. Poslední řešená varianta byla taková, že byly vybrány všechny vrcholy obou vozidel dohromady a nové trasy byly navrženy dle Clark – Wrightova algoritmu.

46

V závěrečné části byly porovnány různé varianty řešení a byla vybrána ta nejlepší z nich. Výsledkem optimalizace byly tedy nové trasy pro svoz mléka, které obslouží všechny vrcholy a při kterých bude uražena nejmenší možná vzdálenost. Tato nejlepší varianta byla také srovnána se současným stavem, aby byl jasně vidět přínos a zlepšení, které optimalizace přináší. Při současném stavu je celková vzdálenost, kterou obě vozidla během jednoho dne dohromady ujedou, 492 km. Podle nového návrhu by denní ujetá vzdálenost byla 391 km. To je o celých 101 km méně během jediného dne. Vzhledem k tomu, že mléko se sváží každý den, ušetřená vzdálenost za celý rok by činila 36 865 km. Při průměrné spotřebě vozidel 34 litrů nafty na sto kilometrů a při průměrné ceně nafty v uplynulém roce 32,87 Kč za litr si můžeme snadno spočítat finanční úsporu, kterou nám nový svozový plán nabízí. Za jeden den by bylo možné ušetřit 1 129 Kč, za jeden rok potom 411 996 Kč. Částka, kterou firma za pohonné hmoty utratí během jednoho roku, je 2 006 950 Kč. Z toho je patrné, že společnost TPK Pribina by při použití nových tras na svoz mléka mohla ročně ušetřit více jak 20 % nákladů, které na svoz mléka vynakládá nyní. To by pro ni znamenalo určitě velmi příjemnou změnu v rozpočtu. Změna současných tras a zavedení tras nových ale není jednoduchou záležitostí. Záleží na společnosti a na jednotlivých kravínech, zda jsou ochotni a zda je v jejich možnostech dohodnout se tak, aby byly nově navrhované trasy skutečně zavedeny.

47

8 Literatura Knihy a brožury [1] MOCKOVÁ, D. :Základy teorie dopravy: úlohy. Vyd. 1. V Praze: Nakladatelství ČVUT, 2007, 96 s. ISBN 978-80-01-03791-1. [2] VOLEK, J. – LINDA, B. :Teorie grafů - aplikace v dopravě a veřejné správě. Vyd. 1. Pardubice: Univerzita Pardubice, 2012, 190 s. ISBN 978-80-7395-225-9. [3] VOLEK, J. :Operační výzkum I. Vyd. 1. Pardubice: Univerzita Pardubice, 2002, 111 s. ISBN 80-7194-410-6. [4] DEMEL, J. :Grafy a jejich aplikace. Vyd. 1. Praha: Academia, 2002, 257 s. ISBN 80-200-0990-6. Internetové stránky [5] Seznam.cz: MAPY.CZ [online]. [cit. 2015-07-19]. Dostupné z: www.mapy.cz [6] TPK Pribina: O firmě [online]. [cit. 2015-07-23]. Dostupné z: www.pribina-tpk.cz/o-firme [7] EU2009.CZ: Regiony ČR [online]. [cit. 2015-07-23]. Dostupné z: www.eu2009.cz/cz/czech-republic/regions/regiony-cr-328/ [8] Ministerstvo dopravy: Výjimky [online]. [cit. 2015-07-23]. Dostupné z: http://www.mdcr.cz/cs/Silnicni_doprava/Nakladni_doprava/Re%C5%BEim+%C5%99idi%C4 %8D%C5%AF/V%C3%BDjimky/V%C3%BDjimky.htm Ostatní [9] Interní zdroj

48

9 Seznam obrázků Obrázek 1: Logo TPK Pribina .............................................................................................. 10 Obrázek 2: Mlékárenský výrobní podnik Pribina .................................................................. 11 Obrázek 3: Poloha mlékárny Pribina v ČR ........................................................................... 12 Obrázek 4: Trasy malého vozidla ......................................................................................... 15 Obrázek 5: Trasy vozidla s vlekem ...................................................................................... 17 Obrázek 6: Malé vozidlo ...................................................................................................... 17 Obrázek 7: Graf a dvě HK pro trasu I. malého vozidla ......................................................... 23 Obrázek 8: Graf a HK pro trasu II. malého vozidla ............................................................... 25 Obrázek 9: Graf a dvě HK pro trasu III. malého vozidla ....................................................... 27 Obrázek 10: Graf s HK pro trasu III. vozidla s vlekem .......................................................... 29 Obrázek 11: Graf se dvěma HK pro obsluhu všech vrcholů tras malého vozidla .................. 34 Obrázek 12: Graf se čtyřmi HK pro obsluhu všech vrcholů tras vozidla s vlekem................. 37

49

10 Seznam tabulek Tabulka 1: Trasy malého vozidla ......................................................................................... 14 Tabulka 2: Trasy vozidla s vlekem ....................................................................................... 16 Tabulka 3: Distanční matice (malé vozidlo, trasa I.) ............................................................. 21 Tabulka 4: Matice úspor (malé vozidlo, trasa I.) ................................................................... 21 Tabulka 5: Jednotlivé iterace algoritmu (malé vozidlo, trasa I.) ............................................ 22 Tabulka 6: HK pro trasu I. malého vozidla ............................................................................ 22 Tabulka 7: Distanční matice (malé vozidlo, trasa II.) ............................................................ 23 Tabulka 8: Matice úspor (malé vozidlo, trasa II.) .................................................................. 24 Tabulka 9: Jednotlivé iterace algoritmu (malé vozidlo, trasa II.) ........................................... 24 Tabulka 10: HK pro trasu II. malého vozidla ......................................................................... 25 Tabulka 11: Distanční matice (malé vozidlo, trasa III.) ......................................................... 25 Tabulka 12: Matice úspor (malé vozidlo, trasa III.) ............................................................... 26 Tabulka 13: Jednotlivé iterace algoritmu (malé vozidlo, trasa III.) ........................................ 26 Tabulka 14: HK pro trasu III. malého vozidla ........................................................................ 27 Tabulka 15: Distanční matice (vozidlo s vlekem, trasa III.) ................................................... 27 Tabulka 16: Matice úspor (vozidlo s vlekem, trasa III.) ......................................................... 28 Tabulka 17: Jednotlivé iterace algoritmu (vozidlo s vlekem, trasa III.) .................................. 28 Tabulka 18: HK pro trasu III. vozidla s vlekem ..................................................................... 28 Tabulka 19: Distanční matice (všechny vrcholy tras malého vozidla) ................................... 30 Tabulka 20: Matice úspor s objemy mléka (všechny vrcholy tras malého vozidla) ............... 30 Tabulka 21: Jednotlivé iterace algoritmu (všechny vrcholy tras malého vozidla) .................. 31 Tabulka 22: Distanční matice s objemy mléka (všechny vrcholy tras malého vozidla) .......... 33 Tabulka 23: HK pro všechny vrcholy tras malého vozidla .................................................... 33 Tabulka 24: Distanční matice (všechny vrcholy tras vozidla s vlekem) ................................. 35 Tabulka 25: Matice úspor s objemy mléka (všechny vrcholy tras vozidla s vlekem) ............. 35 Tabulka 26: Jednotlivé iterace algoritmu (všechny vrcholy tras vozidla s vlekem) ................ 35 Tabulka 27: Distanční matice s objemy mléka (všechny vrcholy tras vozidla s vlekem) ....... 36 Tabulka 28: HK pro všechny vrcholy tras vozidla s vlekem .................................................. 37 Tabulka 29: Distanční matice (všechny vrcholy tras obou vozidel) ....................................... 38 Tabulka 30: Matice úspor s objemy mléka (všechny vrcholy tras obou vozidel) ................... 39 Tabulka 31: Jednotlivé iterace algoritmu (všechny vrcholy tras obou vozidel) ...................... 40 Tabulka 32: Změna poslední iterace algoritmu (všechny vrcholy tras obou vozidel)............. 44 Tabulka 33: Porovnání současného stavu a vybraného řešení ............................................ 45

50

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ

Recommend Documents