Optimalizace cest ve skladu Optimal routes in a storehouse

ˇ – Technicka´ univerzita Ostrava VSB Fakulta elektrotechniky a informatiky Katedra aplikovane´ matematiky

Optimalizace cest ve skladu Optimal routes in a storehouse

2012

Adam Silber

Velice dˇekuji vedouc´ımu mé diplomové práce Mgr. Petru Kovárˇ ovi, Ph.D. za jeho rady, návrhy a pˇripom´ınky, které mi vyraznˇ e pomohly a za cˇ as, ktery´ mi v ´ ˚ ehu psan´ı práce vˇenoval. Také dˇekuji panu Janu Korponaiovi, ktery´ se nám prubˇ vˇenoval pˇri naˇs´ı návˇstˇevˇe skladu, a s kterym ´ jsme problém konzultovali prostˇred˚ nictv´ım emailu. Dˇekuji také mym rodiˇ c um, kteˇr´ı mˇe bˇehem studia trpˇelivˇe pod´ porovali.

Abstrakt Tato diplomová práce se zabyv´ ´ a rˇ eˇsen´ım reálného problému, optimalizovat cestu ¨ vysokozdviˇzného voz´ıku ve skladu, problém byl zadany´ firmou Molnlycke He´ celem zefektivnˇen´ı kompletace objednávek. Zadany´ problém lze alth Care za uˇ pˇreformulovat jako problém obchodn´ıho cestuj´ıc´ıho a v práci je následnˇe rˇ eˇsen ˚ Konkrétn´ı rˇ eˇsen´ı potom vycház´ı z Christofipomoc´ı aproximaˇcn´ıch algoritmu. dova algoritmu. Práce demonstruje moˇznou spolupráci akademické obce se soukromym ´ sektorem. ˇ a´ slova: optimalizace skladu, problém obchodn´ıho cestuj´ıc´ıho, ChristoKl´ıcov ˚ algoritmus fiduv

Abstract ¨ This thesis deals with the problem of finding optimal routes in a Molnlycke Health Care’s storehouse. The problem is similar to the traveling salesman problem and it is solved using approximation algorithms. For the solution we modiffy the Christofides algorithm. This thesis also shows possibility of cooperation between university and industry. Keywords: warehouse optimization, storehouse, travelling salesman problem, Christofides algorithm

Seznam pouˇzitych ´ zkratek a symbolu˚ G(V, E) V (G) E(G) T SP

– Graf G s mnoˇzinou vrcholu˚ V a mnoˇzinou hran E – Mnoˇzina vrcholu˚ gragu G – Mnoˇzina hran gragu G – Problém obchodn´ıho cestuj´ıc´ıho

1

Obsah 1

´ Uvod

3

2

Zformulován´ı problému 2.1 Souˇcasny´ stav . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Následuj´ıc´ı postup . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6

3

Definice a pojmy z teorie grafu˚

8

4

Problém obchodn´ıho cestuj´ıc´ıho 4.1 Problém obchodn´ıho cestuj´ıc´ıho v metrickém prostoru . . . . . . . 4.2 Heuristické algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . .

15 17 19

5

Teoreticky´ rozbor 5.1 Minimáln´ı kostra grafu . . . . . . . . . ´ 5.2 Minimáln´ı upln´ e párován´ı . . . . . . . 5.3 Eulerovsky´ tah . . . . . . . . . . . . . . 5.4 Teoreticky´ pohled na zadany´ problém

. . . .

20 20 21 22 23

6

Optimalizace 6.1 Implementace Algoritmu . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27 27 39

7

Závˇer

41

8

Literatura

43

9

Neveˇrejná cˇ a´ st

44

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2

´ u˚ Seznam obrazk 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Cesta kolem svˇeta . . . . . . . . . . . . . . . . . . . . . . . . . Pˇr´ıklad jednoduchého grafu G . . . . . . . . . . . . . . . . . Pˇr´ıklad multigrafu . . . . . . . . . . . . . . . . . . . . . . . . Stupnˇe vrcholu˚ grafu G . . . . . . . . . . . . . . . . . . . . . . Kompletn´ı grafy K4 a K9 . . . . . . . . . . . . . . . . . . . . . Cykly C3 a C8 . . . . . . . . . . . . . . . . . . . . . . . . . . . Graf G a jeho kostra K. . . . . . . . . . . . . . . . . . . . . . . Pˇr´ıklad ohodnocen´ı hran grafu. . . . . . . . . . . . . . . . . . Minimáln´ı kostra. . . . . . . . . . . . . . . . . . . . . . . . . . ´ Minimáln´ı upln´ e párován´ı. . . . . . . . . . . . . . . . . . . . . Mapa soutˇezˇ e . . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace Christofidova algoritmu. . . . . . . . . . . . . . . . ˚ algoritmus . . . . . . . . . . . . . . . . . . . . . . Kruskaluv ˚ algoritmus . . . . . . . . . . . . . . . . . . . . . . . . Jarn´ıkuv Zjednoduˇseny´ graf popisuj´ıc´ı situaci ve skladu. . . . . . . . . c Obrázek grafu reprezentuj´ıc´ı sklad v programu MATLAB ⃝ Pˇr´ıklad diskutabiln´ıho rˇ eˇsen´ı . . . . . . . . . . . . . . . . . . ´ Nalezené rˇ eˇsen´ı po upravˇ e. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

3 8 9 10 11 12 12 13 14 14 16 19 21 22 26 28 37 38

3

´ 1 Uvod Optimalizaˇcn´ı problém, problém nalezen´ı nejlepˇs´ıho ze vˇsech pˇr´ıpustnych ´ rˇ eˇsen´ı, je cˇ asto formulován jako hledán´ı minima ceny, pouˇzitého materiálu nebo energie. V této diplomové práci se budeme zabyvat hledán´ım minimáln´ı, nejkratˇs´ı trasy, ´ která mus´ı obsahovat urˇcité povinné zastávky. ¨ Zadán´ı diplomové práce vzniklo na zˇ a´ dost firmy Molnlycke Health Care Kli¨ nipro, resp. jej´ıho zamˇestnance Jana Korponaie. Molnlycke Health Care je pˇredn´ı ˚ vyrobk svˇetovy´ dodavatel jednorázovych u˚ pro hojen´ı ´ chirurgickych ´ prostˇredku, ´ ran a sluˇzeb pro zdravotnictv´ı. Firma vyráb´ı a skladuje zdravotnicky´ materiál. ˚ e zákazn´ıky, je nutné jednotlivé kompoBˇehem kompletace objednávek pro ruzn´ nenty z objednávky posb´ırat a svézt ze skladu na urˇcité m´ısto. Optimalizace bude obsahovat popis algoritmu, ktery´ jednotlivé poloˇzky z objednávky sestav´ı v takovém poˇrad´ı, zˇ e obsluha skladu uraz´ı bˇehem jejich vyzvednut´ı co nejkratˇs´ı cestu a nebude si zbyteˇcnˇe zacházet, v naˇsem pˇr´ıpadˇe zaj´ızˇ dˇet s vysokozdviˇznym ´ voz´ıkem. T´ım mysl´ıme, zˇ e poloˇzky budou seˇrazeny postupnˇe v ˚ závislosti na poˇrad´ı, ve kterém se nacházej´ı pˇri pruchodu nejkratˇs´ı trasy, pˇr´ıpadnˇe jedné z nejkratˇs´ıch tras. Zdali touto cestou obsluha vysokozdviˇzného voz´ıku skuteˇcnˇe pojede cˇ i ne uˇz algoritmus zajistit nedovede. Rovnˇezˇ se neoˇcekává implementace algoritmu, ktery´ v pˇr´ıpadˇe budouc´ı implementace mus´ı komunikovat se stávaj´ıc´ım obsluˇznym ´ systémem skladu. Pˇri pˇr´ıpravˇe objednávky je ve skladu potˇreba navˇst´ıvit urˇcité regály ”biny”s poˇzadovanou komponentou a se vˇsemi vyzvednutymi komponentami se po´ ´ tom vrátit na m´ısto kompletace. Takto zadaná uloha, má bl´ızko ke známému problému obchodn´ıho cestuj´ıc´ıho - TSP (travelling salesman problem), ktery´ uvedeme v kapitole 4. Jedná se o diskrétn´ı optimalizaˇcn´ı problém nalezen´ı nejkratˇs´ı moˇzné cesty procházej´ıc´ı vˇsemi zadanymi body na mapˇe, kaˇzdym ´ ´ právˇe jednou.

Obrázek 1: World tour z knihy The Traveling Salesman Problem [2]

4

˚ Tento problém je jiˇz pomˇernˇe dukladnˇ e prostudován a existuj´ı i algoritmy které ho rˇ eˇs´ı. Zásadn´ı pot´ızˇ vˇsak je, zˇ e problém obchodn´ıho cestuj´ıc´ıho patˇr´ı mezi ´ tzv. NP-tˇezˇ ké ulohy, pro které se nepˇredpokládá existence polynomiáln´ıho algoritmu a v obecném pˇr´ıpadˇe nen´ı známo jak nalézt pˇresné rˇ eˇsen´ı v rozumném ´ cˇ ase. Tuto komplikaci bude tˇreba v práci zahrnout do uvahy, jelikoˇz nen´ı moˇzné, aby se na nalezen´ı optimáln´ıho poˇrad´ı cˇ ekalo nˇekolik hodin, ve skuteˇcnosti by mˇel byt k dispozici v rˇ a´ du vteˇrin, nebo lépe zlomku˚ vteˇriny. ´ vysledek ´ Pˇri rˇ eˇsen´ı zadaného problému budeme diskutovat známé algoritmy a pouˇz´ı˚ z tohoto duvodu ˚ vat obraty a pojmy z teorie Grafu, je do práce zahrnuta kapitola ˚ která slouˇz´ı k objasnˇen´ı pouˇz´ıvanych ˚ 3 Definice a pojmy z teorie grafu, ´ pojmu. ˚ V kapitole 2 si pˇredstav´ıme zadany´ problém dukladnˇ eji a seznám´ıme se zde s terminologi´ı obsluhy skladu, kterou potom budeme dále pouˇz´ıvat, abychom se vyhnuli pˇr´ıpadnym ´ nejasnostem. Pod´ıváme se na známe algoritmy a v kapitole ´ 5 zhodnot´ıme, ktery´ a za jakych by mohl byt ´ pˇr´ıpadnych ´ uprav ´ pro násˇ problém ten nejvhodnˇejˇs´ı. Samotny´ algoritmus potom pop´ısˇ eme v kapitole 6.

5

2

´ ı problemu ´ Zformulovan´

Diplomová práce rˇ eˇs´ı reálny´ problém optimalizace cesty pˇri kompletaci objednáv¨ ky ve skladu medic´ınského materiálu firmy Molnlycke Health Care v Karviné. Zadán´ı problému bylo specifikováno pˇri osobn´ı návˇstˇevˇe skladu, které se kromˇe ´ castnil také vedouc´ı diplomové práce Petr Kovárˇ . Po autora diplomové práce zuˇ ¨ celou dobu naˇs´ı návˇstˇevy se nám vˇenoval zamˇestnanec firmy Molnlycke Health Care, Jan Korponai, ktery´ nás spoleˇcnˇe se svym ´ kolegou skladem provedli a zodpovˇedˇeli naˇse otázky. Skladové prostory a rozm´ıstˇen´ı regálu˚ uvnitˇr je patrné z obrázku ?? na stranˇe ??, uvedeném v neveˇrejné kapitole 9. Tyto informace jsou povaˇzovány firmou ¨ Molnlycke Health Care za citlivé a nejsou proto uvedeny ve veˇrejné cˇ a´ sti práce. ´ ych Sklad je tvoˇren s´ıt´ı pravouhl ´ uliˇcek oddˇelenymi ´ regály, ve kterych ´ jsou uloˇzeny krabice s medic´ınskym ´ materiálem. Ve skladu se kompletuj´ı zakázky obsahuj´ıc´ı ˚ y´ poˇcet komponent, které je tˇreba pˇred kompletac´ı svézt na jedno m´ısto poruzn moc´ı vysokozdviˇzného voz´ıku. Cestu tohoto vysokozdviˇzného voz´ıku budeme cht´ıt optimalizovat tak, aby se minimalizovala vzdálenost, kterou vysokozdviˇzny´ voz´ık pˇri nab´ırán´ı materiálu pro objednávku ujede, a t´ım pádem sn´ızˇ ila doba nutná pro pˇr´ıpravu, svoz komponent.

2.1

ˇ Soucasn y´ stav

