FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV MATEMATIKY

´ UCEN ˇ Í TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ YRSTV ´ Í FAKULTA STROJNÍHO INZEN ´ USTAV MATEMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF MATHEMATICS

´ MODELY DOPRAVNÍCH ULOH ´ MATEMATICKE MATHEMATICAL MODELS FOR TRANSPORTATION PROBLEMS

´ RSK ˇ A ´ PRACE ´ BAKALA BACHELOR’S THESIS

´ AUTOR PRACE

´ HELENA PASCHKEOVA

AUTHOR

´ VEDOUCÍ PRACE SUPERVISOR

BRNO 2012

RNDr. PAVEL POPELA, Ph.D.

Vysoké učení technické v Brně, Fakulta strojního inženýrství Ústav matematiky Akademický rok: 2011/2012

ZADÁNÍ BAKALÁŘSKÉ PRÁCE student(ka): Helena Paschkeová který/která studuje v bakalářském studijním programu obor: Matematické inženýrství (3901R021) Ředitel ústavu Vám v souladu se zákonem č.111/1998 o vysokých školách a se Studijním a zkušebním řádem VUT v Brně určuje následující téma bakalářské práce: Matematické modely dopravních úloh v anglickém jazyce: Mathematical models for transportation problems Stručná charakteristika problematiky úkolu: Student se seznámí s problematikou matematických modelů dopravních úloh, včetně jejich významu pro logistické aplikace. Zaměří se zejména na úlohy matematického programování s důrazem na úlohy o toku v sítích a úlohy založené na modifikacích úlohy obchodního cestujícího. Budou studovány vlastnosti vybraných úloh, modifikovány algoritmy a realizovány testovací výpočty s využitím dat z realných aplikací. Cíle bakalářské práce: Předpokládá se vývoj původních i modifikace existujících modelů a algoritmů a jejich aplikace v návaznosti na problémy řešené v rámci spolupráce ústavu matematiky FSI VUT v Brně se specialisty v oblasti logistiky z norské Molde University College (prof. Kjetil Kare Haugen).

Seznam odborné literatury: Christofides. N. .: Graph Theory - an Algorithmic Approach. Academic Press 1975. Wolsey L. A.: Integer programming. John Wiley and Sons, 1998. Ghiani, G., Laporte, G., Musmanno, R.: Introduction to Logistics Systems Planning and Control. John Wiley and Sons, New York, 2004.

Vedoucí bakalářské práce: RNDr. Pavel Popela, Ph.D. Termín odevzdání bakalářské práce je stanoven časovým plánem akademického roku 2011/2012. V Brně, dne 29.10.2011 L.S.

_______________________________ prof. RNDr. Josef Šlapal, CSc. Ředitel ústavu

_______________________________ prof. RNDr. Miroslav Doupovec, CSc., dr. h. c. Děkan fakulty

Abstrakt Práce se zab´ yvá modelován´ım a ˇreˇsen´ım vybran´ ych dopravn´ıch u ´loh. Nejprve jsou uvedeny historické postˇrehy, praktické poznatky a formulovány vybrané problémy. Potom se práce vˇenuje modelován´ı vybran´ ych dopravn´ıch u ´loh pomoc´ı matematického (lineárn´ıho a celoˇc´ıselného) programován´ı a teorie graf˚ u. Pozornost je pˇredevˇs´ım vˇenována problému obchodn´ıho cestuj´ıc´ıho a r˚ uzn´ ym metodám jeho ˇreˇsen´ı a jejich modifikac´ım. V práci jsou rovnˇeˇz uvedeny komentáˇre k origináln´ı programové implementaci model˚ u a algoritm˚ u, a to jak model˚ u v systému GAMS, tak grafov´ ych algoritm˚ u v jazyce Python. Algoritmy ˇ Vysledky testován´ı byly testovány na u ´loze zahrnuj´ıc´ı 73 b´ yval´ ych okresn´ıch mˇest v CR. jsou v závˇereˇcné ˇca´sti porovnány a vyhodnoceny. Summary The thesis deals with modelling and solution techniques for the selected transportation problems. Firstly, historical remarks and application-related comments are introduced. Then the selected transportation problems are defined and mathematical programming and graph theory concepts are utilised to model them. The travelling salesman problem and suitable algorithms are under focus. The original implementation in GAMS and Python is discussed. Algorithms have been tested for the instance based on the set of 73 towns in the Czech Republic. Finally, the test results are evaluated and compared. Kl´ıˇ cov´ a slova dopravn´ı u ´lohy, optimalizace, teorie graf˚ u, problém obchodn´ıho cestuj´ıc´ıho, heuristiky Keywords transportation problem, optimization, graph theory, travelling salesman problem, heuristics

´ H. Matematické modely dopravn´ıch u PASCHKEOVA, ´loh. Brno: Vysoké uˇcen´ı technické v Brnˇe, Fakulta strojn´ıho inˇzen´ yrstv´ı, 2012. 60 s. Vedouc´ı RNDr. Pavel Popela, Ph.D.

Prohlaˇsuji, ˇze jsem bakaláˇrskou práci Matematické modely dopravn´ıch u ´loh vypracovala samostatnˇe s pouˇzit´ım materiál˚ u uveden´ ych v seznamu literatury. Helena Paschkeová

Ráda bych zde podˇekovala vedouc´ımu bakaláˇrské práce RNDr. Pavlu Popelovi, PhD. za jeho cenné rady a ˇcas, kter´ y mi vˇenoval pˇri ˇreˇsen´ı dané problematiky. V neposledn´ı ˇradˇe také dˇekuji vˇsem, kteˇr´ı se pod´ıleli na jazykové korektuˇre této bakaláˇrské práce. Helena Paschkeová

Obsah 1 Dopravn´ı u ´ lohy 1.1 Historie . . . . . . . . . . . . . 1.2 Praktické poznatky . . . . . . . 1.3 Typy u ´loh . . . . . . . . . . . . 1.4 Problém obchodn´ıho cestuj´ıc´ıho 1.5 Problém ˇc´ınského listonoˇse . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

13 13 13 14 15 16

2 Matematick´ e programov´ an´ı 2.1 Lineárn´ı programován´ı . . . . . . . 2.1.1 Model dopravn´ı u ´lohy . . . ´ 2.2 Ulohy celoˇc´ıselného programován´ı . 2.2.1 Model problému obchodn´ıho

. . . . . . . . . . . . . . . . . . . . . cestuj´ıc´ıho .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

17 17 18 21 22

3 Teorie graf˚ u 3.1 Základn´ı pojmy . . . . . . 3.2 Cykly v grafu . . . . . . . 3.2.1 Hamilton˚ uv cyklus 3.2.2 Euler˚ uv cyklus . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

25 25 28 28 29

4 Heuristiky 4.1 V´ yznam heuristik . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Heuristiky pro u ´lohu obchodn´ıho cestuj´ıc´ıho . . . . . . . . . . 4.2.1 Metoda hledán´ı nejbliˇzˇs´ıho souseda . . . . . . . . . . . 4.2.2 Metoda hladového algoritmu . . . . . . . . . . . . . . . 4.2.3 Metoda vkládán´ı mˇest do trasy . . . . . . . . . . . . . 4.2.4 Metoda dvojité minimáln´ı kostry grafu . . . . . . . . . 4.2.5 Christofidesova metoda . . . . . . . . . . . . . . . . . . 4.3 Algoritmy pro zlepˇsen´ı vlastnost´ı trasy obchodn´ıho cestuj´ıc´ıho 4.3.1 2-optimáln´ı algoritmus . . . . . . . . . . . . . . . . . . 4.3.2 3-optimáln´ı algoritmus . . . . . . . . . . . . . . . . . . 4.3.3 k-optimáln´ı algoritmus . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

31 31 31 32 34 35 36 37 39 39 43 46

. . . .

. . . .

. . . .

. . . . .

. . . .

. . . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . .

5 Porovn´ an´ı v´ ysledk˚ u testov´ an´ı metod

47

6 Pokroˇ cil´ e algoritmy a modely 51 6.1 Pokroˇcilé algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2 Vehicle routing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7 Z´ avˇ er

55

8 Pˇ r´ılohy 8.1 Minimáln´ı kostra grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Algoritmus pro minimáln´ı párován´ı v grafu . . . . . . . . . . . . . . . . . . 8.3 Seznam pˇr´ıloh na CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59 59 59 60

11

1. Dopravn´ı u ´ lohy Za dopravn´ı u ´lohy a logistiku oznaˇcujeme organizaci, pˇrepravu a uskladnˇen´ı materiálu ˇci v´ yrobk˚ u na cestˇe k zákazn´ıkovi a pˇrepravu samotn´ ych osob z jednoho m´ısta na jiné. [4] Pˇrestoˇze mˇelo slovo logistika dˇr´ıve ˇcistˇe vojensk´ y v´ yznam, dnes se t´ yká pˇreváˇznˇe distribuce v´ yrobk˚ u kaˇzdodenn´ı potˇreby. C´ılem je vytvoˇrit systém, ve kterém je ten správn´ y produkt pˇrepraven na dané m´ısto v dan´ y ˇcas. Tento problém, aˇc se zdá jednoduch´ y, zahrnuje rozsáhlou problematiku od zásobován´ı po koneˇcn´ y prodej a mohou na nˇem záviset dokonce i lidské ˇzivoty. Málokterá firma totiˇz zajiˇst’uje cel´ y v´ yrobn´ı cyklus od vytˇeˇzen´ı surovin aˇz po distribuci v´ yrobk˚ u a mus´ı se proto spoléhat i na subdodavatele. Nav´ıc mnoho zákazn´ık˚ u si dnes jiˇz zvyklo na trh s neustál´ ym pˇr´ısunem nov´ ych model˚ u, které nut´ı firmy k inovac´ım a tedy i neustálému v´ yvoji a vyuˇz´ıván´ı nov´ ych materiál˚ u. T´ım se se s´ıt’ pˇrepravy materiál˚ u a v´ yrobk˚ u mˇen´ı takˇrka kontinuálnˇe. Pˇri tomto procesu, kter´ y je pro kaˇzdou firmu nepostradateln´ y, docház´ı k utrácen´ı nemalého mnoˇzstv´ı penˇez, a proto se jej firmy snaˇz´ı co nejv´ıce zefektivnit. K tomu jim pomáhaj´ı modern´ı modely dopravn´ıch s´ıt´ı, které jsou schopny pˇrizp˚ usobit se zmˇenˇe dodavatel˚ u i odbˇeratel˚ u a uˇsetˇrit pen´ıze, které mohou b´ yt reinvestovány do v´ yzkumu.

1.1. Historie Historie ˇreˇsen´ı dopravn´ıch u ´loh zaˇc´ıná v polovinˇe 19. stolet´ı pˇri rozvoji manufaktur ve vˇetˇs´ıch mˇestech a rozvoji sériové v´ yroby. Z poˇca´tku bylo moˇzné v´ yrobky dodávat jen do nejbliˇzˇs´ıho okol´ı továren, protoˇze doprava zboˇz´ı byla drahá. Nejv´ıce vyuˇz´ıvanou dopravou zboˇz´ı na vˇetˇs´ı vzdálenosti byly lodˇe (pˇredevˇs´ım z Indie a jin´ ych koloni´ı). Sn´ıˇzen´ı náklad˚ u na dopravu prob´ıhalo jednoduˇse tak, ˇze se lodˇe naloˇzily vˇzdy plné a jednotliv´ı prodejci se domlouvali na rozdˇelen´ı náklad˚ u na pˇrepravu. V pr˚ ubˇehu 19. stolet´ı doˇslo k rozvoji ˇ ˇzelezniˇcn´ı s´ıtˇe a t´ım i dopravy vnitrozemské. Zelezniˇcn´ı doprava pˇrispˇela pˇredevˇs´ım k rozvoji na západn´ı stranˇe Spojen´ ych stát˚ u americk´ ych, kam se dopravovalo mnoho v´ yrobk˚ u z v´ ychodu zemˇe. Opravdová revoluce pˇriˇsla ale aˇz s vynálezem automobilu na pˇrelomu 19. a 20. stolet´ı. Auta byla relativnˇe levná, zp˚ usobila rozvoj silniˇcn´ı s´ıtˇe a umoˇznila dopravovat individuálnˇe mnohem menˇs´ı zásilky neˇz vlakem nebo lod´ı a to pˇr´ımo na m´ısto urˇcen´ı. D´ıky rozvoji silniˇcn´ı s´ıtˇe se mnohonásobnˇe rozrostly moˇznosti dopravy a pˇrepravy zboˇz´ı k zákazn´ıkovi. Proto se také ve 30. letech zaˇc´ıná hovoˇrit o tzv. dopravn´ı u ´loze, tedy minimalizován´ı náklad˚ u na distribuci zboˇz´ı. Rozv´ıjej´ıc´ı se teorie je pak vyuˇz´ıváno i v pr˚ ubˇehu druhé svˇetové války k zásobován´ı armád. Po válce docház´ı k prudkému rozvoji dopravn´ı techniky (d´ıky váleˇcn´ ym technologi´ım) a zefektivnˇen´ı dopravn´ıch s´ıt´ı aˇz do dneˇsn´ıch dn´ı. V´ıce o historii viz [5].

1.2. Praktick´ e poznatky V praxi je tˇreba zajistit pˇrepravu v´ yrobk˚ u od v´ yrobce k odbˇerateli a minimalizovat moˇzná zpoˇzdˇen´ı a prodraˇzován´ı zakázek. V angliˇctinˇe se takov´ y postup oznaˇcuje jako Supply chain. Jedná se o komplexn´ı logistick´ y systém, kter´ y zaˇc´ıná u v´ ybˇeru a dovozu základn´ıch surovin, pokraˇcuje zpracován´ım v pˇr´ısluˇsn´ ych závodech a skladován´ım v meziskladech a konˇc´ı u koneˇcného zákazn´ıka. Typick´ y pˇr´ıklad vid´ıme na obrázku 1.1. V pr˚ ubˇehu zpra-

13

cován´ı surovin na v´ yrobky m˚ uˇzeme zvolit i strategii v´ yroby polotovar˚ u. V´ yroba tedy m˚ uˇze b´ yt rozdˇelena na v´ıce závod˚ u, ˇci m˚ uˇzeme hotové polotovary pˇr´ımo nakupovat.

Obrázek 1.1: Schéma distribuce v´ yrobk˚ u [4] Logistika se ale ˇcasto v´ yrobou a konkrétn´ım zpracován´ım v rámci jednotliv´ ych závod˚ u nezab´ yvá a povaˇzuje je za objekty, pro které staˇc´ı vˇedˇet potˇrebné vstupy, v´ ystupy a dobu zpracován´ı materiálu na v´ yrobek. Pokud se soustˇred´ıme na konkrétn´ı v´ yrobek, kter´ y v pr˚ ubˇehu svého vzniku projde cel´ ym t´ımto systémem, m˚ uˇzeme rozliˇsit dva základn´ı modely distribuce: • push supply chains jsou modely distribuce v´ yrobk˚ u takové, kde jsou v´ yrobky zpracovávány pr˚ ubˇeˇznˇe a jejich mnoˇzstv´ı je regulováno pomoc´ı pˇredpovˇedi poptávky. K tˇemto v´ yrobk˚ um patˇr´ı drtivá vˇetˇsina komerˇcnˇe zpracovávaného zboˇz´ı. • pull supply chains jsou modely distribuce, kde je v´ yrobek vyroben pouze v pˇr´ıpadˇe, ˇze o nˇej zákazn´ık poˇzádá. Jedná se tedy pˇredevˇs´ım o kusovou v´ yrobu. Pro distribuci v´ yrobk˚ u v praxi lze pak vyuˇz´ıt kombinaci obou metod a to tak, ˇze jednotlivé polotovary zpracováváme pr˚ ubˇeˇznˇe a koneˇcné v´ yrobky sestavujeme aˇz po vyˇza´dán´ı zákazn´ıka. Zkrát´ıme t´ım podstatnˇe dobu v´ yroby u pull systému, ale zároveˇ n máme vˇetˇs´ı variabilitu v´ yrobk˚ u oproti push systému. D˚ uleˇzité je uvˇedomit si nejen cestu v´ yrobku k zákazn´ıkovi, ale zároveˇ n i cestu od zákazn´ıka k v´ yrobci. Pokud dojde v jakémkoli stupni v´ yroby k závadˇe na v´ yrobku, je tˇreba jej opravit. Pokud závadu objev´ı aˇz zákazn´ık, je tˇreba zajistit pˇrevoz zpˇet do závodu a opravu. Pokud je tedy pˇrepravn´ı s´ıt’ zvolena nevhodnˇe a pˇreprava samostatného vadného v´ yrobku zpˇet je vedena neefektivnˇe, m˚ uˇze nastat i pˇr´ıpad, kdy vadné v´ yrobky jednoduˇse vyhazujeme a ztrác´ıme tak i pˇr´ıpadné náhradn´ı d´ıly na dalˇs´ı v´ yrobky.

