CLARKEOVA-WRIGHTOVA METODA ŘEŠENÍ ÚLOHY VRP 1. Definice úlohy Úloha VRP (Vehicle Routing Problem – problém okružních jízd) je definována na obecné dopravní síti S = (V,H), kde V je množina uzlů sítě a H množina hran spojujících tyto uzly. Uzel V0 je označován jako středisko této sítě a uzly V1,…,Vn představují místa odběru (místa vyžadující obsluhu). V místech odběru vzniká požadavek na přepravu určitého množství dopravních elementů - tato přeprava je uskutečňována vozidly, jejichž trasa začíná a končí ve středisku V0 a jejichž kapacita je shora omezená. Úlohou je pak sestavit sadu tras vozidel tak, aby byl požadavek každého místa odběru uspokojen jedinou obsluhou vozidla, a aby celkové náklady na přepravu byly minimální (z hlediska délky nebo času). Ze zadání úlohy vyplývají dvě podmínky přípustnosti jejího řešení: § každý zákazník musí být v rámci některé trasy obsloužen právě jednou § musí být respektována nepřekročitelná kapacita obsluhujících vozidel
(1) (2)
Vedle těchto základních podmínek mohou být na sadu tras obsluhujících vozidel kladeny další podmínky přípustnosti řešení, jejichž zavedením se původní úloha VRP modifikuje – jsou to např.: Ø globální podmínky: §
množství elementů, které je možné rozvést v rámci jedné trasy
§
omezení maximální doby trvání, resp. délky jedné trasy (nepřekročitelná pracovní doba osádek vozidel, nutné doby odpočinků, zákazy jízd v určitých dnech apod.)
§
omezení vyplývající z maximálně možného počtu obsloužených míst jednou trasou vzhledem k jejich požadavkům a kapacitám vozidel
§
omezený disponibilní vozový park, kde v případě, že je park heterogenní, se mohou jednotlivá vozidla lišit svou technologickou a kapacitní způsobilostí
Ø lokální podmínky: §
respektování časové dosažitelnosti obsluhovaných míst, požadavku obsluhovaného místa v zadaném časovém intervalu
§
respektování technologické dosažitelnosti obsluhovaných míst, tzn. požadavek na obsloužení zákazníka pouze vozidlem určitých parametrů
§
limitovaná spotřeba pohonných hmot; přijatelné náklady vynaložené na obsluhu apod.
tzn.
uspokojení
V dalším textu se budeme zabývat úlohou trasování pro nejjednodušší případ, kdy předpokládáme homogenní vozový park, a kde trasa jednoho vozidla bude tvořena jedinou okružní 1
jízdou. Je-li doba trvání trasy omezená, může být trasa vytvořena z více okružních jízd. Dále v úloze, kterou budeme řešit neklademe žádné omezující časové podmínky pro obsluhu uzlů. Úloha se v tom případě redukuje na pokrytí požadavků odběratelů soustavou tras a následné přidělení těchto tras jednotlivým vozidlům disponibilního parku může být řešeno v následující fázi nezávisle na úloze trasování.
2. Clarkeova-Wrightova metoda Nejznámější heuristickou metodou řešící uvedenou úlohu VRP je Clarkeova-Wrightova, kterou zveřejnili její autoři G. Clarke a J. W. Wright v roce 1964. Postup metody spočívá v tom, že v každé iteraci metody jsou podle jistého kritéria vybrány dvě možné trasy (V0 – Vi – V0) a (V0 – Vj – V0) a tyto jsou spojeny do jedné tzv. sdružené trasy (V0 – Vi – Vj – V0). Dvě trasy mohou být sdruženy jen tehdy, jestliže vzniklá sdružená trasa bude vyhovovat uvedeným podmínkám přípustnosti řešení (1) a (2), což znamená, že součet zátěže sdružovaných tras nesmí překročit kapacitu vozidla K. Při postupu lze snadno kontrolovat i splnění dalších globálních podmínek jako např. maximální délku trasy, počet navštívených uzlů, dobu trvání jízdy, kde příslušná kontrolovaná veličina nově vzniklé sdružené trasy je závislá pouze na odpovídajících sledovaných veličinách sdružovaných tras, resp. sdružovaných uzlů. Výhodnost nebo nevýhodnost sdružení dvou tras je určena úsporou, která jejich sdružením vznikne. Tuto úsporu měříme tzv. výhodnostním koeficientem zij podle vztahu zij = (d0i + d0j – dij), kde d0i, d0j a dij označují délky hran (V0,Vi), (V0,Vj) a (Vi,Vj). Hodnota zij tedy vyjadřuje rozdíl mezi součtem délek tras (V0 – Vi – Vj) a (V0 – Vj – V0) a délkou sdružené trasy (V0 – Vi – Vj – V0). Metoda sdruží v každé iteraci postupu ty dva uzly, které vykazují nejvyšší výhodnostní koeficient zij, pokud je možné s ohledem na přípustnost toto sdružení provést. Výhodou tohoto postupu je, že koeficient zij závisí pouze na vzájemných vzdálenostech uzlů Vi, Vj a V0 a nemění se pokud je možné tyto dva uzly spojit. Metodu, kterou jsme právě popsali můžeme zformulovat do několika kroků: 1)
Pro danou dopravní síť S = (V,H) sestavíme matici vzdáleností D = {d(i,j)}, kde i,j = 0,1,…,n; n = |V|. Obecně nemusí být síť S úplná (tj. v grafové reprezentaci znázorněna grafem, který není úplným grafem), to znamená, že prvky matice D mohou vyjadřovat jak délky úseků, tak i vzdálenosti mezi jednotlivými uzly. Dále mějme zadány následující hodnoty: c……….. průměrná rychlost pohybu vozidla na síti t………... doba potřebná k vyložení jednotkového množství elementů z obsluhujícího vozidla T………..maximální doba pobytu vozidla mimo výchozí uzel V0 K………. kapacita vozidla qi………. množství elementů přepravovaných z uzlu V0 do uzlu Vi (i = 1,…,n)
2)
Vytvoříme počáteční řešení, které představuje soubor elementárních tras (V0 – Vi – V0) pro všechny uzly sítě i = 1,…,n s uvedeným množstvím elementů a dobami přepravy (lze také doplnit doby potřebné k vyložení elementů z vozidla): 2
Trasa
Množství elementů
Doba přepravy
V0 – Vi – V0
q1
2 ⋅ d 01 + q1t c
……..
……..
……..
V0 – Vn – V0
qn
2 ⋅ d 0n + qnt c
3)
Z matice D odvodíme matici výhodnostních koeficientů Z = {zij}, kde i,j = 1,…,n podle vztahu zij = d0i + d0j – dij, kde zij, jak bylo zavedeno, vyjadřuje rozdíl mezi součtem délek tras (V0 – Vi – V0) a (V0 – Vj – V0) a délkou sdružené trasy (V0 – Vi – Vj – V0).
4)
V matici Z najdeme největší kladný prvek zij a sdružíme, je-li to možné, trasy (V0 – Vi – V0) a (V0 – Vj – V0) do sdružené trasy (V0 – Vi – Vj – V0). Pokud takový prvek neexistuje, skončíme. Aktuální množina okružních tras je výsledkem algoritmu. V opačném případě přejdeme na krok 5).
5)
Zkontrolujeme, zda sdružením tras (V0 – Vi – V0) a (V0 – Vj – V0) vznikne přípustná trasa. Pokud přípustná trasa nevznikne, tak položíme zij = 0 a přejdeme na krok 4). V opačném případě pokračujeme krokem 6).
6)
Aktualizujeme množinu uzlů V vyjmutím uzlů i a j, pokud sdružením tras přestaly být krajními uzly trasy. Položíme zij = 0. Aktualizujeme množinu tras vyjmutím sdružených tras a vložením nové trasy. Současně také aktualizujeme ostatní sledované parametry (dobu přepravy, množství elementů, délku trasy aj.). Není-li krok 4) a 5) možný, najdeme nejblíže menší nebo stejně velký prvek zst a sdružíme trasy obsahující uzly Vs a Vt; mohou to být elementární trasy nebo trasy, vzniklé předchozím sdružováním. Pro krajní uzly Vs a Vt nově vzniklé trasy položíme zst = 0 a přejdeme na krok 4). Postup opakujeme, pokud není matice Z vyčerpána nebo pokud není zřejmé, že kapacity vozidel jsou vyčerpány a další řešení nemá smysl. Výsledné řešení nemusí být optimální, ale často bude jen suboptimální.
3. Příklad Máme dánu neorientovanou, souvislou a hranově ohodnocenou dopravní síť S = (V,H). Požadujeme přepravit dané množství dopravních elementů z výchozího uzlu V0 do ostatních uzlů sítě Vi, kde i = 1,…,n. Dále známe průměrné rychlosti a kapacity všech vozidel a budeme předpokládat, že jsou stejné. Množství elementů, přepravované do kteréhokoliv uzlu, nepřekračuje kapacitu jednoho vozidla. Dále je známa doba potřebná pro vyložení elementu z vozidla, která je stejná pro všechny komplety a všechny uzly. Doba mezi výjezdem a návratem každého vozidla do výchozího uzlu V0 je shora omezená. 3
Úkolem je určit počet vozidel a jejich trasy tak, aby při splnění všech uvedených požadavků byl součet délek tras všech vozidel, začínajících a končících v uzlu V0, minimální. Pro nalezení suboptimálního řešení této úlohy použijeme popsanou C-W metodu. Dopravní síť úlohy je definována pomocí matice vzdáleností D této sítě, která je úplnou sítí (tzn., že prvky matice vzdáleností jsou zároveň délkami příslušných úseků – hran). Jsou dány počty elementů qi a další výchozí údaje: c = 30 km/h; t = 0,1 h; T = 8h; K = 15 elementů. Matice vzdáleností D je v tomto případě neorientované sítě symetrická, můžeme tedy prvky pod hlavní diagonálou vynechat – matice vypadá takto: i/j
0
1
2
3
4
5
0
0
33
60
54
50
52
0
38
35
34
76
0
15
70
94
0
48
73
0
28
1 2 3 4
0
5
Z matice vzdáleností D je odvozena matice výhodnostních koeficientů Z = {zij}: i/j
1
2
3
4
5
1
0
55
52
49
9
0
99
40
18
0
56
33
0
74
2 3 4
0
5 Údaje v následující tabulce zachycují počáteční řešení: Elementární trasy 0–1–0 0–2–0 0–3–0 0–4–0 0–5–0
qi
Délky
6 3 8 5 4
66 120 108 100 104
Doby přepravy a vykládky 2,8 4,3 4,4 3,8 3,9
1. iterace: Podle kroku 4) hledáme první zlepšující řešení: max zij = z23 = 99; sdružíme proto trasy (0 – 2 – 0) a (0 – 3 – 0). Podle kroku 5) kontrolujeme přípustnost sdružené trasy na základě provedení kroku 6) takto: vyjmutím právě sdružené trasy aktualizujeme množinu tras počátečního řešení; pro právě sdruženou trasu aktualizujeme množství elementů q a dále aktualizujeme délku trasy a dobu T strávenou kompletem mimo uzel V0. Po provedení kroku 6) zjišťujeme, že součet zátěží q2 + q3 = 11, což je hodnota nižší než přípustná 4
kapacita vozidla K = 15. Dále zjišťujeme, že nová doba pobytu vozidla mimo uzel V0 je rovna 5,4 a tedy nepřekračuje zadanou přípustnou hodnotu T = 8. Nepřekročení hodnot K a T znamená, že nová sdružená trasa (0 – 2 – 3 – 0) je přípustnou trasou. Uvedené skutečnosti jsou zřejmé z následující tabulky. Nakonec kroku 6) položíme z23 = 0 a dále pokračujeme krokem 4) v hledání další přípustné trasy. Trasa
q2 + q3
Délka
Doba
0–2–3–0
11
129
5,4
Po 1. iteraci dostáváme tuto aktualizovanou množinu tras a odpovídající zátěže: Elementární trasy 0–1–0 0–2–3–0 0–4–0 0–5–0
qi
Délky
6 11 5 4
66 129 100 104
Doby přepravy a vykládky 2,8 5,4 3,8 3,9
2. iterace: Pokračujeme hledáním dalšího přípustného řešení: max zij = z45 = 74, sdružená trasa (0 – 4 – 5 – 0) je přípustná, viz tabulka: Trasa
q4 + q5
Délka
Doba
0–4–5–0
9
130
5,2
Po 2. iteraci dostáváme tuto aktualizovanou množinu tras a odpovídající zátěže: Elementární trasy 0–1–0 0–2–3–0 0–4–5–0
qi
Délky
6 11 9
66 129 130
Doby přepravy a vykládky 2,8 5,4 5,2
3. iterace: Pokračujeme hledáním dalšího přípustného řešení: max zij = z34 = 56, vytvořit sdruženou trasu by znamenalo sdružit trasy obsahující uzly V3 a V4, tzn. trasy (0 – 2 – 3 – 0) a (0 – 4 – 5 – 0); z tabulky je zřejmé, že taková trasa je nepřípustná, protože bychom překročili přípustnou kapacitu K obsluhujícího vozidla: q(0 – 2 – 3 – 0) = 11, q(0 – 4 – 5 – 0) = 9; 11+9=20 > K=15. Proto po 3. iteraci zůstávají množina tras a odpovídající zátěže nezměněné. 4. iterace: Pokračujeme hledáním dalšího přípustného řešení: max zij = z12 = 55, trasa vzniklá sdružením tras, které obsahují uzly V1 a V2, tj. (0 – 1 – 0) a (0 – 2 – 3 – 0) je opět nepřípustná, protože 6+11=17 > K=15, což nelze. Tedy i po 4. iteraci zůstávají množina tras a odpovídající zátěže nezměněné. 5
5. iterace: Pokračujeme hledáním dalšího přípustného řešení: max zij = z13 = 52; nastává stejná situace jako po 4. iteraci; trasa vzniklá sdružením tras, které obsahují uzly V1 a V3, tj. (0 – 1 – 0) a (0 – 2 – 3 – 0) je opět nepřípustná, protože 6+11=17 > K=15, což nelze. I po 5. iteraci zůstávají množina tras a odpovídající zátěže nezměněné. 6. iterace: Pokračujeme hledáním dalšího přípustného řešení: max zij = z14 = 49; trasa vzniklá sdružením tras, které obsahují uzly V1 a V4, tj. (0 – 1 – 0) a (0 – 4 – 5 – 0) je přípustná, protože 6+9=15, což není hodnota větší než K=15 Trasa
q1 + q4 + q5
Délka
Doba
0–1–4–5–0
15
147
6,4
Po 6. iteraci již nelze kroky 4) a 5) opakovat, tzn. že další sdružování tras není možné, a proto poslední aktualizovaná množina tras, zátěže, délek tras a dob pobytu mimo výchozí uzel obsahuje nalezené řešení – viz tabulku:
Elementární trasy
qi
Délky
Doby přepravy a vykládky
0–1–4–5–0 0–2–3–0
15 11
147 129
6,4 5,4
Optimální množina tras vozidel je tedy dvouprvková, výsledné řešení má součet délek tras 276 km oproti výchozímu součtu délek elementárních tras 498 km; součet dob provozu vozidel je 11,8 h. Protože T = 8 < 11,8 < 2x8 = 16, jsou pro splnění úkolu nutná dvě vozidla.
4. Zdroje § CLARKE, G; WRIGHT, J. W.: „Scheduling of Vehicles from a Central Depot to a Number of Delivery Points“, Operations research 12, 1964, strana 568-581 § TUZAR, A.; MAXA, P.; SVOBODA, V.: „Teorie dopravy“, ČVUT v Praze, Praha 1997
6