¨ Souˇcasny´ stav je následuj´ıc´ı. Ve skladu firmy Molnlycke Health Care v Karviné ˚ zity) operuje nˇekolik (jejich pˇresny´ poˇcet nen´ı pro rˇ eˇsen´ı diplomové práce duleˇ ´ ˚ Komponenty kaˇzdé objednávky se vytisknou na tzv. vysokozdviˇznych ´ voz´ıku. ”picking list”, ktery´ se pˇredá obsluze vysokozdviˇzného voz´ıku. Ta podle svého vlastn´ıho uvázˇ en´ı zvol´ı trasu, kterou sklad projede a nabere vˇsechny poˇzadované komponenty. Vlastn´ı sklad je systematicky rozdˇelen na cˇ tyˇri cˇ a´ sti: sklad A, sklad B, sklad C a sklad D. Ve skladu A se nacházej´ı komponenty, které se vyuˇz´ıvaj´ı nejˇcastˇeji a rovnˇezˇ se v nˇem dokuj´ı pˇripravené objednávky. Picking list je seznam krabic, obsahuj´ıc´ı jednotlivé komponenty, které jsou potˇrebné pro danou objednávku. Obsahuje informace o velikosti krabice, expiraˇcn´ı dobˇe materiálu a pozici binu, kde je krabice um´ıstˇena ve skladu. Bin je m´ısto pro uloˇzen´ı krabice s komponentami ve skladu. Je jednoznaˇcnˇe ´ urˇceno pomoc´ı kodu, ktery´ je souˇca´ st´ı ”picking listu”, oznaˇcuj´ıc´ı sklad, uliˇcku, patro a pozici v uliˇcce. Um´ıstˇen´ı komponenty ve skladu je dáno jednoznaˇcnˇe, jelikoˇz se pˇri kompletaci objednávky trvá na tom, zˇ e se pouˇzij´ı komponenty s nejkratˇs´ı expiraˇcn´ı dobou, aby ty jejihˇz trvanlivost je delˇs´ı mohly byt ´ pouˇzity pro pozdˇejˇs´ı objednávku.

6

Po osobn´ı konzultaci autora diplomové práce a vedouc´ıho diplomové práce ¨ se zadavatelem problému ze strany Molnlycke Health Care pˇri návˇstˇenˇe skladu ˚ castnˇené strany se zjednoduˇsen´ım, které nebere v Karviné, souhlasily vˇsechny zuˇ v potaz moˇznost, kdy je objednávka pˇr´ıliˇs rozsáhlá na to, aby mohla byt ´ svezena ze skladu pˇri jediné j´ızdˇe vysokozdviˇzného voz´ıku. Tato eventualita se podle zamˇestnancu˚ skladu vyskytuje velice vyj´ımeˇcnˇe.

2.2

´ Nasleduj´ ıc´ı postup

V této diplomové práci se budeme snaˇzit navrhnout algoritmus, ktery´ najde pro kaˇzdou objednávku v rozumném cˇ ase optimáln´ı cestu pro vysokozviˇzny´ voz´ık mezi jednotlivymi biny obsahuj´ıc´ı komponenty z objednávky ve skladu. Tento ´ algoritmus potom jednotlivé biny podle této cesty seˇrad´ı a vytiskne na ”picking list”, ktery´ obsluze vysokozdviˇzného voz´ıku ukázˇ e v jakém poˇrad´ı je nejvhodnˇejˇs´ı komponenty sb´ırat. Cesta mezi jednotlivymi komponentami uˇz v ”pic´ ´ e s´ıti uliˇcek a zkuˇsenosti king listu”zachycena nen´ı, ale vzhledem k pravouhl´ zamˇestnancu˚ se pˇredpokládá vyuˇzit´ı jedné z najkratˇs´ıch cest. Nalezen´ı nejkratˇs´ı moˇzné cesty procházej´ıc´ı vˇsemi zadanymi body ve skladu ´ ´ resp. nalezen´ı nejkratˇs´ı hamiltonovské kruˇznice na podgrafu je NP- upln y´ problém a pˇredpokládá1 se, zˇ e zˇ a´ dny´ ”rychly”, ´ (s polynomiáln´ı sloˇzitost´ı) deterministicky´ algoritmus, neexistuje. Nalezen´ı nejkratˇs´ı moˇzné cesty procházej´ıc´ı ´ vˇsemi zadanymi body ve skladu je uloha, která je velice bl´ızká problému ob´ chodn´ıho cestuj´ıc´ıho. Problém obchodn´ıho cestuj´ıc´ıho, ktery´ si podrobnˇeji pˇredstav´ıme v kapitole 4, by se dal formulovat jako problém nalezen´ı nejkratˇs´ı moˇzné cesty, která projde zadanymi m´ısty, kaˇzdym ´ ´ právˇe jednou. Tento problém je tedy skuteˇcnˇe skoro stejny´ s t´ım, ktery´ máme my a budeme tedy vycházet se známych ´ algoritmu˚ pro rˇ eˇsen´ı problému obchodn´ıho cestuj´ıc´ıho. Nemus´ıme byt ´ pˇritom tak ˚ zeme pˇr´ısn´ı na podm´ınku, aby jsme kaˇzdé m´ısto navˇst´ıvili právˇe jednou, ale muˇ se spokojit s podm´ınkou, aby kaˇzdé m´ısto (které bude zadáno) bylo navˇst´ıveno alesponˇ jednou. Aby skuteˇcnˇe doˇslo k zefektivnˇen´ı vyroby ve skladu nen´ı moˇzné, aby algorit´ mus hledal optimáln´ı rˇ eˇsen´ı pˇr´ıliˇs dlouho. Bude proto tˇreba naj´ıt vhodny´ algoritmus, jiny´ neˇz porovnáván´ı délky vˇsech moˇznych ´ cest ve skladu se sloˇzitost´ı n!. Naskyt´ ´ a se nám zde nˇekolik moˇznost´ı: a) Uˇzit´ı nedeterministického algoritmu. Nedeterministické nebo heuristické algoritmy davaj´ı vˇetˇsinou pˇribliˇzny´ vysledek a pˇri opakovaném stejném vstupu ´ ˚ zou dávat rozd´ılné vysledky, muˇ d´ıky moˇznosti volby kroku. Neprocházej´ı ´ vˇsechny moˇznosti a za cenu urˇcité nejistoty jsou vypoˇ ´ cetnˇe ménˇe nároˇcné. 1

Jedná se o jeden z otevˇrenych ´ problému˚ tis´ıcilet´ı (anglicky Millenium Prize Problems), za ˚ vyˇreˇsen´ı kaˇzdého z nich vypsal Clay Mathematics Institute odmˇenu jednoho milionu dolaru.

7

˚ se ale budeme snaˇzit vyhnout, jelikoˇz by bylo vhodné, Tˇemto algoritmum aby pro dvˇe stejné objednávky dal algoritmus stejné vysledky. ´ ˚ zeme pokusit zjednob) Zjednoduˇsen´ı. Graf popisuj´ıc´ı strukturu skladu se muˇ duˇsit, zanedbat faktory, které nehrajou vyraznou roli, vyuˇz´ıt vhodné závis´ ˚ ze nastat zkreslen´ı losti, které se ve skladu vyskytuj´ı. Pˇri zjednoduˇsen´ı muˇ ˚ ze byt reálné situace, toto muˇ e pokud za cenu vnesen´ı drobné nepˇre´ vyhodn´ ´ ´ snosti z´ıskáme vyznamnou usporu vypoˇ ´ ´ cetn´ı nároˇcnosti problému. Touto cestou se budeme snaˇzit j´ıt. c) Vyuˇzit´ı symetrie grafu. Pokud nechceme pouˇz´ıt nedeterministicky´ algoritmus ˚ ze byt ale deterministicky, ´ ktery´ muˇ ´ pro obecné grafy vypoˇ ´ cetnˇe pˇr´ıliˇs nároˇc˚ zeme vyuˇz´ıt skuteˇcnosti, zˇ e graf na kterém budeme problém rˇ eˇsit, ny, ´ muˇ dobˇre známe. Nemus´ıme procházet vˇsecny moˇzné cesty, protoˇze nˇekteré ˚ ˚ zeme vyuˇz´ıt opakuj´ıc´ı se struktury v nebudou vubec existovat. Rovnˇezˇ muˇ grafu.

8

3

Definice a pojmy z teorie grafu˚

V této kapitole zavedeme pojmy, vˇety a definice, na které se budeme v dalˇs´ım textu odkazovat. Abychom nemuseli text práce neustále pˇreruˇsovat definicemi vysvˇetluj´ıc´ı právˇe pouˇz´ıvané pojmy, je vˇetˇsina z nich uvedena v této kapitole. Pojmy jsou rˇ azeny tak, aby k pochopen´ı právˇe uvedené definice staˇcila znalost ˚ nejedná se vˇsak v zˇ a´ pˇredchoz´ıch. Pojmy a definice jsou z oblasti teorie grafu, ´ dném pˇr´ıpadˇe o upln y´ vyˇ ´ cet vˇsech definic této matematické discipl´ıny, coˇz by snad ani nebylo moˇzné, ale pouze o pˇrehled tˇech definic, které budeme v práci vyuˇz´ıvat, nebo jejichˇz znalost by se nám mohla hodit. Nˇekteré vˇety a definice byly pˇrevzaty ze skript teorie grafu˚ [1]. V znaˇcen´ı pojmu˚ se snaˇz´ım drˇzet bˇezˇ nˇe pouˇz´ıvané symboliky, známé ze skript ˚ Nˇekdy je ale, vzhledem k potˇrebˇe rozliˇsovat stejné pojmy cˇ i odbornych ´ cˇ lánku. ˚ ych u ruzn ´ grafu˚ (napˇr´ıklad poˇcet vrcholu˚ nebo pravidelnost grafu) pouˇzito nestandardn´ı znaˇcen´ı. Zkratky a znaˇcen´ı vˇetˇsinou vycházej´ı z anglické terminologie, napˇr. oznaˇcen´ı mnoˇziny vrcholu˚ V (vertices) a hran E (edges).

Definice 3.1 Jednoduchý graf G je uspoˇra´ daná dvojice (V, E), kde V je neprázdná mnoˇzina vrcholu˚ a E je nˇejaká podmnoˇzina dvouprvkových podmnoˇzin mnoˇziny V . Prvkum ˚ E rˇ´ıkáme hrany. ˇ ı jako body a hrany Graf je nejˇcastˇeji zadán diagramem, kde se vrcholy znázornuj´ jako kˇrivky spojuj´ıc´ı tyto body. t

y w

x

z

Obrázek 2: Pˇr´ıklad jednoduchého grafu G s mnoˇzinou vrcholu˚ V = {t, w, x, y, z} a mnoˇzinou hran E = {{x, y}, {x, w}, {x, z}, {w, z}}. Definice 3.2 Mnoˇzinu vˇsech vrcholu˚ grafu G budeme znaˇcit V (G) a mnoˇzinu vˇsech hran E(G). V textu nˇekdy pracujeme s libovolnym ´ grafem G, na jehoˇz parametry nemáme zˇ a´ dné poˇzadavky. Chceme-li u grafu specifikovat poˇcet vrcholu˚ n = |V (G)|, rˇ ekneme, zˇ e jde o graf na n vrcholech nebo o graf rˇ a´ du n.

9 Definice 3.3 Dva vrcholy x, y ∈ V (G) jsou sousedn´ı, kdyˇz existuje hrana xy ∈ E(G). Na obrázku 2 jsou napˇr´ıklad vrcholy x a z sousedn´ı, zat´ımco vrcholy w a y sou˚ se také rˇ´ıká závislé a nesousedn´ım nezávislé sedn´ı nejsou. Sousedn´ım vrcholum vrcholy. ˇ Definice 3.4 Rekneme, zˇ e hrana e = {x, y} ∈ E(G) je incidentn´ı s vrcholem x právˇe tehdy, kdyˇz x ∈ e. Vrcholy x, y nazveme koncové vrcholy hrany e. Definice 3.5 Graf, ve kterém mohou být dva ruzn´ ˚ e vrcholy spojeny v´ıce neˇz jednou hranou, nazveme multigraf. Hranám které maj´ı stejné oba koncové vrcholy se rˇ´ıká násobné hrany, multihrany nebo paraleln´ı hrany. b

a

c

d

Obrázek 3: Pˇr´ıklad multigrafu s mnoˇzinou vrcholu˚ V = {a, b, c, d} . ˇ Definice 3.6 Rekneme, zˇ e graf H = (V ′ , E ′ ) je podgrafem grafu G = (V, E), jestliˇze ′ V ⊆ V a souˇcasnˇe E ⊆ E ′ . ˚ zeme Jestliˇze o grafu H rˇ ekneme, zˇ e je podgrafem grafu G, potom také graf G muˇ oznaˇcit za nadgraf grafu H. Definice 3.7 Podgraf F = (V ′ , E ′ ) grafu G = (V, E), se nazývá faktor grafu G jestliˇze V = V ′.   Definice 3.8 Doplnˇek grafu G = (V, E) je graf G = (V, F ), kde F = V2 \E a V (G) =   V (G). V2 znaˇc´ı vˇsechny dvouprvkové podmnoˇziny mnoˇziny V (G). Doplnˇek grafu G tedy obsahuje vˇsechny vrcholy grafu G, a kaˇzdy´ vrchol x ∈ V (G) je sousedn´ı s právˇe tˇemi vrcholy, se kterymi v grafu G sousedn´ı nen´ı. ´ Definice 3.9 Stupenˇ vrcholu x je roven poˇctu vˇsech hran, které jsou s vrcholem x incidentn´ı. Stupenˇ vrcholu x znaˇc´ıme deg(x).

10

Stupenˇ vrcholu x souˇcasnˇe dává informaci s kolika vrcholy je vrchol x sousedn´ı. ˚ ze byt Je tedy zˇrejmé, zˇ e stupenˇ zˇ a´ dného vrcholu nemuˇ ´ vˇetˇs´ı neˇz poˇcet vrcholu˚ v ˚ ze byt grafu bez vrcholu samotného, jelikoˇz sám se sebou nemuˇ ´ sousedn´ı. Nejvyˇssˇ´ı ˇ kterého muˇ ˚ ze vrcholu x ∈ V (G) nabyvat, moˇzny´ stupen, je deg(x) = |V (G)| − 1. ´ Toto plat´ı pouze pro grafy, nikoliv uˇz vˇsak pro multigrafy. deg(t)=0

deg(y)=1 deg(w)=2

deg(x)=3

deg(z)=2

Obrázek 4: Stupnˇe vrcholu˚ grafu G Vˇeta 3.1 (Princip sudosti) Mˇejme libovolný graf G s vrcholy v1 , v2 , . . . , vn , kde n ≥ 1. Poˇcet hran grafu G oznaˇc´ıme h(G) = |E(G)|. Potom plat´ı  deg(vi ) = 2 h(G). vi ∈V (G)

˚ ˚ Vˇsimneme-li si, Dukaz vˇety 3.1 je moˇzné naj´ıt v kaˇzdych ´ skriptech teorie grafu. ˚ zjist´ıme, zˇ e v zˇ e kaˇzdá hrana zvyˇsuje stupenˇ vrcholu o 1 právˇe u dvou vrcholu, kaˇzdém grafu je souˇcet stupnˇ u˚ vrcholu˚ vˇsech vrcholu˚ grafu roven dvojnásobku poˇctu hran. ˚ ze byt Poznámka 3.1 Vˇeta 3.1 nám rˇ´ıká, zˇ e v grafu nemuˇ ´ lichy´ poˇcet vrcholu˚ lichého stupnˇe (poˇcet hran mus´ı byt ´ celé cˇ ´ıslo). Definice 3.10 [1] Graf nazveme sudy, ´ jestliˇze má vˇsechny vrcholy sudého stupnˇe. Podobnˇe budeme mluvit o sudých multigrafech. Definice 3.11 [1] Sled v grafu je taková posloupnost vrcholu˚ a hran (v0 , e1 , v1 , e2 , v2 . . . , en , vn ), zˇ e hrana ei má koncové vrcholy vi−1 a vi pro vˇsechna i = 1, 2, . . . , n. Délku sledu definujeme jako poˇcet hran obsaˇzených ve sledu. Definice 3.12 [1] Tah je sled ve kterém se zˇ a´ dná hrana neopakuje. Tah s poˇca´ teˇcn´ım vrcholem u a koncovým vrcholem v budeme nazývat (u, v)-tah. Délku tahu definujeme jako poˇcet hran obsaˇzených v (u, v)-tahu.