1.3. Typy u ´ loh V pˇr´ıpadˇe sestavován´ı jakéhokoli modelu je tˇreba si uvˇedomit, které skuteˇcnosti jsou natolik podstatné, ˇze je nezbytnˇe nutné je do modelu zahrnout. Vˇetˇsinou staˇc´ı pouze 14

vytvoˇrit model m´ıst d˚ uleˇzit´ ych pro v´ yrobu a distribuci a vzájemn´ ych cest mezi nimi. Mohou zde b´ yt ovˇsem i poˇzadavky na pˇrevoz v´ yrobku, kter´ y m˚ uˇze b´ yt kˇrehk´ y, chemicky nebezpeˇcn´ y nebo rychle se kaz´ıc´ı. M˚ uˇze se jednat napˇr´ıklad i o ˇzivá zv´ıˇrata. Zároveˇ n mohou m´ıt zákazn´ıci poˇzadavky na ˇcas doruˇcen´ı a je tedy tˇreba navˇst´ıvit zákazn´ıky v urˇcitém ˇcasovém poˇrad´ı. Pˇri vykládán´ı a nakládán´ı zboˇz´ı je tˇreba zváˇzit, zda je potˇreba tuto ˇcasovou prodlevu zanedbat nebo je podstatná vzhledem k dobˇe pˇrepravy. Obecnˇe se vˇsak snaˇz´ıme modely vytváˇret co nejjednoduˇsˇs´ı a t´ım si v´ yraznˇe uspoˇrit práci a v´ ypoˇcetn´ı ˇcas. Dále se ve zbytku práce budeme zab´ yvat pouze ˇreˇsen´ım problém˚ u, které závis´ı na pˇrepravˇe mezi dan´ ymi m´ısty a nebudeme uvaˇzovat ˇza´dné speciáln´ı poˇzadavky na v´ yrobky nebo od zákazn´ık˚ u. Rozebereme si základn´ı u ´lohu pˇrepravy ˇreˇsenou pomoc´ı lineárn´ıho programován´ı a dále u ´lohu obchodn´ıho cestuj´ıc´ıho, která je d˚ uleˇzitou základn´ı u ´lohou pro ˇreˇsen´ı dalˇs´ıch sloˇzitˇejˇs´ıch u ´loh.

1.4. Probl´ em obchodn´ıho cestuj´ıc´ıho Problém obchodn´ıho cestuj´ıc´ıho je jedn´ım z nejznámˇejˇs´ıch problém˚ u z oblasti diskrétn´ı optimalizace. Zadán´ı u ´lohy zn´ı takto: Obchodn´ı cestuj´ıc´ı má sch˚ uzku v n mˇestech a chce je navˇst´ıvit v takovém poˇrad´ı, aby mu cestován´ı zabralo nejménˇe ˇcasu. Kaˇzdé mˇesto je navˇst´ıveno minimálnˇe jednou a po navˇst´ıven´ı vˇsech mˇest se obchodn´ı cestuj´ıc´ı vrac´ı do p˚ uvodn´ıho mˇesta. [13] Jedná se tedy o u ´lohu nalezen´ı nejkratˇs´ı cesty mezi vˇsemi mˇesty, které chce dan´ y obchodn´ı cestuj´ıc´ı navˇst´ıvit. Formulace minimálnˇe jednou“ je ˇcasto nahrazena formulac´ı ” právˇe jednou“. Formulace minimálnˇe jednou vede na obecnˇejˇs´ı zadán´ı u ´lohy. Obecnˇe ” totiˇz graf mˇest s cestami m˚ uˇze m´ıt tvar tzv. stromu a nemus´ı b´ yt Hamiltonovsk´ y. V´ıce k tomuto tématu najdete v kapitole 3.2.1. ´ Uloha samozˇrejmˇe obecnˇe nemus´ı b´ yt symetrická, tedy z mˇesta A do mˇesta B m˚ uˇze b´ yt jiná vzdálenost neˇz z mˇesta B do A. Pro lepˇs´ı pˇredstavu je vhodné pˇredstavit si parn´ık, kter´ y pluje po a proti proudu ˇreky. Zat´ımco po proudu bude parn´ık pˇrekonávat vzdálenost s minimáln´ı námahou, proti proudu bude tˇreba motor˚ u, které spotˇrebovávaj´ı palivo a prodraˇzuj´ı cestu. Cena cesty tedy nemus´ı záviset pouze na vzdálenosti, ale i na pˇrev´ yˇsen´ı, pouˇzitém prostˇredku dopravy a podobnˇe. Ve své práci se budu podrobnˇe zab´ yvat hlavnˇe t´ımto problémem, kter´ y budu pro ˇ e republiky. Jako testovac´ı mˇesta jsem vyuˇzila vˇsech 73 názornost ˇreˇsit na mapˇe Cesk´ ˇ e republiky a vytvoˇrila matici urˇcuj´ıc´ı vzdálenosti, mezi b´ yval´ ych okresn´ıch mˇest Cesk´ tˇemito mˇesty. Domn´ıvám se, ˇze právˇe tento model poskytne ˇctenáˇri dostateˇcnou orientaci a pˇredstavu o tom, jak jednotlivé v´ ypoˇcty a postupy ˇreˇsen´ı prob´ıhaj´ı. Poˇcet mˇest se mi zdá dostateˇcn´ y pro znázornˇen´ı sloˇzitosti problému. Uspoˇra´dán´ı mˇest ukazuje obrázek 1.2. Vzájemná poloha mˇest je pˇrevzata z kartografick´ ych map [1]. Jako vzdálenost mezi mˇesty poˇc´ıtám vzduˇsnou spojnici mezi nimi. Vzdálenost mezi mˇesty je Eulerovská a na vˇsech algoritmech je tedy jasnˇe vidˇet princip jejich postupu. Pro libovolné dalˇs´ı modely lze samozˇrejmˇe vytvoˇrit obecnou matici vzdálenost´ı a aplikovat algoritmy s touto matic´ı.

15

•

•• •

• •• • • • • • • • • • • • • • • • • • • • • • •

• • • •

• •

•

• • • •

• •

•

•

•

• • •

• • • • • • • • • • • • • • • • • • • • • • ˇ e republiky Obrázek 1.2: Stylizovaná mapa okresn´ıch mˇest Cesk´ •

•

1.5. Probl´ em ˇ c´ınsk´ eho listonoˇ se Problém ˇc´ınského listonoˇse je zadán´ım velmi podobn´ y problému obchodn´ıho cestuj´ıc´ıho, pˇresto se ˇreˇsen´ı velmi liˇs´ı. Zadán´ı u ´lohy zn´ı takto: ˇ ınský listonoˇs mus´ı roznést poˇstovn´ı psan´ı do vˇsech ulic ve svém mˇestˇe a C´ vrátit se zpˇet na m´ısto, ze kterého vycházel. V jakém poˇrad´ı a v jakém smˇeru má ulice proj´ıt, aby jeho trasa byla nejkratˇs´ı moˇzná? Tuto u ´lohu formuloval ˇc´ınsk´ y matematik M. K. Kwan roku 1962. Tato u ´loha lze opˇet zobrazit v grafu, kde jednotlivé ulice reprezentuj´ı hrany a kˇriˇzovatky mezi ulicemi reprezentuj´ı vrcholy v grafu. V´ıce o této problematice a Eulerov´ ych cyklech lze nalézt v kapitole 3.2.2. Plat´ı, ˇze pokud v grafu existuje Eulerovsk´ y tah, pak je tento Eulerovsk´ y tah optimáln´ı cestou listonoˇse. [13]

16

2. Matematick´ e programov´ an´ı 2.1. Line´ arn´ı programov´ an´ı Lineárn´ı programován´ı ˇreˇs´ı problémy souvisej´ıc´ı s hledán´ım vázan´ ych extrém˚ u u lineárn´ıch funkc´ı v´ıce promˇenn´ ych. Omezuj´ıc´ı podm´ınky tˇechto funkc´ı jsou ve tvaru lineárn´ıch ˇ sen´ım tˇechto problém˚ rovnic nebo nerovnost´ı. Reˇ u se jako jeden z prvn´ıch matematik˚ u zab´ yval J. B. J. Fourier, kter´ y je vyuˇzil ve své teorii pravdˇepodobnosti a v analytické mechanice. Od ˇctyˇricát´ ych let se vyuˇz´ıvalo lineárn´ıho programován´ı v ekonomii a pozdˇeji i k ˇreˇsen´ı dopravn´ıch problém˚ u. Rozvoj efektivn´ıch metod ˇreˇsen´ı tˇechto u ´loh pˇredstavil G. B. Dantzig, kter´ y vytvoˇril tzv. simplexovou metodu.1 , která je dnes jiˇz vˇseobecnˇe známou metodou. V souˇcasné dobˇe se stále pracuje na dalˇs´ıch metodách ˇreˇsen´ı tˇechto u ´loh. S rozvojem poˇc´ıtaˇc˚ u se otev´ıraj´ı moˇznosti pro ˇreˇsen´ı pomoc´ı paraleln´ıch v´ ypoˇct˚ u. Matematickou formulac´ı u ´lohy lineárn´ıho programován´ı ve standardn´ım tvaru rozum´ıme: min{

n X

cj x j |

X

aij xj = bi , i = 1, . . . , m, xj ≥ 0, j = 1, . . . , n},

j=1

kde cj , bi , aij ∈ R jsou konstantn´ı koeficienty u ´lohy a xj ∈ R jsou neznámé promˇenné u ´lohy. V literatuˇre je uvedeno, ˇze kaˇzdou u ´lohu lineárn´ıho programován´ı lze pˇrevést na standardn´ı tvar. [9] T´ımto pˇr´ıstupem lze vyˇreˇsit i ˇsirokou paletu dalˇs´ıch problém˚ u, dopravn´ıch u ´loh a organizace pˇrepravy. Zadán´ı nˇekter´ ych z tˇechto problém˚ u se pokus´ım naznaˇcit na nˇekolika dalˇs´ıch ˇrádc´ıch. Pˇ reprava zboˇ z´ı dodavatel – odbˇ eratel Základn´ı u ´lohou je u ´loha pˇrepravy zboˇz´ı od r˚ uzn´ ych dodavatel˚ u k odbˇeratel˚ um. Pˇriˇcemˇz lze do modelu pˇridat mezisklady, ˇci továrny, které pˇr´ıpadné polotovary od dodavatel˚ u ´ pˇremˇen´ı v koneˇcn´ y v´ yrobek a poté jej transportuj´ı k odbˇerateli. Ukolem je pak minimalizovat celkovou cenu pˇrepravy, pˇr´ıpadnˇe celkov´ y pˇrepravn´ı ˇcas. Lepˇs´ı pochopen´ı ˇs´ıˇre problému pak uvád´ı obrázek 1.1. Proces v´ yroby Jedná se o u ´lohu nalezen´ı optimáln´ıho postupu v´ yroby v´ yrobku. At’ uˇz z hlediska mnoˇzstv´ı pouˇzit´ ych materiál˚ u, tak poˇrad´ım jednotliv´ ych krok˚ u v´ yroby. Dobr´ ym pˇr´ıkladem m˚ uˇze b´ yt v´ yroba urˇcitého typu oceli a jej´ıho dodateˇcného legován´ı. [9] Jak m˚ uˇzeme vidˇet, jsou metody lineárn´ıho programován´ı pomˇernˇe uˇziteˇcné na praktické aplikace v dopravˇe a ekonomii v´ yroby. Pomoc´ı vhodn´ ych algoritm˚ u tzv. ˇreˇsiˇc˚ u staˇc´ı pak jen vhodnˇe formulovat u ´lohu a zadat ji danému vhodnému ˇreˇsiˇci na vyˇreˇsen´ı. S rozvojem poˇc´ıtaˇcové technologie a v´ ypoˇcetn´ı kapacity pak maj´ı i tyto metody reálné pouˇzit´ı v praxi. 1

Srozumitelné vysvˇetlen´ı lze nalézt na internetové adrese: http://www.algoritmy.net/article/1416/Simplexova-metoda.

17

ˇ siˇce jsou ˇcasto vyv´ıjeny jednotliv´ Reˇ ymi univerzitami nebo prestiˇzn´ımi firmami. Jsou ˇ siˇce m˚ ˇcasto specializované na dan´ y typ u ´loh. Reˇ uˇzeme obecnˇe dˇelit na ˇreˇsiˇce urˇcené pro lineárn´ı programován´ı (LP), lineárn´ı programován´ı s celoˇc´ıseln´ ymi promˇenn´ ymi (MIP) ˇci nelineárn´ı programován´ı (NLP). Program GAMS nab´ız´ı ˇsirokou paletu velmi efektivn´ıch ˇreˇsic˚ u, které m˚ uˇzeme pouˇz´ıt pro náˇs v´ ypoˇcet. Pro problém v následuj´ıc´ı kapitole byl zvolen ˇreˇsiˇc CPLEX pro lineárn´ı programován´ı vyv´ıjen´ y spoleˇcnost´ı IBM. Pro lepˇs´ı orientaci v zadán´ı u ´loh jsem se rozhodla uvést jedno vzorové sestaven´ı modelu a jeho vyˇreˇsen´ı. Pˇredevˇs´ım chci pˇribl´ıˇzit postup a ˇreˇsen´ı konkrétnˇe a pak také ukázat, ˇze k vyˇreˇsen´ı tˇechto model˚ u staˇc´ı i obyˇcejn´ y tabulkov´ y kalkulátor, kter´ y m˚ uˇze b´ yt i zdarma dostupn´ y ke staˇzen´ı na internetu.

