VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE. Optimalizace trasy při revizích elektrospotřebičů

VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY Hlavní specializace: Ekonometrie a operační výzkum

Název diplomové práce

Optimalizace trasy při revizích elektrospotřebičů

Diplomant: Vedoucí diplomové práce:

Bc. Michal Rusín Ing. Jan Fábry, Ph.D.

Prohlášení: Prohlašují, že jsem diplomovou práci na téma „Optimalizace trasy při revizích elektrospotřebičů“ zpracoval samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury.

Lužec nad Vltavou, 10.5.2009

Michal Rusín

-2-

Poděkování: Chtěl bych poděkovat vedoucímu diplomové práce Ing. Janu Fábrymu Ph.D. za jeho ochotný a vstřícný přístup při konzultaci této práce.

-3-

Obsah 1.

Úvod .......................................................................................................................... 5

2.

Teoretická část .......................................................................................................... 7 2.1.

Úloha obchodního cestujícího ........................................................................... 7

2.2.

Rozvozní úloha.................................................................................................. 9

2.3.

Rozvozní úloha – Model 1 .............................................................................. 11

2.4.

Rozvozní úloha – Model 2 .............................................................................. 13

2.5.

Heuristické metody ......................................................................................... 17

2.5.1. Heuristiky pro úlohu obchodního cestujícího ........................................... 17 2.5.2. Heuristiky pro rozvozní úlohu – model 1 .................................................. 19 2.5.3. Heuristiky pro rozvozní úlohu – Model 2 ................................................. 24 3.

4.

Aplikace v MS Excel .............................................................................................. 32 3.1.

Menu ............................................................................................................... 32

3.2.

Zadávání dat .................................................................................................... 33

3.3.

Výpočet ........................................................................................................... 36

3.4.

Výsledky ......................................................................................................... 48

Praktická část .......................................................................................................... 51 4.1.

Zadání problému ............................................................................................. 51

4.2.

Popis a sběr dat................................................................................................ 53

4.3.

Výpočty ........................................................................................................... 57

4.3.1. Úloha obchodního cestujícího ................................................................... 57 4.3.2. Rozvozní úloha – model 1 ......................................................................... 59 4.3.3. Rozvozní úloha – model 2 ......................................................................... 61 4.4.

Porovnání modelů a heuristik.......................................................................... 64

4.4.1. Porovnání modelů ..................................................................................... 64 4.4.2. Porovnání heuristik ................................................................................... 64 5.

Závěr ....................................................................................................................... 66

Seznam použité literatury ............................................................................................... 67 Internetové zdroje ........................................................................................................... 67 Přílohy ............................................................................................................................ 68

-4-

1. Úvod Tématem mojí diplomové práce je optimalizace trasy při revizích spotřebičů. Důvodem pro volbu tohoto tématu byla snaha o aplikaci poznatků získaných při studiu, na reálných úlohách v praxi. Mezi vypsanými tématy mě zaujaly rozvozní úlohy. Snažil jsem se tedy vyhledat data, která bych mohl využít k aplikaci modelů rozvozní úlohy. Podařilo se mi získat data z oblasti revizí elektrospotřebičů. Revizní technik se při své práci pohybuje mezi řadou míst, na kterých vykonává revize. Na optimalizaci trasy revizního technika lze tedy použít modely okružních úloh. Úloha obchodního cestujícího a rozvozní úloha jsou NP-obtížné úlohy. Proto k výpočtům použiji heuristické metody. Jedná se o metodu nejbližšího souseda, metodu výhodnostních čísel a metodu nejlevnějšího vkládání. K výpočtům heuristik naprogramuji v programu MS Excel, respektive v programovacím jazyce VBA aplikaci. V této aplikaci pak budu řešit všechny tři heuristiky pro tři modely okružních úloh. Práce je rozdělena do čtyř hlavních částí. První součástí je aplikace Heuristiky pro řešení heuristických metod nejbližšího souseda, výhodnostních čísel a nejlevnějšího vkládání. Tyto heuristiky jsou řešeny ve verzích pro úlohu obchodního cestujícího a pro dvě modifikace rozvozní úlohy. Druhou částí je kapitola popisující teoretické modely a heuristiky. V kapitole jsou popsány matematické modely úlohy obchodního cestujícího, rozvozní úloha a její dvě modifikace. Další součástí kapitoly je popis heuristik nejbližšího souseda, výhodnostních čísel a nejlevnějšího vkládání. Každá heuristická metoda je rozepsána ve verzi pro úlohu obchodního cestujícího, pro rozvozní úlohu – model 1 a pro rozvozní úlohu – model 2. Třetí kapitola je popisem aplikace Heuristiky, jejíž vytvoření je součástí práce. Tato kapitola slouží jako manuál k aplikaci. Je zde popsáno uživatelské prostředí, způsob zadávání dat a interpretace výsledků.

-5-

Poslední částí je vlastní výpočet heuristik pro všechny tři uvedené modely a prezentace výsledků a výběr nejlepších variant trasy revizního technika. Je zde také uvedeno srovnání modelů a srovnání použitých heuristik. Cílem této práce je vytvořit aplikaci v MS Excel, resp. VBA, pro výpočet heuristických metod nejbližšího souseda, výhodnostních čísel a nejlevnějšího vkládání a optimalizace trasy revizního technika při revizích elektrospotřebičů.

-6-

2. Teoretická část V této kapitole popíši teoretický základ modelů, které budu v dalších kapitolách využívat. Jako první popíši matematický model úlohy obchodního cestujícího. Dále uvedu matematický model rozvozní úlohy, která z úlohy obchodního cestujícího vychází a rozšiřuje ji. Poté uvedu modifikaci rozvozní úlohu v podobě použité v aplikační části diplomové práce. Tento model bude označen jako Model 1. Posledním modelem bude matematický model rozvozní úlohy upravený pro použití dvou různých délek cyklů. Tento model bude označen jako Model 2. Závěrečné části této kapitoly budou věnovány popisu použitých heuristik. Zmíním jejich obecný popis pro úlohu obchodního cestujícího a jejich modifikace pro rozvozní úlohu použité v aplikaci.

2.1 Úloha obchodního cestujícího Úloha obchodního cestujícího (okružní dopravní problém) patří mezi okružní úlohy. Matematickým modelem této úlohy je graf G  V , E. Množina V  1,2,..., n obsahuje uzly a množina E obsahuje všechny hrany spojující uzly. Všechny hrany v grafu G jsou ohodnoceny. Hrana i, j  je ohodnocena číslem d ij , které představuje dobu přejezdu mezi objekty i a j . Cílem této úlohy je vyjít z výchozího místa a postupně navštívit všechna ostatní místa právě jednou v libovolném pořadí s nejnižšími náklady. V našem konkrétním případě se jedná o minimalizaci času stráveného přejezdy mezi objekty. Cyklus, který se snažíme najít, se nazývá Hamiltonův cyklus. Je složen z hran z množiny E . V úloze musíme zavést bivalentní proměnné xij takové, že xij  1 , v případě, že hrana spojující uzly i, j  leží na hledaném cyklu, anebo xij  0 , pokud Hamiltonův cyklus hranu i, j  neobsahuje. Nyní formulujeme podmínku, která zaručí, že uzel i bude ležet na tomto cyklu.

-7-

Tuto podmínku rozdělíme a formulujeme ji jako dvě samostatné podmínky. Podmínkou (2.1) zajistíme, aby z uzlu i vycházela právě jedna hrana cyklu. Podmínkou (2.2) zajistíme, aby do uzlu i vstupovala právě jedna hrana. n

x j 1

ij

 1,

i  1,2,..., n ,

(2.1)

ij

 1,

j  1,2,..., n .

(2.2)

n

x i 1

Rovnice (2.1) a (2.2) nezaručí, že jejich řešením bude skutečně Hamiltonův cyklus. Abychom vyloučili vznik parciálních cyklů, musíme přidat smyčkové podmínky. Použijeme smyčkové podmínky Miler-Tucker-Zemlin1 ve tvaru t i  t j  nxij  n  1 ,

i  1,2,..., n, j  2,3,..., n .

(2.3)

Počet těchto smyčkových podmínek je roven počtu hran. Proměnné t i a t j nemusí splňovat podmínky nezápornosti ani celočíselnosti. Úkolem úlohy je minimalizovat čas strávený přejezdy mezi objekty. V účelové funkci proto minimalizujeme součet ocenění hran zařazených v cyklu, tedy hran pro které platí xij  1 . Toto ocenění zapíšeme ve tvaru n

n

 d i 1 j 1

ij

xij ,

(2.4)

a budeme jej minimalizovat. Z výrazů (2.1) – (2.4) formulujeme matematický model úlohy obchodního cestujícího: minimalizovat n

n

z   d ij xij

(2.5)

i 1 j 1

1

[2] http://nb.vse.cz/~fabry/4EK314-prezentace.ppt s.66.

-8-

Za podmínek n

x j 1

ij

 1,

i  1,2,..., n ,

ij

 1,

j  1,2,..., n ,

n

x i 1

t i  t j  nxij  n  1 ,

i  1,2,..., n, j  2,3,..., n ,

xij  0,1,

i  1,2,..., n, j  1,2,..., n .

(2.6)

2.2 Rozvozní úloha Rozvozní úloha je rozšířením výše uvedené úlohy obchodního cestujícího. V rozvozní úloze je přípustné řešení s více cykly. Tím se liší od úlohy obchodního cestujícího. Každý cyklus musí obsahovat výchozí uzel. Označíme ho uzel 1. V tomto uzlu každý cyklus začíná a také končí. Všechny uzly musí být zařazeny do některého z cyklů. V této úloze je oproti úloze obchodního cestujícího definována kapacita vozidla, označovaná V . V aplikačním příkladu ze čtvrté kapitoly nahradíme kapacitu vozidla pracovní dobou revizního technika. Poslední modifikací jsou požadavky odběratelů v jednotlivých uzlech. V této diplomové práci jsou požadavky odběratelů nahrazeny dobou trvání činnosti revizního technika v jednotlivých uzlech. Pracovní doba revizního technika V , musí být kladné číslo V  0 . Dobu trvání činnosti v i -tém uzlu označíme s i . Proměnná označená t i v modelu rozvozní úlohy zpravidla znamená velikost nákladu ve vozidle po návštěvě uzlu i . V našem příkladu jsme nahradili kapacitu vozidla disponibilní pracovní dobou revizního technika. Jako t i budeme označovat vyčerpanou pracovní dobu po návštěvě uzlu i . Je to okamžik, kdy revizní technik opustí uzel i . Musí tedy platit podmínka

si  t i  V ,

i  2,3,..., n .

(2.7)

Podmínka (2.7) zaručuje, že disponibilní pracovní doba V nebude v cyklu překročena.

-9-

Smyčkové podmínky Miler-Tucker-Zemlin z úlohy obchodního cestujícího nahradíme novými podmínkami ve tvaru t i  s j  V 1  xij   t j ,

i  1,2,..., n, j  2,3,..., n .

(2.8)

Na začátku každého cyklu, v uzlu 1, je pracovní doba rovna V . Proměnná t1 , vyčerpaná pracovní doba v cyklu, se tedy rovná nule.

t1  0 .

(2.9)

Do modelu rozvozní úlohy ještě přidáme poslední podmínky. Jedná se o modifikované podmínky z úlohy obchodního cestujícího (2.1) a (2.2). V rozvozní úloze musí z každého uzlu i , pro i  2,3,..., n vystupovat právě jedna hrana cyklu. Platnost této podmínky zajistíme výrazem n

x j 1

ij

 1,

i  2,3,..., n .

(2.10)

Do každého uzlu j , j  2,3,..., n pro musí vstupovat právě jedna hrana cyklu. Tuto podmínku formulujeme výrazem n

x i 1

ij

 1,

j  2,3,..., n .

(2.11)

Oproti úloze obchodního cestujícího se podmínky (2,10), resp. (2.11) nevztahují na proměnné x1 j , kde j  1,2,..., n a xi1 , kde i  1,2,..., n . Součet proměnných v prvním řádku, resp. prvním sloupci bude vyšší v případě, že bude vytvořeno více cyklů. Účelová funkce bude mít stejný tvar jako v případě úlohy obchodního cestujícího. Opět minimalizujeme čas strávený přejezdy mezi uzly. Zapíšeme účelovou funkci jako výraz n

n

 d i 1 j 1

ij

xij .

(2.12)

Nyní máme definovány všechny potřebné podmínky a můžeme z nich sestavit matematický model rozvozní úlohy:

- 10 -

minimalizovat n

n

z   d ij xij

(2.13)

i 1 j 1

za podmínek n

x j 1

ij

 1,

i  2,3,..., n ,

ij

 1,

j  2,3,..., n ,

n

x i 1

t i  s j  V 1  xij   t j ,

i  1,2,..., n, j  2,3,..., n ,

si  t i  V ,

i  2,3,..., n ,

(2.14)

t1  0 , xij  0,1,

i  1,2,..., n, j  1,2,..., n .

2.3 Rozvozní úloha – Model 1 Výše uvedená rozvozní úloha není vhodná pro řešení příkladu ze závěrečné části této diplomové práce. V matematickém modelu rozvozní úlohy je definována pracovní doba 𝑉. Do této pracovní doby se v modelu započítává pouze činnost prováděná v uzlu. V příkladu vyžadujeme, aby cesty mezi uzly a činnosti vykonané v uzlech byly provedeny v pracovní době. Při použití modelu rozvozní úlohy by byly započítány pouze činnosti provedené v uzlech a cesty by se do pracovní doby nepočítaly. Cesty, které by pak musel revizní technik vykonat, by nešly v pracovní době uskutečnit a výsledky by byly bezcenné. Musíme proto matematický model modifikovat, aby vyhovoval našim účelům. Pro potřeby aplikačního příkladu musíme provést modifikaci modelu. Aby se čas strávený přejezdy mezi uzly také započítával do pracovní doby, musíme upravit podmínku (2.8) z předchozího modelu.

- 11 -

Rozšíříme ji tak, aby byl do pracovní doby 𝑉 započten i čas potřebný na přejezdy mezi uzly i a j , tj. d ij . Nahradíme podmínku (2.8) následujícím tvarem podmínky t i  s j  d ij  V 1  xij   t j ,

i  1,2,..., n, j  2,3,..., n ,

(2.15)

Podmínka je nyní upravena na tvar, který požadujeme k výpočtům. Ještě musíme upravit podmínku (2.7), abychom počítali s návratem do uzlu 1, bez úpravy této podmínky bychom neuvažovali cestu zpět do výchozího uzlu a pracovní doba by mohla být o část doby návratu překročena.

si  t i ,

i  2,3,..., n .

(2.16)

t i  d i1 xi1  V ,

i  2,3,..., n .

(2.17)

Nyní již máme naformulovány všechny podmínky. Můžeme tedy zapsat celý matematický model Modelu 1: minimalizovat n

n

z   d ij xij

(2.18)

i 1 j 1

za podmínek n

x j 1

ij

 1,

i  2,3,..., n ,

ij

 1,

j  2,3,..., n ,

n

x i 1

t i  s j  d ij  V 1  xij   t j ,

i  1,2,..., n, j  2,3,..., n ,

s i  t i  d j1 x j 1  V ,

i  2,3,..., n ,

t1  0 , xij  0,1,

i  1,2,..., n, j  1,2,..., n .

- 12 -

(2.19)

2.4 Rozvozní úloha – Model 2 V modelu 2 přiblížím model více reálnému problému. Uvolním předpoklad neměnné pracovní doby V . Budeme vycházet z předpokladu, že je možné v několika cyklech překročit pracovní dobu 𝑉 a prodloužit tím cyklus. Zkrácení cesty je však vykompenzováno zvýšením nákladů revizního technika. Delší pracovní dobu si lze představit jako služební cesty nebo práci přesčas. V případě práce přesčas bychom museli počítat se zvýšenou mzdovou sazbou. Přesčasová práce připadá v úvahu při krátkém prodloužení pracovní doby, např. o několik málo hodin. Služební cesta je výhodnější při delším prodloužení pracovní doby, například o několik dní. V případě služební cesty se náklady zvýší o diety a ubytování. V této diplomové práci použiji navýšení pracovní doby o celý jeden den. Jedná se tedy o případ se služební cestou. V aplikačním příkladu se náklady na služební cestu budou lišit podle kraje, ve kterém revizní technik přenocuje. Náklady na ubytování proto nebudu do matematického modelu uvádět, ale budu je přičítat až po vypočtení cesty. Jak už bylo výše zmíněno, matematický model bude obsahovat dvě různé délky pracovní doby. Ve formulaci rozvozní úlohy je definována pracovní doba V . Tato proměnná označuje standardní délku pracovní doby. V případě, že chceme pracovní dobu prodloužit, použijeme k tomu konstantu W . Konstanta W je rozdíl mezi delší pracovní dobou V  W a standardní délkou pracovní doby V . V modelu 2 musí platit podmínka, která zaručí, že z každého uzlu i , pro i  2,3,..., n bude vystupovat právě jedna hrana. Tato podmínka se bude od podmínky

(2.10) lišit tím, že v modelu 2 musíme přidat součet přes index k , kde k  1,2,..., n  1 . Podle indexu k zjistíme, v jakém cyklu je hrana xijk zařazena. Podmínku tedy můžeme formulovat ve tvaru

- 13 -

n

n 1

 x j 1 k 1

k ij

 1,

i  2,3,..., n, k  1,2,..., n  1. (2.20)

V matematickém modelu nesmí chybět ani podmínka zaručující, aby do každého uzlu j , pro j  2,3,..., n vstupovala právě jedna hrana. Opět přidáme sumaci s indexem

k , kde k  1,2,...., n  1 . Podmínku zapíšeme výrazem n