11

Definice 3.13 [1] Cesta je sled ve kterém se neopakuje zˇ a´ dný vrchol. Cestu s poˇca´ teˇcn´ım vrcholem u a koncovým vrcholem v budeme nazývat (u, v)-cesta. Délku cesty definujeme jako poˇcet hran obsaˇzených v (u, v)-cestˇe. Definice 3.14 Graf se nazývá souvisly, ´ jestliˇze mezi kaˇzdými dvˇema jeho vrcholy x, y existuje (x, y)-cesta. Definice 3.15 [1] Uzavˇrený tah v grafu G, který obsahuje vˇsechny hrany a vˇsechny vrcholy grafu G, se nazývá (uzavˇreny) ´ eulerovsky´ tah. Graf, ve kterém existuje uzavˇrený eulerovský tah, se nazývá eulerovsky´ graf a rˇ´ıkáme, zˇ e graf G lze nakreslit jedn´ım tahem. Následuj´ıc´ı vˇeta dává nutnou a postaˇcuj´ıc´ı podm´ınku existence eulerovského tahu v daném grafu. Vˇeta 3.2 (Eulerovsky´ tah) Graf G je eulerovsky´ právˇe tehdy, kdyˇz je sudy´ a souvisly. ´ Poznámka 3.2 (Eulerovsky´ tah) Vˇeta 3.2 plat´ı analogicky i pro multigrafy. Multigraf G je eulerovský právˇe tehdy, kdyˇz je sudý a souvislý. Pro vyznamn´ e typy grafu˚ se pouˇz´ıvá vlastn´ı název a oznaˇcen´ı. Název vˇetˇsinou ´ plyne ze symetrie nebo vlastnost´ı grafu. Definice 3.16 Graf, jehoˇz kaˇzdé dva vrcholy jsou navzájem sousedn´ı, nazýváme Kompletn´ı graf a znaˇc´ıme Kn , kde n je poˇcet vrcholu˚ kompletn´ıho grafu.

Obrázek 5: Kompletn´ı grafy K4 a K9 ´ ´ Kompletn´ı graf, nazyvan y´ také upln y´ graf, má uplnou mnoˇzinu hran E(Kn ) = ´ V (Kn ) . Poˇcet hran v kompletn´ım grafu na n vrcholech je tedy n (n−1) . Doplnˇek 2 2 ˚ jelikoˇz podle definice 3.8 kompletn´ıho grafu je mnoˇzina nezávislych vrcholu, ´ je E(Kn ) = ∅. Kaˇzdy´ kompletn´ı graf má vˇsechny vrcholy nejvyˇssˇ´ıho moˇzného stupnˇe, je (n − 1)-pravidelny. ´

12 Definice 3.17 Graf s mnoˇzinou vrcholu˚ V = {x1 , x2 , . . . , xn }, kde n ≥ 3, a mnoˇzinou hran E = {x1 x2 , x2 x3 , . . . , xn−1 xn , xn x1 }, se nazývá cyklus a znaˇc´ıme jej Cn .

Obrázek 6: Cykly C3 a C8 Cyklus je 2-pravidelny´ graf se stejnym ´ poˇctem vrcholu˚ a hran |E(Cn )| = n. O poˇctu vrcholu˚ n grafu Cn se cˇ asto hovoˇr´ı jako o délce cyklu. V tomto smyslu jsou na obrázku 6 cykly délky 3 a 8. Cyklem v grafu G budeme rozumˇet takovy´ podgraf grafu G, ktery´ je souˇcasnˇe cyklem podle definice 3.17. Vyznamnou roli mezi tˇemito cykly má takovy´ cyklus ´ ktery´ projde vˇsemi vrcholy nadgrafu G. Definice 3.18 [1] Cyklus, který procház´ı vˇsemi vrcholy grafu G, se nazývá hamiltonovsky´ cyklus v grafu G. Graf, který obsahuje hamiltonovský cyklus, se nazývá hamiltonovsky´ graf. Definice 3.19 Graf se nazývá acyklický, jestliˇze zˇ a´ dný jeho podgraf nen´ı cyklus. Souvislý acyklický graf se nazývá strom. Definice 3.20 Takový faktor grafu, který je souˇcasnˇe stromem, se nazývá kostrou grafu.

Obrázek 7: Graf G a jeho kostra K.

13

Nyn´ı zavedeme pojmy a definice souvisej´ıc´ı s ohodnocen´ım grafu. Definice 3.21 [11] Ohodnocen´ı grafu je funkce f , která vrcholum ˚ nebo hranám v grafu G pˇriˇrad´ı cˇ´ısla, nejˇcastˇeji z mnoˇziny pˇrirozených cˇ´ısel. Pˇriˇrazená cˇ ´ısla maj´ı vˇetˇsinou nˇejaky´ fyzikáln´ı nebo prakticky´ vyznam, napˇr. ´ délky, kapacity, ceny. Definice 3.22 Hodnota vrcholu x nebo hrany xy grafu G je cˇ´ıslo pˇriˇrazené v ohodnocen´ı f vrcholu x nebo hranˇe xy. Definice 3.23 [11] Jsou-li v ohodnocen´ı f pˇriˇrazeny hodnoty pouze hranám grafu G = (V, E), hovoˇr´ıme o hranovém ohodnocen´ı grafu, v pˇr´ıpadˇe kdy jsou hodnoty pˇriˇrazeny pouze vrcholum, ˚ hovoˇr´ıme o vrcholovém ohodnocen´ı grafu. V této práci budeme pouˇz´ıvat pouze hranová ohodnocen´ı grafu, jelikoˇz hodnoty budeme pˇriˇrazovat pouze hranám v závislosti na vzdálenosti jejich kon˚ covych ´ vrcholu.

5 3 2

4

Obrázek 8: Pˇr´ıklad ohodnocen´ı hran grafu H. Definice 3.24 Minimáln´ı kostra grafu G pˇri ohodnocen´ı f je taková kostra, zˇ e souˇcet hodnot hran kostry je minimáln´ı moˇzný. ˇ ıkáme, Definice 3.25 [1] Nezávislá mnoˇzina hran M grafu G se nazývá párován´ım. R´ zˇ e koncové vrcholy hran v M jsou spárovány nebo M -saturované. Párován´ı budeme obvykle oznaˇcovat p´ısmenem M z anglického matching. ´ Definice 3.26 [1] Párován´ı M se nazývá upln´ e, jestliˇze je kaˇzdý vrchol grafu G M saturovaný.

14

3 2

4

Obrázek 9: Minimáln´ı kostra grafu H z obrázku 8. Definice 3.27 Minimáln´ı upln´ ´ e párován´ı M grafu G je takové upln´ ´ e párován´ı, zˇ e souˇcet hodnot pˇriˇrazeným hranám v párován´ı M je ze vˇsech moˇzných upln´ ´ ych párován´ı grafu G minimáln´ı.

5 3 2

4

´ Obrázek 10: Minimáln´ı upln´ e párován´ı grafu H z obrázku 8.

15

´ obchodn´ıho cestuj´ıc´ıho Problem

4

It’s addictive. No matter how much progress you make, you always have the nagging feeling that you still did not nail down a couple of hunches that could bring about another quantum leap. – Vaˇsek Chvátal, 1998.2 Ve tˇricátych ´ letech dvacátého stolet´ı 3 byl formulován tzv. Problém obchodn´ıho ´ cestuj´ıc´ıho, ktery´ je zaloˇzen na uvaze, kdy obchodn´ı cestuj´ıc´ı vyrázˇ ´ı z urˇcitého ´ mˇesta, a bˇehem své cesty má za ukol navˇstivit nˇekolik dalˇs´ıch mˇest (vˇetˇsinou se poˇzaduje aby kaˇzdé mˇesto navˇst´ıvil právˇe jednou) a potom se opˇet vrátit zpˇet. ˇ sen´ım problému je nalezen´ı takové cesty mezi mˇesty, které má obchodn´ı cesReˇ tuj´ıc´ı navˇst´ıvit, zˇ e jakákoliv jiná obchodn´ı cesta bude stejnˇe dlouhá nebo delˇs´ı. Pˇredstavme si, zˇ e jste obchodn´ı cestuj´ıc´ı z Ostravy. A máte navˇst´ıvit vˇsechna ˇ mˇesta v Cesk´ e Republice s poˇctem obyvatel nad 250 000. Máte tedy navˇst´ıvit Prahu, Brno a Ostravu, kde zaˇc´ınáme. Jak to udˇelat aby vysledn´ a cesta byla co nej´ kratˇs´ı? No jednoduˇse pojedete z Ostravy do Prahy a potom do Brna a zpˇet do Ostravy. Nebo v obráceném poˇrad´ı Ostrava, Brno, Praha, Ostrava, kde délka cesty bude stejná jako v pˇredchoz´ım pˇr´ıpadˇe. Zde se zat´ım v tichosti pˇredpokládá, zˇ e délka cesty z Ostravy do Prahy je stejná jako z Prahy do Ostravy. Jednoduché, dalˇs´ı moˇznosti neexistuj´ı. Problém je tedy v tomto pˇr´ıpadˇe vyˇreˇsen a vy jako ob˚ zete vyrazit do Prahy nebo do Brna podle toho kam se v´ıce chodn´ı cestuj´ıc´ı, muˇ tˇesˇ´ıte. Poté co se vrát´ıte ze své prvn´ı obchodn´ı cesty, rozhodnete se navˇst´ıvit pˇri své ˇ dalˇs´ı cestˇe vˇsechna mˇesta v Cesk´ e Republice s poˇctem obyvatel nad 100 000. Takˇze ˇ Liberec a Olomouc. A náhle je problém o dosti tˇezˇ sˇ´ı, minule nám pˇribude Plzen, kdyˇz jsme vyrázˇ eli z Ostravy jsme mˇeli k dispozici dvˇe mˇesta a at’ jsme si vybrali kterékoliv z nich následovala potom cesta do toho zbyvaj´ ´ ıc´ıho a zpˇet do Ostravy. Nyn´ı si mus´ıme vybrat z pˇeti mˇest a aˇz do nˇejakého odcestujeme, tak se vybˇ ´ er moˇznost´ı sn´ızˇ ´ı na cˇ tyˇri, potom na tˇri atd. Celkovy´ poˇcet moˇznych cest je nyn´ı ´ 5! = 5 · 4 · 3 · 2 · 1 = 120, kdyˇz pˇrihlédneme ke skuteˇcnost,i zˇ e poˇrad´ı navˇst´ıvanych ´ ˚ zeme obrátit, aniˇz by se zmˇenila délka cesty, dostáváme 120/2 = 60. To mˇest muˇ ˚ ych sice jeˇstˇe nen´ı nepˇrekonatelny´ problém ale porovnat 60 ruzn ´ cest uˇz zabere nˇejaky´ cˇ as. Po návratu z druhé cesty se rozhodnete navˇst´ıvit vˇsechna mˇesta s ˇ poˇctem obyvatel nad 10 000, v roce 2011 jich v Cesk´ e republice bylo 132... V roce 1962 firma Procter & Gamble vyhlásila soutˇezˇ o $ 10,000 , za coˇz se dal ˚ [3]. Zadán´ı soutˇezˇ e bylo následuj´ıc´ı: tehdy postavit dum 2 3

Citát z kn´ızˇ ky: In Pursuit of the Traveling Salesman, [3]. Dá se pˇredpokládat, zˇ e se varianty tohoto problému rˇ eˇsili uˇz dˇr´ıve, i kdyˇz tˇreba jen intuitivnˇe.

16

Pˇredstavte si, zˇ e Toody a Muldoon chtˇej´ı projet Spojené státy a navˇst´ıvit pˇri tom 33 lokac´ı uvedenych ´ na mapˇe (viz Obrázek 11). Chtˇej´ı to ale udˇelat tak, aby celkem ujeli co nejkratˇs´ı vzdálenost. Máte jejich cestu naplánovat z m´ısta na m´ısto tak, aby vysledn´ a cesta byla co nej´ kratˇs´ı. Zaˇc´ınáte v Chigagu, Illinois a také tam mus´ıte skonˇcit.

Obrázek 11: Soutˇezˇ firmy Procter & Gamble z roku 1962 [3] Problém obchodn´ıho cestuj´ıc´ıho, dále jen TSP (Traveling Salesman Problem), ´ je klasická optimalizaˇcn´ı uloha, kdy hledáme hamiltonovsky´ cyklus s nejniˇzsˇ´ım souˇctem hodnot hran v kompletn´ım hranovˇe ohodnoceném grafu s n vrcholy. Bu´ deme se zde zabyvat pouze tzv. symetrickou variantou ulohy, kdy cena“ hod´ ”

17

nota hrany z vrcholu A do vrcholu B je stejná jako cena“ hodnota hrany z vrcholu ” B do vrcholu A, ceny zde tedy maj´ı charakter vzdálenost´ı.

4.1

´ obchodn´ıho cestuj´ıc´ıho v metrickem ´ prostoru Problem

Variantou tohoto problému je problém obchodn´ıho cestuj´ıc´ıho v metrickém proˇ ı trojuheln´ ´ storu, ve kterém vzdálenosti na grafu splnuj´ ıkovou nerovnost, coˇz je jeden z axiomu˚ metrického prostoru. Toto zjednoduˇsen´ı odpov´ıdá velkému mnoˇzstˇ v´ı reálnych konstrukci ´ problému˚ (napˇr. hledán´ı na mapˇe), a zárovenˇ umoˇznuje ˚ Tato varianta bude pro nás jistˇe zaj´ımavá, jelikoˇz syaproximaˇcn´ıch algoritmu. stém na sebe kolmych ´ cest ve skladu splnujˇe vˇsechny axiomy metrického prostoru. Definice 4.1 (metrického prostoru) Metrický prostor je dvojice (M, ρ), kde M je libovolná neprázdná mnoˇzina (v naˇsem pˇr´ıpadˇe to bude mnoˇzina vrcholu) ˚ a ρ je tzv. metrika, coˇz je zobrazen´ı ρ:M×M→R splnuj´ ˇ ıc´ı následuj´ıc´ı axiomy: 1. nezápornost 2. symetrie