2.1.1. Model dopravn´ı u ´ lohy Uk´ azkov´ y pˇ r´ıklad ˇ ych Budˇejovic´ıch, Kutné Hoˇre a Olomouci) Mˇejme firmu se tˇremi továrnami (v Cesk´ vyrábˇej´ıc´ımi hraˇcky, která má poboˇcky ve tˇrech mˇestech (v Praze, Brnˇe a Ostravˇe). Do poboˇcek ve mˇestech chod´ı lidé nakupovat tyto hraˇcky a t´ım vytváˇrej´ı poptávku. Firma se snaˇz´ı m´ıt co nejvˇetˇs´ı zisk a neutrácet proto mnoho na pˇrepravˇe. Je tedy zapotˇreb´ı minimalizovat náklady.

Obrázek 2.1: Jednoduch´ y model Sestav´ıme tedy následuj´ıc´ı model, kde indexem i oznaˇc´ıme promˇenné souvisej´ıc´ı s továrnami a indexem j promˇenné souvisej´ıc´ı s poboˇckami. Problém: 3 X 3 X minimalizuj cij xij i=1 j=1

Kde promˇenná xij oznaˇcuje, kolik hraˇcek se poveze z továrny i do poboˇcky j. Cenu cesty urˇcuje matice cen C, jej´ıˇz prvky jsou ceny pˇrepravy cij mezi továrnou i a poboˇckou j. Podm´ınky: • kaˇzdá továrna m˚ uˇze vyprodukovat maximálnˇe ai v´ yrobk˚ u X xij ≤ ai , ∀ i ∈ {1, 2, 3} • kaˇzdá poboˇcka mus´ı b´ yt zásobena minimálnˇe tak, aby se uspokojili vˇsichni zákazn´ıci v n´ı nakupuj´ıc´ı. Mus´ı m´ıt dovezeno minimálnˇe bj v´ yrobk˚ u. X xij ≥ bj , ∀ j ∈ {1, 2, 3} 18

cenová matice C Kutná Hora ˇ e Budˇejovice Cesk´ Olomouc

Praha Brno Ostrava 87 176 343 155 213 380 283 77 95

Dále udáme v´ yrobn´ı kapacity jednotliv´ ych továren a velikost poptávky v jednotliv´ ych poboˇckách matice kapacity v´ yroby A kapacita v´ yroby ai matice poptávky B poptávka bj

ˇ e Budˇejovice Olomouc Kutná Hora Cesk´ 600 4500 3000 Praha 3000

Brno 2500

Ostrava 1500

Takto lze tedy definovat základn´ı u ´lohu dopravy zboˇz´ı. Tuto u ´lohu lze jednoduˇse ˇreˇsit simplexovou metodou pomoc´ı algoritmu a nalézt ˇreˇsen´ı. Literatura uvád´ı dalˇs´ı efektivnˇejˇs´ı algoritmy [13]. V´ yhodou pouˇzit´ı simplexové metody je jej´ı rozˇs´ıˇren´ı a dostupnost. V dneˇsn´ı dobˇe existuje ˇrada program˚ u, které maj´ı standardn´ı ˇreˇsiˇce a lze je bez problému vyuˇz´ıt. ´ Ulohu jsem tedy ˇreˇsila ukázkovˇe v programech GAMS a MS Excel. GAMS je specializovan´ y software pro ˇreˇsen´ı optimalizaˇcn´ıch u ´loh a je tedy vhodné uvést alespoˇ n jednoduchou ukázku z nˇej. Tabulkové kalkulátory Microsoft Excel ˇci Open Office Calc jsou dnes jiˇz rozˇs´ıˇren´ ymi programy na témˇeˇr kaˇzdém poˇc´ıtaˇci a jedná se o obecnˇe pouˇziteln´ y nástroj i pro pokroˇcilé matematické v´ ypoˇcty, proto jsem si dovolila zaˇradit i ˇreˇsen´ı tohoto pˇr´ıkladu v tˇechto programech. Zdrojové kódy a programy jsou pˇriloˇzené na CD v deskách práce. ˇ sen´ım této u Reˇ ´lohy tedy bude matice pˇrepravy X: matice pˇrepravy v´ yrobk˚ uX Kutná Hora ˇ Ceské Budˇejovice Olomouc

Praha Brno Ostrava 600 0 0 2400 1000 0 0 1500 1500

Grafické ˇreˇsen´ı pak bude vypadat takto:

Obrázek 2.2: Grafické ˇreˇsen´ı u ´vodn´ıho pˇr´ıkladu ˇ Cerven´ e ˇsipky ukazuj´ı ˇreˇsen´ı této u ´lohy. Modré spojnice reprezentuj´ı cesty, které z˚ ustávaj´ı nevyuˇzity. 19

V´ yˇse popsan´ y model je samozˇrejmˇe velmi zjednoduˇsen´ y a vhodn´ y sp´ıˇse jako ilustraˇcn´ı ´ pˇr´ıklad. V praxi programy pracuj´ı s mnohem vˇetˇs´ım mnoˇzstv´ım dat. Ulohu lze pˇredevˇs´ım rozˇs´ıˇrit a pˇribl´ıˇzit realitˇe modelován´ım: • sklad˚ u a mezisklad˚ u v´ yrobk˚ u • závislost´ı produkce v´ yrobk˚ u na daném ˇcase nebo dnu v t´ ydnu • závislost´ı prodeje v´ yrobk˚ u na daném ˇcase nebo dnu v t´ ydnu • postupné pˇrepravy mezi továrnami (dle technologického postupu v´ yroby) • pˇreprava pˇr´ımo k zákazn´ıkovi × pˇreprava do lokáln´ı poboˇcky V´ıce podrobnost´ı ke vˇsem tˇemto variantám lze nalézt v knize Introduction to logistics systems planning and control [4].

20

´ 2.2. Ulohy celoˇ c´ıseln´ eho programov´ an´ı Celoˇc´ıselné programován´ı se vyznaˇcuje t´ım, ˇze jedna nebo v´ıce promˇenn´ ych je celoˇc´ıselného charakteru, ˇci speciálnˇe binárn´ıho charakteru. Matematickou formulac´ı u ´lohy celoˇc´ıselného lineárn´ıho programován´ı ve standardn´ım tvaru rozum´ıme n X X min{ cj x j | aij xj = bi , i = 1, . . . , m, xj ≥ 0, j = 1, . . . , n, xj ∈ M, j ∈ JM } j=1

kde cj , bi , aij ∈ R jsou konstantn´ı koeficienty u ´lohy a xj ∈ R jsou neznámé promˇenné u ´lohy. Konkrétnˇe pak m˚ uˇzeme rozliˇsit u ´lohy: • Integer Program (IP) – jedná se o typ lineárn´ıho programován´ı, kde vˇsechny promˇenné maj´ı celoˇc´ıseln´ y charakter: M = Z, JM = {1, . . . , n} • Mixed Integer Program (MIP) – jedná se o typ lineárn´ıho programován´ı, kde nˇekteré promˇenné maj´ı celoˇc´ıseln´ y charakter: M = Z, JM ⊂ {1, . . . , n} • Binary Integer Program (BIP) – jedná se o speciáln´ı typ celoˇc´ıselného programován´ı, kde promˇenné maj´ı binárn´ı charakter, tedy jsou rovny bud’ 0 nebo 1: M = {0, 1}, JM = {1, . . . , n} Této skuteˇcnosti se pak vyuˇz´ıvá pˇri zadán´ı mnoha u ´loh s dopravn´ı tématikou. Reálnˇe totiˇz plat´ı, ˇze m˚ uˇzeme vˇzdy vypravit celoˇc´ıselné násobky vlak˚ u nebo letadel. Problematiku lze tedy vyuˇz´ıt pˇri: Pl´ anov´ an´ı j´ızdn´ıch ˇ r´ ad˚ u vlak˚ u Pro dan´ y plán trat’ové s´ıtˇe v´ıme, ˇze odjezdy a pˇr´ıjezdy vlak˚ u do námi urˇcen´ ych stanic se maj´ı opakovat po urˇcitém ˇcasovém odstupu. Napˇr´ıklad ze stanice A má vyj´ıˇzdˇet aspoˇ n jeden vlak kaˇzdou hodinu. Vzdálenosti mezi jednotliv´ ymi stanicemi v s´ıti známe, stejnˇe tak ˇcas potˇrebn´ y k pˇrekonán´ı této vzdálenosti. Plat´ı zároveˇ n podm´ınka, ˇze dva vlaky jedouc´ı po sobˇe na dané trati mus´ı m´ıt nˇejak´ y námi dan´ y ˇcasov´ y rozestup. Pro pasaˇzéry mus´ı zase ˇreˇsen´ı umoˇznit pˇrestup z jedné vlakové linky na druhou a poskytnout jim dostatek ´ ˇcasu pro tento pˇrestup. Ukolem pak je naj´ıt takov´ y plán pˇrepravy, aby vyhovoval vˇsem tˇemto podm´ınkám. [13] Pl´ anov´ an´ı pohybu leteck´ ych pos´ adek Pro dan´ y pravideln´ y plán let˚ u pro dan´ y typ letadla je tˇreba naj´ıt pravideln´ y plán let˚ u pro posádku. Kaˇzd´ y den mus´ı b´ yt kaˇzdá posádka pˇriˇrazena k letu na jedné, ˇci v´ıce linkách, které zároveˇ n mus´ı splˇ novat letov´ y plán dle zájmu zákazn´ık˚ u na dané trase letˇet. Zároveˇ n je poˇzadováno, aby jednotlivé linky na sebe navazovaly, aby byl nejkratˇs´ı ˇcas pˇreletu a aby se letadla zbyteˇcnˇe nezdrˇzovala na letiˇsti z d˚ uvod˚ u tax. Hledáme tedy minimum vynaloˇzen´ ych prostˇredk˚ u na posádky letadel, coˇz je funkc´ı ˇcasu letu letadla, délky pracovn´ı doby a pauz mezi lety letadla. Zároveˇ n ale mus´ıme minimalizovat i letové ˇcasy a letiˇstn´ı taxy. [13]

21

Pl´ anov´ an´ı let˚ u na letiˇ sti Jedná se o podobn´ y problém jako plánován´ı pohybu leteck´ ych posádek, ale tentokrát ze strany letiˇstn´ıho personálu. Na základˇe pˇr´ıchoz´ıch let˚ u je tˇreba rozhodnout, které letadlo kam pˇristavit, aby pasaˇzéˇri mohli mezi letadly pˇrestoupit a aby mˇeli dostateˇcn´ y ˇcas na pˇrestup. To vˇse s minimalizac´ı náklad˚ u a nehodovosti na letiˇsti. [13] Z pˇredchoz´ıho popisu celoˇc´ıselného programován´ı by se mohlo zdát, ˇze se jedná o velmi podobnou u ´lohu, jako je lineárn´ı programován´ı. Bohuˇzel pouh´ ym zaokrouhlen´ım v´ ysledk˚ u z lineárn´ıho programován´ı se nedostaneme k optimáln´ımu ˇreˇsen´ı celoˇc´ıselného programován´ı. Je tedy tˇreba pouˇz´ıt jiné ˇreˇsiˇce, neˇz v pˇr´ıpadˇe lineárn´ıho programován´ı. Tuto problematiku podrobnˇe rozeb´ırá kniha [13], kde lze nalézt mnoho pˇr´ıklad˚ u z celoˇc´ıselného programován´ı a technik ˇreˇsen´ı tohoto typu u ´loh. Dále se budeme zab´ yvat pouze konkrétn´ı u ´lohou v oblasti dopravy a vysvˇetl´ıme si základn´ı formulaci u ´lohy celoˇc´ıselného programován´ı a v´ yznam jednotliv´ ych podm´ınek.

2.2.1. Model probl´ emu obchodn´ıho cestuj´ıc´ıho Problém obchodn´ıho cestuj´ıc´ıho budeme ˇreˇsit na grafu, kter´ y bude symetrick´ y a formulujeme jej jako metodu celoˇc´ıselného programován´ı následovnˇe: minimalizuj

n X n X

cij xij

i=1 j=1

xij ∈ {0, 1} n X

xij = 1,

i = 0, 1, . . . , n

xij = 1,

j = 0, 1, . . . , n

i=1 n X j=1

XX

xij ≥ 1 pro S ⊂ N, S 6= ∅

i∈S j ∈S /

ˇ ıslo cij urˇcuje cenu V tomto modelu jsou opˇet cij koeficienty cenové matice C. C´ pˇrepravy z mˇesta i do mˇesta j. Pokud je graf symetrick´ y, pak je i matice C symetrická. Matice X je binárn´ı matice, která urˇcuje poˇrad´ı mˇest, která budou navˇst´ıvena. Plat´ı pro ni: 1 pokud cesta z mˇesta i do mˇesta j leˇz´ı v trase obchodn´ıho cestuj´ıc´ıho xij = 0 jinak Ze zápisu jednoduˇse vypl´ yvá podm´ınka, ˇze souˇcet v kaˇzdém ˇrádku a v kaˇzdém sloupci je jedna, nebot’ z kaˇzdého a do kaˇzdého mˇesta vede právˇe jedna cesta. Jedná se vlastnˇe o speciáln´ı pˇr´ıpad dˇr´ıve probrané dopravn´ı u ´lohy 2.1.1, tzv. pˇriˇrazovac´ı problém, kdy z kaˇzdého z n mˇest pˇrepravujeme co nejlevnˇeji jednotková mnoˇzstv´ı zboˇz´ı do jednoho ze zb´ yvaj´ıc´ıch n − 1 mˇest. Zdá se tedy, ˇze by k vyˇreˇsen´ı mohlo staˇcit lineárn´ı programován´ı. Tato specifikace ale k vyˇreˇsen´ı u ´lohy jeˇstˇe nestaˇc´ı. Posledn´ı podm´ınka zaruˇcuje, ˇze nebudou 22

Obrázek 2.3: Pˇr´ıklad jedné souvislé trasy × vznik dvou subcykl˚ u vznikat tzv. lokáln´ı smyˇcky, ale vytvoˇr´ı se jeden velk´ y cyklus obsahuj´ıc´ı vˇsechna mˇesta, jak ukazuje obrázek 2.3. Hledan´ ym ˇreˇsen´ım je pak to ˇreˇsen´ı s minimáln´ı ohodnocenou trasou. Zadán´ı vypadá tedy pomˇernˇe jednoduˇse. Jaká je ovˇsem nároˇcnost a rozsáhlost této u ´lohy? M˚ uˇzeme zaˇc´ıt v libovolném mˇestˇe z n mˇest a z nˇej máme n − 1 moˇznost´ı jak pokraˇcovat dál. Pro dalˇs´ı mˇesto uˇz to bude n − 2 moˇznost´ı a tak dále. V koneˇcném d˚ usledku tedy máme (n − 1)! moˇzn´ ych ˇreˇsen´ı. Pro malá n je tedy problém dobˇre ˇreˇsiteln´ y, ale pro rozsáhlejˇs´ı u ´lohy nároˇcnost ne´ umˇernˇe roste. Pro lepˇs´ı pˇredstavu na naˇsem modelu máme 73 okresn´ıch mˇest. To je pˇribliˇznˇe 4, 47 · 10105 moˇznost´ı cest, které splˇ nuj´ı vˇsechny v´ yˇse urˇcené podm´ınky modelu. Odtud je jiˇz jasnˇe vidˇet, ˇze nalezen´ım vˇsech moˇznost´ı a jejich tˇr´ıdˇen´ım rozhodnˇe nedosáhneme efektivn´ıho v´ ypoˇctu. Nav´ıc i pˇri dneˇsn´ım pokroku v oblasti poˇc´ıtaˇcov´ ych technologi´ı bychom mˇeli velké problémy s pamˇet´ı poˇc´ıtaˇce. S v´ yhodou jsem vyuˇzila jiˇz funkˇcn´ı ˇreˇsen´ı podobné u ´lohy, která je souˇca´st´ı knihovny ukázkov´ ych ˇreˇsen´ı programu GAMS. Programu tsp42, kter´ y p˚ uvodnˇe poˇc´ıtal optimáln´ı trasu skrz 42 nejvˇetˇs´ıch mˇest Spojen´ ych stát˚ u, jsem jako vstup poskytla data vˇsech okresn´ıch mˇest a vzdálenost´ı mezi nimi. Program funguje na principu ˇreˇsen´ı, které navrhli v roce 1954 autoˇri Dantzig, Fulkerson a Johnson. V jednoduchosti se jedná o dva kroky. Prvn´ım krokem je tzv. relaxace ˇreˇsen´ı, ve které se matice ˇreˇsen´ı X transponuje a seˇcte s p˚ uvodn´ı matic´ı X. X + XT = Y n P i=1

Pro lepˇs´ı pˇredstavu uvedeme jednoduch´ y pˇr´ıklad. Matice X1 a X2 odpov´ıdaj´ı podm´ınkám n P xij = 1 a xij = 1. X2 ovˇsem reprezentuje dvˇe uzavˇrené trasy, X1 tvoˇr´ı jednu j=1

uzavˇrenou trasu.    X1 =   

0 0 0 0 1

1 0 0 0 0

0 0 0 1 0

0 1 0 0 0

0 0 1 0 0





  ,  

  X2 =   

0 1 0 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1

0 0 1 0 0

     

Pokud dojde k souˇctu tˇechto matic s jejich traspozicemi, vzniknou nové matice Y1 a Y2 . Které budou symetrické a na diagonále nulové. Zab´ yváme se tedy pouze prvky pod diagonálou.     . . . . . . . . . .  1 . . . .   2 . . . .         0 0 . . . Y1 =  0 0 . . .  , Y2 =     0 1 1 . .   0 0 1 . .  1 0 0 0 . 0 0 1 1 . 23

Pak tedy reformulujeme prodm´ınky

n P i=1

X

xij = 1 na jedinou podm´ınku:

j=1

X

yij +

j, j
n P

xij = 1 a

yij = 2

i, i>j

T´ımto postupem z´ıskáme tzv. relaxované ˇreˇsen´ı, které program tsp42 spoˇcte. V´ ysledek zobraz´ıme pˇrevodem matice X do syntaxe LATEXu.

•

•• • •

• •• • • • • • • • • • • • • • • • • • • • • • • •

• • • • •

•

• •

•

•

• • •

•

• • •

• • • •

•

•

•

• • • • • • • • • • • • •

•

• • •

Obrázek 2.4: Relaxované ˇreˇsen´ı u ´lohy pomoc´ı programu GAMS Poté docház´ı k postupnému sdruˇzován´ı jednotliv´ ych subcykl˚ u tohoto ˇreˇsen´ı. Zároveˇ n mus´ıme kontrolovat, zda docház´ı ke splnˇen´ı dan´ ych podm´ınek pro ˇreˇsen´ı p˚ uvodn´ı u ´lohy. Podrobnˇeji jsou metody popsány pˇr´ımo v ˇclánku Solution of a Large-Scale TravelingSalesman Problem [2]. Program tsp42 z relaxovaného ˇreˇsen´ı postupn´ ym spojován´ım a optimalizován´ım jednotliv´ ych subcykl˚ u u ´lohu vyˇreˇs´ı a nalezne optimum. Toto optimum má celkovou délku trasy (po korekci zaokrouhlován´ı) 4095 km.

•

•• • •

• •• • • • • • • • • • • • • • • • • • • • • • • •

• • • • •

•

• •

•

•

• • •

•

•

• • • • •

• •

•

•

•

• • • • • • • • • • • • •

• • •

Obrázek 2.5: Optimum u ´lohy Délka ˇreˇseni je 4 095 km. Dalˇs´ı pˇr´ıstupy ˇreˇsen´ı u ´lohy TSP zaloˇzené na celoˇc´ıselném lineárn´ım programován´ı lze nalézt v knize [13] a jejich implementace v GAMSu najdeme v [3]. Dále se ale chci zab´ yvat efektivnˇejˇs´ımi algoritmy zaloˇzen´ ymi na teorii graf˚ u.

24

3. Teorie graf˚ u K dalˇs´ımu v´ ykladu je tˇreba definovat základn´ı pojmy z teorie graf˚ u pro lepˇs´ı pozdˇejˇs´ı orientaci v textu. Grafy pak lze velmi dobˇre vyuˇz´ıt k vytvoˇren´ı modelu mˇest a jejich vzájemn´ ych vzdálenost´ı a k názorné ukázce postupu jednotliv´ ych algoritm˚ u pro hledán´ı nejlepˇs´ıch tras obchodn´ıho cestuj´ıc´ıho.

3.1. Z´ akladn´ı pojmy Definice 3.1.1 Graf (obyˇcejn´ y ˇci jednoduch´ y neorientovan´ y graf) je uspoˇra´daná dvojice mnoˇzin G = (V, E), kde V je libovolná koneˇcná neprázdná mnoˇzina a E ⊆ 2V je libovolná mnoˇzina dvouprvkov´ ych podmnoˇzin mnoˇziny V . Mnoˇzinu V naz´ yváme mnoˇzinou vrchol˚ u a mnoˇzinu E mnoˇzinou hran. [6] Je nutno také poznamenat, ˇze jako neorientovan´ y graf lze interpretovat i symetrickou ireflexivn´ı relaci, kde hrany tvoˇr´ı právˇe dvojice prvk˚ u této relace. [6] Grafy specifikujeme bud’ v´ yˇctem vrchol˚ u a hran nebo obrázkem.

Obrázek 3.1: Pˇr´ıklad zobrazen´ı grafu Pro naˇsi u ´lohu budeme reprezentovat mˇesta vrcholy grafu a cesty mezi mˇesty hranami grafu. Definice 3.1.2 Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vycházej´ıc´ıch1 z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). [6] ˇta 3.1.3 Souˇcet stupˇ Ve n˚ u v grafu je vˇzdy sud´ y a roven dvojnásobku poˇctu hran. [6] D˚ ukaz této vˇety je triviáln´ı. Tuto vˇetu vˇsak o pár kapitol dále vhodnˇe vyuˇzijeme u aplikace Christofidesovy metody. Definice 3.1.4 Podgrafem grafu G rozum´ıme libovoln´ y graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), kter´ y má za hrany libovolnou podmnoˇzinu hran grafu G maj´ıc´ıch oba vrcholy ve V (H). P´ıˇseme H ⊆ G. [6] Definice 3.1.5 Isomorfismus graf˚ u G a H je bijektivn´ı (vzájemnˇe jednoznaˇcné) zobrazen´ı f : V (G) → V (H), pro které plat´ı, ˇze kaˇzdá dvojice vrchol˚ u u, v ∈ V (G) je spojená hranou v G právˇe tehdy, kdyˇz je dvojice f (u), f (v) spojená hranou v H. Grafy G a H jsou izomorfn´ı, pokud mezi nimi existuje isomorfismus. P´ıˇseme G ∼ = H. [6]

