Využití lineárního programování při optimalizaci dopravy

Mendelova zemědělská a lesnická univerzita v Brně Provozně ekonomická fakulta

Využití lineárního programování při optimalizaci dopravy Bakalářská práce

Vedoucí práce:

Autor práce:

doc. Ing. Josef Holoubek, CSc.

Nikol Mrázková Brno 2009

Prohlašuji, že jsem tuto bakalářskou práci vypracovala samostatně pod vedením doc. Ing. Josefa Holoubka, CSc. V seznamu literatury jsem uvedla všechny literární a odborné zdroje, ze kterých jsem čerpala.

V Brně dne 25. května 2009

………………………. Podpis autora

Na tomto místě bych chtěla poděkovat doc. Ing. Josefu Holoubkovi, CSc. a Ing. Pavlu Kolmanovi za užitečné rady, které mi poskytli při zpracování mé bakalářské práce. Dále bych zde chtěla poděkovat panu Drahoši Sádlíkovi za poskytnutí podkladových údajů.

Abstrakt Mrázková, N. Využití lineárního programování při optimalizaci dopravy. Bakalářská práce. Brno, 2009. Bakalářská práce se zabývá nalezením optimálních tras při rozvoru nápojů od firmy Starobrno, a.s. s využitím lineárního programování. Teoretická část práce seznamuje s lineárním programováním. Hlavní úlohou, kterou se práce zabývá je okružní problém a způsoby jeho řešení nejen Littlovou metodou. V praktické části jsou popsány okružní trasy a za pomoci programu Lingo a Littlovy metody jsou nalezeny optimální trasy. V závěru jsou získané výsledky porovnány a zhodnoceny.

Klíčová slova: okružní problém, Littlova metoda, Lingo

Abstract Mrázková, N. The use of linear programming to optimize transport. Bachelor thesis. Brno, 2009. The bachelor thesis deals with finding optimal routes in distribution of Starobrno drinks with usage of linear programming. The theoretical part of the work presents a linear programming. The main role of the work deals with the delivery problem and the ways of its solving not only by the Little´s method. In the practical part there are described delivery paths and the optimal route are found with the help of the program Lingo and Little´s method. In conclusion there are compared and evaluated the obtained results.

Keywords: delivery problem, Little´s method, Lingo

Obsah 1

Úvod a cíl práce ........................................................................................................................ 6 1.1 Úvod ................................................................................................................................... 6 1.2 Cíl a metodika ................................................................................................................... 7

2

Teoretická část práce ............................................................................................................... 8 2.1 Operační výzkum ............................................................................................................. 8 2.1.1 Matematické programování.................................................................................... 8 2.2 Lineární programování .................................................................................................... 9 2.3 Speciální úlohy lineárního programování .................................................................. 11 2.3.1 Okružní problém .................................................................................................... 11 2.4 Počítačové zpracování úloh lineárního programování ............................................. 15 2.4.1 Proces formulace modelu podle LINDO Systems Inc [6] ................................. 17 2.4.2 Vytváření LINGO Modelu [12]............................................................................. 17

3

Praktická část práce ............................................................................................................... 19 3.1 Charakteristika zkoumaného objektu a řešeného problému ................................... 19 3.2 Popisy okružních tras..................................................................................................... 20 3.2.1 Původní trasy .......................................................................................................... 22 3.3 Formulace matematického modelu a jeho odladění.................................................. 25 3.3.1 Program Lingo ........................................................................................................ 26 3.3.2 Littlova metoda ....................................................................................................... 27 3.4 Řešení problému s využitím matematického modelu, interpretace výsledků ...... 28 3.4.1 Optimalizované trasy ............................................................................................. 28 3.4.2 Porovnání tras ......................................................................................................... 31

4

Závěr......................................................................................................................................... 35

5

Literatura ................................................................................................................................. 36

6

Přílohy………………………………………………………………………………………. 37

1 ÚVOD A CÍL PRÁCE

6

1 Úvod a cíl práce 1.1 Úvod Optimalizace rozvozu zboží a tras obchodních zástupců hraje v dnešní hektické a úsporné době významnou roli. Od počtu ujetých kilometrů se odvíjí spotřeba pohonných hmot a ze spotřeby se vypočítávají náklady na dopravu, proto má vzdálenost mezi návštěvními místy v hospodaření firem velký význam. Při optimalizaci dopravy však vzdálenost není jediným možným kritériem. Pro některé distributory má větší význam úspora času. Je pravdou, že distributor, který dává přednost úspoře času, může najet mnohem více kilometrů, a tím pádem by měl i větší náklady. To už si však musí každý distributor rozhodnout sám, zda jeho úkolová mzda dokáže tyto náklady pokrýt a ještě přinášet zisk. Minimalizováním či maximalizováním funkcí (= optimalizací) se zabývá nejrozšířenější disciplína matematického programování, kterou je lineární programování. Lineární programování je také považováno za nejvíce propracovanou a v praxi nejpoužívanější disciplínu. Význam lineárního programování spočívá v možnosti aplikovat ho na velký počet problémů, ale také v existenci mnoha metod vedoucích k nalezení optimálního řešení. Použití lineárního programování je například u distribuce, optimalizace dopravy, rozmístění zdrojů nebo u přiřazovacích problémů. Tato práce se bude zabývat optimalizací dopravy pomocí okružního problému. Pro jeho řešení je možno najít mnoho metod lineárního programování, ale většina z nich je velmi náročná na řešení. Jednou z nich je Littlova metoda, která je určena speciálně pro řešení okružního problému a tedy její řešení je snadnější. Littlova metoda vyžaduje ruční výpočet (pomocí tužky a papíru a někdy i kalkulačky), proto je spíše vhodná pro řešení problémů s menším počtem návštěvních míst. V dnešní době rozšířených počítačových technologií existují i programy, které za nás tento výpočet provedou. Ušetří nám tím čas, námahu i případné chyby, které bychom mohli naší nepozorností způsobit. Celou situaci krásně vystihuje Fraško [2] ve svém článku: „V dnešní době si již asi těžko dokážeme představit efektivní způsob plánování a optimalizace dopravy jinak než pomocí počítačové podpory a speciálních programů. Zvláště pro společnosti, které disponují rozsáhlým a rozmanitým vozovým parkem, je správa a efektivní využití vozidel v jejich každodenní činnosti stále nelehkým úkolem. V dnešní silné konkurenci jsou společnosti stále nuceny hledat efektivní a účinná řešení pro zefektivnění a zlepšení služeb zákazníkům a přitom minimalizovat náklady s tím spojené. Jednou z možností, jak řešit otázky typu ‚Jak poskytnout zákazníkovi ještě lepší službu za ještě méně vynaložených prostředků.‘ , je optimalizace logistických procesů pomocí softwarových aplikací. Je však třeba upozornit, že i sebedokonalejší nástroj nikdy nenahradí lidskou práci, zvláště v konečných rozhodovacích procesech. Systémy pro plá-

1 ÚVOD A CÍL PRÁCE

7

nování dopravy je třeba chápat jako podpůrný nástroj pro plánování distribučních procesů společnosti a jistou záruku optimalizace nákladů na dopravu.“

1.2 Cíl a metodika Cílem této bakalářské práce je zjistit, zda návštěvní místa řidiče rozvážejícího nápoje jsou v jednotlivých daných okruzích optimálně uspořádána. Porovnání původních a optimalizovaných tras pro rozvoz nápojů však nebude jediným cílem. Dále pro jednu trasu provedeme výpočet i pomocí jiné metody a následně porovnáme a zhodnotíme výsledky těchto dvou metod. Tato práce se bude zabývat rozvozem nápojů do restaurací od brněnského pivovaru Starobrno. Po získání adres návštěvních míst zjistíme pomocí volně dostupné internetové stránky mapy.cz [10] vzdálenosti a časové úseky mezi jednotlivými adresami. Výsledky hledání zaznamenáme do tabulkového procesoru Excel. Výpočet optimálních tras provedeme pomocí programu Lingo a pro jednu trasu provedeme výpočet i pomocí Littlovy metody, s cílem porovnat a zhodnotit výsledky těchto dvou metod. Po nastudování teoretické části z dostupné literatury zadáme do vytvořeného algoritmu v programu Lingo rozměry matice. V souboru Excel si tuto matici pojmenujme a následně v algoritmu nadefinujeme. Program Lingo si posléze data ze souboru Excel sám načte a vypočítá optimální uspořádání míst. Tento postup opakujeme pro zbylých 7 matic. Dále si sestavíme algoritmus Littlovy metody a opět provedeme výpočet. Všechny vypočtené hodnoty porovnáme. Při výpočtu se zaměříme nejen na minimalizování délky okruhu a s tím spojené minimalizování spotřeby pohonných hmot a nákladů, ale také na minimální spotřebu času.

2 TEORETICKÁ ČÁST PRÁCE

8