ρ(x, y) ≥ 0, ρ(x, y) = 0 ⇔ (x = y) ρ(x, y) = ρ(y, x)

3. trojuheln´ ´ ıková nerovnost

∀x, y ∈ M

∀x, y ∈ M

ρ(x, z) ≤ ρ(x, y) + ρ(y, z)

∀x, y, z ∈ M

Poznámka 4.2 V naˇsem pˇr´ıpadˇe bude metrika ρ, zobrazen´ı pˇriˇrazuj´ıc´ı kaˇzdé dvojici vrcholu˚ (x, y) hodnotu rovnou délce nejkratˇs´ı (x, y)–cestˇe v grafu G. Poznamenejme, zˇ e aproximaˇcn´ı algoritmy pˇredpokládaj´ı, zˇ e je moˇzné se z libovolného vrcholu dostat do jakéhokoliv jiného vrcholu. ˇ ı algoritmus 4.1.1 2–aproximacn´ Problém obchodn´ıho cestuj´ıc´ıho v metrickém prostoru lze pˇribliˇznˇe rˇ eˇsit jednoduchym ´ algoritmem[10] v polynomiáln´ım cˇ ase. Algoritmus nejprve zkonstruuje minimáln´ı kostru grafu, napˇr. podle Jarn´ıkova nebo Kruskalova algoritmu, viz podkapitola 5.1. Z definice kostry plyne, zˇ e souˇcet délky hran minimáln´ı kostry je menˇs´ı (nebo roven) neˇz souˇcet délky hran v optimáln´ım rˇ eˇsen´ı TSP, jelikoˇz minimáln´ı kostra obsahuje v nejhorˇs´ım pˇr´ıpadˇe optimáln´ı rˇ eˇsen´ı TSP bez nejdelˇs´ı ˚ hrany (z duvodu acykliˇcnosti). V druhém kroku projde algoritmus kostru z libovolného vrcholu do hloubky ˚ ˚ a poznamená si vˇsechny pruchody pˇres vrcholy, protoˇze se jedná o pruchod do hloubky, budou zde nˇekteré vrcholy zpracovány v´ıcekrát.

18

V posledn´ım kroku algoritmus tento seznam projde a vynechá vˇsechny dupli˚ T´ımto dojde k vytvoˇren´ı samotného city a zanechá pouze prvn´ı vyskyty vrcholu. ´ ´ hamiltonovského cyklu. Protoˇze v grafu plat´ı trojuheln´ ıková nerovnost, tak se ˚ cena vysledn´ eho hamiltonovského cyklu oproti puvodn´ ı minimáln´ı kostˇre ma´ ˚ ze byt ximálnˇe zdvojnásob´ı a oproti optimáln´ımu rˇ eˇsen´ı muˇ ´ tud´ızˇ maximálnˇe dvakrát delˇs´ı. 4.1.2

Christofiduv ˚ algoritmus.

˚ algoritmus rˇ eˇs´ı problém obchodn´ıho cestuj´ıc´ıho v metrickém proChristofiduv storu tak, zˇ e je vysledn´ a trasa v nejhorˇs´ım pˇr´ıpadˇe 1.5-krát delˇs´ı neˇz délka trasy ´ optimáln´ıho rˇ eˇsen´ı. Toto zlepˇsen´ı je ovˇsem vykoupeno vyraznˇ e obt´ızˇ nˇejˇs´ı imple´ ˚ erném mentac´ı, a zárovenˇ se na reálnych nen´ı v prumˇ ´ datech ukazuje, zˇ e vysledek ´ pˇr´ıpadˇe o mnoho lepˇs´ı neˇz pˇri pouˇzit´ı 2-aproximaˇcn´ıho algoritmu uvedeného vyˇ ´ se [10]. ˚ algoritmus nejprve zkonstruuje minimáln´ı kostru grafu T , Christofidesuv napˇr. podle Jarn´ıkova nebo Kruskalova algoritmu. Z definice kostry plyne, zˇ e soucˇ et délky hran minimáln´ı kostry je menˇs´ı (nebo roven) neˇz souˇcet délky hran v optimáln´ım rˇ eˇsen´ı TSP, jelikoˇz minimáln´ı kostra obsahuje v nejhorˇs´ım pˇr´ıpadˇe ˚ optimáln´ı rˇ eˇsen´ı TSP bez nejdelˇs´ı hrany (z duvodu acykliˇcnosti kostry grafu). Poté kostru projde z libovolného vrcholu do hloubky a vybere ty vrcholy, jeˇz maj´ı lichy´ stupenˇ (vrcholu˚ lichého stupnˇe bude sudy´ poˇcet, viz Vˇeta 3.1) a zkonstru´ uje na nich kompletn´ı graf K. V grafu K nalezne minimáln´ı upln´ e párován´ı M , takové párován´ı mus´ı existovat, protoˇze poˇcet vrcholu˚ je sudy´ a jedná se o kompletn´ı graf. Pˇredstavme si nyn´ı, zˇ e budeme cht´ıt vyˇreˇsit TSP na grafu K, rˇ eˇsen´ı ˚ bude kratˇs´ı nebo stejnˇe dlouhé jako rˇ eˇsen´ı na puvodn´ ım grafu. Vynechán´ım kaˇzdé ˚ a upln´ ´ sudé resp. liché hrany z TSP rˇ eˇsen´ı dostaneme dvˇe ruzn´ a párován´ı, z nichˇz alesponˇ jedno z nich bude m´ıt souˇcet hodnot hran menˇs´ı nebo rovno polovinˇe délky optimáln´ıho rˇ eˇsen´ı TSP. Souˇcet délek vˇsech hran v párován´ı M bude tedy ´ maximálnˇe poloviˇcn´ı oproti optimáln´ımu rˇ eˇsen´ı TSP. Hrany z minimáln´ıho uplného párován´ı pˇridáme do minimáln´ı kostry.Vznikly´ multigraf W , V (W ) = V (T ) a E(W ) = E(T ) ∪ M je nyn´ı eulerovsky´ (tj. existuje v nˇem tah, ktery´ obsahuje vˇsechny hrany multigrafu) a souˇcet hodnot hran je maximálnˇe 1.5 násobek rˇ eˇsen´ı optimáln´ıho; 1-násobek za hodnoty hran minimáln´ı kostry a 0.5-násobek za hod´ noty hran minimáln´ıho upln´ eho párován´ı. ˚ algoritmus v posledn´ım kroku tento eulerovsky´ tah projde a Christofiduv ˚ naraz´ı-li na nˇejaky´ vrchol podruhé, pˇreskoˇc´ı na nejbliˇzsˇ´ı nenavˇst´ıveny. ´ Kvuli ˚ ze t´ımto pˇreskakován´ım zvyˇ trojuheln´ıkové nerovnosti nemuˇ s it koneˇ c nou d´ e lku ´ ˚ ze pˇr´ıpadnˇe sn´ızˇ it, nikoliv vˇsak pod teorˇ eˇsen´ı, ta se t´ımto pˇreskakován´ım muˇ retické minimum. T´ımto dojde k vytvoˇren´ı samotného hamiltonovského cyklu.

19 4

4

2

4 3

2

4

4

2

3 2

2

2

2

2

2

4

2

4

2

4

4

2

4

4

3 2

2

4

4

2

4

3 2

4

4

2

4

2

4 4

4

4

4

4 3

4

4

2

2

4

2

4

3

4

2 4

2

4

2

Obrázek 12: Ilustrace Christofidova algoritmu na grafu K5 .

4.2

Heuristicke´ algoritmy

˚ které rˇ eˇs´ı problém Zde by bylo dobré zm´ınit, zˇ e pomˇernˇe rozsáhlá tˇr´ıda algoritmu, obchodn´ıho cestuj´ıc´ıho jsou tzv. heuristické algoritmy. Heuristické algoritmy vˇe´ tˇsinou také pˇripouˇst´ı urˇcitou m´ıru nepˇresnosti, na ukor toho jsou vˇsak schopny rˇ eˇsit i velice rozsáhlé problémy s poˇctem vrcholu˚ nˇekolikanásobnˇe pˇrevyˇsuj´ıc´ı násˇ problém. Heuristické algoritmy nemus´ı pro dva stejné vstupy dávat dva ˚ Z tˇehto stejné vystupy a jejich implementace cˇ asto zasahuje mimo teorii grafu. ´ ˚ duvod u˚ jsme se rozhodli heuristické algoritmy jako jsou genetické algoritmy nebo mravenˇc´ı kolonie do této práce nezahrnout.

20

5

Teoreticky´ rozbor

V minulé kapitole se objevil problém nalezen´ı minimáln´ı kostry v grafu u aproximaˇcn´ıch algoritmu˚ rˇ eˇs´ıc´ı problém obchodn´ıho cestuj´ıc´ıho. Ukázˇ eme si tedy postupy jak minimáln´ı kostru grafu naj´ıt a zm´ın´ıme se také o Eulerovském grafu a ˚ minimáln´ım párován´ı, které budeme v budoucnu potˇrebovat. Poté se dukladnˇ e pod´ıváme na graf, na kterém budeme zadany´ problém rˇ eˇsit.

5.1

´ ı kostry grafu Algoritmy pro nalezen´ı minaln´

Definice minimáln´ı kostry grafu byla zavedena v kapitole 3 na stranˇe 13. Postup ˚ ych nalezen´ı minimáln´ı kostry je cˇ asto souˇca´ st´ı rˇ eˇsen´ı ruzn ´ technickych ´ i jinych ´ reálnych ´ problému˚ (napˇr´ıklad elektrifikace). Nalezen´ı mináln´ı kostry rˇ eˇs´ı nˇekolik ˚ pˇredpokládejme souvisly´ jednoduchy´ graf G a nezáporné ohodnocen´ı algoritmu, hran f . 5.1.1

Kruskaluv ˚ algoritmus

Algoritmus byl poprvé publikován Josephem B. Kruskalem, zamˇestnancem ˚ algoritmus je pˇr´ıkladem hlaBellovych Laboratoˇr´ı, v roce 1956 [4]. Kruskaluv ´ dového algoritmu. Hrany se procház´ı v poˇrad´ı od nejniˇzsˇ´ı hodnoty po nejvyˇssˇ´ı a v pˇr´ıpadˇe, kdy pˇridán´ım hrany do rˇ eˇsen´ı nevznikne v grafu cyklus, se hrana skuteˇcnˇe do rˇ eˇsen´ı pˇridá. ˚ hladovy´ algoritmus hledá minimáln´ı kostru T na souvislém grafu G s Kruskaluv hranovym ´ ohodnocen´ım f : ˇ sen´ı zaˇc´ıná jako faktor grafu G s prázdnou mnoˇzinou hran, E(T ) = ∅. 1. Reˇ 2. Seˇrad’ hrany pohle jejih hodnoty, f (e1 ) ≤ f (e2 ) ≤ . . . ≤ f (eh ). 3. Procházej hrany v poˇrad´ı podle velikosti. Pokud hrana ei nevytvoˇr´ı v grafu T cyklus, pˇridej hranu ei do mnoˇziny E(T ). 4. Po projit´ı vˇsech hran je rˇ eˇsen´ı T minimáln´ı kostrou grafu G. Ve své práci z roku 1956 Kruskal popisuje variantu k uvedenému postupu, ve kterém se z grafu opakovanˇe odeb´ırá hrana s nejvˇetˇs´ım ohodnocen´ım, která ˚ jeˇstˇe nezpusob´ ı, zˇ e se graf stane nesouvislym. T´ımto ekvivalentn´ım postupem ´ ˚ zeme také vytvoˇrit minimáln´ı kostru grafu. muˇ

21

Obrázek 13: Pˇr´ıklad postupu nalezen´ı minimáln´ı kostry pomoc´ı Kruskalova algoritmu [5]. 5.1.2

Jarn´ıkuv ˚ algoritmus

˚ algoritmus (v zahraniˇc´ı známy´ jako Primuv ˚ algoritmus) pro hledán´ı Jarn´ıkuv mináln´ı kostry poprvé popsal Vojtˇech Jarn´ık roku 1930, pozdˇeji byl nezávisle znovuobjeven roku 1957 Robertem Primem. Algoritmus zaˇc´ıná s mnoˇzinou (komponetou souvislosti) obsahuj´ıc´ı jediny´ (startovn´ı) vrchol. Postupnˇe do komponenty souvislosti pˇridává dalˇs´ı vrcholy, které v n´ı jeˇstˇe nejsou zahrnuty tak, zˇ e z pˇr´ıpustnych moˇznost´ı vˇzdy zvol´ı tu, ´ jenˇz spoj´ı novy´ vrchol s komponentou souvislosti hranou s nejniˇzsˇ´ım moˇznym ´ ohodnocen´ım. Algoritmus skonˇc´ı v momentˇe, kdy komponenta souvislosti obsahuje vˇsechny vrcholy. ˚ algoritmus hledá minimáln´ı kostru T na souvislém grafu G s hranovym Jarn´ıkuv ´ ohodnocen´ım f : 1. Nastav´ıme rˇ eˇsen´ı T do poˇca´ teˇcn´ıho stavu, V (T0 ) = r , E(T0 ) = ∅, kde r je libovolnˇe zvoleny´ startovn´ı vrchol. 2. Z mnoˇziny hran W = {pq ∈ E(G) | p ∈ V (Ti−1 ), q ∈ V (G)\V (Ti−1 )} vyber tu s nejniˇzsˇ´ım ohodnocen´ım f ({p, q}) a pˇridej ji do rˇ eˇsen´ı, E(Ti ) = E(Ti−1 ) ∪ {p, q}, V (Ti ) = V (Ti−1 ) ∪ {q}. 3. Po (n − 1) kroc´ıch máme rˇ eˇsen´ı T = Tn , minimáln´ı kostru grafu G.

5.2

´ ı upln ´ ´ ı Minimaln´ ´ e´ parov an´

´ Definici minimáln´ıho upln´ eho párován´ı jsme zavedli v kapitole 3; definice 3.27. ´ Minimáln´ı upln´ e párován´ı budeme potˇrebovat v jednom kroku algoritmu hledaj´ıc´ı optimáln´ı trasu ve skladu. ´ ´ Problém nalezen´ı minimáln´ıho upln´ eho párován´ı nepatˇr´ı mezi snadné ukoly. A aˇckoliv je pro kompledn´ı grafy do rˇ a´ du 10, a to bude prakticky bez vyj´ımky