25

Obrázek 3.2: Pˇr´ıklad dvou isomorfn´ıch graf˚ u Isomorfismus nám v jednoduchosti ˇr´ıká, ˇze dva r˚ uznˇe nakreslené grafy o urˇcit´ ych vlastnostech jsou stejné“ a m˚ uˇzeme vˇsechny grafy dle této bijekce roztˇr´ıdit do tˇr´ıd, kde kaˇzdou ” tˇr´ıdu m˚ uˇze reprezentovat graf s urˇcit´ ymi dan´ ymi vlastnostmi. Tedy napˇr´ıklad dle obrázku jsou tyto dva grafy isomorfn´ı, tj. nezáleˇz´ı, jak graf kresl´ıme, kdyˇz zachováme vzájemné vlastnosti. Definice 3.1.6 Sledem délky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran v0 , e1 , v1 , e2 , v2 , . . . e1 , v0 ve které vˇzdy hrana ei má koncové vrcholy vi−1 , vi . [6] Definice 3.1.7 Tah je sled v grafu bez opakován´ı hran. Uzavˇ ren´ y tah je tahem, kter´ y konˇc´ı ve vrcholu, ve kterém zaˇcal. Otevˇ ren´ y tah je tahem, kter´ y konˇc´ı v jiném vrcholu, neˇz sám zaˇcal. [6] ˇ sen´ım Sledy a tahy nám pomohou lépe specifikovat trasu obchodn´ıho cestuj´ıc´ıho. Reˇ obchodn´ıho cestuj´ıc´ıho bude vˇzdy uzavˇren´ y tah v grafu mˇest a cest. Nyn´ı uˇz jen zb´ yvá definovat vzdálenost. Definice 3.1.8 Vzd´ alenost dG (u, v) dvou vrchol˚ u u, v v grafu G je dána délkou nejkratˇs´ıho sledu mezi u a v v G. Pokud sled mezi u, v neexistuje, definujeme vzdálenost dG (u, v) = ∞.[6] ˇta 3.1.9 Vzdálenost v grafech splˇ Ve nuje troj´ uheln´ıkovou nerovnost [6]: ∀u, v, w ∈ V (G)

:

dG (u, v) + dG (v, w) ≥ dG (u, w).

Definice 3.1.10 Souvisl´ y graf je takov´ y neorientovan´ y graf, v nˇemˇz plat´ı, ˇze pro kaˇzdé dva vrcholy x a y existuje alespoˇ n jedna cesta z x do y. Definice 3.1.11 V´ aˇ zen´ y graf je graf G spolu s ohodnocen´ım w hran reáln´ ymi ˇc´ısly w : E(G) → R. Kladnˇ e v´ aˇ zen´ y graf je dvojice (G, w) taková, ˇze w(e) > 0 pro vˇsechny hrany e.[6] Definice 3.1.12 V´ aˇ zen´ a vzd´ alenost. Mˇejme kladnˇe váˇzen´ y graf (G, w). Délkou váˇzeného sledu S = (v0 , e1 , v1 , e2 , v2 , . . . e1 , v0 ) v G mysl´ıme souˇcet: dw G (S) = w(e1 ) + w(e2 ) + · · · + w(en ). Váˇzenou vzdálenost´ı v (G, w) mezi dvˇema vrcholy u, v pak mysl´ıme w dw G (u, v) = min{dG (S) : S je sled s konci u, v} 1

Pozn. U hran v ˇceˇstinˇe ˇr´ık´ ame, ˇze vych´ az´ı z obou vrchol˚ u souˇcasnˇe.

26

Definice 3.1.13 Celkov´ ym ohodnocen´ım podgrafu rozum´ıme souˇcet ohodnocen´ı vˇsech jeho hran. T´ım jsme tedy definovali váˇzenou vzdálenost mezi vrcholy a délku váˇzeného sledu. Pˇri ˇreˇsen´ı u ´lohy obchodn´ıho cestuj´ıc´ıho se dle grafové terminologie snaˇz´ıme o uzavˇren´ y tah, kter´ y bude m´ıt minimáln´ı váˇzenou vzdálenost. Dále je tˇreba definovat strom a dalˇs´ı d˚ uleˇzité pojmy. Definice 3.1.14 Neorientovan´ y uzavˇ ren´ y tah v grafu G nazveme kruˇ znic´ı v grafu G. [10] Definice 3.1.15 Strom je jednoduch´ y souvisl´ y graf G bez kruˇznic. [6] D´ıky znalosti tˇechto pojm˚ u pak m˚ uˇzeme lépe pochopit kostru grafu a minimáln´ı kostru grafu. Definice 3.1.16 Kostrou souvislého grafu G je podgraf v G, kter´ y je sám stromem a obsahuje vˇsechny vrcholy grafu G. [6] Definice 3.1.17 Minim´ aln´ı kostrou souvislého váˇzeného grafu G definujeme jako takovou kostru grafu G, která má nejmenˇs´ı moˇzné celkové ohodnocen´ı. [6] Definice 3.1.18 P´ arov´ an´ı v grafu G je podmnoˇzina hran M ⊆ E(G) taková, ˇze ˇza´dné dvˇe hrany z M nesd´ılej´ı koncov´ y vrchol. [6] Definice 3.1.19 Minim´ aln´ı p´ arov´ an´ı ve váˇzeném grafu G je takové párován´ı, které má minimáln´ı celkové ohodnocen´ı. Definice 3.1.20 Perfektn´ı p´ arov´ an´ı ve váˇzeném grafu G je takové párován´ı, které pokryje vˇsechny vrcholy grafu G. Pojem minimáln´ı kostry grafu vyuˇzijeme v dalˇs´ıch kapitolách ke konstrukci ˇreˇsen´ı u ´lohy obchodn´ıho cestuj´ıc´ıho. Zároveˇ n také ke konstrukci vyuˇzijeme tzv. párován´ı v grafech.

27

3.2. Cykly v grafu Dalˇs´ı d˚ uleˇzitou kapitolou k pochopen´ı algoritm˚ u obchodn´ıho cestuj´ıc´ıho jsou cykly (uzavˇrené tahy) v grafech. Cyklus v grafu m˚ uˇze pˇredstavovat jednoduchou posloupnost pohybu zboˇz´ı mezi vrcholy pˇr´ıpadnˇe skrz dané hrany grafu. Tato tématika se jiˇz v minulosti aplikovala na nˇekteré dopravn´ı problémy a hry, proto si u této kapitoly dovol´ım nˇekolik historick´ ych poznámek.

3.2.1. Hamilton˚ uv cyklus Historie vzniku probl´ emu Hamiltonova u ´loha byla formulována poprvé W. R. Hamiltonem v roce 1857 [12]. Hamilton ji jako nápad prodal lond´ ynskému prodejci her, kter´ y z n´ı vyrobil dˇrevˇenou deskovou hru a t´ım problém rozˇs´ıˇril do celého svˇeta. Jednalo se o hru na dvanáctistˇenu, jehoˇz pláˇst’ se rozloˇzil do roviny a vytvoˇril se graf vrchol˚ u a hran dvanáctistˇenu. C´ılem je vˇsech 20 vrchol˚ u dvanáctistˇenu propojit tak, aby vznikl cyklus, kter´ y kaˇzd´ ym vrcholem projde právˇe jednou. Proto se této hˇre ˇr´ıkalo The Icosian game, tedy Hra na dvanáctistˇenu.

Obrázek 3.3: Graf hran a vrchol˚ u dvanáctistˇenu a jedno z moˇzn´ ych ˇreˇsen´ı u ´lohy

Obecn´ a definice Definice 3.2.1 Hamilton˚ uv cyklus v grafu G definujeme jako uzavˇren´ y tah, kter´ y kaˇzd´ y vrchol pˇri pr˚ uchodu grafem zahrne právˇe jednou. Graf, kter´ y obsahuje Hamilton˚ uv cyklus se naz´ yvá Hamiltonovsk´ y graf. Pokud se tedy budeme na u ´lohu obchodn´ıho cestuj´ıc´ıho d´ıvat jako na graf s mˇesty jako vrcholy a cestami jako hranami, pak Hamilton˚ uv cyklus je jedno z moˇzn´ ych ˇreˇsen´ı problému a cyklus s nejmenˇs´ım celkov´ ym ohodnocen´ım je optimáln´ım ˇreˇsen´ım této u ´lohy.

28

3.2.2. Euler˚ uv cyklus Historie vzniku probl´ emu Euler˚ uv cyklus byl poprvé ˇreˇsen Leonardem Eulerem, kdyˇz se roku 1736 pokouˇsel vyˇreˇsit ´ slavn´ y problém sedmi most˚ u mˇesta Královce. Ukolem bylo v mˇestˇe Královci (nyn´ı Kaliningradu) pˇrej´ıt vˇsech sedm most˚ u právˇe jednou. Právˇe Euler jako prvn´ı dokázal, ˇze tato u ´loha nemá ˇreˇsen´ı a proto nen´ı moˇzné mosty ˇzádn´ ym takov´ ym zp˚ usobem pˇrej´ıt. Právˇe po nˇem jsou proto grafy s danou vlastnost´ı pojmenovány. Mezi znám´ y pˇr´ıpad Eulerova cyklu patˇr´ı i kreslen´ı obrázku domeˇcku jedn´ım tahem.

Obrázek 3.4: Typick´ y pˇr´ıklad Eulerova cyklu na kreslen´ı domeˇcku jedn´ım tahem Obecn´ a definice Definice 3.2.2 Eulerovsk´ y cyklus v grafu je takov´ y tah, kter´ y kaˇzdou hranu grafu projde právˇe jednou. Pokud tedy vytvoˇr´ıme graf, kter´ y bude reprezentovat mˇesto, zp˚ usobem takov´ ym, ˇze vrcholy budou pˇredstavovat kˇriˇzovatky a hrany mezi nimi budou pˇredstavovat ulice mezi nimi, pak staˇc´ı naj´ıt v tomto grafu libovoln´ y Euler˚ uv cyklus a t´ım vyˇreˇs´ıme u ´lohu ˇc´ınského listonoˇse. Pro Eulerovy cykly plat´ı také nˇekolik znám´ ych zákonitost´ı, které dále v textu vyuˇzijeme. ˇta 3.2.3 Neorientovan´ Ve y graf je Eulerovsk´ y, je-li souvisl´ y a kaˇzd´ y jeho vrchol má sud´ y stupeˇ n. Euler˚ uv cyklus pak bude uzavˇren´ y tah. ˇta 3.2.4 Neorientovan´ Ve y graf je Eulerovsk´ y, je-li souvisl´ y a má-li právˇe dva vrcholy lichého stupnˇe. Euler˚ uv cyklus pak bude otevˇren´ y tah.