n 1

 x i 1 k 1

k ij

 1,

j  2,3,..., n, k  1,2,..., n  1 . (2.21)

Další podmínkou zajistíme, aby nebyla překročena pracovní doba. Podmínku (2.16) upravíme o možnost prodloužení pracovní doby maximálně o hodnotu W . Budeme definovat novou pomocnou bivalentní proměnnou y k , kde k  1,2,...., n  1 . Pomocí proměnné y k zajistíme požadovaný počet cyklů s delší pracovní dobou. V případě, že pracovní doba bude mít standardní délku V , bude platit y k  0 . Naopak, když využijeme prodlouženou pracovní dobu V  W , platí, že y k  1 . Podmínku vyjádříme výrazem

t ik  d i1 xik1  V  Wyk ,

i  2,3,..., n, k  1,2,..., n  1 (2.22)

Pokud bychom použili pouze výraz (2.21), mohla by nastat situace, že všechny cykly budou využívat prodlouženou pracovní dobu. Takový stav by nebyl žádoucí, a proto musíme počet prodloužených pracovních dob omezit. Počet prodloužených cyklů snížíme na 4, tj. y k se může rovnat jedné pouze ve čtyřech případech, v ostatních cyklech se y k bude rovnat nule a bude použita standardní délka pracovní doby V . Tuto podmínku vyjádříme výrazem n 1

y k 1

k

 4.

(2.23)

Podmínka (2.22) zaručí, že budou využity právě čtyři cykly s delší pracovní dobou V  W . Pokud bychom chtěli zajistit maximálně čtyři nebo povolit méně delších cyklů, nahradili bychom výraz (2.22) novou upravenou podmínkou n 1

y k 1

k

4

(2.24)

- 14 -

Dalšími podmínkami, které jsou nezbytné pro model 2, jsou smyčkové podmínky. Vyjdeme opět z matematického modelu rozvozní úlohy, tentokrát však v úpravě pro model 1. Podmínku (2.15) upravíme takovým způsobem, abychom ji mohli použít v modelu 2. Nejprve musíme podmínku upravit, protože proměnné využívají nový index k , kde k  1,2,...., n  1 . Poté přidáme možnost delších cyklů. Nová podmínka bude mít následující tvar

t ik  s j  d ij  V  W 1  xijk   t kj , i  1,2,..., n, j  2,3,..., n , k  1,2,..., n  1 .

Výrazy v závorkách roznásobíme

t ik  s j  d ij  V  Vxijk  W  Wxijk   t kj , t ik  s j  d ij  V  Vxijk  W  Wxijk  t kj ,

i  1,2,..., n, j  2,3,..., n , k  1,2,..., n  1

(2.25)

V modelu nesmí chybět ani podmínka, která zajistí, že proměnná t1k se bude rovnat nule. Tato podmínka zaručuje, že vyčerpaná pracovná doba se na začátku každého cyklu bude rovnat nule, pro každé k  1,2,..., n  1 .

t1k  0 ,

k  1,2,..., n  1 .

(2.26)

Model ještě musíme doplnit o poslední dvě podmínky. První podmínka zaručí, že návštěva uzlu se uskuteční právě v jednom cyklu (Fábry J., 2006). n

n

i 1

i 1

 xijk   x kji ,

j  2,3,..., n, k  1,2,..., n  1 . (2.27)

Nerovnice (2.27) zaručuje v obecném případě, že každé vozidlo odjede z výchozího místa nejvýše jednou, tzn. některá vozidla nemusí vyjet (Fábry J., 2006). V tomto modelu však bude mít podmínka odlišnou interpretaci. Nerovnice zaručuje, že počet cest, které revizní technik uskuteční, se bude rovnat nebo bude menší než n  1 (Fábry J., 2006). n

x i 1

k 1j

 1,

k  1,2,..., n  1 .

- 15 -

(2.28)

Účelová funkce bude mít oproti předcházejícím úlohám odlišný tvar. Opět budeme hledat její minimální hodnotu. Do účelové funkce ještě přidáme indexy k , kde k  1,2,..., n  1 a provést součet i přes tento nový index. Nový tvar účelové funkce tedy

bude n

n 1

n

 d i 1 j 1 k 1

ij

xijk .

(2.29)

Nyní již máme připraveny všechny omezující podmínky a můžeme z nich sestavit matematický model: minimalizovat n

n 1

n

z   d ij xijk i 1 j 1 k 1

za podmínek n

n 1

 x j 1 k 1

n

n 1

 x i 1 k 1

k ij

 1,

i  2,3,..., n, k  1,2,..., n  1,

k ij

 1,

j  2,3,..., n, k  1,2,..., n  1 ,

t ik  s j  d ij  V  Vxijk  W  Wxijk  t kj ,

i  1,2,..., n, j  2,3,..., n , k  1,2,..., n  1

t ik  d j1 x kj1  V  Wy k , n 1

y k 1

k

i  2,3,..., n, k  1,2,..., n  1,

 4,

t1k  0 , n

x

  x kji ,

j  2,3,..., n, k  1,2,..., n  1 ,

k 1j

 1,

k  1,2,..., n  1 ,

x i 1

n

k ij

i 1

n

k  1,2,..., n  1 ,

i 1

xijk  0,1,

i  1,2,..., n, j  1,2,..., n ,

- 16 -

k  1,2,..., n  1 ,

y k  0,1,

k  1,2,..., n  1

z ijk  0,1,

i  1,2,..., n, j  1,2,..., n

k  1,2,..., n  1 .

2.5 Heuristické metody Heuristiky jsou metody, kterými lze dospět k přípustným řešením, ale dosažené řešení nemusí být optimální. Úloha obchodního cestujícího a rozvozní úloha patří mezi NP-obtížné úlohy (Pelikán J., 1999). Při vysokém počtu proměnných nemusí optimalizační algoritmy dospět k řešení v reálném čase. V takových případech je výhodné zvolit některou z heuristických metod. Výhody ze získání výsledků v krátké době převáží nevýhody ze získání výsledků odchýlených od optimálního řešení.

2.5.1 Heuristiky pro úlohu obchodního cestujícího Metoda nejbližšího souseda Postup (Pelikán J., 1999): Krok 1. Zvolíme počáteční uzel (v našem případě vždy uzel 1) a zařadíme ho na první místo na trase. První řádek v matici s časy přejezdů proškrtneme. Krok 2. V matici časů jízd zvolíme řádek odpovídající poslednímu zařazenému uzlu. V řádku nalezneme minimum z neproškrtnutých prvků matice. Sloupec, ve kterém leží minimální prvek, zařadíme za poslední uzel na trase. Proškrtneme řádek, ve kterém jsme hledali minimum a sloupec, v němž toto minimum leží. Krok 3. Opakujeme krok 2, dokud matice časů jízd obsahuje nevyškrtnuté prvky. V opačném případě následuje krok 4.

- 17 -

Krok 4. Za poslední zařazený uzel přidáme počáteční uzel, abychom dostali uzavřený okruh.

Metoda výhodnostních čísel Postup (Pelikán J., 1999): Krok 1. Nejdříve spočítáme matici výhodnostních čísel S  sij . Její prvky dostaneme podle předpisu sij  d i1  d1 j  d ij ,

i  2,3,..., n, j  2,3,..., n, i  j ,

kde D  d ij  je matice obsahující časy přejezdů mezi uzly. Krok 2. V matici S nalezneme největší výhodnostní číslo s ij . Zapíšeme cestu i  j do výsledného cyklu. Abychom předešli vzniku parciálních cyklů, vyškrtneme prvek s ji , řádek i a sloupec j . Krok 3. Nyní vybíráme z matice S maximum v řádku j . Toto řádkové maximum je prvek s jk . Nalezneme maximum ve sloupci i (prvek s li ). Porovnáme maximální hodnoty v řádku a ve sloupci. V případě, že s jk  sli , zařadíme uzel k na konec cesty. Vyškrtneme prvek spojující konec a začátek cesty, tj. s ki a řádek j . Provedeme substituci j  k . V opačném případě, když bude s jk  sli , zařadíme uzel l na začátek cesty. Vyškrtneme prvek spojující konec a začátek cesty s lj a řádek l . Provedeme substituci

il.

- 18 -

Krok 4. Opakujeme krok 3, dokud nebudou z matice S vyškrtány všechny prvky. Krok 5. Doplníme výchozí uzel na začátek a konec cesty a tím spojíme cestu do cyklu.

Metoda nejlevnějšího vkládání Postup (Pelikán J., 1999): Krok 1. Vybereme výchozí uzel (budeme volit uzel 1). Krok 2. V prvním řádku matice s časy přejezdů D  i, j nalezneme největší prvek

 d  max d  . Vytvoříme uzavřenou cestu 1  s  1 . 1j j  1s  Krok 3. Nalezneme hranu i, j  ležící na již vytvořeném cyklu a uzel k neležící na vytvořeném cyklu tak, aby výraz d ik  d kj  d ij byl minimální. Hledáme tedy uzel k , jehož přidáním do cyklu se cesta co nejméně prodlouží. Uzel k přidáme do cesty mezi uzly i a j . Krok 4. Opakujeme krok 3, dokud nejsou zařazeny všechny uzly do cyklu.

2.5.2 Heuristiky pro rozvozní úlohu – model 1 Heuristické metody pro řešení rozvozní úlohy se odlišují od metod pro řešení úlohy obchodního cestujícího. V jejich algoritmu musí být neustále kontrolováno, zda po zařazení nového uzlu nebude překročena kapacita vozidla, či v našem případě pracovní doba. Pokud by k tomu došlo, musí být uzel na trase ignorován a zkoušíme najít jiný nezařazený uzel. Ignorovaný uzel pak zkoušíme zařadit do jiného cyklu. Pokud není pracovní doba vyčerpána přesně, musíme prohledávat všechny nezařazené

- 19 -

uzly pro případ, že by se ještě mohly do aktuálního cyklu vejít. V heuristických metodách pro řešení úlohy obchodního cestujícího každý uzel ihned zařadíme, ale v heuristikách pro řešení rozvozní úlohy tyto prvky zkoušíme zařadit několikrát. To činí algoritmy pro rozvozní úlohy výpočetně náročnějšími. Nejprve zavedeme označení pro snazší orientaci. Matici se zadáním časů přejezdů označíme jako matici A s prvky a ij . Matici, kterou budeme při vybírání uzlů vyškrtávat, označíme jako matici B s prvky bij . V aplikaci Heuristiky je pro řešení rozvozní úlohy - model 1 pracovní doba označena jako délka cyklu 1.

Metoda nejbližšího souseda Postup: Krok 1. Zvolíme výchozí uzel (v našem případě volíme vždy uzel 1) a zařadíme ho na první místo v nového cyklu. Krok 2. Z matice B vyškrtneme všechny řádky a sloupce, které odpovídají všem dříve zařazeným uzlům. Z matice B ještě vyškrtneme první sloupec. Krok 3. V řádku, který odpovídá poslednímu uzlu zařazenému do cyklu, nalezneme minimum. Minimum leží v řádku i a ve sloupci j . Minimum v matici je prvek bij . Krok 4. Otestujeme, zda lze uzel zařadit do cyklu. Sečteme časy přejezdů od prvního do posledního zatím zařazeného uzlu a doby trvání činností v uzlech. K tomuto součtu ještě přičteme dobu přejezdu z uzlu i do j , tj. prvek matice 𝐵, bij a také dobu trvání činnosti v uzlu j . Ještě musíme připočítat návrat do výchozího uzlu. Připočteme čas přejezdu mezi uzlem i a uzlem 1. Tento součet porovnáme s pracovní dobou.

- 20 -

V případě, že je součet menší nebo roven pracovní době, zařadíme uzel j za poslední uzel v cyklu. Jestliže je součet větší než pracovní doba, nemůžeme uzel j zařadit do cyklu. V obou případech vyškrtneme sloupec j z matice B . Krok 5. Opakujeme kroky 3 a 4, dokud nevyškrtáme celou matici B , potom pokračujeme krokem 6. Krok 6. Uzavřeme cyklus zapsáním výchozího uzlu. Krok 7. V případě, že ještě nejsou zařazeny všechny uzly, přejdeme na krok 1 a zařazujeme prvky do nového cyklu. Pokud jsou všechny uzly zařazeny, výpočet končí.

Metoda výhodnostních čísel Postup: Krok 1. Jako první spočítáme matici výhodnostních čísel S . Její prvky vypočítáme z matice časů přejezdů sij  ai1  a1 j  aij ,

i, j  2,3,..., n, i  j .

Kde A  aij  je matice obsahující časy přejezdů mezi uzly. Krok 2. Vytvoříme matici B , jejíž rozměr je n  n a její prvky jsou bij  sij . V matici B vyškrtáme všechny řádky a sloupce odpovídající dříve zařazeným uzlům. Krok 3. V matici B nalezneme největší výhodnostní číslo bij .

- 21 -

Krok 4. Otestujeme, zda lze uzly i a j zařadit do cyklu. Sečteme časy přejezdů na cestě 1  i  j  1 a činnosti v uzlech i a j .

Pokud je součet menší nebo roven pracovní době, zapíšeme cestu i  j do výsledného cyklu. Z matice B vyškrtneme prvek b ji , řádek i a sloupec j a pokračujeme krokem 5. V případě, že součet je větší než pracovní doba, vyškrtneme prvek bij . Pokud ještě nejsou vyškrtnuty všechny prvky matice B , pokračujeme krokem 3. Pokud jsou všechny prvky v matici vyškrtnuty, pokračujeme krokem 6. Krok 5. Nyní budeme vybírat z matice B maximum v řádku

j . Toto maximum

označíme b jk . Vybereme také maximum ve sloupci a označíme ho bli . Porovnáme maxima v řádku a ve sloupci. V případě, že b jk  bli , otestujeme délku cyklu. Sečteme časy přejezdů na cestě 1  i  ...  j  k  1 a činnosti v uzlech i až k . V případě, že součet je větší než délka

cyklu 1, vyškrtneme prvek b jk z matice B . Pokud jsou v řádku j nebo sloupci i nějaké nevyškrtané prvky, pokračujeme opět krokem 5, jinak pokračujeme krokem 7. Pokud je součet menší než délka cyklu 1, zařadíme uzel k na konec cesty. Vyškrtneme prvek bki a řádek j . Provedeme substituci j  k a opakujeme krok 5. V opačném případě, když b jk  bli , otestujeme délku cyklu. Sečteme časy přejezdů na cestě 1  l  i  ...  j  1 a činnosti v uzlech l až j . Když je součet větší než délka cyklu 1, vyškrtneme prvek bli . Pokud jsou v řádku j nebo sloupci i ještě nějaké nevyškrtnuté prvky, pokračujeme krokem 5, jinak přejdeme na krok 7. Pokud je součet cesty a činností menší než délka cyklu 1, zařadíme uzel l na začátek cesty. Vyškrtneme prvek blj a sloupec i z matice B . Provedeme substituci i  l a pokračujeme opět krokem 5.

- 22 -

Krok 6. Pokud máme vyškrtanou celou matici B a v cyklu ještě nejsou zařazeny žádné prvky, zařadíme do cyklu první nezařazený uzel a pokračujeme krokem 7. Krok 7. Na začátek cyklu dosadíme výchozí uzel 1. Na konec cyklu dosadíme uzel 1. Pokud ještě máme nezařazené uzly, začneme nový cyklu a pokračujeme krokem 2. V opačném případě výpočet končí.

Metoda nejlevnějšího vkládání Postup: Krok 1. Vybereme výchozí uzel (budeme volit uzel 1) Krok 2. Vytvoříme matici B , která má rozměr n  n a prvky bij odpovídají prvkům matice s časy přejezdů A , tj. bij  aij . Vyškrtneme řádky a sloupce, které odpovídají již zařazeným uzlům. Krok 3. U prvního řádku matice A vybereme největší prvek a1s . Vytvoříme uzavřenou cestu 1  s  1 . Krok 4. Nalezneme hranu i, j  , která leží na již vytvořeném cyklu a uzel 𝑘, který neleží na vytvořeném cyklu tak, abychom minimalizovali výraz bik  bkj  bij . Snažíme se tedy najít uzel k , po jehož přidání se cesta co nejméně prodlouží. Otestujeme délku cyklu. Zkusíme přidat uzel k do vytvořené cesty. Pokud je součet menší nebo roven délce cyklu 1, ponecháme uzel k zařazen v cyklu a pokračujeme krokem 4. Pokud jsou zařazeny všechny uzly, pokračujeme krokem 5.

- 23 -

V případě, že je součet větší než délka cyklu 1, vymažeme uzel k z cyklu. Vyškrtneme minimum výrazu bik  bkj  bij a mezi ostatními hledáme nové minimum. Pokud jsou všechny výrazy vyškrtány, pokračujeme krokem 5. Krok 5. Pokud existují nezařazené uzly, pokračujeme krokem 2, jinak výpočet končí.

2.5.3 Heuristiky pro rozvozní úlohu – Model 2 V aplikaci Heuristiky je pro řešení rozvozní úlohy - model 2 standardní délka pracovní doby označena jako délka cyklu 1. Pro delší pracovní dobu je použito označení délka cyklu 2. U modelu heuristik pro model 2 musíme zavést tři matice. První matice je shodná s modelem 1. Matici obsahující časy přejezdů mezi uzly označíme jako matici A s prvky a ij . Nyní musíme rozdělit uzly do dvou množin. Zavedeme pravidlo, podle

kterého rozdělíme uzly do dvou množin. Pro každý uzel i , kde i  2,3,..., n , spočítáme výraz (2.31) a porovnáme ho s délkou cyklu 1. čas přejezdu 1, i  + činnost v uzlu i  + čas přejezdu i,1 .

(2.30)