22

Obrázek 14: Pˇr´ıklad postupu nalezen´ı minimáln´ı kostry pomoc´ı Jarn´ıkova algoritmu [5]. násˇ pˇr´ıpad, moˇzné rˇ eˇsit tento problém hrubou silou, je dobré m´ıt v záloze i sofistikovanˇejˇs´ı algoritmus. Jedn´ım z takovych, ktery´ by bylo moˇzné pouˇz´ıt, je Ed´ ˚ algoritmus, ktery´ zde nebudeme popisovat. Popis algoritmu je moˇzné mondsuv naj´ıt v cˇ lánku [9] nebo lépe v cˇ lánku Edmonds’ Minimum Weight Perfect Matching Algorithm [8]. Hrubou silou se v tomto pˇr´ıpadˇe mysl´ı porovnat souˇcty hodnot hran vˇsech ´ moˇznost´ı upln´ eho párován´ı, kterych ´ v naˇsem pˇr´ıpadˇe, kdy hledáme minimáln´ı  ´ upln´ e párován´ı na kompletn´ım grafu sudého rˇ a´ du4 , bude n/2 i=1 (2i − 1), kde n je poˇcet vrcholu˚ minimáln´ı kostry, které jsou lichého stupnˇe. Pro hodnotu n = 10 dostáváme 945 moˇznost´ı, kdy pro kaˇzdou moˇznost je potˇreba seˇc´ıst hodnoty ˚ erny´ dneˇsn´ı poˇc´ıtaˇc zvládne za zlomek sekundy. Pro práci se 5 hran, coˇz prumˇ c je moˇzné vyuˇz´ıt jiˇz implementované funkce pro nalezen´ı sowtwarem MATLAB⃝ ´ minimáln´ıho upln´ eho párován´ı, obsaˇzené v toolboxu grTheory [7].

5.3

Eulerovsky´ tah

Definici eulerovského tahu jsme zavedli v kapitole 3; definice 3.15. Eulerovsky´ tah se nám bude v jedné fázi algoritmu hledaj´ıc´ı optimáln´ı trasu hodit, proto zde zm´ın´ıme postup jak eulerovsky´ tah naj´ıt. Eulerovské grafy jsou grafy, o kterych ´ ˚ zeme rˇ´ıct, zˇ e je lze nakreslit ”jedn´ım tahem”, t´ım mysl´ıme, zˇ e tuˇzku v prubˇ ˚ ehu muˇ kreslen´ı nezvedneme z pap´ıru, coˇz pˇresnˇe odpov´ıdá definici 3.15 uzavˇreného eulerovského sledu. Cesta vysokozdviˇzného voz´ıku po skladu je v urˇcitém smyslu taky ”jedn´ım tahem”, nebudeme ale hledat eulerovsky´ tah na grafu reprezentuj´ıc´ı cely´ sklad, ale jen na urˇcitém podgrafu, obsahuj´ıc´ı vrcholy reprezentuj´ıc´ı biny, které mus´ıme navˇst´ıvit. Algoritmus vycház´ı z Vˇety 3.2 na stranˇe 11. Ovˇerˇ´ıme-li, zˇ e je graf (multigraf) sudy´ a souvisly, ´ v´ıme zˇ e bude obsahovat eulerovsky´ tah, zbyv´ ´ a jen naj´ıt poˇrad´ı hran. 4

Graf bude sudého rˇ a´ du jelikoˇz hledáme minimáln´ı párován´ı jen mezi vrcholy minimáln´ı kostry, které jsou lichého stupnˇe, a tˇech je podle Vˇety 3.1 sudy´ poˇcet.

23

Algoritmus pro hledán´ı uzavˇreného eulerovského tahu na zadaném grafu, multigrafu G: 1. Ovˇerˇ´ıme, zˇ e je graf G souvisly, ´ a zˇ e je sudy. ´ Pokud tomu tak nen´ı, konˇc´ı algoritmus vypisem, zˇ e graf uzavˇreny´ eulerovsky´ tah neobsahuje. ´ 2. Vybereme náhodnˇe poˇca´ teˇcn´ı vrchol u ∈ V (G). 3. Postupnˇe konstruujeme (u, u)−tah tak, zˇ e se pˇresunujeme z aktuáln´ıho vrcholu do libovolného sousedn´ıho a hranu, kterou jsme k pˇresunu pouˇzili spoleˇcnˇe s koncovym ´ vrcholem uloˇz´ıme do tahu. Postupujeme tak dlouho neˇz se znovu dostaneme na vrchol u. T´ım dostaneme uzavˇreny´ (u, u)−tah. 4. Uzavˇreny´ (u, u)−tah zkontrolujeme. Postupnˇe procház´ıme vrcholy v (u, u)−tahu, a u kaˇzdého vrcholu x zkontrolujeme zda je incidentn´ı s hranou, která nepatˇr´ı do (u, u)−tahu. Jestliˇze ano, pak pˇreruˇs´ıme kontrolu, (u, u)−tah ve vrcholu x rozpoj´ıme a m´ısto vrcholu x vloˇz´ıme (x, x)−tah, ktery´ zkonstruujeme stejnˇe jako jsme konstruovali (u, u)−tah v pˇredchoz´ım kroku. Sousedn´ı vrcholy ale vyb´ıráme tak, aby jsme do (x, x)−tahu ukládali jen hrany, které nejsou souˇca´ st´ı (u, u)−tahu, toto je d´ıky splnˇen´ı podm´ınek z prvn´ıho kroku vˇzdy moˇzné. Po vloˇzen´ı (x, x)−tahu pokraˇcujeme v kontrole (u, u)−tahu. 5. Pˇredposledn´ı krok 4 opakujeme do doby, neˇz kontrola probˇehne bez nalezen´ı vrcholu, ktery´ by byl incidentn´ı s hranou, která nepatˇr´ı do (u, u)−tahu.

5.4

´ Teoreticky´ pohled na zadany´ problem

˚ zeme pod´ıvat Nyn´ı vybaveni teoretickymi znalostmi a známymi algoritmy, se muˇ ´ ´ na zadany´ problém v novém svˇetle a pokusit se ho zformulovat ve tvaru, se kterym ´ se nám bude snadno manipulovat. V následuj´ıc´ıch odstavc´ıch budu pouzˇ ´ıvat vyraz ”uliˇcka”, t´ımto budu dále myslet prostor mezi regály, kde se pohy´ buje vysokozdviˇzny´ voz´ık. Na mapˇe skladu (obrázek ??) zobrazené na stranˇe ?? v Neveˇrejné cˇ a´ sti to odpov´ıdá vodorovnym regály. ´ mezerám mezi zˇ lutymi ´ Pod pojmem ”uliˇcka”budou spadat i regály, které ji obklopuj´ı, budeme napˇr´ıklad hovoˇrit o binech nebo materiálu, které jsou ve stejné ”uliˇcce”. Cesty, které jednotlivé uliˇcky spojuj´ı, budu nazyvat spojovac´ı cesty. Dále nebudeme brát v potaz ´ patra skladu, jelikoˇz je z pohledu nejkratˇs´ı trasy naprosto lhostejné ve kterém patˇre se materiál k vyzvednut´ı nacház´ı, vysokozdviˇzny´ voz´ık mus´ı zastavit na stejném m´ıstˇe pˇri vyzvednut´ı materiálu z tˇret´ıho i pátého patra. Vˇsechny patra tedy slouˇc´ıme do jednoho ”pˇr´ızem´ı”, kde budeme problém rˇ eˇsit. Pokud bude ˚ e materiály uloˇzené ve pˇri vysledn´ em sestavován´ı poˇrad´ı binu˚ nutné nabrat ruzn´ ´

24

˚ ych skladu v ruzn ´ patrech nad sebou, naberou se tyto materiály tˇesnˇe po sobˇe v ˚ nebo pˇr´ıpadnˇe v takovém, které nejv´ıce vyhovuje obsluze poˇrad´ı od shora dolu, vysokozdviˇzného voz´ıku. Zde nen´ı moˇzné nijak systematicky uˇsetˇrit cˇ as. Problém, tak jak jsme ho uvedli v kapitole 2, je tˇreba pˇrevést do rˇ eˇci teorie ˚ abychom mˇeli jednoznaˇcnˇe danou strukturu, se kterou budeme pracovat. grafu, Budeme-li hledat graf, ktery´ by situaci skladu dobˇre interpretoval, prvn´ı co nás pravdˇepodobnˇe napadne, bude reprezentovat kaˇzdy´ bin ve skladu vrcholem a jednotlivé uliˇcky a spojovac´ı cesty vedouc´ı od jednoho binu k druhému, hranami. T´ım z´ıskáme graf, ktery´ celkem vystiˇ ´ znˇe popisuje dany´ sklad, obrázek grafu je uveden v neveˇrejné kapitole 9 na stranˇe ??. Pokud na nˇem budeme cht´ıt dany´ problém rˇ eˇsit, budeme postupovat tak, zˇ e si oznaˇc´ıme vrcholy, které reprezentuj´ı biny s materiálem k vyzvednut´ı. Tyto oznaˇcené vrcholy potom budou tvoˇrit povinné zastávky obchodn´ıho cestuj´ıc´ıho, ktery´ bude grafem cestovat. Nevyhoda ´ tohoto pˇr´ıstupu spoˇc´ıvá v zm´ınˇené sloˇzitosti problému obchodn´ıho cestuj´ıc´ıho ˚ pro graf s velkym ´ poˇctem vrcholu. Pokud se ale v objednávce vyskytnou poˇzadavky na materiál, ktery´ je uloˇzen ˚ zeme takovéto v binech ve stejné uliˇcce bl´ızko sebe, nebo se nacház´ı naproti, muˇ biny slouˇcit do jednoho vrcholu s konstatován´ım, zˇ e se doupouˇst´ıme urˇcitého ˚ zjednoduˇsen´ı. Slouˇcen´ım v´ıce binu˚ do jednoho vrcholu zpusob´ ıme, zˇ e vˇsechen materiál z objednávky nacházej´ıc´ı se v binech slouˇcenych do jednoho vrcholu ´ bude nabrán spoleˇcnˇe, v poˇrad´ı které budeme specifikovat dále. To sebou pˇrinásˇ´ı jednu velkou vyhodu a to, zˇ e v rámci hledán´ı optimáln´ıho poˇrad´ı binu˚ povaˇzuju ´ vˇsechny biny slouˇcené do jednoho vrcholu za jeden jediny, ´ a navˇst´ıvit jakykoliv ´ ˚ ze z nich znamená navˇst´ıvit vˇsechny. Vyvstává otázka, zda toto zjednoduˇsen´ı muˇ vnést do rˇ eˇsen´ı urˇcitou chybu. Pokud jde o pˇr´ıpad, kdy se dva biny nacházej´ı v jedné uliˇcce naproti sobˇe, tak jejich slouˇcen´ım se zˇ a´ dné chyby nedopouˇst´ıme, vysokozdviˇzny´ voz´ık mus´ı v kaˇzdém pˇr´ıpadˇe pˇrijet na stejné m´ısto, kde se posléze otoˇc´ı doleva cˇ i doprava, coˇz trvá stejnou dobu. Pˇri zpˇetném sestavován´ı poˇrad´ı binu˚ tedy nen´ı nutné brát v potaz, ve kterém ze dvou regálu˚ ohraniˇcuj´ıc´ı uliˇcku se materiál nacház´ı. Pokud jde o pˇr´ıpad, kdy se biny nacházej´ı v jedné uliˇcce ˚ zeme byt bl´ızko sebe, ale uˇz ne naproti sobˇe, je situace sloˇzitˇejˇs´ı a zde si jiˇz nemuˇ ´ jisti, zˇ e se nedopust´ıme drobné chyby. Vzhledem k tomu, zˇ e optimáln´ı rˇ eˇsen´ı jistˇe nebude obsahovat cestu, kde se budeme vracet na jiˇz navˇst´ıvená m´ısta pro ”zapo˚ zeme oˇcekávat, zˇ e tato pˇr´ıpadná chyba bude zanedbatelná, menuty”materi´ al, muˇ ´ a d´ıky vyˇ e klesne poˇcet vrcholu˚ v grafu ´ se popsanému zjednoduˇsen´ı nám vyraznˇ ´ reprezentuj´ıc´ı sklad a t´ım i vypoˇ ´ cetn´ı sloˇzitost celého problému. ˚ zeme na mapˇe skladu Tuto moˇznost sjednocen´ı binu˚ do jednoho vrcholu muˇ provést na v´ıce m´ıstech s ohledem na rozm´ıstˇen´ı binu˚ ve skladu. Vhodnym ´ pˇr´ıkladem jsou uliˇcky, které maj´ı pouze jeden vstup, ktery´ je tˇreba pouˇz´ıt také i pro ˚ zeme opuˇstˇen´ı uliˇcky, jelikoˇz druhy´ konec tvoˇr´ı stˇena. V takovém pˇr´ıpadˇe muˇ vˇsechny biny z této uliˇcky reprezentovat jedn´ım vrcholem, a v pˇr´ıpadˇe, kdy se

25