29

30

4. Heuristiky 4.1. V´ yznam heuristik Heuristiky jsou takové algoritmy, které poskytnou dostateˇcnˇe pˇresné ˇreˇsen´ı v rozumném v´ ypoˇcetn´ım ˇcase. Toto ˇreˇsen´ı nemus´ı b´ yt optimáln´ı, pˇresto je pˇri velk´ ych modelech v´ yhodné ˇ jej vyuˇz´ıt. Casto heuristik vyuˇz´ıváme i v pˇr´ıpadech, kdy neexistuje metoda nalezen´ı pˇresného ˇreˇsen´ı. V praxi jsou tyto metody velmi ˇcasto uˇz´ıvané a nˇekteré z nich nám dokonce zaruˇcuj´ı danou procentuáln´ı vzdálenost od optimáln´ıho ˇreˇsen´ı. [7]

4.2. Heuristiky pro u ´ lohu obchodn´ıho cestuj´ıc´ıho Heuristiky pro TSP jsou algoritmy, které po nalezen´ı ˇreˇsen´ı problému TSP jiˇz nijak toto ˇreˇsen´ı nezlepˇsuj´ı. Nejlepˇs´ı z tˇechto algoritm˚ u dokonce zaruˇcuj´ı, ˇze spoˇc´ıtaj´ı ˇreˇsen´ı, které se bude liˇsit maximálnˇe o 10–15 % od optimáln´ıho ˇreˇsen´ı. Nemus´ı b´ yt ovˇsem pravidlem, ˇze pro z´ıskán´ı nejlepˇs´ıho ˇreˇsen´ı mus´ıme pouˇz´ıt nejlepˇs´ı konstrukˇcn´ı algoritmus. Mnoho takto z´ıskan´ ych ˇreˇsen´ı lze zlepˇsovat pomoc´ı tzv. zlepˇsovac´ıch algoritm˚ u, které mohou b´ yt velmi v´ ykonné a mohou ˇreˇsen´ı posunout mnohem bl´ıˇze k optimu. V naˇsem modelu opˇet pˇredpokládáme, ˇze pro mnoˇzinu mˇest m˚ uˇzeme urˇcit graf cest, kter´ y bude u ´pln´ y a bude pro nˇej platit troj´ uheln´ıková nerovnost. Jednoduch´ y model mˇest a cest si lze prohlédnout na obrázku 4.1. Jednotlivé metody budou prezentovány napˇred pomoc´ı nˇekolika prvn´ıch krok˚ u právˇe na tomto modelu. Vlastn´ı programován´ı a v´ ypoˇcty pak byly provedeny v jazyce Python a za modelov´ y pˇr´ıklad mnoˇziny mˇest byla opˇet ˇ e republiky. vybrána b´ yvalá okresn´ı mˇesta Cesk´

Obrázek 4.1: Modelov´ y pˇr´ıklad mˇest a cest mezi nimi Typy tˇechto metod a jejich uplatnˇen´ı jsem studovala v rámci spolupráce s norskou univerzitou Molde University College. Z vlastn´ı zkuˇsenosti a studia literatury [13], [7] vid´ım, ˇze tyto metody jsou pouˇz´ıvány a mohou b´ yt ˇcasto velmi efektivn´ı pˇri hledán´ı ˇreˇsen´ı ˇ na velmi velk´ ych modelech. Casto se pouˇz´ıvaj´ı i v pˇr´ıpadech nestandardn´ıch doplˇ nuj´ıc´ıch podm´ınek ˇci v pˇr´ıpadˇe, ˇze budeme potˇrebovat flexibiln´ı model, pˇri kterém se podm´ınky mohou ˇsiroce mˇenit. V´ yhodou je také to, ˇze ˇreˇsen´ı si pomoc´ı bezplatného softwaru m˚ uˇzeme naprogramovat sami a nemus´ıme se spoléhat na ˇreˇsiˇce, pokud budeme u ´lohu ˇreˇsit pomoc´ı metod matematického programován´ı.

31

4.2.1. Metoda hled´ an´ı nejbliˇ zˇ s´ıho souseda Jedná se o nejjednoduˇsˇs´ı metodu hledán´ı ˇreˇsen´ı, která napadne témˇeˇr kaˇzdého. Algoritmus startuje v zadaném poˇca´teˇcn´ım vrcholu grafu (neboli v startovn´ım mˇestˇe). Z tohoto vrcholu tvoˇr´ıme sled a pˇridáváme do sledu dalˇs´ı hranu a vrchol tak, aby následuj´ıc´ı vrchol mˇel nejmenˇs´ı váˇzenou vzdálenost od vrcholu pˇredeˇslého. Podm´ınkou je, ˇze kaˇzd´ y vrchol mus´ı b´ yt pouˇz´ıt ve sledu právˇe jednou. Jinak ˇreˇceno zaˇcneme ve startovn´ım mˇestˇe a vˇzdy pˇridáme do posloupnosti jemu nejbliˇzˇs´ı mˇesto a postup opakujeme se zb´ yvaj´ıc´ımi mˇesty, dokud nenavˇst´ıv´ıme vˇsechna mˇesta právˇe jednou v celém grafu. Tento algoritmus bohuˇzel nijak nezaruˇcuje efektivnost ˇreˇsen´ı. Vˇetˇsinou neposkytuje dostateˇcnˇe dobrou aproximaci a je nutné jej zlepˇsovat dalˇs´ımi algoritmy. Nav´ıc nen´ı zcela jasné, které mˇesto by mˇelo b´ yt startovn´ı. Naˇstˇest´ı se jedná o pomˇernˇe jednoduchou techniku v´ ypoˇctu a proto nen´ı problém vypoˇc´ıtat v´ıce variant tras a po té vybrat tu nejvhodnˇejˇs´ı ze vˇsech. [8] Lepˇs´ı pˇredstavu postupu tohoto algoritmu doplˇ nuje obrázek.

Obrázek 4.2: Naznaˇcen´ı postupu ˇreˇsen´ı pomoc´ı metody nejbliˇzˇs´ıho souseda Základn´ı algoritmy bud uvádˇet dále v pseudokódu, kter´ y je obdobn´ y tomu, kter´ y se pˇri publikaci grafov´ ych algoritm˚ u obvykle pouˇz´ıvá. Algoritmus hled´ an´ı nejbliˇ zˇ s´ıho souseda Vstupem je seznam mˇest mesta a matice vzdálenost´ı dist. V´ ystupem je trasa tour. begin tour = [ ]; vychozi mesto = mesta(1); mesta.odeber(vychozi mesto); while length(mesta) > 0 nasledujici mesto = najdi nejblizsi mesto(vychozi mesto, mesta); tour.pridej(nasledujici mesto); mesta.odeber(vychozi mesto); end end

32

Konkr´ etn´ı ˇ reˇ sen´ı Tuto metodu jsem naprogramovala ve skriptovac´ım jazyce Python a analyzovala jsem ˇ sen´ı vˇsech model˚ jej´ı vlastnosti. Reˇ u jsem pak zobrazila pomoc´ı rozˇsiˇruj´ıc´ıho bal´ıku funkc´ı pro jazyk Python s názvem NumPy. Za data jsem si opˇet zvolila vˇsechna b´ yvalá okresn´ı ˇ mˇesta (tj. 73 uzl˚ u grafu) v Ceské republice, nebot’ se jedná o vˇetˇs´ı vzorek dat a bude lépe vidˇet variabilitu v závislosti na poˇcáteˇcn´ım zvolen´ı v´ ychoz´ıho mˇesta. Za vzdálenosti mezi mˇesty pouˇz´ıvám vzduˇsnou vzdálenost, která dobˇre aproximuje vzdálenosti skuteˇcné. Ze simulac´ı vypl´ yvá, ˇze obecnˇe nelze nijak urˇcit, které mˇesto by bylo pro zaˇcátek algoritmu nejvhodnˇejˇs´ı. Mezi mnou vypoˇcten´ ym nejlepˇs´ım a nejhorˇs´ım ˇreˇsen´ım je znaˇcn´ y rozd´ıl, kter´ y je po vykreslen´ı grafu zcela patrn´ y. T´ım se jen potvrzuje, ˇze tato metoda nen´ı vhodná pro koneˇcné ˇreˇsen´ı tohoto problému a bude tˇreba ˇreˇsen´ı dále posunout nˇejakou dalˇs´ı metodou bl´ıˇze k optimáln´ımu ˇreˇsen´ı. Konkrétnˇe pak pro m˚ uj pˇr´ıpad je nejlepˇs´ı aproximac´ı v´ ychoz´ı mˇesto Kol´ın a nejhorˇs´ı v´ ychoz´ı mˇesto Tachov. Z tohoto srovnán´ı by se mohlo zdát, ˇze okrajová mˇesta jsou na tom vˇzdy o trochu h˚ uˇre, obecnˇe se vˇsak toto tvrzen´ı simulacemi nepotvrdilo.

Obrázek 4.3: Nejlepˇs´ı ˇreˇsen´ı na okresn´ıch mˇestech Celková délka trasy = 4 508 km.

33

Obrázek 4.4: Nejhorˇs´ı ˇreˇsen´ı na okresn´ıch mˇestech Celková délka trasy = 5 266 km.

4.2.2. Metoda hladov´ eho algoritmu Tato metoda tvoˇr´ı cestu mezi mˇesty tak, ˇze utˇr´ıd´ı vˇsechny hrany grafu (cesty mezi mˇesty) dle velikosti. Vybere nejkratˇs´ı hranu a pokud tato hrana spln´ı podm´ınku, ˇze jej´ım pˇridán´ım nevznikne cyklus s ménˇe mˇesty neˇz je celkov´ y poˇcet mˇest a ˇze pˇridán´ım této hrany nevzroste u libovolného vrcholu (mˇesta) stupeˇ n vrcholu na v´ıce neˇz dva, pak je tato hrana pˇridána do cyklu. Poté se vyb´ırá nejmenˇs´ı hrana následuj´ıc´ı. Algoritmus se ukonˇc´ı po nalezen´ı cyklu se vˇsemi mˇesty. Postup algoritmu je podobn´ y Kruskalovu hladovému algoritmu, kter´ ym se budeme zab´ yvat u Christofidesovy metody. [8] Postup algoritmu lze dobˇre pochopit z ilustraˇcn´ıho obrázku 4.5, kter´ y navazuje na ˇ obrázek 4.1. C´ısla u jednotliv´ ych hran reprezentuj´ı poˇrad´ı pˇridán´ı hrany do cyklu.

Obrázek 4.5: V´ yvoj hladového algoritmu Tuto metodu jsem dále ˇza´dn´ ym zp˚ usobem nezpracovala ani neprogramovala.

34

4.2.3. Metoda vkl´ ad´ an´ı mˇ est do trasy Tato metoda je opˇet pomˇernˇe pˇr´ımá a má mnoho variant. Algoritmus naˇc´ıná na podmnoˇzinˇe vrchol˚ u (mˇest) a postupnˇe se k nim po jednom pˇridávaj´ı dalˇs´ı mˇesta. Poˇca´teˇcn´ı podmnoˇzinou je ˇcasto trojice ˇci dvojice vrchol˚ u. Princip metody spoˇc´ıvá v tom, ˇze v kaˇzdém kroku se snaˇz´ıme pˇridat dalˇs´ı vrchol do uzavˇreného tahu tak, aby pˇr´ır˚ ustek vzdálenosti, kter´ y vznikne pˇridán´ım tohoto vrcholu, byl minimáln´ı. Takto opakujeme, aˇz do uzavˇreného tahu pˇridáme vˇsechny vrcholy a vynikne nám tedy cyklus mˇest. Obrázek ilustruje nˇekolik prvn´ıch krok˚ u metody na modelovém pˇr´ıkladˇe, kde poˇca´teˇcn´ı podmnoˇzinou byly vybrány vrcholy grafu, které spojuje nejkratˇs´ı hrana. Poˇrad´ı u ˇsed´ ych hran naznaˇcuje postup celého algoritmu.

Obrázek 4.6: V´ yvoj metody vkládán´ı cest do trasy Tuto metodu jsem opˇet zpracovala ve skriptovac´ım jazyce Python a zobrazila pomoc´ı NumPy. V´ ysledem v´ ypoˇctu m˚ uˇzete vidˇet na obrázku n´ıˇze. Délkou trasy je metoda srovnatelná s metodou hledán´ı nejbliˇzˇs´ıho souseda.

ˇ Obrázek 4.7: Pouˇzit´ı metody vkládán´ı mˇest do trasy na b´ yval´ ych okresn´ıch mˇestech CR Celková délka trasy = 4 854 km.

35

4.2.4. Metoda dvojit´ e minim´ aln´ı kostry grafu Tato metoda patˇr´ı jiˇz mezi sofistikovanˇejˇs´ı metody. Základem je sestrojen´ı tzv. minimáln´ı kostry grafu. Jedná se o podgraf grafu, pro kter´ y plat´ı, ˇze mezi kaˇzd´ ymi dvˇema vrcholy lze naj´ıt spojnici a celkové ohodnocen´ı hran v tomto grafu bude minimáln´ı. Pˇri konstrukci tohoto podgrafu lze vyuˇz´ıt Kruskalova algoritmu. Postup tohoto algoritmu lze naj´ıt v pˇr´ıloze na konci práce.

ˇ Obrázek 4.8: Sestrojen´ı minimáln´ı kostry grafu na b´ yval´ ych okresn´ıch mˇestech CR Celková délka cest = 3 716 km. Metoda dvojité minimáln´ı kostry grafu pak spoˇc´ıvá pouze v dublován´ı kostry grafu. Tedy vytvoˇr´ıme novou mnoˇzinu a kaˇzdá hrana v minimáln´ı kostˇre grafu bude v námi novˇe vytvoˇrené mnoˇzinˇe hran obsaˇzena právˇe dvakrát. Na této mnoˇzinˇe hran pak lze sestrojit Euler˚ uv cyklus pouˇzit´ım vˇsech hran. Euler˚ uv cyklus pak jednoduˇse pˇrevedeme na Hamilton˚ uv. Procházen´ım Eulerova cyklu si postupnˇe zapisujeme navˇst´ıvené vrcholy a vrcholy, které se v seznamu budou opakovat vynecháme. T´ım vznikne Hamilton˚ uv cyklus, kde kaˇzd´ y vrchol navˇst´ıv´ıme právˇe jednou. [8] Tato metoda zaruˇcuje nejh˚ uˇre dvojnásobnˇe dlouhou dráhu oproti optimáln´ımu ˇreˇsen´ı, nebot’ plat´ı, ˇze kostra grafu bude m´ıt vˇzdy menˇs´ı celkové ohodnocen´ı trasy neˇz trasa optimáln´ı.

36