2 Teoretická část práce 2.1 Operační výzkum Literatury zabývající se touto tématikou je velké množství, avšak nejvíce se tímto tématem zabývá stejnojmenná kniha Operační výzkum od Jablonského [5]. Jablonský [5] definuje operační výzkum jako: „vědní disciplínu nebo spíše soubor relativně samostatných disciplín, které jsou zaměřeny na analýzu různých typů rozhodovacích problémů. Operační výzkum nachází aplikace všude tam, kde se jedná o analýzu a koordinaci provádění operací v rámci nějakého systému.“ Pro porovnání ještě uvedeme definici Rašovského [8], který definuje operační výzkum jako: „soubor přístupů a metod, které slouží k řešení složitých, zejména rozhodovacích problémů.“ Jak se uvádí v mnoha publikacích (uvádí také Holoubek [4]) operační výzkum se v anglicky psané literatuře označuje jako „operational research“, „operations research“ nebo „management science“. Jablonský [5]: „Cílem operačního výzkumu je stanovit takovou úroveň provádění těchto operací nebo jejich vzájemný vztah tak, aby bylo zajištěno co možná nejlepší fungovaní celého systému. Pro posouzení toho, zda systém funguje hůře či lépe, je přitom třeba stanovit nějaké kritérium či kritéria. Provádění operací v systému nemůže byt absolutně nezávislé - ve všech případech závisí na omezených zdrojích, které jsou při těchto operacích čerpány, na provádění jiných operací, na vnějších činitelích ovlivňujících chod systému apod. Operační výzkum je možné tedy charakterizovat i jako prostředek pro nalezení nejlepšího (optimálního) řešení daného problému při respektování celé řady různorodých omezení, které mají na chod systému vliv.“ Holoubek [4]: „Díky velké rozmanitosti problémů zkoumaných a řešených v rámci operačního výzkumu a díky značné rozmanitosti použitého matematického aparátu je operační výzkum členěn na relativně samostatné disciplíny či odvětví. Mezi nejvýznamnější patří matematické programování.“

2.1.1 Matematické programování „Cílem této disciplíny je hledání optimálního řešení problému, který vyplývá z existence množiny omezujících podmínek. Omezující podmínky jsou zapsány v podobě soustavy rovnic a nerovnic. Model typické úlohy matematického programování je možno zapsat takto: z extr = f ( x1 , x 2 ..., x n ) g1 ( x1 , x 2 ,..., x n ) ≥≤ b1 g 2 ( x1 , x 2 ,..., x n ) ≥≤ b2


9 g m ( x1 , x 2 ,..., x n ) ≥≤ bm xj ≥ 0

kde j = 1, 2,…,n. Funkce gi (i = 1, 2,.., m) představují jednotlivé omezující podmínky, které v daném problému hrají důležitou roli. Funkce f představuje kritérium, podle kterého posuzujeme úroveň jednotlivých řešení daného problému a která nám rovněž umožní určit řešení optimální, tj. takové řešení, při kterém hodnota funkce f dosáhne extrémní (maximální, minimální) hodnoty. V úloze s n proměnnými xj a m vlastními omezujícími podmínkami jde o nalezení takových hodnot proměnných, které by jednak vyhovovaly všem uvažovaným omezením a navíc zabezpečovaly, že účelová funkce nabude extrémní hodnoty. Mají-li jak účelová funkce f tak funkce gi lineární charakter můžeme problém řešit v rámci lineárního programování. V případě, že některá z funkcí f nebo gi je nelineární, jde o problém nelineárního programování.“ Jablonský [5]: „Aplikace úloh lineárního programování jsou velmi časté. Mezi běžné oblasti aplikací patří optimalizace výrobního programu firmy, směšovací úlohy jako například optimalizace portfolia, určení strategie reklamy, návrh výživy, dále optimalizace distribuce zboží od výrobců přes velkosklady k odběratelům a mnoho dalších.“

2.2 Lineární programování Holoubek [4]: „Lineární programování jako jedna z dříve uvedených součástí operačního výzkumu je nejlépe propracovaná a v praxi snad nejčastěji využívaná. Existuje řada typických úloh spadajících do lineárního programování, které umožňují vyhledání optimálního řešení daného problému. Výhodou lineárního programování je skutečnost, že pro řešení všech úloh dané třídy existuje univerzálně použitelná a přitom relativně jednoduchá metoda.“ Obecný tvar úlohy lineárního programování „Chceme-li jistý existující problém řešit jako úlohu lineárního programování, je třeba nejdříve sestavit lineární deterministický statický matematický model problému. Každý z tří uvedených přívlastků matematického modelu je signálem toho, že uvedený model není zcela přesným zobrazením daného problému. Záměrného a přijatelného zjednodušení se zde dopouštíme hlavně proto, abychom mohli využít relativně jednoduchého aparátu lineární algebry a existence univerzální metody řešení. Ze slovního modelu problému musí být možné stanovit •

proměnné a to jak z hlediska jejich věcného významu tak i počtu;


10

•

co v daném problému představuje různá omezení, která je při úvahách o řešení nezbytné respektovat;

•

co je považováno za kritérium, podle něhož jsou jednotlivá řešení porovnávána;

ve všech třech případech vždy včetně správných měrných jednotek.

Obecný tvar lineárního matematického modelu (v rozepsané formě) má tuto podobu: z extr = c1 x1 + c 2 x 2 + K + c n x n

(2.1)

a11 x1 + a12 x 2 + K + a1n x n ≥≤ b1 a 21 x1 + a 22 x 2 + K + a 2 n x n ≥≤ b2 MM

(2.2)

a m1 x1 + a m 2 x 2 + K + a mn x n ≥≤ bm x1 , x 2 , K , x n ≥ 0

(2.3)

Strukturu tohoto modelu tvoří •

vztah 2.1 – lineární mnohočlen, pro který je nejčastěji užíváno označení účelová funkce (nebo také kriteriální funkce);

•

vztah 2.2 – soustava lineárních rovnic a nerovnic označovaných jako vlastní omezující podmínky1;

•

vztah 2.3 – soustava nerovnic tzv. podmínky nezápornosti.

Cílem této úlohy je stanovit takové hodnoty strukturních proměnných x1,… xn , aby účelová funkce ( při respektování vlastních omezujících podmínek a podmínek nezápornosti) dosáhla extrémní hodnoty. Hledáme-li řešení s nejvyšší hodnotou účelové funkce pak úlohu označujeme jako maximalizační a v opačném případě řešíme minimalizační úlohu. Výše uvedená rozepsaná forma zápisu modelu, který má m vlastních omezujících podmínek a n strukturních proměnných, je sice srozumitelná ale pracná, proto se užívají i úspornější formy zápisu modelu. Sumační forma zápisu: n

z extr = ∑ c j x j j =1

1

Použití relačního znaku ≥≤ je třeba chápat tak, že mezi levou a pravou stranou konkrétní vlastní omezující

podmínky může nastat pouze jedna z těchto tří relací: ≥, ≤ nebo =. Je-li na levé straně výrazu více proměnných jedná se o systémovou podmínku, při jedné proměnné jde o individuální omezující podmínku.

2 TEORETICKÁ ČÁST PRÁCE n

∑a j =1

ij

11

x j ≥≤ bi

(i = 1,…, m)

xj ≥ 0

(j = 1, …, n)

kde použité symboly jsou označovány těmito názvy: cj – koeficient účelové funkce vztahující se k j – té proměnné xj – strukturní proměnná aij – strukturní (technicko-ekonomický) koeficient vyjadřující vztah mezi i – tou omezující podmínkou a j – tou proměnnou bi – pravá strana i – té vlastní omezující podmínky“ Gros [3]: „Vzhledem k tomu, že omezení lze formálními úpravami převést na omezení stejného typu, např. „menší nebo rovno“(vynásobení omezení typu „větší nebo rovno“ -1), nebo minimalizaci převést na maximalizaci vynásobením celého modelu -1, lze zapsat model lineárního programování v maticové formě ve tvaru

max z = cx Ax ≤ b x≥0

kde vektor b

je sloupcový vektor pravých stran omezení,

matice A

obdélníková matice typu (m, n) technických koeficientů,

c

řádový vektor ocenění proměnných v účelové funkci a

x

sloupcový vektor optimalizovaných proměnných.“

2.3 Speciální úlohy lineárního programování Jablonský [5]: „Mezi typickými úlohami lineárního programování lze najít úlohy, které se vyznačují některými speciálními vlastnostmi. Tyto vlastnosti se mohou týkat speciální struktury modelu, způsobů jejich řešení apod. Nejtypičtější úlohy lineárního programování jsou distribuční úlohy. Dále do lineárního programování patří dopravní problém, kontejnerový dopravní problém, přiřazovací problém, okružní dopravní problém, celočíselné programování a cílové programování.“

2.3.1 Okružní problém Holoubek [4]: „V praxi výrobních i obchodních firem je možné se setkat i s otázkou jak co nejúsporněji dodat požadované zboží odběratelům. V tomto případě však nejde o klasickou podobu dopravní úlohy, kdy odběratelé mohou být zásobování z několika míst (výrobců, skladů). 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čí ve stejném místě. V průběhu této jízdy musí být všichni odběratelé navštíveni právě je-


12

denkrát. Úloha tohoto typu má řadu praktických aplikací, protože problém optimálního sestavení okruhu vzniká ve firmách, které pravidelně či nepravidelně rozvážejí či svážejí určité produkty, zásilky a podobně ( svoz zásilek z poštovních schránek, svoz komunálního odpadu, rozvoz tisku do prodejních stánků, zásobování prodejen aj.). 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 okruhu, spotřebu času či pohonných hmot, náklady. Je zřejmé, že u úloh tohoto typu nehraje podstatnou roli kapacita dopravního prostředku. Typickou ukázkou je problém obchodního cestujícího, který si chce naplánovat návštěvu jednotlivých klientů tak, aby v rámci své cesty ujel co nejmenší vzdálenost.2 “ Nejjednodušší okružní problém Rašovský [8] popisuje takto: „Nechť máme: •

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