z jakéhokoliv z tˇehto binu˚ nabere materiál, naberou se pˇri této zastávce i vˇsechy materiály z ostatn´ıch binu˚ v této uliˇcce, jsou-li nˇejaké obsaˇzeny v objednávce. Je zˇrejmé, zˇ e do takovéto uliˇcky nen´ı za zˇ a´ dnych okolnost´ı vyhodn´ e vracet se ´ ´ podruhé. U uliˇcky se dvˇema vstupy/vystupy uˇz tomu tak sice byt ´ ´ nemus´ı, ale zahrneme-li do uváhy manévr, ktery´ mus´ı obsluha vysokozdviˇzného voz´ıku provést, aby do uliˇcky zatoˇcila a následnˇe z n´ı vyjela (pˇri vyjezdu z uliˇcky je rovnˇezˇ ´ ˚ mu˚ potˇreba dávat pozor, aby nedoˇslo ke kolizi dvou vysokozdviˇznych ´ voz´ıku), zˇ eme si situaci ulehˇcit t´ım, zˇ e i biny z takovéto uliˇcky sjednot´ıme do jednoho ˇ sen´ı nalezené v zjednoduˇseném grafu potom sice nemus´ı byt vrcholu. Reˇ ´ nejlepˇs´ı moˇzné co se celkové vzdálenosti tyˇ ´ ce, pˇredpokládáme vˇsak, zˇ e bude cˇ asovˇe vyhodnˇ ejˇs´ı nebo rovnocené. Zásadn´ı vyhodou tohoto pˇr´ıstupu ovˇsem je, zˇ e vy´ ´ ´ znamnˇe sn´ızˇ ´ı poˇcet vrcholu˚ v grafu, kterym ´ budeme sklad reprezentovat. T´ım dojde ke sn´ızˇ en´ı cˇ asové nároˇcnosti algoritmu. Nyn´ı se pod´ıváme na kostrukci grafu, ktery´ pro nás bude pˇredstavovat model reprezentuj´ıc´ı sklad. Jelikoˇz tento graf budeme kostruovat v závislosti na mapˇe skladu, bude tato cˇ a´ st uvedena v neveˇrejné kapitole 9. Vysledn y´ graf, zobrazen na Obrázku 15, je vhodnym ´ ´ zjednoduˇsuj´ıc´ım modelem skladu. Strukturu skladu a pohyb mezi ”biny”jeˇstˇe dobˇre popisuje podle ˚ skuteˇcnosti, ale jen s vyuˇzit´ım minimáln´ıho poˇctu vrcholu. ˚ vyuˇzijeme postupu, kterym Pˇri zpˇetném sestavován´ı vysledn´ eho poˇrad´ı binu, ´ ´ jsme sestavovali model skladu. Jelikoˇz kaˇzdy´ vrchol v grafu reprezentuj´ıc´ı sklad obsahuje vˇzdy pouze biny z jedné uliˇcky, která má jeden pˇr´ıpadnˇe dva vstupy/vystupy, je vˇzdy jedna z moˇznost´ı nabrat materiál zleva doprava (podle cˇ ´ısla ´ pozice binu v uliˇcce vzestupnˇe) nebo zprava doleva (podle cˇ ´ısla pozice binu v uliˇcce sestupnˇe) optimáln´ı. Vybˇ ´ er jedné z moˇznost´ı je závisy´ na um´ıstˇen´ı pˇredchoz´ıho vrcholu v optimalizovaném poˇrad´ı. Nacházel-li se pˇredchoz´ı vrchol na obrázku 15 vpravo od aktuáln´ıho, procház´ıme biny v sestupném poˇrad´ı, jinak procház´ıme biny ve vzestupném poˇrad´ı.

26

Obrázek 15: Zjednoduˇseny´ graf popisuj´ıc´ı situaci ve skladu. Tento graf budeme pouˇz´ıvat jako model reprezentuj´ıc´ı sklad.

27

6

Optimalizace

Nyn´ı si ukázˇ eme algoritmus, pomoc´ı kterého budeme cestu ve skladu optimalizovat. Zde by bylo vhodné zm´ınit, zˇ e pro deterministicky´ algoritmus je zcela zásadn´ı volba modelu reprezentuj´ıc´ı sklad, o cˇ emˇz jsme pojednávali v podkapitole 5.4. Model mus´ı byt ´ dostateˇcnˇe zjednoduˇsuj´ıc´ı a souˇcasnˇe pokryt ´ vˇsechny ˚ zité aspekty pro hledán´ı skuteˇcné, fyzicky existuj´ıc´ı optimáln´ı trasy. Tˇemto duleˇ ˚ bude zajisté vyhovovat v´ıce modelu. ˚ My jsme, po peˇclivé uváze, zvolili kritérium model reprezentuj´ıc´ı sklad grafem na obrázku 15. V této kapitole nejdˇr´ıve pop´ısˇ eme vlastn´ı funguj´ıc´ı program s konkrétn´ımi ˚ Poté si pˇribl´ızˇ ´ıme algoritmus v obecné návrhy na rˇ eˇsen´ı nˇekterych problému. ´ podobˇe tak, aby mohl byt ´ implementovám v jakémkoliv programovac´ım jazyce. Pˇri implementaci algoritmu jsme vycházeli z myˇslenky Christofidova algoritmu, ˚ popsaném v podkapitole 4.1.2, a pˇrizpusobili jsme ho naˇs´ı konkrétn´ı situaci.

6.1

Implementace Algoritmu

Pro vlastn´ı potˇrebu autora diplomové práce vznikal postupnˇe program rˇ eˇs´ıc´ı optimalizaci cesty v konkrétn´ım modelu skladu na reálnych datech zaslanych ´ ´ ¨ firmou Molnlycke Health Care. Ukázka vstupn´ıch dat je pˇriloˇzena v kapitole 9 na stranˇe ??. Vstupn´ı data osahovala nˇekolik objednávek, kaˇzdá sestávaj´ıc´ı z nˇekolika komponent, kterym ´ bylo pˇriˇrazeno cˇ ´ıslo binu, kde se maj´ı vyzvednout. Vstupn´ı hodnoty tedy reprezentovaly body na mapˇe skladu. Oˇcekávany´ vystup ´ potom mˇel obsahovat seˇrazen´ı binu˚ podél nejkratˇs´ı cesty pro kaˇzdou objednávku. Pˇr´ıklad vystupn´ ıch dat je rovnˇezˇ v kapitole 9. ´ c pouˇzit´ım bal´ıku˚ MatProgram byl implementován v softwaru MATLAB⃝s graph [6] a grTheory [7] pro práci s grafy a grafovymi algoritmy. Tento software ´ ˚ byl vybrán z duvodu, zˇ e jiˇz s n´ım byl autor práce dˇr´ıve seznámen, algoritmus samotny´ je moˇzné implementovat v libovolném programovac´ım jazyce. ˇ Nejdˇr´ıve bylo potˇreba vytvoˇrit graf G (obrázek 15 na stranˇe 26), onen zminovany´ model skladu, se kterym budeme d´ a le pracovat, ´ g=graph; %mrizka 22x6 (cesta krat cesta) grid(g,22,6) ; %odstranime hrany a vrcholy ktere do grafu nepatri a=[67,89,111]; b=5:22; c=27:44; d=53:66; r=[a,b,c,d ]’;

28

delete(g,r ) ; o1=38:57; o2=39:58; O=[o1’,o2 ’]; delete(g,O); p1=5:7; p2=6:8; P=[p1’,p2 ’]; delete(g,P); L=[11,18;12,19;14,21;15,22]; delete(g,L);

Vypis 1: vytvoˇr´ı graf uvedeny´ na obrázku 16. ´

Obrázek 16: Graf reprezentuj´ıc´ı sklad (vykreslen v MATLABu). a sestavit matici D délek najkratˇs´ı cesty, Di,j = ρ(i, j),

29

kde ρ je metrika zavedená v definici 4.1 resp. 4.2 na stranˇe 17. Uloˇzit si matici ˚ V algoritmu budeme cˇ asto D je vyhodn´ e i pˇres to, zˇ e obsahuje |(V (G))|2 prvku. ´ potˇrebovat zjistit vzdálenost dvou vrcholu˚ a v takovém pˇr´ıpadˇe bude staˇcit vybrat pˇr´ısluˇsny´ prvek z matice D. D=dist(g);

Vypis 2: vytvoˇr´ı matici D. ´ ¨ Naˇcteme data zaslaná firmou Molnlycke Health Care, resp. pouze tu cˇ a´ st dat kterou budeme pro násˇ algoritmus potˇrebovat. Jedná se o tˇri sloupce ze souboru.xls obsahuj´ıc´ı cˇ ´ıslo objednávky, poˇrad´ı poloˇzky v rámci objednávky a um´ıstˇen´ı poloˇzky ve skladu uveden´ım binu. Na obrázku ?? v neveˇrejné cˇ a´ sti – kapitola 9 jsou pˇr´ısluˇsné sloupce oznaˇceny barevnˇe. [L1,L2,L3]=nactip(’VstupniData.txt’ ) ;

Vstupn´ı data se naˇc´ıtaj´ı z textového souboru, do kterého jseme si dˇr´ıve uloˇzili zm´ınˇené tˇri sloupce dat. Kaˇzdy´ ze sloupcu˚ si uloˇz´ıme jako vektor cˇ ´ısel, resp. ˚ znaku. function[objednavka,poradi,bin] = nactip( pickinglist ) % funkce nacte picking list fid = fopen( pickinglist ) ; mydata = textscan(fid, ’ %n %n %s’); fclose( fid ) ; objednavka=mydata{1}; poradi=mydata{2}; bin=mydata{3};

Vypis 3: funkce pro naˇcten´ı dat. ´ Nyn´ı naˇctená data projdeme, oddˇel´ıme od sebe jednotlivé objednávky, a pro ˚ My kaˇzdou objednávku poté provedeme optimalizaci poˇrad´ı uvedenych binu. ´ jsme pouˇzili následuj´ıc´ı jednoduchy´ postup u kterého jsme nav´ıc kontrolovali zda se nejedná o posledn´ı poloˇzku seznamu. %seznam vrcholu grafu g, ktere musime projit v ramci jedne objednavky u =[]; %seznam binu v ramci jedne objednavky ubin={}; %pocet polozek v nactenem seznamu delkapickinglistu =length(L1); %ukazatel v ramci objednavky cislo polozky=1; for ukazatel=1:delkapickinglistu if ukazatel == delkapickinglistu %vypise se vse co zbyva %podobny postup jako v casti else s jednim volanim optimalizace zapis navic.

30

else if L2(ukazatel)==cislo polozky %do objednavky se vlozi dalsi polozka polozka=L3(ukazatel); u(cislo polozky )=bin(polozka{1}); ubin(cislo polozky )=L3(ukazatel); %cislo polozky se zvysi o 1 cislo polozky=cislo polozky+1; else %ulozi cislo zkompletovane objednavky obj=L1(ukazatel−1); % zavola cast programu pro optimalizaci a zapis do souboru optimalizace zapis % vzmaze stavajici hodnoty, priprava pro novou objednavku u =[]; ubin={}; ret=L3(ukazatel); % vlozi prvni polozku do nove objednavky u(1)=bin(ret{1}); ubin(1)=L3(ukazatel); %nastavi ukazatelatel na druhou polozku cislo polozky=2; end end end

Vypis 4: procházen´ı naˇctenych ´ ´ dat. Pˇri procházen´ı dat jsme pro kaˇzdou objednávku vytvoˇrili seznam vrcholu˚ ˚ u, jehoˇz prvky odpov´ıdaj´ı vrcholum, které je pˇri kompleteci objednávky tˇreba ˚ které tento vrchol reprezentuje, obsahuj´ı navˇst´ıvit, jelikoˇz jeden nebo v´ıce binu, poloˇzku z objednávky. Seznam vrcholu˚ u obsahuje cˇ ´ısla, pomoc´ı kterych ´ je moˇzno jednoznaˇcnˇe identifikovat vrchol z grafu G pomoc´ı obrázku 16 (v algoritmu se k vrcholu pˇristupuje pˇr´ımo pˇres cˇ ´ıslo, pod kterym ´ je ve struktuˇre grafu uloˇzen). Pˇri naˇcten´ı a následném rozdˇelen´ı dat jsem mˇeli k dispozici pouze seznam ˚ tak jak nám ho poskytla firma Molnlycke ¨ binu, Health Care, viz obrázek ?? v neveˇrejné cˇ a´ sti na stranˇe ??. Ukázˇ eme si, jak jsme v algoritmu vyˇreˇsili cˇ a´ st, kterou jsme popsali v podkapitole 5.4, kdy pod jeden vrchol v námi zvolené modelové ˚ Pro tento uˇ ´ cel je potˇreba sestavit urˇcity´ pˇrekladaˇc, ktery´ situaci spadá v´ıce binu. zadanému binu bude schopen pˇriˇradit vrchol (ˇc´ıslo vrcholu), ktery´ tento bin v naˇsem modelu reprezentuje. Problém zpˇetného pˇrekladu pak jiˇz nen´ı tˇreba rˇ eˇsit, nebot’ právˇe rozdˇelen´ı binu˚ do jednotlivych ´ vrcholu˚ bylo konstruováno tak, aby v rámci jednoho vrcholu bylo moˇzné seˇradit biny jen podle jejich uspoˇra´ dán´ı v uliˇcce. Pˇrekladaˇc v tuto chv´ıli pˇrekládá jen biny, které jsou zadány ve formátu sklad uliˇcka – patro – pozice v uliˇcce. V pickinglistu se vyskytuj´ı i biny v jiném

31

formátu (zbytkové zboˇz´ı), ty ale bez pˇresné znalosti m´ısta uloˇzen´ı, které v tuto chv´ıli nemáme k dispozici, nemohou byt ´ do optimalizace zaˇrazeny. function[n] = bin(s) %funkce vraci cislo vrcholu reprezentujici zadany bin s % vstup −− s retezec znaku % vystup −− n cislo vrcholu

Vypis 5: funkce pˇriˇrad´ı binu vrchol grafu G. (funkˇcn´ı verze funkce je uvedena na ´ konci neveˇrejné cˇ a´ sti práce) V tuto chv´ıli máme pˇripraveny´ jak graf G, matici D obsahuj´ıc´ı vzdálenosti ˚ které potˇrebujeme navˇst´ıvit. jednotlivych ´ vrcholu˚ grafu G tak i seznam vrcholu, Nejdˇr´ıve si ukázˇ eme cˇ a´ st programu, která zapisuje vysledek do vystupn´ ıho sou´ ´ ˚ zitˇejˇs´ı cˇ a´ sti optimalizace, kterou tato cˇ a´ st volá. boru, poté pˇrejdeme k nejduleˇ ´ Následuj´ıc´ı cˇ a´ st zdrojového kodu zapisuje optimálnˇe seˇrazené biny z jednotlivych objednávek do souboru ”output2.txt”. Pro kaˇzdou objednávku vytiskne ´ jej´ı cˇ ´ıslo a v pˇr´ıpadˇe, zˇ e je poˇcet vrcholu˚ k optimalizaci5 alesponˇ 3 (1 nebo 2 vrcholy nen´ı tˇreba optimalizovat, jakékoliv ”poˇrad´ı je optimáln´ı”) zavolá funkci, ˚ podle kterého se potom vyp´ısˇ ou biny do která nalezne optimáln´ı poˇrad´ı vrcholu, vystupn´ ıho souboru. ´ %Otevre soubor pro zapis file 2 = fopen(’output2.txt ’ , ’ a’ ) ; %Vytiskne cislo aktualni objednavky fprintf ( file 2 , ’ −−−−−−−−−−−OBJEDNAVKA %d −−−−−−−−−−\n’,obj); %Vytiskne biny z objednavky for i =1:length(ubin) fprintf ( file 2 , ’ o %s \n’,ubin{i}); end %Vytiskne vstupni vektor s vrcholy ktere se maji navstivit for j =1:length(u) fprintf ( file 2 , ’ %d ’,u(j ) ) ; end %Ulozi puvodni poradi vrcholu uu=u; vysledneporadi=[]; %Seradi vrcholy podle prirazenych cisel, odstrani duplicity a pripadne %hodnoty 0. u=unique(u); if u(1)==0 u=u(2:length(u)); end %Overeni vstupnich podminek %Pokud mame na vstupu 1 nebo 2 vrcholy, jsou uz optimalne serazene. if length(u)<3 5