4.2.5. Christofidesova metoda Algoritmus Christofides je pojmenován podle Nicose Christofidese, kter´ y jako prvn´ı navrhl tento zp˚ usob v´ ypoˇctu. Vˇetˇsina heuristik garantuje nejhorˇs´ı v´ ysledek ve dvojnásobné v´ yˇsi oproti optimu (tedy nalezená trasa heuristikou je v nejhorˇs´ım pˇr´ıpadˇe dvakrát tak dlouhá neˇz optimáln´ı trasa). Nicos Christofides navrhl rozˇs´ıˇren´ı algoritmu tak, aby nejhorˇs´ı moˇzn´ y v´ ysledek mˇel v˚ uˇci optimu pomˇer 3/2 (tedy nejhorˇs´ı pˇr´ıpad nalezené trasy bude o polovinu delˇs´ı neˇz délka optimáln´ı trasy). Tento algoritmus je zároveˇ n i nejlepˇs´ım dosud znám´ ym algoritmem. [7] Vytvoˇr´ıme graf G = (V, E), kde vrcholy grafu budou námi navˇst´ıvená mˇesta a E budou hrany mezi nimi. Konstrukce trasy pak prob´ıhá následovnˇe: • vytvoˇr´ıme minimáln´ı kostru grafu G • vytvoˇr´ıme podmnoˇzinu vrchol˚ u C grafu, která obsahuje pouze vrcholy s lich´ ym stupnˇem • na mnoˇzinˇe C vytvoˇr´ıme minimáln´ı perfektn´ı párován´ı • hrany minimáln´ı kostry grafu a minimáln´ıho perfektn´ıho párován´ı sjednot´ıme do jedné mnoˇziny 1 • Z tohoto sjednocen´ı vytvoˇr´ıme Euler˚ uv cyklus • Euler˚ uv cyklus transformujeme na Hamilton˚ uv cyklus [7] Nyn´ı s v´ yhodou vyuˇzijeme pojm˚ u vysvˇetlen´ ych v kapitole 3. Je d˚ uleˇzité si uvˇedomit, ˇze Euler˚ uv cyklus sestroj´ıme v takto upraveném podgrafu vˇzdy. Po konstrukci minimáln´ı kostry grafu vyb´ıráme právˇe vrcholy s lich´ ym stupnˇem, které nám brán´ı v konstrukci Eulerova cyklu. Ty pak d´ıky minimáln´ımu párován´ı a sjednocen´ı budou m´ıt vˇsechny sud´ y stupeˇ n. Z vˇety 3.2.3 ale v´ıme, ˇze lze sestrojit Euler˚ uv cyklus. Pˇrevod Eulerova cyklu na Hamilton˚ uv pak vytvoˇr´ıme jednoduˇse tak, ˇze utvoˇr´ıme posloupnost po sobˇe jdouc´ıch vrchol˚ u v Eulerovˇe cyklu a opakuj´ıc´ı se vrcholy vynecháme. T´ım vznikne Hamilton˚ uv cyklus na vˇsech vrcholech grafu G. Tuto metodu jsem opˇet zpracovala ve skriptovac´ım jazyce Python. Na grafu jsem vytvoˇrila minimáln´ı kostru grafu pomoc´ı hladového algoritmu (viz pˇr´ılohy práce). Po té jsem urˇcila vrcholy grafu s lich´ ym poˇctem stupˇ n˚ u a na nich provedla minimáln´ı pseudopárován´ı. Vzhledem k pokroˇcilé tématice pro algoritmy na minimáln´ı perfektn´ı párován´ı v grafech jsem se rozhodla pro zjednoduˇsen´ y algoritmus, kter´ y na tˇechto bodech vytvoˇr´ı tzv. pseudopárován´ı. Algoritmus funguje tak, ˇze setˇr´ıd´ı hrany mezi vybran´ ymi mˇesty dle velikosti a vybere nejkratˇs´ı hranu. Poté tyto dva jiˇz spojené vrcholy odstran´ı a opˇet zb´ yvaj´ıc´ı hrany setˇr´ıd´ı a vybere nejkratˇs´ı z nich. Takto pokraˇcuje, aˇz spáruje vˇsechny mˇesta. Tento problém jsem ˇreˇsila i pomoc´ı program˚ u, které vytvoˇr´ı minimáln´ı párován´ı na mnou dané mnoˇzinˇe vrchol˚ u s lich´ ym stupnˇem. Ukázalo se, ˇze mnou navrˇzen´ y algoritmus generuje pro ˇ mnou navrˇzen´ y pˇr´ıklad 73 okresn´ıch mˇest v Ceské republice stejné ˇreˇsen´ı, jako algoritmus urˇcuj´ıc´ı minimáln´ı párován´ı. Tyto dvˇe mnoˇziny jsem po té sjednotila a vytvoˇrila Euler˚ uv 1

Zde je nutno poznamenat, ˇze pokud bude libovolná hrana zastoupena v obou podmnoˇzinách, pak je nutné ji ve sjednocen´ı poˇc´ıtat jako objekt, kter´ y se v této mnoˇzinˇe vyskytne dvakrát. Coˇz je bohuˇzel i ˇc´ asteˇcné poruˇsen´ı definice grafu. Tuto konstrukci je nutné provést, abychom v dalˇs´ım kroku mohli sestrojit Euler˚ uv cyklus.

37

cyklus. Ten jsem pak jednoduch´ ym zp˚ usobem transformovala na Hamilton˚ uv cyklus, a t´ım jsem z´ıskala Christofidesovo ˇreˇsen´ı.

Obrázek 4.9: Minimáln´ı kostra grafu a pseudominimáln´ı párovan´ı Celková délka cest = 4 753 km.

ˇ sen´ı motodou Christofides Obrázek 4.10: Reˇ Celková délka trasy = 4 271 km.

38

4.3. Algoritmy pro zlepˇ sen´ı vlastnost´ı trasy obchodn´ıho cestuj´ıc´ıho V pˇredchoz´ım textu jsme shrnuli nˇekolik metod, jak spoˇc´ıtat ˇreˇsen´ı problému obchodn´ıho cestuj´ıc´ıho s dostateˇcnˇe dobrou aproximac´ı od optimáln´ı trasy. Dále je nutno uvést, ˇze tyto algoritmy mohou b´ yt u ´ˇcinné, ale stále je tu mnohdy moˇznost posunout dané nalezené pˇribliˇzné ˇreˇsen´ı jeˇstˇe v´ıce k ˇreˇsen´ı optimáln´ımu. Vzniká tedy nová tˇr´ıda algoritm˚ u, které na vstupu dostanou jiˇz nˇejaké libovolnˇe nalezené pˇribliˇzné ˇreˇsen´ı problému obchodn´ıho cestuj´ıc´ıho a dále jej pouze pˇribliˇzuj´ı k optimu a trasu jako takovou jiˇz nekonstruuj´ı. Z tˇechto algoritm˚ u lze vybrat od jednoduch´ ych a rychl´ ych aˇz po sofistikované a velmi efektivn´ı. Pak má tento pˇr´ıstup v´ yhodu tedy i v tom, ˇze lze libovolnˇe kombinovat konstrukˇcn´ı a zlepˇsuj´ıc´ı heuristiky a tedy i na daném problému pouˇz´ıt danou nejvhodnˇejˇs´ı kombinaci metod. Tyto metody jsem studovala i v rámci spolupráce s norskou univerzitou Molde University College pˇri ˇreˇsen´ı u ´kol˚ u projektu, na kterém jsem se mohla pod´ılet. Z vlastn´ı zkuˇsenosti tedy v´ım, ˇze ˇrada tˇechto metod (pˇredevˇs´ım pokroˇcilejˇs´ıch) se pouˇz´ıvá v praxi a velmi dobˇre funguje i na velk´ ych modelech, které by v pˇr´ıpadˇe celoˇc´ıselného lineárn´ıho programován´ı stály podstatnˇe v´ıce v´ ypoˇcetn´ıho ˇcasu.

4.3.1. 2-optim´ aln´ı algoritmus Jedn´ım z prvn´ıch algoritm˚ u je tzv. 2-optimáln´ı algoritmus, kter´ y jako jeden z prvn´ıch 2 navrhl G. A. Croes jiˇz v roce 1958 . Tento algoritmus stav´ı na jednoduché metodˇe zámˇeny dvou cest v celkové trase a testován´ı, zda je ohodnocen´ı novˇe vytvoˇrené trasy menˇs´ı, neˇz ohodnocen´ı trasy p˚ uvodn´ı. Názornˇe je moˇzno si tuto metodu pˇredstavit na obrázku 4.11. Tato metoda je pomˇernˇe jednoduchá a rychlá, a proto se jej´ı pouˇzit´ı doporuˇcuje témˇeˇr vˇzdy. Laicky lze ˇr´ıci, ˇze po aplikován´ı tohoto algoritmu vznikne kolem mˇest tzv. bublina. Tedy z grafického pohledu, kde vˇsechny cesty budou znázornˇeny jako u ´seˇcky, které budou proporcionálnˇe odpov´ıdat své vzdálenosti mezi mˇesty, se cesty nemohou kˇr´ıˇzit a budou obep´ınat mˇesta ve formˇe jedné velké zdeformované bubliny. Nejlépe je tento efekt vidˇet na následuj´ıc´ıch aplikac´ıch, pˇredevˇs´ım na obrázku 4.12.

Obrázek 4.11: Schéma 2-optimáln´ıho algoritmu Metodu lze konkrétnˇe velmi dobˇre pochopit na algoritmu zapsaném na dalˇs´ı stranˇe textu. Trasu obchodn´ıho cestuj´ıc´ıho reprezentujeme jednotliv´ ymi body, poskládan´ ymi za sebou v posloupnosti, v poˇrad´ı, v jakém jsou navˇst´ıveny. Tuto poˇca´teˇcn´ı posloupnost 2

G. A. CROES (1958). A method for solving traveling salesman problems.

39

nazveme initial tour, pozdˇeji ve v´ ypoˇctu jiˇz jen promˇennou tour. Vstupem do algoritmu je zároveˇ n matice vzdálenost´ı mezi mˇesty dist, kde dist(i, j) znaˇc´ı vzdálenost mezi mˇestem i a j. Pokud bude distanˇcn´ı matice dist symetrická, pak je zˇrejmˇe i problém obchodn´ıho cestuj´ıc´ıho symetrick´ y. Nutno k tomuto algoritmu jeˇstˇe podotknout jednu specifikaci. Pokud bude vybráno mˇesto i = 1, pak by algoritmus pˇri v´ ypoˇctu distanˇcn´ı matice vybral mˇesto v promˇenné tour(0). To se m˚ uˇze zdánlivˇe zdát jako chyba algoritmu, proto definuji tour(0) jako stejné mˇesto na konci pole, tedy tour(a). Tento zdánliv´ y nesoulad nepˇredstavuje v praxi problém, ’ nebot ˇrada jazyk˚ u má takto i nˇekterá pole implementována a je vhodné je tedy pouˇz´ıt. Mé vlastn´ı ˇreˇsen´ı v jazyce Python této v´ yhody pˇr´ımo vyuˇz´ıvá. Algoritmus pro nalezen´ı 2-optim´ aln´ı cesty Vstupem je vygenerovaná poˇcáteˇcn´ı trasa initial tour a matice vzdálenost´ı dist. V´ ystupem je trasa tour, která je 2-optimáln´ı. begin tour := initial tour; a := length(tour); tour1 := [ ]; while tour1 !=tour Pokud tour1 == tour, pak je cyklus 2-optimáln´ı. tour1 := tour for i := 1 to a step 1 do for j := 1 to a step 1 do u := dist(tour(i), tour(i − 1)) + dist(tour(j), tour(j − 1)); Délka dvou cest, které se maj´ı zamˇenit v := dist(tour(i), tour(j)) + dist(tour(i − 1), tour(j − 1)); Délka dvou cest u zamˇenˇené varianty if u > v tour := tour.zamen mezi mesty(i, j); Funkce zmˇen´ı smˇer pr˚ uchodu mezi mˇesty i a j end end end end end

Tento algoritmus lze s v´ yhodou jeˇstˇe vylepˇsit. Staˇc´ı si povˇsimnout, ˇze v pˇr´ıpadˇe, kdy je zmˇena trasy v´ yhodná, mus´ı platit, ˇze délka jedné ze zamˇenˇen´ ych hran mus´ı b´ yt kratˇs´ı neˇz délka p˚ uvodn´ı nezamˇenˇené hrany. Lze tedy vytvoˇrit dvˇe jednoduˇsˇs´ı podm´ınky a udˇelat pˇr´ıpadnou zámˇenu aˇz v pˇr´ıpadˇe, ˇze algoritmus spln´ı alespoˇ n jednu z nich. Této v´ yhody jsem také vyuˇzila a aplikovala ji na sv˚ uj v´ ypoˇcet v programovac´ım jazyce Python. Samotn´ y zdrojov´ y kód je moˇzno shlédnout na pˇriloˇzeném CD. Metodu jsem aplikovala na jiˇz dˇr´ıve vypoˇctené varianty poˇca´teˇcn´ıch tras obchodn´ıho cestuj´ıc´ıho. Na obrázc´ıch si lze vˇsimnout jiˇz dˇr´ıve zmiˇ novaného tzv. bublinového efektu, tedy nekˇriˇzen´ı cest. 40

Z tˇechto v´ ypoˇct˚ u jasnˇe vypl´ yvá, ˇze rozd´ıl mezi nejhorˇs´ım a nejlepˇs´ım ˇreˇsen´ım Metody nejbliˇzˇs´ıho souseda po aplikován´ı 2-optimáln´ıho algoritmu je témˇeˇr setˇren. P˚ uvodn´ı rozd´ıl témˇeˇr 760 kilometr˚ u byl d´ıky aplikaci 2-optimáln´ıho algoritmu sn´ıˇzen na zhruba 207 kilometr˚ u. Pozdˇeji v textu uvid´ıme, ˇze tento rozd´ıl lze jeˇstˇe v´ıce sn´ıˇzit.

41

Obrázek 4.12: Pouˇzit´ı 2-optimáln´ı metody na jednotlivá poˇca´teˇcn´ı ˇreˇsen´ı.

42

4.3.2. 3-optim´ aln´ı algoritmus Tento algoritmus je velmi podobn´ y 2-optimáln´ımu algoritmu. Jedinou zmˇenou je to, ˇze m´ısto dvou cest jsou zamˇenˇeny cesty tˇri. Algoritmus je u ´ˇcinnˇejˇs´ı, co se t´ yˇce zlepˇsen´ı trasy a pˇribl´ıˇzen´ı se optimu. Na druhou stranu je o nˇeco nároˇcnˇejˇs´ı, neˇz 2-optimáln´ı algoritmus. Moˇznosti pˇrepnut´ı hran reprezentuje obrázek 4.13. Moˇznosti pˇrepnut´ı hran jsou pouze dvˇe. Druhou variantu je moˇzné rotovat na cyklu, ale jedná se principiálnˇe o stejnou zmˇenu.

Obrázek 4.13: Schéma 3-optimáln´ıho algoritmu Algoritmus pro vytvoˇren´ı 3-optimáln´ı cesty je opˇet uveden v pseudokódu. Vstupem do algoritmu je opˇet libovolnˇe zvolená poˇcáteˇcn´ı trasa initial tour a matice vzdálenost´ı v grafu dist. Algoritmus vybere vˇsechny kombinace trojic, které lze zamˇenit a spoˇc´ıtá pro nˇe jak p˚ uvodn´ı, tak zamˇenˇenou délku trasy. Tyto délky tras seˇrad´ı dle velikosti a najde tedy nejv´ yhodnˇejˇs´ı variantu. Pokud je jedna ze zámˇen v´ yhodnˇejˇs´ı, pak ji provede. Je nutné si povˇsimnout, ˇze zde mus´ıme poˇc´ıtat se dvˇema variantami zámˇeny mˇest tour.zamen mezi mesty1(i, j, k) a tour.zamen mezi mesty2(i, j, k), nebot’ se jedná o dvˇe r˚ uzné zámˇeny a u jedné z nich se smˇer pr˚ uchodu ani v jedné ˇcásti cyklu nezmˇen´ı (prvn´ı varianta zámˇeny) a u druhé se mˇen´ı poˇrad´ı mˇest i smˇer pr˚ uchodu v alespoˇ n jedné ˇca´sti cyklu. Tuto metodu lze zefektivnit t´ım, ˇze nebude procházet vˇsechny trojice mˇest, ale opakuj´ıc´ı se trojice bude vynechávat, takˇze cyklem projde jen pˇribliˇznˇe ˇsestina moˇznost´ı. To je ale vykoupeno dalˇs´ım testován´ım tras, protoˇze jiˇz nebude zahrnuta druhá varianta zmˇeny trasy obecnˇe a je tˇreba ji testovat na vˇsechny druhy rotovan´ ych variant. Pˇresto tato metoda urychl´ı v´ ypoˇcet alespoˇ n ˇca´steˇcnˇe. Algoritmus 3-opt jsem v modifikované verzi naprogramovala v programovac´ım jazyce Python a pouˇzila na trasy jiˇz dˇr´ıve spoˇc´ıtané heuristikami. Verzi algoritmu lze naj´ıt na pˇriloˇzeném CD na zadn´ıch deskách práce.