•

n kroků trasy (např. 1 krok je přejezd z výchozího stanoviště do prvního návštěvního místa, poslední krok je přejezd z předposledního návštěvního místa do výchozího stanoviště); (k = 1, 2, …, n)

a nechť •

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

•

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

n

n

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

při omezeních n

n

∑∑ x i =1 j =1 n

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

ijk

=1

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

ijk

=1

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

n

∑∑ x j =1 k =1 n

=1

ijk

n

∑∑ x i =1 k =1 n

n

i =1

j =1

∑ xijk = ∑ xijk +1

2

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

Vedle uvedeného označení „okružní problém“ se pro úlohy tohoto typu v literatuře běžně užívá i název

„problém obchodního cestujícího“, popřípadě „problém listonoše“.

2 TEORETICKÁ ČÁST PRÁCE při k = n je k+1 = 1

13

{

x = 0 ijk 1

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

Holoubek [4]: „Okružní problém je v zásadě lineární úlohou, takže by bylo možné řešit jej za určitých předpokladů simplexovou metodou, avšak vzhledem k degenerovanosti je to nevýhodné a výpočetně náročné i pro nepříliš rozsáhlé úlohy. Kvůli typickým vlastnostem úloh tohoto druhu je vhodnější použít některé ze specifických metod, mezi něž patří i Littlova metoda. Tato metoda je postavena na uplatnění metody větvení a mezí, při níž se množina přípustných řešení systematicky zmenšuje až do okamžiku nalezení optimálního řešení. Při řešení tohoto typu distribučního problému Littlovou metodou je možné využít některé poznatky z maďarské metody užívané v přiřazovacích úlohách. Úlohu si tedy lze zapsat do čtvercové matice. V jednotlivých políčcích jsou uvedeny například délky tras mezi jednotlivými odběrateli – koeficienty účelové funkce. Matice vzdáleností může být symetrická i nesymetrická, podle toho, zda předpokládáme či nepředpokládáme, že vzdálenost mezi místem i a j je v obou směrech shodná. Z podstaty problému vyplývá, že v matici vylučujeme 2 druhy tras: •

trasu z místa i zpět přímo do místa i – tj. políčka na hlavní diagonále matice (tyto zakázané trasy si v matici označíme symbolem ‚–‘ );

•

trasy, které by předčasně uzavřely okruh, tj. dříve než jsou do okruhu zapojena všechna plánovaná místa. Cesty zakázané z tohoto důvodu označíme například symbolem ‚∞‘.“

Zjednodušeně Rašovský [8] shrnuje algoritmus Littlovy metody do tohoto sledu úkonů: 1. „Redukujeme výchozí matici vzdáleností mezi jednotlivými návštěvními místy, tj. od každého řádku a každého sloupce matice odečteme nejnižší sazbu (transformační konstantu – a,b) nacházející se v příslušném řádku a sloupci. Touto redukcí získáme v každém řádku a sloupci alespoň jednu nulovou sazbu ( ci , j = 0 ). Řešení úlohy s takto redukovanou maticí je ekvivalentní s řešením původní úlohy. 2. Vypočítáme hodnotu Z0, o kterou se sníží hodnota účelové funkce libovolného přípustného řešení při odpočtu příslušných transformačních konstant. n

n

i =1

j =1

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


14

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

i, j

= ci′,min + c ′j ,min ,

kde ci′, min …nejmenší redukovaná vzdálenost v i – tém řádku, c ′j ,min …nejmenší redukovaná vzdálenost v j – tém sloupci.

4. Ze všech vypočítaných Φ i, j vybereme tu, která má maximální hodnotu. Platí-li Φ

= Φ , pak první etapa hledaného optimálního okruhu bude vést po cestě max i, j z i – tého do j – tého místa. (Je-li maximálních hodnot v matici více, pak si lze pro zařazení do okruhu vybrat kteroukoliv z těchto cest.)

5. Vypočteme hodnotu účelové funkce Z

i, j

při nezařazení cesty z i – tého místa

do j – tého místa do okruhu

Z

i, j

= Z +Φ . 0 max

6. Vynecháme i – tý řádek a j – tý sloupec redukované matice vzdáleností. 7. Zakážeme protisměrnou jízdu mezi místy určujícími první etapu, tj. vyloučíme průjezd mezi j – tým a i – tým místem – políčko odpovídající ve zmenšené matici „zakázané“ cestě můžeme označit znakem ∞. 8. Ověříme, zda zmenšená a redukovaná matice získaná v předcházejícím kroku obsahuje v každé řadě alespoň jednu nulovou sazbu. V případě, že v některé řadě není žádná nulová sazba, pak pomocí transformačních konstant je možno tento požadavek zajistit stejně jako v bodu 1. 9. Byla-li do okruhu správně zařazena cesta z i – tého do j – tého místa, pak musí platit

Z

i, j

≤Z

i, j

,

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

n

i =1

j =1

∑ ai + ∑ b j . Transformační konstanty a i , b j odpovídají bodu 8. Pokud uvedený vztah neplatí, nebyl důsledně dodržen stanovený algoritmus a je třeba řešení začít znovu.


15

10. Opakujeme výše uvedený postup počínaje bodem 3 až do okamžiku, kdy redukovaná čtvercová matice vzdáleností bude mít rozměr 2 x 2, přičemž dvě ze čtyř cest v matici jsou zakázané. Dvě zbývající cesty uzavřou celý okruh.“ Littlovu metodu ani další programy pro řešení okružního problému Devlin [1] ve své knize nepovažuje za nejefektivnější. Devlin [1]: „Žádná z dnes známých metod není nikterak podstatně lepší než ohodnocení všech tras a porovnání jejich délek, pokud se nejedná o velice malý počet míst. Při řešení problému obchodního cestujícího pro deset měst, dostaneme deset možností, kde začít, pak devět možných měst, která navštívíme jako druhá, osm možností třetího města a tak dále, takže celkový počet různých tras je 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800.

Náročná matematika není zapotřebí. Jediné, co potřebujeme je sčítání dlouhých řad čísel a porovnávání výsledků. To co dělá tento problém těžkým je pouhá velikost čísla udávajícího počet tras. Změníme-li počet měst z deseti na jedenáct, výsledný počet různých tras je zjedenáctinásobí. Konstrukce efektivních procedur, které by uměly vyřešit úlohy, jakou je problém obchodního cestujícího, by průmyslu přinesla růst zisků o miliardy dolarů. Protože tato metoda je tak důležitá, obětovalo po mnoho let obrovské množství talentovaných mladých výzkumníků mnoho hodin snaze najít efektivní cesty k jejich řešení. Zatím se však nepodařilo tyto cesty najít a je velmi pravděpodobné, že tuto hádanku vyřeší ‚neznámý amatér‘ – tedy někdo bez matematické průpravy. Prvním úkolem, se kterým se teoretici setkali, bylo nalezení způsobu měření času potřebného k provedení určitého úkonu na počítači. Například: jak dlouho bude trvat nalezení optimální trasy pro jistou konkrétní skupinu měst? Je zřejmé, že odpověď závisí na (nejméně) dvou věcech: na typu počítače, který použijeme, a to zejména na jeho rychlosti a paměťové kapacitě, a pak na počtu měst. Je jasné, že čím více vstupních dat problém má, tím déle bude výpočet trvat. Příkladem může být i jeden z dosud nejlepších výsledků získaných v roce 1998. Tým matematiků nalezl nejkratší trasu, po které je možno navštívit všech 13 509 měst ve Spojených státech, které mají alespoň pět set obyvatel. Zabralo to tři a půl měsíce nepřetržitých výpočtů na propojené trojici vysoce výkonných vědeckých počítačů, kterým pomáhaly dalších třicet dva osobních počítačů typu Pentium.“

2.4 Počítačové zpracování úloh lineárního programování Jablonský [5]: „Nabídka programů pro řešení optimalizačních úloh je poměrně široká. Zahrnuje jednak nejjednodušší, velmi levné (několik málo desítek USD) programy, které jsou limitovány možností řešit úlohy s maximálně několika málo desítkami proměnných a omezujících podmínek, určené zpravidla pro výuku, ale i profesionální, vysoce výkonné systémy, které umožňují řešit úlohy obsahující i několik desítek tisíc proměnných


16

a několik tisíc omezujících podmínek. Tomu odpovídá i jejich cena, která se pohybuje často v tisících USD. Tyto optimalizační programy jsou schopny pomocí algoritmů a výpočtů poskytnout nejrůznějších kombinace a simulace možných řešení a poskytnout představu o jejich ideálním řešení. Výsledky těchto simulací mohou následně vést ke změnám řízení v oblasti výrobních procesů, dodavatelských vazeb, skladovacích kapacit společnosti apod. Pro řešení menších úloh lineárního programování si však případný uživatel nemusí pořizovat specializovaný programový systém, protože možnost zpracovávat tyto typy úloh je k dispozici v tabulkovém kalkulátoru MS Excel, který má zpravidla uživatel k dispozici na svém počítači.“ Plevný [7]: „STORM je softwarový balíček obsahující moduly pro řešení nejčastěji používaných kvantitativních technik pro modelování ekonomických problémů. Často se též využívá jako školní software v kurzech operačního výzkumu a dalších kurzech obsahujících kvantitativní metody. Je to samostatný produkt s vlastním editorem pro zadávání vstupních dat na bázi spreadsheetu, přičemž je možné importovat i data z jiných spreadsheetů. V současnosti je dostupná verze STORM 4.0 z roku 2001. Obsahuje devatenáct modulů, jejichž kompozice a funkce jsou konzistentní. V každém modulu má uživatel k dispozici nabídku výstupních zpráv pro zobrazení výsledků výpočtů. Kromě těchto výstupních zpráv poskytuje STORM možnost provádění citlivostní analýzy. Není obtížné experimentovat s hodnotami parametrů či hledat jejich nejlepší nastavení. Optimalizační systém LINDO je produktem firmy LINDO Systems, Inc. a je jedním z nejpoužívanějších optimalizačních systémů. Je to všestranný nástroj pro řešení úloh lineárního, nelineárního, celočíselného a kvadratického programování, který má poměrně jednoduché ovládání. Verze pro Windows nabízí intuitivní prostředí s plně funkčním editorem pro modelování a roletovým menu. Problémy mohou být vyjádřeny v jednoduchém zřetelném rovnicovém tvaru. V profesionálních verzích je tento systém schopen řešit poměrně rozsáhlé lineární a celočíselné problémy. LINDO vykazuje všechny potřebné vlastnosti pro zadávání modelů, jejich editování, řešení, zobrazování, vyšetřování a citlivostní analýzu.“ Jablonský [5]: „LINGO představuje především nástroj pro řešení lineárních i nelineárních optimalizačních úloh a pro řešení soustavy lineárních i nelineárních rovnic. U proměnných daného modelu umožňuje navíc uvažovat i podmínky celočíselnosti (obecně celočíselné i bivalentní proměnné). Pro řešení různých skupin úloh využívá LINGO tři zabudované řešitele, které se podle charakteru úlohy volí automaticky. Jedná se o řešitele pro: •

lineární optimalizační úlohy případně soustavy lineárních rovnic,

•

nelineární optimalizační úlohy a soustavy nelineárních rovnic,

•

úlohy s podmínkami celočíselnosti.

LINGO je, stejně jako systém LINDO, produktem firmy LINDO Systems, Inc. Vzhledem k tomu je uživatelské prostředí pro práci s oběma systémy téměř totožné. Velice roz-


17

dílné jsou však možnosti, které oba systémy poskytují. Jednou z hlavních charakteristik systému LINGO je skutečnost, že obsahuje speciální jazyk pro matematické modelování. Ten je také hlavní odlišností tohoto sytému od většiny jiných optimalizačních produktů jako je například LINDO. V těchto bezesporu velmi výkonných systémech musí uživatel připravit vstupní data navrženého modelu v požadovaném formátu jako je například MPS formát. Poté lze spustit vlastní optimalizační výpočet. Také systém LINGO lze používat podobným způsobem – tím by se však uživatel připravil o hlavní výhodu, kterou je používání zmíněného modelovacího jazyka. LINGO umožňuje uživateli zapsat navržený model pomocí tohoto speciálního jazyka – tento zápis je velmi blízký běžnému matematickému zápisu daného modelu. Tento obecný model stačí potom spojit s připraveným datovým souborem. Může se přitom jednat o běžný textový soubor bez zvláštních požadavků na jeho formát nebo soubor připravený ve spreadsheetu nebo databázi. Konkrétní model pro zpracování tak vzniká spojením obecné části (matematický model) s datovým souborem. Obecnou část lze přitom samozřejmě používat opakovaně pro různé úlohy daného typu (stačí mít k dispozici příslušné datové soubory).“

2.4.1 Proces formulace modelu podle LINDO Systems Inc [6] Při použití jakéhokoliv analytického nebo modelového přístupu při pouštění se do řešení problému existuje pět hlavních kroků: 1. Porozumění skutečného problému. 2. Formulace modelu problému. 3. Sběr a generování vstupních dat pro model (např. náklady na jednotku, která bude použita). 4. Řešení nebo spuštění modelu. 5. Provádění a interpretace řešení v reálném světě. Obecně lze říci, že existuje určité množství opakování těchto pěti kroků. Z výše uvedeného je nejjednodušší řešení tohoto modelu na počítači. Kroky 1, 3 a 5 jsou, ne-li nejtěžší, přinejmenším nejvíce časově náročné. Úspěch těchto kroků závisí do značné míry na tom, jak jste dobře obeznámeni s organizací (například je dobré znát někoho, kdo ví, jaká je skutečná míra produkce na určitém stroji). Krok 2 vyžaduje nejvíce analytické schopnosti. Kroky 1 a 5 vyžadují většinu lidských schopností. Formulace správných modelů je umění hraničící s vědou.

2.4.2 Vytváření LINGO Modelu [12] Optimalizační model se skládá ze tří částí: • Cílová funkce - to je jediný vzorec, který přesně popisuje, co by měl model optimalizovat. Základním výrobním příkladem objektivní funkce by byla minimalizace doby cyklu pro daný produkt.


18

• Proměnné - jedná se o množství, která můžou být změněna, aby se vytvořila optimální hodnota cílové funkce. Například při řízení automobilu, délka trvání cesty (t) a rychlost (v), při které se určuje vzdálenost (d), která může být ujeta. • Omezení - to jsou vzorce, které definují limity hodnot proměnných. Pokud obchod se zmrzlinou je určen počtem příchutí, které může nabídnout, pak jen pozitivní číslo příchutí je proveditelné. Toto omezení může být vyjádřena jako příchutě >= 0.

3 PRAKTICKÁ ČÁST PRÁCE

19

3 Praktická část práce 3.1 Charakteristika zkoumaného objektu a řešeného problému [11] Společnost STAROBRNO, a.s., člen skupiny Heineken, patří v současné době s více než pětiprocentním podílem na trhu mezi největší pivovarnické skupiny v České republice. Vlastní stejnojmenný pivovar Starobrno a pivovar Hostan ve Znojmě. Co do objemu prodeje sudového piva na domácím trhu si drží v posledních letech třetí příčku mezi velmi silnou konkurencí všech pivovarů. V regionu jižní Moravy patří značkám Starobrno a Hostan čtvrtina celého trhu s pivem a v samotném Brně pak pivovar Starobrno dodává své produkty do více než poloviny všech gastronomických zařízení. Společnost Starobrno dodává na český trh široké portfolio pivních značek. Tvoří jej produktová řada značky Starobrno, produktová řada značky Hostan, vlastní speciální piva Baron Trenck, Červený Drak a Black Drak, licenčně vyráběné premiové pivo Zlatý Bažant a importované koncernové značky Heineken, Amstel, Murphy´s a Edelweiss. Portfolio pivních značek doplňují ještě vlastní sudové, přírodním cukrem slazené limonády ZULU kola a ZULU citron a pivní pálenka BierBrand. Kromě stálého sortimentu uvádí Starobrno na trh jednorázové pivní rarity (např. Zelené pivo na Zelený čtvrtek), čímž potvrzuje svou roli inovátora na českém pivním trhu. Pro distribuci svých produktů brněnský pivovar Starobrno využívá nabídky podnikatelů (soukromých distributorů). Jen pro město Brno má pivovar uzavřeno smlouvu s asi 40 podnikateli. Každý podnikatel má libovolný počet nákladních aut, se kterými rozváží produkty. Pro tuto bakalářskou práci byly získány informace od jednoho z těchto distributorů – pana Sádlíka (dále jen „podnikatel“). Podnikatel tuto činnost vykonává na základě dříve vydávaného živnostenského listu (v dnešní době díky novele zákona o živnostenském podnikání se živnostenské listy již nevydávají, jsou nahrazeny výpisem ze živnostenského rejstříku) a tudíž pivovar Starobrno není jeho zaměstnavatelem. Podnikatel vlastní 4 nákladní auta, která zajišťují distribuci do 200–250 restaurací za týden. Tato 4 nákladní auta jezdí každý den na jiná místa, takže jezdí každý den jinou trasu. Je malá pravděpodobnost, že se jednotlivé trasy budou opakovat, neboť musí respektovat individuální potřeby zákazníků. Každý zákazník si objednává podle své vlastní potřeby, tedy v momentě, kdy vidí, že mu zásoby určitého produktu docházejí. Zákazník si tedy neobjednává v pravidelných intervalech, např. každou středu. V této práci jsme si problém zúžili a zaměřili jsme se na jeden konkrétní den podnikatele, tudíž se zde nezabýváme všemi restauracemi, které podnikatel navštěvuje. V následujícím textu přiblížíme pracovní náplň jednoho dne podnikatele pro objasnění několika základních otázek, jako jsou např. „Jaký je vztah mezi distributorem a jednotlivými restauracemi?“, „Kdo sestavuje okruhy pro 4 nákladní auta podnikatele?“, „Vyplácí pivovar fixní mzdu nebo je mzda závislá na výkonech?“.


20

Pracovní vztah mezi distributorem a jednotlivými restauracemi není žádný. V případě, kdy restauraci (navštívenému místu) docházejí zásoby piva a nealkoholických nápojů, zavolá na příslušnou telefonní linku do pivovaru Starobrno a objedná si na konkrétní den požadované množství těchto produktů. Operátorky tyto požadavky zpracovávají a večer je ve formě seznamu adres navštívených míst a množství produktů předávají podnikateli. Operátorky navrhují optimální trasy cest s nejnižším počtem ujetých kilometrů, pravděpodobně pomocí GPS a také tyto údaje předávají podnikateli. Ten však už po mnohaletých zkušenostech s dopravní strukturou, se stavem silnic a frekvencí dopravy ve městě Brně si trasy všech 4 aut plánuje sám. Večer tedy naplánuje trasy, které druhý den pojede. Sám si také musí určit, které nákladní auto pojede kterou trasu. Při plánování těchto tras však musí brát ohled na tato 3 kritéria: •

Kvalita cesty: Často se stává, že operátorky najdou a doporučí cestu, která vede po účelové komunikaci. Je tedy nezpevněná, mohou se na ní vyskytovat větší nerovnosti a v zimní období není udržovaná. Pro nákladní auta naložené někdy i skleněnými láhvemi není tento druh pozemní komunikace vhodný.

•

Otevírací doba navštěvovaných restaurací: Každá restaurace otevírá v jinou dobu. V některých restauracích je však možnost individuální domluvy, neboť někteří pracovníci musí chodit do práce dříve než je otevírací doba.

•

Nosnost auta: Podnikatel musí trasy plánovat také podle toho, jaké množství produktů si jednotlivé restaurace objednají, protože musí dodržovat maximální nosnost auta a maximální objem nákladního prostoru.

Tato 3 kritéria jsme ve svých výpočtech nezohlednili. Podnikatel si vytváří trasy s nejkratším časem jízdy a to z toho důvodu, že pivovar Starobrno vyplácí úkolovou mzdu. Tedy za 1 hl piva nebo nealkoholických nápojů vyplácí podle vnitřní směrnice určitou částku. Cílem podnikatele proto je, navštívit co nejvíce míst v co nejkratším čase.

3.2 Popisy okružních tras Pro určování vzdáleností mezi návštěvními místy, jsme na stránkách mapy.cz [10] využili funkce „Plánovač trasy“. Tato funkce dále nabízí možnost výběru, podle jakého kritéria bude cesta mezi zadanými místy určena. V této práci porovnáme trasy z obou možných hledisek – nejkratší a nejrychlejší cesta. Nejkratší cesta minimalizuje počet ujetých kilometrů a nejrychlejší minimalizuje čas ujeté vzdálenosti. Díky těmto 2 hlediskům vzniknou pro každou trasu 2 matice hodnot. Funkce Plánovač tras také udává u nejkratší cesty i dobu ujetí a u nejrychlejší cesty i počet ujetých kilometrů.


21

Podnikatel vlastní 4 nákladní auta a tak jsme získali informace o 4 okružních trasách, které, jak již bylo řečeno v předchozím textu, si podnikatel vytváří sám. Trasy jsou označeny písmeny A, B, C, O, přičemž trasu O jezdí sám podnikatel a ostatní trasy jezdí jeho spolupracovníci. Okružní problém se tedy bude řešit pro 8 matic (viz. příloha Tab. 17 – Tab. 24). Na trasách C, O jsou některé cesty přikázané, což znamená, že například na trase C první místo, které musí být navštíveno jsou Hlinky 12, aby zde mohlo být naloženo zboží. Tyto přikázané cesty jsou v příslušných maticích označeny tak, že všechny ostatní cesty jsou zakázané. Pro každou trasu jsou uvedeny vzdálenosti i doby jízdy a to proto, aby bylo možné obě cesty (nejkratší a nejrychlejší) porovnat. Trasy, které v současnosti podnikatel se svými spolupracovníky jezdí jsou označovány jako „původní trasy“ a trasy získané programem Lingo jako „optimalizované“. V každé trase se vyskytuje adresa Hlinky 12, kterou musí všechna 4 auta povinně navštívit ve stanoveném pořadí. Tato adresa určuje umístění centrálního skladu piva pivovaru Starobrno, ale také místo výroby piva. Adresa Svratecká 5 je sídlem firmy pana Sádlíka. Všechna nákladní auta z této adresy ovšem nevyjíždějí, proto jednotlivé trasy mají jiná výchozí místa. Vyjíždí odtud pouze podnikatel a jeden jeho spolupracovník, tudíž trasy C a O začínají na této adrese. Každá trasa obsahuje jiný počet návštěvních míst. Ulice Svratecká se nachází v městské části Brno-Komín. Mezi návštěvními místy nejsou pouze okolní městské části Brno-Bystrc, Brno-Jundrov nebo Brno-Žabovřesky. Podnikatel se svými kolegy navštěvuje i městské části Brno-střed, Brno-Královo Pole, Brno-Řečkovice, ale také jezdí až do městské části Brno-Jehnice a Brno-Ořešín. Z přílohy Obr. 7 vyplývá, že podnikatel obsluhuje převážně severní část města Brna. Pro zjištění nákladů na distribuci produktů, je nutné znát průměrnou spotřebu nákladního auta a cenu nafty. Každé nákladní auto podnikatele má průměrnou spotřebu nafty 20 litrů na 100 km, tedy za 1 km projede 0,2 l nafty. Z Obr. 1 vyplývá, že situace na trhu s pohonnými hmotami je nestálá. Na cenu benzínu i nafty může mít vliv mnoho ekonomických ale i politických faktorů. Například současná ekonomická krize nebo případná válka v zemích těžících ropu způsobuje změny cen pohonných hmot. Z tohoto důvodu použijeme pro určení nákladů průměrnou cenu nafty za 1. čtvrtletí roku 2009 pro okres Brno-město (1. 1. 2009–30. 4. 2009), která je 25,30 Kč/l.


22

Obr. 1 Vývoj ceny nafty v Kč/l v okrese Brno-město v období od 1. 1. 2009 do 30. 4. 2009 (Zdroj: CCS [9])

3.2.1 Původní trasy Trasa A Tato tras má 10 návštěvních míst a začíná na ulici Hlinky 12. Spolupracovník podnikatele přijede s nákladním autem na Hlinky 12, tady naloží požadované množství piva a rozveze ho na příslušná místa. Po navštívení všech návštěvních míst se vrací do pivovaru Starobrno na Hlinky 12, kde předá prázdné sudy a přepravky s lahvemi. Tím tento okruh končí. Tab. 1 Původní trasa A Nejkratší cesta Nejrychlejší cesta Pořadí Navštívené místo Vzdálenost Doba Vzdálenost Doba [km] [min] [km] [min] 0 Hlinky12 0,0 0 0,0 0 1 Křížová 20 1,2 2 1,2 2 2 Nádražní 7 1,4 3 1,4 3 3 Údolní 34 1,9 4 1,9 4 4 Tábor 17 1,8 4 1,8 4 5 Poděbradova 26 1,5 3 1,5 3 6 Bayerova 23 1,7 4 1,7 4 7 Úvoz 39 1,4 3 1,4 3 8 Zahradnická 14 2,5 5 2,5 5 9 Minská 35 4,6 9 4,6 9 10 Hlinky12 3,0 6 3,0 6 Celkem 21,0 43 21,0 43

Nejkratší cesta: Počet ujetých km: 21 km Spotřeba nafty v litrech: 21km × 0,2l / km = 4,20l Náklady na naftu v Kč: 4,2l × 25,30 Kč / l = 106,26 Kč


23

Nejrychlejší cesta: u trasy A je tato cesta stejná jako cesta nejkratší, tudíž i náklady na tuto trasu jsou stejné.

Trasa B Trasa B obsahuje 7 návštěvních míst. I když tato trasa má nejmenší počet navštívených míst, není její celkový čas ani vzdálenost nejkratší. Je to způsobeno tím, že narozdíl od trasy A, návštěvní místa zde mají větší vzdálenosti. Výchozím a cílovým místem je zde opět pivovar Starobrno na ulici Hlinky 12. Tab. 2 Původní trasa B Nejkratší cesta Nejrychlejší cesta Pořadí Navštívené místo Vzdálenost Doba Vzdálenost Doba [km] [min] [km] [min] 0 Hlinky 12 0,0 0 0,0 1 Tučkova 9 3,3 7 3,3 2 Kotlářská 18 0,2 0 0,2 3 Kytnerova 1 5,0 11 5,0 4 Kytnerova 6 0,1 0 0,1 5 Tvrdého 3 6,2 13 6,4 6 Böhmova 13 6,1 13 6,3 7 Hlinky 12 7,1 15 7,3 Celkem 28,0 59 28,6

0 7 0 11 0 12 12 14 56

Nejkratší cesta: Počet ujetých km: 28 km Spotřeba nafty v litrech: 28km × 0,2l / km = 5,60l Náklady na naftu v Kč: 5,6l × 25,30 Kč / l = 141,68 Kč Nejrychlejší cesta: Počet ujetých km: 28,6 km Spotřeba nafty v litrech: 28,6km × 0,2l / km = 5,72l Náklady na naftu v Kč: 5,72l × 25,30 Kč / l = 144,72 Kč Trasa C Trasa C má 9 návštěvních míst a je to druhá nejdelší trasa, jak po stránce vzdálenosti, tak i časově. Tato trasa začíná i končí v místě sídla firmy na Svratecké 5. Všechna 4 auta musí navštívit centrální sklad pivovaru Starobrno, aby zde mohla naložit potřebné množství piva, proto prvním místem kam se ze sídla firmy pojede jsou Hlinky 12.


24

Tab. 3 Původní trasa C Pořadí

Navštívené místo

0 1 2 3 4 5 6 7 8 9

Svratecká 5 Hlinky 12 Srbská 4 Obřanská 135 Makovského nám.1 Kachlíková 14 Přístavní parc.č.328 Obvodová 4 Svratecká 11 Svratecká 5 Celkem

Nejkratší cesta Nejrychlejší cesta Vzdálenost Doba Vzdálenost [km] [min] [km] Doba [min] 0,0 0 0,0 0 5,4 11 5,4 11 5,4 11 5,4 11 6,5 12 6,5 12 7,9 15 8,0 15 6,5 14 6,6 13 1,4 3 1,4 3 2,5 6 2,5 5 2,6 6 2,6 5 1,2 3 1,2 3 39,4 81 39,6 78

Nejkratší cesta: Počet ujetých km: 39,4 km Spotřeba nafty v litrech: 39,4km × 0,2l / km = 7,88l Náklady na naftu v Kč: 7,88l × 25,30 Kč / l = 199,36 Kč Nejrychlejší cesta: Počet ujetých km: 39,6 km Spotřeba nafty v litrech: 39,6km × 0,2l / km = 7,92l Náklady na naftu v Kč: 7,92l × 25,30 Kč / l = 200,38 Kč Trasa O Podnikatel na této trase navštěvuje 11 návštěvních míst a vyjíždí ze svého sídla firmy na ulici Svratecká 5. Stejně jako u trasy C i zde je prvním povinným navštíveným místem centrální sklad pivovaru na Hlinkách 12. Jako jediný z těchto 4 dopravců, musí navíc jezdit pro nealkoholické nápoje do dalšího skladu, který je umístěn na ulici Hájecká 15. Proto na druhém místě navštíví vždy tuto adresu. Tato trasa je nejen z tohoto důvodu nejdelší, ale také proto, že obsahuje největší počet návštěvních míst, která mají velké vzdálenosti mezi sebou.


25

Tab. 4 Původní trasa O Pořadí

Navštívené místo

0 1 2 3 4 5 6 7 8 9 10 11

Svratecká 5 Hlinky 12 Hájecká 15 Dornych 120 Drobného 6 Nám. 3.května 5 Nám. 3.května 7 Klimešova 27 Böhmova 17 Optátova 2a Banskobystrická 68 Svratecká 5 Celkem

Nejkratší cesta Nejrychlejší cesta Vzdálenost Doba Vzdálenost Doba [km] [min] [km] [min] 0,0 0 0,0 5,4 11 5,4 6,1 13 6,3 2,6 5 2,6 3,1 7 3,1 8,4 15 8,4 0,1 0 0,1 1,2 3 1,2 5,1 11 5,1 6,3 13 6,5 6,0 12 6,0 5,5 11 5,5 49,8 101 50,2

0 11 12 5 7 15 0 3 11 12 12 11 99

Nejkratší cesta: Počet ujetých km: 49,8 km Spotřeba nafty v litrech: 49,8km × 0,2l / km = 9,96l Náklady na naftu v Kč: 9,96l × 25,30 Kč / l = 251,99 Kč Nejrychlejší cesta: Počet ujetých km: 50,2 km Spotřeba nafty v litrech: 50,2km × 0,2l / km = 10,04l Náklady na naftu v Kč: 10,04l × 25,30 Kč / l = 254,01Kč

Všechny trasy jsou pouze po městě Brně, a tak rozdíly mezi jednotlivými cestami jsou velmi malé. U malého počtu návštěvních míst je velká pravděpodobnost, že optimalizované údaje budou velmi blízké, ne-li stejné s původními. V tabulkách jsou proto uvedeny výsledky zaokrouhlené na 1 desetinné místo a ve výpočtech litrů a nákladů na 2 desetinná místa.

3.3 Formulace matematického modelu a jeho odladění Pro zjištění optimálních tras použijeme program Lingo. Tento způsob jsme zvolili díky rychlosti výpočtu tohoto programu a menší náročnosti na výpočet. Se stoupajícím počtem návštěvních míst roste i počet kroků nutných pro získání optimální trasy. Pro trasu A vypočteme optimální cestu i pomocí Littlovy metody a následně tyto výsledky porovnáme. Pro ostatní trasy výpočty již provedeme pouze pomocí programu Lingo.


26

3.3.1 Program Lingo Následující algoritmus je modelem u programu Lingo a je převzat z LINDO Systems [6]. Modrou barvou písma jsou v něm uvedeny základní znaky algoritmu a zelenou je uveden komentář.

MODEL: ! Traveling Salesman Problem for the cities of Atlanta, Chicago, Cincinnati, Houston, LA, Montreal; SETS: CITY / 1..9/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): DIST, ! The distance matrix; X; ! X( I, J) = 1 if we use link I, J; ENDSETS !The model:Ref. Desrochers & Laporte, OR Letters, Feb. 91; N = @SIZE( CITY); MIN = @SUM( LINK: DIST * X); @FOR( CITY( K): ! It must be entered; @SUM( CITY( I)| I #NE# K: X( I, K)) = 1; ! It must be departed; @SUM( CITY( J)| J #NE# K: X( K, J)) = 1; ! Weak form of the subtour breaking constraints; ! These are not very powerful for large problems; @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K: U( J) >= U( K) + X ( K, J) ( N - 2) * ( 1 - X( K, J)) + ( N - 3) * X( J, K) ); ); ! Make the X's 0/1; @FOR( LINK: @BIN( X)); ! For the first and last stop we know...; @FOR( CITY( K)| K #GT# 1: U( K) <= N - 1 - ( N - 2) * X( 1, K); U( K) >= 1 + ( N - 2) * X( K, 1) ); DATA:

!Distance matrix, it need not be symmetric;

DIST=@ole('obchodni_cestujici.xls'); !DIST =

ENDDATA END

0 702 454 842 702 0 324 1093 454 324 0 1137 842 1093 1137 0 2396 2136 2180 1616 1196 764 798 1857

2396 1196 2136 764 2180 798 1616 1857 0 2900 2900 0;


27

3.3.2 Littlova metoda Matice hodnot, které jsou při výpočtu pomocí Littlovy metody zapotřebí, jsou uvedeny v příloze. Na prvním kroku nejkratší cesty (příloha Tab. 25) popíšeme postup výpočtu Littlovou metodou podle sledu kroků uvedených v teoretické části. Pro zbývající kroky a pro nejrychlejší cestu jsou tabulky uvedeny v příloze (Tab. 26 – Tab. 42). 1. Od každého řádku odečteme nejnižší sazbu nacházející se v příslušném řádku. Tím získáme v každém řádku alespoň jednu nulovou sazbu. Nulová sazba musí dále být i v každém sloupci, takže jsme od sloupce 2, 5, 6 a 10 odečetli opět nejnižší sazbu nacházející se v příslušném sloupci. 2. Vypočítáme hodnotu Z0. n

n

i =1

j =1

Z 0 = ∑ ai + ∑ b j = 7,3 + 1,8 = 9,1 . 3. Pro každou nulovou sazbu vypočítáme hodnotu Φ

i, j

= ci′,min + c ′j ,min .

Například pro nulovou sazbu o souřadnicích [A1,A2] se Φ vou sazbu o souřadnicích [A3,A7] se Φ

i, j

i, j

= 0 + 0 = 0 , pro nulo-

= 0,6 + 0 = 0,6 .

4. Mezi vypočtenými Φ i, j vyhledáme nejvyšší hodnotu. V naší tabulce se nachází dvě nejvyšší hodnoty Φ i, j = 1,2 (v tabulce jsou vyznačeny červenou barvou), tudíž v 1. kroku máme na výběr dvě možné cesty. První cesta je z místa A4 (Tábor 17) do místa A9 (Minská 35). Druhá cesta je, že mezi místy A4 a A9 pojedeme opačným směrem, tedy z místa A9 do místa A4. Vzdálenosti jsou zde stejné, proto je lhostejné, kterou cestu si zvolíme. Zcela náhodně jsme si zvolili cestu z A4 do A9 (příslušný sloupec a řádek jsou vyznačeny v tabulce žlutou barvou). 5. Vypočteme hodnotu účelové funkce Z Z

49

i, j

= Z +Φ = 9,1 + 1,2 = 10,3 . 0 max

6. Vytvoříme novou matici, ve které vynecháme 4. řádek a 9. sloupec. 7. Zakážeme protisměrnou jízdu, tedy do políčka o souřadnicích [A9,A4] napíšeme znak ∞. 8. Ve zredukované matici zjistíme, zda je v každém řádku a sloupci alespoň jedna nulová sazba. V případě, že není, opakujeme krok 1. V případě, že je splněna tato podmínka, pokračujeme krokem 2. 9. Cesta z A4 do A9 byla zařazena správně, protože platí vztah: Z ≤ Z ⇒ 10,3 = 10,3 , 49 49


28

= Z + ∑ ai + ∑ b j = 9,1 + 1,2 + 0 = 10,3 . 49 0 Tyto kroky opakujeme až do doby, kdy vznikne matice o rozměrech 2 × 2 (příloha Tab. 33). V této matici jsou již cesty dány – z A2 (Nádražní 7) do A6 (Bayerova 23) a z A9 (Minská 35) do A7 (Úvoz 39). Ostatní cesty jsou zde zakázané. Z

3.4 Řešení problému s využitím matematického modelu, interpretace výsledků 3.4.1 Optimalizované trasy Trasa A Tab. 5 Optimalizovaná trasa A

Tab. 6 Optimalizovaná trasa A

- nejkratší Pořadí 0 1 2 3 4 5 6 7 8 9 10

- nejrychlejší

Navštívené místo Hlinky12 Zahradnická 14 Křížová 20 Nádražní 7 Bayerova 23 Poděbradova 26 Tábor 17 Minská 35 Úvoz 39 Údolní 34 Hlinky12 Celkem

Vzdálenost [km] 0,0 2,3 0,4 1,4 2,5 1,7 1,6 0,4 1,8 0,1 1,1 13,3

Doba [min] 0 4 1 3 6 4 4 1 4 0 2 29

Pořadí 0 1 2 3 4 5 6 7 8 9 10

Navštívené Vzdálenost místo [km] Hlinky12 0,0 Zahradnická 14 2,3 Křížová 20 0,4 Nádražní 7 1,4 Bayerova 23 2,5 Poděbradova 26 1,7 Minská 35 2,0 Tábor 17 0,4 Úvoz 39 1,7 Údolní 34 0,1 Hlinky12 1,1 Celkem 13,6

Doba [min] 0 4 1 3 6 4 4 1 3 0 2 28

Nejkratší cesta: Počet ujetých km: 13,3 km Spotřeba nafty v litrech: 13,3km × 0,2l / km = 2,66l Náklady na naftu v Kč: 2,66l × 25,30 Kč / l = 67,30 Kč Nejrychlejší cesta: Počet ujetých km: 13,6 km Spotřeba nafty v litrech: 13,6km × 0,2l / km = 2,72l Náklady na naftu v Kč: 2,72l × 25,30 Kč / l = 82,98 Kč Tab. 5 a Tab. 6 uvádějí optimalizované trasy pomocí programu Lingo. U této trasy byla použita pro výpočet optimální cesty i Littlova metoda, ze které je poznat, kolik možných uspořádání návštěvních míst mohou tyto trasy mít. Hned v prvním kroku na nejkratší cestě (příloha Tab. 25) máme na výběr ze dvou tras. Největší výběr zařazení další cesty do okruhu máme ve třetím kroku nejrychlejší cesty (příloha Tab. 36). Díky velkému a libovolnému výběru je optimalizovaná trasy pomocí Littlovy metody naprosto stejná


29

s výsledkem z programu Lingo. Tudíž Tab. 5 a Tab. 6 jsou také jedním z možných řešení pomocí Littlovy metody. Trasa B Tab. 7 Optimalizovaná trasa B

Tab. 8 Optimalizovaná trasa B

- nejkratší Pořadí 0 1 2 3 4 5 6 7

- nejrychlejší

Navštívené místo Hlinky 12 Tučkova 9 Kytnerova 6 Kytnerova 1 Böhmova 13 Kotlářská 18 Tvrdého 3 Hlinky 12 Celkem

Vzdálenost [km] 0,0 3,3 5,0 0,1 0,7 4,9 1,4 1,0 16,4

Doba [min]

Pořadí

0 7 11 0 2 11 3 2 36

0 1 2 3 4 5 6 7

Navštívené místo Hlinky 12 Tvrdého 3 Tučkova 9 Kotlářská 18 Kytnerova 6 Kytnerova 1 Böhmova 13 Hlinky 12 Celkem

Vzdálenost [km] 0,0 1,9 1,5 0,2 4,9 0,1 0,7 7,3 16,6

Doba [min] 0 4 3 0 10 0 2 14 33

Nejkratší cesta: Počet ujetých km: 16,4 km Spotřeba nafty v litrech: 16,4km × 0,2l / km = 3,28l Náklady na naftu v Kč: 3,28l × 25,30 Kč / l = 82,98 Kč Nejrychlejší cesta: Počet ujetých km: 16,6 km Spotřeba nafty v litrech: 16,6km × 0,2l / km = 3,32l Náklady na naftu v Kč: 3,32l × 25,30 Kč / l = 84 Kč Trasa C Tab. 9 Optimalizovaná trasa C

Tab. 10 Optimalizovaná trasa C

- nejkratší Pořadí 0 1 2 3 4 5 6 7 8 9

Navštívené místo Svratecká 5 Hlinky 12 Obřanská 135 Srbská 4 Makovského nám. 1 Svratecká 11 Přístavní parc. č. 328 Kachlíková 14 Obvodová 4 Svratecká 5 Celkem

- nejrychlejší Vzdálenost [km] 0,0 5,4 8,0 6,5

Doba [min]

Pořadí

0 11 18 13

0 1 2 3

1,8

3

4

2,8

6

5

3,1 1,4 3,8 2,9 35,7

6 3 8 7 75

6 7 8 9

Navštívené místo Svratecká 5 Hlinky 12 Obřanská 135 Srbská 4 Makovského nám. 1 Kachlíková 14 Přístavní parc. č. 328 Obvodová 4 Svratecká 11 Svratecká 5 Celkem

Vzdálenost [km] 0,0 5,4 8,2 6,7

Doba [min] 0 11 17 12

1,8

3

6,6

13

1,4

3

2,5 2,6 1,2 36,4

5 5 3 72


30

Nejkratší cesta: Počet ujetých km: 35,7 km Spotřeba nafty v litrech: 35,7 km × 0,2l / km = 7,14l Náklady na naftu v Kč: 7,14l × 25,30 Kč / l = 180,64 Kč Nejrychlejší cesta: Počet ujetých km: 36,4 km Spotřeba nafty v litrech: 36,4km × 0,2l / km = 7,28l Náklady na naftu v Kč: 7,28l × 25,30 Kč / l = 184,18 Kč

Trasa O Tab. 11 Optimalizovaná trasa O

Tab. 12 Optimalizovaná trasa O - nejrychlejší

- nejkratší Pořadí 0 1 2 3 4 5 6 7 8 9 10 11

Navštívené Vzdálenost místo [km] Svratecká 5 0,0 Hlinky 12 5,4 Hájecká 15 6,1 Dornych 120 2,6 Drobného 6 3,1 Nám. 3.května 7 8,3 Klimešova 27 1,2 Nám. 3.května 5 1,2 Böhmova 17 4,0 Banskobystric0,3 ká 68 Optátova 2a 6,0 Svratecká 5 1,7 Celkem 39,9

Doba [min]

Pořadí

0 11 13 5 7 15 3 2 9 1 12 4 82

0 1 2 3 4 5 6 7 8 9 10 11

Navštívené Vzdálenost místo [km] Svratecká 5 0,0 Hlinky 12 5,4 Hájecká 15 6,3 Dornych 120 2,6 Drobného 6 3,1 Nám. 3.května 7 8,3 Nám. 3.května 5 0,1 Klimešova 27 1,2 Banskobystrická 5,3 68 Böhmova 17 0,3 Optátova 2a 6,5 Svratecká 5 1,7 Celkem 40,8

Nejkratší cesta: Počet ujetých km: 39,9 km Spotřeba nafty v litrech: 39,9km × 0,2l / km = 7,98l Náklady na naftu v Kč: 7,98l × 25,30 Kč / l = 201,89 Kč Nejrychlejší cesta: Počet ujetých km: 40,8 km Spotřeba nafty v litrech: 40,8km × 0,2l / km = 8,16l Náklady na naftu v Kč: 8,16l × 25,30 Kč / l = 206,45 Kč

Doba [min] 0 11 12 5 7 15 0 2 11 1 12 4 80


31

3.4.2 Porovnání tras Optimalizace s programem Lingo přinesla rozdílné trasy ve srovnání s původními trasami. Z Obr. 2 zjistíme, že pro každou trasu se našlo lepší řešení než je původní. Největší úspory jsme dosáhli na trase B. Optimalizovaná cesta nejkratší se nám zkrátila o 11,6 km a cesta nejrychlejší nám ušetřila 23 min. Naopak na druhé nejdelší trase, na trase C, došlo k nejmenšímu rozdílu. Vzdálenost se zkrátila o 3,7 km a doba o 6 min. Obr. 2 Vzdálenosti (v km) na nejkratší cestě u původní a optimalizované trasy Nejkratší cesta

Vzdálenosti (km)

50,0 40,0 30,0

původní trasa

20,0

optimalizovaná trasa

10,0 0,0 A

B

C

O

Trasy

Pro lepší porovnání uvádíme tyto rozdíly i v relativním vyjádření. Původní trasy jsou považovány za 100 % a následující tabulky (Tab. 13 a Tab. 14) vyjadřují procentní rozdíl původní a optimalizované trasy. Tedy na trase B došlo k úspoře o 41 % oproti původní trase a to u nejkratší i u nejrychlejší cesty. Na trase C byl nejmenší rozdíl oproti původní trase u nejrychlejší cesty, což bylo o 7,7 %.

Tab. 13 Relativní rozdíly mezi původní a optimalizovanou trasou na nejkratší cestě (v %) Trasa

Relativní rozdíly (%)

A

36,7

Tab. 14 Relativní rozdíly mezi původní a optimalizovanou trasou na nejrychlejší cestě (v %) Trasa


A

34,9

B

41,4

B

41,1

C

9,4

C

7,7

O

19,9

O

19,2


32

Obr. 3 Relativní rozdíly mezi původní a optimalizovanou trasou (v%)

%

Relativní rozdíly 45 40 35 30 25 20 15 10 5 0

nejkratší nejrychlejší

A

B

Trasy

C

O

Ve stejném poměru došlo i ke snížení spotřeby pohonných hmot. Toto snížení má pozitivní vliv na náklady na dopravu podnikatele. Na Obr. 4 je toto snížení zachyceno pro nejkratší cestu. Graf nejrychlejší cesty zde již uveden není, neboť je totožný s Obr. 4. Obr. 4 Náklady na naftu (v Kč) na nejkratší cestě Náklady na naftu v Kč na nejkratší cestě 260 230 200 původní trasa

140

optimalizovaná trasa

Kč

170

110 80 50 A

B

Trasa

C

O

Úspory, které jsme dosáhli na jednotlivých trasách se zdají být minimální. Musíme však brát na vědomí, že tyto 4 trasy jsou pouze jeden den podnikatele. Druhý den pojede jiné trasy, na kterých může dosáhnout i větších úspor, ale také se může stát, že původní cesta je cestou optimální, tím pádem by nepřinesla žádné další úspory. Větší pravděpo-


33

dobnost však je, že se na každé další trasy najde optimální cesta, která přinese úspory. Největší snížení nákladů se projeví v ročním zúčtování podnikatele, kdy se všechny dosažené úspory nakumulují. V posledním srovnání porovnáme vzdálenosti a doby jízdy tras podle 2 základních kritérií (nejkratší a nejrychlejší cesta), která po celou dobu této práce uvádíme. Srovnávat budeme optimalizované trasy. V relativním srovnání vzdáleností je za 100 % považována nejrychlejší cesta a ve srovnání dob nejkratší cesta. Na Obr. 5 vidíme, že rozdíly ve vzdálenostech mezi nejkratší a nejrychlejší cestou jsou tak malé, že je jedno, kterou cestu si podnikatel vybere. Z Tab. 15 lze vyčíst, že za malý je považován 2% rozdíl. Naopak z Obr. 6 je vidět, že trasy při minimalizaci doby jízdy vykazují o něco větší rozdíly než v případě minimalizace vzdálenosti. Z Tab. 16 vyplývá, že nejrychlejší cesta dokáže ušetřit 8,3 % doby jízdy, což jsou 3 minuty. Tento čas je tak malý a kumulovat se nedá, že výrazně neovlivní hospodaření podnikatele. I přesto, v případě, že by podnikatel preferoval minimalizaci doby jízdy, doporučili bychom mu nejrychlejší cestu.

Tab. 15 Relativní rozdíly při porovnání nejrychlejší a nejkratší cesty mezi vzdálenostmi (v %) Trasa A

Relativní rozdíly (%) 2,2

B

1,2

C

1,9

O

2,2

Tab. 16 Relativní rozdíly při porovnání nejrychlejší a nejkratší cesty mezi dobami jízdy (v %) Trasa


A

3,4

B

8,3

C

4,0

O

2,4


34

Obr. 5 Vzdálenosti tras (v km) na nejkratší a nejrychlejší cestě Vzdálenosti (km) 45 40 35

Km

30

nejkratší

25 nejrychlejší

20 15 10 5 0 A

B

Trasy

C

O

Obr. 6 Doba jízdy (v min) na nejkratší a nejrychlejší cestě Doba jízdy (min) 90 80 70 60 nejkratší

Min

50 40

nejrychlejší

30 20 10 0 A

B

Trasy

C

O

4 ZÁVĚR

35

4 Závěr Tato práce se zabývala optimalizací okružních tras při rozvozu produktů do brněnských restaurací od pivovaru Starobrno. Od jednoho z distributorů těchto produktů byly získány okružní trasy a podrobné informace, které byly podkladem této práce. Za pomoci programu Lingo se podařilo získat optimalizované trasy. Porovnáním původních a optimalizovaných tras bylo zjištěno, že se tyto trasy neshodují. Bylo tedy nalezeno optimální řešení oproti původnímu. Všechny trasy jsou sestaveny z míst ve městě Brně, takže vzdálenosti mezi jednotlivými místy jsou malé. Z tohoto důvodu se čekalo, že rozdíly mezi původní a optimalizovanou trasou budou velmi malé. Díky tomuto očekávání si tedy troufáme tvrdit, že některé výsledné rozdíly jsou velké. Největší úspory se dosáhlo na trase B, kde se ušetřilo 41% a nejmenší úspory na trase C, což bylo o 7%. Dalším cílem, který byl vytyčen bylo použití i jiné metody výpočtu než pomocí programu Lingo. Proto jedna optimalizovaná trasa byla zjišťována i pomocí Littlovy metody. Při výpočtu Littlovou metodou jsme na trase A získali několik možných řešení. Jedním z možných řešení bylo i uspořádání cest ve stejném pořadí, které nabízel program Lingo. Tedy pomocí Littlovy metody jsme dospěli ke stejnému výsledku jako v případě programu Lingo. Littlova metoda má oproti programu Lingo výhodu v tom, že je zde vidět, že úloha má na výběr více řešení. Proto je tato metoda výpočtu vhodnější, pokud bychom úlohu řešili s přihlédnutím ke 3 kritériím (kvalita cesty, otevírací doba restaurací, nosnost auta). Výpočet Littlovou metodou má i svoji nevýhodu, kterou je náročnost výpočtu, protože tato metoda je vhodnější pro úlohy s menším počtem návštěvních míst. Naše úloha neobsahuje velké množství údajů, ale už je zde výpočet náročnější. Náročnost výpočtu okružního problému můžeme potvrdit i v programu Lingo. Pro nalezení optimální trasy B, která obsahuje pouze 7 návštěvních míst, bylo zapotřebí 1 689 kroků. Toto však byl extrémní výsledek. Průměrně se počet kroků pohyboval okolo 500. Čím víc kroků je nezbytných k získání řešení, tím je čas výpočtu delší. Proto tento způsob řešení není nejlepším a u úloh velkého rozsahu může dojít i k několikatýdennímu řešení nebo také k nevyřešení úlohy. Problém obchodního cestujícího by tedy opravdu potřeboval vymyslet nový algoritmus řešení.

5 LITERATURA

36

5 Literatura [1]

DELVIN, K. Problémy pro třetí tisíciletí: Sedm největších nevyřešených otázek matematiky. Přeložil Luboš Pick. 1. vyd. Praha: Dokořán a Agro, 2005. 272 s. ISBN 807363-016-8.

[2]

FRAŠKO, V. Časopis IT Systéme -> Rok 2004 -> 9/2004 -> Plánování a optimalizace dopravy [online]. [cit. 2. 3. 2009]. Dostupné z:

[3]

GROS, I. Kvantitativní metody v manažerském rozhodování. 1. vyd. Praha: Grada Publishing a.s., 2003. 432 s. ISBN 80-247-0421-8.

[4]

HOLOUBEK, J. Ekonomicko-matematické metody. 1. vyd. Brno: Mendelova zemědělská a lesnická univerzita v Brně, 2006. 153 s. ISBN 80-7157-970-X.

[5]

JABLONSKÝ, J. Operační výzkum. 1. vyd. Praha: Professional publishing, 2002. 323 s. ISBN 80-86419-23-1.

[6]

Optimization modeling with Lingo. 6th edition. Chicago (Illinois): LINDO Systems, 2006. 603 s. ISBN 1-893355-00-4.

[7]

PLEVNÝ, M., ŽIŽKA, M. Modelování a optimalizace v manažerském rozhodování. 1. vyd. Plzeň: Západočeská univerzita v Plzni, 2005. 298 s. ISBN 80-7043-435-X.

[8]

RAŠOVSKÝ, M., ŠIŠLÁKOVÁ, H. Ekonomicko-matematické metody. 1.vyd. Brno: Mendelova zemědělská a lesnická univerzita v Brně, 1999. 195 s. ISBN 80-7157412-0.

[9]

CCS. Ceny pohonných hmot v ČR [online]. [cit. 1. 5. 2009]. Dostupné z:

[10]

Mapy.cz [online]. [cit. 2. 3. 2009]. Dostupné z: <www.mapy.cz/#x=138206208@y=132851712@z=11@mm=ZP >

[11]

Starobrno [online]. spolecnosti/>

[cit. 15. 3. 2009].

Dostupné

z:

<www.starobrno.cz/o-

[12]

THORNBURG, K., HUMMEL, A. Lingo 8.0 tutorial [online]. [cit. 15. 4. 2009]. Dostupné z:

Využití lineárního programování při optimalizaci dopravy

Recommend Documents