˚ Ve skuteˇcnosti by staˇcilo optimalizovat poˇrad´ı 4 a v´ıce vrcholu.

32

fprintf ( file 2 , ’ NIZKY−POCET−VRCHOLU \n’); fprintf ( file 2 , ’ vysledne poradi vrcholu je:\n’); fprintf ( file 2 , ’ −− %d’,u); vysledneporadi=u; %Jinak se zavola funkce pro optimalizaci else %zavola funkci ktera najde optimalni poradi vrcholu %vstup funkce je graf g, matice vzdalenosti D a vektor vrcholu u. [poradi,delka,cas] = optimalizace(g,D,u); fprintf ( file 2 , ’ ooo−−−−−−DIPLOMOVA−PRACE−−−−−−−ooo\n’); fprintf ( file 2 , ’ vysledne poradi vrcholu je: \n’) ; fprintf ( file 2 , ’ −− %d’,poradi); fprintf ( file 2 , ’ delka je: %d \n’,delka); fprintf ( file 2 , ’ cas nalezeni: %d \n’,cas); vysledneporadi=poradi; % pokud je vrcholu mene nez 8 (jinak by jsme cekali prilis dlouho) % muzeme nasi funkci porovnat s funkci TSP pro nalezeni cesty % obchodniho cestujiciho, ktera je implementovana v toolboxu grTheory if length(u)<8; [TSPporadi,TSPdelka,TSPcas] = najdi tsp(D,u); fprintf ( file 2 , ’ o−−−−−−−−−TSP−MATLAB−−−−−−−−−o\n’); fprintf ( file 2 , ’ vysledne poradi TSP je: \n’); fprintf ( file 2 , ’ −− %d’,TSPporadi); fprintf ( file 2 , ’ delka TSP je: %3.1f \n’,TSPdelka); fprintf ( file 2 , ’ cas nalezeni TSP: %d \n’,TSPcas); %a pokud by se vysledne delky tras odlisovaly, upozornime na to. if (int32 (mdelka)) ˜= (int32 (TSPdelka)) fprintf ( file 2 , ’ POZOR−DELKY JSOU RUZNE \n’); end end end %Nyni zname poradi vrcholu a potrebujeme jeste vysledne poradi binu. count=1; listbin ={}; %Seradime je podle poradi vrcholu a jeste v ramci ulicky , %posledni dve cisla binu udavaji jeho pozici v ulicce . for i =1:length(vysledneporadi) sprvni={}; bprvni =[]; pozicevrcholu=find(uu==vysledneporadi(i)); for j =1:length(pozicevrcholu) sprvni{j}=ubin{pozicevrcholu(j)}; end for jj =1:length(pozicevrcholu) a bin=sprvni{ jj }; bprvni(k)=((10∗(str2double(a bin(7)) ) )+(str2double(a bin(8)) ) ) ; end [A,X]=sort(bprvni); for jjj =1:length(pozicevrcholu)

33