43

Algoritmus pro nalezen´ı 3-optim´ aln´ı cesty Vstupem je vygenerovaná poˇcáteˇcn´ı trasa initial tour a matice vzdálenost´ı dist. V´ ystupem je trasa tour, která je 3-optimáln´ı. begin tour := initial tour; a := length(tour); tour1 := [ ]; while tour1 !=tour Pokud tour1 == tour, pak je cyklus 2-optimáln´ı. tour1 := tour for i := 1 to a step 1 do for j := 1 to a step 1 do for k := 1 to a step 1 do u := dist(tour(i), tour(i − 1)) + dist(tour(j), tour(j − 1)) +dist(tour(k), tour(k − 1)); Délka tˇr´ı cest, které se maj´ı zamˇenit. v := dist(tour(i − 1), tour(j)) + dist(tour(i), tour(g − 1)) +dist(tour(k), tour(j − 1)); Prvn´ı ze zmˇen dle obrázku 4.13 w := dist(tour(i − 1), tour(j − 1)) + dist(tour(i), tour(k − 1)) +dist(tour(j), tour(k)); Jedna z rotovan´ ych zámˇen obrázku 4.13 nejvyhodnejsi varianta := sort(u, v, w) if nejvyhodnejsi varianta(1) = v tour := tour.zamen mezi mesty(i, j, k); Funkce zmˇen´ı smˇer pr˚ uchodu mezi mˇesty i, j a k dle prvn´ıho pˇrepnut´ı end if nejvyhodnejsi varianta(1) = w tour := tour.zamen mezi mesty2(i, j, k); Funkce zmˇen´ı smˇer pr˚ uchodu mezi mˇesty i, j a k dle druhého pˇrepnut´ı end end end end end end

44

45

Obrázek 4.14: Pouˇzit´ı 3-optimáln´ı metody na jednotlivá poˇca´teˇcn´ı ˇreˇsen´ı.

4.3.3. k-optim´ aln´ı algoritmus Nen´ı nutné konˇcit s v´ ypoˇcty na 3-optimáln´ım algoritmu a lze s touto technikou doj´ıt jeˇstˇe dál. Lze pokraˇcovat od 4-optimáln´ıho algoritmu aˇz k k-optimáln´ımu algoritmu. Tyto algoritmy ale spotˇrebuj´ı mnohem v´ıce v´ ypoˇcetn´ıho ˇcasu, a pˇri stále menˇs´ım efektu na zlepˇsen´ı celkové délky trasy k-optimáln´ıho algoritmu oproti k − 1-optimáln´ımu algoritmu. Tyto metody se proto neaplikuj´ı pro a > 4 a pro 4-optimáln´ı se pouˇz´ıvá vˇetˇsinou jen konstrukce tzv. pˇrekˇr´ıˇzen´ ych most˚ u (anglicky: the crossing bridges) [8]. Tuto konstrukci m˚ uˇzeme shlédnout na obr. 4.15.

Obrázek 4.15: Schéma metody crossing bridges Tuto metodu jsem jiˇz neimplementovala a nemohu tedy posoudit, jako moc je u ´ˇcinná. V´ıce informac´ı k tomuto tématu lze z´ıskat v ˇclánku autora K. Helsgaun, “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic”.

46

5. Porovn´ an´ı v´ ysledk˚ u testov´ an´ı metod V pˇredchoz´ıch kapitolách byly popsány nˇekteré metody pro ˇreˇsen´ı u ´lohy obchodn´ıho cestuj´ıc´ıho. D˚ uleˇzit´ ym dalˇs´ım krokem je tedy srovnán´ı u ´ˇcinnosti tˇechto metod mezi sebou a vyvozen´ı závˇeru o vhodnosti pouˇzit´ı. Tyto závˇery budou vyvozeny z modelového ˇ e republiky. pˇr´ıkladu okresn´ıch mˇest Cesk´

ˇ V´ ysledky na modelu okresn´ıch mˇ est Cesk´ e republiky Pro dan´ y model byly provedeny vˇsechny moˇzné kombinace dosud popsan´ ych ˇreˇsen´ı. V´ yvoj tˇechto ˇreˇsen´ı byl zanesen do grafu 5.1, kter´ y znázorˇ nuje poˇcáteˇcn´ı aproximaci optimáln´ıho ˇreˇsen´ı a dále aplikac´ı 2-optimáln´ıho a 3-optimáln´ıho algoritmu. Na svislé ose grafu je znázornˇena celková délka nalezené trasy pro danou metodu. Na vodorovné ose je znázornˇen postup jednotliv´ ych aplikac´ı k-optimáln´ıch algoritm˚ u, pˇriˇcemˇz ˇc´ıslo 1 reprezentuje p˚ uvodn´ı metodu, která nalezne aproximaci cesty, ˇc´ıslo 2 reprezentuje 2-optimáln´ı algoritmus a ˇc´ıslo 3 pak 3-optimáln´ı algoritmus. Pro kaˇzdou lomenou ˇcáru v grafu tedy plat´ı, ˇze prvn´ı hodnota reprezentuje ˇreˇsen´ı dané heuristiky, druhá pak aplikaci 2-optimáln´ıho algoritmu na toto dané ˇreˇsen´ı a tˇret´ı hodnota urˇcuje délku trasy po aplikaci 3-optimáln´ıho ˇreˇsen´ı na danou p˚ uvodn´ı metodu. Graf se m˚ uˇze zdát nepˇrehledn´ y mnoˇzstv´ım ˇcar, proto jsou nˇekteré z nich odliˇseny tlouˇst’kou ˇca´ry. Nen´ı zde d˚ uleˇzitá ani tak hodnota daného ˇreˇsen´ı, ale vztah a v´ yvoj ˇreˇsen´ı. Pozorované charakteristiky jsou tedy sp´ıˇse kvantitativn´ı. Barevné oznaˇcen´ı jednotliv´ ych metod v grafu je pak zvoleno takto: • Metody nejbliˇzˇs´ıho souseda jsou znázornˇeny nejtenˇc´ımi liniemi. Jsou zde zobrazeny vˇsechny poˇca´teˇcn´ı aproximace, které závisej´ı na startovn´ım mˇestˇe. • Metoda vkládán´ı mˇest do trasy je zaznaˇcena tmavˇe modrou tlustou ˇcarou. • Christofidesova metoda je znázornˇena tmavˇe ˇcervenou tlustou ˇcarou. • Optimáln´ı ˇreˇsen´ı spoˇc´ıtané pomoc´ı programu GAMS je znázornˇeno tmavˇe zelenou tlustou ˇcarou. Optimáln´ı ˇreˇsen´ı je v grafu konstantn´ı a urˇcuje tedy hranici, ke které se vˇsechna ostatn´ı ˇreˇsen´ı postupnou aplikac´ı k-optimáln´ıch metod bl´ıˇz´ı. Ze sklonu jednotliv´ ych pˇr´ımek je patrné, jak moc se ˇreˇsen´ı danou metodou zlepˇs´ı a pˇribl´ıˇz´ı se optimáln´ımu. Pro p˚ uvodn´ı metody vid´ıme, ˇze nejlepˇs´ı aproximac´ı optimáln´ıho ˇreˇsen´ı je v naˇsem pˇr´ıpadˇe skuteˇcnˇe Christofidesova metoda, zat´ımco soubor aproximac´ı metodou nejbliˇzˇs´ıho souseda tvoˇr´ı mnohem horˇs´ı odhady od optimáln´ı metody. Metoda vkládán´ı mˇest do trasy má také odhad trasy podobn´ y odhad˚ um metod nejbliˇzˇs´ıho souseda. Po aplikaci 2-optimáln´ıho algoritmu je ale v grafu vidˇet velké zlepˇsen´ı pro metodu nejbliˇzˇs´ıho souseda a zároveˇ n pouze malé zlepˇsen´ı Christofidesovy metody. Metody nejbliˇzˇs´ıho souseda se jiˇz pˇribl´ıˇzily odhadu Christofidesovy metody. Pˇri aplikaci 3-optimáln´ıho ˇreˇsen´ı na dané p˚ uvodn´ı metody je pak zcela evidentn´ı srovnatelnost jednotliv´ ych metod. 47

Obrázek 5.1: Graf v´ ysledk˚ u

48

Christofidesova metoda po aplikaci 3-optimáln´ıho algoritmu se dostává sv´ ym ohodnocen´ım cesty mezi pr˚ umˇer metod nejbliˇzˇs´ıho souseda s 3-optimáln´ım algoritmem. P˚ uvodn´ı metoda vkládán´ı cest do trasy s 3-optimáln´ım algoritmem dokonce pˇredˇcila Christofidesovu metodu. Nejlepˇs´ı aproximaci pak poskytla metoda nejbliˇzˇs´ıho souseda, která se svoj´ı p˚ uvodn´ı aproximac´ı zaˇradila mezi pr˚ umˇerné. Zdánlivˇe ideáln´ı pouˇzit´ı celoˇc´ıselného lineárn´ıho programován´ı v rozsáhlejˇs´ıch u ´lohách je pˇr´ıliˇs ˇcasovˇe nároˇcné. Celkovˇe tedy vzniká srovnán´ı jednotliv´ ych metod a vhodnost jejich pouˇzit´ı. Protoˇze k-optimáln´ı algoritmy jsou pomˇerné jednoduché na teorii a programován´ı, ale pomˇernˇe nároˇcné na v´ ypoˇcetn´ı ˇcas, hod´ı se v kombinaci s jednoduˇsˇs´ımi poˇcáteˇcn´ımi aproximacemi optimáln´ıho ˇreˇsen´ı pro menˇs´ı u ´lohy, které vyˇreˇs´ı s dostateˇcnˇe dobr´ ym odhadem, jenˇz je srovnateln´ y s pouˇzit´ım Christofidesovy metody. Plat´ı tedy: ´ Ulohy o menˇ s´ım rozsahu je vhodn´ e ˇ reˇ sit jednoduˇ sˇ s´ımi metodami v kombinaci s k -optim´ aln´ımi algoritmy Christofidesova metoda je naopak nároˇcnˇejˇs´ı na teorii a správné naprogramován´ı. Po té pracuje velmi efektivnˇe a s mnohem menˇs´ım objemem v´ ypoˇct˚ u. Hod´ı se proto pro rozsáhlejˇs´ı u ´lohy, které vyuˇzij´ı jej´ı sofistikovanˇejˇs´ı pˇr´ıstup a vyuˇzij´ı efektivnˇe poskytnut´ y v´ ypoˇcetn´ı ˇcas. Plat´ı tedy: ´ Ulohy o vˇ etˇ s´ım rozsahu je vhodn´ eˇ reˇ sit sofistikovanˇ ejˇ s´ımi metodami (napˇ r. Christofidesovou metodou)

49

50

6. Pokroˇ cil´ e algoritmy a modely 6.1. Pokroˇ cil´ e algoritmy V praxi se ovˇsem pouˇz´ıvaj´ı i pokroˇcilejˇs´ı algoritmy neˇz k-optimáln´ı. Podrobnˇe se jimi v textu zab´ yvat jiˇz nebudeme, pˇresto si dovol´ım letmo zm´ınit nˇekolik z nich, protoˇze pˇredstavuj´ı smˇery, ve kter´ ych je moˇzné na moji práci dále navázat. Tabu-Search Jedná se o meta-heuristiku, která dokáˇze potlaˇcit neduhy metody nejbliˇzˇs´ıho souseda. Problém u metody nejbliˇzˇs´ıho souseda je ten, ˇze ˇcasto ˇreˇsen´ı skonˇc´ı v lokáln´ım optimu a stávaj´ıc´ı algoritmy jiˇz nemaj´ı moˇznost posunout ˇreˇsen´ı bl´ıˇze k optimu. Tomu se m˚ uˇzeme vyhnout pouˇzit´ım právˇe metody Tabu-Search. Tato metoda totiˇz povoluje v pr˚ ubˇehu v´ yvoje ˇreˇsen´ı konat i nev´ yhodné zmˇeny trasy a t´ım je schopna se vymanit z lokáln´ıch optim. Aby ovˇsem nedocházelo k cyklickému v´ yvoji ˇreˇsen´ı a znehodnocen´ı algoritmu, jsou pˇredchoz´ı kroky v postupu ˇreˇsen´ı uchovávány v tzv. tabu-listu a algoritmus se k nim za dan´ ych podm´ınek nesm´ı vrátit. Odtud pak plyne název metody Tabu-Search, nebot’ nˇekteré zmˇeny v ˇreˇsen´ı jsou pro algoritmus tabu. [8] Simulated Annealing V ˇceském jazyce také tzv. simulované ˇz´ıhán´ı. Jedná se o pravdˇepodobnostn´ı optimalizaˇcn´ı metodu zaloˇzenou na simulaci ˇz´ıhán´ı oceli. Metoda se opˇet snaˇz´ı vymanit z lokáln´ıch minim a vytváˇr´ı náhodné prohledáván´ı daného okol´ı aktuáln´ıho ˇreˇsen´ı. Pokud nalezne lepˇs´ı ˇreˇsen´ı, pak pˇrepne do tohoto ˇreˇsen´ı. Právˇe umoˇznˇen´ı zhorˇsen´ı ˇreˇsen´ı má za následek, ˇze algoritmus neuv´ızne v lokáln´ım minimu. Pˇri kaˇzdém posunu se prohledávané okol´ı zmenˇsuje, aby se splnil poˇzadavek konvergence algoritmu. [8] Ant Colony Optimization Optimalizace pomoc´ı metody mravenˇc´ı kolonie pˇredstavuje pomˇernˇe nov´ y pˇr´ıstup k ˇreˇsen´ı této problematiky, kter´ y souvis´ı pˇredevˇs´ım s rozvojem poˇc´ıtaˇcové techniky. Princip této metody vycház´ı z chován´ı koloni´ı hmyzu. D´ıky aplikován´ı jednoduch´ ych pravidel pro jedince vzniká komplexn´ı chován´ı decentralizovaného systému jedinc˚ u jako celku. Jsou tedy v rámci metody implementován´ı tzv. umˇel´ı mravenci, kteˇr´ı umˇej´ı mezi sebou kooperovat, ˇr´ıdit se podle tzv. feromonové stopy a pomoc´ı tˇechto feromonov´ ych stop spolu komunikovat. Takto vytvoˇrené spoleˇcenstv´ı pak procház´ı námi vytvoˇren´ y graf. Postupem ˇcasu se cesty, kudy procház´ı jednotlivci ustál´ı na ˇreˇsen´ı v´ yhodném pro celou kolonii. T´ım se nalezne nˇejaké lokáln´ı minimum. [8]

6.2. Vehicle routing problem Zdálo by se, ˇze problém obchodn´ıho cestuj´ıc´ıho je u ´zce specializovan´ y problém, kter´ y v praxi uˇz moc vyuˇzit´ı nenalezne. Naˇstˇest´ı opak je pravdou a vˇsechny poznatky z chován´ı této u ´lohy lze uplatnit jako pod´ ulohu dalˇs´ıch rozsáhlejˇs´ıch u ´loh. Tˇemito u ´lohami jsou právˇe VRP. V plném anglickém názvu Vehicle Routing Problems. V ˇceském jazyce se s pˇrekladem v odborné literatuˇre témˇeˇr nesetkáme. Název lze pˇreloˇzit jako problémy pˇrepravy s v´ıce vozidly (dále oznaˇc´ıme jako VRP). VRP je rozˇs´ıˇren´ım u ´lohy obchodn´ıho cestuj´ıc´ıho a v praxi je velmi vyuˇz´ıvaná.