V případě, že výraz (2.31) bude větší než délka cyklu 1, zařadíme uzel i do množiny U . Uzly, pro které bude výraz (2.31) menší než délka cyklu 1, zařadíme do množiny V . Vytvoříme matici, která má stejný rozměr n  n jako matice A , ale obsahuje pouze řádky a sloupce uzlů z množiny U . Ostatní prvky matice jsou proškrtnuty. Tuto matici označíme B a její prvky bij . Vytvoříme matici C s prvky cij . Matice bude mít rozměr n  n . Budou vyplněny pouze řádky a sloupce z množiny V . Ostatní prvky matice budou proškrtnuty. V modelu 2 je povoleno použít dvě různé délky cyklu. V heuristických metodách pro model 2 je nejprve použita délka cyklu 2 a po vyčerpání počtu cyklů 2 je ve všech následujících cyklech použita délka cyklu 1. Při uvádění podmínky pro výběr délky cyklu, by se heuristiky staly méně přehledné. Pro lepší přehlednost je toto

- 24 -

pravidlo uvedeno pouze zde a v popisu heuristik je již uváděna pouze délka cyklu nebo pracovní doba.

Metoda nejbližšího souseda Postup: Krok 1. Zvolíme výchozí uzel (budeme volit vždy uzel 1) a zařadíme ho na první místo v novém cyklu. Krok 2. Vytvoříme matice B a C podle výše uvedeného postupu. Z matice B i C vyškrtneme řádky a sloupce, které odpovídají dříve zařazeným uzlům. Z matic B a C vyškrtneme první sloupec. Pokud matice B obsahuje nějaké prvky, pokračujeme krokem 3, jinak pokračujeme krokem 6. Krok 3. V řádku matice B , který odpovídá poslednímu zařazenému uzlu, najdeme minimum, tj. prvek bij . Krok 4. Otestujeme, zda lze prvek zařadit do cyklu. Sečteme časy přejezdů mezi uzly v cyklu a přičteme bij a také dobu trvání činnosti v uzlu j . Ještě připočítáme dobu návratu do výchozího uzlu, tj. cestu z uzlu j do uzlu 1. Tento součet porovnáme s pracovní dobou. V případě, že je součet menší nebo roven délce pracovní doby, zařadíme uzel j na poslední místo v cyklu. Jestliže je součet větší než pracovní doba (délka cyklu), nezařadíme uzel j do cyklu. V obou případech však vyškrtneme řádek j z matice B . Přejdeme na krok 5.

- 25 -

Krok 5. Opakujeme krok 3 a 4, dokud nevyškrtáme celou matici B . Krok 6. Pokud jsou již v aktuálním cyklu zařazeny nějaké uzly, vyškrtneme řádek 1 z matice C . Krok 7. V řádku matice C , který odpovídá poslednímu zařazenému uzlu, najdeme minimum cij . Krok 8. Testujeme, zda můžeme prvek zařadit do cyklu. Provedeme součet časů přejezdů mezi uzly v cyklu a přičteme doby trvání činností v zařazených uzlech. K tomuto součtu ještě připočteme dobu přejezdu cij a také dobu trvání činnosti v uzlu j . Musíme ještě připočítat dobu návratu z uzlu j zpět do uzlu 1. Součet opět porovnáme s pracovní dobou. Pokud bude součet menší nebo roven pracovní době, zařadíme uzel j na poslední místo v cyklu. V případě, že bude součet větší než pracovní doba, nemůžeme uzel j do cyklu zařadit. V obou případech vyškrtneme řádek j z matice C a přejdeme na krok 9. Krok 9. Krok 7 a 8 opakujeme, dokud matice C ještě obsahuje nevyškrtané prvky. Krok 10. V případě, že nejsou zařazeny všechny uzly do cyklů, pokračujeme krokem 1 a vytvoříme nový cyklus, jinak výpočet končí.

- 26 -

Metoda výhodnostních čísel Postup: Krok 1. Nejdříve spočítáme matici výhodnostních čísel S . Její prvky vypočítáme z matice časů přejezdů podle výrazu sij  ai1  a1 j  aij ,

i, j  2,3,..., n, i  j ,

kde A  aij  je matice obsahující časy přejezdů mezi uzly. Krok 2. Vytvoříme matice B a C výše uvedeným postupem. Z matic B a C vyškrtneme řádky a sloupce, které odpovídají již dříve zařazeným uzlům. Z matic B a

C vyškrtneme první řádek a sloupec. Pokud matice B obsahuje nějaké nevyškrtnuté prvky, pokračujeme krokem 3, jinak pokračujeme až krokem 7. Krok 3. V matici B nalezneme největší výhodnostní číslo bij . Krok 4. Budeme testovat, zda lze uzly i a j zařadit do cyklu. Sečteme časy přejezdů na cyklu 1  i  j  1 a činnosti v uzlech i a j . Pokud je tento součet menší nebo roven délce cyklu, zapíšeme cestu i  j do výsledného cyklu a vyškrtneme prvek b ji , řádek i a sloupec j . Pokračujeme krokem 5. Jestliže je součet větší než délka cyklu, vyškrtneme prvek bij . Pokud ještě nejsou vyškrtnuty všechny prvky matice B , pokračujeme krokem 3. Pokud jsou všechny prvky v matici vyškrtnuty, pokračujeme krokem 10. Krok 5. Vybereme z matice B maximum v řádku j . Toto maximum označíme b jk . Vybereme také maximum ve sloupci i a označíme ho bli . Porovnáme prvky b jk a bli .

- 27 -

Jestliže je b jk  bli , otestujeme délku cyklu. Sečteme časy přejezdů na cyklu 1  i  ...  j  k  1 a činnosti v uzlech i až k . Pokud je součet větší než délka cyklu,

vyškrtneme prvek b jk z matice B . Pokud jsou v řádku j nebo sloupci i nějaké nevyškrtnuté prvky, pokračujeme opět krokem 5, jinak pokračujeme krokem 10. Pokud je součet menší než délka cyklu, zařadíme uzel k na konec cesty. Vyškrtneme prvek bki a řádek j . Provedeme substituci j  k a pokračujeme krokem 5. V opačném případě, tj. b jk  bli , otestujeme délku cyklu. Sečteme časy přejezdů na cestě 1  l  i  ...  j  1 a činnosti v uzlech l až j . Pokud je součet větší než délka cyklu, vyškrtneme prvek bli . Pokud jsou v řádku j nebo sloupci i nevyškrtnuté prvky, budeme pokračovat krokem 5, jinak přejdeme na krok 10. Pokud je součet cesty a činností menší než délka cyklu, zařadíme uzel l na začátek cesty. Vyškrtneme prvek blj a sloupec i z matice B . Substituujeme i  l a pokračujeme opět krokem 5. Krok 6. Pokud máme vyškrtanou celou matici B a v množině U jsou stále ještě nezařazené uzly, zařadíme do cyklu první nezařazenný uzel z množiny U . Proměnné i a j budou mít shodně hodnotu indexu zařazovaného uzlu. Pokračujeme krokem 9. Krok 7. V matici C najdeme nejvyšší výhodnostní číslo cij . Krok 8. Otestujeme, zda lze uzly i a j zařadit do cyklu. Sečteme časy přejezdů na cyklu 1  i  j  1 a činnosti prováděné v uzlech i a j .

V případě, že je tento součet menší nebo roven délce cyklu, zapíšeme cestu i  j do výsledného cyklu a vyškrtneme prvek c ji , řádek i a sloupec j . Budeme pokračovat krokem 10.

- 28 -

Jestliže bude součet větší než délka cyklu, vyškrtneme z matice C prvek cij . Pokud jsou v matici C ještě nevyškrtnuté prky, pokračujeme krokem 7. Pokud jsou všechny prvky v matici C vyškrtnuty, pokračujeme krokem 12. Krok 9. Pokud je první uzel i v cyklu z množiny U , musíme přidat do matice C sloupec i z matice A . Jestliže je poslední uzel j v cyklu z množiny U , přidáme do matice C řádek j z matice A . V obou případech potom vyškrtneme prvek c ji z matice

C. Krok 10. V matici C vybereme největší prvek v řádku j a označíme ho c jk . Opět vybíráme nejvyšší hodnotu ve sloupci i a označíme ji cli . Porovnáme prvky c jk a cli . V případě, že c jk  cli , testujeme délku cyklu. Sečteme časy přejezdů na trase 1  i  ...  j  k  1 a činnosti v uzlech i až k . Když bude součet větší než délka cyklu,

vyškrtneme prvek c jk z matice C . Pokud jsou v řádku j nebo sloupci i nějaké nevyškrtnuté prvky, pokračujeme opět krokem 10. Jinak přejdeme na krok 12. Pokud je součet menší než délka cyklu, zařadíme uzel k na konec trasy. Vyškrtneme prvek c ki a řádek j . Provedeme substituci j  k a pokud jsou v řádku j a sloupci i nevyškrtnuté prvky, pokračujeme krokem 10, jinak přejdeme na krok 12. V případě, že c jk  cli , opět otestujeme délku cyklu. Sečteme časy přejezdů na trase 1  l  i  ...  j  1 a činnosti v uzlech l až j . Pokud je součet větší než délka cyklu, vyškrtneme z matice C prvek cli . Pokud jsou v řádku j nebo sloupci i nevyškrtnuté prvyk, pokračujeme krokem 10, jinak přejdeme na krok 12. Pokud je součet cesty a činností menší než délka cyklu, zařadíme uzel l na začátek cesty. Vyškrtneme prvek clj a sloupec i z matice B . Provedeme substituci i  l . Pokud jsou v řádku j a sloupci i nevyškrtnuté prvky, pokračujeme krokem 10, jinak přejdeme na krok 12.

- 29 -

Krok 11. Pokud máme vyškrtanou celou matici C a v cyklu ještě není zařazen žádný uzel, zařadíme do cyklu první nezařazený uzel z množiny V a pokračujeme krokem 12. Krok 12. Na začátek a konec cyklu dosadíme uzel 1 (výchozí uzel). Pokud ještě máme nezařazené uzly, začneme nový cyklu a pokračujeme krokem 2. Pokud jsou všechny prvky zařazené, výpočet končí.

Metoda nejlevnějšího vkládání Postup: Krok 1. Vybereme výchozí uzel (zvolíme uzel 1). Krok 2. Vytvoříme matici B a C podle výše uvedeného postupu. Vyškrtneme z matic B a C řádky a sloupce odpovídající již dříve zařazeným uzlům. Pokud je matice B

prázdná, přejdeme na krok 6, jinak pokračujeme krokem 3. Krok 3. V prvním řádku matice B nalezneme největší prvek b1s . Vytvoříme cestu

1  s  1. Krok 4. Najdeme hranu i, j  , která leží na vytvořeném cyklu a uzel k z množiny U , který neleží na vytvořeném cyklu tak, abychom minimalizovali výraz bik  bkj  bij . Hledáme uzel k , který nejméně prodlouží cyklus. Testujeme délku cyklu. Zkusíme přidat uzel k do vytvořeného cyklu. Sečteme časy přejezdů na cyklu a činnosti v uzlech. Pokud je součet menší nebo roven délce cyklu, ponecháme uzel k zařazený v cyklu a pokračujeme krokem 4.

- 30 -

V opačném případě, když je součet větší než délka cyklu, vyškrtneme uzel k z cesty. Vyškrtneme také minimální výraz bik  bkj  bij a mezi ostatními hledáme nové minimum. Pokud jsou všechny výrazy vyškrtány, pokračujeme krokem 6. Krok 5. V prvním řádku matice C nalezneme největší prvek c1s . Vytvoříme cyklus

1  s  1. Krok 6. Hledáme hranu i, j  , která leží na vytvořené cestě a uzel k z množiny V , který neleží na vytvořené cestě tak, abychom minimalizovali výraz cik  ckj  cij . Snažíme se najít uzel k , který co nejméně prodlouží cestu. Otestujeme délku cyklu. Přidáme uzel

k do vytvořeného cyklu. Sečteme časy přejezdů a činnosti prováděné v uzlech. V případě, že je součet menší nebo roven délce cyklu, necháme uzel k zařazený v cyklu a pokračujeme krokem 6. Pokud je naopak součet větší než délka cyklu, vyškrtneme uzel k z cesty. Vyškrtneme také minimum výrazu cik  ckj  cij a mezi zbylými hledáme nové minimum. Pokud jsou všechny výrazy vyškrtány, pokračujeme krokem 7. Krok 7. Pokud ještě máme nezařazené uzly, pokračujeme krokem 2, v opačném případě výpočet končí.

- 31 -

3. Aplikace v MS Excel Součástí diplomové práce je aplikace Heuristiky. Je vytvořena v jazyce Visual Basic for Applications (VBA) v programu MS Excel. Tato kapitola slouží jako manuál k aplikaci Heuristiky. Popíši zde ovládání aplikace, zadávání dat a také popis možných chybových hlášení, která se můžou objevit při běhu aplikace.

3.1 Menu Všechny ovládací prvky programu jsou na listu „Menu“.

Obrázek 3.1 Menu

Jak je patrné z obrázku 3.1, menu je rozděleno do tří částí.

- 32 -

V první části nazvané Úloha obchodního cestujícího si uživatel pomocí zaškrtávacích tlačítek zvolí, kterou z heuristik chce při výpočtech použít. K dispozici má následující možnosti: 

metoda nejbližšího souseda,



metoda výhodnostních čísel a



metoda nejlevnějšího vkládání.

Je možné zvolit si pro výpočet jednu nebo více heuristik současně. Ve druhé části pojmenované Rozvozní úloha má uživatel na výběr heuristiku z následujících možností: 

metoda nejbližšího souseda,



metoda výhodnostních čísel a



metoda nejlevnějšího vkládání.

Při volbě rozvozní úlohy je potřeba specifikovat délku cyklu a případně i jejich počet. Pro potřeby této diplomové práce je možno zadávat dvě různé délky cyklů. V případě řešení rozvozní úlohy s jednou délkou cyklu (kapacitou) je potřeba zadat stejné hodnoty pro délku cyklu 1 a pro délku cyklu 2. V případě použití různě dlouhých cyklů je vždy potřeba zadat cyklus 2 delší než cyklus 1. Rovněž je potřeba věnovat pozornost nastavení počtu delších cyklů. Poslední část ovládacího menu tvoří dvě tlačítka. Tlačítko Nové zadání slouží k vytvoření listů pro zadávání matic a vektoru a přípravě jejich struktury pro snadnější zadávání. Tlačítkem Výpočet se spouští výpočet vybraných heuristik.

3.2 Zadávání dat Před spuštěním výpočtů je nutné zadat všechna potřebná data. K výpočtům potřebujeme znát matici vzdáleností mezi uzly, matici s časy přejezdů mezi uzly a vektor činností vykonávaných v uzlech. Matice vzdáleností musí být symetrická podle hlavní diagonály. Musí mít rozměry n  n , přičemž n  3 . Musíme ji zadat na list „Vzdalenosti“. První řádek a

- 33 -

sloupec je rezervován pro záhlaví s názvy uzlů. Názvy z prvního sloupce jsou pak použity při prezentaci výsledků. Pro matici s časy přejezdů platí analogická omezení. Matice musí být symetrická podle hlavní diagonály s rozměry n  n , kde n  3 . Matice s časy přejezdů mezi uzly se zadává do listu „Cas“. Do prvního řádku a sloupce opět patří názvy uzlů. První prvek matice se zadává do buňky „B2“, resp. „R2C2“ při použití nastavení odkazů R1C1. Požadované rozměry vektoru činností jsou n  1 , přičemž n  3 . Zadává se do listu „Cinnosti“. První řádek slouží jako záhlaví a první sloupec je určen pro názvy uzlů. První prvek vektoru se zadává opět do buňky „B2“, resp. „R2C2“. Ke snadnějšímu zadávání vstupních údajů slouží tlačítko Nové zadání na listu „Menu“. Po jeho stisknutí se objeví následující okno (obrázek 3.2).

Obrázek 3.2 Počet uzlů

Do tohoto okna uživatel zadá počet uzlů. Hodnota v okně je implicitně nastavena na hodnotu 3. Počet uzlů musí být celé kladné číslo větší nebo rovno 3. V případě zadání kladného čísla, které není celé, bude zaokrouhleno. Při zadání jiných než požadovaných hodnot, např. písmen, záporných čísel apod., se objeví chybové hlášení (obrázek 3.3).

Obrázek 3.3 Počet uzlů musí být celé kladné číslo větší nebo rovno 3

- 34 -

Při nesprávném zadání a stisknutí tlačítka „OK“ na okně chybového hlášení se znovu objeví menu aplikace. Při vytváření nového zadání budou všechny údaje na listech „Vzdalenosti“, „Cas“ a „Cinnosti“ smazány. Po správném zadání počtu uzlů aplikace vytvoří tři nové listy a vytvoří na nich strukturu, která usnadňuje zapsání matic a vektoru. Na listu „Vzdalenosti“ a „Cas“ bude vytvořena následující struktura (obrázek 3.4). Na obrázku list „Vzdalenosti“ v případě, že 𝑛 = 5.

Obrázek 3.4 List Vzdalenosti

Listy „Vzdalenosti“ a „Cas“ se liší pouze textem v buňce „A1“. První řádek a sloupec jsou určeny pro názvy uzlů. Uzly jsou pojmenovány Uzel 1 až Uzel n . Názvy uzlů lze změnit. Aby se změna názvů projevila při prezentaci výsledků, je potřeba přejmenovat uzly v prvním sloupci na listu „Vzdalenosti“. Názvy uzlů v prvním řádku a na listu „Cas“ a „Cinnosti“ se v aplikaci nevyužívají a slouží pouze uživateli pro snadnější orientaci při zadávání dat. Na listu „Cinnosti“ je připravena struktura znázorněná na následujícím obrázku (obrázek 3.5). Opět je uvedena ilustrace pro n  5 .

