ˇ e vysok´e uˇcen´ı technick´e v Praze Cesk´ Fakulta dopravn´ı
´ PRACE ´ DIPLOMOVA
´ ˚ V ULOH ´ ´ ´ TN´I V YU Zˇ IT´I GENETICK YCH ALGORITM U ACH DISKR E OPTIMALIZACE
Alena Rybiˇckov´a
2012
Prohl´asˇen´ı Nem´am z´avaˇzn´y d˚uvod proti uˇz´ıv´an´ı tohoto sˇkoln´ıho d´ıla ve smyslu § 60 Z´akona cˇ .121/2000 Sb., o pr´avu autorsk´em, o pr´avech souvisej´ıc´ıch s pr´avem autorsk´ym a o zmˇenˇe nˇekter´ych z´akon˚u (autorsk´y z´akon).
5
Prohl´asˇen´ı Prohlaˇsuji, zˇ e jsem pˇredloˇzenou pr´aci vypracovala samostatnˇe a zˇ e jsem uvedla veˇsker´e pouˇzit´e informaˇcn´ı zdroje v souladu s Metodick´ym pokynem o etick´e pˇr´ıpravˇe vysokoˇskolsk´ych z´avˇereˇcn´ych prac´ı.
V Praze dne Alena Rybiˇckov´a
6
Podˇekov´an´ı Na tomto m´ıstˇe bych r´ada podˇekovala vˇsem, kteˇr´ı se pod´ıleli na vzniku t´eto pr´ace. Pˇredevˇs´ım sv´e vedouc´ı Ing. Denise Mockov´e, Ph.D. za veden´ı diplomov´e pr´ace a cenn´e rady.
7
Abstrakt Diplomov´a pr´ace se zab´yv´a vyuˇzit´ım genetick´ych algoritm˚u v optimalizaˇcn´ıch u´ loh´ach v dopravˇe - u´ loze okruˇzn´ıch j´ızd a lokaˇcn´ıch u´ loh´ach. V teoretick´e cˇ a´ sti jsou definov´any a pˇredstaveny oba typy u´ loh, jejich varianty a moˇzn´e zp˚usoby ˇreˇsen´ı. D´ale je pops´an obecn´y princip fungov´an´ı genetick´ych algoritm˚u. V praktick´e cˇ a´ sti je pro obˇe u´ lohy vytvoˇren genetick´y algoritmus s v´ıce moˇznostmi pouˇzit´ych oper´ator˚u a otestov´an na re´aln´e u´ loze distribuce n´ahradn´ıch d´ıl˚u pro autoservisy. Souˇca´ st´ı ˇreˇsen´ı je porovn´an´ı v´ysledk˚u v pˇr´ıpadˇe u´ lohy okruˇzn´ıch j´ızd s heuristickou Clarke-Wrightovou metodou, v pˇr´ıpadˇe lokaˇcn´ıch u´ loh s exaktn´ım ˇreˇsen´ım.
8
Abstract This master thesis focuses on the use of genetic algorithms in transportation-optimization problems - vehicle routing problem and location problem. In the theoretical part both types of problems, their variants and possible solution are defined and introduced. Further, general principles of genetic algorithms are described. In the practical part a specific genetic algorithm with several possible operators for both problems is proposed and tested on a real problem of spare parts distribution for garages. Part of the solution is the comparison with Clarke-Wright heuristic method in case of vehicle routing problem and comparison with exact solution in case of location problem.
9
O BSAH
Seznam obr´azk˚u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Seznam tabulek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Seznam pˇr´ıloh na CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1
´ Uvod
16
2
´ Ulohy diskr´etn´ı optimalizace
19
2.1
Sloˇzitost algoritm˚u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.2
Lokaˇcn´ı u´ lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3
´ Uloha okruˇzn´ıch j´ızd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.4
Metody ˇreˇsen´ı u´ loh diskr´etn´ı optimalizace . . . . . . . . . . . . . . . . . . . .
29
3
4
5
Genetick´e algoritmy
37
3.1
Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.2
Princip genetick´eho algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.3
V´ıcekriteri´aln´ı u´ lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Clarke-Wrightova metoda
45
4.1
Princip Clarke-Wrightovy metody . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2
V´ysledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
´ Aplikace genetick´ych algoritmu˚ na ulohu okruˇzn´ıch j´ızd
50
5.1
50
N´avrh genetick´eho algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
5.2
V´ysledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
5.3
Porovn´an´ı v´ysledk˚u GA a CW . . . . . . . . . . . . . . . . . . . . . . . . . .
73
6
´ Aplikace genetick´ych algoritmu˚ na lokaˇcn´ı ulohu
74
7
Z´avˇer
82
Literatura
84
A Seznam autoservisu˚
88
11
´ U˚ S EZNAM OBR AZK
3.1
V´ybˇer pomoc´ı v´azˇ en´e rulety . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2
Z´akladn´ı typy kˇr´ızˇ en´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.3
Z´akladn´ı typy mutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.1
Sch´ema v´ypoˇctu u´ spor u Clarke-Wrightovy metody . . . . . . . . . . . . . . .
46
4.2
Trasy z´ıskan´e pomoc´ı Clarke-Wrightovy metody . . . . . . . . . . . . . . . .
48
5.1
Pˇr´ıklad reprezentace genomu . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.2
Pˇr´ıklad kˇr´ızˇ en´ı
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.3
Pr˚ubˇeh algoritmu - varianta 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
5.4
Pr˚ubˇeh algoritmu - varianta 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.5
Pr˚ubˇeh algoritmu - varianta 3 . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.6
Pr˚ubˇeh algoritmu - varianta 4 . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
5.7
Pr˚ubˇeh algoritmu - varianta 5 . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.8
Pr˚ubˇeh algoritmu - varianta 6 . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
5.9
Nejlepˇs´ı nalezen´e ˇreˇsen´ı - Praha . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.10 Srovn´an´ı minim´aln´ıch nalezen´ych hodnot . . . . . . . . . . . . . . . . . . . .
70
5.11 Srovn´an´ı prvn´ıch 200 krok˚u algoritmu . . . . . . . . . . . . . . . . . . . . . .
70
5.12 Nejlepˇs´ı nalezen´e ˇreˇsen´ı - Brno . . . . . . . . . . . . . . . . . . . . . . . . . .
72
6.1
Rozloˇzen´ı hodnot fitenss funkce pro dvˇe umist’ovan´a stˇrediska . . . . . . . . .
78
6.2
Rozloˇzen´ı hodnot fitenss funkce pro tˇri umist’ovan´a stˇrediska . . . . . . . . . .
78
12
6.3
Nejlepˇs´ı nalezen´e trasy po zmˇenˇe um´ıstˇen´ı dep . . . . . . . . . . . . . . . . .
13
80
S EZNAM TABULEK
5.1
Minim´aln´ı hodnoty fitness funkce pro variantu 1 . . . . . . . . . . . . . . . . .
56
5.2
Minim´aln´ı hodnoty fitness funkce pro variantu 2 . . . . . . . . . . . . . . . . .
58
5.3
Minim´aln´ı hodnoty fitness funkce pro variantu 3 . . . . . . . . . . . . . . . . .
60
5.4
Minim´aln´ı hodnoty fitness funkce pro variantu 4 . . . . . . . . . . . . . . . . .
62
5.5
Minim´aln´ı hodnoty fitness funkce pro variantu 5 . . . . . . . . . . . . . . . . .
64
5.6
Minim´aln´ı hodnoty fitness funkce pro variantu 6 . . . . . . . . . . . . . . . . .
66
5.7
Minim´aln´ı hodnoty fitness funkce pro trasy z brnˇensk´eho depa . . . . . . . . .
71
5.8
Srovn´an´ı nalezen´ych ˇreˇsen´ı z CW a GA . . . . . . . . . . . . . . . . . . . . .
73
6.1
Minim´aln´ı hodnoty fitness funkce pro 2 umist’ovan´a stˇrediska . . . . . . . . . .
77
6.2
Minim´aln´ı hodnoty fitness funkce pro 3 umist’ovan´a stˇrediska . . . . . . . . . .
77
6.3
Srovn´an´ı nalezen´ych ˇreˇsen´ı z CW a GA . . . . . . . . . . . . . . . . . . . . .
79
ˇ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Seznam autoservis˚u v CR
91
14
S EZNAM P Rˇ ´I LOH NA CD
Diplomov´a pr´ace v pdf Pˇr´ıloha cˇ .1 – Program pro generov´an´ı vzd´alenost´ı Pˇr´ıloha cˇ .2 – Implementace Clarke-Wrightova algoritmu Pˇr´ıloha cˇ .3 – Implementace genetick´eho algoritmu pro u´ lohu okruˇzn´ıch j´ızd Pˇr´ıloha cˇ .4 – Implementace genetick´eho algoritmu pro lokaˇcn´ı u´ lohu
15
K APITOLA 1 ´ Uvod
Bˇehem cel´e historie cˇ el´ı lidstvo optimalizaˇcn´ım probl´em˚um a zab´yv´a se ot´azkou jak je co nejl´epe vyˇreˇsit. Poˇca´ tky praktick´e optimalizace jako vˇedy o pˇridˇelov´an´ı omezen´ych zdroj˚u ˇ s co nejlepˇs´ım v´ysledn´ym efektem sahaj´ı do poloviny minul´eho stolet´ı. Rada z dnes bˇezˇ nˇe pouˇz´ıvan´ych technik m´a svoje koˇreny v metod´ach vyvinut´ych bˇehem druh´e svˇetov´e v´alky, kdy bylo nutn´e vypoˇra´ dat se s obrovsk´ymi logistick´ymi probl´emy vych´azej´ıc´ıch z potˇreby pˇresouvat do t´e doby nev´ıdan´e mnoˇzstv´ı lid´ı a techniky. Kaˇzd´a metoda, kter´a slibovala zlepˇsen´ı efektivity v´aleˇcn´eho snaˇzen´ı, byla velmi v´ıtan´a: jak´e je optim´aln´ı um´ıstˇen´ı z´asob nafty, jak´y je nejlepˇs´ı vzor pro hled´an´ı ponorek – na takov´e ot´azky se snaˇzily tyto metody odpovˇedˇet. Bˇehem v´alky byly vytvoˇreny z´aklady prvn´ı optimalizaˇcn´ı techniky pro rozs´ahl´e u´ lohy – simplexov´e metody, kter´a byla kr´atce po v´alce dovedena k dokonalosti v souvislosti s dostupnost´ı prvn´ıch poˇc´ıtaˇcu˚ . S n´astupem vˇedecko-technick´e revoluce, rozvojem modern´ıch technologi´ı a moˇznost´ı v´ypoˇcetn´ı techniky doˇslo k jeˇstˇe v´yraznˇejˇs´ımu n´ar˚ustu vyuˇzit´ı ˇr´ıd´ıc´ıch a optimalizaˇcn´ıch proces˚u ve vˇsech pr˚umyslov´ych odvˇetv´ıch. Se sloˇzitˇejˇs´ımi procesy ˇr´ızen´ı se rozˇsiˇruj´ı i u´ lohy, jeˇz je tˇreba ˇreˇsit. ´ ernˇe tomu roste v´yznam optimalizace a dnes hraj´ı optimalizaˇcn´ı techniky st´ale v´yznamnˇejˇs´ı Umˇ roli pˇri kaˇzdodenn´ıch ot´azk´ach v pr˚umyslov´em pl´anov´an´ı, alokov´an´ı zdroj˚u, rozvrhov´an´ı nebo rozhodov´an´ı. ˇ Rada probl´em˚u, kter´e jsou ˇreˇseny v r´amci operaˇcn´ıho v´yzkumu, vede na matematick´e modely obsahuj´ıc´ı celoˇc´ıseln´e promˇenn´e nebo je modelov´ana diskr´etn´ımi mnoˇzinami – hovoˇr´ıme o diskr´etn´ı optimalizaci. Vyuˇzit´ı tˇechto u´ loh se objevuje v mnoha pr˚umyslov´ych odvˇetv´ıch jako
16
je napˇr. v´yroba a distribuce, n´avrh telekomunikaˇcn´ıch nebo distribuˇcn´ıch s´ıt´ı, tvorba rozvrh˚u leteck´ych pos´adek, apod., i v aplikovan´e vˇedˇe (fyzika, biochemie, stroj´ırenstv´ı). V dopravn´ı problematice jsou pak nejˇcastˇeji ˇreˇsen´ymi u´ lohami probl´em obchodn´ıho cestuj´ıc´ıho, probl´em okruˇzn´ıch j´ızd, cˇ i lokaˇcn´ı u´ loha. V tˇechto u´ loh´ach je cˇ asto mnoˇzina vˇsech pˇr´ıpustn´ych ˇreˇsen´ı tak obs´ahl´a, zˇ e hrubou silou ani bˇezˇ n´ymi heuristick´ymi metodami nen´ı moˇzn´e naj´ıt ˇreˇsen´ı v pˇrijateln´em cˇ ase s pouˇzit´ım finanˇcnˇe pˇrimˇeˇren´e v´ypoˇcetn´ı techniky. Napˇr. v u´ loze obchodn´ıho cestuj´ıc´ıho je poˇcet vˇsech moˇzn´ych ˇreˇsen´ı moˇzn´e vypoˇc´ıtat jako faktori´al poˇctu bod˚u, kter´e m´a obchodn´ı cestuj´ıc´ı navˇst´ıvit, coˇz pro v´ıce neˇz zhruba 15 bod˚u cˇ in´ı prohled´av´an´ı prostoru vˇsech ˇreˇsen´ı prakticky neprovediteln´ym. Z toho d˚uvodu byly vyvinuty metody, oznaˇcovan´e jako metaheuristiky, kter´e pracuj´ı na principech kombinatorick´e optimalizace a hledaj´ı ˇreˇsen´ı nedeterministicky metodou postupn´eho iterativn´ıho zlepˇsovan´ı poˇca´ teˇcn´ıho ˇreˇsen´ı na omezen´em prostoru vˇsech pˇr´ıpustn´ych ˇreˇsen´ı. V´yhodou metaheuristik je polynomi´aln´ı cˇ asov´a n´aroˇcnost, naopak nev´yhodou je, zˇ e nen´ı zaruˇceno nalezen´ı optim´aln´ıho ˇreˇsen´ı. Metaheuristik existuje mnoho druh˚u, pˇriˇcemˇz v posledn´ı dobˇe k nejpouˇz´ıvanˇejˇs´ım patˇr´ı evoluˇcn´ı algoritmy. Evoluˇcn´ı algoritmy se nech´avaj´ı inspirovat procesy pˇrirozenˇe prob´ıhaj´ıc´ımi v pˇr´ırodˇe pˇri v´yvoji zˇ ivoˇciˇsn´ych a rostlinn´ych druh˚u, kdy vlastnosti jedinc˚u jedn´e generace (jejich genetick´a v´ybava) se jejich vz´ajemn´ym kˇr´ızˇ en´ım za souˇcasn´e pˇr´ıtomnosti n´ahodn´ych mutac´ı kombinuj´ı do vlastnost´ı potomk˚u tvoˇr´ıc´ıch n´asleduj´ıc´ı generaci. Ti pak proch´azej´ı v´ybˇerem, kter´y je ovlivnˇen selekˇcn´ımi tlaky okoln´ıho prostˇred´ı, a jen ti nejl´epe adaptovan´ı maj´ı nejvˇetˇs´ı nadˇeji na pˇreˇzit´ı a mohou dostat sˇanci pˇredat svoje geny do dalˇs´ı generace. Pˇri implementaci jsou vyuˇz´ıv´any r˚uzn´e varianty tvorby populac´ı, kter´e napodobuj´ı urˇcit´e konkr´etn´ı selekˇcn´ı mechanismy, kter´e funguj´ı v nˇekter´ych zˇ ivoˇciˇsn´ych nebo rostlinn´ych spoleˇcenstvech. Nezˇr´ıdka jsou vyuˇz´ıv´any i cˇ lovˇekem umˇele zkonstruovan´e mechanismy maj´ıc´ı za c´ıl ponˇekud vylepˇsit sice robustn´ı, leˇc ve sv´e podstatˇe jednoduchou a nˇekdy zdlouhavou pˇr´ırodn´ı metodu o prvky, kter´e maj´ı urychlit proces hled´an´ı optim´aln´ıho jedince, napˇr. v´ybˇerem tˇech nejlepˇs´ıch jedinc˚u populace pro kˇr´ızˇ en´ı a vytvoˇren´ı nov´e generace. C´ılem t´eto diplomov´e pr´ace je prozkoumat moˇznosti vyuˇzit´ı genetick´ych algoritm˚u pro u´ lohy diskr´etn´ı matematiky na konkr´etn´ım pˇr´ıkladˇe. Druh´a kapitola pr´ace pˇrin´asˇ´ı pˇrehled problematiky, algoritm˚u a metod ˇreˇsen´ı u´ loh diskr´etn´ı optimalizace a popisuje principy dvou v dopravˇe a logistice nejˇcastˇeji se vyskytuj´ıc´ıch u´ loh: u´ lohy okruˇzn´ıch j´ızd a lokaˇcn´ı u´ lohy.
17
Tˇret´ı kapitola bl´ızˇ e rozeb´ır´a jednu z podmnoˇzin metaheuristick´ych metod pouˇz´ıvan´ych k ˇreˇsen´ı tˇechto u´ loh – genetick´e algoritmy, jejich moˇznosti a principy. Ve cˇ tvrt´e kapitole, kter´a odkazuje na mou bakal´aˇrskou pr´aci ˇreˇs´ıc´ı probl´em optimalizace rozvozov´ych tras distribuˇcn´ı s´ıtˇe autoservis˚u Peugeot a Citro¨en, pak na praktick´em pˇr´ıkladu t´eto distribuˇcn´ı s´ıtˇe nalezneme s pomoc´ı nejzn´amˇejˇs´ı a nejpouˇz´ıvanˇejˇs´ı heuristick´e Clarke-Wrightovy metody ˇreˇsen´ı rozvozov´ych tras, kter´e n´am bude slouˇzit jako etalon pro srovn´an´ı s v´ysledky poskytovan´ymi genetick´ym algoritmem. V n´asleduj´ıc´ı p´at´e kapitole navrhneme nˇekolik variant genetick´eho algoritmu vhodn´ych k nalezen´ı optim´aln´ıch rozvozov´ych tras vzhledem k dan´emu um´ıstˇen´ı rozvozov´ych dep a dan´e s´ıti obsluhovan´ych bod˚u (´uloha okruˇzn´ıch j´ızd) a jejich v´ysledky porovn´ame s v´ysledky dosaˇzen´ymi Clarke-Wrightovou metodou. Posledn´ı sˇest´a kapitola pak ˇ hled´a optim´aln´ı um´ıstˇen´ı rozvozov´ych dep vzhledem k dan´e s´ıti servis˚u a silniˇcn´ı s´ıti Cesk´ e republiky (lokaˇcn´ı u´ loha) a pro tato nov´a um´ıstˇen´ı jsou pot´e genetick´ym algoritmem navrˇzeny optim´aln´ı rozvozov´e trasy a zhodnocena u´ spora.
18
K APITOLA 2 ´ Ulohy diskr´etn´ı optimalizace
Diskr´etn´ı optimalizace, cˇ asto oznaˇcovan´a tak´e jako kombinatorick´a optimalizace, patˇr´ı mezi nejmladˇs´ı oblasti diskr´etn´ı matematiky. Aˇckoli jej´ı koˇreny m˚uzˇ eme naj´ıt v kombinatorice, operaˇcn´ım v´yzkumu i teoretick´e informatice, jako samostatn´a oblast se vyˇclenila aˇz kolem poloviny dvac´at´eho stolet´ı. Vyuˇzit´ı u´ loh diskr´etn´ı optimalizace se objevuje v pr˚umyslov´ych odvˇetv´ıch (napˇr. v´yroba a distribuce, n´avrh telekomunikaˇcn´ıch s´ıt´ı, tvorba rozvrh˚u leteck´ych pos´adek) i v aplikovan´e vˇedˇe (statistika, fyzika, chemie). Pojem optimalizace zahrnuje celou ˇradu u´ loh, jejichˇz spoleˇcn´e vlastnosti lze shrnout do dvou bod˚u [1]: - jsou d´any omezuj´ıc´ı podm´ınky, kter´e popisuj´ı mnoˇzinu pˇr´ıpustn´ych ˇreˇsen´ı u´ lohy; - je d´ana tzv. u´ cˇ elov´a funkce, kter´a jednotliv´ym ˇreˇsen´ım pˇriˇrazuje jejich funkˇcn´ı hodnotu. C´ılem optimalizace je naj´ıt ˇreˇsen´ı, kter´e je vzhledem k u´ cˇ elov´e funkci minim´aln´ı (nebo maxim´aln´ı, dle ˇreˇsen´eho probl´emu). Podle charakteru omezuj´ıc´ıch podm´ınek m˚uzˇ eme optimalizaˇcn´ı u´ lohy rozdˇelit na dvˇe hlavn´ı skupiny - diskr´etn´ı a spojit´e. Mnoˇzina pˇr´ıpustn´ych ˇreˇsen´ı se v diskr´etn´ıch u´ loh´ach skl´ad´a z nˇekolika izolovan´ych bod˚u nebo oblast´ı, coˇz odpov´ıd´a tomu, zˇ e je v matematice vyjadˇrujeme pomoc´ı cel´ych cˇ´ısel. Takov´e u´ lohy se vyskytuj´ı pˇredevˇs´ım v kombinatorice, a proto se tak´e pojmy kombinatorick´e a diskr´etn´ı optimalizace zamˇenˇ uj´ı. V pˇr´ıpadˇe, zˇ e uvaˇzujeme obecnˇejˇs´ı 19
minimalizaci (resp. maximalizaci) funkce v prostoru re´aln´ych parametr˚u, jedn´a se o spojitou optimalizaci.
2.1
Sloˇzitost algoritmu˚
V u´ loh´ach diskr´etn´ı optimalizace je cˇ asto mnoˇzina vˇsech pˇr´ıpustn´ych ˇreˇsen´ı velmi rozs´ahl´a. Napˇr´ıklad u u´ lohy obchodn´ıho cestuj´ıc´ıho lze poˇcet vˇsech moˇzn´ych ˇreˇsen´ı vypoˇc´ıtat jako faktori´al poˇctu bod˚u, kter´e m´a obchodn´ı cestuj´ıc´ı navˇst´ıvit. Vzhledem k poˇctu pˇr´ıpustn´ych ˇreˇsen´ı je u algoritm˚u diskr´etn´ı optimalizace d˚uleˇzit´e prov´est ˇ anal´yzu, kterou b´yv´a nejˇcastˇeji anal´yza cˇ asov´a, nˇekdy tak´e anal´yza pamˇet’ov´a. Casov´ a sloˇzitost algoritmu popisuje, kolik operac´ı se provede v z´avislosti na velikosti vstupu. Zaj´ım´a-li n´as sloˇzitost algoritmu, jedn´a se obvykle o asymptotick´e chov´an´ı funkce f (poˇctu operac´ı) pˇri velk´ych hodnot´ach vstupu n. Pro odhad cˇ asov´e sloˇzitosti se nejˇcastˇeji pouˇz´ıv´a oper´ator O, kter´y znaˇc´ı horn´ı asymptotick´y odhad. Z´apis f ∈ O(g) tedy znamen´a, zˇ e f roste nejv´ysˇe tak rychle jako g. Teorie sloˇzitosti rozliˇsuje nˇekolik tˇr´ıd u´ loh. Vˇetˇsina algoritm˚u, kter´e jsou dnes bˇezˇ nˇe pouˇz´ıv´any at’ uˇz v dopravˇe cˇ i jin´ych oblastech, m´a polynomi´aln´ı cˇ asovou sloˇzitost, kterou s pouˇzit´ım oper´atoru O m˚uzˇ eme zapsat jako O(nc ) pro nˇejakou konstantu c. Probl´emy, pro kter´e existuj´ı algoritmy s polynomi´aln´ı cˇ asovou sloˇzitost´ı, oznaˇcujeme jako patˇr´ıc´ı do tˇr´ıdy P (nebo tak´e zvl´adnuteln´e), pro ˇradu praktick´ych probl´em˚u vˇsak nejsou takov´e algoritmy zn´amy. Mezi typick´e u´ lohy z dopravy ze tˇr´ıdy P patˇr´ı napˇr. probl´em nejkratˇs´ı cesty v grafu, hled´an´ı minim´aln´ı kostry grafu nebo dopravn´ı probl´em. Pokud m´a algoritmus vyˇssˇ´ı sloˇzitost neˇz polynomi´aln´ı, typicky exponenci´aln´ı, je moˇzn´e ho pouˇz´ıt pouze pro mal´e hodnoty n. Pro vˇetˇs´ı vstupy by bˇeh programu v rozumn´em cˇ ase v˚ubec neskonˇcil. Probl´emy, kter´e nepatˇr´ı do tˇr´ıdy P oznaˇcujeme jako nezvl´adnuteln´e. S takov´ymi u´ lohami se setk´av´ame v nejr˚uznˇejˇs´ıch oblastech teoretick´e matematiky i aplikovan´ych vˇed. Protoˇze maj´ı tyto u´ lohy cˇ asto d˚uleˇzit´e praktick´e vyuˇzit´ı, ale moˇznosti naj´ıt optim´aln´ı ˇreˇsen´ı existuj´ı pouze pro mal´e vstupy, hledaj´ı se algoritmy, kter´e v polynomi´aln´ım cˇ ase vr´at´ı alespoˇn ,,skoro optim´aln´ı ˇreˇsen´ı”. Takov´ym algoritm˚um ˇr´ık´ame polynomi´aln´ı aproximaˇcn´ı algoritmy.
20
V dopravˇe do t´eto skupiny u´ loh patˇr´ı napˇr.: - probl´em hamiltonovsk´e kruˇznice, - probl´em obchodn´ıho cestuj´ıc´ıho, - probl´em okruˇzn´ıch j´ızd, - lokaˇcn´ı u´ lohy. Tyto u´ lohy patˇr´ı k nejˇcastˇeji zkouman´ym probl´em˚um z oblasti diskr´etn´ı optimalizace a byla pro nˇe vyvinuta ˇrada aproximaˇcn´ıch algoritm˚u. Algoritmy pro hled´an´ı pˇribliˇzn´ych ˇreˇsen´ı m˚uzˇ eme rozdˇelit do dvou z´akladn´ıch kategori´ı. Obecn´e heuristiky oznaˇcovan´e tak´e jako metaheuristiky se daj´ı pouˇz´ıt pro celou ˇradu kombinatorick´ych u´ loh, zat´ımco probl´emovˇe specifick´e heuristiky ˇreˇs´ı pouze jednu konkr´etn´ı u´ lohu. V n´asleduj´ıc´ım textu se zamˇeˇr´ıme na ty u´ lohy, kter´e pozdˇeji vyuˇzijeme pro ˇreˇsen´ı praktick´eho probl´emu z oblasti optimalizace z´asobov´an´ı autoservis˚u - lokaˇcn´ı u´ lohy a probl´em okruˇzn´ıch j´ızd. Pop´ısˇeme obecn´e zad´an´ı u´ loh, moˇzn´e varianty a nˇekter´e moˇznosti ˇreˇsen´ı.
2.2
´ Lokaˇcn´ı ulohy
Pl´anov´an´ı optim´aln´ıho um´ıstˇen´ı logistick´ych stˇredisek patˇr´ı mezi v´yznamn´e rozhodovac´ı probl´emy. To, kter´e m´ısto zvol´ıme jako nejlepˇs´ı, z´aleˇz´ı na ˇradˇe krit´eri´ı, kter´ymi m˚uzˇ e b´yt optim´aln´ı vzd´alenost, kapacita stˇrediska, hustota os´ıdlen´ı, v´ysˇe n´aklad˚u apod. Nejˇcastˇeji se pouˇz´ıv´a krit´erium vzd´alenosti, ale re´aln´e probl´emy jsou cˇ asto komplexnˇejˇs´ı a je nutn´e zahrnout do u´ lohy kombinaci v´ıce krit´eri´ı najednou. C´ılem lokaˇcn´ıch u´ loh je pak naj´ıt um´ıstˇen´ı pro dan´y poˇcet stˇredisek tak, aby byla hodnota zvolen´e kriteri´aln´ı funkce minim´aln´ı (resp. maxim´aln´ı u maximalizaˇcn´ı u´ lohy). Na z´akladˇe v´ybˇeru kriteri´aln´ı funkce rozliˇsujeme u´ lohy jedno- nebo v´ıcekriteri´aln´ı. Lokaˇcn´ı probl´em byl poprv´e pˇredstaven Cooperem [2] a rozˇs´ıˇren na v´azˇ enou s´ıt’ Hakimim [3]. K dalˇs´ımu rozvoji pˇrispˇeli napˇr. Badri [4], Klose a Drexl [5], Henrik a Robert [6].
21
Terminologie Pˇredt´ım neˇz lokaˇcn´ı u´ lohy rozebereme podrobnˇeji, je tˇreba vysvˇetlit z´akladn´ı pojmy. Mezi z´akladn´ı komponenty lokaˇcn´ıch u´ loh patˇr´ı stˇrediska, obsluhovan´e vrcholy (resp. hrany) a atrakˇcn´ı obvody. V r˚uzn´ych typech lokaˇcn´ıch u´ loh se jejich role mohou liˇsit.
Stˇredisko Pojmem stˇredisko nebo depo je v lokaˇcn´ıch u´ loh´ach oznaˇcov´an objekt, jehoˇz prostorov´e um´ıstˇen´ı je optimalizov´ano pouˇzit´ım zvolen´eho modelu nebo algoritmu, kter´y zahrnuje vz´ajemn´e vztahy stˇrediska s jiˇz existuj´ıc´ımi objekty v syst´emu. Pˇr´ıklady stˇredisek mohou b´yt napˇr. obchody, sˇkoly, nemocnice, sklady, stanice poˇza´ rn´ı nebo z´achrann´e sluˇzby. Jedn´ım ze z´akladn´ıch parametr˚u lokaˇcn´ıch model˚u je poˇcet stˇredisek, kter´a je potˇreba um´ıstit. Nejjednoduˇssˇ´ım pˇr´ıpadem je lokace pouze jednoho stˇrediska, cˇ astˇeji ovˇsem uvaˇzujeme v´ıce stˇredisek, kter´a jsou umist’ov´ana z´aroveˇn. Dalˇs´ım d˚uleˇzit´ym parametrem je typ stˇrediska. Ten zahrnuje kapacitu stˇrediska a sluˇzby, kter´e stˇredisko poskytuje. Kapacita m˚uzˇ e b´yt omezen´a nebo neomezen´a podle velikosti popt´avky, kterou m˚uzˇ e stˇredisko obslouˇzit. Klasifikace m˚uzˇ e prob´ıhat tak´e na z´akladˇe sluˇzeb, kter´e stˇredisko nab´ız´ı. Rozliˇsujeme stˇrediska, kter´a nab´ız´ı pouze jednu sluˇzbu nebo skupinu sluˇzeb. Dalˇs´ım v´yznamn´ym parametrem jsou n´aklady. Uvaˇzujeme zde dva druhy n´aklad˚u - fixn´ı a variabiln´ı. Fixn´ı n´aklady se vztahuj´ı ke zˇr´ızen´ı stˇrediska, zat´ımco variabiln´ı z´avis´ı pˇredevˇs´ım na zp˚usobu zajiˇstˇen´ı sluˇzeb, kter´e stˇredisko nab´ız´ı.
Obsluhovan´e vrcholy a hrany Druhou z´akladn´ı souˇca´ st´ı lokaˇcn´ıch u´ loh jsou vrcholy. Ve vrcholech jsou um´ıstˇeni z´akazn´ıci, kteˇr´ı poˇzaduj´ı dostupnost sluˇzby nebo z´asobov´an´ı zboˇz´ım. Protoˇze je lokaˇcn´ı probl´em u´ zce spojen´y s uspokojen´ım popt´avky z´akazn´ık˚u, je d˚uleˇzit´e zn´at jej´ı rozloˇzen´ı, objem a chov´an´ı. V jin´ych typech u´ loh jsou zdojem poˇzadavk˚u cel´e hrany, v tomto pˇr´ıpadˇe mluv´ıme o hranov´e lokaci. Jedn´a se napˇr. o zajiˇstˇen´ı zimn´ı u´ drˇzby silnic.
22
Atrakˇcn´ı obvod Jako atrakˇcn´ı obvod oznaˇcujeme sp´adovou oblast patˇr´ıc´ı k dan´emu depu. Atrakˇcn´ı obvod depa A(v) je mnoˇzina vrchol˚u a hran s´ıtˇe obsluhovan´ych pouze z jednoho depa v ∈ Dk , pro kter´e plat´ı: vrchol u ∈ A(v), pokud neexistuje depo w ∈ Dk , pro kter´e d(w, u) < d(v, u); hrana h ∈ A(v), pokud neexistuje depo w ∈ Dk , pro kter´e d(w, h) < d(v, h), kde d(u, v) je zvolen´a metrika. Prvotn´ı atrakˇcn´ı obvod depa A0 (v) je mnoˇzina vrchol˚u a hran s´ıtˇe obsluhovan´ych z depa v ∈ Dk , pro kter´e plat´ı: vrchol u ∈ A0 (v), pokud neexistuje depo w ∈ Dk , pro kter´e d(w, u) ≤ d(v, u); hrana h ∈ A0 (v), pokud neexistuje depo w ∈ Dk , pro kter´e d(w, h) ≤ d(v, h). Pˇridˇelen´y atrakˇcn´ı obvod A∗ (v) je mnoˇzina vrchol˚u a hran s´ıtˇe obsluhovan´ych z depa v ∈ Dk , pro kter´e plat´ı: A0 (v) ⊆ A∗ (v) ⊆ A(v) pro kaˇzd´e depo v ∈ Dk ; S v∈Dk
A∗ (v) = X ∪ V ,
A∗ (v) ∩ A∗ (u) = ∅ pro u 6= v; u, v ∈ Dk , kde mnoˇzina X oznaˇcuje mnoˇzinu vˇsech hran a V mnoˇzinu vˇsech vrchol˚u.
Matematick´a formulace Lokaˇcn´ı u´ loha (v angliˇctinˇe oznaˇcovan´a jako Uncapacitated Facility Location Problem), tj. u´ loha, ve kter´e uvaˇzujeme neomezenou kapacitu stˇredisek, m˚uzˇ e b´yt definov´ana n´asledovnˇe [7]: Necht’ je d´ana mnoˇzina z´akazn´ık˚u I = 1, ..., m, kteˇr´ı maj´ı b´yt obslouˇzeni, a mnoˇzina moˇzn´ych um´ıstˇen´ı stˇredisek J = 1, ..., n. Pro um´ıstˇen´ı stˇrediska do m´ısta j ∈ J jsou d´any fixn´ı n´aklady fj a pro uspokojen´ı popt´avky z´akazn´ıka i ∈ I ze stˇrediska j ∈ J jsou d´any n´aklady cij . D´ale uvaˇzujeme: 23
xij = 1, pokud stˇredisko j zajiˇst’uje obsluhu z´akazn´ıka i, xij = 0 jinak,
yj = 1, pokud je v m´ıstˇe j um´ıstˇeno stˇredisko, yj = 0 jinak. Potom m˚uzˇ e b´yt model formulov´an n´asledovnˇe. Hled´ame minimum u´ cˇ elov´e funkce: m X n X
cij xij +
i=1 j=1
n X
fj y j
j=1
za podm´ınek: n X j=1
xij = 1, pro ∀i
xij − yj ≤ 0, pro ∀i, ∀j xij ∈ {0, 1}, pro ∀i, ∀j yj ∈ {0, 1}, pro ∀j
´ Modely lokaˇcn´ıch uloh Lokaˇcn´ı u´ lohy a modely, kter´e je mohou reprezentovat, lze rozdˇelit podle r˚uzn´ych krit´eri´ı [8].
Spojit´e a s´ıt’ov´e lokaˇcn´ı modely V nˇekter´ych situac´ıch je vhodn´e umoˇznit, aby stˇrediska mohla b´yt um´ıstˇena kdekoli v r´amci dan´e oblasti. Tak´e poˇzadavky mohou b´yt modelov´any jako spojitˇe rozm´ıstˇen´e v uvaˇzovan´em prostoru. V tˇechto pˇr´ıpadech se jedn´a o spojit´e modely. Tyto modely jsou nejvhodnˇejˇs´ı, pokud chceme zn´at pˇribliˇzn´y odhad poˇctu stˇredisek a kde pˇribliˇznˇe by mˇela b´yt stˇrediska um´ıstˇena. Za pˇredch˚udce spojit´ych lokaˇcn´ıch u´ loh m˚uzˇ eme povaˇzovat Weberovu u´ lohu [9], kter´a hled´a stˇred gravitace mnoˇziny bod˚u. Dalˇs´ı v´yzkum tohoto typu u´ loh byl zaloˇzen na geometrickopravdˇepodobnostn´ı teorii [10], v tomto pˇr´ıpadˇe bylo snahou zahrnout i n´aklady na provoz vozidel. Spojit´e modely se pot´ykaj´ı s mnoˇzstv´ım v´ypoˇcetn´ıch i praktick´ych probl´em˚u. Vedou na neline´arn´ı rovnice, kter´e je sloˇzit´e ˇreˇsit, pˇredevˇs´ım v pˇr´ıpadech, kdy poˇzadujeme um´ıstˇen´ı 24
v´ıce neˇz jednoho stˇrediska. Z praktick´eho hlediska je v´ysledn´ym ˇreˇsen´ım tˇechto model˚u cˇ asto um´ıstˇen´ı, kter´e nen´ı realizovateln´e (napˇr. uprostˇred vodn´ı plochy). Pˇrestoˇze ˇrada autor˚u (napˇr. [11, 12, 13]) vyvinula spojit´e modely se zahrnut´ım zak´azan´ych oblast´ı, tyto modely o to v´ıce nar´azˇ´ı na v´ypoˇcetn´ı pˇrek´azˇ ky. Na rozd´ıl od spojit´ych lokaˇcn´ıch model˚u, s´ıt’ov´e lokaˇcn´ı modely pˇredpokl´adaj´ı, zˇ e stˇrediska i poˇzadavky jsou um´ıstˇeny v uzlech nebo na hran´ach s´ıtˇe. Pokud uvaˇzujeme poˇzadavky pouze v uzlech, vznik´a zde ot´azka, zda-li i optim´aln´ı ˇreˇsen´ı u´ lohy leˇz´ı v uzlech, nebo je nutn´e uvaˇzovat i hrany s´ıtˇe. Hakimi [3] v roce 1964 jako prvn´ı uk´azal, zˇ e pro lokaˇcn´ı u´ lohu na obecn´e s´ıti um´ıstˇen´ı stˇredisek pouze do uzl˚u nedegraduje ˇreˇsen´ı1 . Pokud u´ lohu t´ımto zp˚usobem zjednoduˇs´ıme, pˇrin´asˇ´ı to pˇri ˇreˇsen´ı takovou v´yhodu, zˇ e se pouˇz´ıv´a ˇ sen´ı zjednoduˇsen´e u´ lohy podporuje i to, zˇ e i v pˇr´ıpadˇe u´ loh, u kter´ych se ˇreˇsen´ı degraduje. Reˇ v re´aln´ych u´ loh´ach je um´ıstˇen´ı stˇredisek obvykle omezeno na koneˇcnou mnoˇzinu m´ıst. ´ Ulohy, kter´e pˇredpokl´adaj´ı, zˇ e poˇzadavky i stˇrediska jsou um´ıstˇeny do diskr´etn´ıch bod˚u v prostoru, se naz´yvaj´ı diskr´etn´ı lokaˇcn´ı u´ lohy. Pro v´ypoˇcet vzd´alenost´ı mezi tˇemito stˇredisky a poˇzadavky se pouˇz´ıv´a zvolen´a vzd´alenostn´ı metrika (napˇr. nejjednoduˇssˇ´ı euklidovsk´a). Je zˇrejm´e, zˇ e mnoho model˚u a algoritm˚u vyvinut´ych pro s´ıt’ov´e u´ lohy lze pouˇz´ıt i pro diskr´etn´ı lokaˇcn´ı u´ lohy.
Statick´e a dynamick´e modely Vˇsechny klasick´e lokaˇcn´ı modely funguj´ı jako statick´e modely pˇredpokl´adaj´ıc´ı, zˇ e rozhodnut´ı prob´ıhaj´ı pouze v jednom okamˇziku a n´aklady, vzd´alenost a poˇzadavky se v cˇ ase nemˇen´ı. Ve skuteˇcnosti se vstupy model˚u v cˇ ase mˇen´ı a rozhodov´an´ı prob´ıh´a v delˇs´ım obdob´ı. Rozhodnut´ı v urˇcit´em okamˇziku omez´ı moˇznosti v budoucnu, napˇr. pˇri otevˇren´ı stˇrediska v urˇcit´em cˇ asov´em okamˇziku je nutn´e, aby toto stˇredisko z˚ustalo otevˇren´e po pl´anovan´e obdob´ı.
Deterministick´e a stochastick´e modely Klasick´e modely jsou nejen statick´e, ale tak´e deterministick´e, kter´e pˇredpokl´adaj´ı, zˇ e vˇsechny vstupy jsou zn´am´e a nejsou zde zˇ a´ dn´e n´ahodn´e procesy, kter´e by ovlivˇnovaly popt´avku 1
degradovan´e ˇreˇsen´ı - aˇckoli ne vˇsechna optim´aln´ı ˇreˇsen´ı u´ lohy jsou um´ıstˇena do vrchol˚u, Hakimi dok´azal, zˇ e
vˇzdy existuje ˇreˇsen´ı, kter´e minimalizuje u´ cˇ elovou funkci a leˇz´ı pouze v uzlech
25
a obsluhu z´akazn´ık˚u. Stochastick´e modely naopak uvaˇzuj´ı, zˇ e faktory jako je popt´avka, ale i um´ıstˇen´ı z´akazn´ık˚u nebo stˇredisek se v cˇ ase mohou mˇenit. Tyto modely obvykle pracuj´ı se zvolen´ym pravdˇepodobnostn´ım rozdˇelen´ım promˇenn´e veliˇciny.
Jedno a v´ıcekriteri´aln´ı modely Pˇrev´azˇ n´a cˇ a´ st model˚u pouˇz´ıv´a jedno krit´erium, v re´aln´ych probl´emech vˇsak vstupuje do rozhodov´an´ı v´ıce promˇenn´ych. Ty maj´ı cˇ asto rozd´ıln´e a nˇekdy i protich˚udn´e c´ıle. Konfliktn´ı krit´eria se zdaj´ı b´yt lokaˇcn´ım u´ loh´am vlastn´ı. Napˇr. pˇri um´ıstˇen´ı u´ loˇziˇstˇe odpadu chceme minimalizovat dopad tˇechto stˇredisek na obytn´e oblasti, a tedy maximalizovat jejich vzd´alenost od tˇechto obytn´ych oblast´ı, ale tak´e minimalizovat n´aklady na pˇrepravu odpadu. Protoˇze vˇetˇsina odpadu vznik´a v obytn´ych oblastech, dost´avaj´ı se tyto c´ıle do konfliktu.
2.3
´ Uloha okruˇzn´ıch j´ızd
´ Ulohu okruˇzn´ıch j´ızd m˚uzˇ eme popsat jako u´ lohu, ve kter´e je c´ılem urˇcit trasy vozidel, kdy kaˇzd´a trasa zaˇc´ın´a v depu, navˇst´ıv´ı podmnoˇzinu z´akazn´ık˚u ve specifick´e posloupnosti a vr´at´ı se zpˇet do depa. Kaˇzd´y z´akazn´ık mus´ı b´yt pˇriˇrazen k pr´avˇe jedn´e z tras a celkov´a velikost dod´avek z´akazn´ık˚u pˇriˇrazen´ych ke kaˇzd´emu vozidlu nesm´ı pˇrekroˇcit kapacitu vozidla. Volba tras by mˇela b´yt takov´a, aby celkov´e n´aklady na dod´an´ı byly minim´aln´ı [14]. M˚uzˇ eme ˇr´ıci, zˇ e u´ loha okruˇzn´ıch j´ızd je zobecnˇen´ım u´ lohy obchodn´ıho cestuj´ıc´ıho. Na rozd´ıl od u´ lohy obchodn´ıho cestuj´ıc´ıho m´a ˇradu dalˇs´ıch omezen´ı a rozˇs´ıˇren´ı, kter´a m˚uzˇ eme cˇ asto naj´ıt v re´aln´ych probl´emech. Zahrnuj´ı napˇr. n´asleduj´ıc´ı: - distribuce m˚uzˇ e prob´ıhat z v´ıce dep; - kaˇzd´e vozidlo m˚uzˇ e operovat na v´ıce neˇz jedn´e trase, pokud celkov´y cˇ as nepˇrekroˇc´ı stanovenou hodnotu; - kaˇzd´y z´akazn´ık mus´ı b´yt obslouˇzen v dan´em cˇ asov´em intervalu, kter´emu ˇr´ık´ame cˇ asov´e okno; - u´ loha m˚uzˇ e zahrnovat jak doruˇcov´an´ı tak odvoz od z´akazn´ık˚u;
26
- rozliˇsujeme u´ lohy s homogenn´ım a heterogenn´ım vozov´ym parkem, kdy je pouˇzit bud’ jeden, nebo v´ıce typ˚u vozidel; - vozidl˚um m˚uzˇ e b´yt pˇriˇrazeno cˇ asov´e rozpˇet´ı, kdy mohou pracovat, apod.
Matematick´a definice Obecnou verzi u´ lohy okruˇzn´ıch j´ızd (v angliˇctinˇe oznaˇcovan´e jako Capacitated Vehicle Routing Problem - CVRP) m˚uzˇ eme form´alnˇe popsat n´asledovnˇe [15]: je dan´e jedno centr´aln´ı depo 0, kter´e pouˇz´ıv´a k nez´avisl´ych vozidel s identickou kapacitou K, kter´a zajiˇst’uj´ı uspokojen´ı ˇ sen´ım u´ lohy okruˇzn´ıch j´ızd je rozklad mnoˇziny popt´avky di od n z´akazn´ık˚u, i = 1, ..., n. Reˇ n z´akazn´ık˚u do k tras R1 , ..., Rk , kter´y minimalizuje u´ cˇ elovou funkci celov´ych pˇrepravn´ıch n´aklad˚u a z´aroveˇn na zˇ a´ dn´e trase Rj nen´ı pˇrekroˇcena kapacita vozidla minFCV RP =
k X
P
vp ∈Rj
dp ≤ K:
C(Rj ).
j=1
N´aklady jedn´e trasy Rj = v0 , v1 , ..., vl+1 , kde v0 = vl+1 = 0, se spoˇc´ıtaj´ı nasledovnˇe: C(Rj ) =
l X
ci,i+1
i=0
kde cij oznaˇcuje pˇrepravn´ı n´aklady mezi z´akazn´ıky i a j pro i, j = 1, ..., n. Plat´ı cii = 0 pro ∀i = 1, ..., n a pro symetrickou u´ lohu nav´ıc plat´ı, zˇ e ∀i, j : cij = cji .
´ Varianty ulohy okruˇzn´ıch j´ızd D´ale si podrobnˇeji rozebereme nˇekter´e z variant, jmenovitˇe u´ lohu zahrnuj´ıc´ı sluˇzby doruˇcov´an´ı a odvozu, u´ lohu okruˇzn´ıch j´ızd s v´ıce stˇredisky, u´ lohu okruˇzn´ıch j´ızd s v´ıce komoditami, stochastickou u´ lohu okruˇzn´ıch j´ızd a probl´em rozvrhov´an´ı vozidel.
´ Uloha zahrnuj´ıc´ı sluˇzby doruˇcov´an´ı a odvozu ˇ Rada aplikac´ı zahrnuje sluˇzby doruˇcov´an´ı a odvozu mezi stˇredisky a ostatn´ımi lokacemi (sklady, obchody, stanicemi). Doruˇcen´ı se vztahuje k dopravˇe zboˇz´ı ze stˇrediska k z´akazn´ıkovi a odvoz opaˇcn´ym smˇerem do depa. V u´ loze m˚uzˇ e b´yt poˇzadov´ano, aby nejdˇr´ıve probˇehl rozvoz a aˇz pot´e odvoz, nebo je moˇzn´e spojit doruˇcov´an´ı a odvoz do jedn´e trasy. V literatuˇre je tento 27
probl´em zn´am´y jako ,,delivery and pick-up problem (DPD)”. C´ılem je nal´ezt mnoˇzinu tras, kter´ymi se zajist´ı doruˇcen´ı zboˇz´ı z´akazn´ık˚um a odvoz od z´akazn´ık˚u tak, zˇ e kapacita vozidel nen´ı pˇrekroˇcena a celkov´a ujet´a vzd´alenost je minim´aln´ı.
´ Uloha s v´ıce stˇredisky V pˇr´ıpadˇe v´ıce stˇredisek mohou tato stˇrediska b´yt autonomn´ı s vlastn´ım vozov´ym parkem a geografickou oblast´ı z´akazn´ık˚u, kterou obsluhuj´ı. V t´eto situaci se ˇreˇs´ı v´ıcekr´at jednoduch´a u´ loha okruˇzn´ıch j´ızd s jedn´ım stˇrediskem. V opaˇcn´em pˇr´ıpadˇe, kdy stˇrediska nejsou autonomn´ı, ale jejich operace jsou prov´azan´e a mezi sebou z´avisl´e, mluv´ıme o v´ıcen´asobn´e u´ loze okruˇzn´ıch j´ızd. Jednotliv´a vozidla mohou po obsluze z´akazn´ık˚u skonˇcit ve stejn´em, ale i v jin´em stˇredisku, neˇz ze kter´eho vyrazila.
´ V´ıcekomoditn´ı uloha okruˇzn´ıch j´ızd V u´ loze, kterou oznaˇcujeme jako v´ıcekomoditn´ı u´ lohu okruˇzn´ıch j´ızd, zajiˇst’uj´ı vozidla doruˇcen´ı r˚uzn´ych typ˚u zboˇz´ı a kaˇzd´y z´akazn´ık m˚uzˇ e poˇzadovat zvolen´e mnoˇzstv´ı od kaˇzd´e komodity.
´ Stochastick´a uloha okruˇzn´ıch j´ızd V pˇr´ıpadˇe probl´emu trasov´an´ı a doruˇcov´an´ı v podm´ınk´ach n´ahodn´e popt´avky hovoˇr´ıme ´ o stochastick´e u´ loze okruˇzn´ıch j´ızd. Uloha je obvykle formulov´ana s n´asleduj´ıc´ımi podm´ınkami: - popt´avka z´akazn´ık˚u je n´ahodn´a promˇenn´a se zn´am´ym rozdˇelen´ım pravdˇepodobnosti; - trasy mus´ı b´yt navrˇzen´y pˇred t´ım, neˇz je zn´ama skuteˇcn´a popt´avka; - c´ılem je minimalizovat pˇredpokl´adanou sumu ujet´ych vzd´alenost´ı.
´ Uloha rozvrhov´an´ı vozidel ´ Ulohu rozvrhov´an´ı vozidel lze povaˇzovat za u´ lohu okruˇzn´ıch j´ızd s dodateˇcn´ymi omezen´ımi dan´ymi cˇ asov´ymi intervaly, bˇehem nichˇz maj´ı probˇehnout r˚uzn´e cˇ innosti. Sloˇzitost tohoto typu u´ loh je d´ana nejˇcastˇeji tˇremi omezen´ımi: 28
- dobou po jakou je vozidlo v provozu pˇred t´ım, neˇz se mus´ı vr´atit do depa (napˇr. kv˚uli servisu nebo natankov´an´ı); - skuteˇcnost´ı, zˇ e nˇekter´e cˇ innosti mohou b´yt zabezpeˇceny pouze nˇekter´ymi typy vozidel; - pˇr´ıtomnost´ı jednoho nebo v´ıce dep.
´ Zahrnut´ı okruˇzn´ıch j´ızd do lokaˇcn´ıch uloh Vˇsechny klasick´e lokaˇcn´ı u´ lohy pˇredpokl´adaj´ı, zˇ e sluˇzba je doruˇcov´ana ze stˇrediska vozidlem jedouc´ım k jednomu z´akazn´ıkovi a pak zpˇet do stˇrediska, nebo naopak jednotliv´ı z´akazn´ıci cestuj´ı ke stˇredisku. Kriteri´aln´ı funkce se tedy spoˇc´ıt´a jako souˇcet vzd´alenost´ı ze stˇrediska k uzlu s poˇzadavky n´asobenou mnoˇzstv´ım poˇzadavk˚u dan´eho uzlu. Neuvaˇzuj´ı se cesty, pˇri kter´ych by se navˇst´ıvilo v´ıce z´akazn´ık˚u, pˇrestoˇze tento syst´em je v praxi velmi cˇ ast´y. Pˇr´ıtomnost obsluˇzn´ych cest s v´ıce z´akazn´ıky na trase m˚uzˇ e v lokaˇcn´ım modelu v´yznamnˇe sn´ızˇ it pˇrepravn´ı n´aklady, a t´ım i n´aslednˇe ovlivnit poˇcet a um´ıstˇen´ı stˇredisek. Webb [16] byl mezi prvn´ımi, kteˇr´ı pouk´azali na to, zˇ e modelov´an´ı distribuˇcn´ıch n´aklad˚u jako n´aklad˚u jednotliv´ych cest ze stˇrediska k z´akazn´ık˚um m˚uzˇ e v´yznamnˇe zkreslit skuteˇcn´e n´aklady. T´ım je n´aslednˇe ovlivnˇen i v´ybˇer um´ıstˇen´ı stˇredisek ve prospˇech pouze suboptim´aln´ı varianty ve srovn´an´ı se zahrnut´ım okruˇzn´ıch j´ızd. Perl a Daskin [17] formulovali integrovan´y probl´em line´arn´ıho programov´an´ı pro lokaˇcnˇetrasovac´ı u´ lohu pro um´ıstˇen´ı sklad˚u. Rozpoznali, zˇ e u´ loha zahrnuje tˇri z´akladn´ı propojen´a rozhodnut´ı: kam um´ıstit stˇrediska, jak pˇriˇradit z´akazn´ıky ke stˇredisk˚um a jak zvolit trasy vozidel obj´ızˇ dˇej´ıc´ı z´akazn´ıky. Probl´em vyˇreˇsili postupn´ym pouˇzit´ım tˇr´ı heuristik, kdy kaˇzd´a heuristika byla pouˇzita na dvojici ze tˇr´ı rozhodov´an´ı.
2.4
´ Metody rˇ eˇsen´ı uloh diskr´etn´ı optimalizace
V n´asleduj´ıc´ı kapitole si uk´azˇ eme algoritmy, kter´e byly vyvinuty pro ˇreˇsen´ı u´ loh diskr´etn´ı optimalizace. Vˇetˇsina pˇr´ıstup˚u nen´ı omezena jen na lokaˇcn´ı u´ lohy a u´ lohy optim´aln´ıho trasov´an´ı, obecn´e sch´ema lze pouˇz´ıt na velk´e mnoˇzstv´ı u´ loh. Bˇehem let byla vyvinuta ˇrada metod, kter´e mohou b´yt klasifikov´any do n´asleduj´ıc´ıch skupin:
29
- exaktn´ı pˇr´ıstupy; - klasick´e heuristiky; - metaheuristiky.
Exaktn´ı metody ´ Ulohy menˇs´ıho rozsahu je moˇzn´e ˇreˇsit exaktn´ımi pˇr´ıstupy, kter´e postupnˇe proch´azej´ı a vyhodnocuj´ı vˇsechna moˇzn´a ˇreˇsen´ı u´ lohy. Jedn´a se pˇredevˇs´ım o metody vˇetv´ı a hranic (branch and bound) a vˇetv´ı a ˇrez˚u (branch and cut).
Heuristiky Klasick´e heuristiky jsou metody, kter´e nezaruˇcuj´ı nalezen´ı optima, zaruˇcuj´ı ovˇsem zˇ e je ˇreˇsen´ı ,,dostateˇcnˇe dobr´e” a je nalezeno v rozumn´em cˇ ase. Heuristick´e metody funguj´ı na nˇekolika principech.
Hladov´e algoritmy Nejjednoduˇssˇ´ı algoritmus pro ˇreˇsen´ı mnoha lokaˇcn´ıch u´ loh je hladov´y algoritmus. S t´ımto pˇr´ıstupem najdeme nejlepˇs´ı um´ıstˇen´ı prvn´ıho stˇrediska vyhodnocen´ım zvolen´e u´ cˇ elov´e funkce. Pˇri umist’ov´an´ı druh´eho stˇrediska uvaˇzujeme pozici prvn´ıho stˇrediska jako danou a opˇet spoˇc´ıt´ame pro kaˇzd´e moˇzn´e um´ıstˇen´ı zvolenou funkci. Kaˇzd´e dalˇs´ı stˇredisko je umist’ov´ano identick´ym zp˚usobem. Stejnˇe jako je moˇzn´e stˇrediska hladov´ym algoritmem pˇrid´avat, je moˇzn´e je stejn´ym zp˚usobem i ub´ırat. Zaˇcneme um´ıstˇen´ım stˇrediska v kaˇzd´em uvaˇzovan´em m´ıstˇe. V kaˇzd´em kroku pak odebereme jedno stˇredisko a to vˇzdy takov´e, jehoˇz odebr´an´ı zp˚usob´ı nejniˇzsˇ´ı pˇr´ır˚ustek v´azˇ en´e sumy n´aklad˚u. Takto pokraˇcujeme dokud nezb´yv´a pr´avˇe P stˇredisek v ˇreˇsen´ı. Zat´ımco hladov´e algoritmy mohou generovat ˇreˇsen´ı relativnˇe rychle, v´ysledek cˇ asto nen´ı dostaˇcuj´ıc´ı. Byla proto vyvinuta ˇrada algoritm˚u, kter´e vych´azej´ı z hladov´ych algoritm˚u a n´ahodn´ymi nebo jin´ymi zp˚usoby se snaˇz´ı zlepˇsit z´ıskan´e ˇreˇsen´ı.
30
Lok´aln´ı hled´an´ı Dalˇs´ı skupina heuristick´ych algoritm˚u vyuˇz´ıv´a tzv. lok´aln´ıho hled´an´ı: zaˇc´ınaj´ı od nˇejak´eho st´avaj´ıc´ıho pˇr´ıpustn´eho ˇreˇsen´ı (zpravidla z´ıskan´e pouˇzit´ım jin´e heuristick´e metody) a postupnˇe ho mˇen´ı tak, zˇ e prozkoum´avaj´ı okol´ı st´avaj´ıc´ıho ˇreˇsen´ı. Pokud je nˇekter´a ze zmˇen lepˇs´ı neˇz st´avaj´ıc´ı ˇreˇsen´ı, prohl´as´ı se toto ˇreˇsen´ı za st´avaj´ıc´ı a d´ale se zkoum´a okol´ı nov´eho ˇreˇsen´ı. Tento postup se opakuje, dokud se daˇr´ı ˇreˇsen´ı zlepˇsovat nebo pokud nalezneme dostateˇcnˇe dobr´e ˇreˇsen´ı. Z algoritm˚u pro ˇreˇsen´ı lokaˇcn´ıch u´ loh m˚uzˇ eme do t´eto skupiny zaˇradit iterativn´ı algoritmus [18]. Z´akladn´ı myˇslenka je zamˇenit uzel v aktu´aln´ı mnoˇzinˇe vybran´ych um´ıstˇen´ı uzlem, kter´y v t´eto mnoˇzinˇe nen´ı. Pokud v´ymˇena zlepˇs´ı hodnotu u´ cˇ elov´e funkce, je pˇrijata jako nov´e aktu´aln´ı ˇreˇsen´ı, v opaˇcn´em pˇr´ıpadˇe se vr´at´ıme k p˚uvodn´ımu. Obecnˇe pokraˇcujeme, dokud je moˇzn´e naj´ıt z´amˇenu, kter´a zlepˇs´ı hodnotu u´ cˇ elov´e funkce.
Dalˇs´ı heuristiky Jin´ym principem v heuristick´ych metod´ach je pouˇzit´ı upraven´ych variant exaktn´ıch metod, v nichˇz se vyuˇz´ıv´a ne zcela pˇresn´ych a spolehliv´ych odhad˚u. T´ım se v´ypoˇcet v´yraznˇe urychl´ı, kv˚uli nepˇresn´emu odhadu ovˇsem nemus´ı b´yt nalezeno optimum.
Metaheuristiky Metaheuristiky jsou metody urˇcen´e pro ˇreˇsen´ı velmi obecn´ych tˇr´ıd u´ loh. M˚uzˇ eme je ch´apat jako obecn´y r´amec, kter´y m˚uzˇ e b´yt aplikov´an na ˇradu r˚uzn´ych optimalizaˇcn´ıch probl´em˚u s relativnˇe m´alo modifikacemi, kter´e jsou potˇreba k adaptaci algoritmu na specifick´y probl´em [19]. Na rozd´ıl od klasick´ych heuristik se metaheuristiky vyznaˇcuj´ı tak´e t´ım, zˇ e je moˇzn´e za urˇcit´ych podm´ınek opustit lok´aln´ı optimum, a to v pˇr´ıpadˇe, zˇ e v jin´e oblasti pˇr´ıpustn´ych ˇreˇsen´ı je nadˇeje na nalezen´ı ˇreˇsen´ı s lepˇs´ı hodnotou u´ cˇ elov´e funkce. K tomu obvykle vyuˇz´ıvaj´ı urˇcit´y kompromis mezi randomizac´ı a lok´aln´ım hled´an´ım. V literatuˇre se pojmy heuristika a metaheuristika cˇ asto zamˇenˇ uj´ı, v´yvoj ale smˇeˇruje k tomu, pouˇz´ıvat term´ın metaheuristiky pro metody, ve kter´ych je pouˇzit n´ahodn´y prvek. Aˇckoli jsou metaheuristiky sˇiroce pouˇz´ıvan´e techniky, st´ale jeˇstˇe nen´ı zcela pochopen´e, jak a proˇc funguj´ı.
31
Uvedeme si struˇcn´y pˇrehled metaheuristik nejˇcastˇeji pouˇz´ıvan´ych pro ˇreˇsen´ı u´ loh diskr´etn´ı optimalizace. Metody byly zpracov´any dle [20].
Simulovan´e zˇ´ıh´an´ı Simulovan´e zˇ´ıh´an´ı patˇr´ı do tˇr´ıdy lok´aln´ıch prohled´avac´ıch algoritm˚u zn´am´ych jako prahov´e algoritmy. Prahov´e algoritmy hraj´ı speci´aln´ı roli ze dvou d˚uvod˚u. Jednak jsou tyto algoritmy u´ spˇesˇn´e pˇri aplikaci na sˇirok´e spektrum praktick´ych u´ loh a nav´ıc maj´ı nˇekter´e prahov´e algoritmy, mezi kter´e patˇr´ı i simulovan´e ochlazov´an´ı, n´ahodnou komponentu, kter´a umoˇznˇ uje teoretickou anal´yzu jejich asymptotick´e konvergence. Pˇr´ıstup simulovan´eho zˇ´ıh´an´ı vych´az´ı z teoretick´e fyziky a metod Monte-Carlo, kter´e jsou zde vyuˇz´ıv´any pro simulaci jev˚u ve statistick´e termodynamice. Jejich pˇredch˚udcem je tzv. Metropolis filter. Simulaˇcn´ı metoda m˚uzˇ e b´yt ve fyzice motivov´ana n´asledovnˇe. Uvaˇzujme velk´e mnoˇzstv´ı cˇ a´ stic o konstantn´ım objemu pˇri urˇcit´e teplotˇe. Protoˇze se cˇ a´ stice pohybuj´ı, mohou se v d˚usedku vz´ajemn´ych sr´azˇ ek dostat do r˚uzn´ych energetick´ych stav˚u. Pravdˇepodobnost, zˇ e cˇ a´ stice je ve stavu o urˇcit´e energii E, je d´ana Maxwellov´ym-Boltzmannov´ym rozdˇelen´ım f (E) =
exp(−E/κB ϑ) , z(ϑ)
kde z(ϑ) je normalizaˇcn´ı faktor a κB je Bolzmannova konstanta. Rozdˇelen´ı
charakterizuje statistickou rovnov´ahu syst´emu pˇri teplotˇe ϑ.
Tabu prohled´av´an´ı Metoda tabu prohled´av´an´ı byla pˇredstavena Fredem Gloverem [21]. Zkuˇsenosti uk´azaly, zˇ e tabu prohled´av´an´ı je dobˇre funguj´ıc´ı aproximaˇcn´ı technika, kter´a m˚uzˇ e soutˇezˇ it s t´emˇeˇr kaˇzdou zn´amou metodou a kter´a je svou flexibilitou schopn´a porazit mnoho klasick´ych postup˚u. Tabu prohled´av´an´ı kombinuje deterministick´y iterativn´ı zlepˇsovac´ı algoritmus s moˇznost´ı pˇrijmout i ˇreˇsen´ı zvyˇsuj´ıc´ı n´aklady. T´ım je prohled´av´an´ı odvedeno od lok´aln´ıho minima a mohou b´yt prozkoum´any ostatn´ı cˇ a´ sti dan´eho prostoru. Dalˇs´ı navˇst´ıven´e ˇreˇsen´ı je vˇzdy vybr´ano jako pˇr´ıpustn´y soused souˇcasn´eho ˇreˇsen´ı s nejlepˇs´ımi n´aklady, a to i v pˇr´ıpadˇe zˇ e jsou tyto n´aklady horˇs´ı neˇz u souˇcasn´eho ˇreˇsen´ı. Mnoˇzina pˇr´ıpustn´ych soused˚u je omezena tabu seznamem navrˇzen´ym tak, aby zabr´anil cyklen´ı. Tabu seznam se dynamicky mˇen´ı bˇehem bˇehu algoritmu. Tabu seznam definuje ˇreˇsen´ı, kter´a
32
ˇ sen´ı z tabu seznamu m˚uzˇ e b´yt pˇrijato, pokud je nejsou pˇrijateln´a v pˇr´ısˇt´ıch nˇekolika iterac´ıch. Reˇ v urˇcit´em smyslu dostateˇcnˇe kvalitn´ı, a to v pˇr´ıpadˇe zˇ e dos´ahlo urˇcit´e poˇzadovan´e v´ysˇe n´aklad˚u.
Neuronov´e s´ıtˇe Pouˇzit´ı neuronov´ych s´ıt´ı k hled´an´ı ˇreˇsen´ı kombinatorick´ych optimalizaˇcn´ıch probl´em˚u se dost´av´a v posledn´ı dobˇe zv´ysˇen´e pozornosti. Neuronov´e s´ıtˇe se skl´adaj´ı ze s´ıtˇe [22], kterou tvoˇr´ı element´arn´ı uzly (neurony) navz´ajem propojen´e v´azˇ en´ymi spoji. Uzly pˇredstavuj´ı v´ypoˇcetn´ı jednotky schopn´e prov´adˇet jednoduch´e operace, kter´e tvoˇr´ı seˇcten´ı v´azˇ en´ych vstup˚u, n´asledovan´e pˇriˇcten´ım konstanty naz´yvan´e pr´ah a aplikac´ı neline´arn´ı funkce. V´ysledek v´ypoˇctu jednotky tvoˇr´ı v´ystup, kter´y je pouˇzit jako vstup pro uzly, kter´e maj´ı s t´ımto uzlem odpov´ıdaj´ıc´ı ´ orientovan´y spoj. Ukolem cel´e s´ıtˇe je dos´ahnout urˇcit´eho nastaven´ı, napˇr. poˇzadovan´eho vztahu mezi vstupem a v´ystupem. Tento proces je cˇ asto naz´yv´an tak´e samoorganizace. Prvn´ı pokus pouˇzit´ı neuronov´ych s´ıt´ı pro ˇreˇsen´ı u´ lohy obchodn´ıho cestuj´ıc´ıho byl zaloˇzen na Hopfieldov´ych neuronov´ych s´ıt´ıch [23]. Hopfieldovy s´ıtˇe mohou slouˇzit jako asociativn´ı pamˇeti pro ukl´ad´an´ı a z´ısk´av´an´ı informac´ı a k ˇreˇsen´ı kombinatorick´ych probl´em˚u. Patˇr´ı do tˇr´ıdy rekurentn´ıch neuronov´ych s´ıt´ı. Implementace zahrnuje dva z´akladn´ı kroky:
1. transformaci n´aklad˚u a omezen´ı probl´emu do jedn´e funkce, kterou oznaˇcujeme jako Hopfieldovu energetickou funkci; 2. urˇcen´ı Lagrangeov´ych parametr˚u. Tyto kroky jsou rozhoduj´ıc´ımi faktory u´ spˇechu aplikace. Jsou tak´e d˚uvodem proˇc je pˇrevod Hopfieldovy metody pˇri ˇreˇsen´ı u´ lohy obchodn´ıho cestuj´ıc´ıho velmi obt´ızˇ n´y. K mapov´an´ı u´ lohy obchodn´ıho cestuj´ıc´ıho do Hopfieldova r´amce je nutn´e sch´ema pro reprezentaci koncov´eho stavu s´ıtˇe ve formˇe seznamu tras. Hopfield a Tank [23] zvolili reprezentaˇcn´ı sch´ema, ve kter´em je posloupnost mˇest v seznamu tras k´odov´ana koncov´ymi stavy mnoˇziny neuron˚u. Pro u´ lohu s n mˇesty potˇrebujeme s´ıt’ s n2 neurony - jeden neuron pro kaˇzdou moˇznou pozici na trase pro kaˇzd´e mˇesto. Protoˇze m´ame n mˇest a kaˇzd´e m˚uzˇ e b´yt na n pozic´ıch, je potˇreba n × n neuron˚u.
33
Samoorganizuj´ıc´ı se mapy Samoorganizuj´ıc´ı se mapy jsou pˇr´ıkladem tzv. soutˇezˇ iv´ych neuronov´ych s´ıt’ov´ych model˚u [24, 25]. Samoorganizace prob´ıh´a postupn´ymi zmˇenami vah na spoj´ıch neuron˚u.
Mravenˇc´ı kolonie Metoda mravenˇc´ıch koloni´ı byla pˇredstavena Dorigem [26] a poprv´e pouˇzita na u´ loze obchodn´ıho cestuj´ıc´ıho. Pozorov´an´ı skuteˇcn´ych mravenc˚u hledaj´ıc´ıch potravu bylo inspirac´ı k napodoben´ı chov´an´ı mravenˇc´ıch koloni´ı. Skuteˇcn´ı mravenci jsou schopni si mezi sebou pˇred´avat informace t´ykaj´ıc´ı se zdroj˚u potravy pouˇzit´ım pachov´ych esenc´ı - feromon˚u. Vyluˇcov´an´ım feromon˚u si znaˇc´ı cestu v z´avislosti na jej´ı d´elce a kvalitˇe nalezen´eho zdroje potravy. Ostatn´ı mravenci jsou tak schopni nal´ezt feromonovou stopu a n´asledovat ji. Popsan´e chov´an´ı mravenˇc´ıch koloni´ı m˚uzˇ e b´yt pouˇzito pro ˇreˇsen´ı kombinatorick´ych optimalizaˇcn´ıch u´ loh, kde umˇel´e mravenˇc´ı kolonie simuluj´ı skuteˇcn´e mravence pˇri jejich prohled´av´an´ı prostˇred´ı. Hodnoty u´ cˇ elov´e funkce odpov´ıdaj´ı kvalitˇe potravn´ıch zdroj˚u a adaptivn´ı pamˇet’ odpov´ıd´a feromonov´ym stop´am, nav´ıc jsou umˇel´e kolonie vybaveny lok´aln´ı heuristickou funkc´ı, kter´a zajiˇst’uje, zˇ e hled´an´ı prob´ıh´a pouze na mnoˇzinˇe pˇr´ıpustn´ych ˇreˇsen´ı.
Evoluˇcn´ı algoritmy Analogie mezi pˇrirozen´ym v´ybˇerem a uˇcen´ım se (nebo tak´e optimalizac´ı) vedla k rozvoji tzv. ,,evoluˇcn´ıch algoritm˚u”, jejichˇz hlavn´ım c´ılem je simulovat evoluˇcn´ı proces na poˇc´ıtaˇci. Pouˇzit´ı evoluˇcn´ıch algoritm˚u se stalo v posledn´ı dobˇe velmi popul´arn´ı a rozˇs´ıˇrilo se prakticky do vˇsech mysliteln´ych obor˚u. Pro mnoho re´aln´ych probl´emu jsou evoluˇcn´ı techniky robustnˇejˇs´ı a efektivnˇejˇs´ı neˇz metody zaloˇzen´e na form´aln´ı logice nebo matematick´em programov´an´ı a se sloˇzit´ymi u´ lohami jsou schopny se vypoˇra´ dat l´epe neˇz tradiˇcn´ı optimalizaˇcn´ı metody. ˇ s´ı oblast, pro kterou se dnes pouˇz´ıv´a oznaˇcen´ı evoluˇcn´ı algoritmy, zahrnuje t´emata evoluˇcn´ı Sirˇ strategie, evoluˇcn´ıho programov´an´ı, umˇel´e inteligence, klasifikaˇcn´ıch syst´em˚u, genetick´eho programov´an´ı a nejnovˇeji i uˇc´ıc´ı se hardware. Vˇsechny evoluˇcn´ı algoritmy maj´ı dva hlavn´ı znaky, kter´e je odliˇsuj´ı od ostatn´ıch algoritm˚u. Za prv´e jsou zaloˇzen´e na populac´ıch a za druh´e mezi cˇ leny populace prob´ıh´a komunikace
34
a v´ymˇena informac´ı. Tato komunikace a v´ymˇena informace vznik´a jako v´ysledek selekce a rekombinace v evoluˇcn´ıch algoritmech. Obecn´y r´amec evoluˇcn´ıch algoritm˚u lze shrnout do n´asleduj´ıc´ıch krok˚u [27]: 1. nastav i = 1 2. n´ahodnˇe generuj poˇca´ teˇcn´ı populaci P (i) 3. opakuj dokud populace nezkonverguje k poˇzadovan´e hodnotˇe nebo nen´ı dosaˇzen zadan´y cˇ as (poˇcet cykl˚u): - vyhodnot’ fitness funkci pro kaˇzd´eho cˇ lena populace P (i) - vyber rodiˇce z populace na z´akladˇe hodnoty fitness funkce - pouˇzij oper´ator selekce na rodiˇce a vytvoˇr novou generaci P (i + 1) Konkr´etn´ı algoritmy, kter´e vych´azej´ı z tohoto obecn´eho sch´ematu, se pak liˇs´ı zp˚usobem, jak´y pouˇz´ıvaj´ı pro reprezentaci cˇ len˚u populace, a sch´ematem, kter´ym implementuj´ı fitness funkci, oper´ator selekce a rekombinace. Evoluˇcn´ı strategie Pro evoluˇcn´ı strategie plat´ı, zˇ e reprezentace prvk˚u je velmi podobn´a pˇrirozen´e reprezentaci u´ lohy a nezd˚urazˇnuje se genetick´a reprezentace. V pˇr´ıpadˇe numerick´ych optimalizaˇcn´ıch u´ loh mohou b´yt prvky reprezentov´any napˇr´ıklad vektorem re´aln´ych cˇ´ısel sp´ısˇe neˇz bin´arn´ım ˇretˇezcem. Evoluˇcn´ı strategie obvykle pouˇz´ıvaj´ı deterministick´e sch´ema selekce, Gaussovu mutaci a diskr´etn´ı rekombinaci. Jen zˇr´ıdka se v kontextu evoluˇcn´ıch strategi´ı setk´av´ame s pojmem kˇr´ızˇ en´ı, protoˇze simulace evoluce neprob´ıh´a na u´ rovni gen˚u. Evoluˇcn´ı programov´an´ı V pˇr´ıpadˇe pouˇzit´ı pro numerickou optimalizaci jsou mezi evoluˇcn´ımi strategiemi a evoluˇcn´ım programov´an´ım jen mal´e rozd´ıly. Stejnˇe jako u evoluˇcn´ı strategie je u evoluˇcn´ıho programov´an´ı pouˇzita Gaussova mutace a k reprezentaci vektor re´aln´ych cˇ´ısel. Nejv´yznamnˇejˇs´ı rozd´ıl se t´yk´a rekombinace a selekce, evoluˇcn´ı programov´an´ı rekombinaci a selekci nepouˇz´ıv´a a nam´ısto nich je jako mechanismus selekce zvoleno pravdˇepodobnostn´ı soutˇezˇ en´ı.
35
Genetick´e algoritmy Genetick´e algoritmy (GA) se od evoluˇcn´ıch strategi´ı a evoluˇcn´ıho programov´an´ı liˇs´ı pˇredevˇs´ım ve zp˚usobu reprezentace cˇ len˚u populace a oper´atorem rekombinace. Genetick´e algoritmy zd˚urazˇnuj´ı genetick´e k´odov´an´ı potenci´aln´ıch ˇreˇsen´ı do chromozom˚u a aplikaci genetick´ych oper´ator˚u na tyto chromozomy. Genetick´a reprezentace m´a na u´ spˇech algoritmu z´asadn´ı v´yznam. Dobˇre zvolen´a reprezentace ˇreˇsen´ı probl´emu v´yraznˇe usnadn´ı, sˇpatn´a reprezentace bude m´ıt vliv opaˇcn´y. Genetick´e algoritmy budou podrobnˇe rozebr´any v dalˇs´ı kapitole.
36
K APITOLA 3 Genetick´e algoritmy
N´ahodn´e optimalizaˇcn´ı algoritmy si rychle z´ıskaly popularitu po t´e, co se uk´azaly nedostatky klasick´ych analytick´ych a enumerativn´ıch metod. Analytick´e metody, kter´e vyuˇz´ıvaj´ı znalost´ı matematick´e anal´yzy, jsou omezeny pˇredevˇs´ım existenc´ı derivace a spojitost´ı funkce a cˇ asto u nich dojde k uv´ıznut´ı v lok´aln´ım extr´emu. Enumerativn´ı metody jsou naproti tomu velmi jednoduch´e. Funguj´ı tak, zˇ e postupnˇe proch´azej´ı vˇsechna moˇzn´a ˇreˇsen´ı, jejich cˇ asov´a sloˇzitost je ovˇsem velmi vysok´a. Aˇckoli lze pˇredpokl´adat, zˇ e n´ahodn´e hled´an´ı pˇrinese pˇri delˇs´ım bˇehu lepˇs´ı v´ysledky neˇz enumerativn´ı metody, efektivita jednoduch´ych n´ahodn´ych metod jako je n´ahodn´a proch´azka nebo n´ahodn´a sch´emata, kter´a hledaj´ı a ukl´adaj´ı pouze nejlepˇs´ı ˇreˇsen´ı, je st´ale velmi n´ızk´a. Je ovˇsem d˚uleˇzit´e rozliˇsit striktnˇe n´ahodn´e metody od randomizovan´ych technik. Genetick´e algoritmy jsou pˇr´ıkladem procedury, kter´a vyuˇz´ıv´a n´ahodn´y v´ybˇer pouze jako prostˇredek ke smˇerov´an´ı v ˇr´ızen´em procesu hled´an´ı. U randomizovan´ych metod tedy nemus´ı platit, zˇ e hled´an´ı prob´ıh´a zcela bezc´ılnˇe. Pˇri zkoum´an´ı d˚uvod˚u funkˇcnosti a robustnosti genetick´ych algoritm˚u, je zˇrejm´e, zˇ e se mus´ı od tradiˇcn´ıch optimalizaˇcn´ıch metod liˇsit v z´asadn´ıch vlastnostech. Tyto rozd´ıly lze shrnout do cˇ tyˇr bod˚u [27]:
37
1. Geneteck´e algoritmy pracuj´ı s k´odov´an´ım parametr˚u mnoˇziny, ne s parametry samotn´ymi. Vyˇzaduj´ı pˇrirozenou mnoˇzinu parametr˚u optimalizovan´eho probl´emu, kter´a je k´odov´ana do ˇretˇezce koneˇcn´e d´elky nad koneˇcnou abecedou. 2. Genetick´e algoritmy pracuj´ı s populac´ı bod˚u, ne s jedn´ım bodem. V mnoha optimalizaˇcn´ıch metod´ach se pohybujeme z jednoho bodu v rozhodovac´ım prostoru k dalˇs´ımu pomoc´ı pˇrechodov´ych pravidel, coˇz cˇ asto vede k uv´ıznut´ı v lok´aln´ım optimu. Genetick´e algoritmy oproti tomu pracuj´ı s celou mnoˇzinou bod˚u souˇcasnˇe. Paralelnˇe nal´ezaj´ı r˚uzn´a lok´aln´ı optima a v´yraznˇe t´ım sniˇzuj´ı sˇanci ukonˇcen´ı algoritmu ve sˇpatn´em bodˇe. 3. Genetick´e algoritmy vyuˇz´ıvaj´ı informace z u´ cˇ elov´e funkce, ne odvozen´e nebo jin´e pˇridruˇzen´e znalosti, napˇr´ıklad v´ypoˇcty derivac´ı apod. 4. Genetick´e
algoritmy
pouˇz´ıvaj´ı
pravdˇepodobnostn´ı
pˇrechodov´a
pravidla,
ne
deterministick´a pravidla. N´ahodn´a volba zde slouˇz´ı jako prostˇredek k pˇrechodu do oblast´ı s pravdˇepodobn´ym zlepˇsen´ım.
3.1
Terminologie
Terminologie uveden´a v n´asleduj´ıc´ı kapitole vych´az´ı z [28, 29]. Genetick´e algoritmy pouˇz´ıvaj´ı terminologii pˇrevzatou z genetiky. Kaˇzd´y jedinec v populaci m´a v genetick´ych algoritmech stejnˇe jako v pˇr´ırodˇe geny. Tyto geny tvoˇr´ı ˇretˇezec oznaˇcovan´y jako chromozom, v nˇemˇz jsou geny uspoˇra´ d´any do line´arn´ı posloupnosti. Kaˇzd´y gen v pˇr´ırodˇe zajiˇst’uje dˇediˇcn´y pˇrenos jednoho nebo nˇekolika znak˚u. Geny urˇcit´ych znak˚u jsou um´ıstˇeny na dan´ych m´ıstech v ˇretˇezci. Jak´ykoli znak jedince (napˇr. barva vlas˚u) se projevuje urˇcit´ym zp˚usobem - ˇr´ık´ame zˇ e gen m´a nˇekolik stav˚u, kter´e oznaˇcujeme jako alely. Sadu parametr˚u chromozomu naz´yv´ame genotyp. Kaˇzd´y genotyp by tedy pˇredstavoval potenci´aln´ı ˇreˇsen´ı dan´eho probl´emu. Celkov´a dˇediˇcn´a informace organismu tvoˇr´ı genom, kter´y se skl´ad´a z nˇekolika chromozom˚u, u cˇ lovˇeka napˇr. z 23 p´ar˚u chromozom˚u. V genetick´ych algoritmech jsou ˇreˇsen´ı obvykle tvoˇrena pouze jedn´ım chromozomem a term´ıny genom a chromozom maj´ı t´ım p´adem stejn´y v´yznam. Evoluˇcn´ı proces pracuj´ıc´ı s populac´ı genom˚u pak odpov´ıd´a prohled´av´an´ı prostoru potenci´aln´ıch ˇreˇsen´ı.
38
Fitness funkce V literatuˇre se d´ale pouˇz´ıvaj´ı term´ıny u´ cˇ elov´a funkce (cost function) a fitness funkce (fitness function, cˇ esky oznaˇcovan´a tak´e jako vhodnost). Fitness funkce cˇ´ıselnˇe vyjadˇruje kvalitu kaˇzd´eho jedince a je transformovanou hodnotou u´ cˇ elov´e funkce. Obvykle se pouˇz´ıv´a maximalizaˇcn´ı funkce, pˇr´ıpadnˇe s normalizac´ı do zvolen´eho intervalu. Fitness funkce d´ale slouˇz´ı pro v´ybˇer rodiˇcu˚ , kteˇr´ı se pouˇzij´ı pro dalˇs´ı v´yvoj populace. Podle Darwinovy teorie pˇreˇz´ıvaj´ı jen ti nejlepˇs´ı, proto by i v genetick´ych algoritmech mˇeli b´yt upˇrednostnˇeni jedinci s vyˇssˇ´ı hodnotou fitness funkce. Na druhou stranu, pokud by byli vyb´ır´ani vˇzdy jen nejlepˇs´ı jedinci, brzy by mohlo doj´ıt k uv´ıznut´ı na mrtv´em bodˇe a je tedy vhodn´e zahrnout s menˇs´ı pravdˇepodobnost´ı i horˇs´ı jedince, kteˇr´ı mohou pˇrin´est vhodn´e geny.
K´odov´an´ı Pro k´odov´an´ı chromozom˚u se pouˇz´ıv´a nejˇcastˇeji bin´arn´ı k´odov´an´ı, tj. posloupnost nul a jedniˇcek. Dle typu u´ lohy lze pro reprezentaci pouˇz´ıt i cel´a cˇ´ısla, re´aln´a cˇ´ısla, matice, vektory nebo kˇrivky. Existuj´ı i dalˇs´ı typy k´odov´an´ı, napˇr. pro u´ lohu obchodn´ıho cestuj´ıc´ıho nebo u´ lohu okruˇzn´ıch j´ızd je vhodn´e k´odov´an´ı oznaˇcovan´e jako permutaˇcn´ı, kdy je kaˇzd´emu vrcholu, kter´y m´a b´yt obslouˇzen, pˇriˇrazeno specifick´e cˇ´ıslo a posloupnost cˇ´ısel v chromoz´omu pak ud´av´a trasu.
3.2
Princip genetick´eho algoritmu
Genetick´e algoritmy pouˇz´ıvaj´ı tˇri z´akladn´ı oper´atory, kter´e si d´ale pop´ısˇeme. Jedn´a se o: - selekci, - kˇr´ızˇ en´ı, - mutaci. V´ysledkem aplikace tˇechto oper´ator˚u na st´avaj´ıc´ı generaci je vytvoˇren´ı nov´e generace.
39
Selekce Pro v´ybˇer jedinc˚u v dan´e populaci, kteˇr´ı se stanou rodiˇci, slouˇz´ı ˇrada metod. Nejˇcastˇeji se jedn´a o v´ybˇer pomoc´ı v´azˇ en´e rulety, poˇradovou selekci a turnajovou selekci. Pro ohodnocen´ı kvality jedinc˚u se pouˇz´ıv´a fitness funkce, jedinci s vyˇssˇ´ı hodnotu fitness funkce tak maj´ı vyˇssˇ´ı pravdˇepodobnost, zˇ e budou vybr´ani.
V´ybˇer pomoc´ı v´azˇ en´e rulety Metoda selekce pomoc´ı v´azˇ en´e rulety pouˇz´ıv´a pomyslnou ruletu, jej´ızˇ obvod je rozdˇelen do r˚uznˇe velk´ych oblast´ı. Kaˇzd´y jedinec dostane takov´y pod´ıl, kter´y odpov´ıd´a hodnotˇe jeho fitness funkce.
Obr´azek 3.1: V´ybˇer pomoc´ı v´azˇ en´e rulety. Kaˇzd´emu jedinci je pˇriˇrazen pod´ıl, kter´y odopov´ıd´a hodnotˇe jeho fitness funkce. V pˇr´ıpadˇe maximalizaˇcn´ıho krit´eria je c´ılem vyb´ırat cˇ astˇeji jedince s vyˇssˇ´ı hodnotou fitness funkce, kter´ym je na pomysln´e ruletˇe pˇriˇrazena vˇetˇs´ı v´yseˇc. V pˇr´ıpadˇe minimalizaˇcn´ıho krit´eria je nutn´e pouˇzit´ı transformace, kter´a menˇs´ım hodnot´am fitness pˇriˇrad´ı vˇetˇs´ı pod´ıl na ruletˇe. Zdroj: Autor
Algoritmus lze zapsat do n´asleduj´ıc´ıch krok˚u [29]: 1. spoˇcti sumu vˇsech u´ cˇ elov´ych hodnot v populaci a oznaˇc ji S; 2. vygeneruj n´ahodn´e cˇ´ıslo r z intervalu (0,S); 3. projdi populac´ı a pro kaˇzd´eho jedince spoˇc´ıtej sumu u´ cˇ elov´ych hodnot od hodnoty nula. Jakmile tato suma pˇrekroˇc´ı r, je vybr´an posledn´ı jedinec do reprodukˇcn´ıho pole. Na stejn´em principu jako v´ybˇer pomoc´ı v´azˇ en´e rulety funguje tak´e v´ybˇer na jednotkov´e u´ seˇcce, kdy nejsou hodnoty zobrazeny na kruhu, ale na pomysln´e u´ seˇcce. 40
Poˇradov´a selekce V´ybˇer pomoc´ı v´azˇ en´e rulety nen´ı vhodn´y v pˇr´ıpadˇe, zˇ e hodnoty fitness funkce nejsou transformov´any do intervalu (0,1) s rovnomˇern´ym rozdˇelen´ım. U poˇradov´e selekce se pouˇz´ıv´a jin´y syst´em pˇrerozdˇelen´ı - nejmenˇs´ı hodnota dostane hodnotu 1, n´asleduj´ıc´ı hodnotu 2 atd. T´ım se zmenˇs´ı rozd´ıly mezi jedinci a ti z´ıskaj´ı podobnou sˇanci, zˇ e budou vybr´ani. D´ale metoda funguje stejnˇe jako v´ybˇer pomoc´ı v´azˇ en´e rulety.
Turnajov´a selekce V t´eto metodˇe se vˇzdy n´ahodnˇe vybere skupina jedinc˚u (minim´alnˇe dvou, ale m˚uzˇ e jich b´yt i v´ıce) a z nich se zvol´ı nejlepˇs´ı na z´akladnˇe hodnoty fitness funkce. Ten se st´av´a v´ıtˇezem turnaje.
Elitismus Elitismus nen´ı selekˇcn´ı metodou. Je to mechanismus, kter´y zajiˇst’uje, zˇ e pˇri pˇrechodu do nov´e generace nepˇrijdeme o nejlepˇs´ı existuj´ıc´ı chromoz´om. Nejlepˇs´ı jedinec je tedy pˇr´ımo vybr´an ze st´avaj´ıc´ı generace a zkop´ırov´an do nov´e. Teprve pot´e se pouˇzije jin´a selekˇcn´ı metoda na v´ybˇer rodiˇcu˚ .
Kˇr´ızˇ en´ı Mezi vˇsemi evoluˇcn´ımi metodami pouˇz´ıvaj´ı genetick´e algoritmy rekombinaˇcn´ı oper´atory, kter´e se nejv´ıce bl´ızˇ´ı pˇr´ırodn´ımu modelu. Rekombinace dvou chromoz´om˚u, tzv. kˇr´ızˇ en´ı, spoˇc´ıv´a ve v´ymˇenˇe cˇ a´ st´ı genotyp˚u. V pˇr´ıpadˇe jednobodov´eho kˇr´ızˇ en´ı (single-point crossover - SPX) jsou oba rodiˇcovsk´e chromoz´omy pˇreruˇseny v n´ahodnˇe urˇcen´em bodˇe. N´aslednˇe je nov´y genotyp potomka vytvoˇren spojen´ım prvn´ı cˇ a´ sti chromoz´omu prvn´ıho rodiˇce a druh´e cˇ a´ sti druh´eho rodiˇce (Obr. 3.2a). Ve dvoubodov´em kˇr´ızˇ en´ı (two-point crossover - TPX) jsou oba rodiˇcovsk´e chromoz´omy rozdˇeleny ve dvou bodech a potomek je vytvoˇren z krajn´ıch cˇ a´ st´ı prvn´ıho rodiˇce a prostˇredn´ı cˇ a´ sti druh´eho rodiˇce (Obr. 3.2b). Obecnou formou operace kˇr´ızˇ en´ı je v´ıcebodov´e kˇr´ızˇ en´ı (multi-
41
Obr´azek 3.2: Z´akladn´ı typy kˇr´ızˇ en´ı. Dvˇe rodiˇcovsk´a ˇreˇsen´ı, kter´a proch´az´ı procesem kˇr´ızˇ en´ı, jsou tvoˇrena chromozomy o deseti genech. Kaˇzd´y gen m˚uzˇ e nab´yvat dvou hodnot - b´ıl´e a sˇed´e. V pˇr´ıpadˇe (a) dojde k pˇreruˇsen´ı rodiˇcovsk´ych ˇreˇsen´ı v jednom m´ıstˇe, jedn´a se o jednobodov´e kˇr´ızˇ en´ı, analogicky (b) dvoubodov´e kˇr´ızˇ en´ı a (c) v´ıcebodov´e kˇr´ızˇ en´ı. Zdroj: Autor
point crossover - MPX) (Obr. 3.2c). Pro chromoz´omy pevn´ych d´elek jsou zvolen´e body kˇr´ızˇ en´ı pro oba rodiˇce vˇzdy identick´e.
Mutace V´yznam mutace spoˇc´ıv´a v zachov´an´ı diverzity jedinc˚u t´ım, zˇ e do nich pˇrin´asˇ´ı mal´e n´ahodn´e zmˇeny. V pˇr´ıpadˇe chromozom˚u pevn´e d´elky lze mutaci prov´est n´ahodnou zmˇenou hodnoty (alely) genu. Podobnˇe jako pˇri kˇr´ızˇ en´ı je obecnˇejˇs´ı variantou mutace zmˇena v´ıce gen˚u nar´az, a to bud’ u soused´ıc´ı skupiny (dvoubodov´a mutace), nebo zcela nez´avisl´ych n´ahodn´ych gen˚u (n-bodov´a mutace). Pokud pouˇzijeme pro reprezentaci chromoz´om˚u bin´arn´ı k´odov´an´ı, provedeme mutaci jednoduˇse pˇrepnut´ım hodnot (z 0 na 1 a obr´acenˇe). V pˇr´ıpadˇe, zˇ e pracujeme s re´aln´ymi cˇ´ısly, vych´az´ı se u mutace obvykle z norm´aln´ıho pravdˇepodobnostn´ıho rozdˇelen´ı. Alternativou k mutaci m˚uzˇ e b´yt permutace, kdy si dva geny v chromozomu vymˇen´ı m´ısta. To m´a samozˇrejmˇe smysl jen pˇr´ıpadˇe stejn´ych datov´ych typ˚u jednotliv´ych gen˚u. Permutace m˚uzˇ e b´yt uˇziteˇcn´a u u´ loh, kter´e maj´ı za u´ kol stanovit poˇrad´ı prvk˚u, jako je tomu napˇr´ıklad u u´ lohy obchodn´ıho cestuj´ıc´ıho nebo optim´aln´ıho trasov´an´ı.
42
Obr´azek 3.3: Z´akladn´ı typy mutace. Vybran´y jedinec, kter´y je tvoˇren chromozomem s deseti geny, proch´az´ı procesem mutace. Kaˇzd´y gen m˚uzˇ e nab´yvat dvou hodnot - b´ıl´e a sˇed´e. V pˇr´ıpadˇe (a) dojde n´ahodn´e zmˇenˇe v jednom genu, jedn´a se o jednobodovou mutaci, analogicky (b) dvoubodov´a mutace a (c) n-bodov´a mutace. Zdroj: Autor
Parametry kˇr´ızˇ en´ı a mutace Ke kˇr´ızˇ en´ı a mutaci doch´az´ı s urˇcitou pˇredem zvolenou pravdˇepodobnost´ı. Pokud je pravdˇepodobnost kˇr´ızˇ en´ı nulov´a, k zˇ a´ dn´emu kˇr´ızˇ en´ı nedoch´az´ı a vˇsichni potomci vzniknou jako pˇresn´e kopie rodiˇcu˚ vybran´ych bˇehem selekce. Naopak pokud pravdˇepodobnost kˇr´ızˇ en´ı zvol´ıme 100%, budou vˇsichni potomci vytvoˇreni kˇr´ızˇ en´ım. Podobnˇe jako v pˇr´ıpadˇe kˇr´ızˇ en´ı je to i u mutace, rozd´ıln´e jsou vˇsak hodnoty pravdˇepodobnosti, kter´e se pouˇz´ıvaj´ı. Doporuˇcen´a pravdˇepodobnost kˇr´ızˇ en´ı je podle [30] 80 - 95% a pro mutaci 0,5 - 1%.
3.3
´ V´ıcekriteri´aln´ı ulohy
K oblastem, kde doch´az´ı u evoluˇcn´ıch algoritm˚u k nejrychlejˇs´ımu rozvoji, patˇr´ı pˇredevˇs´ım v´ıcekriteri´aln´ı u´ lohy, kter´e na rozd´ıl od jednokriteri´aln´ıch obsahuj´ı v´ıce, cˇ asto protich˚udn´ych c´ıl˚u, kter´e vyˇzaduj´ı optimalizaci. V pˇr´ıpadˇe v´ıcekriteri´aln´ıch u´ loh obvykle neexistuje jedno optim´aln´ı ˇreˇsen´ı, a je proto nutn´e vybrat ˇreˇsen´ı s urˇcit´ymi kompromisy, kter´e by mˇelo na pˇrijateln´e u´ rovni splˇnovat vˇsechny poˇzadovan´e c´ıle. V mnoha odvˇetv´ıch re´aln´eho svˇeta lze nal´ezt probl´emy, kter´e vedou k ˇreˇsen´ı sloˇzit´ych v´ıcekriteri´aln´ıch u´ loh, a byla pro nˇe vyvinuta ˇrada technik v r´amci informatiky, vˇed na podporu
43
rozhodov´an´ı a operaˇcn´ıho v´yzkumu. N´apad vyuˇz´ıt potenci´al evoluˇcn´ıch algoritm˚u pro ˇreˇsen´ı v´ıcekriteri´aln´ıch u´ loh se objevuje jiˇz v sˇedes´at´ych letech, ale k prvn´ı implementaci doˇslo aˇz v letech osmdes´at´ych. Evoluˇcn´ı algoritmy obecnˇe byly aˇz do poloviny osmdes´at´ych let ˇreˇseny pˇredevˇs´ım na teoretick´e u´ rovni, coˇz souvis´ı s rozvojem a rozˇs´ıˇren´ım poˇc´ıtaˇcov´e techniky. Od t´e doby doˇslo v t´eto oblasti, kter´a je dnes oznaˇcovan´a jako evoluˇcn´ı v´ıcekriteri´aln´ı optimalizace (evolutionary multiobjective optimization - EMOO), k rozs´ahl´emu v´yvoji. Hlavn´ı motivace pro pouˇzit´ı evoluˇcn´ıch algoritm˚u pro ˇreˇsen´ı u´ loh v´ıcekriteri´aln´ı optimalizace spoˇc´ıv´a v tom, zˇ e evoluˇcn´ı algoritmy jsou schopn´e souˇcasnˇe vytv´aˇret mnoˇzinu ˇreˇsen´ı (tzv. populaci), coˇz umoˇzn´ı nal´ezt prvky Paretovsky optim´aln´ı mnoˇziny1 v jednom bˇehu algoritmu na rozd´ıl od tradiˇcn´ıch matematick´ych metod, kter´e potˇrebuj´ı k dosaˇzen´ı stejn´eho v´ysledku spuˇstˇen´ı ˇrady oddˇelen´ych bˇeh˚u. ˇ Rada probl´em˚u v oblasti dopravy se snaˇz´ı nal´ezt ˇreˇsen´ı, kter´e m´a b´yt optim´aln´ı z hlediska cˇ asov´e n´aroˇcnosti, bezpeˇcnosti, d˚usledk˚u pro zˇ ivotn´ı prostˇred´ı, extern´ıch a intern´ıch n´aklad˚u apod. V takov´ych pˇr´ıpadech mohou genetick´e algoritmy nach´azet svoje uplatnˇen´ı.
1
Paretova mnoˇzina oznaˇcuje mnoˇzinu bod˚u takov´ych, zˇ e pro zˇ a´ dn´y z nich neexistuje bod, kter´y by mu
dominoval. Vztah dominance je definov´an tak, zˇ e pro kaˇzdou sloˇzku vektor˚u u, v plat´ı, zˇ e hodnota v podle it´eho krit´eria je vˇetˇs´ı nebo rovn´a hodnotˇe u podle i-t´eho krit´eria a z´aroveˇn existuje alespoˇn jedno i, pro kter´e je ˇ ık´ame, zˇ e v dominuje u (v pˇr´ıpadˇe minimalizaˇcn´ı u´ lohy). hodnota u ostˇre vˇetˇs´ı neˇz v. R´
44
K APITOLA 4 Clarke-Wrightova metoda
Pro porovn´an´ı chov´an´ı a v´ysledk˚u jednotliv´ych metod vyuˇzijeme stejn´y pˇr´ıklad jako v m´e bakal´aˇrsk´e pr´aci [31], kter´a se zab´yvala optimalizac´ı distribuce n´ahradn´ıch d´ıl˚u ve spoleˇcnosti ˇ Gefco. Gefco zajiˇst’uje v Cesk´ e republice z´asobov´an´ı autorizovan´ych servis˚u znaˇcek Peugeot a Citr¨oen. Z´asobov´an´ı prob´ıh´a ze dvou dep um´ıstˇen´ych v bl´ızkosti Prahy a Brna, ze kter´ych ˇ e republice celkem 97. Jejich jsou d´ıly rozv´azˇ eny do jednotliv´ych autoservis˚u, kter´ych je v Cesk´ pˇrehled je uveden v pˇr´ıloze v Tabulce cˇ . A.1 Bakal´aˇrsk´a pr´ace se zab´yvala pouze servisy, jejichˇz z´asobov´an´ı prob´ıh´a z praˇzsk´eho depa a hledala trasy vozidel tak, aby n´aklady na distribuci byly minim´aln´ı pˇri souˇcasn´em splnˇen´ı cˇ asov´ych omezen´ı a limit˚u dan´ych kapacitou vozidel. K ˇreˇsen´ı probl´emu byla pouˇzita nejzn´amˇejˇs´ı heuristick´a metoda pro u´ lohu okruˇzn´ıch j´ızd - Clarke-Wrightova metoda (CW). Aˇckoli je zaloˇzena na velmi jednoduch´e myˇslence, poskytuje obvykle relativnˇe dobr´e ˇreˇsen´ı, tedy takov´e, kter´e se jen m´alo odliˇsuje od optima.
4.1
Princip Clarke-Wrightovy metody
Algoritmus funguje na principu u´ spor n´aklad˚u z´ıskan´ych spojen´ım dvou tras do jedn´e tak, jak je ilustrov´ano na Obr´azku cˇ . 4.1, kde bod 0 pˇredstavuje depo.
45
Obr´azek 4.1: Sch´ema v´ypoˇctu u´ spor u Clarke-Wrightovy metody Zdroj: Autor
Na zaˇca´ tku jsou z´akazn´ıci i a j jsou obslouˇzeni na r˚uzn´ych tras´ach (Obr. 4.1a). Alternativnˇe lze tyto dva z´akazn´ıky navˇst´ıvit na stejn´e trase, napˇr´ıklad v poˇrad´ı i − j, jak je uk´az´ano na Obr´azku 4.1b. Vzd´alenosti (respektive pˇrepravn´ı n´aklady), kter´e minimalizujeme jsou zn´am´e, a je tedy moˇzn´e spoˇc´ıtat u´ sporu spojen´e trasy (4.1b) oproti dvˇema tras´am (4.1a). Pˇrepravn´ı n´aklady pro dvˇe samostan´e trasy (Obr. 4.1a) lze vyj´adˇrit jako: Da = c0i + ci0 + c0j + cj0 , a pro trasu vzniklou spojen´ım i a j (Obr. 4.1b): Db = c0i + cij + cj0 Odeˇcten´ım obou rovnic z´ısk´ame u´ sporu Sij Sij = ci0 + c0j − cij Vysok´a hodnota Sij indikuje, zˇ e je v´yhodn´e navˇst´ıvit body i a j na stejn´e trase a to tak, aby byly v poˇrad´ı hned za sebou. V prvn´ım kroku algoritmu jsou spoˇcteny u´ spory pro kaˇzdou dvojici z´akazn´ık˚u a u´ spory se pot´e setˇr´ıd´ı od nejvˇetˇs´ıch hodnot k nejmenˇs´ım. N´aslednˇe se vybere nejvyˇssˇ´ı hodnota u´ spor, kter´a je na prvn´ım m´ıstˇe v seznamu, a testuje se, zda lze odpov´ıdaj´ıc´ı dvojici bod˚u spojit do jedn´e trasy. Trasy lze spojit do jedn´e, pokud jsou body i a j koncov´e body dvou tras a z´aroveˇn jsou splnˇeny podm´ınky pˇr´ıpustnosti (d´elka trasy, kapacita vozidel apod.). Takto projdeme vˇsechny hodnoty u´ spor v setˇr´ıdˇen´em seznamu. V pˇr´ıpadˇe, zˇ e nˇekter´y bod nebyl pˇriˇrazen do zˇ a´ dn´e trasy, je nutn´e ho navˇst´ıvit na samostatn´e trase.
46
4.2
V´ysledky
Probl´em nyn´ı rozˇs´ıˇr´ıme o druh´e depo, vyuˇzijeme jiˇz z´ıskan´e v´ysledky pomoc´ı ClarkeWrightovy metody a stejnou metodu pouˇzijeme i pro n´avrh tras z brnˇensk´eho depa. Tyto hodnoty n´am budou slouˇzit pro z´akladn´ı porovn´an´ı u´ spˇesˇnosti navrhovan´ych metaheuristick´ych algoritm˚u. Program byl spuˇstˇen pro jednu kombinaci pouˇzit´ych vstupn´ıch hodnot z praˇzsk´eho depa a tut´ezˇ kombinaci z brnˇensk´eho depa. Hodnoty omezen´ı vych´azely z p˚uvodn´ıho ˇreˇsen´ı distribuce, poˇzadavk˚u na cˇ asy dod´an´ı a kapacity vozidel. Byly zvoleny 400 km jako maxim´aln´ı ujet´a vzd´alenost na jedn´e trase a 8 bod˚u jako maxim´aln´ı poˇcet navˇst´ıven´ych servis˚u na jedn´e trase. Maxim´aln´ı poˇcet servis˚u na trase odpov´ıd´a omezen´e kapacitˇe vozidla. Pˇri zn´am´ych hodnot´ach hmotnosti a poˇctu rozv´azˇ en´ych kus˚u by bylo samozˇrejmˇe moˇzn´e zohlednit jako omezuj´ıc´ı podm´ıku maxim´aln´ı hmotnost n´akladu. Ta se ovˇsem mˇen´ı kaˇzd´y den, zat´ımco optimalizace tras se pˇredpokl´ad´a jako jednor´azov´a pro delˇs´ı obdob´ı, a proto jsou hmotnosti nahrazeny maxim´aln´ım poˇctem servis˚u, kter´y odpov´ıd´a pr˚umˇern´ym objem˚um rozv´azˇ en´ych n´ahradn´ıch d´ıl˚u. Nalezen´e trasy jsou uvedeny v n´asleduj´ıc´ım souhrnu. Pro vˇetˇs´ı pˇrehlednost jsou pouˇzita pouze cˇ´ısla autoservis˚u, kter´a odpov´ıdaj´ı ID (poˇradov´emu cˇ´ıslu) v Tabulce A.1, nula odpov´ıd´a v obou pˇr´ıpadech - pro Prahu i Brno - depu. Pˇri dan´ych omezen´ıch 400 km a 8 bod˚u na trase vyˇslo celkem 8 rozvozov´ych tras z praˇzsk´eho (jaˇzlovick´eho) depa a 5 tras z brnˇensk´eho. Celkov´a minim´aln´ı nalezen´a d´elka vˇsech tras z obou dep je 1578 + 2492 km, dohromady tedy 4070 km. Nalezen´e trasy jsou zn´azornˇeny na mapˇe ˇ Cesk´ e republiky na Obr. 4.2.
Depo Praha trasa 1: 0 → 20 → 22 → 21 → 23 → 24 → 53 → 52 → 50 → 0 D´elka trasy: 367,5 km trasa 2: 0 → 59 → 61 → 60 → 62 → 63 → 64 → 45 → 44 → 0 D´elka trasy: 327,9 km
47
trasa 3: 0 → 10 → 11 → 12 → 2 → 4 → 57 → 3 → 1 → 0 D´elka trasy: 75,4 trasa 4: 0 → 15 → 16 → 17 → 18 → 19 → 6 → 7 → 5 → 0 D´elka trasy: 390,1 km trasa 5: 0 → 13 → 14 → 58 → 41 → 40 → 25 → 26 → 27 → 0 D´elka trasy: 258,8 km trasa 6: 0 → 51 → 56 → 54 → 55 → 49 → 48 → 47 → 46 → 0 D´elka trasy: 366,3 km trasa 7: 0 → 9 → 36 → 35 → 31 → 32 → 29 → 30 → 28 → 0 D´elka trasy: 359,9 km trasa 8: 0 → 34 → 37 → 38 → 39 → 43 → 42 → 33 → 8 → 0 D´elka trasy: 346,2 km Celkov´a d´elka: 2492,1 km
Obr´azek 4.2: Trasy z´ıskan´e pomoc´ı Clarke-Wrightovy metody Zdroj: Autor
48
Depo Brno trasa 1: 0 → 73 → 76 → 74 → 67 → 66 → 82 → 79 → 0 d´elka trasy: 399,1 km trasa 2: 0 → 86 → 88 → 87 → 89 → 90 → 70 → 78 → 0 d´elka trasy: 234,9 km trasa 3: 0 → 91 → 80 → 84 → 77 → 0 d´elka trasy: 256,1 km trasa 4: 0 → 92 → 93 → 94 → 95 → 96 → 97 → 85 → 0 d´elka trasy: 297,1 km trasa 5: 0 → 69 → 68 → 65 → 75 → 71 → 72 → 81 → 83 → 0 d´elka trasy: 390,4 km Celkov´a d´elka: 1577,60 km
49
K APITOLA 5 Aplikace genetickych ´ algoritmu˚ na ulohu ´ okruˇzn´ıch j´ızd
Pro stejn´a data z pˇredchoz´ı kapitoly se zachov´an´ım um´ıstˇen´ı dep nyn´ı pouˇzijeme genetick´y algoritmus. Konkr´etn´ı sch´ema implementovan´eho genetick´eho algoritmu vych´az´ı z [15]. Nejz´asadnˇejˇs´ı ot´azkou je v pˇr´ıpadˇe genetick´ych algoritm˚u pouˇzit´ych pro u´ lohu okruˇzn´ıch j´ızd zp˚usob reprezentace jednotliv´ych ˇreˇsen´ı a d´ale zajiˇstˇen´ı toho, zˇ e se nevytv´aˇr´ı ˇreˇsen´ı s duplicitn´ımi hodnotami pˇri kˇr´ızˇ en´ı a mutaci.
5.1
N´avrh genetick´eho algoritmu
Reprezentace Reprezentace genom˚u byla zvolena tak, aby co nejv´ıce pˇripom´ınala pˇrirozenou reprezentaci u´ lohy. Kaˇzd´y genom (jedinec) je tvoˇren mnoˇzinou seznam˚u jednotliv´ych bod˚u, kdy body jsou v seznamu v takov´em poˇrad´ı v jak´em jsou navˇst´ıveny na dan´e trase. K reprezentaci jsou pouˇzita pˇrirozen´a cˇ´ısla, kter´a odpov´ıdaj´ı cˇ´ıseln´emu identifik´atoru ID z Tabulky A.1. Pˇr´ıklad reprezentace jednoho genomu, kter´y je tvoˇren trasami s celkem deseti navˇst´ıven´ymi vrcholy je uveden na Obr. 5.1.
50
Obr´azek 5.1: Pˇr´ıklad reprezentace jednoho genomu s deseti navˇst´ıven´ymi vrcholy Zdroj: Autor
Pˇri poˇca´ teˇcn´ı inicializaci jsou jedinci tvoˇreni n´ahodnˇe, z´aroveˇn ale pˇri inicializaci i v kaˇzd´em kroku algoritmu prob´ıh´a kontrola, zda jsou splnˇeny vˇsechny omezuj´ıc´ı podm´ınky. Pokud je na nˇekter´e trase jedince pˇrekroˇcena maxim´aln´ı d´elka nebo poˇcet vrchol˚u, rozdˇel´ı se dan´a trasa do nˇekolika nov´ych, kter´e jiˇz dan´a omezen´ı splˇnuj´ı.
Fitness funkce Volba fitness funkce vypl´yv´a ze zad´an´ı u´ lohy, kdy je c´ılem minimalizovat celkovou ujetou vzd´alenost. Proto hodnotu fitness funkce vol´ıme jako prost´y celkov´y souˇcet d´elek jednotliv´ych tras a krit´erium je pouˇzito jako minimalizaˇcn´ı.
Selekce Jako metoda selekce je pouˇzita turnajov´a selekce, kter´a je pops´ana v cˇ a´ sti 3.2, s parametrem 3, tj. v kaˇzd´em kroku jsou n´ahodnˇe vybr´ani tˇri jedinci a z nich je na z´akladˇe hodnoty fitness funkce vybr´an nejlepˇs´ı, kter´y d´ale vstupuje jako rodiˇc do procesu kˇr´ızˇ en´ı.
Kˇr´ızˇ en´ı Jak jiˇz bylo zm´ınˇeno v´ysˇe, v u´ loze okruˇzn´ıch j´ızd nen´ı moˇzn´e pouˇz´ıt klasick´e metody kˇr´ızˇ en´ı s jedn´ım nebo nˇekolika body, ve kter´ych se pˇreruˇs´ı rodiˇcovsk´a ˇreˇsen´ı a jejich jednotliv´e cˇ a´ sti se pot´e pospojuj´ı dohromady. U takov´eho zp˚usobu kˇr´ızˇ en´ı by doch´azelo ke vzniku duplicit, a t´ım nepˇr´ıpustn´ych ˇreˇsen´ı. Nam´ısto toho je z jednoho rodiˇcovsk´eho ˇreˇsen´ı n´ahodnˇe vybr´ana cˇ a´ st
51
trasy a ta je vloˇzena do druh´eho rodiˇcovsk´eho ˇreˇsen´ı, ze kter´eho jsou pot´e vymaz´any vˇsechny hodnoty z vkl´adan´eho u´ seku tak, aby byl kaˇzd´y bod v ˇreˇsen´ı opˇet pr´avˇe jednou. Pˇr´ıklad fungov´an´ı takov´eho kˇr´ızˇ en´ı je zobrazen na Obr. 5.2.
Obr´azek 5.2: Pˇr´ıklad kˇr´ızˇ en´ı Zdroj: Autor
M´ısto, kam vkl´ad´ame zvolen´y u´ sek, m˚uzˇ e b´yt vybr´ano n´ahodnˇe. Jinou moˇznost´ı, kter´a je pops´ana v cˇ l´anku [15], je nal´ezt bod v rodiˇcovsk´em ˇreˇsen´ı, kter´y je nejbl´ızˇ e prvn´ımu bodu vkl´adan´eho u´ seku (a z´aroveˇn se tento bod nevyskytuje ve vkl´adan´em u´ seku), a vloˇzit u´ sek pˇr´ımo za nˇej. Pˇri testov´an´ı byly pouˇzity obˇe varianty, jejichˇz v´ysledky budou pops´any d´ale. Z´aroveˇn byla testov´ana varianta, kdy se n´ahodnˇe stˇr´ıdaj´ı obˇe moˇznosti. Pravdˇepodobnost pˇriˇrazen´a obˇema zp˚usob˚um kˇr´ızˇ en´ı byla zvolena shodn´a, tj. 0,5. Metoda, pˇri kter´e se vkl´ad´a k nejbliˇzsˇ´ımu bodu, zajist´ı rychlejˇs´ı konvergenci ˇreˇsen´ı, mohla by ovˇsem zp˚usobit, zˇ e by se velk´a mnoˇzina prostoru moˇzn´ych ˇreˇsen´ı v˚ubec nenavˇst´ıvila.
Mutace Stejnˇe jako v pˇr´ıpadˇe kˇr´ızˇ en´ı i zp˚usob prov´adˇen´ı mutace je nutn´e pˇrizp˚usobit charakteru u´ lohy. Zvolen´a mutace prob´ıh´a z´amˇenou dvou bod˚u v ˇreˇsen´ı, kter´e jsou oba vybr´any n´ahodnˇe. Jinou moˇznost´ı, kterou by bylo moˇzn´e v tomto pˇr´ıpadˇe pouˇz´ıt, je zvolit bod a vloˇzit ho do jin´eho m´ısta ˇreˇsen´ı.
52
Elitismus Byly otestov´any varianty s pouˇzit´ım i vynech´an´ım elitismu. V pˇr´ıpadˇe zahrnut´ı elitismu je do dalˇs´ı generace pˇresouv´an jeden jedinec s nejlepˇs´ı hodnotou fitness funkce.
Parametry kˇr´ızˇ en´ı a mutace Kˇr´ızˇ en´ı a mutace neprob´ıhaj´ı vˇzdy, ale s pˇredem stanovenou pravdˇepodobnost´ı. Nejprve se pomoc´ı selekce vyberou dva rodiˇce, vygeneruje se n´ahodn´e cˇ´ıslo z intervalu (0,1) a pokud je toto cˇ´ıslo menˇs´ı neˇz pravdˇepodobnost kˇr´ızˇ en´ı, vstupuj´ı rodiˇce do procesu kˇr´ızˇ en´ı. Pokud n´ahodn´e cˇ´ıslo pˇrevyˇsuje stanovenou hodnotu pravdˇepodobnosti, pˇresuneme prvn´ıho rodiˇce pˇr´ımo do dalˇs´ı generace a druh´eho jiˇz d´ale neuvaˇzujeme. Analogicky prob´ıh´a mutace, ke kter´e doch´az´ı pouze, pokud je vygenerovan´e cˇ´ıslo menˇs´ı neˇz zvolen´a hodnota pravdˇepodobnosti mutace. Na z´akladˇe doporuˇcen´ych hodnot pravdˇepodobnosti kˇr´ızˇ en´ı a mutace [30] byl program spuˇstˇen pro vˇsechny moˇzn´e kombinace n´asleduj´ıc´ıch hodnot parametr˚u: - pravdˇepodobnost kˇr´ızˇ en´ı: 0,70; 0,80; 0,85; 0,90; 0,95; - pravdˇepodobnost mutace: 0,05; 0,10; 0,15.
Implementace Pro implementaci algoritmu bylo zvoleno prostˇred´ı Matlab. Matlab umoˇznˇ uje velmi jednoduchou pr´aci s poli, kter´e jsou implicitn´ı datovou strukturou, nen´ı potˇreba pˇredem alokovat pamˇet’ ani ji posl´eze uvolˇnovat. Vzhledem k rozd´ıln´e d´elce jednotliv´ych ˇretˇezc˚u jsou pro ukl´ad´an´ı jednotliv´ych ˇreˇsen´ı pouˇzita tzv. bunˇecˇ n´a pole (CellArray), kdy je moˇzn´e do kaˇzd´e buˇnky pole vloˇzit jin´y datov´y typ (v naˇsem pˇr´ıpadˇe se do jednotliv´ych bunˇek vkl´adaj´ı vektory cˇ´ısel r˚uzn´ych d´elek). Klasick´e v´ıcerozmˇern´e pole s pevnˇe dan´ymi rozmˇery by na rozd´ıl od bunˇecˇ n´e struktury mˇelo v´yraznˇe vyˇssˇ´ı pamˇet’ov´e n´aroky, kdy by velk´a cˇ a´ st pole z˚ust´avala pr´azdn´a.
53
Na druh´e stranˇe je v´ypoˇcet pomalejˇs´ı neˇz pˇri pouˇzit´ı jin´ych programovac´ıch jazyk˚u, pˇri bˇehu algoritmu s vytv´aˇren´ım des´ıtek tis´ıc populac´ı se tyto rozd´ıly jiˇz v´yraznˇe projevuj´ı. Pˇri poˇzadavku na z´ısk´an´ı ˇreˇsen´ı v kratˇs´ım cˇ ase by bylo vhodn´e zvolit napˇr. programovac´ı jazyk C.
5.2
V´ysledky
Praˇzsk´e depo Stejnˇe jako pˇri ˇreˇsen´ı u´ lohy Clarke-Wrightovou metodou jsou zvoleny omezuj´ıc´ı podm´ınky 8 bod˚u na trase a d´elka trasy omezen´a na 400 km. Pro toto zad´an´ı pak bylo testov´ano chov´an´ı genetick´eho algoritmu s r˚uzn´ym nastaven´ım jednotliv´ych parametr˚u: - typem kˇr´ızˇ en´ı, - pravdˇepodobnost´ı kˇr´ızˇ en´ı, - pravdˇepodobnost´ı mutace, - velikost´ı populace, - pouˇzit´ı elitismu. Poˇcet iterac´ı omez´ıme na 20 000, kdy se minim´aln´ı nalezen´a hodnota fitness funkce mˇen´ı jiˇz minim´alnˇe. Jednotliv´e varianty a vliv nastaven´ı parametr˚u nejprve porovn´ame na cˇ a´ sti u´ lohy, kter´a zahrnuje servisy pˇr´ısluˇsej´ıc´ı praˇzsk´emu depu. Nejl´epe funguj´ıc´ı variantu pak vyuˇzijeme d´ale pro n´avrh tras z brnˇensk´eho depa a tak´e pro n´avrh tras po zmˇenˇe um´ıstˇen´ı dep.
54
Varianta 1 - kˇr´ızˇ en´ı s n´ahodn´ym vkl´ad´an´ım bez elitismu Prvn´ı testovanou variantou je genetick´y algoritmus, kter´y pouˇz´ıv´a zp˚usob kˇr´ızˇ en´ı, kdy jsou u´ seky mezi rodiˇci pˇresouv´any na n´ahodn´e pozice. Minim´aln´ı nalezen´e hodnoty fitness funkce pro vˇsechny kombinace pravdˇepodobnosti kˇr´ızˇ en´ı, pravdˇepodobnosti mutace a velikosti populace jsou shrnuty v Tabulce 5.1 a z´aroveˇn jsou zde data z tabulky zobrazena pro pˇrehlednost do graf˚u. Pokud srovn´ame z´ıskan´e hodnoty s v´ysledky Clarke-Wrightovy metody (2492,1 km), je zˇrejm´e, zˇ e v´ysledky genetick´eho algoritmu u t´eto varianty jsou velmi vzd´alen´e od optima (kter´e mus´ı b´yt nutnˇe menˇs´ı nebo rovno v´ysledk˚um Clarke-Wrighta). I v nejlepˇs´ım pˇr´ıpadˇe, kdy je celkov´a ujet´a vzd´alenost 2847,9 km, se jedn´a o rozd´ıl v´ıce neˇz 14 procent oproti Clarke-Wrightovi. Z graf˚u u Tabulky 5.1 je tak´e patrn´a v´yznamn´a z´avislost v´ysledk˚u na nastaven´ı jednotliv´ych parametr˚u. Jen mal´y vliv m´a pravdˇepodobnost mutace, naopak pˇri zmˇenˇe pravdˇepodobnosti kˇr´ızˇ en´ı se projevuj´ı vˇetˇs´ı rozd´ıly. Oproti oˇcek´av´an´ı byly z´ısk´any lepˇs´ı v´ysledky pˇri niˇzsˇ´ıch pravdˇepodobnostech kˇr´ızˇ en´ı (0,7), pˇrestoˇze se jedn´a o niˇzsˇ´ı hodnoty, neˇz kter´e jsou obecnˇe doporuˇcov´any (dle [30] kolem 0,9). Je pravdˇepodobn´e, zˇ e i mal´e zmˇeny, kter´e vznikaj´ı pˇri kˇr´ızˇ en´ı nebo mutaci, mohou v´yraznˇe ovlivnit d´elku tras a zp˚usobit ztr´atu dobr´ych ˇreˇsen´ı. Proto n´ızk´e hodnoty pravdˇepodobnosti kˇr´ızˇ en´ı, kdy jsou jiˇz z´ıskan´a dobr´a ˇreˇsen´ı pˇrenesena do dalˇs´ı generace, zajist´ı nalezen´ı lepˇs´ı v´ysledn´e hodnoty fitness funkce. Z tohoto d˚uvodu otestujeme ve variant´ach 4,5 a 6 zahrnut´ı elitismu. Z´avislost je vidˇet i pˇri zmˇenˇe velikosti populace, kdy jsou z´ıskan´e v´ysledky lepˇs´ı s vˇetˇs´ı velikost´ı populace, coˇz odpov´ıd´a tomu, zˇ e je vytvoˇreno a otestov´ano vˇetˇs´ı mnoˇzstv´ı moˇzn´ych ˇreˇsen´ı. Pr˚ubˇeh jednoho konkr´etn´ıho spuˇstˇen´ı algoritmu zachycuje graf na Obr. 5.3. Je zde vidˇet, zˇ e po poˇca´ teˇcn´ıch nˇekolika stech kroc´ıch jiˇz nedoch´az´ı k t´emˇeˇr zˇ a´ dn´e konvergenci maxim´aln´ı, minim´aln´ı a pr˚umˇern´e fitness hodnoty. Naopak pr˚umˇern´a a minim´aln´ı hodnota fitness funkce se v jednotliv´ych populac´ıch cˇ asto v´yraznˇe vzd´al´ı od jiˇz nalezen´eho absolutn´ıho minima. Na grafu na Obr. 5.3b je pro stejn´e hodnoty parametr˚u zachycen pr˚ubˇeh prvn´ıch dvˇe stˇe krok˚u bˇehu algoritmu.
55
0,10
0,15
0,70
3412,2
3469,6
3791,7
0,80
3823,9
3791,6
3968,5
0,85
3972,7
3914,7
4139,1
0,90
4032,2
4119,9
4193,6
0,95
4211,9
4398,5
4332,4
0,10
0,15
0,70
3099,0
3366,1
3430,6
0,80
3561,9
3696,5
3873,8
0,85
3638,8
3869,4
3690,2
0,90
3819,2
3885,7
3750,1
0,95
3955,3
4029
4141,9
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
kˇr´ızˇ en´ı
0,10
0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
4000
0,10 0,15
3500
3000 0, 7
0,05
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Pravdˇepodobnost mutace 0,05
0,10
0,15
0,70
2847,9
2971,5
2967,1
0,80
3243,7
3195,3
3516,9
0,85
3548,2
3421
3691,9
0,90
3657,8
3751,6
3724,6
0,95
3733,1
3807,4
3590,5
60
0,05
0,15
Pravdˇepodobnost mutace 0,05
30
4000
3500
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,05
20
Pravdˇepodobnost
Pravdˇepodobnost mutace
Fitness [km]
Velikost populace
3500 0,15
0,05
0,10
3000 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.1: Minim´aln´ı hodnoty fitness funkce pro variantu 1. V grafech jsou zobrazeny nalezen´e hodnoty fitness funkce v z´avislosti na hodnotˇe pravdˇepodobnosti kˇr´ızˇ en´ı. Tabulky a jim odpov´ıdaj´ıc´ı grafy jsou zobrazeny zvl´asˇt’ pro velikost populace 20, 30 a 60 jedinc˚u. Pravdˇepodobnost mutace je konstantn´ı pro kaˇzdou zobrazenou kˇrivku a jej´ı hodnota je zobrazena u dan´e kˇrivky. Zdroj: Autor
56
Fitness [km]
6000
5000
min, max avg
4000
3000
min abs
5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104
Fitness [km]
9000 8000 min, max 7000
avg
6000
min abs
5000 4000
0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.3: Pr˚ubˇeh algoritmu - varianta 1. Graf zn´azorˇnuje chov´an´ı jednoho bˇehu algoritmu s poˇca´ teˇcn´ımi hodnotami 30 cˇ len˚u v populaci, pravdˇepodobnost´ı mutace 0,1 a pravdˇepodobnost´ı kˇr´ızˇ en´ı 0,8. Na grafu (a) je vˇzdy po 100 iterac´ıch zobrazena maxim´aln´ı hodnota fitness funkce v populaci (max), pr˚umˇern´a hodnota fitness v populaci (avg), minim´aln´ı hodnota fitness v populaci (min) a minim´aln´ı celkov´a hodnota fitness nalezen´a od zaˇca´ tku bˇehu algoritmu (min abs). Na grafu (b) jsou tyt´ezˇ hodnoty fitness funkce zobrazeny pro prvn´ıch dvˇe stˇe iterac´ı. Zdroj: Autor
57
Varianta 2 - kˇr´ızˇ en´ı s vkl´ad´an´ım k nejbliˇzsˇ´ımu bodu bez elitismu Druh´a testovan´a varianta pouˇz´ıv´a kˇr´ızˇ en´ı, ve kter´em je n´ahodnˇe vybr´an u´ sek rodiˇce 1 a vloˇzen na m´ısto v rodiˇci 2 za takov´y bod, kter´y je nejbl´ızˇ e prvn´ımu bodu pˇresouvan´eho u´ seku. Minim´aln´ı nalezen´e hodnoty fitness funkce jsou shrnuty v Tabulce 5.2.
0,10
0,15
0,70
2769,4
2728,6
2693,8
0,80
2763,0
2641,0
2745,7
0,85
2755,3
2754,3
2718,1
0,90
2865,8
2746,5
2800,6
0,95
2783,5
2674,7
2782,3
0,10
0,15
0,70
2634,5
2660,1
2573,8
0,80
2677,3
2693,7
2723,3
0,85
2796,8
2794,3
2555,7
0,90
2711,8
2795,1
2583,2
0,95
2653,3
2702,0
2517,9
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
kˇr´ızˇ en´ı
Pravdˇepodobnost
0,15
2700
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2800 2700
0,05
0,10 0,15
2600 2500 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Pravdˇepodobnost mutace 0,05
60
0,05
2600 0, 7
Pravdˇepodobnost mutace 0,05
30
2800
0,10
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,05
20
2900
Pravdˇepodobnost mutace
0,10
2800
0,15
0,70
2831,9
2715,1
2621,8
0,80
2771,2
2763,4
2774,5
0,85
2780,8
2732,4
2629,6
0,90
2603,1
2641,8
2737,7
0,95
2736,5
2762,6
2602,4
Fitness [km]
Velikost populace
0,05
0,10 2700 0,15 2600 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.2: Minim´aln´ı hodnoty fitness funkce pro variantu 2 - Popis viz Tabulka 5.1 Zdroj: Autor
Zmˇena typu kˇr´ızˇ en´ı v´yraznˇe ovlivnila v´ysledky a nalezen´a minim´aln´ı hodnota fitness funkce se pro r˚uzn´e hodnoty parametr˚u pohybuje mezi 2517,9 a 2865,8. V´ysledn´e hodnoty nevykazuj´ı v´yraznou z´avislost na nastaven´ı parametr˚u a je tedy moˇzn´e z´ıskat relativnˇe dobr´e ˇreˇsen´ı pro 58
jak´ekoli poˇca´ teˇcn´ı nastaven´ı pravdˇepodobnost´ı a velikosti populace. Pˇri srovn´an´ı s ClarkeWrightem se jiˇz nejlepˇs´ı nalezen´a hodnota o tolik neliˇs´ı, ale st´ale se nepodaˇrilo naj´ıt ˇreˇsen´ı s kratˇs´ı d´elkou tras. Rozd´ıl je v tomto pˇr´ıpadˇe pˇribliˇznˇe 1%. Na Obr. 5.4 je pak vidˇet chov´an´ı algoritmu v cˇ ase. Na rozd´ıl od n´ahodn´eho kˇr´ızˇ en´ı se zde minimum populace a absolutn´ı minimum t´emˇeˇr shoduj´ı a i pr˚umˇern´a hodnota fitness populace m´a jen mal´e v´ychylky. Z´aroveˇn doch´az´ı k rychl´e konvergenci na poˇca´ tku bˇehu algoritmu (Obr. 5.4b) a po pˇeti tis´ıc´ıch kroc´ıch se nalezen´e ˇreˇsen´ı jiˇz prakticky nemˇen´ı (Obr. 5.4a).
Fitness [km]
4000
min, max avg 3000
min abs
5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104 9000 Fitness [km]
8000 7000
min, max
6000
avg
5000
min abs
4000 3000
0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.4: Pr˚ubˇeh algoritmu - varianta 2. Hodnoty paramter˚u a popis graf˚u viz Obr. 5.3 Zdroj: Autor
59
Varianta 3 - stˇr´ıd´an´ı obou metod kˇr´ızˇ en´ı bez elitismu Ve tˇret´ı variantˇe je zkombinov´an zp˚usob kˇr´ızˇ en´ı pouˇzit´y ve variantˇe 1 a 2. Metoda kˇr´ızˇ en´ı je v kaˇzd´em kroku volena n´ahodnˇe s pravdˇepodobnost´ı 0,5. Minim´aln´ı hodnoty fitness funkce jsou uvedeny v Tabulce 5.3.
0,10
0,15
0,70
2468,8
2560,1
2587,7
0,80
2542,4
2535,8
2597,7
0,85
2599,7
2584,9
2700,0
0,90
2668,1
2622,4
2723,3
0,95
2728,6
2755,7
2724,9
0,10
0,15
0,70
2482,8
2491,8
2506,0
0,80
2524,1
2521,7
2571,8
0,85
2514,9
2567,7
2608,7
0,90
2587,7
2593,4
2654,0
0,95
2571,6
2644,6
2680,6
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
0,10
0,15
0,70
2683,3
2542,9
2493,8
0,80
2495,6
2477,2
2524,6
0,85
2470,2
2498,4
2513,7
0,90
2620,8
2512,5
2525,6
0,95
2523,8
2524,7
2594,9
kˇr´ızˇ en´ı
Pravdˇepodobnost
0,05 0,10
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2700
2600
0,15
0, 7
0,10
0,05
2500
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2700
Pravdˇepodobnost mutace 0,05
60
0,15
2600
0, 7
Pravdˇepodobnost mutace 0,05
30
2700
2500
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,05
20
2800
Pravdˇepodobnost mutace
Fitness [km]
Velikost populace
0,05 2600 0,15 2500 0, 7
0,10 0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.3: Minim´aln´ı hodnoty fitness funkce pro variantu 3 - Popis viz Tabulka 5.1 Zdroj: Autor
Kombinac´ı obou typ˚u kˇr´ızˇ en´ı se podaˇrilo z´ıskat jeˇstˇe lepˇs´ı v´ysledky neˇz u varianty 2. Minim´aln´ı nalezen´a hodnota 2468,8 km je jiˇz niˇzsˇ´ı neˇz v´ysledky z´ıskan´e pomoc´ı Clarke-Wrightovy metody (2492,1 km). Z graf˚u na Obr. 5.5 je vidˇet, zˇ e oproti druh´e variantˇe doch´az´ı na poˇca´ tku 60
k pomalejˇs´ımu poklesu fitness funkce a i v dalˇs´ım pr˚ubˇehu jsou minim´aln´ı i pr˚umˇern´e hodnoty v´ıce kol´ısav´e. Vˇetˇs´ı variabilita pravdˇepodobnˇe umoˇznila z´ıskat lepˇs´ı v´ysledky. Ty z´aroveˇn nevykazuj´ı z´asadn´ı z´avislost na nastaven´ych parametrech, jak je vidˇet z Tabulky 5.3.
Fitness [km]
4000
min, max avg
3000
min abs
2000
5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104 9000
Fitness [km]
8000 7000
min, max
6000
avg
5000
min abs
4000 3000 0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.5: Pr˚ubˇeh algoritmu varianta 3 - Hodnoty paramter˚u a popis graf˚u viz Obr. 5.3 Zdroj: Autor
61
Varianta 4 - kˇr´ızˇ en´ı s n´ahodn´ym vkl´ad´an´ım s elitismem V chov´an´ı algoritmu u varianty 1 se projevilo, zˇ e pokud nezahrneme do algoritmu elitismus, pˇrich´az´ıme cˇ asto o dobr´a ˇreˇsen´ı a t´ım nalezneme i celkovˇe horˇs´ı v´ysledn´a ˇreˇsen´ı. V t´eto variantˇe proto zachov´ame zp˚usob kˇr´ızˇ en´ı z varianty 1 a pˇrid´ame elitismus.
0,05
0,10
0,15
0,70
2655,2
2482,7
2563,0
0,80
2559,7
2546,9
2626,2
0,85
2788,6
2750,2
2526,9
0,90
2674,4
2782,5
2578,4
0,95
2736,7
2528,4
2712,2
kˇr´ızˇ en´ı
Pravdˇepodobnost
20
Velikost populace
2800
Pravdˇepodobnost mutace Fitness [km]
Velikost populace
0,05
2700 2600
0,15 2500
0,10
0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2800
Pravdˇepodobnost mutace 0,10
0,15
0,70
2463,7
2481,5
2466,7
0,80
2562,2
2551,7
2696,6
0,85
2566,2
2756,0
2664,2
0,90
2592,3
2658,0
2696,5
0,95
2570,6
2661,5
2662,6
0,10
0,15
0,70
2582,9
2789,3
2733,3
0,80
2542,6
2596,2
2547,5
0,85
2630,1
2643,3
2644,6
0,90
2615,9
2648,6
2567,2
0,95
2669,0
2696,3
2724,1
kˇr´ızˇ en´ı
Pravdˇepodobnost
0,15
2600 0,05
0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2800
Pravdˇepodobnost mutace 0,05
60
2700
2500
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,10
0,05
30
0,10
2700 0,15 2600
0,05 2500 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.4: Minim´aln´ı hodnoty fitness funkce pro variantu 4 - Popis viz Tabulka 5.1 Zdroj: Autor
Pˇrestoˇze se v algoritmu jedn´a o relativnˇe malou zmˇenu, projevila se v koneˇcn´ych hodnot´ach v´yrazn´ym poklesem nalezen´e hodnoty fitness funkce. V´ysledky se pohybuj´ı v podobn´em
62
rozmez´ı jako ve variant´ach 2 a 3, nejlepˇs´ı nalezen´a hodnota fitness je v pˇr´ıpadˇe t´eto varianty 2463,7 km. Minim´aln´ı nalezen´e hodnoty fitness funkce jsou shrnuty v Tabulce 5.4. Vzhledem k pouˇzit´ı n´ahodn´eho kˇr´ızˇ en´ı doch´az´ı dle oˇcek´av´an´ı k pomalejˇs´ımu poklesu fitness funkce i vˇetˇs´ı variabilitˇe populac´ı, jak je vidˇet na Obr. 5.6. 6000
Fitness [km]
5000
min, max 4000 avg
3000 5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104
Fitness [km]
9000 8000 min, max
7000
avg
6000 5000 4000
0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.6: Hodnoty parametr˚u a popis graf˚u viz Obr. 5.3 Grafy na Obr. 5.6, 5.7 a 5.8 nezobrazuj´ı absolutn´ı minimum fitness funkce, kter´e se pˇri zahrnut´ı elitismu rovn´a minimu jednotliv´ych populac´ı. Zdroj: Autor
63
Varianta 5 - kˇr´ızˇ en´ı s vkl´ad´an´ım k nejbliˇzsˇ´ımu bodu s elitismem Pˇrid´an´ı elitismu do varianty 2 m´a na rozd´ıl od varianty 1 jen velmi mal´y vliv. To odpov´ıd´a tak´e tomu, zˇ e se i bez zahrnut´ı elitismu (varianta 2) minimum populace a absolutn´ı minimum po cel´y pr˚ubˇeh programu t´emˇeˇr shodovala a souˇcasnˇe pr˚umˇern´a hodnota fitness funkce v populaci byla jen o m´alo vyˇssˇ´ı neˇz jej´ı minimum. Po poˇca´ teˇcn´ı rychl´e konvergenci dojde k tomu, zˇ e pˇri kˇr´ızˇ en´ı, kter´e je do urˇcit´e m´ıry deterministick´e, doch´az´ı jen k mal´ym zmˇen´am v populaci. Nejlepˇs´ı ˇreˇsen´ı se tak i bez zahrnut´ı elitismu s vysokou pravdˇepodobnost´ı pˇren´asˇ´ı do dalˇs´ı generace. Velikost populace
2900
Pravdˇepodobnost mutace 0,10
0,15
0,70
2803,2
2763,1
2742,8
0,80
2762,4
2808,9
2682,8
0,85
2872,0
2653,3
2585,5
0,90
2812,4
2759,3
2700,0
0,95
2668,1
2827,6
2705,7
0,15
0,70
2738,5
2704,8
2503,4
0,80
2694,3
2752,6
2624,0
0,85
2528,5
2849,0
2623,9
0,90
2734,4
2603,7
2585,4
0,95
2750,5
2637,7
2578,0
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
0,70 kˇr´ızˇ en´ı
Pravdˇepodobnost
60
0,10
0,15
2695,9
2834,1
2610,0
0,15
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
0,10 2800 2700 2600 2500 0, 7
Pravdˇepodobnost mutace 0,05
2700
2900 Fitness [km]
0,10
0,10
0, 7
Pravdˇepodobnost mutace 0,05
30
2800
2600
0,15 0,05 0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2900 0,05 Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,05
0,05
20
2800 0,10 2700
0,80
2640,7
2651,3
2564,9
0,85
2597,3
2728,7
2523,6
2600
0,90
2913,1
2683,4
2661,6
2500 0, 7
0,95
2552,4
2594,5
2633,7
0,15 0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.5: Minim´aln´ı hodnoty fitness funkce pro variantu 5 - Popis viz Tabulka 5.1 Zdroj: Autor
64
Minim´aln´ı nalezen´a hodnota je 2468,4, kter´a je spolu s v´ysledky ostatn´ıch kombinac´ı pravdˇepodobnost´ı uvedena v Tabulce 5.5. Z pr˚ubˇehu algoritmu na Obr. 5.7a se m˚uzˇ e zd´at zvl´asˇtn´ı, zˇ e k v´yrazn´emu poklesu minima fitness funkce doˇslo v oblasti kolem 10 000 iterac´ı. Zde se pravdˇepodobnˇe jedn´a o vliv mutace, kter´a zajistila i po velk´em poˇctu krok˚u skokov´e zlepˇsen´ı. Tento z´avˇer koresponduje i s t´ım, zˇ e tento typ kˇr´ızˇ en´ı, kter´y m´alo vyuˇz´ıv´a n´ahodn´ych proces˚u, nemus´ı v´est k nejlepˇs´ım ˇreˇsen´ım.
Fitness [km]
4000
min, max avg 3000
5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104 9000
Fitness [km]
8000 7000 min, max
6000
avg
5000 4000 3000 0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.7: Hodnoty paramter˚u a popis graf˚u viz Obr. 5.6 Zdroj: Autor
65
Varianta 6 - stˇr´ıd´an´ı obou metod kˇr´ızˇ en´ı s elitismem Posledn´ı testovan´a varianta kombinuje oba typy kˇr´ızˇ en´ı spolu s elitismem. T´ım se podaˇrilo z´ıskat nejen nejniˇzsˇ´ı hodnotu ze vˇsech testovan´ych variant, ale celkovˇe se pro vˇsechny kombinace parametr˚u daˇrilo dosahovat n´ızk´ych hodnot, jak je vidˇet z Tabulky 5.6. Minim´aln´ı hodnoty fitness funkce se zde pohybuj´ı v rozmez´ı 2462,2 aˇz 2661,9 km. Nav´ıc doch´az´ı k rychl´emu poklesu fitness funkce na poˇca´ tku bˇehu programu, jej´ızˇ hodnota se v testovan´em bˇehu po 1000 kroc´ıch jiˇz d´ale nemˇen´ı (viz. grafy na Obr. 5.8).
0,10
0,15
0,70
2502,5
2633,0
2495,6
0,80
2548,5
2482,3
2559,8
0,85
2501,1
2565,9
2551,8
0,90
2538,2
2519,4
2527,1
0,95
2522,6
2627,0
2468,4
0,10
0,15
0,70
2490,5
2550,4
2509,6
0,80
2549,7
2661,9
2638,8
0,85
2517,6
2565,6
2562,6
0,90
2572,5
2538,8
2539,2
0,95
2569,9
2479,0
2528,3
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
0,10
0,15
0,70
2553,0
2563,2
2470,5
0,80
2525,0
2622,0
2476,3
0,85
2601,6
2542,2
2462,2
0,90
2652,0
2552,0
2542,4
0,95
2543,6
2488,4
2501,2
kˇr´ızˇ en´ı
0,15
2500
0,05 0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
0,10 2600 0,15 0,05
2500 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
2700
Pravdˇepodobnost mutace 0,05
60
0,10
2700
Pravdˇepodobnost mutace 0,05
30
2600
0, 7
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
Fitness [km]
0,05
20
Pravdˇepodobnost
Pravdˇepodobnost mutace
Fitness [km]
Velikost populace
0,10
0,05
2600
2500 0, 7
0,15 0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.6: Minim´aln´ı hodnoty fitness funkce pro variantu 6 - Popis viz Tabulka 5.1 Zdroj: Autor
66
Fitness [km]
5000
4000 min, max avg 3000
5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
(a) 1×104 9000
Fitness [km]
8000 7000 6000
min, max
5000
avg
4000 3000 2000
0
100 Poˇcet iterac´ı
200
(b)
Obr´azek 5.8: Hodnoty paramter˚u a popis graf˚u viz Obr. 5.3 Zdroj: Autor
67
Porovn´an´ı v´ysledku˚ Srovn´an´ı pr˚ubˇehu vˇsech sˇesti variant je zobrazeno na grafech na Obr. 5.10 a 5.11. Grafy zobrazuj´ı minim´aln´ı nalezenou hodnotu fitness funkce pro cel´y pr˚ubˇeh 20 000 iterac´ı (Obr. 5.10), resp. pro prvn´ıch dvˇe stˇe krok˚u (Obr. 5.11), stejnˇe jako tomu bylo u graf˚u zobrazen´ych u jednotliv´ych variant. Je zde vidˇet, zˇ e u varianty 1 doch´az´ı na poˇca´ tku k nejpomalejˇs´ımu poklesu hodnoty fitness funkce a z´aroveˇn je v cel´em pr˚ubˇehu minim´aln´ı hodnota fitness funkce v´yraznˇe vyˇssˇ´ı neˇz u ostatn´ıch variant. U varianty 4 doch´az´ı tak´e k pomalejˇs´ımu poˇca´ teˇcn´ımu poklesu, ale po pˇribliˇznˇe dvou tis´ıc´ıch iterac´ıch se jiˇz varianty 2 aˇz 6 pohybuj´ı v podobn´em rozmez´ı a koneˇcn´e v´ysledky jsou podobn´e. Nejlepˇs´ı ˇreˇsen´ı bylo z´ısk´ano u varianty 6 s celkovou d´elkou tras 2462,2 km, coˇz je o 1,2% niˇzsˇ´ı hodnota neˇz ˇreˇsen´ı nalezen´e pomoc´ı Clarke-Wrightovy metody. Pˇrehled tras je uveden v n´asleduj´ıc´ım odstavci a na Obr. 5.9 jsou trasy zobrazeny na mapˇe. U sˇest´e varianty byly z´aroveˇn z´ısk´any v´ysledky s nejmenˇs´ım rozmez´ım hodnot. Ot´azka rozptylu v´ysledk˚u je d˚uleˇzit´a pro obecn´e pouˇzit´ı algoritmu, abychom si mohli b´yt jisti, zˇ e nalezen´a hodnota nen´ı pˇr´ıliˇs vzd´alen´a od optima. I pˇresto z v´ysledk˚u vypl´yv´a, zˇ e je u genetick´ych algoritm˚u v dan´e u´ loze vhodnˇejˇs´ı pouˇz´ıt v´ıce kombinac´ı parametr˚u.
Nejlepˇs´ı nalezen´e rˇ eˇsen´ı trasa 1: 0 → 41 → 40 → 45 → 44 → 42 → 34 → 33 → 8 → 0 d´elka trasy: 309,7 km trasa 2: 0 → 47 → 48 → 49 → 56 → 55 → 54 → 52 → 53 → 0 d´elka trasy: 350,9 km trasa 3: 0 → 9 → 36 → 35 → 31 → 32 → 30 → 29 → 28 → 0 d´elka trasy: 362,1 km trasa 4: 0 → 27 → 25 → 26 → 37 → 38 → 39 → 43 → 46 → 0 d´elka trasy: 328,6 km trasa 5: 0 → 2 → 59 → 64 → 63 → 61 → 62 → 60 → 58 → 0 d´elka trasy: 295,1 km 68
trasa 6: 0 → 7 → 6 → 18 → 19 → 17 → 16 → 15 → 5 → 0 d´elka trasy: 390,3 km trasa 7: 0 → 10 → 11 → 12 → 13 → 14 → 4 → 57 → 1 → 0 d´elka trasy: 76,8 km trasa 8: 0 → 51 → 50 → 24 → 23 → 22 → 21 → 20 → 3 → 0 d´elka trasy: 348,7 km
Celkov´a d´elka: 2462,2 km
Obr´azek 5.9: Nejlepˇs´ı ˇreˇsen´ı nalezen´e genetick´ym algoritmem pro servisy pˇriˇrazen´e praˇzsk´emu depu Zdroj: Autor
69
4000
Fitness [km]
varianta 1 varianta 2 varianta 3
3000
varianta 4 varianta 5 varianta 6 5×103
0
1×104 Poˇcet iterac´ı
1, 5×104
2×104
Obr´azek 5.10: Srovn´an´ı minim´aln´ıch nalezen´ych hodnot jednotliv´ych varianta pro cel´y bˇeh algoritmu s poˇca´ teˇcn´ımi hodnotami 30 cˇ len˚u v populaci, pravdˇepodobnost´ı mutace 0,1 a pravdˇepodobnost´ı kˇr´ızˇ en´ı 0,8. Zdroj: Autor
1×104
Fitness [km]
9000 8000
varianta 1
7000
varianta 2
6000
varianta 3 varianta 4
5000
varianta 5
4000
varianta 6
3000 0
100 Poˇcet iterac´ı
200
Obr´azek 5.11: Srovn´an´ı minim´aln´ıch nalezen´ych hodnot pro prvn´ıch 200 krok˚u bˇehu algoritmu s poˇca´ teˇcn´ımi hodnotami 30 cˇ len˚u v populaci, pravdˇepodobnost´ı mutace 0,1 a pravdˇepodobnost´ı kˇr´ızˇ en´ı 0,8. Zdroj: Autor
70
Brnˇensk´e depo Na z´akladˇe otestov´an´ı chov´an´ı jednotliv´ych variant algoritmu, bylo pro z´ısk´an´ı rozvozov´ych tras z brnˇensk´eho depa pouˇzito pouze nastaven´ı parametr˚u z varianty 6, pˇri kter´em byly dosaˇzeny nejlepˇs´ı v´ysledky. Jedn´a se tedy o kombinaci obou typ˚u kˇr´ızˇ en´ı se zahrnut´ım elitismu. V´ysledky jsou opˇet shrnuty v pˇrehledov´e tabulce 5.7 spoleˇcnˇe se zobrazen´ım tˇechto v´ysledk˚u do graf˚u.
0,10
0,15
0,70
1462,5
1463,3
1576,3
0,80
1468,4
1465,3
1570,0
0,85
1467,6
1678,8
1467,5
0,90
1468,4
1468,4
1467,6
0,95
1469,6
1466,7
1464,8
0,10
0,15
0,70
1468,4
1468,4
1499,0
0,80
1572,2
1615,3
1577,1
0,85
1494,7
1465,7
1586,6
0,90
1577,7
1465,7
1467,5
0,95
1467,5
1616,7
1579,4
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
kˇr´ızˇ en´ı
Pravdˇepodobnost
1500
1400 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
1600
1500
0, 7
0,10
0,15
0,05
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Pravdˇepodobnost mutace 0,05
0,10
0,15
0,70
1467,6
1467,0
1468,9
0,80
1463,3
1465,2
1467,6
0,85
1468,4
1470,0
1468,0
0,90
1467,1
1462,5
1467,5
0,95
1472,5
1466,7
1467,8
60
0,15
Pravdˇepodobnost mutace 0,05
30
1600
0,05
Fitness [km]
kˇr´ızˇ en´ı
Pravdˇepodobnost
Velikost populace
0,10 Fitness [km]
0,05
20
1700
Pravdˇepodobnost mutace
Fitness [km]
Velikost populace
1470
0,15
0,10 0,05 1460 0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 5.7: Minim´aln´ı hodnoty fitness funkce pro trasy z brnˇensk´eho depa Zdroj: Autor
71
Minim´aln´ı nalezen´a hodnota fitness funkce je 1462,5 km pro trasy uveden´e v n´asleduj´ıc´ım pˇrehledu. Na Obr. 5.12 jsou tyto trasy zobrazeny na mapˇe.
Nejlepˇs´ı nalezen´e rˇ eˇsen´ı trasa 1: 0 → 72 → 71 → 75 → 65 → 68 → 69 → 70 → 79 → 0 d´elka trasy: 382,3 trasa 2: 0 → 74 → 73 → 76 → 67 → 66 → 82 → 81 → 83 → 0 d´elka trasy: 399,9 trasa 3: 0 → 85 → 97 → 96 → 95 → 94 → 93 → 92 → 91 → 0 d´elka trasy: 293,6 trasa 4: 0 → 78 → 0 d´elka trasy: 3,6 trasa 5: 0 → 77 → 80 → 84 → 90 → 89 → 87 → 88 → 86 → 0 d´elka trasy: 383,1 km Celov´a d´elka 1462,5
Obr´azek 5.12: Nejlepˇs´ı ˇreˇsen´ı nalezen´e genetick´ym algoritmem pro servisy pˇriˇrazen´e brnˇensk´emu depu Zdroj: Autor
72
5.3
Porovn´an´ı v´ysledku˚ GA a CW
Pokud srovn´ame z´ıskan´a ˇreˇsen´ı z obou dep s Clarke-Wrightovou metodou, podaˇrilo se naj´ıt trasy kratˇs´ı celkem o 3,56%. Pˇrehled nejlepˇs´ıch nalezen´ych ˇreˇsen´ı obou metod a procentu´aln´ı u´ spory genetick´eho algoritmu oproti Clarke-Wrightovi jsou uvedeny v Tabulce 5.8. depo Praha
depo Brno
celkem
Clarke-Wright [km]
2492,1
1577,60
4069,7
GA [km]
2462,2
1462,5
3924,7
´ uspora GA oproti CW
1,20%
7,30%
3,56%
Tabulka 5.8: Srovn´an´ı nalezen´ych ˇreˇsen´ı pomoc´ı Clarke-Wrightovy metody a genetick´ych algoritm˚u
73
K APITOLA 6 Aplikace genetickych ´ algoritmu˚ na lokaˇcn´ı ulohu ´
V pˇredchoz´ı kapitole jsme uvaˇzovali pozici dep danou na z´akladˇe jejich skuteˇcn´eho souˇcasn´eho um´ıstˇen´ı. Nyn´ı se zamˇeˇr´ıme na to, jak´y vliv m´a na d´elku rozvozov´ych tras zmˇena jejich lokace, pokus´ıme se naj´ıt optim´aln´ı um´ıstˇen´ı a pro toto nov´e um´ıstˇen´ı navrhneme nov´e rozvozov´e trasy, abychom je mohli porovnat s trasami nalezen´ymi pˇri p˚uvodn´ım um´ıstˇen´ı dep. Na rozd´ıl od u´ lohy okruˇzn´ıch j´ızd je pouˇzit´ı genetick´ych algoritm˚u pro lokaˇcn´ı u´ lohy jednoduˇssˇ´ı. Standardn´ı verze oper´ator˚u nen´ı potˇreba upravovat a jsou pro tento typ u´ lohy pˇr´ımo ˇ pouˇziteln´e. Um´ıstˇen´ı stˇredisek je omezeno na koneˇcnou mnoˇzinu m´ıst a to tak, zˇ e Ceskou republiku rozdˇel´ıme na 250 bod˚u ve vodorovn´em smˇeru a 150 ve svisl´em, coˇz odpov´ıd´a kroku pˇribliˇznˇe 2 km v obou smˇerech. Kaˇzd´y pr˚useˇc´ık t´eto s´ıtˇe je uvaˇzov´an jako moˇzn´e um´ıstˇen´ı stˇrediska, celkem je tedy moˇzn´e um´ıstˇen´ı do 37 500 bod˚u. Pro kaˇzd´y z tˇechto bod˚u byla spoˇctena vzd´alenost do vˇsech z 97 autoservis˚u pomoc´ı GoogleMaps. Vzhledem k denn´ımu limitu GoogleMaps 2500 dotaz˚u za den byl v´ypoˇcet ˇreˇsen distribuovanˇe pomoc´ı webov´e aplikace1 . 1
http://www.fish-life.net/diplomka/
74
Reprezentace Stejnˇe jako u u´ lohy okruˇzn´ıch j´ızd byla zvolena reprezentace pomoc´ı pˇrirozen´ych cˇ´ısel. Jednotliv´e lokace, kam mohou b´yt um´ıstˇena stˇrediska, jsou oˇc´ıslov´any a kaˇzd´y jedinec (ˇreˇsen´ı) v populaci tvoˇr´ı neuspoˇra´ dan´y seznam vybran´ych lokac´ı o d´elce n, kde n je poˇcet umist’ovan´ych stˇredisek.
Fitness funkce Servisy jsou pˇridˇeleny do atrakˇcn´ıch obvod˚u stˇredisek tak, zˇ e kaˇzd´y servis je pˇridˇelen do atrakˇcn´ıho obvodu toho stˇrediska, ke kter´emu je nejbl´ızˇ e. Pˇri shodn´ych vzd´alenostech se atrakˇcn´ı obvod zvol´ı n´ahodnˇe. Hodnota fitness funkce se pot´e spoˇc´ıt´a jako souˇcet vzd´alenost´ı vˇsech servis˚u ke stˇredisku, do jehoˇz atrakˇcn´ıho obvodu je dan´y servis pˇridˇelen. Jedn´a se o minimalizaˇcn´ı krit´erium.
Selekce Stejnˇe jako v pˇr´ıpadˇe u´ lohy okruˇzn´ıch j´ızd byla pouˇzita turnajov´a selekce.
Mutace Mutace je ˇreˇsena tak, zˇ e v genomu je n´ahodnˇe vybr´ana pozice a na jej´ı m´ısto je vloˇzen n´ahodn´y prvek ze seznamu vˇsech moˇzn´ych lokac´ı.
Kˇr´ızˇ en´ı Byla zvoleno jednobodov´e kˇr´ızˇ en´ı, tak jak bylo pops´ano v sekci 3.2.
V´ysledky V pˇr´ıpadˇe jednoho nebo dvou umist’ovan´ych stˇredisek je moˇzn´e z´ıskat v´ysledky i otestov´an´ım vˇsech moˇzn´ych kombinac´ı, kter´ych je
n k
, kde n je poˇcet moˇzn´ych um´ıstˇen´ı a k poˇcet
umist’ovan´ych stˇredisek. Pro k vˇetˇs´ı neˇz dva zaˇc´ın´a poˇcet moˇzn´ych kombinac´ı v´yraznˇe nar˚ustat a v´ypoˇcet ˇreˇsen´ı ,,hrubou silou” v rozumn´em cˇ ase neskonˇc´ı. Jiˇz pˇri umist’ov´an´ı tˇr´ı stˇredisek je 75
v naˇs´ı u´ loze poˇcet moˇzn´ych ˇreˇsen´ı pˇribliˇznˇe 9 × 1012 . Naproti tomu v genetick´em algoritmu o velikosti populace 50 a poˇctu generac´ı 20 000 se vytv´aˇr´ı a ohodnocuje 1 000 000 jedinc˚u (ˇreˇsen´ı). Problematick´ym m´ıstem je v t´eto u´ loze velk´e mnoˇzstv´ı moˇzn´ych um´ıstˇen´ı, kter´e bylo zvoleno tak, aby se ˇreˇsen´ı bl´ızˇ ilo spojit´e lokaˇcn´ı u´ loze, kdy je moˇzn´e um´ıstˇen´ı stˇrediska zcela libovoln´e. Doch´az´ı tak k tomu, zˇ e se velk´y poˇcet z moˇzn´ych lokac´ı bˇehem cel´eho bˇehu programu v˚ubec nepouˇzije. ˇ sen´ım tohoto probl´emu by mohla b´yt zmˇena mutace tak, zˇ e bliˇzsˇ´ı lokace by mˇely vˇetˇs´ı Reˇ pravdˇepodobnost v´ybˇeru na z´akladˇe zvolen´eho typu rozdˇelen´ı. T´ım by se zkoumala pouze oblast s vˇetˇs´ı pravdˇepodobnost´ı vhodn´eho um´ıstˇen´ı stˇrediska. Zde je ovˇsem nutn´a tak´e zmˇena reprezentace, kdy nestaˇc´ı pouze oˇc´ıslovan´y seznam lokac´ı, ale je nutn´e zn´at tak´e jejich geografick´e vztahy a rozm´ıstˇen´ı. Z´aroveˇn by pravdˇepodobnost mutace v pˇr´ıpadˇe vysok´eho pomˇeru moˇzn´ych lokac´ı a umist’ovan´ych stˇredisek nemˇela b´yt pˇr´ıliˇs n´ızk´a, aby se do ˇreˇsen´ı pouˇzilo v´ıce moˇznost´ı. Do testov´an´ı byla proto zahrnuta i vysok´a pravdˇepodobnost mutace 50%. V re´aln´ych situac´ıch obvykle spojitou u´ lohu neuvaˇzujeme, protoˇze moˇzn´e um´ıstˇen´ı je t´emˇeˇr vˇzdy limitov´ano a poˇcet moˇzn´ych um´ıstˇen´ı neb´yv´a velik´y. Pokud bychom ovˇsem v u´ loze uvaˇzovali jen mal´y poˇcet moˇzn´ych lokac´ı nemˇelo by velk´y v´yznam ˇreˇsit u´ lohu pomoc´ı genetick´ych algoritm˚u, protoˇze i pro vˇetˇs´ı poˇcty umist’ovan´ych stˇredisek by bylo st´ale moˇzn´e proj´ıt vˇsechny moˇznosti. V´ysledky genetick´eho algoritmu pro dvˇe a tˇri umist’ovan´a stˇrediska jsou v Tabulk´ach 6.1 a 6.2. Z´aroveˇn bylo exaktn´ım v´ypoˇctem ovˇeˇreno, zˇ e pro dvˇe stˇrediska se minim´aln´ı nalezen´a hodnota 7784,7 km rovn´a i skuteˇcn´emu optimu. Pˇribliˇznˇe ve tˇretinˇe v´ysledk˚u se tedy podaˇrilo naj´ıt optimum, a to pˇrestoˇze je poˇcet vytv´aˇren´ych ˇreˇsen´ı v genetick´em algoritmu pro dvˇe stˇrediska ˇra´ dovˇe 1000-kr´at niˇzsˇ´ı neˇz skuteˇcn´y poˇcet moˇzn´ych ˇreˇsen´ı. V pˇr´ıpadˇe mutace 50% nebyly z´ısk´any lepˇs´ı v´ysledky neˇz pˇri niˇzsˇ´ıch hodnot´ach, zde by bylo zˇrejmˇe vhodn´e uvaˇzovat o pˇrid´an´ı elitismu, protoˇze v pˇr´ıpadˇe vysok´e mutace pˇrich´az´ıme o dobr´a ˇreˇsen´ı. Pro tˇri stˇrediska jiˇz nen´ı moˇzn´e porovnat v´ysledky s exaktn´ım ˇreˇsen´ım. Vzhledem k relativnˇe mal´emu rozptylu z´ıskan´ych hodnot, je ovˇsem pravdˇepodobn´e, zˇ e v´ysledky nebudou od optima pˇr´ıliˇs vzd´alen´e.
76
0,05
0,10
0,15
0,50
0,70
7869,1
7784,7
7784,7
7804,5
0,80
7784,7
7795,0
7785,6
7792,7
0,85
7839,0
7785,6
7784,7
7792,7
0,90
7785,6
7784,7
7785,6
7784,7
0,95
7785,6
7784,7
7785,6
7826,2
kˇr´ızˇ en´ı
2 Pravdˇepodobnost
Pravdˇepodobnost mutace Fitness [km]
Poˇcet stˇredisek
7850
0,05 0,50
7800
0,10 0,15
0, 7
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 6.1: Minim´aln´ı hodnoty fitness funkce pro 2 umist’ovan´a stˇrediska Zdroj: Autor
0,05
0,10
0,15
0,50
0,70
6507,0
6479,3
6519,6
6543,7
0,80
6507,9
6506,4
6515,3
6503,0
0,85
6542,7
6530,6
6479,3
6548,7
0,90
6506,4
6561,2
6496,8
6546,8
0,95
6574,1
6482,7
6486,1
6554,5
kˇr´ızˇ en´ı
3 Pravdˇepodobnost
Pravdˇepodobnost mutace
6600 Fitness [km]
Poˇcet stˇredisek
0,50 0,05
6500 0,10 0, 7
0,15
0, 8 0, 9 Pravdˇepodobnost kˇr´ıˇzen´ı
Tabulka 6.2: Minim´aln´ı hodnoty fitness funkce pro 3 umist’ovan´a stˇrediska Zdroj: Autor
Hodnoty fitness funkce jsou d´ale zobrazeny na Obr. 6.1 a 6.2. Pro kaˇzd´y bod z moˇzn´ych lokac´ı, kter´y byl bˇehem bˇehu programu zahrnut do ˇreˇsen´ı, se spoˇc´ıtal pr˚umˇer hodnot fitness funkce, kter´e byly dan´emu ˇreˇsen´ı pˇriˇrazeny. V pˇr´ıpadˇe umist’ov´an´ı dvou stˇredisek se vyhodnotila fitness funkce dan´eho jedince a tato hodnota fitness funkce se pˇriˇcetla pro obˇe um´ıstˇen´ı k hodnotˇe, kter´a se na z´avˇer zpr˚umˇerovala. Na obr´azc´ıch je zn´azornˇeno jak je kter´a oblast vhodn´a pro um´ıstˇen´ı stˇrediska. Je zde vidˇet, ˇ e republice a tak´e rozm´ıstˇen´ım zˇ e v´ysledky u´ lohy jsou velmi ovlivnˇeny silniˇcn´ı s´ıt´ı v Cesk´ servis˚u ve velk´ych mˇestech a jejich okol´ı. V obou pˇr´ıpadech, jak pˇri umist’ov´an´ı dvou, tak tˇr´ı stˇredisek je nejv´yraznˇejˇs´ım m´ıstem Praha a to z d˚uvodu velk´eho poˇctu servis˚u v dan´e oblasti. Oproti oˇcek´av´an´ı se v pˇr´ıpadˇe dvou stˇredisek nevytvoˇrily dvˇe v´yrazn´e oblasti a kromˇe zˇrejm´eho um´ıstˇen´ı stˇrediska v Praze tvoˇr´ı velk´a oblast takˇrka barevnˇe jednolitou plochu jen s mal´ymi rozd´ıly fitness funkce. Naopak pˇri umist’ov´an´ı tˇr´ı stˇredisek se tˇri oblasti jednoznaˇcnˇe vyˇclenily.
77
ˇ se Obr´azek 6.1: Rozloˇzen´ı hodnot fitenss funkce pro dvˇe umist’ovan´a stˇrediska zobrazen´e na mapˇe CR zn´azornˇen´ım d´alnic a hlavn´ıch silnic. Zdroj: Autor
Obr´azek 6.2: Rozloˇzen´ı hodnot fitenss funkce pro tˇri umist’ovan´a stˇrediska Zdroj: Autor
78
Nov´e v´ysledky optim´aln´ıho um´ıstˇen´ı dep d´ale poslouˇzily jako vstup k vytvoˇren´ı nov´ych rozvozov´ych tras, aby se otestovalo, jak velk´y vliv by mˇela zmˇena um´ıstˇen´ı stˇredisek na celkovou d´elku tras. K tomu byl opˇet vyuˇzit genetick´y algoritmus tak, jak byl pops´an v Kapitole 5 ve variantˇe 6. Nov´e um´ıstˇen´ı dep spoleˇcnˇe s navrˇzen´ymi trasami je zn´azornˇeno na Obr. 6.3 a souhrn v´ysledk˚u t´eto i pˇredchoz´ıch kapitol je v Tabulce 6.3. Pˇrestoˇze pro umist’ov´an´ı dep bylo pouˇzito krit´erium minimalizace vzd´alenost´ı k servis˚um a nikoli krit´erium minimalizace d´elek rozvozov´ych tras, jsou novˇe nalezen´e trasy o 4,08% kratˇs´ı neˇz pˇri p˚uvodn´ım um´ıstˇen´ı dep. Lokaˇcn´ı u´ loha s krit´eriem minimalizace d´elek tras je u´ lohou, kter´a kombinuje dva NP-´upln´e probl´emy, kter´e je nutn´e ˇreˇsit propojenˇe. Genetick´e algoritmy by mohly b´yt v tomto pˇr´ıpadˇe vhodnou volbou pr´avˇe z d˚uvodu moˇznosti zahrnut´ı v´ıce krit´eri´ı do v´ypoˇctu fitness funkce a z´aroveˇn t´ematem pro moˇzn´e pokraˇcov´an´ı ve vyuˇzit´ı genetick´ych algoritm˚u v t´eto oblasti. depo 1
depo 2
celkem
Clarke-Wright [km]
2492,1
1577,60
4069,7
˚ GA1 puvodn´ ı depa [km]
2462,2
1462,5
3924,7
´ uspora oproti CW
1,20%
7,30%
3,56%
GA2 nov´a depa [km]
2506,3
1258,0
3764,3
´ uspora oproti CW
-0,57%
20,26%
7,50%
´ uspora oproti GA1
-1,79%
13,98%
4,08%
Tabulka 6.3: Srovn´an´ı nalezen´ych ˇreˇsen´ı pomoc´ı Clarke-Wrightovy metody a genetick´ych algoritm˚u
Nov´e trasy Depo 1 trasa 1: 0 → 28 → 29 → 30 → 36 → 35 → 31 → 38 → 37 → 0 d´elka trasy: 398,1 km trasa 2: 0 → 33 → 26 → 25 → 27 → 94 → 93 → 96 → 95 → 0 d´elka trasy: 346,4 km trasa 3: 0 → 12 → 1 → 46 → 10 → 11 → 8 → 9 → 0 d´elka trasy: 90,7 km
79
trasa 4: 0 → 51 → 50 → 24 → 23 → 22 → 21 → 20 → 0 d´elka trasy: 324,4 km trasa 5: 0 → 34 → 42 → 43 → 39 → 44 → 45 → 41 → 40 → 0 d´elka trasy: 300,4 km trasa 6: 0 → 61 → 62 → 60 → 15 → 16 → 17 → 18 → 19 → 0 d´elka trasy: 396,0 km trasa 7: 0 → 47 → 48 → 49 → 56 → 55 → 54 → 52 → 53 → 0 d´elka trasy: 364,6 km trasa 8: 0 → 4 → 57 → 3 → 2 → 13 → 0 d´elka trasy: 38,2 km trasa 9: 0 → 14 → 5 → 7 → 6 → 58 → 59 → 64 → 63 → 0 d´elka trasy: 247,5 km
D´elka celkem: 2506,3 km
Obr´azek 6.3: Nejlepˇs´ı nalezen´e trasy po zmˇenˇe um´ıstˇen´ı dep Zdroj: Autor
80
Depo 2 trasa 1: 0 → 80 → 92 → 32 → 84 → 83 → 81 → 82 → 0 d´elka trasy: 370,4 km trasa 2: 0 → 79 → 77 → 91 → 97 → 85 → 78 → 90 → 0 d´elka trasy: 291,0 km trasa 3: 0 → 71 → 72 → 73 → 76 → 74 → 67 → 66 → 75 → 0 d´elka trasy: 290,3 km trasa 4: 0 → 65 → 68 → 69 → 89 → 87 → 86 → 88 → 70 → 0 d´elka trasy: 306,3 km
D´elka celkem: 1258,0 km
81
K APITOLA 7 Z´avˇer
C´ılem t´eto pr´ace bylo navrhnout genetick´y algoritmus a analyzovat jeho chov´an´ı a v´ysledky pro u´ lohy diskr´etn´ı matematiky, konkr´etnˇe ty u´ lohy, kter´e maj´ı d˚uleˇzit´e vyuˇzit´ı v dopravˇe a logistice: u´ lohu okruˇzn´ıch j´ızd a lokaˇcn´ı u´ lohu. Jedn´a se o u´ lohy, kter´e patˇr´ı do skupiny probl´em˚u, pro nˇezˇ neexistuje algoritmus, kter´y by v rozumn´em cˇ ase nalezl optim´aln´ı ˇreˇsen´ı. Hledaj´ı se proto metody, kter´e poskytuj´ı ˇreˇsen´ı alespoˇn skoro optim´aln´ı, ale zato v´yraznˇe rychleji. Velikou skupinu takov´ych metod oznaˇcujeme jako metaheuristiky, do nichˇz patˇr´ı i genetick´e algoritmy. Genetick´e algoritmy jsou inspirov´any evoluˇcn´ımi procesy v pˇr´ırodˇe a snaˇz´ı se simulovat principy evoluce na poˇc´ıtaˇci. Jednotliv´e generace tvoˇr´ı jedinci r˚uzn´ych vlastnost´ı, kteˇr´ı pˇri pˇrechodu z jedn´e generace do druh´e proch´az´ı selekc´ı, kˇr´ızˇ en´ım a mutac´ı, a t´ım se postupnˇe zlepˇsuje vytv´aˇren´e ˇreˇsen´ı. V r´amci genetick´ych algoritm˚u existuje ˇrada variant, jak algoritmus implementovat, a r˚uzn´e moˇznosti se hod´ı pro r˚uzn´e typy u´ loh. Vytvoˇren´ı genetick´eho algoritmu spoˇc´ıv´a pˇredevˇs´ım ve volbˇe zp˚usobu reprezentace jedinc˚u a n´avrhu jednotliv´ych oper´ator˚u (selekce, kˇr´ızˇ en´ı a mutace). Pro porovn´an´ı chov´an´ı a v´ysledk˚u jednotliv´ych metod poslouˇzil pˇr´ıklad z m´e bakal´aˇrsk´e pr´ace, kter´a se vˇenovala optimalizaci z´asobovac´ı s´ıtˇe autoservis˚u. V bakal´aˇrsk´e pr´aci byla pro navrˇzen´ı rozvozov´ych tras pouˇzita Clarke-Wrightova metoda, kter´a je nejzn´amˇejˇs´ı heuristickou metodou pro u´ lohu okruˇzn´ıch j´ızd. Vytvoˇren´y program jsem v t´eto diplomov´e pr´aci d´ale rozˇs´ıˇrila na celou ˇ oblast Cesk´ e republiky a pro stejn´e zad´an´ı navrhla a implementovala genetick´y algoritmus.
82
Aplikaci genetick´ych algoritm˚u na nezjednoduˇsenou u´ lohu okruˇzn´ıch j´ızd nebyla v minulosti vˇenov´ana velk´a pozornost. Zamˇeˇrila jsem se proto na z´akladn´ı verzi u´ lohy bez dodateˇcn´ych ´ omezen´ı, tak aby byla vyuˇziteln´a pro uvaˇzovanou praktickou u´ lohu. Uloha okruˇzn´ıch j´ızd m´a nˇekter´a specifika a nen´ı moˇzn´e pouˇz´ıt standardn´ı genetick´e oper´atory, kter´e se bˇezˇ nˇe pouˇz´ıvaj´ı pˇri ˇreˇsen´ı jin´ych matematick´ych probl´em˚u. Algoritmus jsem navrhla s nˇekolika variantami opet´ator˚u a testovala s r˚uzn´ymi kombinacemi nastaven´ı vstupn´ıch parametr˚u. Pˇri pouˇzit´ı nejjednoduˇssˇ´ıch oper´ator˚u nebyly v´ysledky pˇr´ıliˇs uspokojiv´e, ale s dalˇs´ımi zmˇenami se podaˇrilo vytvoˇrit genetick´y algorimus, kter´y nalezl ˇreˇsen´ı srovnateln´e nebo i lepˇs´ı neˇz Clarke-Wrightova metoda. Na z´akladˇe testov´an´ı byly nalezeny doporuˇcen´e hodnoty vstupn´ıch parametr˚u, citlivost na nastaven´ı tˇechto parametr˚u nen´ı ovˇsem u nejl´epe funguj´ıc´ı varianty velk´a, a je tedy moˇzn´e z´ıskat relativnˇe dobr´e v´ysledky s libovoln´ym vstupn´ım nastaven´ım. Nastaven´ı vstupn´ıch parametr˚u je obecnˇe problematick´ym bodem metaheuristick´ych metod a u z´ıskan´ych v´ysledk˚u nen´ı jasn´e, jak dobr´e nebo sˇpatn´e v´ysledky jsme z´ıskali. Nav´ıc je moˇzn´e d´ıky n´ahodn´e sloˇzce pˇri stejn´em poˇca´ teˇcn´ım nastaven´ı z´ıskat r˚uzn´e v´ysledky. V nejlepˇs´ı testovan´e variantˇe byl pˇri r˚uzn´em nastaven´ı vstupn´ıch parametr˚u rozd´ıl mezi nejlepˇs´ı a nejhorˇs´ı hodnotou 8%. V dalˇs´ı cˇ a´ sti jsem se zamˇeˇrila na optimalizaci um´ıstˇen´ı dep vzhledem k dan´e s´ıti obsluhovan´ych servis˚u. C´ılem bylo ovˇeˇrit, jak´y vliv bude m´ıt zmˇena polohy dep na celkovou d´elku rozvozov´ych tras. Pro lokaˇcn´ı u´ lohu byl opˇet pouˇzit genetick´y algoritmus, kter´y bylo v pˇr´ıpadˇe umist’ov´an´ı dvou dep moˇzn´e porovnat i s exaktn´ım ˇreˇsen´ım (skuteˇcn´ym optimem). Po zmˇenˇe polohy dep byly nalezeny nov´e rozvozov´e trasy pomoc´ı genetick´eho algoritmu ve variantˇe, kter´a poskytovala nejlepˇs´ı v´ysledky. Pˇri zachov´an´ı dep z p˚uvodn´ı u´ lohy se podaˇrilo pomoc´ı genetick´eho algoritmu naj´ıt trasy kratˇs´ı o 3,56% a pˇri zmˇenˇe dep o 7,50% oproti hodnot´am z´ıskan´ym pomoc´ı Clarke-Wrightovy metody. Pouˇzit´ı genetick´ych algoritm˚u pro tyto typy u´ loh je tedy moˇzn´e, ne vˇsechny varianty a nastaven´ı ovˇsem vrac´ı pˇrijateln´e v´ysledky. Vzhledem k tomu, zˇ e v´ysledky byly porovn´any pouze s jednou dalˇs´ı metodou, bylo by vhodn´e ovˇeˇrit navrˇzen´e algoritmy na vˇetˇs´ı skupinˇe testovac´ıch dat, aby bylo moˇzn´e posoudit chov´an´ı algoritmu pˇri r˚uzn´ych velikostech u´ loh i v r´amci srovn´an´ı s jin´ymi metaheuristikami.
83
L ITERATURA
ˇ Y, ´ P. Optimalizaˇcn´ı Ulohy, ´ [1] HLINEN v´yukov´y text (FI: IA102). [vid. 1. 4. 2012]. Dostupn´e ˜ z: http://www.fi.muni.cz/hlineny/Teaching/OU/OU-text07.pdf [2] COOPER L. Location-allocation problems. In: Operations Research, vol. 11, pp. 301-343, 1963. ISSN 0254-5330. [3] HAKIMI, S. L. Optimal location of switching centers and the absolute centers and medians of a graph, In: Operations Research vol. 12, pp. 450–459, 1964. ISSN 0254-5330. [4] BADRI, M. A. Combining the analytic hierarchy process and goal programming for global facility location-allocation problem. In: International Journal of Production Economics, 62, pp. 237– 248, 1999. ISSN: 0925-5273. [5] KLOSE, A. and A. DREXL: Facility location models for distribution system design. In: European Journal of Operational Research vol. 162(1), pp. 4-29, 2005. [6] ROBERT, F. L. and J. HENRIK. Properties and Solution Methods for Large LocationAllocation Problems. In: The Journal of the Operations Research Society, vol. 33, issue 5, pp. 443-352, 1982. ISSN: 0160-5682. [7] GALVAO, R.D. a L.A. RAGGI. A method for solving to optimality uncapacitated location problems. In: Annals of Operations Research, vol. 18, pp. 225-244, 1989. ISSN 02545330. [8] HALL, R. W. Handbook of Transportation Science [online]. Second Edition. Secaucus: Kluwer Academic Publishers, 2002. ISBN 978-1402072468 [vid. 1. 4. 2012]. Dostupn´e z: http://site.ebrary.com/lib/cvut/Doc?id=10067394
84
[9] WEBER, A. Theory of the Location of Industries [online]. Chicago: The University of Chicago Press, 1929. ISBN 978-1153435611 [vid. 1. 4. 2012]. Dostupn´e z: http://archive.org/details/alfredweberstheo00webe [10] KENDALL M.G a P.A.P. MORGAN. Geometrical probability [online]. London: Charles Griffin & Company Limited, 1963 [vid. 1. 4. 2012]. Dostupn´e z: http://archive.org/details/geometricalproba033077mbp [11] ANEJA, Y. P. a M. PARLAR. Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel. IN: Transportation Science, vol. 28, pp. 70-76, 1994. ISSN 0041-1655. [12] BATTA R., GHOSE A. a U. S. PALEKAR. Locating facilities on the Manhatten metric with arbitrarily shaped barriers and convex forbidden regions. In: Transportation Science, vol. 23, pp. 26-36, 1989. ISSN 0041-1655. [13] LARSON R. C. a G. SADIQ. Facility locations with the Manhattan metric in the presence of barriers to travel. In: Operations Research, vol 31, pp. 652-669, 1983. ISSN 0254-5330. [14] FISHER, M.L. Vehicle Routing. IN: Handbooks in Operations Research and Management Science, vol. 8, pp. 1-33, 1995. ISSN 0927-0507. [15] PEREIRA, F. B. GVR: a New Genetic Representation for the Vehicle Routing Problem [online]. [vid. 1. 4. 2012]. Dostupn´e z: http://fmachado.dei.uc.pt/wp-content/papercitedata/pdf/ptmc02a.pdf [16] WEBB, M.H.J. Cost functions in the location of depots for multiple-delivery journeys. In: Operational Research Quarterly, vol. 19-3, pp. 311–320, 1968. ISSN: 0030-3623. [17] PERL, J. a M.S. DASKIN. A warehouse location-routing problem In: Transportation Research, vol. 19B-5, pp. 381–396, 1985. ISSN: 1366-5545. [18] TEITZ, M.B. a P. BART. Heuristic methods for estimating the generalized vertex median of a weighted graph. In: Operations Research vol. 16, pp. 955-961, 1968. ISSN 02545330. [19] Metaheuristics
Network
[online].
[vid.
1.
4.
http://www.metaheuristics.org/index.php?main=1&sub=11 85
2012].
Dostupn´e
z:
[20] PARDALOS, P. M. Combinatorial and Global Optimization [online]. River Edge, USA: World Scientific, 2002. ISBN 978-9812778215 [vid. 1. 4. 2012]. Dostupn´e z: http://site.ebrary.com/lib/cvut/Doc?id=10201288 [21] GLOVER, F. Tabu Search Methods in Artificial Intelligence and Operations Research. In: ORSA Artificial Intelligence, Vol. 1-2, pp. 6, 1987. ISSN 0899-1499. [22] AARTS, E. a J.K. LENSTRA. Local Search in Combinatorial Optimization. Hoboken: Wiley and Sons, 1997. ISBN: 978-0471948223. [23] ANSARI, N. a E. HOU. Computational Intelligence for Optimization. Norwell: Kluwer Academic Publishers, 1997. ISBN: 978-0792398387. [24] GENDRAU, M., G. Laporte a J.Y. POTVIN. Vehicle routing: Modern heuristics. In: Local Search in Combinatorial Optimization, pp. 311-336. Hoboken: Wiley and Sons, 1997. ISBN: 978-0471948223. [25] MODARES, A., S. SOMHOM a T. ENWAKA. A self - organizing neural network approach for multiple travelling salesman and vehicle routing problems. In: International Transactions in Operational Research, vol. 6, pp. 591-606, 1999. ISSN: 0969-6016. [26] DORIGO, M., V. MANIEZZO a A. COLORNI. The ant system: Optimization by a colony of cooperating agents. In: IEEE Transactions on Systems, vol. 26, pp. 1-13, 1996. ISSN: ISSN 1094-6977. [27] GOLDBERG, D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, Kluwer Academic Publishers, 1989. ISBN: 978-0201157673. [28] MICHALEWICZ, Z. Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer, 1994. ISBN: 3-540553878 [29] ZELINKA, I. Evoluˇcn´ı v´ypoˇcetn´ı techniky : principy a aplikace. Praha: BEN - technick´a literatura, 2009. ISBN: 978-8073002183. [30] BEASLEY, D., D. R. BULL a R. R. MARTIN. An overview of genetic algorithms: Part 1, fundamentals. In: University Computing, vol. 15-2, pp. 58-69, 1993. ISSN : 0265-4385.
86
ˇ ´ A. Anal´yza a optimalizace z´asobov´an´ı autorizovan´ych servis˚u vozidel [31] RYBICKOV A, ˇ ˇ ´ Peugeot a Citro¨en. Praha: CVUT 2010. Bakal´aˇrsk´a pr´ace, CVUT, Fakulta dopravn´ı, Ustav ˇr´ızen´ı dopravn´ıch proces˚u a logistiky. ˇ ´ J. a M. SLIVONE. ˇ Optimalizace svozu a rozvozu kusov´ych z´asilek. In: Perner’s [32] SIROK Y, Contacts, vol. 5, no. 1, pp. 255-269, 2010. ISSN 1801-674X.
87
P Rˇ ´I LOHA A Seznam autoservisu˚
ID jm´eno
ˇ PSC
souˇradnice GPS
obec
1
Federal cars
148 00
50◦ 2’13.366”N, 14◦ 29’14.902”E
Praha 4
2
ˇ a republika 140 00 Peugeot Cesk´
50◦ 2’55.019”N, 14◦ 26’26.211”E
Praha 4
3
Autocentral Bart˚unˇek
142 00
50◦ 1’22.506”N, 14◦ 26’38.141”E
Praha 4
4
Domansk´y Citro¨en
155 00
50◦ 2’22.16”N, 14◦ 19’49.68”E
Praha 5
5
Avcars
162 06
50◦ 5’31.359”N, 14◦ 21’2.865”E
Praha 6
6
V group
272 02
50◦ 8’15.274”N, 14◦ 5’39.025”E
Kladno
7
Auto Schwab
272 02
50◦ 8’42.556”N, 14◦ 7’22.808”E
Kladno
8
Intensys
190 12
50◦ 5’7.917”N, 14◦ 34’40.184”E
Praha 9
9
Domansk´y
198 00
50◦ 5’15.361”N, 14◦ 33’21.286”E
Praha 9
10 Autoport
100 33
50◦ 3’53.937”N, 14◦ 29’41.547”E
Praha 10
11 Autospol
100 00
50◦ 4’26.71”N, 14◦ 30’20.545”E
Praha 10
12 Autecentrum Doj´acˇ ek
101 00
50◦ 3’54.688”N, 14◦ 27’33.523”E
Praha 10
ˇ a republika 13 Citro¨en Cesk´
182 00
50◦ 5’36.503”N, 14◦ 26’28.735”E
Praha 8
14 City-car
170 00
50◦ 6’9.986”N, 14◦ 26’49.816”E
Praha 8
15 Joel
434 01
50◦ 28’56.854”N, 13◦ 37’13.701”E
Most
16 Auto Hrub´y
431 59
50◦ 31’9.238”N, 13◦ 28’4.265”E
Vysok´a Pec
17 Auta Dr´asta
430 01
50◦ 29’33.266”N, 13◦ 26’13.144”E
Chomutov
18 Minimo
360 06
50◦ 13’22.922”N, 12◦ 49’17.526”E
Karlovy Vary
88
ID jm´eno
ˇ PSC
souˇradnice GPS
obec
19 Luboˇs Dr´asta auto
356 04
50◦ 10’7.841”N, 12◦ 38’51.966”E
Doln´ı Rychnov
20 Autoservis Plzeˇn Letna
301 52
49◦ 44’59.425”N, 13◦ 24’16.03”E
Plzeˇn
21 Auto Volf
345 62
49◦ 43’50.848”N, 13◦ 21’9.291”E
Plzeˇn
22 Interconex west
317 05
49◦ 43’32.206”N, 13◦ 24’19.689”E
Plzeˇn
23 Invest tel auto
339 01
49◦ 23’27.223”N, 13◦ 16’32.117”E
Klatovy
24 Auto Kaln´y
339 01
49◦ 15’3.171”N, 13◦ 36’24.649”E
ˇ Cimice u Suˇsice
25 Autosalon Louda
280 00
50◦ 1’57.852”N, 15◦ 13’8.404”E
Kol´ın
26 Gefco
280 02
50◦ 3’55.05”N, 15◦ 13’23.097”E
Kol´ın
ˇ 27 Auto Svec
280 02
50◦ 0’43.853”N, 15◦ 13’32.562”E
Kol´ın
28 Unikom
284 45
49◦ 56’48.238”N, 15◦ 17’23.303”E
Kutn´a Hora
29 Citro¨en Autotechnik
530 09
50◦ 3’9.439”N, 15◦ 46’8.6”E
Pardubice
30 Peugeot Autotechnik
530 09
50◦ 3’9.439”N, 15◦ 46’8.6”E
Pardubice
31 Presto
516 01
50◦ 9’39.089”N, 16◦ 16’16.722”E
Rychnov nad Knˇezˇ nou
32 Autoart PP
566 01
49◦ 56’32.597”N, 16◦ 9’59.111”E
Vysok´e M´yto
33 Auto Slav´ık Podˇebrady
290 01
50◦ 8’35.888”N, 15◦ 9’20.414”E
Chot’a´ nky
34 Road cars
289 01
50◦ 13’48.908”N, 15◦ 12’35.188”E
Nymburk
35 Regina
500 03
50◦ 13’2.633”N, 15◦ 52’24.993”E
Hradec Kr´alov´e
36 Accord car
500 03
50◦ 12’48.681”N, 15◦ 49’26.811”E
Hradec Kr´alov´e
37 Auto qualt
544 42
50◦ 25’25.721”N, 15◦ 52’36.272”E
Choustn´ıkovo Hradiˇstˇe
38 Autostyl
541 01
50◦ 34’10.93”N, 15◦ 53’53.419”E
Trutnov
39 VM incom
542 01
50◦ 37’17.72”N, 15◦ 36’37.134”E
Vrchlab´ı
40 Auto Marek
293 01
50◦ 26’2.505”N, 14◦ 55’8.115”E
Mlad´a Boleslav
41 Auto Mrkviˇcka
293 06
50◦ 25’54.569”N, 14◦ 55’52.745”E
Kosmonosy
42 Auto Vondr´ak
506 01
50◦ 25’57.925”N, 15◦ 23’28.211”E
J´ıcˇ´ın
43 Autogalerie V.I.T.V.A.R. 509 01
50◦ 29’42.018”N, 15◦ 31’16.638”E
Nov´a Paka
44 Autohofi
466 05
50◦ 44’53.077”N, 15◦ 7’57.497”E
Jablonec nad Nisou
45 Federal cars
463 13
50◦ 44’32.155”N, 15◦ 3’21.261”E
Liberec
89
ID jm´eno
ˇ PSC
souˇradnice GPS
obec
46 Auto Babiˇs
251 64
49◦ 55’54.315”N, 14◦ 42’51.094”E
Mnichovice
47 Auto Mich´alek
256 01
49◦ 46’38.794”N, 14◦ 41’7.777”E
Beneˇsov
48 Domansk´y
390 03
49◦ 24’49.265”N, 14◦ 39’53.19”E
T´abor
49 Jiˇr´ı Hejda
377 01
49◦ 9’28.045”N, 14◦ 59’52.333”E
Jindˇrich˚uv Hradec
ˇ y 50 Auto Cern´
261 01
49◦ 41’45.972”N, 14◦ 0’47.859”E
Pˇr´ıbram
51 Color cars
261 01
49◦ 42’6.429”N, 14◦ 7’24.576”E
Pˇr´ıbram
52 Veto CZ
397 01
49◦ 18’15.32”N, 14◦ 8’22.299”E
P´ısek
53 Auto Kapl CZ
397 01
49◦ 18’24.297”N, 14◦ 5’43.939”E
P´ısek
54 HS auto
370 01
48◦ 59’16.809”N, 14◦ 27’5.316”E
ˇ e Budˇejovice Cesk´
55 City – car
370 01
48◦ 58’35.497”N, 14◦ 29’5.935”E
ˇ e Budˇejovice Cesk´
56 Auto Linhart
370 01
49◦ 1’8.676”N, 14◦ 29’48.104”E
ˇ e Budˇejovice Cesk´
57 Domansk´y Peugeot
155 00
50◦ 2’22.16”N, 14◦ 19’49.68”E
Praha 5
58 c - car
278 01
50◦ 14’59.606”N, 14◦ 19’14.969”E
Kralupy nad Vltavou
59 Auto Doˇsek
276 01
50◦ 21’56.566”N, 14◦ 28’27.869”E
Mˇeln´ık
60 Auto Dakar
415 01
50◦ 39’39.857”N, 13◦ 51’23.769”E
Teplice
ˇ 61 Autod´ıly Spindler
400 07
50◦ 39’48.466”N, 14◦ 4’54.739”E
´ ı nad Labem Ust´
62 Fair autotop
400 10
50◦ 41’27.998”N, 13◦ 58’57.089”E
´ ı nad Labem Ust´
63 Bash
405 02
50◦ 46’20.059”N, 14◦ 11’57.788”E
Dˇecˇ´ın
64 Auto Grob´ar
404 98
50◦ 46’33.186”N, 14◦ 13’56.89”E
Dˇecˇ´ın
65 Autocentrum Luk´asˇ 757 01
49◦ 29’30.970”N, 17◦ 57’43.056”E
Valaˇssk´e Meziˇr´ıcˇ´ı
66 ADO
738 02
49◦ 40’5.059”N, 18◦ 20’45.557”E
Fr´ydek-M´ıstek
67 Autosalon Svoboda
739 01
49◦ 38’46.576”N, 18◦ 22’11.647”E
Hodonovice
68 IVOS
763 16
49◦ 16’44.443”N, 17◦ 41’6.212”E
Fryˇst´ak
69 Unicars CZ
763 02
49◦ 12’42.509”N, 17◦ 35’32.773”E
Zl´ın
70 M Servis
767 01
49◦ 16’32.574”N, 17◦ 24’10.678”E
Kromˇeˇr´ızˇ
71 Auto Hruˇska
747 14
49◦ 57’11.300”N, 17◦ 52’8.882”E
Opava
90
ID jm´eno
ˇ PSC
souˇradnice GPS
obec
72 S-profit
747 14
49◦ 56’8.365”N, 17◦ 55’0.912”E
Opava
73 Kodecar
702 00
49◦ 51’6.502”N, 18◦ 16’48.637”E
Ostrava
74 Auto Tich´y
703 00
49◦ 48’20.315”N, 18◦ 15’56.030”E
Ostrava
75 JV Car
742 53
49◦ 38’2.328”N, 17◦ 59’21.239”E
Kun´ın
76 Meteor Car
735 14
49◦ 52’45.563”N, 18◦ 25’55.628”E
Orlov´a
77 Famko
602 00
49◦ 11’20.386”N, 16◦ 37’13.883”E
Brno
78 Auto H.B.
617 00
49◦ 10’1.711”N, 16◦ 37’45.361”E
Brno
79 Carling
627 00
49◦ 10’57.767”N, 16◦ 41’5.510”E
Brno
80 CL junior
680 01
49◦ 29’21.386”N, 16◦ 40’0.970”E
Boskovice
81 Kodecar
702 00
49◦ 36’18.331”N, 17◦ 16’49.595”E
Olomouc
82 Artcom Group
772 11
49◦ 35’23.658”N, 17◦ 18’53.327”E
Olomouc
83 Car Citon
774 00
49◦ 35’48.556”N, 17◦ 14’21.354”E
Olomouc
84 Agrega
789 61
49◦ 56’25.094”N, 16◦ 55’29.950”E
Bludov
85 RM Servis
619 00
49◦ 8’36.838”N, 16◦ 36’9.497”E
Brno
86 Auto Wozar
691 44
48◦ 47’59.676”N, 16◦ 47’4.171”E
Lednice
87 Jonal
695 01
48◦ 51’49.468”N, 17◦ 8’57.149”E
Hodon´ın
88 CSAD Hodon´ın
695 39
48◦ 52’20.388”N, 17◦ 7’0.505”E
Hodon´ın
89 Lion Car
686 04
49◦ 2’56.173”N, 17◦ 27’57.863”E
Kunovice
90 UH Car
686 01
49◦ 4’14.178”N, 17◦ 27’51.682”E
Uhersk´e Hradiˇstˇe
91 Brno Car
612 00
49◦ 14’2.728”N, 16◦ 35’11.792”E
Brno
92 Automotive
593 01
49◦ 31’40.829”N, 16◦ 15’18.238”E
Bystˇrice n. Pernˇstejnem
93 Auto Jaroˇs
592 14
49◦ 31’25.586”N, 15◦ 54’34.938”E
Nov´e Vesel´ı
ˇ 94 Autocentrum Spinar 580 01
49◦ 35’42.086”N, 15◦ 34’41.077”E
Havl´ıcˇ k˚uv Brod
95 Autopraktik
396 01
49◦ 32’30.160”N, 15◦ 21’48.510”E
Humpolec
ˇ 96 Auto Spinar
586 01
49◦ 23’54.766”N, 15◦ 36’47.023”E
Jihlava
97 PP Auto
674 01
49◦ 12’50.080”N, 15◦ 49’42.002”E
Tˇreb´ıcˇ
ˇ Tabulka A.1: Seznam autoservis˚u v CR
91