listbin {count}=sprvni{X(jjj ) }; count=count+1; end end % vypiseme vysledne poradi binu. fprintf ( file 2 , ’ Vysledne poradi binu je: \n’); for i =1:length( listbin ) %s \n’, listbin {i }) ; fprintf ( file 2 , ’ x end fclose( file 2 ) ;

Vypis 6: vytiskne poˇzadovany´ vysledek optimalizace do souboru ´ ´ ´ Uvedená cˇ a´ st 6 zdrojového kodu v jedné fázi volá funkci najdi_tsp, která pˇriprav´ı vstupn´ı parametry pro funkci TSP a tu poté zavolá. Funkce TSP, o které jsme zde jiˇz mluvili, je implementována v toolboxu grTheory a pouˇz´ıvali jsme ji k porovnán´ı vysledk u˚ s naˇsim algoritmem. Funkce najdi_tsp byla volána jen ´ v pˇr´ıpadˇe, zˇ e byl poˇcet vrcholu˚ které je tˇreba proj´ıt, menˇs´ı neˇz 8, jinak by se na vysledek této funkce cˇ ekalo pro kaˇzdou objednávku i nˇekolik minut. ´ function [pTS,fmin]=TravSalePro(C) % Function [pTS,fmin]=grTravSale(C) solve the nonsymmetrical % traveling salesman problem. % Input parameter: % C(n,n) − matrix of distances between cities, % maybe, nonsymmetrical; % n − number of cities. % Output parameters: % pTS(n) − the order of cities ; % fmin − length of way. % Uses the reduction to integer LP−problem: % Look: Miller C.E., Tucker A. W., Zemlin R. A. % Integer Programming Formulation of Traveling Salesman Problems. % J.ACM, 1960, Vol.7, p. 326−329. % Author: Sergii Iglin % e−mail: [email protected] % personal page: http :// iglin .exponenta.ru

Vypis 7: komentárˇ k funkci TSP ´ Nyn´ı se uˇz koneˇcnˇe pod´ıváme na samotnou funkci optimalizace, která zadany´ problém rˇ eˇs´ı a hledá optimáln´ı poˇrad´ı vrcholu˚ zadanych ´ ve vektoru u. Funkce optimalizace poˇzaduje jako vstupn´ı hodnoty graf G, reprezentuj´ıc´ı model skladu, matici D, s délkou nejkretˇs´ı (i, j)-cesty v grafu G uloˇzenou v i-tém sloupci a j-tém rˇ a´ dku a seznam vrcholu˚ které je tˇreba navˇst´ıvit. Vystupn´ ı ´ ˚ celková délka trasy a doba bˇehu hodnoty jsou potom optimáln´ı poˇrad´ı vrcholu, algoritmu. Funkce optimalizace pouˇz´ıvá funkce implementované v toolboxu grTheory

34

grMinSpanTree() funkce pro nalezen´ı minimáln´ı kostry. Algoritmy pro nalezen´ı minimáln´ı kostry jsme diskutovali v podkapitole 5.1 grMaxMatch() funkce pro nalezen´ı maximáln´ıho párován´ı. Minimáln´ı párován´ı ˚ zeme z´ıskat pomoc´ı párován´ı maximáln´ıho, pokud od pevnˇe zvolené muˇ konstanty odeˇcteme hodnotu hran. Problém minimáln´ıho párován´ı jsme diskutovali v podkapitole 5.2 euler trail() funkce pro nalezen´ı eulerovského tahu. Eulerovsky´ tah jsme probrali v podkapitole 5.1 function[u poradi,delka,cas] = optimalizace(g,D,u) %−−−−−−−−vystupy %poradi=vysledne poradi vrcholu. %delka= celkova delka trasy. %cas=doba trvani algoritmu. %−−−−−−−−vstupy %g−graf g, sklad. %D−matice vydalenosti. %u−vektor obsahujici cisla vrcholu, ktere se maji navstivit . %zacneme merit cas tic ; l =length(u); %vytvori matici E, ktera reprezentuje hrany kompletniho grafu na %vrcholech z vektoru u. %Kaydy radek matice E reprezentuje jednu hranu. %V prvnich dvou sloupcich jsou ulozeny koncove vrcholy hrany ve tretim %sloupci je potom delka teto hrany odpovidajici delce cesty ve skladu. E=zeros((l∗(l−1)/2),3) ; c=1; for i =1:( l −1) for j =(1+i) : l E(c,1)=u(i ) ; E(c,2)=u(j ) ; E(c,3)=D(u(i) ,u( j ) ) ; c=c+1; end end %Najde minimalni kostru k kompletniho grafu na vrcholech u, s ohodnocenymi %hramami podle matice E. %Volame metodu z toolboxu grTheory, ktera najde minimalni kostru grafu, viz %Kruskaluv algoritmus v kapitole 5.1.1 t=grMinSpanTree(E); k=graph; copy(k,g); label (k) ; clear edges(k)

35

for q=1:(length(t)) fp=find path(g,E(t(q),1) ,E(t(q),2) ) ; for z=1:(length(fp)−1) add(k,fp(z) , fp(z+1)); end end %ulozi delku souctu hran v minimalni kostre k. mdel1=ne(k); %score grafu (minimalni kostry) k. stup=deg(k); %najdeme vrcholy licheho stupne. liche =[]; cc=1; for i =1:(length(stup)) if mod(stup(i),2)==1 liche (cc)=str2double(get label(k, i ) ) ; cc=cc+1; end end %Nyni budeme hledat minimalni uplne parovani na mnozine vrcholu L minimalni %kostry k, ktere jsou licheho stupne(tech bude sudy pocet). %Matice F reprezentuje hrany kompletniho grafu na vrcholech L. %V prvnich dvou sloupcich jsou ulozeny koncove vrcholy hrany ve tretim %sloupci je potom delka teto hrany odpovidajici delce cesty ve skladu. lll =length(liche); F=zeros(( lll ∗( lll −1)/2),3) ; ccc=1; for i =1:( lll −1) for j =(1+i) : lll F(ccc,1)=liche( i ) ; F(ccc,2)=liche( j ) ; F(ccc,3)=D(liche( i ) , liche ( j ) ) ; ccc=ccc+1; end end %Jelikoz budeme volat funkci pro nalezeni maximalniho parovani, ale my %potrebujeme parovani minimalni, odecteme stavajici hodnotu hran v matici F %od konstanty, my zvolime konstantu 30, a nasledne ziskane hrany parovani %budou tvorit minimalni parovani. fv=(size(F)) ; for s=1:(fv (1) ) F(s,3)=30−F(s,3); end %Volame metodu z toolboxu grTheory, ktera najde minimalni parovani. M=grMaxMatch(F); %ulozime hrany minimalniho parovani a secteme jejich delku, nezapomeneme ze %jsme predtim odecitali skutecnou hodnotu hran od konstanty 30. m=graph; copy(m,g);

36

label (m); clear edges(m) mdel2=0; for p=1:(length(M)) add(m,F(M(p),1),F(M(p),2)); mdel2=mdel2+(30−(F(M(p),3))); end %Vytvorime multigraf spojenim minimalni kostry k a minimalniho parovani m. eg=graph; copy(eg,k) union(eg,k,m); %Vznikly multigraf je sudy, nalezneme Eulerovsky tah. %Volame metodu z toolboxu grTheory, ktera najde Eulerovsky tah. Eporadi= euler trail (eg); %ziskame poradi hran, pomoci koncovych vrcholu techto hran dostaneme poradi %vrcholu v Eulerovskem tahu. poradi=Eporadi(:,1); %Nyni z poradi vrcholu odstranime ty vrcholy ktere nas nezajimaji, %to jsou ty ktere nebyly obsazeny ve vstupu u. u poradi =[]; f=1; for i =1:(length(poradi)) for j =1:(length(u)) if poradi( i )==ut(j ) u poradi( f )=mporadi(i); f=f+1; u( j )=0; end end end %secteme delku minimalni kostry a minimalniho parovani. delka=mdel1+mdel2; %ulozime jak dlouho algoritmus bezel. cas=toc;

Vypis 8: funkce vrát´ı optimáln´ı poˇrad´ı vrcholu˚ a celkovou délku trasy. ´ Vyˇ ´ se popsany´ program jsem otestoval na vstupn´ıch datech, která zaslala firma ¨ Molnlycke Health Care. Vstupn´ı data obsahovala 121 objednavek a na poˇc´ıtaˇci s procesorem Intel Core i5 3, 2GHz a 4GB RAM trval pˇribliˇrnˇe 9 sekund. Ve vˇsech pˇr´ıpadech, kdy se vysledek porovnával s vysledkem funkce TSP z toolboxu grThe´ ´ ory, byly délky navrhovanych ´ tras obou algoritmu˚ stejné.

37

6.1.1

ˇ ı Moˇzna´ vylepsen´

V nˇekterych ´ pˇr´ıpadech, nastane situace, kdy algoritmus najde takové rˇ eˇsen´ı, které se lidskému vn´ımán´ı nezdá pˇr´ıliˇs vhodné.

Obrázek 17: Pˇr´ıklad 8, 13, 50, 52, 48, 41.

diskutabiln´ıho

rˇ eˇsen´ı

s

nalezenym ´

poˇrad´ım

˚ A k tomuto rˇ eˇsen´ı cˇ asto existuje jiné, které je stejnˇe dlouhé jako puvodn´ ı, ˇ ale pro cˇ lovˇeka uˇz nen´ı tolik ”kontroverzn´ı”. Reˇsen´ı nalezené na obrázku 17 s ´ ych poˇrad´ım vrcholu˚ 8, 13, 50, 52, 48, 41 je sice v s´ıti pravouhl ´ uliˇcek správnˇe, je ale trochu nepˇr´ıjemné, zˇ e z trojice vrcholu˚ 48, 50, 52 nejdˇr´ıve jdeme do prostˇredn´ıho vrcholu 50 potom do vrcholu 52 a potom se ”vrac´ıme”do vrcholu 48. Mnohem pˇrirozenˇejˇs´ı by bylo navˇst´ıvit je popoˇradˇe 48, 50, 52 nebo pˇr´ıpadnˇe v poˇrad´ı obráceném. Na tomto m´ıstˇe vˇsak poznamenejme, zˇ e celková délka cesty bude ve vˇsech tˇehto pˇr´ıpadech stejná. Tento drobny´ problém nastává ve chv´ıli, kdy algoritmus hledá minimáln´ı párován´ı, které mnohdy nen´ı jednoznaˇcne urˇceno. V této chv´ıli bychom chtˇeli donutit algoritmus aby upˇrednostnoval nˇekterá rˇ eˇsen´ı

38

pˇred jinymi. Konkrétnˇe bychom chtˇeli, aby se v minimáln´ım párován´ı nevysky´ ´ tovaly pˇr´ıliˇs dlouhé hrany, které dovoluj´ı urˇcité useky, do kterych ´ je potom nutné ˚ zeme dosáhnout tak, zˇ e k extrémnˇe dlouhym se ”vracet”, pˇreskoˇcit. Toho muˇ ´ hranám pˇriˇcteme nˇejakou konstantu, která bude vyˇssˇ´ı neˇz konstanta pˇriˇctená k hranám kratˇs´ım. Celková hodnota konstanty by ale mˇela byt ´ niˇzsˇ´ı neˇz je nejratˇs´ı moˇzná délka hrany, tedy 1, abychom nemuseli hl´ıdat, zda jde skuteˇcnˇe jeˇstˇe o minimáln´ı párován´ı. Zde se nab´ız´ı pˇriˇc´ıst druhou mocnimu délky hrany (nejdelˇs´ı hrana má délku 27.) vydˇelenou 1000. V takovém pˇr´ıpadˇe budou zachovány vyˇ ´ se popsané poˇzadavky a algoritmus do minimáln´ıho párován´ı nevybere extrémnˇe dlouhé hrany. ´ Po této upravˇ e nám dá program následuj´ıc´ı rˇ eˇsen´ı, které uˇz je ”pocitovˇe”pˇrijatelné.

´ Obrázek 18: Nalezené rˇ eˇsen´ı po upravˇ e 8, 13, 52, 50, 48, 41.

39

6.2

Algoritmus

Nyn´ı uvedeme v obecné podobˇe algoritmus, ktery´ najde optimáln´ı poˇrad´ı zadanych ´ vrcholu˚ u, které reprezentuj´ı bin, nebo v´ıce binu˚ z objednávky. Algoritmus pracuje s modelem skladu (obrázek 15), ktery´ jsme odvodili v kapitole 5.4. Model skladu je stˇezˇ ejn´ı bod optimalizace, a kdyby byl navrˇzen jinak, nemusel by dále popsany´ algoritmus korektnˇe fungovat. Algoritmus 1. Algoritmus má dva vstupn´ı parametry: graf G, pˇredstavuj´ıc´ı model skladu a mnoˇzinu vrcholu u, coˇz jsou vrcholy, které v modelu reprezentuj´ı biny ze kterych ´ je potˇreba nabrat materiál pro objednávku, u ∈ V (G). 2. Sestav´ıme matici D délek kejkratˇs´ıch cest mezi vrcholy i, j ∈ V (G). Di,j = nejkratˇs´ı (i, j)-cesta v grafu G. 3. Vygenerujeme kompletn´ı graf Ku na u vrcholech a kaˇzdou hranu tohoto grafu ohodnot´ıme f ({i, j}) = Di,j , ∀{i, j} ∈ E(Ku ) ( pˇriˇrad´ıme hodnotu délky nejkratˇs´ı (i, j)-cesty v grafu G). 4. V grafu Ku nalezneme minimáln´ı kostru za pouˇzit´ı Kruskalova algoritmu, viz kapitola 5.1. 5. V grafu G nalezneme strom T , odpov´ıdaj´ıc´ı minimáln´ı kostˇre grafu Ku . Hrany minimáln´ı kostry pˇrevedeme na jim odpov´ıdaj´ıc´ı cesty v grafu G. Mnoˇzina hran E(T ) bude obsahovat sjednocen´ı hrany, které jsou souˇca´ st´ı tˇehto cest (duplicitn´ı hrany budou zahrnuty pouze jednou, nebude se jednat o multigraf). 6. Vrcholy lichého stupnˇe grafu T oznaˇc´ıme W , W ⊆ V (G). Poznamenejme, zˇ e podle principu sudosti bude tˇehto vrcholu˚ sudy´ poˇcet |W | ≡ 0 (mod 2). 7. Vygenerujeme kompletn´ı graf KW na W vrcholech a kaˇzdou hranu tohoto grafu ohodnot´ıme f ({i, j}) = Di,j , ∀{i, j} ∈ E(KW ). ( pˇriˇrad´ıme hodnotu délky nejkratˇs´ı (i, j)-cesty v grafu G) ´ 8. Nalezneme minimáln´ı upln´ e párován´ı M vrcholu˚ W na grafu KW . 9. Sjednocen´ım hran E(T ) a M dostaneme sudy´ multigaf H, ktery´ bude souvisly. ´ 10. Najdeme uzavˇreny´ Eulerovsky´ tah E.

40 11. Vrcholy u seˇrad´ıme podle jejich vyskytu v Eulerovském tahu E, pokud se ´ 6 vrchol v tahu nacház´ı v´ıcekrát , ponecháme pouze jeho prvn´ı vyskyt. ´ ˚ Vysledn´ T´ım z´ıskáme vysledn´ e poˇrad´ı vrcholu. e poˇrad´ı binu˚ potom z´ıskáme ´ ´ postupem, kdy procház´ıme vrcholy v nalezeném vysledném poˇrad´ı a u kaˇzdého vrcholu vyp´ısˇ eme vˇsechny biny, které dany´ vrchol pro danou objednávku re´ prezentuj´ı. Rozdˇelen´ı binu˚ do vrcholu˚ jsme pˇri tom konstruovali umyslnˇ e tak sˇ ikovnˇe, zˇ e pokud je pˇredchoz´ı vrchol ohodnocen niˇzsˇ´ım cˇ ´ıslem vypisujeme biny podle pozice v uliˇcce vzestupnˇe, pokud je pˇredchoz´ı vrchol ohodnocen vyˇssˇ´ım cˇ ´ıslem vypisujeme biny podle pozice v uliˇcce sestupnˇe. Ohodnocen´ı vrcholu˚ lze nalézt na obrázku 16 na stranˇe 28. Toto má nav´ıc vyznam jen pro vrcholy ´ 5, 6, 7, 8, 10, 13, 16, 17, 20, 23 a vrcholy 38 aˇz 58 kde jsou biny um´ıstˇené v uliˇcce do které je moˇzno vjet z obou stran. U vˇsech ostatn´ıch vrcholu˚ toto nehraje roli, jelikoˇz ve slepé uliˇcce je vˇzdy potˇreba dojet aˇz pro materiál, ktery´ je od vjezdu do uliˇcky nejvzdálenˇejˇs´ı, a po cestˇe zpˇet (nebo po cestˇe tam) nabrat postupnˇe materiál zbyvaj´ ´ ıc´ı.

6

˚ ze teoreticky nastat, napˇr´ıklad mezi skladem B a C jsou pouze tˇri pruchody ˚ Tato situace muˇ a je moˇzné, zˇ e nejvyhodnˇ ejˇs´ı bude pouˇz´ıt jeden z nich dvakrát. ´

41

7

´ er ˇ Zav

Tato diplomová práce rˇ eˇs´ı problém optimalizace trasy pro vyzvednut´ı jednot¨ Health Care. Pro zpracován´ı livych ´ poloˇzek ve skladu, zadany´ firmou Molnlycke ˚ erné (napˇr. diplomové práce poskytl zadavatel informace, které povaˇzuje za duvˇ ˚ mapa skladu) a nepˇreje si jejich zveˇrejnˇen´ı. Z tohoto duvodu je diplomová práce rozdˇelena na cˇ a´ st veˇrejnou a neveˇrejnou. Diplomová práce je koncipována tak, aby pˇr´ıpadny´ cˇ tenárˇ byl schopen pochopit námi zvoleny´ pˇr´ıstup k problému a jeho rˇ eˇsen´ı i bez pˇr´ıstupu k neveˇrejné cˇ a´ sti práce. V práci jsme zadany´ problém peˇclivˇe zformulovali a popsali jsme situaci ve ˚ a definic´ım z teorie grafu, ˚ skladu. Samostatnou kapitolu 3 jsme vˇenovali pojmum ˚ ehu celé práce pouˇz´ıvali a které byly potˇreba pˇri formulován´ı které jsme v prubˇ teoretického pˇr´ıstupu k problému. Navrhli jsme urˇcitá zobecnˇen´ı a zjednoduˇsili jsme teoreticky´ model zadaného praktického problému tak, aby obsahoval pouze informace maj´ıc´ı vliv na nalezen´ı nejkratˇs´ı trasy. Informace, které mˇeli zˇ a´ dny, ´ nebo zanedbatelny´ vliv na hledany´ vysledek, nebyly do modelu zahrnuty. Systém, ´ jakym pˇri optima´ byl model reprezentuj´ıc´ı sklad sestaven, má zásadn´ı vyznam ´ lizaci a tvoˇr´ı vyznamnou cˇ a´ st diplomové práce. Dále jsme si pˇredstavili problém ´ obchodn´ıho cestuj´ıc´ıho a aproximaˇcn´ı algoritmy, které ho rˇ eˇs´ı. Nakonec jsme popsali algoritmus pro rˇ eˇsen´ı zadaného problému a s pouˇzit´ım cˇ a´ st´ı zdrojového c popsali postup jeho implementace. ´ kodu aplikace, psané v jazyce MATLAB⃝, c která pro zadanou objednávku najde optimáln´ı Aplikace v jazyce MATLAB⃝, ˚ nen´ı souˇca´ st´ı této práce s ohledem na skuteˇcnost, zˇ e firma Moln¨ poˇrad´ı binu, ˚ ernych lycke Health Care projevila zájem o nezveˇrejnˇen´ı duvˇ ´ informac´ı, které jsou ´ v nˇekterych obsaˇzeny. Mimo to, vlastn´ı aplikace nebyla ´ cˇ a´ stech zdrojového kodu zamyˇ této diplomové práce, sp´ısˇ e slouˇzila k odzkouˇsen´ı navrho´ slena jako vystup ´ vaného algoritmu a zjiˇstˇen´ı pˇribliˇzné doby bˇehu algoritmu na reálnych ´ vstupn´ıch datech, coˇz se podaˇrilo. C´ıle práce bylo dosaˇzeno s konstatován´ım, zˇ e zvoleny´ algoritmus negarantuje sice nalezen´ı naprosto nejkratˇs´ı cesty, ale pˇri testován´ı na datech z reálného provozu, byly délky vˇsech nalezenych ´ tras shodné s délkami tras, které naˇsel TSP algoritmus implementovany´ v toolboxu MATLABu [7]. Doba bˇehu obou algoritmu˚ byla sice pro objednávky obsahuj´ıc´ı maly´ poˇcet komponent rˇ a´ dovˇe stejná, uˇz vˇsak pro objednávky s poˇctem a um´ıstˇen´ım jednotlivych ´ komponent tak, zˇ e ˚ ych je nutné navˇst´ıvit pˇribliˇznˇe deset ruzn m´ıst ve skladu, nacház´ı námi navr´ ˇ hovany´ algoritmus rˇ eˇsen´ı v rˇ a´ du sekund, zat´ımco zminovan y´ TSP algoritmus v rˇ a´ du minut. Uˇzit´ı navrhovaného algoritmu samozˇrejmˇe nen´ı nijak vázáno na c stejné vysledky ˚ zeme oˇcekávat v libovolném prograsoftware MATLAB⃝a muˇ ´ movac´ım jazyce. Samotná implementace algoritmu je dle dohody v kompetenci ¨ firmy Molnlycke Health Care, protoˇze bude souˇca´ st´ı jejich stávaj´ıc´ıho softwaru.

42

Tato práce také ukazuje praktické vyuˇzit´ı teorie grafu˚ pˇri rˇ eˇsen´ı reálného pro˚ blému v prumyslu a moˇznost spolupráce akademické obce se soukromym ´ sekto¨ rem. Na tuto spolupráci se dá v pˇr´ıpadˇe zájmu Molnlycke Health Care navázat s návrhem lepˇs´ı organizace uloˇzen´ı komponent ve skladu, aby se minimalizovaly délky tras pˇri kompletaci objednávek.

43

8

Literatura

ˇ [1] P. K OV A´ Rˇ , Teorie grafu˚ (uˇcebn´ı text), VSB-TU Ostrava, 2012. ´ [2] D. L. A PPLEGATE , R. E. B IXBY, V. C HV ATAL , W. J. C OOK , The Traveling Salesman Problem: A Computational Study, Princeton University Press, 606pp, 2006. [3] W. J. C OOK , In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012. [4] J. B. K RUSKAL , J R ., On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 1956. ˇ ERN Y´ , Základn´ı grafové algoritmy. KAM, MFF UK - Praha, 2010, Verze [5] J. C 0.95. [6] E. S CHEINERMAN , Matgraph –matlab toolbox for working with simple, undirected graphs. 2008 (pouˇzitá verze 2012). http://www.ams.jhu.edu/ ers/matgraph/ [7] S. I GLIN , grTheory –Graph Theory Toolbox with functions for different tasks of c 2003 (pouˇzitá verze 2012). graph theory for MATLAB⃝, [8] L. G ODDYN , Edmonds’ Minimum Weight Perfect Matching Algorithm, Math 408, 2012. http://people.math.sfu.ca/ goddyn/Courseware/edmonds.pdf [9] H. G ABOW, An Efficient Implement at ion of Edmonds’ Maximum – Matching Algorithm, Stanford University, 1972 (Technical Report No. 31). ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/72/328/CS-TR-72328.pdf [10] Algoritmy.net [online], Problém obchodn´ıho cestuj´ıc´ıho, 2012. Dostupné z: http://www.algoritmy.net/article/5407/Obchodni-cestujici ˇ [11] P. K OV A´ Rˇ , On Magic Graph Labelings, Ph.D. Thesis, VSB-TU Ostrava, 2004. [12] R. E. B URKARD et al. , Well-solvable special cases of the traveling salesman problem: a survey, Society for Industrial and Applied Mathematics, Vol. 40, No. 3, 1998.

44

9

´ Neveˇrejna´ cˇ ast

Tato verze diplomové práce je veˇrejná a s ohledem na to v této verzi nejsou ¨ um´ıstˇené citlivé informace firmy Molnlycke Health Care. Veˇskeré informace, na které se odkazujeme v textu vyˇ ´ se, jsou uvedené v neveˇrejné verzi diplomové práce.

Optimalizace cest ve skladu Optimal routes in a storehouse

Recommend Documents