- 35 -

Obrázek 3.5 List Cinnosti

První řádek slouží jako záhlaví. V prvním sloupci jsou uvedeny názvy uzlů. Do sloupce „B“ uživatel zadá dobu trvání činnosti v uzlech. První uzel je výchozím uzlem a proto zde neprobíhá žádná činnost. Hodnota v této buňce je již přednastavena na hodnotu 0. Po vyplnění obou matic a vektoru lze spustit výpočet.

3.3 Výpočet Když jsou obě matice a vektor se vstupními daty vyplněny, můžeme přejít k výpočetní fázi. Výpočet heuristik se spouští tlačítkem „Výpočty“ v menu. Nejprve je potřeba vybrat heuristiky, které chceme použít pro výpočet. Výběr se provádí zaškrtávacími tlačítky v menu. Můžeme vybrat jednu či více heuristik a můžeme také kombinovat výběr heuristik pro úlohu obchodního cestujícího s heuristikami pro výpočet rozvozní úlohy. Vždy však musí být zvolena alespoň jedna metoda. V opačném případě se objeví uživateli následující varování (obrázek 3.6).

Obrázek 3.6 Není vybrána žádná heuristika

- 36 -

Po stisknutí tlačítka „OK“ varování zmizí a můžeme vybrat požadovanou heuristiku a pokračovat ve výpočtech. V případě, že uživatel nevytvořil, nebo smazal list „Vzdalenosti“, objeví se chybové hlášení (obrázek 3.7).

Obrázek 3.7 Musí být vytvořen list Vzdalenosti a zadány hodnoty

Obdobná chybová hlášení se vyskytnou i v případě chybějícího listu „Cas“ (obrázek 3.8), resp. listu „Cinnosti“ (obrázek 3.9).

Obrázek 3.8 Musí být vytvořen list Cas a zadány hodnoty

Obrázek 3.9 Musí být vytvořen list Cinnosti a zadány hodnoty

V situaci, kdy listy „Vzdalenosti“, „Cas“ a „Cinnosti“ existují, ale matice „Vzdalenosti“ nebo „Cas“ neobsahuje žádné hodnoty, zobrazí se chybové hlášení

- 37 -

(obrázek 3.10), resp. (obrázek 3.11) se souřadnicemi prvního prvku, ve kterém chybí údaje.

Obrázek 3.10 Matice vzdáleností neobsahuje žádné hodnoty

Obrázek 3.11 Matice časů přejezdů neobsahuje žádné hodnoty

Chybějící údaje na listu “Cinnosti” oznamuje chybové hlášení na obrázku 3.12.

Obrázek 3.12 Vektor činností nesmí obsahovat prázdné buňky

Mezi další chyby, kterých se může uživatel na listu “Vzdalenosti” dopustit, patří neplatný rozměr matice. Matice “Vzdalenosti” musí být vždy čtvercová o rozměru

n  n . Jestliže tvrzení neplatí, objeví se chybové hlášení (obrázek 3.13).

- 38 -

Obrázek 3.13 Matice vzdáleností není čtvercová

Nesprávný rozměr není přípustný ani u matice “Cas”. V případě, že matice není čtvercová, aplikace ohlásí chybu (Obrázek 3.14).

Obrázek 3.14 Matice časů přejezdů není čtvercová

Matice “Vzdalenosti” musí být symetrická podle hlavní diagonály. Pokud to neplatí, signalizuje to následující hlášení (obrázek 3.15), ze kterého se uživatel dozví, ve kterém prvku matice k chybnému zadání došlo.

Obrázek 3.15 Matice vzdáleností není symetrická podle hlavní diagonály

Tvrzení o symetrii podle hlavní diagonále platí i pro matici “Cas”. V opačném případě to oznámí chybové hlášení (obrázek 3.16) se souřadnicemi prvku, který pravidlo porušuje.

- 39 -

Obrázek 3.16 Matice s časy přejezdů není symetrická podle hlavní diagonály

V případě, že uživatel nevyplní do listu “Vzdalenosti” kladná čísla, ale například písmena nebo jiné znaky, chybové hlášení upozorní uživatele na první buňku, ve které není číselná hodnota (obrázek 3.17).

Obrázek 3.17 Matice vzdáleností neobsahuje čísla

Obdobné chybové hlášení s určením nesprávně zadaného prvku se objeví i u špatného zadání do matice “Cas” (obrázek 3.18).

Obrázek 3.18 Matice s časy přejezdů neobsahuje čísla

Při zadání záporných čísel do matice “Vzdalenosti” chybové hlášení odkáže uživatele na první prvek v matici, ve kterém bylo pravidlo porušeno (obrázek 3.19).

- 40 -

Obrázek 3.19 Matice vzdáleností obsahuje záporná čísla

Zadávání záporných hodnot není přípustné ani v matici “Cas”. V opačném případě bude uživatel zpozorněn chybovým hlášením se souřadnicemi prvku, který porušuje toto pravidlo (obrázek 3.20).

Obrázek 3.20 Matice s časy přejezdů obsahuje záporná čísla

Vektor činností musí být sloupcový. Když uživatel zadá na list “Cinnosti” více sloupců, bude na chybu upozorněn oznámením na obrázku 3.21.

Obrázek 3.21 Vektor činností musí tvořit pouze jeden sloupec

V situaci, kdy uživatel nezadá do vektoru “Cinnosti” žádné hodnoty, upozorní ho na chybu hlášení (obrázek 3.22).

- 41 -

Obrázek 3.22 Vektor činností je prázdný

Pokud uživatel vyplní vektor “Cinnost” nečíselnými hodnotami, upozorní ho chybové hlášení (obrázek 3.23).

Obrázek 3.23 Vektor činností musí obsahovat pouze čísla

V případě, že bude vektor “Cinnosti” obsahovat záporné hodnoty, objeví se hlášení o chybě (obrázek 3.24).

Obrázek 3.24 Vektor činností musí obsahovat pouze kladná čísla

V aplikaci jsou nastaveny minimální rozměry matice “Vzdalenosti”. Při nedodržení požadavku minimálního rozměru matice “Vzdalenosti” n  3 , upozorní uživatele hlášení (obrázek 3.25).

- 42 -

Obrázek 3.25 Minimální rozměr matice vzdáleností je 𝟑 × 𝟑

Požadavek minimálních rozměrů, n  3 , platí i pro matici “Cas”. Jejich nedodržení je oznámeno uživateli (obrázek 3.26).

Obrázek 3.26 Minimální rozměr matice s časy přejezdů je 𝟑 × 𝟑

Minimální požadavek na rozměr vektoru “Cinnosti” je 3 1 . V případě menšího počtu řádků je zobrazeno chybové okno (obrázek 3.27).

Obrázek 3.27 Minimální rozměr vektoru činností je 𝟑 × 𝟏

Následují poslední, ale neméně důležité kontroly rozměrů matic a vektoru. Matice “Vzdalenosti” a “Cas” musí mít stejný rozměr n  n a vektor “Cinnosti” musí mít rozměr n  1 , kde n  3 . Nejdříve jsou porovnány rozměry matic “Vzdalenosti” a “Cas”. Pokud matice nemají shodné rozměry, oznámí to uživateli chybové hlášení (obrázek 3.28).

- 43 -

Obrázek 3.28 Matice vzdáleností nemá stejný rozměr jako matice časů přejezdů

Další kontrola porovnává rozměr matice “Vzdalenosti” s počtem řádků vektoru “Cinnosti”. V případě nestejného rozměru je to oznámeno uživateli (obrázek 3.29).

Obrázek 3.29 Vektor činností nemá stejný počet řádků jako matice vzdáleností

Tyto dva testy stačí na ověření rozměrů dvou matic a vektoru. Shodný počet sloupců a řádků matice “Cas” a řádků vektoru “Cinnosti” vyplývá ze splnění předchozích dvou podmínek. Následující odstavce se týkají pouze výpočtů heuristik pro rozvozní úlohu. Údaje o délce a počtu cyklů je třeba vyplnit pouze při výpočtech rozvozní úlohy. Při výpočtu rozvozní úlohy je třeba zadat délku cyklu 1. V našem aplikačním příkladu se jedná o denní pracovní dobu. Pro tuto hodnotu platí pouze jedno omezení. Délka cyklu musí být kladné číslo. Při nedodržení tohoto předpokladu je chyba oznámena uživateli (obrázek 3.30).

- 44 -

Obrázek 3.30 Délka cyklu 1 musí být kladné číslo

Dalším údajem, který je potřeba vyplnit, je délka cyklu 2. Platí pro něj stejné omezení jako pro délku cyklu 1 (obrázek 3.31).

Obrázek 3.31 Délka cyklu 2 musí být kladné číslo

Délka cyklu 2 se použije v případě, kdy máme dvě různé délky cyklů. V aplikačním příkladu se jedná o dvoudenní pracovní dobu. V případě, že chceme využít pouze jednu délku cyklu, nastavíme hodnotu délka cyklu 2 stejnou jako délka cyklu 1. V případě, kdy je zadaná délka cyklu 2 menší než délka cyklu 1, objeví se hlášení o chybě (obrázek 3.32).

Obrázek 3.32 Délka cyklu 2 nesmí být menší než délka cyklu 1

Pokaždé, když využijeme dvě různé délky cyklů, musíme specifikovat počet delších cyklů 2. Hodnota počet cyklů 2 musí být vždy kladné celé číslo nebo nula. Pokud předchozí tvrzení neplatí, oznámí to uživateli chybové hlášení (obrázek 3.33).

- 45 -

Obrázek 3.33 Počet cyklů 2 musí být kladné celé číslo nebo nula

Po splnění všech předchozích podmínek se spustí algoritmus, který prozkoumá cesty z uzlu 1 do uzlu i + činnost v uzlu i + návrat do uzlu 1, pro i  2,3,..., n . Pokud doba trvání některé cesty přesáhne délku cyklu 2, je nabídnuta uživateli nová délka cyklu 2, aby mohly být do cyklu zařazeny všechny uzly (obrázek 3.34).

Obrázek 3.34 Délka cyklu musí být minimálně…

Výše zmíněný algoritmus také zjistí, kolik cyklů je delších než nastavená délka cyklu 1 a pokud je uživatelem nastavený počet cyklů 2 nižší, nabídne upravenou hodnotu, aby bylo možné zařadit všechny uzly do cyklů (obrázek 3.35).

Obrázek 3.35 Počet cyklů 2 musí být minimálně…

- 46 -

Když uživatel zadá všechny hodnoty správně, spustí se samotný výpočet všech zvolených heuristik. Výsledky heuristik se objeví na listech “Vysledky i ”, kde i je pořadové číslo listu.

- 47 -

3.4 Výsledky Výsledky vybraných heuristik se po dokončení výpočtů zobrazí na listech “Vysledky”. Tyto listy jsou pro přehlednost označeny vzestupně pořadovými čísly podle pořadí výpočtů. Nyní budu popisovat interpretaci výsledků. Jako ilustrace bude sloužit pro úlohu obchodního cestujícího příklad se třemi, resp. pro rozvozní úlohu se čtyřmi uzly. Nejdříve popíši interpretaci výsledků při výpočtech úlohy obchodního cestujícího se třemi uzly.

Obrázek 3.36 Výsledky - úloha obchodního cestujícího

Na listu s výsledky jsou uvedeny uzly v pořadí, v jakém budou ve výsledném cyklu navštíveny. Výchozí uzel je v prvním řádku tabulky a je zvýrazněn tučným písmem. U výchozího uzlu je políčko ve sloupci Činnosti proškrtnuto, protože ve výchozím uzlu neprobíhá žádná činnost. Ve sloupci jízda je uvedena hodnota 0,35. Tento údaj znamená, že doba jízdy mezí výchozím uzlem Fučíkova 153, Lužec nad Vltavou a prvním navštíveným uzlem v cyklu, Zámek Nelahozeves, Nelahozeves 1, trvá 0,35 hodiny. V posledním sloupci Vzdálenost je uvedena vzdálenost mezi výchozím uzlem – Fučíkova 153, Lužec nad Vltavou a prvním navštíveným uzlem – Zámek Nelahozeves, Nelahozeves 1. Tato vzdálenost činí 15,3 km.

- 48 -

Ve druhém uzlu cyklu (Zámek Nelahozeves, Nelahozeves 1) je ve sloupci činnost zapsána hodnota 1. Tento údaj znamená, že činnost, která je vykonána v tomto uzlu, trvá 1 hodinu. Poslední uzel cyklu je shodný s výchozím uzlem. Opět zde neprobíhá žádná činnost. Protože je to koncový uzel cyklu, je i jízda z uzlu a vzdálenost proškrtnuta. Koncový uzel je opět zvýrazněn tučně. Pod tímto soupisem uzlů s činnostmi, časy jízd a vzdálenostmi je souhrnná tabulka. V této tabulce je pro snazší orientaci ve výsledcích uveden název heuristiky, která byla k výpočtům použita. V našem případě se jedná o metodu nejbližšího souseda. Údaj TSP v závorce za názvem metody znamená zkratku Traveling Salesman Problem. Tímto nápisem se rozlišuje, zda se jedná o rozvozní úlohu nebo v našem případě o úlohu obchodního cestujícího. V tabulce jsou uvedeny součty trvání činností, součty celkové doby strávené jízdou mezi uzly a celková ujetá vzdálenost mezi uzly. Rozdíly v prezentaci výsledků rozvozní úlohy a úlohy obchodního cestujícího ilustrujeme na následujícím výpisu výsledků. Příklad na obrázku 3.37 ukazuje příklad pro čtyři uzly.

Obrázek 3.37 Výsledky – rozvozní úloha

Při srovnání obrázků 3.36 a 3.37 vidíme, že výpisy pro úlohu obchodního cestujícího a rozvozní úlohu jsou velmi podobné. I v této úloze je výchozí a koncový uzel zvýrazněn tučně. Na ilustraci vidíme, že výsledkem výpočtů jsou dva cykly. První cyklus začíná v uzlu Fučíkova 153, Lužec nad

- 49 -

Vltavou, prochází uzly Zámek Nelahozeves, Nelahozeves 1, Senovážné náměstí 2, Praha 1 a končí opět v uzlu Fučíkova 153, Lužec nad Vltavou. Tento uzel je koncový uzel prvního cyklu. Protože ještě nebyly zařazeny všechny uzly do cyklů, začne v uzlu Fučíkova 153, Lužec nad Vltavou nový cyklus. Tento cyklus obsahuje výchozí uzel, cesta pokračuje do uzlu T. G. Masaryka 115, Ústí nad Orlicí a protože jsou již všechny uzly zařazeny do cyklů, cesta pokračuje zpět do výchozího uzlu Fučíkova 153, Lužec nad Vltavou. Ze souhrnné tabulky na konci výpisu výsledků se dozvíme, že byl výpočet proveden metodou nejbližšího souseda. Nyní je však v závorce uvedena zkratka VRP. Ze zkratky slov Vehicle Routing Problem se dozvíme, že výpočty byly provedeny algoritmem modifikovaným pro rozvozní úlohu. V tabulce jsou opět uvedeny sumace trvání činností, jízdy mezi uzly a vzdáleností mezi navštívenými uzly.

- 50 -

4. Praktická část Tato kapitola je věnována řešení případu z praxe. V úvodní části popíši zadání příkladu a volbu modelů. Potom se budu zabývat sběrem a popisem dat. Provedu výpočet v programu LINGO2 a v aplikaci Heuristiky, která je součástí diplomové práce. Na závěr zhodnotím dosažené výsledky a zhodnotím přínos jednotlivých heuristik.

4.1 Zadání problému V této části práce nastíním zadání problému, který budu řešit heuristickými metodami a v programu LINGO. Pro potřeby této diplomové práce jsem získal data od pana Jindřicha Kartáka. Jedná se o fyzickou osobu podnikající na základě živnostenského oprávnění. Předmětem podnikání je: montáž, opravy, revize a zkoušky elektrických zařízení 3. Místem podnikání je Fučíkova 153, 277 06, Lužec nad Vltavou. Získal jsem seznam padesáti adres, které revizní technik navštívil. Ke každé adrese mám také popis činnosti, kterou na dané adrese vykonal a také délku trvání této činnosti. Na začátek seznamu jsem připojil místo podnikání, které bude vždy výchozím uzlem. Mým cílem bylo naplánovat trasu, aby mohl revizní technik navštívit všechna místa v co nejkratším čase a pokud to bude možné, porovnat varianty podle nákladů. Při řešení problému jsem použil tři modely. Prvním modelem je úloha obchodního cestujícího. Řešením tohoto modelu získáme nepřerušenou trasu se všemi adresami (uzly) s návratem do výchozího uzlu. Tento model má při řešení našeho problému vážný nedostatek. Trasa, kterou získáme, je nepřerušená a revizní technik by tudíž bez přestávek musel pracovat, v lepším případě, několik dní bez přerušení, než by byl cyklus ukončen znovu v místě podnikání. To není zcela realistický předpoklad, cykly proto musí být kratší. Také zákazníci by zřejmě 2 3

