Vysoká škola logistiky o.p.s.
Optimalizace dopravních tras v distribuční činnosti (Bakalářská práce)
Přerov 2012
Markéta Žákovská
Čestné prohlášení Prohlašuji, že předložená bakalářská práce je původní a vypracovala jsem ji samostatně. Prohlašuji, že citace použitých pramenů je úplná a že jsem v práci neporušila autorská práva (ve smyslu zákona č. 121/2000 Sb. O právu autorském a o právech souvisejících s právem autorským). Souhlasím s prezentačním zpřístupněním své práce v knihovně Vysoké školy logistiky o. p. s. a s případným použitím této práce Vysokou školou logistiky o. p. s. pro pedagogické, vědecké a prezentační účely.
Přerov dne 27. dubna 2012
…………………………… podpis
Poděkování Děkuji vedoucímu své bakalářské práce Ing. Alexandrovi Čapkovi za jeho odborné vedení, rady a připomínky, které mi poskytl při zpracování této bakalářské práce. Dále děkuji jednateli společnosti REDDO CZ, s. r. o. za poskytnuté podklady pro tuto práci.
Přerov dne 27. dubna 2012
…………………………… podpis
Abstrakt Bakalářská práce se věnuje optimalizaci dopravních tras zajišťujících rozvoz zboží podniku REDDO CZ, s. r. o. Řešeni je prováděno pomoci metody obchodního cestujícího, s použitím MS Excel. Výsledky jsou vyhodnoceny z hledisek časové a finanční úspory a je vytvořena zpráva pro zadavatele, ve které jsou shrnuty ekonomické důsledky realizace optimalizovaného řešeni.
Abstract The Bachelor project deals with the transport route optimization on the company REDDO CZ, s. r. o. Solution is made to help the business methods of the passenger, using MS Excel. The cost and time savings attained by the optimization are presented and the suggestions for the next period planning are summarized.
Obsah Úvod………………...………….…………………...………………………………………...…7 1
Teoretické východisko k řešené problematice ...................................................................9 1.1 Definice logistiky.....................................................................................................9 1.2 Distribuce ................................................................................................................9 1.2.1 Distribuční řetězec .........................................................................................10 1.2.2 Distribuční řetězec společnosti REDDO CZ, s. r. o.........................................11 1.2.2.1 Princip fungování distribučního řetězce společnosti REDDO CZ, s. r. o. ....12 1.2.3 Rozsah distribučního řetězce označuje: ..........................................................12 1.2.4 Druhy distribuce podle rozsahu ......................................................................12 1.2.5 Rozdělení distribuce podle počtu stupňů.........................................................13 1.3 Doprava jako součást logistického systému ............................................................13 1.3.1 Dopravní sítě .................................................................................................14 1.4 Teorie grafů (TG)...................................................................................................15 1.4.1 Základní pojmy teorie grafů ...........................................................................15 1.4.1.1 Orientovaná hrana......................................................................................16 1.4.1.2 Neorientovaná hrana ..................................................................................16 1.4.1.3 Cyklus (kružnice) ......................................................................................16 1.4.1.4 Acyklický graf...........................................................................................16 1.4.1.5 Neorientovaný graf ....................................................................................17 1.4.1.6 Orientovaný graf........................................................................................18 1.4.1.7 Souvislost grafu .........................................................................................18 1.5 Lineární programování ...........................................................................................20 1.5.1 Distribuční metody lineárního programování..................................................20 1.6 Matematické modelování dopravních cest ..............................................................20 1.6.1 Okružní dopravní problém .............................................................................20 1.6.1.1 Historie okružního dopravního problému ...................................................21 1.6.2 Obchodní cestující TSP (Travelling salesman problem)..................................22 1.6.2.1 Hamiltonovská kružnice (cesta) .................................................................23 1.6.3 Matematická definice TSP .............................................................................24 1.6.4 Shrnutí problému TSP....................................................................................28 1.7 Využití informačních technologií ...........................................................................28 1.7.1 Systém Plantour Logistic ...............................................................................29 2 Společnost REDDO CZ, s. r. o........................................................................................30 2.1 Charakteristika získaných dat .................................................................................30 2.1.1 Vozový park ..................................................................................................31 2.1.2 Využití vozidel ..............................................................................................32 2.2 Časové zámky a uzávěrky ......................................................................................32 3 Optimalizace tras metodou obchodního cestujícího .........................................................34 3.1 Zadání....................................................................................................................34 3.2 Ruční výpočet optimální trasy A.............................................................................36 3.3 Ruční výpočet optimální trasy B.............................................................................40 4 Zhodnocení výsledků......................................................................................................45 4.1 Vyhodnocení času ..................................................................................................46 4.2 Vyhodnocení nákladů na pohonné hmoty ...............................................................47 4.3 Zpráva pro zadavatele ............................................................................................48 4.3.1 Současný stav ................................................................................................48 4.3.2 Výsledky optimalizace ...................................................................................49 4.3.3 Doporučení pro plánování na další období......................................................49 Závěr ...........................................................................................................................51
Seznam použitých zdrojů
Seznam zkratek Seznam symbolů Seznam tabulek Seznam obrázků Seznam grafů
Úvod Čas jsou peníze. Tímto heslem se dá vyjádřit i situace, která se váže k hodnocení úspěšnosti podniku. Dynamika rozvoje podnikatelského prostředí vystavuje podnikatele neustálému tlaku, neboť o míře úspěchu či neúspěchu rozhoduji často maličkosti. Tlak je na podnikatele vyvíjen nejen ze strany konkurence, ale i ze stany obchodních partnerů, kteří mají vysoké nároky na služby spojené s dodávkou zboží. Obchodní partneři požaduji, aby byla dodávka přivezena ve správném čase, na správné místo a v požadované kvalitě. Tyto požadavky se snaží firmy uspokojit a omezit tak konkurenční vliv ostatních firem. Každá firma musí své rozvozní linky naplánovat tedy takovým způsobem, aby byla schopna požadavky svých obchodních partnerů kompletně uspokojit. Existuje mnoho různých metod pro zjištění optimálních tras. Ty, které byly v minulosti považovány za nejefektivnější, jsou v současné době nevyhovující. Zvolila jsem si metodu obchodního cestujícího, protože patří mezi nejpoužívanější metody hledání optimálních tras. Metoda je založena na lineárním programování. Cílem této práce je nalezení optimální trasy rozvážkových vozidel a zhodnocení ekonomické výhodnosti nové trasy oproti stávající trase se zaměřením na snížení dopravních nákladů. Optimalizace tras je velmi aktuálním a důležitým tématem, kterému je třeba se intenzivně věnovat, neboť žádný podnik se neobejde bez pohybu hmotných statků. Firmy si vytvářejí často pořadí svých linek podle přibližného vlastního uvážení, čímž zbytečně zvyšují své náklady. Tato práce se snaží tyto zbytečné náklady eliminovat a usiluje o takovém pořadí dopravních tras, jenž povede k co nejvýhodnějšímu rozvozu ke svým odběratelům. Doprava do velké míry ovlivňuje podnikatelská rozhodnutí a tudíž ji můžeme považovat díky své významnosti za podstatnou část logistiky. Dalším výstupem práce bude závěrečná zpráva pro vybraný podnik, kde budou shrnuty výsledky práce a kde budou navrženy doporučení pro možnosti plánování nových tras. Práce je vymezena na dvě části: V teoretické části je objasněna především oblast distribuční logistiky, která představuje tu část logistického řetězce, která začíná ve skladu daného podniku a končí u zákazníka. Dále je zde zpracována problematika teorie grafů, lineárního programování a především
7
dvě optimalizační úlohy. Problém obchodního cestujícího a okružní problém. Typickým příkladem k řešení optimalizace tras je problém obchodního cestujícího, který je využit v této práci. Praktická část je zaměřena na shrnutí současného stavu podniku, jeho fungování dodávek, typů dopravních prostředků a dalších informací, které s touto prací souvisí a jsou důležité k optimalizaci dopravních tras. Druhá polovina praktické části se skládá ze samotného výpočtu tras A, B pomocí metody obchodního cestujícího ručním výpočtem, pomocí MS Excel. Tato druhá část také obsahuje mapy původních a optimalizovaných tras, vyhodnocení úspor nákladů na pohonné hmoty a úspory času, které jsou vyjádřené pomocí grafů. Úplným závěrem práce je zhodnocení všech dosažených výsledku a následné porovnání před a po optimalizaci.
8
1 Teoretické východisko k řešené problematice 1.1 Definice logistiky V literárních pramenech můžeme nalézt nespočet definic, a to jak od českých tak i od zahraničních autorů. Nebylo by jistě věcné uvést pouze jednu definici, a z toho důvodu jsou níže uvedeny některé z nich, které byly uznány mezinárodními institucemi pro logistiku:
,,Logistika je 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).
Logistika je 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.
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.“1
Za druhé je třeba si definovat ekonomické funkce logistiky. Logistika svojí činností nevytváří hmotné statky, ale souhrnem svých činností umožňuje jejich výrobu, ale i směnu a spotřebu, neboť dokáže řešit nesoulad, který vzniká mezi místy výroby určitého zboží a mezi místy po jeho poptávce.
1.2 Distribuce Představuje spojovací článek mezi výrobou a odbytovou částí podniku (obr. č. 1). Zahrnuje v sobě všechny skladové a dopravní pohyby materiálů, výrobků k odběrateli. Distribuční logistika se zabývá hlavně činnostmi, které souvisí s materiálovým tokem, se skladováním hotových výrobků až po odbyt, včetně zkoumání těchto činností a s nimi souvisejícími informacemi.
1
SVOBODA, Vladimír. Doprava jako součást logistických systémů. Vyd. 1. Praha : Vydavatelství ČVUT, 2004. 152 s. ISBN 80-01-02914-X.
9
Distribuční logistiku využívají organizace, které prostřednictvím výrobního procesu vyrábí produkty určené pro prodej, ale i ostatní přepravní a obchodní společnosti, které s ní přicházejí do styku.
Oblastí distribuční logistiky je i problematika plánování dopravních tras.
Součástí optimálního plánování dopravních tras je také řízení dodávek k zákazníkovi.
Umět efektivním způsobem řídit dodávky k zákazníkovi může mít trvalý vliv na ekonomický přínos spočívající na snižování provozních nákladů. 2
Obrázek č. 1 - Oblast distribuční logistiky
Zdroj: Vlastní zpracování Cílem distribuční logistiky je uspokojovat poptávku tím, že zboží je dodáno na správné místo, ve správnou dobu, v požadovaném množství, v smluvené kvalitě, s co nejnižšími náklady.3
1.2.1 Distribuční řetězec Jako distribuční řetězec označujeme tu část logistického řetězce, která začíná okamžikem, kdy výrobek opustí výrobní podnik a končí u konečného zákazníka. ,,Distribuční řetězec je soubor organizačních jednotek výrobce a případně i externích 2
Distribuční logistika [online]. VSB, 25.4.2011 [cit. 2012-04-03]. Dostupné z: http://www.id.vsb.cz/sliva/zl/Zaklady%20logistiky_3.pdf. Bakalářská práce. Vysoká škola Báňská. 3
ČUJAN, Zdeněk a Zdeněk MÁLEK. Výrobní a obchodní logistika. první. Zlín : Univerzita Tomáše Bati ve Zlíně, 2008. 200 s. ISBN 978 -80-7318-730-9.
10
zprostředkovatelů, jejichž prostřednictvím jsou výrobky nebo služby dodávány zákazníkům.2 V průběhu pohybu zboží distribučním řetězcem je třeba zajistit pět základních funkcí:
Skladovací - vyrovnávání rozdílů mezi nabídkou a poptávkou vznikající v důsledku nerovnoměrnosti v poptávce.
Kompletace zboží - sdružování objednávek od více zákazníků, které jsou pak předávány dodavatelům, kteří je dále dodávají objednateli, ten je kompletuje a dodává zákazníkům. Výsledným efektem kompletace zboží je snížení přepravních nákladů.
Manipulační - nakládkové, vykládkové a jiné manipulace s distribuovaným zbožím.
Přepravní - přemístění zboží z místa výroby do místa spotřeby.
Komunikační - výměna informací potřebných pro uskutečnění distribučního procesu.4
1.2.2 Distribuční řetězec společnosti REDDO CZ, s. r. o. Obrázek č. 2 - Distribuční řetězec REDDO CZ, s. r. o.
Zdroj: vlastní zpracování Distribuční řetězec společnosti REDDO CZ, s. r. o. si můžeme představit podle obrázku č. 2. Společnost spolupracuje s několika dodavateli a tzv. partnery. Partneři jsou rozmístěni podle regionů (Hranice, Olomouc, Zlín..). Aby si společnost REDDO CZ, s. r. o. udržela důvěru u jejich partnerů, vytváří jim katalogy, webové stránky, e-shopy. 4
ČUJAN, Zdeněk a Zdeněk MÁLEK. Výrobní a obchodní logistika. první. Zlín : Univerzita Tomáše Bati ve Zlíně, 2008. 200 s. ISBN 978 -80-7318-730-9.
11
Protože jsou to menší firmy, neměly by na zaplacení takovýchto forem podpory prodeje a proto jsou jim partneři věrní.
1.2.2.1
Princip fungování distribučního řetězce společnosti REDDO CZ, s. r. o.
1. Objednávka u společnosti REDDO CZ, s. r. o. 2. Společnost objedná zboží u svého dodavatele a dodavatel přímo dopraví zboží partnerovi do prodejny nebo 3. Dodavatel dopraví zboží do skladu společnosti REDDO CZ, s. r. o. odkud se pak objednávky kompletují k zákazníkům.
1.2.3 Rozsah distribučního řetězce označuje:
Délku,
kterou
rozumíme
počet
distribučních
stupňů
mezi
výrobcem
a zákazníkem.
Rozsah, který se měří počtem účastníků, kteří se na distribuci na daném stupni podílejí.5
1.2.4 Druhy distribuce podle rozsahu
Extenzivní distribuce, kdy je zboží dodáváno do všech prodejen v daném úseku, nebo všech prodejnách několika typů, nebo všech prodejnách jednoho typu, nebo všech prodejnách v dané lokalitě.
Společnost REDDO CZ, s. r. o. využívá extenzivní distribuci, protože zboží dodává odlišným odběratelům, jako jsou různé firmy, prodejny, školy, pro osobní účely běžného odběratele..
Výběrová distribuce, kdy si distributor vybírá jen několik prodejen. Distribuuje výrobky, kde je potřeba vysoce kvalifikovaného prodavače.
Exkluzivní distribuce, která vyžaduje obvykle jen jeden obchod, z důvodu velmi komplikovaného servisu.
5
Distribuční logistika [online]. VSB, 25.4.2011 [cit. 2012-04-03]. Dostupné z: http://www.id.vsb.cz/sliva/zl/Zaklady%20logistiky_3.pdf. Bakalářská práce. Vysoká škola Báňská.
12
1.2.5 Rozdělení distribuce podle počtu stupňů Počet stupňů distribučního řetězce, označovaný též jako délka řetězce je počet úrovní, kterými výrobek prochází od výrobce ke konečnému spotřebiteli. Podle počtu stupňů lze rozlišit přímou, nepřímou a kombinovanou distribucí.
Přímá – existuje pouze jeden distribuční stupeň, kdy výrobce dodává zboží přímo konečnému zákazníkovi (při zavádění nového výrobku na trh).
Nepřímá – zboží se dostává k zákazníkovi přes několik stupňů,6 kterou využívá společnost REDDO CZ, s. r. o.
Kombinovaná – kombinace přímé a nepřímé distribuce.
1.3 Doprava jako součást logistického systému ,,Doprava je jakékoliv přemístění osob či hmotných statků provedené buď vlastní silou, nebo silou zprostředkovanou.“ Je však důležité dodat, že z hlediska ekonomického tedy i z hlediska logistiky nejde o jakékoliv přemístění, ale o přemístění, jehož účinky se projevují v systému, ve kterém působí doprava. Z tohoto pojetí lze dopravu charakterizovat jako: ,,Specifickou lidskou činnost, jíž se provádí cílevědomé přemístění osob a hmotných statků, které se svými (nehmotnými) efekty projevuje ve sledovaném systému.“ 7 V logistice je doprava nositelem hmotného toku. I když se různé logistické technologie snaží do určité míry odstraňovat hmotné toky, nakonec vždy zůstane rozpor mezi místem existence vyrobeného hmotného statku a místem jeho spotřeby. Tento rozpor překonává doprava. Doprava především plní potřeby přemístění v logistickém systému. Fáze dopravy, které působí v logistickém systému rozlišujeme na dopravu:
Mezioperační - prováděna na velmi krátkou vzdálenost, často v rámci jednoho závodu.
Technologickou – mezi jednotlivými fázemi výroby, často značné přepravní vzdálenosti.
6
VANĚČEK, Drahoš. Logistika. Jihočeská univerzita v Českých Budějovicích Ekonomická fakulta: ediční středisko : JČU, 2008, s. 16. ISBN 978-80-7394-085-0. 7
SVOBODA, Vladimír. Doprava jako součást logistických systémů. Vyd. 1. Praha : Vydavatelství ČVUT, 2004. 152 s. ISBN 80-01-02914-X.
13
Oběhovou – realizuje se v momentě dokončení finálního výrobku v distribučních procesech.8
1.3.1 Dopravní sítě Existence dopravní sítě je základem dopravní obsluhy logistického systému. Dopravní síť umožňuje dosažení přemístění zboží z místa, kde bylo vyrobeno, do místa kde pokračuje jako součást procesu výroby a dále přes velkoobchod a maloobchod ke konečnému spotřebiteli, včetně likvidace odpadů. Z hlediska technické konstrukce dopravních sítí a tomu odpovídající technické konstrukce dopravních prostředků rozlišujeme:
silniční dopravu – nejhustší dopravní síť
železniční dopravu
vnitrozemskou vodní dopravu
leteckou dopravu
námořní dopravu námořní.
potrubní dopravu9
Dopravní síť je definována jako ,,konečná množina dopravních uzlů a cest, které tyto uzly spojují. Ty posléze tvoří pevnou, nepřemístitelnou část dopravní soustavy, označovanou pojmem dopravní infrastruktura.“ 9 Po formální stránce můžeme dopravní síť zobrazit jako ,,rovinný síťový graf, definovaný množinou uzlů (U), množinou hran (H), které jsou ohodnoceny směrovou orientací, délkou hrany (d) propustností buď sítě jako celku, jednotlivých cest v síti nebo prvků (p).“ 10
8
SVOBODA, Vladimír. Dopravní logistika. Praha: ČVUT 2004. ISBN 80-01-02914-X.
9
SVOBODA, Vladimír. Doprava jako součást logistických systémů. Vyd. 1. Praha : Vydavatelství ČVUT, 2004. 152 s. ISBN 80-01-02914-X. 10
SVOBODA, Vladimír. Doprava jako součást logistických systémů. Vyd. 1. Praha : Vydavatelství ČVUT, 2004. 152 s. ISBN 80-01-02914-X.
14
1.4 Teorie grafů (TG) TG se zabývá studiem matematických útvarů, které nazýváme grafy. Graf je základním objektem TG. ,,Z hlediska TG je graf matematická struktura sloužící především k vyjádření (modelování) té skutečnosti, že mezi prvky nějaké množiny V existují určité vazby z množiny H. Prvkům množiny V říkáme uzly nebo vrcholy grafů a vazbám (symetrickým nebo nesymetrickým) mezi některými (nebo všemi) z těchto uzlů říkáme hrany grafu. Označíme-li množinu všech uzlů grafu písmenem V a množinu všech existujících hran H, můžeme graf definovat jako uspořádanou dvojici (V, H).“11 Grafy slouží jako abstrakce mnoha různých problémů. Často se jedná o zjednodušený model nějaké skutečné sítě (například dopravní), který zdůrazňuje topologické vlastnosti objektů (vrcholů) a zanedbává geometrické vlastnosti, například přesnou polohu.11
1.4.1 Základní pojmy teorie grafů Obrázek č. 3 - Základní pojmy teorie grafů
Zdroj: 12
11
12
ŠEDA, Miloš. Teorie grafů. Brno: Radix, spol. s. r. o., 2003. ISBN 80-963035-64-3. Teorie grafů. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikipedia
Foundation, 2001- [cit. 2012-02-28]. Dostupné z: http://cs.wikipedia.org/wiki/Graf_%28teorie_graf%C5%AF%29
15
1.4.1.1
Orientovaná hrana
Uspořádaná dvojice uzlů (x0, x1), neboli orientované topologické spojení mezi dvěma uzly skládající se z hrany a směru.
1.4.1.2
Neorientovaná hrana
Neuspořádaná dvojice uzlů, neboli hrana, která umožňuje obousměrný pohyb.
1.4.1.3
Cyklus (kružnice)
V teorii grafů se termínem kružnice označuje takový graf, který se skládá z jediného cyklu, tedy uzavřené posloupnosti propojených vrcholů. Kružnice může být orientovaná i neorientovaná. Nejkratší kružnicí je trojúhelník - úplný graf se třemi vrcholy.
1.4.1.4
Acyklický graf
Graf, který neobsahuje cyklus.13
Obrázek č. 4 - Nejkratší kružnice (trojúhelník)
Zdroj: 14
13
PERKNER, Radim. Teorie grafů. Praha, 1999. Skripta. ČVUT Praha, fakulta dopravní.
16
Obrázek č. 5 - Kružnice (cyklus) v obecném grafu
Zdroj: 14
1.4.1.5
Neorientovaný graf
Neorientovaný graf (z pohledu teorie grafů) definujme jako dvojici G = (V, H). Kde:
V = {u1, u2, . . . , un} je konečná množina objektu, kterým říkáme vrcholy, někdy též uzly grafu;
H = {ui, uj , i, j = 1, 2, . . . , n} je množina některých dvojic uzlu, kterým říkáme hrany grafu. Pokud vede hrana z vrcholu A do vrcholu B, vede hrana také z B do A (nerozlišuje se směr hrany).
Obrázek č. 6 - Příklad neorientovaného uzlového grafu – matice sousednosti
1 2Zdroj: 14 14
Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teoriegrafu.cz/zakladni-pojmy/kruznice-cyklus.php
17
1.4.1.6
Orientovaný graf
Orientovaný graf G je dvojice (V, H), kde H je podmnožina kartézského součinu V × V. Prvky H nazýváme šipky nebo orientované hrany. Orientovaná hrana e má tvar (x, y). Říkáme, že tato orientovaná hrana vychází z x a končí v y. Orientovaný graf využijeme u silniční sítě např. v jednosměrné silnici. V takových případech hrana vede pouze jedním směrem. Z takových důvodů zavádíme pojem orientovaný graf.15
Obrázek č. 7 - Příklad orientovaného grafu
Zdroj: 16 1.4.1.7
Souvislost grafu
Použijeme pokud potřebujeme vyjádřit, jestli je nebo není graf "jedním celkem" tj. můžeme-li se dostat z každého vrcholu nějakou cestou do jiného, nebo zda jde o více na sebe nenavazujících částí. Proto se zavádí pojem souvislost grafu. V této práci je využit souvislý graf, neboť se můžeme dostat z jakéhokoliv místa do místa jiného.
a) Souvislý graf Graf G je souvislý, jestliže pro každé jeho dva vrcholy x a y existuje v G cesta z x do y.
15
PERKNER, Radim. Teorie grafů. Praha, 1999. Skripta. ČVUT Praha, fakulta dopravní. Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teoriegrafu.cz/zakladni-pojmy/orientovane-grafy.php 16
18
Neboli graf je souvislý jestliže se můžeme dostat z každého vrcholu nějakou cestou do jiného vrcholu. Obrázek č. 8 - Souvislý graf
Zdroj: 18
b) Nesouvislý graf Nesouvislý graf se vyznačuje vícero na sebe nenavazujících částí. Pokud graf není souvislý, části, ze kterých se skládá a které jsou samy o sobě souvislé se nazývají komponenty souvislosti. Na obr. č. 9 jsou komponentami dva trojúhelníky.17
Obrázek č. 9 - Nesouvislý graf
Zdroj: 18 17
PERKNER, Radim. Teorie grafů. Praha, 1999. Skripta. ČVUT Praha, fakulta dopravní.
19
1.5 Lineární programování ,,Lineární programování je soubor metod umožňující výběr optimální varianty při daném kritériu optimality a daných omezujících podmínkách.“19 Využívá se tam, kde přesné řešení úloh z praxe by systematickým prohledáváním trvalo téměř nekonečně dlouho.19 Umožňuje tak řešit snadno složité problémy.
1.5.1 Distribuční metody lineárního programování Distribuční úlohy patři mezi důležité aplikace úloh lineárního programování. Při řešeni těchto úloh se používají odlišné metody než při řešeni typických úloh lineárního programování. Hlavním cílem lineárního programování je minimalizovat celkové náklady na distribuci. Účelová funkce, jež se minimalizuje, je celková délka trasy ujetá mezi městy. Tato distribuční úloha odpovídá postupu řešení obchodního cestujícího. Další z typů distribučních úloh je problematika okružních cest. Zde se uvažují i kapacity jednotlivých dodavatelů, odběratelů a distribučních kanálů.20 Dopravní úloha byla jedním z prvních problémů, při jejichž řešení bylo úspěšně použito metod lineárního programování. Hlavní rolí dopravního problému obvykle představuje úkol přepravit určitý druh zboží od dodavatelů přímo k odběratelům za co nejnižší cenu nebo po nejkratší cestě.21
1.6 Matematické modelování dopravních cest
1.6.1 Okružní dopravní problém V praxi dodavatelé často řeší situaci jak co nejúsporněji dodat požadovaný objem zboží k odběratelům. V tomto případě však nejde o klasickou podobu dopravní úlohy, kdy 18
Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teoriegrafu.cz/zakladni-pojmy/cesta-a-souvislost-grafu.php 19
ŠEDA, Miloš. Teorie grafů. Brno: Radix, spol. s. r. o., 2003. ISBN 80-963035-64-3.
20
Algoritmus [online]. 28.9.2010 [cit.2012-04-04]. Dostupné z WWW: http//www.algoritmy.net/article/5407/Obchodni- cestujici. 21
The Traveling Salesman Problem [online]. 2005 [cit.2009-06-04]. Dostupne z:
.
20
odběratelé mohou byt zásobováni z několika míst (výrobců, míst). U okružního problému je dodávka zboží (služby) organizována tak, aby zboží bylo rozvezeno všem odběratelům v rámci jedné jízdy, která začíná a konči ve stejném místě. V průběhu této jízdy musí byt všichni odběratelé navštíveni právě jedenkrát. Cílem je uspořádat cestu (pořadí navštívených míst) tak, aby náročnost dopravy byla minimální. Minimalizovat je možné například délku trasy, spotřebu času či pohonných hmot. Typickou ukázkou je problém obchodního cestujícího, který chce naplánovat návštěvu jednotlivých zákazníků tak, aby v rámci své cesty ujel co nejkratší vzdálenost.22
1.6.1.1
Historie okružního dopravního problému
První, kdo řešil okružní problém byl roku 1800 irský matematik William Rowan Hamilton. Tento matematicky problém představil na hádance Hamiltonova cyklu. Úkolem bylo projít neorientovaným Hamiltonovým cyklem tak, aby všechny vrcholy cyklu byly navštíveny jen jednou a poslední vrchol cyklu navázal na počáteční vrchol. Samotný okružní problém poprvé uvedl v roce 1930 rakouský matematik Karl Menger, který jej označil jako tzv. „Botenproblem“, což znamená v překladu „problém posla“ nebo také „problém listonoše“. Nejznámější název „travelling sallesman problem“. V češtině „problém obchodního cestujícího“ byl poprvé použit na Princetonské univerzitě v roce 1940 americkým matematikem Merrillem Floodem, který společně s jeho kolegou Hesslerem Whitneyem řešil problém obslužnosti školního autobusu v Západni Virginii. Po Karlu Mengerovi a Merrillovi Floodovi se problémem zabývalo mnoho matematiků, kteří postupně řešili úlohy pro větši počet míst. Velmi výrazně se na řešeni okružního problému podíleli G. Dantzing, R. Fulkeson a S. Jonhnson. Právě oni vydali popis metody pro řešeni problému obchodního cestujícího a vyřešili přiklad s 49 městy v efektivním čase. Milníkem co do počtu vyřešených instanci se ovšem stal exaktní řešitel Concorde. Tento program je v současné době schopen vyřešit úlohu s 85 900 městy. Jeho autory jsou D. Applegate, R. Bixby, W. Cook a český vědec Václav Chvátal. 23
22
The Traveling Salesman Problem [online]. 2005 [cit.2009-06-04]. Dostupne z: . 23
The Traveling Salesman Problem [online]. 2005 [cit.2009-06-04]. Dostupne z: .
21
1.6.2 Obchodní cestující TSP (Travelling salesman problem) TSP je úloha kombinatorické optimalizace, jejíž cílem je nalézt v zadaném ohodnoceném úplném grafu takovou kružnici, která prochází všemi vrcholy a zároveň je její cena minimální. Může být modelována jako graf. Jinými slovy TSP se týká úloh okružních. Jedná se o nejjednodušší verzi okružních úloh, jejímž cílem je navštívit všechny zákazníky, a to právě alespoň jednou, při tom však obchodník neřeší požadavky těchto zákazníků. Vyjádříme-li tuto úlohu grafem, pak uzly v něm představují výchozí místo a místa, která má obchodní cestující navštívit.24 V grafu jsou každé dva uzly spojeny hranou, která je ohodnocena určitou vzdáleností, která je potřebná urazit, abychom se dostali z místa představující jeden z uzlů do místa, který představuje další uzel.
Obrázek č. 10 - Problém obchodního cestujícího - zadání
Zdroj: 25
24
DVOŘÁK, Petr a Markéta ŠMEJKALOVÁ. Řešení problému obchodního cestujícího s využitím evolučních přístupů. P a M [online]. [cit. 2012-04-06]. Dostupné z: http://www.epame.cz/epame/index.php?option=com_content&view=article&id=3&Itemid=13&lang=cs 25
Problém obchodního cestujícího (TSP). Problém obchodního cestujícího [online]. 25.3.2009 [cit. 201204-04]. Dostupné z: http://www.cs.vsb.cz/kot/anim/a-tsp_approx.pdf
22
Obrázek č. 11 - Problém obchodního cestujícího - cesta
Zdroj: 26
Stejně tak i jinými slovy se jedná o nalezení nejkratší hamiltonovské kružnice v ohodnoceném grafu. V takovéto úloze, s minimálně však třemi uzly, lze vždy snadno najít hamiltonovskou kružnici. Cílem je však najít tu hamiltonovskou kružnici, jejíž délka, která je vyjádřena součtem ohodnocení hran na této kružnici, je nejmenší ze všech hamiltonovských kružnic v grafu. Taková hamiltonovská kružnice je zároveň nejkratší trasou pro úlohu TSP a je tímto tedy jejím řešením. Matematickým modelem těchto úloh je graf G = (V,H), kde:
V = {v1, ..., vn} je množina vrcholů (nebo uzlů)
H = {(vi, vj)|vi, vj Є V, i ≠ j} je množina hran s nezápornými náklady (vzdálenostmi) reprezentované maticí C = (cij).27
1.6.2.1
Hamiltonovská kružnice (cesta)
Problém nalezení hamiltonovské kružnice je definován takto: nechť G je orientovaný graf s označeným počátečním uzlem A a koncovým B. Cesta z uzlu A do B se nazývá hamiltonovská právě tehdy, když obsahuje každý uzel grafu G právě jednou. Počet kroků potřebných na vyřešení problému roste exponenciálně s velikostí grafu. 26
Problém obchodního cestujícího (TSP). Problém obchodního cestujícího [online]. 25.3.2009 [cit. 201204-04]. Dostupné z: http://www.cs.vsb.cz/kot/anim/a-tsp_approx.pdf 27
Uni-protokolle: Hamiltonian [online]. 2009 [cit. 2012-04-11]. Dostupné z: www.uni-protokole.de
23
Neboli jinými slovy hamiltonovská kružnice je uzavřená cesta, která prochází všemi uzly grafu právě jednou. Někdy je tato kružnice nazývána hamiltonovskou cestou. Obecně je problém nalezení hamiltonovské kružnice formulován jako rozhodnutí, zda daný orientovaný graf hamiltonovskou cestu obsahuje či ne.28
Obrázek č. 12 - Hamiltonovská kružnice
Zdroj: 29
1.6.3 Matematická definice TSP Úloha obchodního cestujícího není založena pouze na teorii grafů, ale může být založena i na matematické formulaci. Úloha TSP může být vyjádřena následně. Obchodník chce na své cestě navštívit n různých měst a poté se vrátit do výchozího místa. Konečná ujetá vzdálenost přitom musí být současně minimální a každé navštívené město se musí vyskytovat právě jednou. Ačkoliv je tato definice zdánlivě velmi jednoduchá, o to obtížnější je získat optimální řešení. V n-městské situaci kterékoliv permutace n měst přináší možné řešení. V důsledku toho
n 1! možných cest (vzdálenost měst je zadaná jako symetrická matice; V grafickém 2
podání se jedná o neorientovaný graf) musí být ohodnoceno ve vyhledávacím prostoru. Následující tabulka udává příklady počtů prozkoumávaných cest v závislosti na počtu 28
DELMLOVÁ, Marie. Diskrétní matematika a logika. Praha, 2010. Dostupné z: http://math.feld.cvut.cz/demlova/teaching/dmc/pred100.pdf 29
Hamiltonian path [online] Dostupné z: http://en.wikipedia.org/wiki/Hamiltonian_cycle
24
měst. Jak lze v tabulce č. 1 vidět, počet možných cest je extrémní už jen při počtu 30 měst. 30
Tabulka č. 1 - Počet cest v závislosti na počtu měst
npočet
Počet prozkoumávaných cest
měst 3
1
5
12
7
360
10
181 440
15
43 589 145 600
20
60 822 550 204 416 000
25
310 224 200 866 620 000 000 000
30
4 420 880 996 869 850 000 000 000 000 000
35
147 616 399 519 802 000 000 000 000 000 000 000 000
Zdroj: 30 V matematickém modelu TSP se zavádějí, podobně jako u přiřazovacího problému, bivalentní proměnné tj:
xij, i = 0, 1,…,
m, j = 0, 1,…, m, jejichž hodnota 1 udává, že hrana jdoucí z uzlu i do uzlu j leží v rámci hledané cesty obchodního cestujícího a naopak hodnota xij se rovná 0 znamená, že mezi těmito místy cesta nebude. TSP může byt tedy formulován naprosto stejně jako přiřazovací problém. Navíc je v něm však třeba zajistit, aby byl nalezen skutečně pravě jeden okruh zahrnující všechna místa a ne třeba jen několik dílčích, vzájemně nezávislých okruhů.
Definujeme:
Náklady na přepravu od dodavatele k odběrateli (cij...kde i = 1 …m, j = 1 …n)
30
JAN, Fábry. Dynamic Traveling Salesman Problem: In Mathematical Methods in Economics. Plzeň: Professional Publishing, 2006. ISBN 80-86419-23-1.
25
Objem přepravy od dodavatele k odběrateli xij …kde i = 1…m, j = 1…n)
Účelová funkce (z..celkové náklady – všechny požadavky)
Při řešení dopravního problému se snažíme minimalizovat funkci celkových nákladů na přepravu (viz vzorec č. 1).
Vzorec č. 1 n
Minimalizuj
n
c
ij
xij
i 1 j 1
Tento vztah platí při třech podmínkách: Tabulka č. 2 – tři podmínky, které platí pro vzorec č. 1 n
x ij 1
j 1
i 1 , 2 ,... n
1
j 1,2,...n
2
n
x
ij
1
i 1
S i cij (1 xi , j ) * M s j i 1,2,...n j 1,2,...n
xij 0,1
i , j 1 , 2 ,.... n
3
4
Zdroj: 31 kde : n = počet míst jež chceme navštívit (výchozí místo je označeno č.1). cij = vzdálenost mezi místem i a místem j (i,j = 1,2,...,n).32 31
JAN, Fábry. Dynamic Traveling Salesman Problem: In Mathematical Methods in Economics. Plzeň: Professional Publishing, 2006. ISBN 80-86419-23-1.
32
FÁBRY, Jan. Dynamic Traveling Salesman Problem: In Mathematical Methods in Economics. Plzeň:
26
První dvě podmínky zajišťují, aby každý uzel byl navštíven právě jednou.
Třetí podmínka zajišťuje nedělitelnost Hamiltonovi kružnice, kterou musejí všechna místa procházet.
K zabezpečení toho, aby cesta obsahovala spojení vycházející a jdoucí zpět do tohoto samého místa, musí řešení obsahovat xii = 0 pro všechna i. Dosáhneme to tím, že nastavíme vzdálenost cii na velmi velkou hodnotu pro všechna i. Ohodnocení hledaného cyklu získáme součtem ocenění hran tvořící cyklus, tedy hran, pro které je xij = 1. Hledáme minimální cyklus a proto minimalizujeme toto ohodnocení. Tato minimalizační funkce je pak zapsána jako vzorec č. 1. Podmínka která zaručuje, že každý uzel leží na Hamiltonově cyklu, tedy že každé místo je navštíveno pravě jednou, znamená, že právě jedna hrana tvořící cyklus končí v tomto uzlu a právě jedna hrana tvořící cyklus z tohoto uzlu vychází. Tyto podmínky lze zapsat ve tvaru 1. a 2. vzorce v tabulce č. 2. Smyčkové podmínky, (zde v podobě 3. vzorce v tabulce č. 2) mají zajistit, aby výsledné řešení neobsahovalo parciální cykly. Bez takových to podmínek by formulace problému dovolila odpojení parciálních cyklů. Obrázek č. 13 a 14 ilustruje takovýto příklad cyklu a parciálního cyklu.32
Obrázek č. 13 - Cyklus
Zdroj: Vlastní zpracování
Professional Publishing, 2006. ISBN 80-86419-23-1.
27
Obrázek č. 14 - Parciální cyklus
Zdroj: Vlastní zpracování
1.6.4 Shrnutí problému TSP TSP je klasická optimalizační úloha, kdy se snažíme najít cyklickou cestu mezi skupinou měst tak, aby celková délka okružní trasy byla minimální. Tato úloha se anglicky nazývá Traveling Salesman Problem (TSP), někdy též okružní problém nebo také problém listonoše. Jedná se o velmi složitý problém, pro jehož řešení při větším počtu měst neexistují dostatečně výkonné postupy.
1.7 Využití informačních technologií Řešení úloh lineárního programování lze řešit pomocí méně i více výkonných softwarů, které jsou schopné řešit optimalizační úlohy obsahující tisíce i desetitisíce proměnných. Cena softwaru se odvíjí samozřejmě od jeho celkové výkonnosti. Lze jej pořídit za desítky tisíc USD, ale také jej můžeme sehnat zdarma na internetových stránkách společností, které se těmito softwary zabývají. Pro řešení menších a jednodušších optimalizačních úloh není třeba pořizovat softwary za desetitisíce USD. Pro běžné uživatele lze využít práci s tabulkovým kalkulátorem MS Excel, který má uživatel k dispozici na svém počítači a která byla použita i v této práci. Počet možných řešení velmi roste s počtem obsluhovaných uzlů. Zmíněné metody zanedbávají důležité vstupy jako je např. kapacita dopravního prostředku, kapacita dopravní sítě, pracovní doba řidičů a další. Z toho důvodu dochází k vývoji těchto softwarových produktů, které si kladou za cíl zdokonalit a zjednodušit plánování tras.
28
Příkladem takového produktu je systém Plantour Logistic vyvinutý společností Digitech ČR.
1.7.1 Systém Plantour Logistic Tento systém se úspěšně uvedl na evropském softwarovém trhu jako nástroj pro řešení dopravní obsluhy logistických systémů v oblasti distribučních procesů. Řeší zejména:
Přiřazení objednávek vozidlům disponibilního vozového parku.
Výběr optimální trasy okružní jízdy vzhledem ke zvolenému kritériu.
Zohledňuje omezení při plánování, např. pracovní dobu řidičů vozidel nebo kapacitu prostředku.
Ukládá data pro evidenci a statistiku.
Provádí zpětné analýzy nároků na přepravu vzhledem k plánu dopravní obsluhy ve stanoveném období. 33
Dalšími nejrozšířenějšími systémy na podporu modelování dopravních tras jsou v současné době programy STORM, LINGO, LINDO a MPL for Windows.
33
Plantour logistic. Sysklass cz [online]. [cit. 2012-04-06]. Dostupné z: http://www.sysklass.cz/index.php?t=article&n=clanek-plantour-logistic-49
29
2 Společnost REDDO CZ, s. r. o. Společnost REDDO CZ, s. r. o. působí na českém trhu od roku 2007 jako dodavatel poskytující svým zákazníkům a partnerům komplexní servis v oblasti papíru a kancelářských potřeb, reklamního a tiskového servisu. Podílí se na průběhu celé zakázky od objednávky až po expedici zboží. Zaměstnanci společnosti REDDA CZ, s. r. o. pracují v týmu, a proto jsou schopni vyprodukovat kvalitní zboží i služby. Zákazníkům nabízí kancelářský sortiment, který obsahuje více než 3500 položek, bohatý výběr značek a typů produktů od papíru, archivace, psacích potřeb, cartridge & tonery, prezentační a kancelářské techniky až po obaly a hygienické potřeby.
Podnik sídlí v Lipníku nad Bečvou a pracuje zde 11 zaměstnanců. Je rozdělen na tři úseky: Management, obchodní oddělení, sklad a expedice.
Oddělení managementu se orientuje na řízení celého podniku.
Obchodní oddělení provádí průzkum trhu, zabezpečuje záležitosti spojené s propagací výrobků a uzavírá kontrakty a hospodářské smlouvy s obchodními partnery atd.
Sklad a expedice řídí činnost skladů, organizuje balení, skladování a přípravu k distribuci.
Podnik má zájem maximalizovat zisk, a proto je doprava jednou z oblasti, u které usiluje o snižování nákladů. V důsledku růstu cen paliva, zvyšováni plateb za silnice a požadavků odběratelů stale více narůstají právě tyto náklady na dopravu
2.1 Charakteristika získaných dat Celá problematika dopravy společnost REDDO CZ, s. r. o. byla konzultována s jednatelem společnosti. Doprava je realizována od pondělí do pátku podle přesně stanoveného rozvozového plánu (viz. tab. č. 3) na území celé střední Moravy (Přerov, Olomouc, Vsetín, Kroměříž, Hranice, Valašské Meziříčí..).
30
Tabulka č. 3 - Rozvozový plán
Rozvozový plán
TRASA A Pondělí
Směr: Lipník nad Bečvou, Hranice, Valašské Meziříčí, Nový Jičín, Rožnov pod Radhoštěm, Vsetín, Bystřice pod Hostýnem
TRASA B Úterý
Směr: Přerov, Olomouc, Prostějov, Kroměříž, Holešov, Zlín
TRASA A Středa
Lipník nad Bečvou, Hranice, Valašské Meziříčí, Nový Jičín, Rožnov pod Radhoštěm, Vsetín, Bystřice pod Hostýnem
TRASA B Čtvrtek
Směr: Přerov, Olomouc, Prostějov, Kroměříž, Holešov, Zlín
TRASA A Pátek
Lipník nad Bečvou, Hranice, Valašské Meziříčí, Nový Jičín, Rožnov pod Radhoštěm, Vsetín, Bystřice pod Hostýnem
Zdroj: vlastní zpracování
2.1.1 Vozový park Vozový park společnosti tvoří 3 vlastní vozidla (viz. tab. č. 4). Kromě níže uvedených vozidel firma využívá i externí dopravu pro větší zásilky nebo pro kusové zásilky mimo střední Moravu (PPL).
31
Tabulka č. 4 - Přehled vozidel Název vozidla
Nosnost
Citroën Jumper
1,5 t
Volkswagen Caddy Citroën C2
Spotřeba
Rok výroby
Palivo
10,5
2008
Benzin
600-650 kg
6
2006
Diesel
300-350 kg
6,5
2008
Benzin
(l/100 km)
Zdroj: Vlastní zpracování
2.1.2 Využití vozidel Využití vozidel je individuální podle množství přepravovaného zboží k jednotlivým odběratelům. Společnost REDDO CZ, s. r. o. nemá přesně stanovené dny, kdy se využívá konkrétní vozidlo. Řidiči vyjíždějí vždy jedenkrát denně a to vždy v 8:30 hod. Před samotným rozvozem dochází k vystavení objednávek dodavatelům a vystavování dokladů do skladu k expedici. Společnost má přesně stanovené časové zámky a uzávěrky.
2.2 Časové zámky a uzávěrky a) Vystavování objednávek dodavatelům
Nastavení časové uzávěrky - zaslání objednávky dodavatelům nejpozději do 11 hod (pro rychlejší logistiku od dodavatelů). Hlavní dodavatelé jsou schopni zboží dodat na 2. den při objednávce do výše uvedeného času. Tohle nastavení se týká především objednávek velkoobchodního sortimentu. Pokud přijdou objednávky od zákazníků po 11 hod, tak se automaticky vydané objednávky přesouvají na následující pracovní den do 11 hod. b) Vystavování dokladů do skladu k expedici
Nastavení časové uzávěrky předávání dokladů (dodacích listů, výdejek, vydaných faktur) nejpozději do 13:30 hod do skladu.
Vždy do 15:30 hod je ve skladu nachystáno zboží pro rozvoz následující den ve vychystávajícím prostoru včetně konečných dokladů.
32
V době od 7:30 – 8:15 hod bude probíhat nakládka zboží (účastní se řidič společně se skladníkem).
Od 8:30 hod probíhá rozvoz zboží zákazníkům dle rozvozového plánu.
33
3 Optimalizace tras metodou obchodního cestujícího 3.1 Zadání Metodou sestavy okružní trasy vypočíst celkovou délku okružní trasy tak, aby tato trasa byla minimální (řešit problém obchodního cestujícího). Je dáno celkem 13 měst ve kterých sídlí odběratelé společnosti REDDO CZ, s. r. o. Jsou vytvořeny dvě neoptimalizované trasy A, B, které v současné době společnost využívá. viz. tab. č. 5 a č. 6.
Tabulka č. 5 – Neoptimalizovaná (intuitivní) trasa A Pořadí
Název města
1A
Lipník nad Bečvou
2B
Hranice
3C
Valašské Meziříčí
4D
Nový Jičín
5E
Rožnov pod Radhoštěm
6F
Vsetín
7G
Bystřice pod Hostýnem
Celková délka neoptimalizované trasy A je 162 km.
34
Obrázek č. 15 - Mapa neoptimalizované trasy A
Zdroj: 34
Tabulka č. 6 – Neoptimalizovaná (intuitivní) trasa B Pořadí
Název města
1A
Přerov
2B
Olomouc
3C
Prostějov
4D
Kroměříž
5E
Holešov
6F
Zlín
7G
Lipník nad Bečvou
Zdroj: Vlastní zpracování Celková délka neoptimalizované trasy B je 183 km.
34
www.maps.google.cz
35
Obrázek č. 16 - Mapa neoptimalizované trasy B
Zdroj: 30
3.2 Ruční výpočet optimální trasy A a) Jsou vytvořeny kilometrické vzdáleností mezi městy (matice vzdáleností). Tabulka č. 7 – Kilometrické vzdálenosti mezi městy (matice vzdáleností) 1 Město Lipník 1 2
n/B. Hranice Val.
3
Meziříčí Nový
4
Jičín Rožnov
5 6
p/R. Vsetín Bystřice
7
p/H.
Lipník n/B.
2 Hranice
3
4
5
Val.
Nový
Rožnov
Meziříčí
Jičín
p/R.
6 Vsetín
7 Bystřice p/H.
-
12,2
35,9
42,6
47,7
52,9
20,7
12,2
-
24,3
26
36
42,2
19,5
35,9
24,3
-
18
14,7
19,2
26,7
42,6
26
18
-
29,7
35,9
44,7
47,7
36
14,7
29,7
-
27,5
40,4
52,9
42,2
19,2
35,9
27,5
-
32,2
20,7
19,5
26,7
44,7
40,4
32,2
-
36
Tabulka byla vytvořena v MS Excel s pomocí www.maps.google.cz.
Pro všechna místa uvažované okružní cesty jsou sečteny vzdálenosti do všech ostatních míst (součet sloupců), viz tab. č. 7.
Jsou vybrána tři místa s největšími součtovými vzdálenostmi, které vytvoří základní okružní trasu. Základní okružní trasa je tvořena městy: 1 – 6 – 4 – 1 (Lipník nad Bečvou, Vsetín, Nový Jičín, Lipník nad Bečvou). Délka trasy je: 52,9 + 42,6 + 35,9 = 131,4 km).
Ze zbývajících míst, nezahrnutých do základní okružní trasy jsou postupně vybrána ta místa, která mají v pořadí další nejvyšší součty vzdáleností. Tato místa jsou zapojována do okružní trasy tak, aby přírůstek délky této trasy byl co nejmenší.
Přírůstek vzdálenosti vzniklý zapojením místa „k“ mezi místa „i“ a „j“: Lpř ij = Lik + Lkj - Lij kde: Lik
- vzdálenost z místa i do místa k
Lkj – vzdálenost z místa k do místa j Lij – vzdálenost z místa i do místa j Zapojení místa č. 5 (Rožnov pod Radhoštěm) v pořadí 4.
1 5
L15 + L56 - L16 = 47,7 + 27,5 + 52,9 = 22,3
5
L65 + L54 – L64 = 27,5 + 29,7 + 35,9 = 21,3 minimum, proto 5 mezi 4 a 6
5
L45 + L51 – L41 = 29,7 + 47,7 + 42,6 = 34,8
6
4
1
Výsledná trasa: 1 – 6 – 5 – 4 – 1 = 52,9 + 27,5 + 29,7 = 110,1 km
37
Zapojení místa č. 7 (Bystřice pod Hostýnem) v pořadí 5.
1 7
L17 + L76 – L16 = 20,7 + 32,2 – 52,9 = 0
minimum proto 7 mezi 1 a 6
7
L67 + L75 – L65 = 32,2 + 40,4 – 27,5 = 45,1
7
L57 + L74 – L54 = 40,4 + 44,7 – 29,7 = 55,4
7
L47 + L71 – L41 = 44,7 + 20,7 – 42,6 = 22,8
6
5
4
1
Výsledná trasa: 1 – 7 – 6 – 5 – 4 - 1= 20,7 + 32,2 + 27,5 + 29,7 = 110,1 km Zapojení místa č. 2 (Hranice) v pořadí 6.
1 2
L12 + L27 – L17 = 12,2 + 19,5 – 20,7 = 11
2
L72 + L26 – L76 = 19,5 + 42,2 – 32,2 = 29,5
2
L62 + L25 – L65 = 42,2 + 36 – 27,5 = 50,7
2
L52 + L24 – L54 = 36 + 26 - 29,7 = 32,3
2
L42 + L21 – L41 = 26 + 12,2 – 42,6 = -4,4 minimum proto 2 mezi 4 a 1
7
6
5
4
1
Výsledná trasa: 1 – 7 – 6 – 5 – 4 – 2 – 1 = 20,7 + 32,2 + 27,5 + 29,7 + 26 + 12,2 = 148,3 km
38
Zapojení místa č. 3 (Val. Meziříčí) v pořadí 7. 1 3
L13 +L37 - L17 = 35,9 + 26,7 – 20,7 = 41,9
3
L73 + L36 – L76 = 26,7 + 19,2 – 32,2 = 13,7
3
L63 + L35 – L65 = 19,2 + 14,7 – 27,5 = 6,4
3
L53 + L34 – L54 = 14,7 + 18 – 29,7 = 3 minimum proto 3 mezi 5 a 4
3
L43 + L32 – L42 = 18 + 24,3 – 26 = 16,3
3
L23 + L31 – L21 = 24,3 + 35,9 – 12,2 = 48
7
6
5
4
2
1
Výsledná (optimalizovaná) trasa: 1 – 7 – 6 – 5 – 3 – 4 – 2 – 1 = 20,7 + 32,2 + 27,5 + 14,7 + 18 + 26 + 12,2 = 151,3 km Optimalizovaná trasa je uvedena v tab. č. 8 a zobrazena na obr. č. 16.
Tabulka č. 8 – Optimalizovaná trasa A p.č.
název města
1
Lipník n/B.
7
Bystřice p/H.
6
Vsetín
5
Rožnov p/R.
3
Val. Meziříčí
4
Nový Jičín
2
Hranice
1
Lipník n/B.
Zdroj: Vlastní zpracování
39
Obrázek č. 17 - Mapa optimalizované trasy A
Zdroj: 30
Celková délka optimalizované trasy A je 151,3 km.
Celková délka neoptimalizované trasy A je 162 km.
Rozdíl po optimalizaci trasy je 10,7 km.
3.3 Ruční výpočet optimální trasy B a) Jsou vytvořeny kilometrické vzdáleností mezi městy (matice vzdáleností). Tabulka byla vytvořena v MS Excel s pomocí www.maps.google.cz.
40
Tabulka č. 9 - Kilometrické vzdálenosti mezi městy (matice vzdáleností) 1
2
3
4
5
6
7
Město
Přerov
Olomouc
Prostějov
Kroměříž
Holešov
Zlín
1
Přerov
-
24,3
27,5
24,6
20,7
40,6
15
2
Olomouc
24,3
-
20,5
74,3
43,6
63,4
31,5
3
Prostějov
27,5
20,5
-
36,5
51,6
67,5
50,3
4
Kroměříž
24,6
74,3
36,5
-
20
35,9
38,7
5
Holešov
20,7
43,6
51,6
20
-
18,3
31,2
6
Zlín
40,6
63,4
67,5
35,9
18,3
-
49
7
Lipník n/B.
15
31,5
50,3
38,7
31,2
49
-
Součet
152,7
257,6
253,9
230
185,4
274,7
215,7
Pořadí
7
2
3
4
6
1
5
Lipník n/B
Zdroj: Vlastní zpracování a) Pro všechna místa uvažované okružní cesty jsou sečteny vzdálenosti do všech ostatních míst (součet sloupců), viz tab. č. 9. b) Jsou vybrána tři místa s největšími součtovými vzdálenostmi, které vytvoří základní okružní trasu. Základní okružní trasa je tvořena městy: 6 – 2 – 3 – 6 (Lipník nad Bečvou, Vsetín, Nový Jičín, Lipník nad Bečvou). Délka trasy je: 52,9 + 42,6 + 35,9 = 131,4 km). c) Ze zbývajících míst, nezahrnutých do základní okružní trasy jsou postupně vybrána ta místa, která mají v pořadí další nejvyšší součty vzdáleností. Tato místa jsou zapojována do okružní trasy tak, aby přírůstek délky této trasy byl co nejmenší. Přírůstek vzdálenosti vzniklý zapojením místa „k“ mezi místa „i“ a „j“: Lpř ij = Lik + Lkj - Lij kde: Lik - vzdálenost z místa i do místa k: Lkj – vzdálenost z místa k do místa j Lij – vzdálenost z místa i do místa j
41
Zapojení místa č. 4 (Kroměříž) v pořadí 4.
6 4
L64 + L42 – L62 = 35,9 + 74,3 – 63,4 = 46,8
4
L24 + L43 – L23 = 74,3+ 36,5 – 20,5 = 90,3
4
L34 + L46 – L36 = 36,5 + 35,9 – 67,5 = 4,9 minimum proto 4 mezi 3 a 6
2
3
6
Výsledná trasa: 6 – 2 – 3 – 4 – 6 = 63,4 + 20,5 + 36,5 + 35,9 = 156,3 km Zapojení místa č. 7 (Lipník nad Bečvou) v pořadí 5.
6 7
L67 + L72 – L62 = 49 + 31,5 – 63,4 = 17,1 minimum proto 7 mezi 6 a 2
7
L27 + L73 – L23 = 31,5 + 50,3 – 20, 5 = 61,3
7
L37 + L74 – L34 = 50,3 + 38,7 – 36,5 = 52,5
7
L47 + L76 – L46 = 38,7 + 49 – 35,9 = 51,8
2
3
4
6
Výsledná trasa: 6 – 7 – 2 – 3 – 4 – 6 = 49 + 31,5 + 20,5 + 36,5 + 35,9 = 173,4 km Zapojení místa č. 5 (Holešov) v pořadí 6.
6 5
L65 + L57 – L67 = 18,3 + 31,2 – 49 = 0,5 minimum proto 5 mezi 6 a 7
5
L75 + L52 – L72 = 31,2 + 43,6 – 31,5 = 43,3
7
2
42
5
L25 + L53 – L23 = 43,6 + 51,6 – 20,5 = 74,7
5
L35 + L54 – L34 = 51,6 + 20 – 36,5 = 35,1
5
L45 + L56 – L46 = 20 + 18,3 – 35,9 = 2,4
3
4
6
Výsledná trasa: 6 – 5 – 7 – 2 – 3 – 4 – 6 = 18,3 + 31,2 + 31, 5 + 20,5 + 36,5 + 35,9 = 173,9 km Zapojení místa č. 1 (Přerov) v pořadí 7.
6 1
L61 + L15 – L65 = 40,6 + 20,7 – 18,3 = 43
1
L51 + L17 – L57 = 20,7 + 15 – 31,2 = 4,5 minimum proto 1 mezi 5 a 7
1
L71 + L12 – L72 = 15 + 24,3 – 31,5 = 7,8
1
L21 + L13 – L23 = 24,3 + 27,5 – 20,5 = 31,3
1
L31 + L14 – L34 = 27,5 + 24,6 – 36,5 = 15,6
1
L41 + L16 – L46 = 24,6 + 40,6 – 35,9 = 29,3
5
7
2
3
4
6 Výsledná trasa: 6 – 5 – 1 – 7 – 2 - 3 – 4 – 6 = 18,3 + 20,7 + 15 + 31,5 + 20,5 + 36,5 + 35,9 = 178,4 km 183 km Optimalizovaná trasa je uvedena v tab. č. 10 a zobrazena na obr. č. 18.
43
Tabulka č. 10 – Optimalizovaná trasa B p.č.
název města
0
Lipník nad Bečvou
2
Olomouc
3
Prostějov
4
Kroměříž
6
Zlín
5
Holešov
1
Přerov
7
Lipník nad Bečvou
Zdroj: Vlastní zpracování
Obrázek č. 18 - Mapa optimalizované trasy B
Zdroj: 30
Celková délka optimalizované trasy B je 178,4 km.
Celková délka neoptimalizované trasy B je 183 km.
Rozdíl po optimalizaci trasy je 4,6 km. 44
4 Zhodnocení výsledků Jak už bylo zmíněno, společnost REDDO CZ, s. r. o. má zvolené vlastní rozvozové trasy, které si nazývají trasami A a B. Tyto dvě trasy se střídají od pondělí do pátku. Pomocí maps.google.cz byla zjištěná celková okružní vzdálenost trasy A a to 162 km. Ručním výpočtem optimalizované trasy bylo zjištěno, že výsledek ukazuje pořadí měst v opačném směru, ale na celkové kilometry to nemá žádný vliv a také poukazuje na to, že tato trasa může být o 10,7 km kratší, tedy přesně 151,3 km, pokud se změní pořadí mezi dvěma městy a to mezi Valašským Meziříčím a Novým Jičínem. viz. tabulka č. 8. Stejně jako u trasy A, tak i u trasy B byla zjištěná celková okružní vzdálenost pomocí maps.google.cz, která činí 183 km. Ručním výpočtem optimalizované trasy bylo zjištěno, že tato trasa je po optimalizaci kratší o 4,6 km tedy celková optimalizovaná vzdálenost činí 178,4 km. Pořadí všech měst zůstává stejné až na 3 města (Zlín, Holešov, Přerov) (viz. tabulka č. 10). Ruční výpočet ověřil, že intuitivně využívané trasy se s malými odchylkami téměř shodují s optimalizovanou trasou. Délka tras závisí na konkrétních okolnostech např. zda se jedná o rozvoz zboží k více odběratelům v každém městě. Ve většině případů se jedná o rozvoz zboží k jednomu odběrateli do každého města. Dalším faktem, který ovlivňuje délku trasy je skutečnost, že vzdálenosti tras nebyly zjištěny podle skutečného měření, ale pomocí maps.google.cz.
Tabulka č. 11 - Vyhodnocení vzdáleností Původní
Optimální
vzdálenost
vzdálenost
(km)
(km)
A
162
151,3
10,7
B
183
178,4
4,6
Celkem
345
329,7
15,3
Trasa
Zdroj: Vlastní zpracování
45
Absolutní rozdíl (km)
Graf č. 1 - Vyhodnocení vzdáleností
200 180 160 140 120 km 100 80 60 40 20 0
Původní Zoptimalizovaná Rozdíl
A
B Trasa
4.1 Vyhodnocení času Dalším důležitým faktorem, který souvisí s optimalizací tras je úspora času. I když výsledná optimalizovaná trasa se příliš neliší od té původní (intuitivní), úspora času je velmi důležitá, i když se jedná jen o nepatrné rozdíly. A protože je doba ujeté trasy závislá nejen na kilometrické vzdálenosti, ale také na typu terénu, byla pro výpočet doby ujetí jednotlivých tras využita funkce plánovače tras,35který zohledňuje tyto terénní odchylky, avšak nezohledňuje další vlivy např. situace na silnicích, jejich opravy, počasí.. Do plánovače tras byla vložena místa všech zastávek, jak původních (intuitivních) tras, tak i optimalizovaných tras a byly sledovány jejich časy, které pak byly vzájemně porovnány. Výsledkem je, že u trasy A byla zjištěna úspora času 16 minut a u trasy B byla úspora času 32 minut. Jsou to rozdíly, které můžou ušetřit až 2 hodiny týdně. Což se projeví v úspoře časové, tak i v úspoře nákladů na mzdy zaměstnanců. Vždyť každá minuta je dobrá.
35
www.maps.google.cz
46
Graf č. 2 - Vyhodnocení linek z hlediska času
215 210 205 200 195 Čas (min) 190
Původní
185
Zoptimalizovaná
180 175 170 165 A
B Trasa
Zdroj: Vlastní zpracování
4.2 Vyhodnocení nákladů na pohonné hmoty Při vyhodnocování nákladů na pohonné hmoty je vycházeno z aktuálních cen pohonných hmot, které v současné době činí průměrně 36,60 Kč na litr benzinu
36
a z informací o spotřebě vozidel od zadavatele. Pro tento výpočet jsem zvolila vozidlo značky Citroën Jumper o celkové spotřebě benzinu 10,5 litrů na 100 km. Ve skutečnosti je trasa A obsluhována za týden 3krát a trasa B je využívána 2krát. Náklady na pohonné hmoty původní trasy A i B činí týdně 3 274,3 Kč a náklady na zoptimalizované trasy činí 3 115,4 Kč za týden. Celkem tedy vedla optimalizace obou linek k úspoře 158,9 Kč za týden. Pokud uvažujeme 261 dnů v roce, kde jsou odečtené víkendy jedná se o úsporu 8 294,6 Kč ročně. Nicméně do této ceny nejsou započítány další náklady, které s dopravou souvisí, jako je opotřebení vozidel a dálniční známky potřebné na určité trasy, které se dají pořídit za 1 500 Kč na rok 2012, což jsou další náklady navíc.
36
http://www.kurzy.cz/komodity/benzin-nafta-cena/
47
Tabulka č. 12 - Náklady na pohonné hmoty
Původní Trasa
vzdálenos
Optimální
Cena
vzdálenost
Spotřeba pohonný
(km)
t (km)
l/km
ch hmot (Kč)
A (3x)
162
151,3
0,105
36,60
B (2x)
183
178,4
0,105
36,60
Celkem
345
329,7
Náklady
Náklady
na
na
Absolutní
původní
optimální
rozdíl
trasu
trasu
(Kč)
(Kč)
(Kč)
622,6 x 3
581,4 x 3
41,2
= 1867,7
= 1744,2
123,5
703,3 x 2
685,6 x 2
17,7
= 1406,6
= 1371,2
35,4
1325,9
1267
58,9
3274,3
3115,4
158,9
Zdroj: Vlastní zpracování Graf č. 3 - Náklady na pohonné hmoty
800 700 600 500 Náklady 400 (Kč) 300 200 100 0
Původní Zoptimalizovaná Rozdíl A
B Trasa
Zdroj: Vlastní zpracování
4.3 Zpráva pro zadavatele
4.3.1 Současný stav
Podnik obslouží každý týden 2 trasy, které jsou nazvány trasami A, B. Trasu A podnik využívá 3krát za týden a trasu B využívá 2krát do týdne.
Pro optimalizaci byly zvoleny obě trasy A, B.
48
Neoptimalizovaná trasa A má 7 uzlů a celkovou vzdálenost 162 km, trasa B má také 7 uzlů o celkové vzdálenosti 183 km.
Trasy byly optimalizovány ručním výpočtem pomocí MS Excel.
4.3.2 Výsledky optimalizace
Největší úspora z hlediska nejvíce ušetřených kilometrů byla zjištěna u trasy A 10,7 km.
U trasy B byla zjištěna úspora 4,6 km.
Celkově vedla optimalizace obou tras k úspoře 15,3 km.
Jelikož je trasa A využívána 3krát týdně a trasa B 2krát týdně, úspora za týden byla zjištěna na 58,2 km.
Při aktuální průměrné ceně benzinu 36,60 Kč za litr a při uvedené spotřebě vozidel vychází finanční úspora 58,90 Kč na obě trasy a týdenní finanční úspora vychází na 158,9 Kč.
Pokud uvažujeme 261 pracovních dnů v roce, pak je možno na optimalizovaných trasách ušetřit až 8 294,3 Kč.
4.3.3 Doporučení pro plánování na další období Společnost REDDO CZ, s. r. o. v současné době používá GPS s lokalizací pohybu, pomocí níž může kontrolovat polohu vozidla, jeho zastávky, délku jízdy, rychlost jízdy. Hlavní výhodou je, že může kontrolovat ujeté vzdálenosti konkrétního vozidla a zároveň i spotřebu pohonných hmot. Další výhodou je, že v případě krádeže vozidla může společnost snadno zjistit, kde se auto nachází. Nevýhodou GPS je, že nedokáže zvolit nejoptimálnější trasu. Z tohoto důvodu navrhuji zakoupení navigace, která právě tuto funkci zahrnuje. Výběr navigace závisí od individuálních požadavků společnosti. Ceny navigací, které by byly vhodné pro účely podniku se pohybují kolem 5 000 Kč, což není tak vysoká částka, jako zakoupení optimalizačního programu. Pokud by však společnost chtěla více investovat doporučuji zakoupení optimalizačního programu s využitím nejen pro vlastní účely, ale také pro účely pronájmu okolním firmám, čímž by se náklady na pořízení softwaru snížily. Využití optimalizačního
49
softwaru je mnohem přesnější a přínosnější, avšak naopak nákladnější. Vše závisí na možnostech společnosti. Avšak největší problém společnosti je, že z velké části distribuuje zboží do každého města pouze jednomu odběrateli. Pokud by měl v každém městě alespoň 3 odběratele zvýšila by se jeho celková produktivita. Řidiči vozidel by obsloužili mnohem více odběratelů než obslouží v současné době. Tímto by došlo ke snížení všech nákladů.
50
Závěr Rozvoz zboží společnosti REDDO CZ, s. r. o. je z hlediska distribuce velmi flexibilní. Cílem této práce bylo nalezení optimální trasy rozvážkových vozidel a zhodnocení ekonomické výhodnosti nové trasy oproti stávající trase se zaměřením na snížení dopravních nákladů. Pro výpočet byly zvoleny trasy, které si podnik pojmenoval trasami A, B. Cílem práce bylo naplánovat dopravní trasy takovým způsobem, aby přepravní vzdálenosti byly co nejkratší a s tím související co nejnižší náklady na pohonné hmoty. Výpočet optimálních tras byl proveden ručně pomoci metody obchodního cestujícího v MS Excel. Po optimalizaci došlo u obou tras ke snížení celkové ujeté vzdálenosti. Největší úspora byla zjištěna u trasy A, která činí 10,7 km a u trasy B byla zjištěna úspora 4,6 km. Pokud je uvažováno 261 pracovních dnů v roce, pak celková úspora na obou trasách činí 3 993,3 km ročně. Trasy jsou obsluhovány 5 dní v týdnu a to střídavě: 3krát trasa A a 2krát trasa B, proto dojde i ke značné úspoře pohonných hmot. Při aktuální průměrné ceně benzinu 36,60 Kč za litr a při uvedené spotřebě vozidel vychází finanční úspora 58,90 Kč na obě trasy. Pak je možno na optimalizovaných trasách ušetřit až 8 294,3 Kč ročně. Výsledkem všech úspor je i úspora času. U trasy A byla zjištěna úspora 16 minut a u trasy B 32 minut. Jsou to rozdíly, které můžou ušetřit až 2 hodiny týdně. Za rok to mohou být více než 4 dny navíc, které vedou ke snížení mzdových nákladů pro zaměstnance. Úspora času vede také ke snížení opotřebení vozového parku, nicméně tyto náklady nejsou ve výpočtech zahrnuty.
51
Seznam použitých zdrojů [1] ČUJAN, Zdeněk a Zdeněk MÁLEK. Výrobní a obchodní logistika. první. Zlín : Univerzita Tomáše Bati ve Zlíně, 2008. ISBN 978 -80-7318-730-9.
[2] DELMLOVÁ, Marie. Diskrétní matematika a logika. Praha, 2010. Dostupné z: http://math.feld.cvut.cz/demlova/teaching/dmc/pred100.pdf [3] DVOŘÁK, Petr a Markéta ŠMEJKALOVÁ. Řešení problému obchodního cestujícího s využitím evolučních přístupů. P a M [online]. [cit. 2012-04-06]. Dostupné z: http://www.epame.cz/epame/index.php?option=com_content&view=article&id=3&Ite mid=13&lang=cs [4] FÁBRY, Jan. Dynamic Traveling Salesman Problem: In Mathematical Methods in Economics. Plzeň: Professional Publishing, 2006. ISBN 80-86419-23-1. [5] PERKNER, Radim. Teorie grafů. Praha, 1999. Skripta. ČVUT Praha, fakulta dopravní. [6] SVOBODA, Vladimír. Doprava jako součást logistických systémů. Vyd. 1. Praha : Vydavatelství ČVUT, 2004. 152 s. ISBN 80-01-02914-X. [7] SVOBODA, Vladimír. Dopravní logistika. Praha: ČVUT 2004. ISBN 80-01-02914X. [8] ŠEDA, Miloš. Teorie grafů. Brno: Radix, spol. s. r. o., 2003. ISBN 80-963035-64-3. [9] VANĚČEK, Drahoš. Logistika. Jihočeská univerzita v Českých Budějovicích Ekonomická fakulta: ediční středisko : JČU, 2008, s. 16. ISBN 978-80-7394-085-0. [10] VÍT, Jan. Optimalizace dopravních tras výrobce masných produktů. Bakalářská práce. 2009 [11] Distribuční logistika [online]. VSB, 25.4.2011 [cit. 2012-04-03]. Dostupné z: http://www.id.vsb.cz/sliva/zl/Zaklady%20logistiky_3.pdf. Vysoká škola Báňská.
Akademický
příspěvek.
[12] Teorie grafů. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikipedia
Foundation,
2001-
[cit.
2012-02-28].
Dostupné
z:
http://cs.wikipedia.org/wiki/Graf_%28teorie_graf%C5%AF%29 [13] Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teorie-grafu.cz/zakladni-pojmy/kruznice-cyklus.php [14] Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teorie-grafu.cz/zakladni-pojmy/orientovane-grafy.php [15] Http://teorie-grafu.cz. Teorie grafů [online]. 2009 [cit. 2012-04-03]. Dostupné z: http://teorie-grafu.cz/zakladni-pojmy/cesta-a-souvislost-grafu.php [16]
Algoritmus
[online].
28.9.2010
[cit.2012-04-04].
Dostupné
z
WWW:
http//www.algoritmy.net/article/5407/Obchodni- cestujici. [17] The Traveling Salesman Problem [online]. 2005 [cit.2012-04-04]. Dostupne z: . [18] The Traveling Salesman Problem [online]. 2005 [cit.2012-04-04]. Dostupne z: . [19] Problém obchodního cestujícího (TSP). Problém obchodního cestujícího [online]. 25.3.2009
[cit.
2012-04-04].
Dostupné
z:
http://www.cs.vsb.cz/kot/anim/a-
tsp_approx.pdf
[20] Uni-protokolle: Hamiltonian [online]. 2009 [cit. 2012-04-11]. Dostupné z: www.uni-protokole.de
[21] Hamiltonian path [online] Dostupné z: http://en.wikipedia.org/wiki/Hamiltonian_cycle
[22] Plantour logistic. Sysklass cz [online]. [cit. 2012-04-06]. Dostupné z: http://www.sysklass.cz/index.php?t=article&n=clanek-plantour-logistic-49
Seznam zkratek LP
Lineární programování
MS
Microsoft
PPL
Přepravní a kurýrní služby (Professional parcel logistic)
TG
Teorie grafů
TSP
Problém obchodního cestujícího (Travelling salesman problem)
USD
Americký dolar
Seznam symbolů V
Množina prvků (uzel, vrchol grafu)
H
Množina prvků (hrana)
G
Graf
e
Orientovaná hrana
n
Počet míst jež chceme navštívit
cij
Vzdálenost mezi místem i a místem j
H = {(vi, vj)|vi, vj Є V, i ≠ j}
Množina hran s nezápornými náklady
C = (cij)
Matice
(cij...kde i = 1 …m, j = 1 …n)
Náklady na přepravu od dodavatele k odběrateli
(xij …kde i = 1…m, j = 1…n)
Objem přepravy od dodavatele k odběrateli
n
n
c
ij
xij
Minimalizační funkce
i 1 j 1
Lpř ij
Přírůstek vzdálenosti vzniklý zapojením místa „k“ mezi místa „i“ a „j“:
Lik
Vzdálenost z místa i do místa k:
Lkj
Vzdálenost z místa k do místa j
Lij
Vzdálenost z místa i do místa j
Seznam tabulek Tabulka č. 1
Počet cest v závislosti na počtu měst ………………………..…25
Tabulka č. 2
Tři podmínky, které platí pro vzorec č. 1 ………………………26
Tabulka č. 3
Rozvozový plán ………………………………………………...31
Tabulka č. 4
Přehled vozidel …………………………………………………32
Tabulka č. 5
Neoptimalizovaná (intuitivní) trasa A ………………………….34
Tabulka č. 6
Neoptimalizovaná (intuitivní) trasa B ……………………….....35
Tabulka č. 7
Kilometrické vzdálenosti mezi městy (matice vzdáleností) ……36
Tabulka č. 8
Optimalizovaná trasa A ………………………………………...39
Tabulka č. 9
Kilometrické vzdálenosti mezi městy (matice vzdáleností) ……41
Tabulka č. 10
Optimalizovaná trasa B ………………………………………...44
Tabulka č. 11
Vyhodnocení vzdáleností ………………………………………45
Tabulka č. 12
Náklady na pohonné hmoty ……………………………………48
Seznam obrázků Obrázek č. 1
Oblast distribuční logistiky……………………………………..10
Obrázek č. 2
Distribuční řetězec REDDO CZ, s. r. o. ………………………..11
Obrázek č. 3
Základní pojmy teorie grafů ……………………………………15
Obrázek č. 4
Nejkratší kružnice (trojúhelník) ………………………………..16
Obrázek č. 5
Kružnice (cyklus) v obecném grafu ……………………………17
Obrázek č. 6
Příklad neorientovaného uzlového grafu – matice sousednosti . 17
Obrázek č. 7
Příklad orientovaného grafu ……………………………………18
Obrázek č. 8
Souvislý graf …………………………………………………...19
Obrázek č. 9
Nesouvislý graf ………………………………………………...19
Obrázek č. 10
Problém obchodního cestujícího – zadání……………………... 22
Obrázek č. 11
Problém obchodního cestujícího - cesta………………………...23
Obrázek č. 12
Hamiltonovská kružnice ………………………………………..24
Obrázek č. 13
Cyklus …………………………………………………………27
Obrázek č. 14
Parciální cyklus ………………………………………………...28
Obrázek č. 15
Mapa neoptimalizované trasy A …………………………….…35
Obrázek č. 16
Mapa neoptimalizované trasy B ……………………………..…36
Obrázek č. 17
Mapa optimalizované trasy A ……………………………….…40
Obrázek č. 18
Mapa optimalizované trasy B …………………………………..44
Seznam grafů Graf č. 1
Vyhodnocení vzdáleností ………………………………………46
Graf č. 2
Vyhodnocení linek z hlediska času …………………………….47
Graf č. 3
Náklady na pohonné hmoty ……………………………………48
Autor (vypracovala)
Markéta Žákovská
Název BP
Optimalizace dopravních tras v distribuční činnosti
Studijní obor
Dopravní logistika
Rok obhajoby BP
2012
Počet stran
45
Počet příloh
0
Vedoucí BP
Ing. Alexander Čapka
Oponent BP
prof. Ing. Vladimír Strakoš, DrSc.
Tato práce je zaměřena na hledání optimálních tras rozvážkových vozidel a zhodnocení ekonomické výhodnosti nových tras oproti stávajícím trasám se zaměřením na snížení dopravních nákladů. Anotace
Teoretická část je věnována distribuci, teorii grafů a problému obchodního cestujícího. Praktická část je zaměřena na analýzu dopravních tras u vybraného subjektu pomocí metody obchodního cestujícího, která přispívá ke zlepšení současné situace v podniku.
Klíčová slova
Distribuce, optimalizace tras, obchodní cestující
Místo uložení
ITC (knihovna) Vysoké školy logistiky v Přerov
Signatura