51

Obrázek 6.1: Princip VRP. [11] Mˇejme ukázkové mˇesto, které reprezentujeme grafem G = (V, E) tak, ˇze vrcholy V reprezentuj´ı zákazn´ıky, kter´ ym mus´ıme dodat urˇcit´ y typ zboˇz´ı, nebo depa, kde máme zaparkovány dopravn´ı prostˇredky pro pˇrepravu. Hrany E grafu reprezentuj´ı cesty mezi zákazn´ıky a depy. Zároveˇ n m˚ uˇze platit pro urˇcitou podmnoˇzinu hran F ⊆ E, ˇze právˇe tyto hrany mus´ıme ve svém ˇreˇsen´ı pouˇz´ıt. Depa jsou pak takové vrcholy grafu G, ˇze pro kaˇzd´ y takov´ y vrchol definujeme mi vozidel, které jsou v daném depu k dispozici. Pokud zde existuje podmnoˇzina hran F , pak takto zvolenou mnoˇzinou vˇetˇsinou modelujeme vˇetˇs´ı mnoˇzstv´ı zákazn´ık˚ u, kteˇr´ı s´ıdl´ı v nˇejaké dostateˇcnˇe kompaktn´ı oblasti. Dobr´ ym pˇr´ıkladem m˚ uˇze b´ yt rozvoz poˇsty ˇci odvoz domovn´ıho odpadu z jedné konkrétn´ı ulice. [4] Vˇetˇsinou vˇsak takto sloˇzitou u ´lohu neˇreˇs´ıme. Pokud nemáme definovanou podmnoˇzinu hran F , pak se u ´loha zjednoduˇs´ı na Node routing problem (tedy u ´lohu ˇreˇs´ıc´ı pˇrepravu s v´ıce vozidly jen mezi jednotliv´ ymi zákazn´ıky jako vrcholy grafu). Pokud na druhou stranu ˇreˇs´ıme pouze problém s podmnoˇzinou F a v grafu neexistuj´ı ˇza´dn´ı dalˇs´ı zákazn´ıci, kteˇr´ı jsou reprezentováni vrcholy v grafu, pak takovéto u ´loze ˇr´ıkáme Arc routing problem. V praxi se uplatˇ nuje napˇr´ıklad pˇri sváˇzen´ı odpadu v ulic´ıch mˇesta. Snadno vid´ıme, ˇze u ´loha obchodn´ıho cestuj´ıc´ıho je speciáln´ı pˇr´ıpadem u ´lohy VRP, kdy máme k dispozici pouze jedno vozidlo v jednom depu a zákazn´ıky reprezentujeme jako ´ vrcholy v grafu. Ulohu ˇc´ınského listonoˇse zase m˚ uˇze pˇredstavovat speciáln´ı pˇr´ıpad VRP, kdy máme k dispozici pouze jedno vozidlo v jednom depu a snaˇz´ıme se obslouˇzit zákazn´ıky reprezentované pouze hranami E v grafu. Dalˇs´ımi dodateˇcn´ ymi zpˇresˇ nuj´ıc´ımi podm´ınkami pro definován´ı modelu mohou b´ yt napˇr´ıklad podm´ınky: • mnoˇzstv´ı vozidel mi nemus´ı b´ yt fixn´ı, m˚ uˇze b´ yt nastavena pouze horn´ı hranice vozidel k dispozici • celkov´ y náklad vozidla bˇehem cesty nesm´ı pˇrekroˇcit danou kapacitu vozidla • doba cesty vozidla nesm´ı pˇrekroˇcit zvolen´ y ˇcasov´ y limit pro danou smˇenu ˇridiˇce vozidla 52

• zákazn´ıci si pˇrej´ı b´ yt obslouˇzeni v pˇredem dan´ ych ˇcasov´ ych intervalech (v angl. time windows) • nˇekteˇr´ı zákazn´ıci mus´ı b´ yt obslouˇzeni dan´ ym typem vozidla Pokud nastav´ıme podm´ınky pˇr´ıliˇs omezuj´ıc´ı, pak se m˚ uˇze stát, ˇze ˇreˇsen´ı u ´lohy ani nebude existovat, nebot’ jej i nevhodnˇe zvolená podm´ınka m˚ uˇze zcela vyˇsachovat ze hry. VRP b´ yvaj´ı ˇcasto velmi komplexn´ı u ´lohou, proto se u tˇechto u ´loh se jiˇz projev´ı v´ yhoda heuristik, protoˇze je lze aplikovat efektivnˇe na m´ıru danému konkrétn´ımu problému a obdrˇzet tak dobré ˇreˇsen´ı v krátkém ˇcase. Tyto metody jsou podrobnˇe a prakticky popsány v knize [4].

53

54

7. Z´ avˇ er Má práce shrnuje základn´ı problematiku modelován´ı dopravn´ıch u ´loh. D˚ uraz je kladen na formulaci a ˇreˇsen´ı u ´lohy obchodn´ıho cestuj´ıc´ıho, a to jak pomoc´ı celoˇc´ıselného ˇreˇsen´ı, tak pˇredevˇs´ım pomoc´ı grafov´ ych algoritm˚ u a jejich modifikac´ı. Vu ´vodu se zab´ yvám motivac´ı, aplikacemi a základn´ımi pojmy z této problematiky. Vzhledem k velké variabilitˇe pˇr´ıstup˚ u k modelován´ı a ˇreˇsen´ı r˚ uzn´ ych dopravn´ıch u ´loh jsem práci rozdˇelila na d´ılˇc´ı celky. Nejprve se zab´ yvám lineárn´ım programován´ım a jeho aplikac´ı na jednoduch´ y dopravn´ı ˇ e republice. Na tomto pˇr´ıkladu jsou demonstrovány problém v rámci zásobován´ı v Cesk´ základn´ı principy sestavován´ı modelu a základn´ı uˇzit´ı programu GAMS a tabulkového kalkulátoru MS Excel. Dále se zab´ yvám celoˇc´ıseln´ ym programován´ım a ˇreˇsen´ım problému obchodn´ıho cesˇ e republiky pomoc´ı protuj´ıc´ıho na vlastn´ım vytvoˇreném modelu okresn´ıch mˇest Cesk´ gramu GAMS. V´ ysledek tˇechto metod poté slouˇz´ı k referenˇcn´ımu porovnán´ı s efektivitou v´ ypoˇctu v dalˇs´ı ˇcásti práce. V druhé ˇca´sti práce se vˇenuji ˇreˇsen´ım u ´lohy obchodn´ıho cestuj´ıc´ıho pomoc´ı heuristik, tedy algoritm˚ u, které spoˇc´ıtaj´ı dostateˇcnˇe dobré ˇreˇsen´ı, které ovˇsem nemus´ı b´ yt optimem u ´lohy. Pro lepˇs´ı pochopen´ı teorie jsem zaˇradila pˇred samotn´ y v´ yklad metod kapitolu vˇenuj´ıc´ı se základ˚ um teorie graf˚ u, kde jsem vysvˇetlila základn´ı pojmy potˇrebné k pochopen´ı dalˇs´ıch algoritm˚ u. Dále uvád´ım nˇekolik pˇr´ıklad˚ u heuristik a jejich aplikaci na mnou ˇ vytvoˇren´ y model okresn´ıch mˇest Ceské republiky. Následuje v´ yklad a aplikace zlepˇsuj´ıc´ıch algoritm˚ u na ˇreˇsen´ı spoˇc´ıtané p˚ uvodn´ımi heuristikami. Vˇsechny algoritmy jsem implementovala v rámci jazyka Python a vˇsechna takto z´ıskaná ˇreˇsen´ı a jejich v´ yvoj v pr˚ ubˇehu aplikace zlepˇsuj´ıc´ıch algoritm˚ u jsou zanesena do grafu 5.1. V pˇredposledn´ı kapitole porovnávám v´ ysledky v´ ypoˇct˚ u, jejich vlastnosti a efektivitu jednotliv´ ych metod. V posledn´ı kapitole pak nastiˇ nuji moˇznost dalˇs´ıho v´ yvoje v rámci rozˇsiˇrován´ı sloˇzitosti u tˇechto u ´loh.

55

56

Literatura ˇ a republika: seˇsitový atlas pro základn´ı ˇskoly a v´ıceletá gymnázia. 1. vyd. Praha: [1] Cesk´ Kartografie Praha, 2006, 32 s. ISBN 80-701-1870-9. [2] DANTZIG, G B, FULKERSON, and JOHNSON. Solution of a Large-Scale TravelingSalesman Problem. Journal of the Operations Research Society of America, 1954, 393–410 s. [3] GAMS Model library [online]. 2012 [cit. 2012-03-25]. Dostupné z: http://www.gams. com/modlib/libhtml/alfindx.htm [4] GHIANI, Gianpaolo, Gilbert LAPORTE a Roberto MUSMANNO. Introduction to logistics systems planning and control. Hoboken, NJ, USA: J. Wiley, c2004, 352 s. ISBN 04-708-4917-7. [5] GEORGIA INSTITUTE OF TECHNOLOGY. The Traveling Salesman Problem Website [online]. 2012 [cit. 2012-03-25]. Dostupné z: http://www.tsp.gatech.edu/ ˇ Y. ´ P. Základy teorie graf˚ [6] HLINEN u: pro (nejen) informatiky [online]. [cit. 2012-04-01]. Dostupné z: http://is.muni.cz/el/1433/podzim2011/MA010/um/Grafy-text11. pdf?lang=cs [7] CHRISTOFIDES, Nicos. Graph theory: an algorithmic approach. New York: Academic Press, 1975, 400 s. ISBN 01-217-4350-0. [8] NILSSON, C. Heuristics for the traveling salesman problem. Tech. Report, Linköping University, Sweden, 2003. [cit. 2012-03-09]. Dostupné z: http://www.ida.liu.se/ ~TDDB19/reports_2003/htsp.pdf [9] POPELA, P. Optimalizaˇcn´ı modely. (pˇrednáˇsky) Brno: VUT, FSI, zimn´ı semestr akademického roku 2010/2011. ˇ [10] SEDA, M. Teorie graf˚ u[online]. [Skripta pro 5. roˇcn´ık studia.] Brno: VUT, FSI, 2003. [cit. 2012-03-09]. Dostupné z: http://www.uai.fme.vutbr.cz/~mseda/TG03_ MS.pdf [11] TU Dortmund, PG 534: Vehicle Routing. In: [online]. [cit. 2012-05-20]. Dostupné z: http://ls11-www.cs.uni-dortmund.de/people/chimani/VehicleRouting/ [12] Wolfram MathWorld [online]. [cit. 2012-05-20]. Dostupné z: http://mathworld. wolfram.com/ [13] WOLSEY, Laurence A. Integer programming. New York: John Wiley, 1998, 264 s. ISBN 04-712-8366-5.

57

58

8. Pˇ r´ılohy 8.1. Minim´ aln´ı kostra grafu Kruskal˚ uv hladov´ y algoritmus funguje na jednoduchém principu. Setˇr´ıd´ı vˇsechny hrany grafu dle velikosti a poté vytváˇr´ı podgraf grafu tak, ˇze pˇridá danou v poˇrad´ı nejmenˇs´ı hranu do grafu tehdy, pokud jej´ım pˇridán´ım nevzniká ˇzádn´ y cyklus v grafu. Pak pˇrejde na dalˇs´ı nejmenˇs´ı hranu v poˇrad´ı. Tento cyklus je ukonˇcen po vytvoˇren´ı kostry grafu. Tedy jak´ ymkoliv dalˇs´ım pˇridán´ım hrany vznikne v grafu cyklus. Kruskal˚ uv algoritmus pro nalezen´ı minim´ aln´ı kostry grafu. Vstupem je seznam mˇest mesta, hran mezi nimi cesty a matice vzdálenost´ı dist. y obsahuje vybrané cesty. V´ ystupem je grafov´ y strom min strom, kter´ begin min strom= [ ] for n ∈ mesta vytvor mnozinu(n) Pro kaˇzdé mˇesto vytvoˇr´ı samostatnou mnoˇzinu. end cesty.sort(dist) Setˇr´ıd´ı cesty dle matice vzdálenosti dist for n := 1 to length(cesty) a = cesty(n); if mnozina(a.vychozi mesto) ! = mnozina(a.koncove mesto) Pokud jsou mnoˇziny obsahuj´ıc´ı poˇcáteˇcn´ı a koncové mˇesto disjunktn´ı, pak vloˇz´ı hranu do kostry grafu. min strom.pridej(a) end end end

8.2. Algoritmus pro minim´ aln´ı p´ arov´ an´ı v grafu Z d˚ uvodu velké sloˇzitosti pˇri hledán´ı minimáln´ıho párován´ı v grafu jsem navrhla vlastn´ı alespoˇ n pˇribliˇzné ˇreˇsen´ı tohoto párován´ı. Algoritmus pracuje na principu podobném, jako Kruskal˚ uv algoritmus. Hrany grafu setˇr´ıd´ıme podle velikosti. Vˇzdy vybereme nejmenˇs´ı hranu a pˇridáme ji do mnoˇziny hran podgrafu párován´ı. Poté odstran´ıme vˇsechny hrany, které vycházej´ı z mˇest, které jsme v pˇredchoz´ım kroku napárovali a opˇet pokraˇcujeme v minimáln´ım párován´ı, tentokráte s N − 2 mˇesty.

59

Algoritmus pro pseudop´ arov´ an´ı v grafu Vstupem je seznam hran mezi mˇesty cesty, seznam mˇest mesta a matice vzdálenost´ı dist. V´ ystupem je mnoˇzina hran min match, která obsahuje vybrané cesty. begin min match= [ ] cesty.sort(dist) Setˇr´ıd´ı cesty dle matice vzdálenosti dist for n := 1 to length(length(mesta)/2) min match.pridej(cesty(1)); Pˇridá danou nejkratˇs´ı cestu do podgrafu a = cesty(1) cesty.odstran(a.mesto1); cesty.odstran(a.mesto2); Pˇr´ıkaz, kter´ y odstran´ı vˇsechny hrany vycházej´ıc´ı z mˇest dané pˇridané hrany. end end

8.3. Seznam pˇ r´ıloh na CD Data jsou rozdˇelena do ˇctyˇr adresáˇr˚ u podle pˇr´ısluˇsn´ ych kapitol v textu. • 1. Linearni programovani – Priklad linearniho programovani.xls – ˇreˇsen´ y pˇr´ıklad v programu MS Excel y pˇr´ıklad v programu GAMS – Priklad linearniho programovani.gms – ˇreˇsen´ • 2. Celociselne programovane – 1.Vypocet optima pomoci tsp42.gms – program a data v GAMSu, kter´ y poˇc´ıtá ˇreˇsen´ı problému obchodn´ıho cestuj´ıc´ıho – 2.Prevod reseni do LaTeXu.gms – program, kter´ y zobraz´ı ˇreˇsen´ı do LATEXu • 3. Heuristiky – 1.Heuristiky pro tsp.py – vˇsechny potˇrebné skripty pro realizaci heuristik • 4. Data pro porovnani metod – 1.Urceni polohy mest.xls – tabulka urˇcuj´ıc´ı pˇrepoˇcet polohy mˇest pro moˇ e republiky del okresn´ıch mˇest Cesk´ – 2.Matice vzdalenosti.xls – tabulka s matic´ı vzdálenosti mezi vˇsemi mˇesty – 3.Vysledky metod pro porovnani.xls - v´ ysledky vˇsech variant algoritm˚ ua jejich zobrazen´ı do grafu 5.1

60

FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV MATEMATIKY

Recommend Documents