Optimalizační systém LINGO je produktem firmy Lindo Systems Inc. (http://www.lindo.com) [6] http://www.rzp.cz...

- 51 -

neměli pochopení, kdyby revizní technik přijel pracovat v pozdních nočních hodinách. Tento model však také vypočítám, protože může sloužit k porovnání heuristik a pokud to bude možné i k porovnání výsledku z programu LINGO. Model úlohy obchodního cestujícího není nejlepším řešením pro naši úlohu. Aby byl model realističtější, přidáme do něj pracovní dobu, tím získáme rozvozní úlohu. Pracovní dobu nastavíme na 10 hodin. Pracovní doba je o delší než běžných 8 nebo 8,5 hodin, ale v úloze zabere spoustu času cestování, proto jsem zvětšil pracovní dobu. Nyní již máme celkem realistické předpoklady. Takový model je modelem 1 rozvozní úlohy (2.18) a (2.19). Ve třetím modelu, kterým se budeme zabývat, uvolníme předpoklad pracovní doby. V modelu 1 zabere spoustu času cestování mezi uzly. Pokud zvětšíme pracovní dobu (délku cyklu), může revizní technik strávit více času podstatou svého podnikání a méně času nezbytným cestováním. V modelu 2 tedy povolíme delší pracovní dobu. Nyní máme dvě možnosti jak prodloužit pracovní dobu. První možností je zvětšit pracovní dobu o práci přesčas, např. na 12 hodin. Druhou možností je povolit služební cesty. To by znamenalo, že revizní technik bude pracovat 10 hodin, potom práci přeruší a přenocuje poblíž místa, kde se zrovna nachází. Druhý den bude znovu 10 hodin pracovat a na konci druhého dne se vrátí do výchozího uzlu. Tato varianta nese zvýšené náklady za ubytování na služební cestě, ale náklady na cestování by se měly snížit. V modelu 2 jsem se rozhodl pro druhou variantu se služebními cestami. Při zběžném nahlédnutí do adres a činností zjistíme, že např. činnost na adrese Na Průhoně 3412, Mělník 1 trvá 20 hodin. Revizní technik by musel práci přerušit, protože práci nelze vykonat v deseti hodinové pracovní době. Podobných činností najdeme ještě několik. Tento poznatek vybízí k využití služebních cest v modelu. K řešení modelů použiji heuristické metody. Budu používat metodu nejbližšího souseda, metodu výhodnostních čísel a metodu nejlevnějšího vkládání. V případě, že to bude možné, použiji výpočty pomocí programu LINGO.

- 52 -

4.2 Popis a sběr dat K výpočtům v aplikaci Heuristiky potřebujeme znát několik údajů. Jedná se o matici vzdáleností mezi uzly, matici s časy přejezdů mezi uzly a vektor s délkami trvání činností v jednotlivých uzlech. Ze zadání problému známe pouze uzly a délky trvání činností v nich. K výpočtům musíme získat matici vzdáleností a matici s časy přejezdů. Obě matice jsem získal na serveru www.mapy.cz pomocí plánovače tras.

Obrázek 4.1 Plánovač tras, první část

- 53 -

Obrázek 4.2 Plánovač tras, druhá část

V plánovači tras jsem vždy volil nejrychlejší cesty, protože úkolem je minimalizace potřebného času. Z okna v pravé části (obrázek 4.2) získáme údaje o celkové délce a celkovém času. Do plánovače jsem postupně zadal všechny párové kombinace 51 uzlů a získal jsem polovinu matic pod hlavní diagonálou. Údaje jsem vždy zkopíroval i do horní poloviny matice. Tím jsem získal potřebnou matici vzdáleností a matici s časy přejezdů mezi uzly. V dalších částech diplomové práce budu provádět i nákladovou analýzu. Pro analyzování nákladů musíme znát náklady vztažené na jeden ujetý kilometr. Dále při služebních cestách musíme znát i náklady na ubytování. Pokud chceme analyzovat náklady na jeden ujetý kilometr, musíme znát několik údajů. Důležitým faktorem je cena pohonných hmot a také typ vozidla. Od typu vozidla se odvíjí druh pohonných hmot, spotřeba a výpočet amortizace. Revizní technik v našem případě používá k podnikání automobil Škoda Octavia Combi 1.9 TDI. Z údajů o tomto voze budeme vycházet při dalších výpočtech. Druh

- 54 -

pohonných hmot je určen typem agregátu. Budeme tedy uvažovat naftu. Ceny pohonných hmot jsou značně rozkolísané a v čase se velmi liší. Při výpočtech vyjdeme z cen pohonných hmot v následující tabulce4. Průměr za měsíc Duben 08 Květen 08 Červen 08 Červenec 08 Srpen 08 Září 08 Říjen 08 Listopad 08 Prosinec 08 Leden 09 Únor 09 Březen 09 Roční průměr

Nafta 31,23 33,37 35,04 34,70 33,22 32,42 30,54 28,00 25,73 24,66 24,93 24,77 29,88

Tabulka 4.1 Průměrné ceny nafty v období duben 2008 – březen 2009

Vývoj ceny nafty v celé ČR 35,00 33,00 31,00 29,00 27,00 25,00 23,00

Nafta

Obrázek 4.3 Vývoj ceny nafty v celé ČR v období duben 2008 – březen 2009

V grafu na obrázku (4.2) vidíme nestálost cen nafty ve sledovaném období od dubna 2008 do března 2009. Při výpočtech použijeme průměrnou cenu za sledované období. Výrobce vozidla uvádí kombinovanou spotřebu automobilu 5,1 l/km5. Z těchto údajů vypočítáme náklady na pohonné hmoty vztažené k jednomu ujetému kilometru

4 5

[4] http://www.ccs.cz/... [7] http://www.skoda-auto.com/...

- 55 -

průměrná cena nafty ×kombinovaná spotřeba 100 km

=

29,88×5,1 100

= 1,524 kč/km.

Druhou složkou nákladů na jeden kilometr je opotřebení automobilu. Budeme předpokládat, že s vozem lze ujet 300 000 km, než je vůz zcela opotřeben. Nebudeme uvažovat žádnou zůstatkovou hodnotu vozidla. Budeme předpokládat, že revizní technik si poté bude chtít pořídit k podnikání nové vozidlo. Dále uvažujeme, že bude chtít srovnatelný automobil. Nejblíže k této představě je model Škoda Octavia Combi Tour. Tento model se začal vyrábět v roce 1996 a nyní již nebude vyhovovat všem nárokům. Proto budeme uvažovat nejnovější verzi Škoda Octavia Combi. Podle konfigurátoru na stránkách výrobce6 jsem našel odpovídající model Škoda Octavia Combi Classic 1.9 TDI PD DPF 77 kW. Pořizovací cena tohoto modelu je 615 050 Kč. Tuto cenu použijeme při dalším výpočtu. Hodnota opotřebení automobilu na jeden ujetý kilometr vypočítáme pořizovací cena nového vozu počet ujetých kilometrů

615050

= 300000 = 2,050 kč/km.

Další náklady, např. maziva, pojištění apod. nebudeme při výpočtech uvažovat. Celkové náklady na jeden ujetý kilometr získáme sečtením nákladů na pohonné hmoty a náklady opotřebení 1,524 + 2,050 = 3,574 kč/km. Další náklady jsou spojeny s ubytováním na služebních cestách. Opět není snadné vyjádřit náklady na ubytování jedním číslem, protože se liší podle krajů, kategorie ubytování a dalších charakteristik. Údaje, které jsou v tabulce uvedeny, jsem získal zprůměrováním několika nabídek penzionů v každém kraji7. Ve výpočtech pak použijeme cenu podle kraje, ve kterém se revizní technik ubytuje.

6 7

[1] http://cc.skoda-auto.com/cze/cc_6_finish.aspx?SessIdentifier=SI0 [3] http://www.abc-hotel.cz/cz/

- 56 -

Kraj Praha Středočeský Královéhradecký Liberecký Ústecký Karlovarský Plzeňský Jihočeský Vysočina Pardubický Jihomoravský Olomoucký Moravskoslezský Zlínský

Cena osoba/den 486,25 381,25 275,00 332,50 350,00 320,00 325,00 380,00 350,00 267,50 300,00 285,00 335,00 445,00

Tabulka 4.2 Průměrné ceny ubytování podle krajů

Abychom mohli analyzovat všechny náklady, potřebovali bychom znát i mzdu revizního technika. Revizní technik je v tomto případě fyzickou osobou podnikající podle živnostenského oprávnění. Jeho mzda je dána úkolem, který splní. Průměrnou mzdu tedy nemůžeme zjistit a při analýzách nákladů se budeme muset spokojit s odhadem nákladů na ubytování a nákladů na ujeté kilometry. Je ale zřejmé, že čím kratší část pracovní doby stráví přejížděním mezi uzly, tím méně času může věnovat hlavním pracovním činnostem.

4.3 Výpočty V této části provedeme výpočty tří modelů. Nejprve úlohy obchodního cestujícího, poté rozvozní úlohy – model 1 a nakonec i model 2 rozvozní úlohy.

4.3.1 Úloha obchodního cestujícího Matematický model úlohy obchodního cestujícího je vyjádřen omezujícími podmínkami (2.6) a účelovou funkcí (2.5), kterou minimalizujeme. Nejprve jsem provedl výpočet úlohy obchodního cestujícího pomocí heuristické metody nejbližšího souseda. Z výsledků se dozvíme, že čas strávený jízdou mezi uzly činí 28,75 hodiny, tj. 28 hodin a 45 minut. Ujetá vzdálenost činí 1600,6 km. Podle heuristické metody výhodnostních čísel bude délka cyklu činit 25 hodin. Vzdálenost, kterou musí revizní technik ujet při návštěvách uzlů, činí 1362,4 km.

- 57 -

Poslední heuristickou metodou je metoda vkládací. Podle výpočtů provedených touto metodou, bude délka cyklu 26,69 hodiny, tj. 26 hodin a 41 minut. Vzdálenost, kterou revizní technik ujede, je 1402,6 km. Úloha obchodního cestujícího patří mezi NP-obtížné úlohy (Pelikán J., 1999). Její řešení je velmi časově náročné. Algoritmus najde přípustné řešení, s přibývajícím výpočetním časem se hodnota účelové funkce snižuje, ale po čase se její klesání téměř zastaví a účelová funkce se snižuje jen velmi pozvolna. Provedl jsem výpočet v programu LINGO a sledoval jsem průběh výpočtu. Několik minut algoritmus hodnotu účelové funkce snižoval, ale po pár minutách se hodnota účelové funkce ustálila a již dále neklesala. Celkem jsem nechal algoritmus počítat 30 minut. I když s velkou pravděpodobností hodnota účelové funkce není optimální, jedná se o přípustné řešení. Z tohoto důvodu ho zde také uvádím. Délka cyklu je 25,48 hodiny, tj. 25 hodin a 29 minut. Revizní technik celkem ujede vzdálenost 1326,2 km. Doba trvání činnosti je předem dána a způsob výpočtu ji nemůže žádným způsobem ovlivnit. Celkem provádění činnosti v uzlech trvá 140 hodin. Výsledky všech výpočtů uvádím v následující tabulce. Náklady jsem získal vynásobením vzdálenosti a celkových nákladů na ujetý kilometr.

Činnosti Jízda Čas celkem Vzdálenost Náklady

Metoda Metoda Metoda nejbližšího výhodnostních nejlevnějšího LINGO souseda čísel vkládání 140 140 140 140 28,75 25,00 26,69 25,48 168,75 165,00 166,69 165,48 1600,6 1362,4 1402,6 1326,2 5720,544 4869,218 5012,892 4739,839 Tabulka 4.3 Výsledky – úloha obchodního cestujícího

V tabulce vidíme, že nejvýhodnější variantou z hlediska času, je metoda výhodnostních čísel. Výsledek získaný programem LINGO je o 29 minut delší, ale vzdálenost, kterou musí revizní technik překonat, je o 36,2 km kratší. Pokud se budeme držet pouze minimalizace účelové funkce (času), bude nejlepší metodou heuristika výhodnostních čísel, pokud vezmeme v úvahu náklady, bude lepší optimalizace provedená v LINGU. Obě metody jsou v tomto případě srovnatelné.

- 58 -

Je nutné však znovu upozornit, že výsledky v LINGU také nejsou optimální, protože byl výpočet přerušen po 30 minutách. Výsledky z úlohy obchodního cestujícího nelze v praxi příliš dobře využít. Je zcela nereálné, aby revizní technik navštívil všechny uzly v jednom cyklu. Pokud bychom cyklus pojali jako služební cestu a přidali bychom zastávku s ubytováním každých deset hodin, museli bychom připočítat náklady na ubytování pro 16 nocí strávených na cestě. To by zvýšilo náklady a 17-ti denní služební cesta by pro revizního technika nebyla přípustná. V praxi by se navíc jednalo o více než 17-ti denní cyklus, protože v cyklu uvažujeme pouze pracovní dny. Museli bychom také ocenit ubytování o víkendech a náklady také ocenit ztrátu volného času, který by revizní technik nemohl volně využít v místě svého bydliště. Pokud bychom se tomuto problému chtěli vyhnout, mohli bychom příklad vypočítat jako rozvozní úlohu – model 1 s pětidenní pracovní dobou. Víkendy by mohl technik strávit v místě bydliště, ale i takto dlouhé a časté služební cesty by byly pro revizního technika nevyhovující. Přejdeme tedy k rozvozní úloze – modelu 1 s deseti hodinovou pracovní dobou, která je blíže reálným předpokladům. Všechny výsledky výpočtů i se zápisem celé cesty jsou uvedeny v sekci příloh.

4.3.2 Rozvozní úloha – model 1 Matematický model úlohy tvoří minimalizační účelová funkce (2.18) a soustava omezujících podmínek (2.19). Na rozdíl od úlohy obchodního cestujícího, je řešení rozděleno na několik samostatných cyklů. Tyto cykly shodně začínají a končí ve stejném (výchozím a zároveň koncovém) uzlu. Abych mohl provést výpočet, bylo nezbytné předtím upravit matici vzdáleností, časů přejezdů a také vektor činností. Provedl jsem následující výpočet pro každý uzel i , kde i  2,3,..., n čas přejezdu 1, i  + činnost v uzlu i  + čas přejezdu i,1 .

- 59 -

Pokud je hodnota výrazu větší než pracovní doba 10 hodin, uzel i bychom nemohli zařadit do žádného cyklu. Proto jsem u uzlů, které měli hodnotu výrazu větší než pracovní doba, rozdělil činnosti na více úseků tak, aby všechny úseky splňovaly výše uvedený výraz. Jednalo se o uzly Na Průhoně 3412 Mělník 1, který jsem rozdělil na tři části s dobou trvání činnosti 9,46, 9,46, resp. 1,08 hodiny. Dalším rozděleným uzlem je Rudolfovská 461/95, České Budějovice 1 s délkou činností 4,36 a 2,64. Posledním rozděleným uzlem je U Vysočanského pivovaru 9, Praha 9. Tento uzel je rozdělený na dva s dobou trvání činností 8,74 a 3,26. Počet uzlů se zvýšil z 51 uzlů na 55 uzlů, což neovlivnilo rychlost výpočtu heuristik. Upravená data jsou uvedena v příloze na přiloženém CD. Při výpočtu heuristickou metodou nejbližšího souseda jsem dospěl k času 69 hodin a 52 minut. Délka cyklu je 4163,6 km. Metoda výhodnostních čísel má výsledný čas 69 hodin a 30 minut. Ujetá vzdálenost činí 4131,4 km. Heuristikou nejlevnějšího vkládání jsem získal výsledný čas 83,49 tj. 83 hodin a 29 minut. Výsledná délka cyklu je 5126,5 km. Výpočet v programu LINGO jsem provedl pouze na malém příkladě s 𝑛 = 5 uzly pro kontrolu správnosti formulací v teoretické části. Výsledky jsou uvedeny v příloze. U větší úlohy se mi za 30 minut nepodařilo získat přípustné řešení. K získání přípustného řešení by bylo potřeba spustit výpočet na delší dobu, nebo použít výkonnějším softwaru. Doby činnosti jsou opět stejné – 140 hodin u všech heuristik. Všechny výsledky i s náklady jsou uvedeny v tabulce.

- 60 -

Činnosti Jízda Čas celkem Vzdálenost Náklady

Metoda Metoda Metoda nejbližšího výhodnostních nejlevnějšího souseda čísel vkládání 140 140 140 69,87 69,5 83,49 209,87 209,5 223,49 4163,6 4131,4 5126,5 14880,71 14765,62 18322,11

Tabulka 4.4 Výsledky - rozvozní úloha – model 1

Z tabulky lze vyčíst, že nejvýhodnější je zvolit výsledek dosažený metodou výhodnostních čísel. Při bližším pohledu na výsledky v příloze zjistíme, že metoda výhodnostních čísel vytvořila 29 samostatných cyklů. Metodou nejbližšího souseda bychom všechny uzly prošli v 23 cyklech. Vezmeme v úvahu, že metodou nejbližšího souseda bychom lepším využitím pracovní doby ušetřili 6 pracovních dní. Náklady by se nám zvýšili o 115 Kč, což není ani 1% nákladů na dopravu mezi cykly. Z tohoto úhlu pohledu je výhodnější zvolit metodu nejbližšího souseda, i když se na první pohled zdála méně výhodná. Mírným zklamáním může být výrazný propad metody nejlevnějšího vkládání, jehož výsledek je o více než 13 hodin a téměř tisíc ujetých kilometrů horší než dvě další heuristiky. Problém je ve vlastním algoritmu metody nejlevnějšího vkládání. Nejdříve vybíráme nejdelší cestu od počátku do uzlu s a zpět a poté přidáváme uzly při co nejmenším prodloužení cyklu. V našem případě je délka cyklu příliš krátká a v cyklech je malý počet uzlů. Při větším počtu uzlů a delších cyklech se projeví výhody metody. Můžeme si toho všimnout u úlohy obchodního cestujícího, kdy metoda nejlevnějšího vkládání snesla srovnání s ostatními heuristikami. Všechny výsledky jsou opět uvedeny v příloze.

4.3.3 Rozvozní úloha – model 2 Nyní se zaměříme opět na rozvozní úlohu, avšak v modifikaci pro dvě délky cyklů. Matematický model je uveden v kapitole 2.4.

- 61 -

V tomto modelu máme dvě různé délky cyklů. Délka kratšího cyklu je shodná s předchozím modelem V  10 . Původním záměrem bylo stanovit délku W  10 , aby výsledný delší cyklus V  W měl délku 20. Ukázalo se, že je to nepraktické, protože jedna z činností má délku právě 20 hodin a nezbyl by žádný čas na příjezd k uzlu a odjezd. Musel bych opět činnost rozdělit. Jedná se však pouze o jeden uzel a cesta z uzlu 1 do tohoto uzlu a zpět trvá pouze 32 minut. Rozhodl jsem se proto, že nebudu dělit činnost jako v předchozím modelu. Místo toho zvětším hodnotu W na 11 hodin. Tím se delší cyklus zvětší na 21 hodin a všechny činnosti již půjdou zařadit. V modelu povolíme 4 delší cykly, aby do nich vešly všechny delší činnosti a projevily se výhody z používání delších cyklů. Při provádění výpočtů jsem opět začal metodou nejbližšího souseda. Doba cyklu bude 63 hodin a 13 minut a ujetá vzdálenost bude činit 3798,6 km. Metodou výhodnostních čísel jsem dospěl k následujícím výsledkům. Délka cyklu je 51 hodin a 6 minut a vzdálenost ujetá revizním technikem činí 2903,4 km. Poslední heuristikou, metodou nejlevnějšího vkládání jsem získal délku cyklu 57 hodin a 41 minut. Při ujeté vzdálenosti 3390,8 km. Výpočet v programu LINGO jsem opět provedl pouze na malém příkladě s n  5 uzly k ověření správnosti formulací v teoretické části. Výsledky jsou uvedeny v příloze. U větší úlohy se mi za 30 minut nepodařilo získat přípustné řešení. V následujících tabulkách jsou uvedeny adresy, poblíž kterých by se technik na služební cestě ubytoval. Náklady na ubytování se liší podle kraje, ve kterém se revizní technik ubytoval. Vždy jsem volil místo nejblíže polovině cyklu. Metoda nejbližšího souseda Uzel Na Průhoně 3412, Mělník 1 U vysočanského pivovaru 9, Praha 9 Rudolfovská 461/95, České Budějovice 1 Plavební 735, Mělník

Cena osoba/den Kraj Středočeský 381,25 Praha 486,25

Jihočeský Středočeský

Ubytování celkem Tabulka 4.5 Ubytování – metoda nejbližšího souseda

- 62 -

380 381,25 1628,75

Metoda výhodnostních čísel Uzel Rudolfovská 461/95, České Budějovice 1 U vysočanského pivovaru 9, Praha 9 Na Průhoně 3412, Mělník 1

Kraj Jihočeský Praha

Cena osoba/den

Středočeský Královéhradecký

Kamenice 113, Náchod Ubytování celkem

380 486,25 381,25 275,00 1522,5

Tabulka 4.6 Ubytování – metoda výhodnostních čísel

Metoda nejlevnějšího vkládání Uzel Balbínova 14/192, Praha 2 U vysočanského pivovaru 9, Praha 9 Na Průhoně 3412, Mělník 1 Na Kačence 165, Praha 9 Ubytování celkem

Cena osoba/den Kraj Praha 486,25 Praha 486,25 Středočeský 381,25 Praha 486,25 1840,00

Tabulka 4.7 Ubytování – metoda nejlevnějšího vkládání

Výsledky jsou i s náklady uvedeny v tabulce. Doby trvání činností opět nelze ovlivnit zvolením jiného výpočetního postupu.

Činnosti Jízda Celkem Vzdálenost Náklady - jízda Náklady ubytování Náklady celkem

Metoda Metoda Metoda nejbližšího výhodnostních nejlevnějšího souseda čísel vkládání 140 140 140 63,22 51,11 57,69 203,22 191,11 197,69 3798,6 2903,4 3390,8 13576,2 10376,75 12118,72 1628,75 1522,5 1840 15204,95 11899,25 13958,72

Tabulka 4.8 Výsledky – rozvozní úloha – model 2

Vybrat nejlepší metodu není jednoduché. Nejkratší cyklus vytvořila heuristika výhodnostních čísel, ale metodou nejlevnějšího vkládání jsme získali pouze 17 cyklů oproti devatenácti u obou ostatních metod. Podle nákladů a ujeté vzdálenosti je lepší metoda výhodnostních čísel. Stojí za zvážení, jestli úspora dvou pracovních dnů vyváží náklady zvýšené o cca 2000 Kč. Když budeme uvažovat jako prioritní úsporu času, zvolíme metodu nejlevnějšího vkládání. K přesnějšímu rozhodování bychom potřebovali vědět, jaká je mzda revizního technika. Jak již bylo uvedeno výše, tyto náklady neznáme.

- 63 -

4.4 Porovnání modelů a heuristik Na závěr kapitoly zbývá zhodnocení použitých modelů a přínosy jednotlivých heuristických metod pro řešení problému.

4.4.1 Porovnání modelů Jak již bylo uvedeno výše, úloha obchodního cestujícího není vhodná pro řešení našeho problému. Důvodem je příliš dlouhý cyklus. Model jsme však použili také pro srovnání heuristik. Rozvozní úloha – model 1 a model 2 jsou vhodnými modely, kterými lze naši úlohu vyřešit. Srovnáme řešení modelu 1 vypočteného metodou nejbližšího souseda a řešení modelu 2 heuristikou nejlevnějšího vkládání. Porovnáním těchto výsledků zjistíme, že v modelu 1 jsou náklady o 922 Kč vyšší a vzdálenost je delší o 772 km. Výhodou modelu je také časová úspora 12 hodin a 11 minut. Také počet cyklů je nižší u modelu 2, 17 oproti 23. I když mají 4 cykly dvojnásobnou délku, znamená to úsporu 2 pracovních dnů. Všechny tyto argumenty hovoří pro využívání modelu 2.

4.4.2 Porovnání heuristik Pokud bychom vybírali nejlepší heuristiku pouze podle nejlepšího dosaženého času, byla by metoda výhodnostních čísel nejlepší volbou. Jako jediná je nedominovanou variantou, protože dosažený čas byl vždy nejlepší. Musíme ovšem vzít v úvahu, že u každého modelu jsme porovnávali metody i podle dalších kritérií. Podle vzdálenosti, nákladů a u modelu 1 a 2 i podle počtu vytvořených cyklů. Proto jsme u každého modelu zvolili jako nejlepší jinou heuristiku. Metoda nejbližšího souseda byla nejlepší při řešení modelu 1. Metoda výhodnostních čísel byla zvolena u úlohy obchodního cestujícího a heuristika nejlevnějšího vkládání se osvědčila u modelu 2. Je pravděpodobné, že v případě odlišných vstupních dat bychom jako nejlepší v jednotlivých modelech zvolili jiné heuristiky. V našem případě však nemůžeme zavrhnout žádnou z použitých heuristik jako nevyhovující. Každá pro nás byla u určitého modelu výhodná.

- 64 -

Bylo výhodné používat více heuristických postupů, protože jejich porovnáním jsme u modelů získali lepší řešení, než kdybychom používali pouze jednu metodu.

- 65 -

5. Závěr Cílem diplomové práce bylo vytvořit aplikaci v MS Excel pro výpočet heuristických metod. Jmenovitě pro metody nejbližšího souseda, výhodnostních čísel a nejlevnějšího vkládání. Druhým cílem byla optimalizace trasy revizního technika při revizích elektrospotřebičů. Aplikace Heuristiky, která je součástí diplomové práce, splňuje vytčené cíle. Lze v ní vypočítat výše uvedené tři heuristické metody pro úlohu obchodního cestujícího i pro rozvozní úlohu – model 1 a model 2. Při programování této aplikace jsem získal řadu poznatků o heuristikách a o programování ve VBA. V teoretické části práce jsem se věnoval popisu matematických modelů úlohy obchodního cestujícího, rozvozní úlohy a jejich modifikací. Rovněž jsou zde uvedeny heuristické metody v modifikacích pro úlohu obchodního cestujícího a dvě modifikace rozvozní úlohy. Součástí práce je i část o aplikaci Heuristiky. Slouží jako manuál k aplikaci a je zde popsáno uživatelské rozhraní, zadávání dat a interpretace výsledků. Druhý cíl – optimalizace trasy revizního technika je splněn v poslední praktické části. Je zde proveden rozbor výsledků a výběr vhodných variant pro volbu trasy revizního technika. Popisuji zde také výhody a nevýhody jednotlivých modelů a rovněž i porovnání heuristických metod použitých v této práci. Zpracování diplomové práce pro mě bylo velmi přínosné a naučil jsem se při něm hodně nových věcí. Zejména jsem získal poznatky o heuristických metodách a hodně zkušeností s programováním ve VBA. Rovněž je přínosem získané řešení optimalizační úlohy.

- 66 -

Seznam použité literatury [1.]

Černý J.: Excel 2000 – 2007 Záznam, úprava a programování maker, 1. vydání Grada Publishing, Praha 2008, ISBN 978-80-247-2305-1

[2.]

Černý J.: Programování v Excelu 5, 7, 97, 2000, 2002 Podrobný průvodce pokročilého uživatele, 1. vydání, Grada Publishing, Praha 2001, ISBN 80-247-0047-6

[3.]

Černý J.: Programování v Excelu 2000, 2002, 2003, 1.vydání Grada Publishing, Praha 2005, ISBN 80-247-0922-8

[4.]

Fábry J.: Dynamické okružní a rozvozní úlohy, disertační práce, VŠE-FIS, Praha 2006

[5.]

Jablonský J.: Operační výzkum Kvantitativní modely pro ekonomické rozhodování, 2. vydání, Professional Publishing, Praha 2002, ISBN 80-86419-42-8

[6.]

Jacobson R.: Excel 97 Visual Basic krok za krokem, 1. vydání Computer Press, Praha 1998, ISBN 80-7226-067-7

[7.]

Pelikán J.: Diskrétní modely, 1. vydání VŠE 1999, ISBN 80-7079-179-9

Internetové zdroje [1.] [2.] [3.] [4.] [5.] [6.]

[7.]

http://cc.skoda-auto.com/cze/cc_6_finish.aspx?SessIdentifier=SI0 (2.5.2009) http://nb.vse.cz/~fabry/4EK314-prezentace.ppt (17.4.2009) http://www.abc-hotel.cz/cz/ (23.4.2009) http://www.ccs.cz/www/?action=rady_PHM&SID=sb0jsco128r06a3f0l4mmgjs1 6&sign=7b9f177ab372990cd61c87c33d21550b (24.4.2009) http://www.mapy.cz (25.6.2008) http://www.rzp.cz/cgibin/aps_cacheWEB.sh?VSS_SERV=ZVWSBJVYP&IDICO=0723cee25acb25d 737d6&historie=1 (2.5.2009) http://www.skodaauto.com/importer/webcontrols/techdata.aspx?set=model&modelcode=1U2&eq uipmentcode=1&motorcode=54&actioncode=&modelyear=2008 (2.5.2009)

- 67 -

Přílohy Úloha obchodního cestujícího – metoda nejbližšího souseda Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou U školky 306, Horní Beřkovice Na Průhoně 3412, Mělník 1 Plavební 735, Mělník Rybáře 750, Mělník Mladoboleslavská 3287, Mělník náměstí Republiky 400, Neratovice Na Kačence 165, Praha 9 Slévačská 744/1, Praha 9 U vysočanského pivovaru 9, Praha 9 Janovského 48, Praha 7 Balbínova 14/192, Praha 2 Panská 6, Praha 1 Boleslavova 10, Praha 4 Senovážné náměstí 2, Praha 1 Heleny Malířové 16, Praha 6 U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 K Hájům 4, Praha 5 Tylovická 207, Praha Jiráskova 496, Kralupy nad Vltavou Zámek Nelahozeves, Nelahozeves 1 Riegrova 330, Veltrusy Rvačov 136, Roudnice nad Labem Nové náměstí 136, Štětí Hrnčířská 4, Ústí nad Labem Masarykova 538/16, Teplice Mostecká 2050, Litvínov Budovatelů 1987, Most náměstí 1. Máje 91, Chomutov třída Obránců míru 360, Žatec Česká 158, Louny Jirkovského 2603, Rakovník Tržní 28, Děčín Českobratrské náměstí 1392, Mladá Boleslav Masarykova 221, Lysá nad Labem Husova 79, Jičín náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové

- 68 -

3 1,5 2 20 9 1 1,5 2,5 5 4 12 2,5 2,5 2 5 3 7,5 4 3,5 1 1 6 1 3,5 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1

Jízda 0,02 0,02 0,17 0,23 0,03 0,03 0,1 0,25 0,42 0,28 0,1 0,25 0,1 0,05 0,13 0,15 0,2 0,17 0,18 0,32 0,13 0,73 0,12 0,15 0,4 0,37 0,92 0,37 0,42 0,27 0,47 0,42 0,55 0,93 1,1 1,42 0,62 1,12 0,38 0,37 0,62

Vzdálenost 0,1 0,6 5,9 11,2 1,2 0,7 2,4 21,4 16,1 8,5 3 7,5 3,3 1,4 3,8 4 6,1 6,3 5,1 15,4 3,8 29 3,5 5,5 22,1 13 41,8 22,7 23,6 13 23,7 22,4 21,5 36,2 117 84,4 32,4 62,6 23,6 18,9 34,1

1 1 1 1 1 1 1 1 2 7 -

U Koruny 73, Hradec Králové Břetislavova 69, Chrudim T. G. Masaryka 115, Ústí nad Orlicí B. Němcové 127, Lanškroun Panská 1493, Rychnov nad Kněžnou Kostelní 4, Dobruška Kamenice 113, Náchod Krkonošská 10, Vrchlabí Krašovská 16, Plzeň Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Metoda nejbližšího souseda (TSP)

Činnosti

Celkem

140

- 69 -

0,63 1,15 0,47 0,97 0,33 0,38 1,27 3,47 2,18 2,82 Jízda 28,75

33,7 53,7 19 45 17,7 18,4 67,5 232,1 142,7 192 Vzdálenost 1600,6

Úloha obchodního cestujícího – metoda výhodnostních čísel Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice Na Průhoně 3412, Mělník 1 Nové náměstí 136, Štětí Rvačov 136, Roudnice nad Labem Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Masarykova 538/16, Teplice Česká 158, Louny Budovatelů 1987, Most Mostecká 2050, Litvínov náměstí 1. Máje 91, Chomutov třída Obránců míru 360, Žatec Jirkovského 2603, Rakovník Krašovská 16, Plzeň Rudolfovská 461/95, České Budějovice 1 Masarykova 221, Lysá nad Labem U Koruny 73, Hradec Králové Břetislavova 69, Chrudim B. Němcové 127, Lanškroun T. G. Masaryka 115, Ústí nad Orlicí Panská 1493, Rychnov nad Kněžnou Kostelní 4, Dobruška Kamenice 113, Náchod Rooseveltova 459, Dvůr Králové náměstí Jiřího z Poděbrad 342, Hořice Krkonošská 10, Vrchlabí Husova 79, Jičín Českobratrské náměstí 1392, Mladá Boleslav Pražského 636/34, Praha 5 U Dívčích hradů 12, Praha 5 K Hájům 4, Praha 5 Tylovická 207, Praha Heleny Malířové 16, Praha 6 Boleslavova 10, Praha 4 Panská 6, Praha 1 Balbínova 14/192, Praha 2 Senovážné náměstí 2, Praha 1 Janovského 48, Praha 7 U vysočanského pivovaru 9, Praha 9 Slévačská 744/1, Praha 9 Na Kačence 165, Praha 9 náměstí Republiky 400, Neratovice

- 70 -

2 20 1 3 1 1 1 1 1 1 1 1 2 2 7 1 1 1 1 1 1 1 1 1 1 1 1 1 3,5 4 1 1 7,5 5 2 2,5 3 2,5 12 4 5 2,5

Jízda 0,18 0,23 0,23 0,37 0,72 0,45 0,67 0,65 0,48 0,27 0,5 0,42 0,85 1,13 2,18 2,67 1,22 0,63 1,33 0,47 0,5 0,33 0,38 0,65 0,37 0,88 0,77 0,7 1 0,18 0,22 0,13 0,27 0,2 0,13 0,05 0,07 0,1 0,25 0,1 0,28 0,42 0,25

Vzdálenost 6,3 11,2 13,1 13 47,4 24,6 33,7 38,3 25,1 13 25,9 22,4 34,3 60,2 142,7 184,6 85,6 33,7 82,2 19 25,8 17,7 18,4 30,8 18,9 47,7 36,6 36,2 70,7 5,1 6,3 3,8 8,4 7,1 3,8 1,4 1,6 3 7,5 3 8,5 16,1 21,4

1,5 1 9 1 6 3,5 1,5 3 -

Mladoboleslavská 3287, Mělník Rybáře 750, Mělník Plavební 735, Mělník Zámek Nelahozeves, Nelahozeves 1 Jiráskova 496, Kralupy nad Vltavou Riegrova 330, Veltrusy 1. Máje 176, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Metoda výhodnostních čísel (TSP)

Činnosti

Celkem

140

- 71 -

0,1 0,03 0,38 0,12 0,15 0,3 0,02 0,02 Jízda

2,4 0,7 19,8 3,5 5,1 14,1 0,6 0,1 Vzdálenost

25

1362,4

Úloha obchodního cestujícího – metoda nejlevnějšího vkládání Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Masarykova 538/16, Teplice Mostecká 2050, Litvínov Budovatelů 1987, Most náměstí 1. Máje 91, Chomutov třída Obránců míru 360, Žatec Krašovská 16, Plzeň Jirkovského 2603, Rakovník Česká 158, Louny Rvačov 136, Roudnice nad Labem Nové náměstí 136, Štětí Na Průhoně 3412, Mělník 1 Mladoboleslavská 3287, Mělník Rybáře 750, Mělník Plavební 735, Mělník Zámek Nelahozeves, Nelahozeves 1 Jiráskova 496, Kralupy nad Vltavou Riegrova 330, Veltrusy Janovského 48, Praha 7 Heleny Malířové 16, Praha 6 Tylovická 207, Praha K Hájům 4, Praha 5 U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 Boleslavova 10, Praha 4 Panská 6, Praha 1 Balbínova 14/192, Praha 2 Senovážné náměstí 2, Praha 1 U vysočanského pivovaru 9, Praha 9 Masarykova 221, Lysá nad Labem Českobratrské náměstí 1392, Mladá Boleslav Husova 79, Jičín Krkonošská 10, Vrchlabí U Koruny 73, Hradec Králové náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Kamenice 113, Náchod Kostelní 4, Dobruška Panská 1493, Rychnov nad Kněžnou

- 72 -

3 1,5 1 1 1 1 1 1 1 2 2 1 3 1 20 1,5 1 9 1 6 3,5 2,5 7,5 1 1 4 3,5 5 2 2,5 3 12 1 1 1 1 1 1 1 1 1 1

Jízda 0,02 0,02 0,88 0,45 0,67 0,42 0,27 0,47 0,42 1,37 1,13 0,93 0,83 0,37 0,23 0,1 0,1 0,03 0,38 0,12 0,15 0,48 0,15 0,27 0,13 0,22 0,18 0,28 0,13 0,05 0,07 0,25 0,7 0,62 0,7 0,77 1,23 0,42 0,37 0,65 0,38 0,33 0,5

Vzdálenost 0,1 0,6 62,1 24,6 33,7 23,6 13 23,7 22,4 78,5 60,2 36,2 40,5 13 13,1 3,7 2,4 0,7 19,8 3,5 5,1 27,2 5,1 8,4 3,8 6,3 5,1 10,3 3,8 1,4 1,6 7 35,2 32,4 36,2 36,6 70,3 23,9 18,9 30,8 18,4 17,7 25,8

1 1 1 7 4 5 2,5 2 -

T. G. Masaryka 115, Ústí nad Orlicí B. Němcové 127, Lanškroun Břetislavova 69, Chrudim Rudolfovská 461/95, České Budějovice 1 Slévačská 744/1, Praha 9 Na Kačence 165, Praha 9 náměstí Republiky 400, Neratovice U školky 306, Horní Beřkovice Fučíkova 153, Lužec nad Vltavou Metoda nejlevnějšího vkládání (TSP)

Činnosti

Celkem

140

- 73 -

0,47 1,33 2,95 2,27 0,28 0,42 0,55 0,18 Jízda 26,69

19 82,2 183,5 155,1 8,5 16,1 25,2 6,3 Vzdálenost 1402,6

Úloha obchodního cestujícího – LINGO Uzel

Činnost 2 9 20 1 1 1 1 1 1 1 1 1 3 3,5 1 6 5 4 12 2 4 3,5 2,5 3 2,5 5 7,5 1 1 2 2 7 1 1 1 1 1 1 1 1 1 1

Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice Plavební 735, Mělník Na Průhoně 3412, Mělník 1 Nové náměstí 136, Štětí Tržní 28, Děčín Hrnčířská 4, Ústí nad Labem Masarykova 538/16, Teplice třída Obránců míru 360, Žatec náměstí 1. Máje 91, Chomutov Budovatelů 1987, Most Mostecká 2050, Litvínov Česká 158, Louny Rvačov 136, Roudnice nad Labem Riegrova 330, Veltrusy Zámek Nelahozeves, Nelahozeves 1 Jiráskova 496, Kralupy nad Vltavou Na Kačence 165, Praha 9 Slévačská 744/1, Praha 9 U vysočanského pivovaru 9, Praha 9 Panská 6, Praha 1 U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 Balbínova 14/192, Praha 2 Senovážné náměstí 2, Praha 1 Janovského 48, Praha 7 Boleslavova 10, Praha 4 Heleny Malířové 16, Praha 6 K Hájům 4, Praha 5 Tylovická 207, Praha Jirkovského 2603, Rakovník Krašovská 16, Plzeň Rudolfovská 461/95, České Budějovice 1 Břetislavova 69, Chrudim B. Němcové 127, Lanškroun T. G. Masaryka 115, Ústí nad Orlicí Panská 1493, Rychnov nad Kněžnou Kostelní 4, Dobruška Kamenice 113, Náchod U Koruny 73, Hradec Králové náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Krkonošská 10, Vrchlabí

- 74 -

Jízda 0,18 0,23 0,03 0,23 1,1 0,45 0,37 0,9 0,42 0,47 0,27 0,62 0,83 0,4 0,15 0,12 0,5 0,28 0,1 0,27 0,23 0,18 0,25 0,07 0,1 0,18 0,2 0,23 0,13 0,88 1,13 2,18 2,95 1,33 0,47 0,5 0,33 0,38 0,75 0,42 0,37 0,78 0,77

Vzdálenost 6,3 10,9 1,2 13,1 51,6 24,6 22,7 51,3 22,4 23,7 13 35,7 40,5 22,1 5,5 3,5 24,3 8,5 3 7,4 6,8 5,1 9,6 1,6 3 5,7 7,1 7,4 3,8 49,8 60,2 142,7 183,5 82,2 19 25,8 17,7 18,4 42 23,9 18,9 36,3 36,6

1 1 1 2,5 1 1,5 1,5 3 -

Husova 79, Jičín Českobratrské náměstí 1392, Mladá Boleslav Masarykova 221, Lysá nad Labem náměstí Republiky 400, Neratovice Rybáře 750, Mělník Mladoboleslavská 3287, Mělník 1. Máje 176, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Lingo (TSP)

Činnosti

Celkem

140

- 75 -

0,7 0,62 0,72 0,3 0,1 0,27 0,02 0,02 Jízda 25,48

36,2 32,4 30,5 13,5 2,4 12,1 0,6 0,1 Vzdálenost 1326,2

Rozvozní úloha model 1 – metoda nejbližšího souseda Uzel Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou U školky 306, Horní Beřkovice Na Průhoně 3412, Mělník 1 Rybáře 750, Mělník Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Plavební 735, Mělník Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Zámek Nelahozeves, Nelahozeves 1 Rvačov 136, Roudnice nad Labem Fučíkova 153, Lužec nad Vltavou Mladoboleslavská 3287, Mělník náměstí Republiky 400, Neratovice Janovského 48, Praha 7 K Hájům 4, Praha 5 Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou Panská 6, Praha 1 Fučíkova 153, Lužec nad Vltavou Nové náměstí 136, Štětí Na Kačence 165, Praha 9 Fučíkova 153, Lužec nad Vltavou Slévačská 744/1, Praha 9 U vysočanského pivovaru 9, Praha 9 Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Fučíkova 153, Lužec nad Vltavou Balbínova 14/192, Praha 2 Senovážné náměstí 2, Praha 1 Tylovická 207, Praha Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Masarykova 221, Lysá nad Labem Fučíkova 153, Lužec nad Vltavou Masarykova 538/16, Teplice

Činnost 3 1,5 2 1,08000004 1 9,46000004 9,46000004 9 3,5 1 3 1,5 2,5 2,5 1 6 2 1 5 4 3,25999999 8,73999977 2,5 3 1 7,5 5 1 1

- 76 -

Jízda 0,02 0,02 0,17 0,23 0,07 0,3 0,27 0,27 0,27 0,27 0,27 0,27 0,32 0,15 0,42 0,43 0,33 0,25 0,48 0,35 0,97 0,4 0,62 0,72 0,5 0,87 0,6 0,62 0,1 0,63 0,63 0,63 0,7 0,07 0,38 1 0,77 0,77 0,78 0,8 1,13 0,87 0,37

Vzdálenost 0,1 0,6 5,9 11,2 1,9 10,8 10,5 10,5 10,5 10,5 10,1 10,1 14,5 5,5 22,9 25,2 12,7 21,4 24,9 11,7 51,4 17,6 30,6 42,8 23,5 53,7 36,5 38,7 3 38,5 38,5 38,5 43 1,6 12 52,3 44,9 44,9 45,4 46,3 50,1 65 22,7

Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Budovatelů 1987, Most Mostecká 2050, Litvínov Fučíkova 153, Lužec nad Vltavou U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 Fučíkova 153, Lužec nad Vltavou Česká 158, Louny třída Obránců míru 360, Žatec náměstí 1. Máje 91, Chomutov Jirkovského 2603, Rakovník Fučíkova 153, Lužec nad Vltavou Českobratrské náměstí 1392, Mladá Boleslav Husova 79, Jičín náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Břetislavova 69, Chrudim T. G. Masaryka 115, Ústí nad Orlicí Fučíkova 153, Lužec nad Vltavou Krašovská 16, Plzeň Fučíkova 153, Lužec nad Vltavou Krkonošská 10, Vrchlabí Kamenice 113, Náchod Kostelní 4, Dobruška Fučíkova 153, Lužec nad Vltavou Panská 1493, Rychnov nad Kněžnou B. Němcové 127, Lanškroun Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Metoda nejbližšího souseda (VRP)

1 1 1 1 4 3,5 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 4,36000013 2,6400001 Činnosti

Celkem

140

- 77 -

0,45 1,03 0,27 1,25 0,88 0,18 0,92 1 0,55 0,42 1,27 1,22 1,08 0,7 0,38 0,37 2,23 1,98 0,63 1,15 3 2,03 2,03 2,23 1,27 0,38 2,62 2,73 0,97 3,28 2,82 2,82 2,82 2,82 Jízda 69,87

24,6 69,1 13 87,3 48,4 5,1 52,4 56,2 21,5 22,4 56,5 65,8 56 36,2 23,6 18,9 128,4 138,5 33,7 53,7 198,3 139,5 139,5 122,5 67,5 18,4 171,9 179,7 45 229 192 192 192 192 Vzdálenost 4163,6

Rozvozní úloha model 1 – metoda výhodnostních čísel Uzel Fučíkova 153, Lužec nad Vltavou B. Němcové 127, Lanškroun T. G. Masaryka 115, Ústí nad Orlicí Panská 1493, Rychnov nad Kněžnou Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou Balbínova 14/192, Praha 2 Fučíkova 153, Lužec nad Vltavou Zámek Nelahozeves, Nelahozeves 1 Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Janovského 48, Praha 7 Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Kamenice 113, Náchod Kostelní 4, Dobruška Fučíkova 153, Lužec nad Vltavou Husova 79, Jičín Krkonošská 10, Vrchlabí Břetislavova 69, Chrudim Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Budovatelů 1987, Most Mostecká 2050, Litvínov náměstí 1. Máje 91, Chomutov třída Obránců míru 360, Žatec Česká 158, Louny Fučíkova 153, Lužec nad Vltavou K Hájům 4, Praha 5

Činnost 1 1 1 1 9,46000004 9,46000004 1,08000004 5 2,5 1 3 2,5 4,36000013 1 1 1 1 1 1 1 2,6400001 1 1 1 1 1 1

- 78 -

Jízda 3,28 0,47 0,5 2,73 1,98 1,98 0,27 0,27 0,27 0,27 0,27 0,27 0,78 0,78 0,7 0,7 0,35 0,35 0,02 0,02 0,63 0,63 2,82 2,82 1,87 0,37 0,65 0,38 2,62 1,6 0,77 1,8 2,17 2,82 2,82 1,13 0,27 0,5 0,42 0,55 1 0,97 1,2

Vzdálenost 229 19 25,8 179,7 138,5 138,5 10,5 10,5 10,5 10,5 10,5 10,5 45,4 45,4 43 43 15,3 15,3 0,1 0,1 40,1 40,1 192 192 109,5 18,9 30,8 18,4 171,9 86,2 36,6 103,5 145,9 192 192 75,8 13 25,9 22,4 21,5 56,2 51,4 86,5

Krašovská 16, Plzeň Jirkovského 2603, Rakovník Fučíkova 153, Lužec nad Vltavou Rvačov 136, Roudnice nad Labem Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Masarykova 538/16, Teplice Fučíkova 153, Lužec nad Vltavou Pražského 636/34, Praha 5 U Dívčích hradů 12, Praha 5 Fučíkova 153, Lužec nad Vltavou Slévačská 744/1, Praha 9 Masarykova 221, Lysá nad Labem Českobratrské náměstí 1392, Mladá Boleslav Rybáře 750, Mělník Fučíkova 153, Lužec nad Vltavou náměstí Republiky 400, Neratovice Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou Fučíkova 153, Lužec nad Vltavou Plavební 735, Mělník Fučíkova 153, Lužec nad Vltavou Na Kačence 165, Praha 9 Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou Panská 6, Praha 1 Tylovická 207, Praha Senovážné náměstí 2, Praha 1 Mladoboleslavská 3287, Mělník Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Nové náměstí 136, Štětí 1. Máje 176, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Metoda výhodnostních čísel (VRP)

2 2 3 1 1 1 3,5 4 4 1 1 1 2,5 6 9 5 7,5 2 1 3 1,5 3,5 2 8,73999977 3,25999999 1 1,5 Činnosti

Celkem

140

- 79 -

1,13 1,22 0,43 0,72 0,45 0,67 0,87 0,92 0,18 0,88 0,62 0,62 0,62 0,83 0,3 0,58 0,58 0,4 0,4 0,27 0,27 0,6 0,6 0,77 0,77 0,72 0,38 0,38 0,68 0,33 0,32 0,32 0,18 0,18 0,63 0,63 0,63 0,9 0,43 0,02 Jízda 69,5

60,2 65,8 25,2 47,4 24,6 33,7 65 52,4 5,1 48,4 38,7 32,4 32,4 44,6 10,8 24,9 24,9 17,6 17,6 10,1 10,1 36,5 36,5 44,9 44,9 42,8 11,8 12 37 12,7 14,5 14,5 6,3 6,3 38,5 38,5 38,5 56,2 23 0,4 Vzdálenost 4131,4

Rozvozní úloha model 1 – metoda nejlevnějšího vkládání Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou B. Němcové 127, Lanškroun Fučíkova 153, Lužec nad Vltavou Mladoboleslavská 3287, Mělník U Koruny 73, Hradec Králové T. G. Masaryka 115, Ústí nad Orlicí Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou Panská 1493, Rychnov nad Kněžnou Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Kostelní 4, Dobruška Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Kamenice 113, Náchod Fučíkova 153, Lužec nad Vltavou Rybáře 750, Mělník Českobratrské náměstí 1392, Mladá Boleslav Husova 79, Jičín náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice Krkonošská 10, Vrchlabí Zámek Nelahozeves, Nelahozeves 1 Fučíkova 153, Lužec nad Vltavou Slévačská 744/1, Praha 9 Břetislavova 69, Chrudim Fučíkova 153, Lužec nad Vltavou Janovského 48, Praha 7 K Hájům 4, Praha 5 Krašovská 16, Plzeň Fučíkova 153, Lužec nad Vltavou Česká 158, Louny třída Obránců míru 360, Žatec náměstí 1. Máje 91, Chomutov Budovatelů 1987, Most

1,5 1 1,5 1 1 4,36000013 1,08000004 2,6400001 3 1 3,25999999 1 3,5 1 1 1 1 1 1 2 1 1 4 1 2,5 1 2 1 1 1 1

- 80 -

Jízda 0,02 3,25 3,28 0,33 1,8 1,1 3 2,82 2,82 0,27 2,87 2,82 0,02 2,73 2,73 0,63 2,08 2,62 0,32 2,37 2,52 0,3 0,83 0,7 0,38 0,37 2,23 0,18 2,2 2,37 0,35 0,62 1,58 2,17 0,63 0,35 1,2 2,03 1 0,55 0,42 0,47 0,27

Vzdálenost 0,4 227,9 229 12,7 123 59,2 198,3 192 192 10,5 196,9 192 0,1 179,9 179,7 38,5 136 171,9 14,5 166 178,6 10,8 44,6 36,2 23,6 18,9 128,4 6,3 122,7 132,2 15,3 38,7 108,4 145,9 40,1 11,7 86,5 139,5 56,2 21,5 22,4 23,7 13

Mostecká 2050, Litvínov Masarykova 538/16, Teplice Fučíkova 153, Lužec nad Vltavou Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Nové náměstí 136, Štětí Rvačov 136, Roudnice nad Labem Fučíkova 153, Lužec nad Vltavou Panská 6, Praha 1 Balbínova 14/192, Praha 2 Jirkovského 2603, Rakovník Fučíkova 153, Lužec nad Vltavou náměstí Republiky 400, Neratovice Masarykova 221, Lysá nad Labem Senovážné náměstí 2, Praha 1 Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou Tylovická 207, Praha Fučíkova 153, Lužec nad Vltavou U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Fučíkova 153, Lužec nad Vltavou Na Kačence 165, Praha 9 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Plavební 735, Mělník Fučíkova 153, Lužec nad Vltavou Metoda nejlevnějšího vkládání (VRP)

1 1 1 1 1 3 2 2,5 2 2,5 1 3 6 1 4 3,5 5 7,5 8,73999977 5 9,46000004 9,46000004 9 Činnosti

Celkem

140

- 81 -

0,42 0,87 0,92 0,45 1,1 0,37 0,43 0,72 0,05 1,13 1,22 0,58 0,72 0,92 0,7 0,4 0,73 1 0,88 0,18 0,92 0,78 0,78 0,77 0,77 0,63 0,63 0,6 0,6 0,27 0,27 0,27 0,27 0,27 0,27 Jízda 83,49

23,6 65 64,3 24,6 51,6 13 25,2 42,8 1,4 61 65,8 24,9 30,5 47,2 42,3 17,6 29 52,3 48,4 5,1 52,4 45,4 45,4 44,9 44,9 38,5 38,5 36,5 36,5 10,5 10,5 10,5 10,5 10,1 10,1 Vzdálenost 5126,5

Rozvozní úloha model 2 – metoda nejbližšího souseda Uzel

Činnost 20 12 4 2,5 7 5 2 3 1,5 2 9 1 1,5 1 3,5 1 3 6 1 2,5 5 2,5 3 1 7,5 1 1 1 1 1 4 3,5

Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou U vysočanského pivovaru 9, Praha 9 Slévačská 744/1, Praha 9 Janovského 48, Praha 7 Fučíkova 153, Lužec nad Vltavou Rudolfovská 461/95, České Budějovice 1 Boleslavova 10, Praha 4 Panská 6, Praha 1 Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou U školky 306, Horní Beřkovice Plavební 735, Mělník Rybáře 750, Mělník Mladoboleslavská 3287, Mělník Nové náměstí 136, Štětí Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Zámek Nelahozeves, Nelahozeves 1 Rvačov 136, Roudnice nad Labem Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou K Hájům 4, Praha 5 Fučíkova 153, Lužec nad Vltavou náměstí Republiky 400, Neratovice Na Kačence 165, Praha 9 Fučíkova 153, Lužec nad Vltavou Balbínova 14/192, Praha 2 Senovážné náměstí 2, Praha 1 Tylovická 207, Praha Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou Masarykova 538/16, Teplice Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Budovatelů 1987, Most Mostecká 2050, Litvínov Fučíkova 153, Lužec nad Vltavou U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5

- 82 -

Jízda 0,27 0,27 0,63 0,1 0,32 0,63 2,82 2,1 0,13 0,72 0,02 0,02 0,17 0,23 0,03 0,1 0,33 0,5 0,32 0,15 0,42 0,43 0,4 0,73 0,97 0,58 0,42 0,6 0,7 0,07 0,38 1 0,77 0,77 0,87 0,37 0,45 1,03 0,27 1,25 0,88 0,18 0,92

Vzdálenost 10,5 10,5 38,5 3 11,7 40,1 192 147,9 3,8 42,8 0,1 0,6 5,9 10,9 0,7 2,4 16,8 23,5 14,5 5,5 22,9 25,2 17,6 32,1 51,4 24,9 16,1 36,5 43 1,6 12 52,3 44,9 44,9 65 22,7 24,6 69,1 13 87,3 48,4 5,1 52,4

1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 -

Fučíkova 153, Lužec nad Vltavou Česká 158, Louny třída Obránců míru 360, Žatec náměstí 1. Máje 91, Chomutov Jirkovského 2603, Rakovník Fučíkova 153, Lužec nad Vltavou Českobratrské náměstí 1392, Mladá Boleslav Masarykova 221, Lysá nad Labem Husova 79, Jičín náměstí Jiřího z Poděbrad 342, Hořice Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Rooseveltova 459, Dvůr Králové Kamenice 113, Náchod Fučíkova 153, Lužec nad Vltavou Krašovská 16, Plzeň Fučíkova 153, Lužec nad Vltavou Břetislavova 69, Chrudim T. G. Masaryka 115, Ústí nad Orlicí Panská 1493, Rychnov nad Kněžnou Fučíkova 153, Lužec nad Vltavou Krkonošská 10, Vrchlabí Kostelní 4, Dobruška Fučíkova 153, Lužec nad Vltavou B. Němcové 127, Lanškroun Fučíkova 153, Lužec nad Vltavou Metoda nejbližšího souseda (VRP)

Činnosti

Celkem

140

- 83 -

1 0,55 0,42 1,27 1,22 1,08 0,62 1,12 0,38 1,87 1,98 0,62 0,65 2,52 2,03 2,03 2,17 1,15 0,5 2,73 2,23 1,58 2,62 3,28 3,28 Jízda 63,22

56,2 21,5 22,4 56,5 65,8 56 32,4 62,6 23,6 109,5 138,5 34,1 30,8 178,6 139,5 139,5 145,9 53,7 25,8 179,7 122,5 78,9 171,9 229 229 Vzdálenost 3798,6

Rozvozní úloha model 2 – metoda výhodnostních čísel Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Břetislavova 69, Chrudim Rudolfovská 461/95, České Budějovice 1 Krašovská 16, Plzeň Fučíkova 153, Lužec nad Vltavou Kostelní 4, Dobruška U vysočanského pivovaru 9, Praha 9 Panská 6, Praha 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Masarykova 221, Lysá nad Labem B. Němcové 127, Lanškroun T. G. Masaryka 115, Ústí nad Orlicí Panská 1493, Rychnov nad Kněžnou Kamenice 113, Náchod Rooseveltova 459, Dvůr Králové náměstí Jiřího z Poděbrad 342, Hořice Krkonošská 10, Vrchlabí Husova 79, Jičín Českobratrské náměstí 1392, Mladá Boleslav Rybáře 750, Mělník Fučíkova 153, Lužec nad Vltavou Budovatelů 1987, Most Mostecká 2050, Litvínov náměstí 1. Máje 91, Chomutov třída Obránců míru 360, Žatec Česká 158, Louny Fučíkova 153, Lužec nad Vltavou Rvačov 136, Roudnice nad Labem Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Masarykova 538/16, Teplice Fučíkova 153, Lužec nad Vltavou U Dívčích hradů 12, Praha 5 K Hájům 4, Praha 5 Tylovická 207, Praha Zámek Nelahozeves, Nelahozeves 1 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou Mladoboleslavská 3287, Mělník

- 84 -

1 1 7 2 1 12 2 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 4 1 1 1 5 1,5

Jízda 1,98 0,63 2,95 2,18 2,03 2,62 2,08 0,27 0,72 0,27 0,27 1,13 2,65 0,47 0,5 0,67 0,65 0,37 0,88 0,77 0,7 0,83 0,3 1,13 0,27 0,5 0,42 0,55 1 0,43 0,72 0,45 0,67 0,87 0,88 0,22 0,13 0,83 0,35 0,78 0,78 0,33 0,68

Vzdálenost 138,5 33,7 183,5 142,7 139,5 171,9 136 7,4 42,8 10,5 10,5 50,1 177,9 19 25,8 35,4 30,8 18,9 47,7 36,6 36,2 44,6 10,8 75,8 13 25,9 22,4 21,5 56,2 25,2 47,4 24,6 33,7 65 48,4 6,3 3,8 32,1 15,3 45,4 45,4 12,7 37,4

2,5 3,5 3 2,5 2,5 6 9 5 7,5 4 3 3,5 2 1 2 1,5 -

Balbínova 14/192, Praha 2 Pražského 636/34, Praha 5 Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Janovského 48, Praha 7 Fučíkova 153, Lužec nad Vltavou náměstí Republiky 400, Neratovice Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou Fučíkova 153, Lužec nad Vltavou Plavební 735, Mělník Fučíkova 153, Lužec nad Vltavou Na Kačence 165, Praha 9 Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou Slévačská 744/1, Praha 9 Senovážné náměstí 2, Praha 1 Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Jirkovského 2603, Rakovník Nové náměstí 136, Štětí Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice 1. Máje 176, Lužec nad Vltavou Fučíkova 153, Lužec nad Vltavou Metoda výhodnostních čísel (VRP)

Činnosti

Celkem

140

- 85 -

0,25 0,92 0,02 0,02 0,63 0,63 0,58 0,58 0,4 0,4 0,27 0,27 0,6 0,6 0,77 0,77 0,62 0,33 0,7 0,32 1,15 1,5 0,5 0,18 0,17 0,02 Jízda 51,11

9,6 52,4 0,1 0,1 40,1 40,1 24,9 24,9 17,6 17,6 10,1 10,1 36,5 36,5 44,9 44,9 38,7 9,5 42,3 14,5 59,6 84 23,5 6,3 5,9 0,4 Vzdálenost 2903,4

Rozvozní úloha model 2 – metoda nejlevnějšího vkládání Uzel

Činnost

Fučíkova 153, Lužec nad Vltavou Mělnická 150, Lužec nad Vltavou 1. Máje 176, Lužec nad Vltavou Rybáře 750, Mělník Balbínova 14/192, Praha 2 Rudolfovská 461/95, České Budějovice 1 Fučíkova 153, Lužec nad Vltavou U školky 306, Horní Beřkovice Slévačská 744/1, Praha 9 U vysočanského pivovaru 9, Praha 9 Zámek Nelahozeves, Nelahozeves 1 Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Riegrova 330, Veltrusy Na Kačence 165, Praha 9 U Koruny 73, Hradec Králové T. G. Masaryka 115, Ústí nad Orlicí B. Němcové 127, Lanškroun Mladoboleslavská 3287, Mělník Fučíkova 153, Lužec nad Vltavou Kamenice 113, Náchod Kostelní 4, Dobruška Panská 1493, Rychnov nad Kněžnou Fučíkova 153, Lužec nad Vltavou Českobratrské náměstí 1392, Mladá Boleslav Husova 79, Jičín náměstí Jiřího z Poděbrad 342, Hořice Rooseveltova 459, Dvůr Králové Fučíkova 153, Lužec nad Vltavou Nové náměstí 136, Štětí náměstí Republiky 400, Neratovice Krkonošská 10, Vrchlabí Fučíkova 153, Lužec nad Vltavou Janovského 48, Praha 7 Břetislavova 69, Chrudim Masarykova 221, Lysá nad Labem Fučíkova 153, Lužec nad Vltavou Panská 6, Praha 1 K Hájům 4, Praha 5 Krašovská 16, Plzeň Fučíkova 153, Lužec nad Vltavou Česká 158, Louny

- 86 -

3 1,5 1 2,5 7 2 4 12 1 20 3,5 5 1 1 1 1,5 1 1 1 1 1 1 1 1 2,5 1 2,5 1 1 2 1 2 1

Jízda 0,02 0,02 0,22 0,75 2,13 2,82 0,18 0,63 0,1 0,62 0,35 0,27 0,27 0,32 0,43 1,52 1,1 0,47 3,15 0,33 2,52 0,38 0,33 2,73 1,08 0,7 0,38 0,37 2,23 0,5 0,58 1,98 2,23 0,63 1,87 1,53 1,13 0,72 0,37 1,2 2,03 1 0,55

Vzdálenost 0,1 0,6 10,4 38,5 149,6 192 6,3 37,9 3 30,8 15,3 10,5 10,5 14,5 23,4 106 59,2 19 213,1 12,7 178,6 18,4 17,7 179,7 56 36,2 23,6 18,9 128,4 23,5 28,5 118,1 122,5 40,1 118,8 94,8 50,1 42,8 11,7 86,5 139,5 56,2 21,5

1 1 1 1 1 1 1 3 3 1 2 4 3,5 5 7,5 6 9 -

třída Obránců míru 360, Žatec náměstí 1. Máje 91, Chomutov Budovatelů 1987, Most Mostecká 2050, Litvínov Masarykova 538/16, Teplice Fučíkova 153, Lužec nad Vltavou Hrnčířská 4, Ústí nad Labem Tržní 28, Děčín Rvačov 136, Roudnice nad Labem Fučíkova 153, Lužec nad Vltavou Senovážné náměstí 2, Praha 1 Tylovická 207, Praha Jirkovského 2603, Rakovník Fučíkova 153, Lužec nad Vltavou U Dívčích hradů 12, Praha 5 Pražského 636/34, Praha 5 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou Heleny Malířové 16, Praha 6 Fučíkova 153, Lužec nad Vltavou Jiráskova 496, Kralupy nad Vltavou Fučíkova 153, Lužec nad Vltavou Plavební 735, Mělník Fučíkova 153, Lužec nad Vltavou Metoda nejlevnějšího vkládání (VRP)

Činnosti

Celkem

140

- 87 -

0,42 0,47 0,27 0,42 0,87 0,92 0,45 1,1 0,43 0,7 0,38 0,88 1,22 0,88 0,18 0,92 0,78 0,78 0,77 0,77 0,4 0,4 0,27 0,27 Jízda 57,69

22,4 23,7 13 23,6 65 64,3 24,6 51,7 25,2 42,3 12 49,8 65,8 48,4 5,1 52,4 45,4 45,4 44,9 44,9 17,6 17,6 10,1 10,1 Vzdálenost 3390,8

Rozvozní úloha model 1 – LINGO Vstupní data:

Časy

Fučíkova 153, Lužec nad Vltavou

U Koruny 73, Hradec Králové

Boleslavova 10, Praha 4

Balbínova 14/192, Praha 2

Zámek Nelahozeves, Nelahozeves 1

0,00

1,98

0,78

0,70

0,35

1,98

0,00

1,52

1,55

1,88

0,78

1,52 1,55

6,00 0,00

0,77

0,70

0,00 6,00

0,35

1,88

0,77

0,68

0,00

Fučíkova 153, Lužec nad Vltavou

U Koruny 73, Hradec Králové

Boleslavova 10, Praha 4

Balbínova 14/192, Praha 2

Zámek Nelahozeves, Nelahozeves 1

0,0

138,5

45,4

43,0

15,3

138,5

0,0

113,6

111,6

135,8

45,4 43,0

113,6 111,6

0,0 2,8

2,8 0,0

42,2 39,8

15,3

135,8

42,2

39,8

0,0

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Boleslavova 10, Praha 4 Balbínova 14/192, Praha 2 Zámek Nelahozeves, Nelahozeves 1

Vzdálenosti

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Boleslavova 10, Praha 4 Balbínova 14/192, Praha 2 Zámek Nelahozeves, Nelahozeves 1

Adresa

Doba trvání činnosti

Fučíkova 153, Lužec nad Vltavou

0,00

U Koruny 73, Hradec Králové

1,00

Boleslavova 10, Praha 4

5,00

Balbínova 14/192, Praha 2

2,50

Zámek Nelahozeves, Nelahozeves 1

1,00

- 88 -

0,68

Výsledky:

Uzel

Činnost 1 2,5 1 5 -

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Balbínova 14/192, Praha 2 Zámek Nelahozeves, Nelahozeves 1 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou LINGO (VRP)

Činnosti

Celkem

9,5

- 89 -

Jízda 1,98 1,55 0,68 0,35 0,78 0,78 Jízda 6,12

Vzdálenost 138,5 111,6 39,8 15,3 45,5 45,5 Vzdálenost 396,2

Rozvozní úloha model 2 – LINGO Vstupní data:

Časy

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Na Průhoně 3412, Mělník 1 Boleslavova 10, Praha 4 Balbínova 14/192, Praha 2

Vzdálenosti

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Na Průhoně 3412, Mělník 1 Boleslavova 10, Praha 4 Balbínova 14/192, Praha 2

Fučíkova 153, Lužec nad Vltavou 0 1,98 0,27 0,78 0,7

U Koruny 73, Hradec Králové 1,98 0 1,9 1,52 1,55

Fučíkova 153, Lužec nad Vltavou 0,0 138,5 10,5 45,4 43,0

U Koruny 73, Hradec Králové

Na Průhoně 3412, Mělník 1

138,5 0,0 126,1 113,6 111,6

10,5 126,1 0,0 50,3 47,9

Adresa

Doba trvání činnosti

Fučíkova 153, Lužec nad Vltavou U Koruny 73, Hradec Králové Na Průhoně 3412, Mělník 1 Boleslavova 10, Praha 4 Balbínova 14/192, Praha 2

0 1 20 5 2,5

- 90 -

Na Průhoně 3412, Mělník 1

Boleslavova 10, Praha 4

Balbínova 14/192, Praha 2

0,27 1,9 0 0,85 0,77

0,78 1,52 0,85 0 6

0,7 1,55 0,77 6 0

Boleslavova Balbínova 10, Praha 4 14/192, Praha 2

45,4 113,6 50,3 0,0 2,8

43,0 111,6 47,9 2,8 0,0

Výsledky: Uzel

Činnost 20 5 2,5 1 -

Fučíkova 153, Lužec nad Vltavou Na Průhoně 3412, Mělník 1 Fučíkova 153, Lužec nad Vltavou Boleslavova 10, Praha 4 Fučíkova 153, Lužec nad Vltavou Balbínova 14/192, Praha 2 U Koruny 73, Hradec Králové Fučíkova 153, Lužec nad Vltavou LINGO (VRP)

Činnosti

Celkem

28,5

- 91 -

Jízda 0,27 0,27 0,78 0,78 0,7 1,55 1,98 Jízda 6,33

Vzdálenost 10,5 10,5 45,5 45,5 43 111,6 138,5 Vzdálenost 405,1

Obsah CD Na přiloženém CD jsou následující soubory: 



  

Data.xls – v souboru je zadání úlohy, a data pro LINGO. Listy Čas 1 a Činnosti 1 jsou pro úlohu obchodního cestujícího a pro rozvozní úlohu - model 2. Listy Čas 2 a Činnosti 2 jsou určeny pro rozvozní úlohu model 1. Heuristiky.xls – aplikace pro řešení heuristických metod nejbližšího souseda, výhodnostních čísel a nejlevnějšího vkládání. Na listech Revize_Vzdalenosti, Revize_Cinnosti a Revize_Cas jsou data pro řešení úlohy obchodního cestujícího a rozvozní úlohy - model 1. Na listech Revize_Vzdalenosti (2), Revize_Cinnosti (2) a Revize_Cas (2) jsou data pro řešení rozvozní úlohy – model 1. Rozvozni_uloha_model_1.lg4 – rozvozni úloha – model 1 pro LINGO. Rozvozni_uloha_model_2.lg4 – rozvozni úloha – model 2 pro LINGO. Uloha_obchodniho_cestujiciho.lg4 – model úlohy obchodního cestujícího pro LINGO.

- 92 -