Univerzita Karlova v Praze Matematicko-fyzikální fakulta
DIPLOMOVÁ PRÁCE
Ondřej Kafka Optimální plánování rozvozu pomocí dopravních prostředků Katedra pravděpodobnosti a matematické statistiky
Vedoucí diplomové práce: RNDr. Martin Branda, Ph.D. Studijní program: Matematika Studijní obor: Pravděpodobnost, matematická statistika a ekonometrie
Praha 2013
Na tomto místě bych rád poděkoval RNDr. Martinovi Brandovi, Ph.D. za vedení práce a cenné připomínky.
Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona.
V ........ dne ............
Podpis autora
Název práce: Optimální plánování rozvozu pomocí dopravních prostředků Autor: Ondřej Kafka Katedra: Katedra pravděpodobnosti a matematické statistiky Vedoucí diplomové práce: RNDr. Martin Branda, Ph.D. Abstrakt: Práce se zabývá optimalizačními problémy, které vznikají při plánování rozvozu pomocí dopravních prostředků. Tyto problémy lze často formulovat jednoduše jako úlohy celočíselného programování, ale málokdy je možné je řešit přímo technikami celočíselného programování. Proto je třeba zkoumat také schopnosti heuristických algoritmů. Hlavním zaměřením práce je rozvozní problém s časovými okny. Pro tento problém byl navržen a implementován algoritmus tabu prohledávání. Algoritmus využívá celočíselné programování při řešení dělícího problému za účelem nalezení optimálního rozdělení všech zákazníků do přípustných tras nalezených během vyhledávacího procesu. V numerické studii jsou porovnány výsledky postupů klasického celočíselného programování, jednoduché vkládací heuristiky a navrženého algoritmu tabu prohledávání. Klíčová slova: rozvozní problém, problém obchodního cestujícího, celočíselné programování, heuristiky, tabu prohledávání
Title: Vehicle Routing Problem Author: Ondřej Kafka Department: Department of Probability and Mathematical Statistics Supervisor: RNDr. Martin Branda, Ph.D. Abstract: The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study. Keywords: vehicle routing problem, traveling salesman problem, integer programming, heuristics, tabu search
Obsah Úvod
1
1 Časová složitost 1.1 Třídy složitosti . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2
2 Problém obchodního cestujícího 2.1 Formulace pomocí celočíselného programování . . . . . . . . . 2.1.1 Podmínky zamezující vytváření subcyklů . . . . . . . . 2.2 Přesné metody řešení problému obchodního cestujícího . . . . 2.3 Heuristiky pro problém obchodního cestujícího . . . . . . . . . 2.3.1 Metoda nejbližšího souseda . . . . . . . . . . . . . . . 2.3.2 Christofidova metoda . . . . . . . . . . . . . . . . . . . 2.3.3 Algoritmus k-opt . . . . . . . . . . . . . . . . . . . . . 2.4 Další problémy související s problémem obchodního cestujícího 2.4.1 Časově závislý problém obchodního cestujícího . . . . . 2.4.2 Problém obchodního cestujícího s časovými okny . . . 2.4.3 Úloha s více obchodními cestujícími . . . . . . . . . . . 2.4.4 Rozvozní problém . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
5 6 7 8 11 11 11 12 13 13 14 15 15
3 Rozvozní problém 3.1 Obecně o rozvozních problémech . . . . . . . . . . . 3.2 Kapacitně omezený rozvozní problém . . . . . . . . 3.2.1 Clarkova-Wrightova heuristika . . . . . . . . 3.3 Rozvozní problém s časovými okny . . . . . . . . . 3.4 Metody řešení rozvozních problémů . . . . . . . . . 3.4.1 Postup pomocí matematického programování 3.4.2 Metoda generování sloupců . . . . . . . . . . 3.4.3 Heuristiky . . . . . . . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
16 16 17 20 22 24 24 28 31
. . . . . . . . . časovými okny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35 35 37 39 39 40 43
. . . .
44 44 47 47 49
4 Tabu prohledávání 4.1 Základní terminologie . . . . . 4.2 Aplikace tabu prohledávání na 4.3 Implementace . . . . . . . . . 4.3.1 Datové struktury . . . 4.3.2 Metody . . . . . . . . 4.4 Obecný postup . . . . . . . .
. . . . . rozvozní . . . . . . . . . . . . . . . . . . . .
. . . . . problém . . . . . . . . . . . . . . . . . . . .
5 Numerická studie 5.1 Přístup pomocí matematického programování 5.2 Heuristiky . . . . . . . . . . . . . . . . . . . . 5.2.1 Solomonova vkládací heuristika . . . . 5.2.2 Tabu prohledávání . . . . . . . . . . .
. . . .
. s . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . .
. . . .
Závěr
55
Reference
56
Seznam použitých zkratek
61
Přílohy
62
A Základní pojmy z teorie grafů
63
B Diagram rozmístění zákazníků problémů typu R
65
C Diagram rozmístění zákazníků problémů typu C (otočeno o 90◦ ) 66 D Diagram rozmístění zákazníků problémů typu RC (otočeno o 90◦ ) 67 E Nejlepší nalezená řešení algoritmem tabu prohledávání
68
Úvod Přeprava zboží a osob je důležitou součástí dnešního světa. Denně se utratí obrovské částky za palivo, platy řidičům, údržbu vozidel a mnoho dalšího. Je tedy jasné, že otázka přepravy nabízí velký prostor k optimalizaci nákladů ať už vylepšováním technického vybavení, infrastruktury nebo kvalitním plánováním. Při plánování distribuce zboží jsou v praxi úspěšně uplatňovány techniky operačního výzkumu. Odhadem lze obvykle docílit snížení nákladů o 5 až 20 % [58]. Asi nejznámější úlohou kombinatorické optimalizace je problém obchodního cestujícího (traveling salesman problem, TSP). Úkolem cestujícího je obejít v libovolném pořadí daných n měst a vrátit se do výchozího tak, aby celková délka či cena cesty byla minimální. Svoji popularitu si tato úloha získala díky snadné formulaci, širokému uplatnění a zároveň obtížnému řešení. Zobecněním TSP je pak rozvozní problém (vehicle routing problem, VRP), ve kterém skupina vozů vycházející z jednoho místa objíždí zákazníky a navrací se zpět. Úkolem je nalézt plán tras minimalizující celkovou ujetou vzdálenost či počet použitých vozidel. K VRP se často přidávají další omezení. Typicky to bývají časová okna, během kterých musí dojít k obsloužení zákazníka (vehicle routing problem with time windows, VRPTW). Protože výpočetní složitost přesných deterministických algoritmů exponenciálně roste s velikostí těchto úloh, velké praktické úlohy je často nutné řešit pomocí heuristických algoritmů, zajišťujících pouze suboptimální řešení. Diplomová práce je rozdělena do kapitol. První kapitola popisuje základní definice NP-těžkých a NP-úplných úloh. Ve druhé kapitole je popsán problém obchodního cestujícího včetně několika způsobů řešení. Třetí kapitola se zabývá rozvozními problémy a metodami jejich řešení. Ve čtvrté kapitole je navržen algoritmus tabu prohledávání pro rozvozní problém s časovými okny. Poslední, pátá kapitola shrnuje numerické výsledky algoritmu tabu prohledávání i běžného postupu pomocí celočíselného programování.
1
1. Časová složitost Algoritmus je seznam instrukcí k vyřešení problému. Časovou složitostí algoritmu budeme rozumět počet všech instrukcí z hlediska nejhoršího případu v závislosti na velikosti vstupních dat a vyjadřovat pomocí „velké O“ notace. Formálně: f (x) je O(g(x)), jestliže existuje konstanta c > 0 a přirozené n0 tak, že pro každé přirozené n ≥ n0 platí f (n) ≤ c·g(n). Má-li tedy algoritmus časovou složitost O(n2 ), doba trvání jeho průběhu se zvyšuje kvadraticky v proměnné velikosti vstupu n. Tento způsob odhadu složitosti rozděluje algoritmy na dvě skupiny - polynomiální1 a nepolynomiální (typicky exponenciální). Rozdíl v rychlosti mezi polynomiálním a exponenciálním algoritmem je zřejmý zejména při úlohách asymptotické velikosti. Zároveň polynomiální algoritmy mnohem lépe využijí případný technologický pokrok. Jasné jsou také matematické výhody tohoto rozdělení. Sečtením, vynásobením i složením dvou polynomů dostaneme opět polynom. Budeme-li tedy rozlišovat algoritmy na „dobré“ a „špatné“ v závislosti na tom, zda mají, či nemají polynomiální složitost, můžeme rovněž klasifikovat problémy jako „lehké“ a „těžké“ podle toho, zda je umíme nebo neumíme vyřešit polynomiálním algoritmem. Výpočetní složitost problému obchodního cestujícího je podrobně popsána v [30]. Odtud jsou také převzaty základní definice této kapitoly. Rozhodovací úlohy jsou úlohy, jejichž výstupem je pouze odpověď na otázku ve smyslu ANO/NE. Každý optimalizační problém lze snadno převést na rozhodovací úlohu, kdy místo hledání optima účelové funkce, se pouze ptáme, jestli existuje řešení splňující nějaké omezení účelové funkce. Pro většinu optimalizačních úloh navíc platí, že pro ně existuje polynomiální algoritmus právě tehdy, když existuje polynomiální algoritmus pro jejich rozhodovací verze. Lze se tak víceméně bez újmy na obecnosti omezit na rozhodovací úlohy. Definice 1. Úloha A je polynomiálně redukovatelná na úlohu B, existuje-li polynomiální algoritmus, který z libovolných vstupních dat a úlohy A vyrobí vstupní data b pro úlohu B takovým způsobem, že odpovědi na otázky spojené s oběma úlohami budou stejné. Zde předpokládáme, že velikost b je také polynomiální funkcí velikosti a. Z vlastnosti skládání polynomů plyne následující věta. Věta 1. Pokud je problém A polynomiálně redukovatelný na problém B a existuje polynomiální algoritmus pro B, pak existuje polynomiální algoritmus pro A.
1.1
Třídy složitosti
Definice 2. Třídu P tvoří rozhodovací úlohy řešitelné deterministickými algoritmy v polynomiálním čase (tzn. jejich složitost je O(nk ) pro nějaké k). Definice 3. Třídu NP (nedeterministicky polynomiální) tvoří rozhodovací úlohy řešitelné v polynomiálním čase na nedeterministickém Turingově stroji, tj. na pomyslném počítači, který dokáže v každém kroku rozvětvit výpočet na n větví a v nich poté současně hledat řešení. 1
Mezi polynomiální patří i např. algoritmy složitosti log(n), neboť O(log(n)) ⊂ O(n).
2
Celková odpověď nedeterministického algoritmu je ANO, pokud nějaká z větví odpoví ANO, jinak je odpověď NE. Například TSP je zřejmě z třídy NP. Nedeterministický počítač může začít v libovolném městě a rozvětvit výpočet na tolik větví, kolik vede z města cest, a v každém z dalších měst postupovat stejně s výjimkou již navštívených měst. Jedním z největších otevřených problémů v teoretické informatice je otázka, zda P = NP. Inkluze P ⊂ NP je zřejmá. Obecně se však předpokládá, že P 6= NP, ale důkaz takového tvrzení dosud nebyl objeven. Protože třída NP obsahuje rozhodovací úlohu TSP, těžko budeme ukazovat, že TSP není řešitelný v polynomiálním čase, pokud nejprve nedokážeme, že P 6= NP. Lze totiž ukázat, že problém P = NP je ekvivalentní problému, zda rozhodovací TSP patří do P. Klíčem k tomu je tzv. NP-úplnost. Definice 4. Řekneme, že optimalizační nebo rozhodovací problém je NP-těžký, jestliže každý problém z NP je na něj polynomiálně redukovatelný. Definice 5. Řekneme, že rozhodovací problém A je NP-úplný, jestliže je NP-těžký a zároveň platí A ∈ NP. Důsledkem těchto definic je tvrzení, že pokud rozhodovací verze problému je NP-úplná, pak jeho optimalizační verze je NP-těžká. NP-úplné úlohy jsou v jistém smyslu nejtěžší úlohy z NP. Pokud by existoval polynomiální algoritmus pro libovolný NP-úplný problém, potom by existoval polynomiální algoritmus pro všechny úlohy z NP a bylo by P = NP. I mezi různými NP-těžkými problémy lze ještě poukázat na rozdíl v obtížnosti jejich řešitelnosti. K některým problémům existují i tzv. pseudopolynomiální algoritmy. Definice 6. Řekneme, že algoritmus řešící problém A je pseudopolynomiální, jestliže jeho časová složitost je omezena polynomem proměnných len(I), max(I), kde jsme označili len(I) velikost vstupu instance I v nějakém kódování a max(I) největší číselný parametr v instanci I. Jednoduchým příkladem pseudopolynomiálního algoritmu je testování prvo√ n číselnosti čísla n postupným dělením čísly {2, 3, . . . , b 2 c}. Definice 7. Nechť A je rozhodovací nebo optimalizační problém. Označme A(p) restrikci problému A na instance I takové, že max(I) ≤ p(len(I)). Řekneme, že A je silně NP-těžký, jestliže existuje polynom p takový, že A(p) je NP-těžký. A nazveme silně NP-úplný, pokud A ∈ NP a existuje polynom p takový, že A(p) je NP-úplný. Pokud A je silně NP-těžký nebo silně NP-úplný problém, pak pokud P 6= NP, neexistuje k A pseudopolynomiální algoritmus.
3
VRP
Obecný TSP
TSP splňující trojúhelníkovou nerovnost
Symetrický TSP
Symetrický TSP splňující trojúhelníkovou nerovnost Problém hamiltonovské kružnice
Euklidovský TSP
Obrázek 1.1: Schéma speciálních případů souvisejících s TSP Problém A je speciálním případem problému B, pokud oba řeší stejnou otázku a množina všech možných vstupních dat problému A je podmnožinou všech možných vstupních dat problému B. Zřejmě tak obecnější případ problému nemůže být „lehčí“ než jeho speciální verze. Bylo dokázáno, že samotné nalezení libovolné hamiltonovské kružnice (kružnice, která právě jednou projde všemi vrcholy) v daném neorientovaném (i orientovaném) grafu je NP-úplný problém [35], dokonce silně, jelikož zadání ani neobsahuje numerická data. Také euklidovský TSP je silně NP-těžký problém [46]. A protože se tato vlastnost v diagramu na obrázku 1.1 zachovává směrem vzhůru, jsou všechny úlohy na diagramu rovněž silně NP-těžké. Dokonce rozhodovací verze problémů jsou z třídy NP, a jsou tedy i silně NP-úplné. Jednotlivé typy problému obchodního cestujícího na obrázku 1.1 se odlišují vlastnostmi vzdáleností svých zákazníků. Matematicky budou popsány v další kapitole.
4
2. Problém obchodního cestujícího Je dáno n měst a v jednom z nich se nachází obchodní cestující. Potřebuje obejít zbývající města a vrátit se zpět. Přitom pro každou dvojici měst zná náklady na cestu oběma směry a hledá celkovou nejlevnější trasu. Jsou-li každá dvě města vzájemně dosažitelná, přípustným řešením úlohy je libovolná permutace n měst, která představuje posloupnost po sobě navštívených měst. Asi nejjednodušší znění úlohy obchodního cestujícího je tedy následující: Pro danou matici C = (cij )n×n , reprezentující ceny, nalezněte permutaci π množiny {1, 2, . . . , n}, která minimalizuje součet cπ(n),π(1) +
n−1 X
cπ(i),π(i+1) .
i=1
Je-li například n = 5, očíslujme města 1, 2, . . . , 5, pak řešení 1→2→3→4→5→1
a
2→3→4→5→1→2
jsou zřejmě totožná. Snadno si tak představíme, že na výchozím městě v úloze obchodního cestujícího nezáleží a počet všech přípustných řešení TSP je (n − 1)!. Jiná formální definice TSP vychází z teorie grafů. Použité definice z teorie grafů jsou shrnuty v příloze A. Nechť G = (V, E) je graf (orientovaný nebo neorientovaný). Označme V = {1, 2, . . . , n}. Pro každou hranu (i, j) ∈ E resp. {i, j} ∈ E je dána její cena cij . Potom úlohou obchodního cestujícího je nalézt hamiltonovskou kružnici v G, jejíž součet cen hran je nejmenší možný. Bez újmy na obecnosti předpokládejme, že G je úplný graf. Chybějící hrany lze jinak dodefinovat jako hrany vysoké ceny. Matici C = (cij )n×n , kde cij odpovídá ceně hrany vedoucí z vrcholu i do vrcholu j, nazveme maticí cen (vzdáleností, vah). Diagonální prvky matice C nejsou zajímavé, později je z praktických důvodů definujeme jako nekonečno. Nicméně povaha matice C definuje dvě velké třídy TSP. Je-li C symetrická (tj. G neorientovaný), mluvíme o symetrickém problému obchodního cestujícího (STSP). Pokud C obecně není symetrická (tj. G orientovaný), jde o nesymetrický problém obchodního cestujícího (ATSP). Poznamenejme, že je možné ATSP formulovat jako STSP s dvojnásobným počtem vrcholů [31]. 3
3
2∗
4
3 −M
−M
4 6
1
3∗
2
5
6
2
3
2 5
2
1
1
1
−M
1∗
Obrázek 2.1: Transformace nesymetrického TSP na symetrický Uvažujme ATSP na orientovaném grafu D = (N, A), N = {1, 2, . . . , n}, C = (cij )n×n . Sestavme neorientovaný graf G∗ = (V ∗ , E ∗ ) s množinou vrcholů 5
V ∗ = N ∪{1∗ , 2∗ , . . . , n∗ }. Ke každé hraně (i, j) ∈ D vytvoříme hranu {i, j ∗ } ∈ G∗ s cenou cij . Dále přidáme hrany {i, i∗ } s cenou −M pro nějaké velké M . Ostatní hrany mají cenu M . Nyní stačí jen ověřit, že řešení ATSP na D je ekvivalentní řešení STSP na G∗ . Jednoduchý příklad této transformace je znázorněn na obrázku 2.1. Jinou transformaci nesymetrického problému na symetrický s trojnásobným počtem vrcholů navrhl Karp [35]. Splňují-li prvky C trojúhelníkovou nerovnost cij + cjk ≥ cik , ∀i, j, k, jedná se o metrický TSP. Speciálně je-li cij přímo euklidovská vzdálenost měst i a j v rovině, jde o euklidovský TSP.
2.1
Formulace pomocí celočíselného programování
V následujících formulacích budeme předpokládat orientované hrany grafů i u symetrických problémů. Formulace celočíselného programování TSP zpravidla vychází z tzv. přiřazovacího problému. Definujme n2 binárních proměnných xij takových, že xij = 1, pokud cesta prochází hranou (i, j) neboli městu i je přiřazeno následující město j. Úlohu minimalizovat za podmínek
n n X X
cij xij
i=1 j=1 n X
(2.1)
xij = 1, j = 1, 2, . . . , n,
(2.2)
xij = 1, i = 1, 2, . . . , n,
(2.3)
xij ∈ {0, 1}, i, j = 1, 2, . . . , n,
(2.4)
i=1 n X j=1
nazýváme přiřazovací problém. Podmínky (2.3), (2.2) zajistí, že každému městu bude přiřazen právě jeden následník a každé město bude přiřazeno právě jednomu předchůdci. V podstatě je přiřazovací problém zvláštní případ známého vyváženého dopravního problému minimalizovat za podmínek
m n X X
cij xij
i=1 j=1 n X i=1 m X
(2.5)
xij = bj , j = 1, 2, . . . , m,
(2.6)
xij = ai , i = 1, 2, . . . , n,
(2.7)
j=1
xij ≥ 0, i = 1, 2, . . . , n, j = 1, 2, . . . , m.
(2.8)
ve kterém xij představují převážený náklad ze skladu i k zákazníkovi j a požadujeme přesné splnění požadavků bj s přesným využitím všech kapacit skladů ai (podmínky (2.6), (2.7) ve tvaru rovnosti). Pokud požadavky bj a kapacity ai nahradíme 1 a položíme n = m neboli mezi n městy přepravujeme jen jednotková množství, dostáváme již přiřazovací problém. Podmínku (2.4) skutečně lze nahradit podmínkou (2.8), a je tedy možné nahlížet na přiřazovací problém jako 6
na úlohu lineárního programování (LP). Důvodem, proč vždy existuje celočíselné řešení, je fakt, že matice A ve formulaci LP přiřazovacího problému je totálně unimodulární, tj. determinant každé její čtvercové podmatice je roven 0, 1 nebo −1 a platí následující věta. Věta 2. Nechť matice A je totálně unimodulární a b ∈ Zm . Potom konvexní polyedrická množina M = {x ∈ Rn | Ax = b, x ≥ 0} má všechny krajní body celočíselné. Důkaz. Nechť A je typu m × n. Každý krajní bod z je určen n × n regulární submaticí A0 ve smyslu A0 z = b0 , kde hodnoty b0 odpovídají příslušným hodnotám vektoru b. Označme (A0 )i matici, kterou získáme z A0 nahrazením i-tého sloupce 0) ) i ∈ Z. vektorem b0 . Podle Cramerova pravidla zi = det((A det(A0 ) Protože lineární programování je problém z P (např. metoda vnitřního bodu [34]), přiřazovací problém patří také do třídy P a jsou pro tento problém známy i polynomiální algoritmy, např. maďarská metoda [37]. Přiřazovací problém je důležitou relaxací TSP, ale sám o sobě k formulaci TSP nestačí. Zřejmě je schopen zajistit, že z každého a do každého města vede právě jedna cesta, řešení ale nemusí tvořit jeden cyklus. Mohou tak vzniknout lokální smyčky jako je tomu na pravé straně obrázku 2.2. 4
4
5
3
1
5
2
3
1
2
Obrázek 2.2: Souvislá trasa vs. dva subcykly na příkladu 5 měst Je tedy nutné přidat další omezení, které zamezí vytváření subcyklů. Tím se bohužel pokazí vlastnosti úlohy.
2.1.1
Podmínky zamezující vytváření subcyklů
Budeme postupně eliminovat subcykly různé délky. Subcyklem délky 1 rozumíme přiřazení města sobě samému a přirozeně definujeme subcykly vyšších délek. K eliminaci subcyklů délky 1 stačí položit xii = 0, i = 1, 2, . . . n. Pokud položíme xii = 0, není nutné tyto proměnné vůbec uvažovat, mírně se tím ale komplikuje matematický zápis úloh. Eliminace těchto subcyklů se obvykle provádí také definováním cen cii = ∞, i = 1, 2, . . . n. Podmínka xij +xji ≤ 1, ∀i, j zřejmě zamezí vzniku subcyklů délky 2. Podobně subcykly délky 3 lze eliminovat podmínkou xij + xjk + xki ≤ 2, ∀i, j, k a dále lze postupovat analogicky, což dohromady dává XX
xij ≤ |S| − 1, ∀S ⊂ {1, 2, . . . , n}; 2 ≤ |S| ≤ n − 1,
i∈S j∈S
7
(2.9)
kde | · | značí mohutnost množiny. Bohužel celkový počet těchto nerovností je téměř 2n .l Sice m je možné jejich počet snížit úvahou, že stačí eliminovat subcykly n do délky 2 , neboť případná existence delšího subcyklu už implikuje přítomnost subcyklu kratšího, ale stále jich pro rozumný zápis do paměti počítače může být příliš mnoho. Podmínka (2.9), prvně formulovaná v [11], se přesto stala velmi užitečnou. Vhodné nerovnosti lze totiž například iterativně přidávat až v průběhu výpočtu. Později byla objevena jiná formulace podmínek vylučujících subcykly se skutečně polynomiálním počtem nerovností [42]: ui − uj + nxij ≤ n − 1, i, j = 2, 3, . . . , n,
(2.10)
kde ui , i = 2, 3, . . . , n jsou nově přidané neomezené reálné proměnné. Ukážeme, že tyto podmínky skutečně eliminují subcykly délek 1 až n − 1. Předpokládejme, že řešení netvoří hamiltonovský cyklus. Protože z každého a do každého vrcholu vede jen jedna hrana, řešení je tvořeno více cykly. Alespoň jeden cyklus neprochází vrcholem 1, označme jej C, počet hran cyklu C označme |E(C)|. Sečteme-li nerovnosti (2.10) přes všechny hrany cyklu C, dostaneme n · |E(C)| ≤ (n − 1) · |E(C)|, což je spor. Nechť naopak E(C) = {(i, j) | xij = 1} je množina hran hamiltonovského cyklu s vrcholy v pořadí v1 , v2 , . . . , vn a v1 = 1. Položme ui = `, je-li i = v` . Pak pro každou hranu (i, j) ∈ E(C), i, j ≥ 2, platí ui − uj = uv` − uv`+1 = −1. Tedy ui − uj + nxij = −1 + n ≤ n − 1. Pro ostatní hrany (i, j) ∈ / E(C), pro které i, j ≥ 2, nerovnost (2.10) přirozeně platí. Každý hamiltonovský cyklus je tedy přípustný. Přiřazovací problém (2.1)–(2.4) spolu s některou z popsaných podmínek je vhodnou formulací problému obchodního cestujícího, přesněji ATSP. V případě STSP je možné formulaci ještě zjednodušit: minimalizovat za podmínek
n n X X
cij xij
i=1 j=1 n X
xij = 2, j = 1, 2, . . . , n,
(2.11) (2.12)
i=1
xij ∈ {0, 1}, i, j = 1, 2, . . . , n, {(i, j) | xij = 1} neobsahuje subcykly.
(2.13) (2.14)
Podmínky (2.12) zajistí každému zákazníkovi j, že bude součástí právě 2 hran výsledné kružnice v grafu. Pro další různé podmínky eliminující subcykly a jiné formulace TSP lze doporučit [50].
2.2
Přesné metody řešení problému obchodního cestujícího
Některé způsoby hledání optimálního řešení TSP jsou založeny na principu větví a mezí (branch and bound). Jeden z nejjednodušších takových algoritmů budeme 8
demonstrovat na příkladě. Uvažujme symetrický TSP zadaný grafem na obrázku 2.3, resp. v tabulce 2.1. Primitivní dolní mez, tedy délku trasy, pro kterou můžeme bezpečně tvrdit, že neexistuje řešení kratší, získáme přímo z tabulky 2.1 prostým sečtením řádkových minim: 3 + 3 + 2 + 2 + 3 = 13, tj. sečtením minimálních cen, za které je možné opustit každé dané město. 4 4
2
5
3
4 5 3
1 2 3 4 5
5 5
1
6
4
2
3
Obrázek 2.3: TSP zadaný grafem
1
2
3
4
5
– 3 6 5 3
3 – 4 5 5
6 4 – 2 4
5 5 2 – 4
3 5 4 4 –
Tabulka 2.1: TSP zadaný tabulkou
Nyní rozdělíme výpočet do čtyř větví. V první větvi předpokládáme x12 = 1, v druhé x13 = 1, ve třetí x14 = 1 a konečně ve čtvrté x15 = 1. Pro každou tuto větev spočteme novou dolní mez za uvedeného předpokladu.
14 =
=
2
16
17
16
x34 = 1
18
x53 = 1
1
x5
3
=
17
1
x24 = 1
1
1
3
x1
17
=
x 54
1
18 =
x2
5
x 25
16
x1
=1
14
1
x 14
x 12
=
=1
13
16 Obrázek 2.4: Průběh výpočtu algoritmu větví a mezí Tedy například ve větvi x12 = 1 vynecháme z tabulky 2.1 první řádek a druhý sloupec, protože z města 1 do města 2 už vede cesta a přičteme součet řádkových minim k ceně hrany (1, 2): (4 + 2 + 2 + 3) + 3 = 14. 9
Jediný rozdíl při výpočtu nových dolních mezí je, že již by mohl vzniknout subcyklus. Ve větvi x12 = 1 už nechceme x21 = 1. Tedy na příslušném místě v tabulce 2.2 je pomlčka.
2 3 4 5
1
3
4
5
– 6 5 3
4 – 2 4
5 2 – 4
5 4 4 –
Tabulka 2.2: Zadaný TSP za předpokladu x12 = 1 Pro každou větev dostaneme postupně nové dolní meze 14, 18, 17, 14. Například ve větvi předpokládající x13 = 1 nelze nalézt řešení s lepší hodnotou než 18. Dále algoritmus pokračuje rozvětvením tam, kde je nejmenší dolní mez. Tedy například k předpokladu x12 = 1 se postupně přidávají x23 = 1, x24 = 1, x25 = 1. Aby opět nevznikaly subcykly, tak např. ve větvi x12 = 1, x23 = 1 požadujeme x31 = 0. Tedy opět na příslušném místě v tabulce 2.3, vzniklé z 2.2 vynecháním sloupce 3 a řádku 2, je pomlčka.
3 4 5
1
4
5
– 5 3
2 – 4
4 4 –
Tabulka 2.3: Zadaný TSP za předpokladu x12 = x23 = 1 Po těchto krocích zůstává nejlepší dolní mez 14 v pravé části diagramu na obrázku 2.4, proto algoritmus dále pokračuje ve výpočtu v této větvi. Protože necyklická trojice hran již jednoznačně určuje řešení problému s pěti vrcholy, na třetí úrovni větvení už dostáváme přípustná řešení problému a s nimi i horní meze (optimální řešení nemůže být horší). Ve větvi x12 = x23 = 1 algoritmus nalézá řešení 1 → 2 → 3 → 4 → 5 → 1 s délkou trasy 16. V tuto chvíli přestává prohledávat všechny větve (uzly), pro které dolní mez je větší nebo rovna 16, tzn. v našem případě se algoritmus zastaví. Algoritmy založené na principu větvení a mezí se mohou lišit způsobem výpočtu dolní meze (nejčastěji lineární relaxace, přiřazovací problém), způsobem větvení (např. binárně x12 = 0, x12 = 1), ale i způsobem výběru dalších uzlů k prozkoumání. Jejich nevýhodou mohou být slabé dolní meze, kvůli kterým je pak nelze použít k řešení větších problémů. V této práci měl příklad hlavně ilustrovat exponenciální složitost exaktních algoritmů. Obecně bývají mnohem rychlejší algoritmy založeny na principu větvení a řezů (branch and cut), což kombinuje metodu větvení a mezí s metodou sečné nadroviny (cutting plane method), podrobný přehled v [43]. Toto schéma využívá i jeden z nejrychlejších současných exaktních algoritmů pro symetrický problém obchodního cestujícího Concorde [2], který například v roce 2006 dokázal vyřešit problém o velikosti 85 900 měst. 10
Z hlediska nejhoršího případu dosud nejlepší známý exaktní algoritmus pro libovolný TSP funguje na principu dynamického programování a má složitost O(n2 2n ) [24].
2.3
Heuristiky pro problém obchodního cestujícího
Jiná možnost, jak přistupovat k řešení složitých problémů, je nehledat přesně optimální řešení, ale spokojit se pouze s nějakým kvalitním řešením, které lze hledat v polynomiálním čase. K tomuto účelu slouží různé heuristiky. Klasické heuristiky lze obecně rozdělit na dvě skupiny. Konstrukční heuristiky, sloužící k nalezení nějakého přípustného řešení, a zlepšovací heuristiky, které se používají k vylepšování nalezeného řešení. Pokud algoritmus dokonce zaručuje, že délka nalezené trasy nepřekročí určitý násobek optima, mluvíme o aproximačním algoritmu.
2.3.1
Metoda nejbližšího souseda
Vůbec nejjednodušší konstrukční heuristikou je metoda nejbližšího souseda. Algoritmus startuje v jednom z vrcholů a postupně tvoří posloupnost vrcholů tak, aby vždy následující vrchol měl nejmenší vzdálenost od předešlého. Přitom každý vrchol musí být použit právě jednou. Protože řešení závisí na volbě startovního vrcholu, lze tuto proceduru provést pro každý vrchol v grafu a vybrat nejlepší řešení. Kvalita výsledného řešení se bohužel zhoršuje s rostoucí velikostí problému. Na druhou stranu jedinou podmínkou pro použití je úplnost zadaného grafu.
2.3.2
Christofidova metoda
Mnohem zajímavější konstrukční heuristikou je tzv. Christofidova metoda pro symetrický TSP [26]. Konstrukce trasy probíhá v několika krocích. Nechť symetrický problém obchodního cestujícího je určen úplným grafem G = (V, E). Nalezneme minimální kostru T grafu G. Označme C množinu vrcholů lichého stupně v T . Z věty A.12 víme, že |C| je sudé, tedy podgraf v G příslušící vrcholům z C obsahuje perfektní párování. Spočteme minimální perfektní párování M a přidáme ho ke kostře T . Některé hrany se mohou zduplikovat a tím mírně i porušit definici grafu. V T ∪ M pak mají všechny vrcholy sudý stupeň a můžeme nalézt Eulerův cyklus R. Odstraněním opakujících se vrcholů v R dostaneme řešení. 4
4 6
5
5
3
5 4 2
5
1
5
3
5
4
4 2
3
2
2
3
1
2
Obrázek 2.5: Minimální kostra grafu TSP 11
2
Lépe je opět postup vidět na příkladě. Mějme symetrický TSP popsán grafem vlevo na obrázku 2.5. Vpravo je pak jeho zřejmá minimální kostra. Vrcholy 5, 1, 4, 3 mají lichý stupeň, hledáme tedy minimální perfektní párování. Jsou tři možnosti: {{1, 3}, {4, 5}}, {{1, 4}, {3, 5}} a {{1, 5}, {3, 4}}, přičemž poslední možnost je minimální s hodnotou 8. Tyto hrany můžeme zakreslit do grafu minimální kostry a získat tím Eulerův cyklus po vrcholech postupně 1, 2, 3, 4, 1, 5, 1. 4 5
3
1
2
Obrázek 2.6: Eulerův cyklus Zbývá vybrat Hamiltonův cyklus vynecháním některých vrcholů. V tomto případě jsou možnosti dvě: 1 — 2 — 3 — 4 — 1 — 5 — 1, 1 — 2 — 3 — 4 — 1 — 5 — 1.
První možnost je dokonce i jedno z optimálních řešení. Hledání minimální kostry i minimálního perfektního párování lze provádět v polynomiálním čase. Nalezení optima v poslední fázi algoritmu je již NP-těžký problém [47]. I přesto ale Christofidův algoritmus zaručuje jistý nejhorší možný výsledek. Jestliže je graf G úplný a vzdálenosti cij jsou nezáporné a splňují trojúhelníkovou nerovnost, pak lze ukázat, že celková délka libovolného řešení nalezeného heuristikou nepřekročí 1.5 násobek optima [26].
2.3.3
Algoritmus k-opt
Algoritmus k-opt patří do třídy zlepšovacích heuristik. Vstupem do algoritmu je spolu s problémem i nějaké řešení, které se následně snažíme zlepšit sérií dalších úprav. Krok 2-opt [9] jednoduše odebere z řešení nějaké dvě hrany, které nemají společný vrchol, a vzniklé dvě cesty opět spojí do nového cyklu. Takto definuje množinu sousedních řešení, tj. řešení, která lze získat krokem 2-opt. Od nejlepšího sousedního řešení pokračuje stejným způsobem až do chvíle, kdy žádný krok typu 2-opt nenalezne zlepšení. Algoritmus 3-opt pracuje podobně, namísto dvou hran odstraňuje tři. Drobný rozdíl je v opětovném propojení, neboť zde již existuje více způsobů propojení do nového cyklu. Algoritmus je možné zobecnit i pro k > 3, nicméně s rostoucím k roste také náročnost výpočtu a naopak efekt zlepšení
12
vzhledem ke k − 1 se zmenšuje1 . Nejlepší algoritmy tohoto typu mají proměnlivé k podle toho, které k přinese největší zlepšení. Algoritmus opět předpokládá symetrický problém, protože výměny hran mohou způsobit změnu směru průchodu mezi některými městy. 4
5
4
× 5
3 6
×
3
×
×
×
1
1
2
Obrázek 2.7: Krok 2-opt
2
Obrázek 2.8: Krok 3-opt
Jedno z nejstarších tvrzení o problému obchodního cestujícího říká, že v optimálním řešení euklidovského TSP se nemohou hrany křížit, např. proto, že 2-opt krok na křížící se hrany by určitě vytvořil lepší řešení (viz obrázek 2.7). Krok typu 3-opt je znázorněn na obrázku 2.8. Zde zmíněné algoritmy patří k těm nejpopulárnějším, samozřejmě ale existuje celá řada dalších heuristik pro STSP i ATSP. Speciální třídu heuristických algoritmů tvoří tzv. metaheuristiky (např. simulované žíhání, genetické algoritmy, tabu prohledávání, mravenčí kolonie aj.), které jsou schopné při prohledávání nalézt cestu i z lokálního minima. Podrobný přehled heuristických algoritmů pro TSP včetně analýzy chování nabízí [28, 29].
2.4
Další problémy související s problémem obchodního cestujícího
Podle potřeby se k problému obchodního cestujícího přidávají další podmínky, popřípadě se problém ještě více zobecňuje. Tím vznikají nové problémy, které je třeba řešit. Některé nejčastější varianty zobecnění TSP uvedeme při zavedeném značení i zde.
2.4.1
Časově závislý problém obchodního cestujícího
Pro každou hranu (i, j) ∈ E grafu G = (V, E) jsou známy ceny ctij , t = 1, 2, . . . , n, které představují náklady na cestu z i do j v závislosti na pořadí t. Počáteční, a tedy i koncové město je 1. Úkolem časově závislého problému obchodního cestujícího je opět nalézt okružní cestu přes všechna města, pro níž jsou náklady v popsané struktuře minimální. Podrobněji se o tomto problému lze dočíst v [48]. 1
S výjimkou 5-opt kroku, který dle [27] nabízí v tomto smyslu z kombinatorického hlediska více možností.
13
2.4.2
Problém obchodního cestujícího s časovými okny
Pro každou hranu (i, j) ∈ E grafu G = (V, E) jsou kromě cen cij dány také doby přesunu tij . Dále je pak pro každý vrchol i dán interval [ai , bi ], 0 ≤ ai ≤ bi , který představuje časové okno, ve kterém má být obsloužen zákazník ve vrcholu i. Bez újmy na obecnosti předpokládáme, že doba obsluhy si je již zahrnuta v tij , tedy si = 0 pro každé i. Pokud cestující dorazí do i dříve, než mu povoluje příslušné časové okno [ai , bi ], musí čekat do času ai . Také zde cestující vyráží a navrací se vrcholu 1, zvaného depo. Označíme-li proměnnou Ti okamžik začátku obsluhy zákazníka i, formulace problému obchodního cestujícího s časovými okny (traveling salesman problem with time windows, TSPTW) je vzhledem k již popsanému TSP poměrně jasná: minimalizovat za podmínek
n X n X
(2.15)
cij xij
i=1 j=1 n X i=1 n X
xij = 1, j = 1, 2, . . . , n,
(2.16)
xij = 1, i = 1, 2, . . . , n,
(2.17)
j=1
ai ≤ Ti ≤ bi , i = 2, 3, . . . , n, t1j − Tj ≤ M (1 − x1j ), j = 2, 3, . . . , n, Ti + tij − Tj ≤ M (1 − xij ), i, j = 2, 3, . . . , n, xij ∈ {0, 1}, i, j = 1, 2, . . . , n.
(2.18) (2.19) (2.20) (2.21)
Podmínka eliminace subcyklů je tu nahrazena podmínkami (2.19) a (2.20). Poznamenejme, že místo vysoké kladné konstanty M lze psát Mij = max{bi + tij − aj , 0}. i,j
Potom, je-li bi + tij ≤ aj , jsou omezení (2.19) a (2.20) splněna vždy a stačí je použít jen pro taková i, j, pro která Mij > 0. Protože výchozí vrchol obvykle představuje nějakou vozovnu či sklad, odkud vozidla vyráží obsluhovat zákazníky, setkáváme se v literatuře s trochu jinou formulací tohoto problému. Nechť V = {0, 1, 2, . . . , n, n + 1}. Zákazníci jsou ve vrcholech 1, 2, . . . , n. Vrchol se skladem je duplicitně 0 i n + 1, přičemž 0 je výchozí bod a n + 1 konečný. Každému vrcholu i ∈ V přísluší časové okno [ai , bi ], kde a0 je počáteční čas výjezdu a bn+1 nejpozdější možný čas návratu a opět klademe Mij = max{bi + tij − aj , 0}. i,j
Pak lze problém obchodního cestujícího s časovými okny formulovat následovně [16]: minimalizovat
n+1 X n+1 X
(2.22)
cij xij
i=0 j=0
za podmínek
n+1 X
xij = 1, i = 1, 2, . . . , n,
j=1
14
(2.23)
n X
x0,j = 1,
(2.24)
j=1 n X i=0 n X
xij −
n+1 X
xji = 0, j = 1, 2, . . . , n,
(2.25)
i=1
xi,n+1 = 1,
(2.26)
i=1
ai ≤ Ti ≤ bi , i = 0, 1, . . . , n + 1, Ti + tij − Tj ≤ Mij (1 − xij ), ∀i, j; Mij > 0, xij ∈ {0, 1}, i, j = 0, 1, . . . , n, n + 1.
(2.27) (2.28) (2.29)
Podmínky (2.23)–(2.26) určují cestu v grafu z 0 do n + 1 přes všechny vrcholy 1, 2, . . . , n. Z binárních proměnných (2.29) lze vynechat x0,n+1 , jelikož s výjimkou účelové funkce není ve formulaci nikde použita. Existují i verze s tzv. měkkými časovými okny, které je možné za cenu určité penalizace porušit.
2.4.3
Úloha s více obchodními cestujícími
Jiným druhem zobecnění TSP je úloha s více obchodními cestujícími (multiple TSP, m-TSP), ve které uvažujeme m obchodních cestujících (vozidel) a jedno společné depo pro všechny. Obecně předpokládáme, že každé vozidlo musí opustit depo a každý zákazník musí být navštíven právě jedním vozidlem. Cílem je samozřejmě minimalizovat celkovou ujetou vzdálenost vozidel. Na rozdíl od rozvozních problémů se v m-TSP nekladou jednotlivým vozidlům žádné podmínky na kapacitu. Typicky tedy problém může najít uplatnění ve firmách poskytujících různé servisní služby. Problém m-TSP lze také snadno formulovat přímo jako TSP. Nicméně specializované algoritmy budou při řešení m-TSP určitě lepší volbou. Nechť C ∗ = (c∗ij )n×n je matice vzdáleností n zákazníků a r je n-složkový vektor, kde ri udává vzdálenost i-tého zákazníka od depa. Potom řešení problému TSP s maticí vzdáleností
C=
C∗ r r · · · r r> ∞ ∞ · · · ∞ r> ∞ ∞ · · · ∞ .. .. .. . . . . .. . . . r> ∞ ∞ · · · ∞
typu (n+m)×(n+m) udává řešení m-TSP [56]. Posledních m sloupců a m řádků matice C náleží všechny depu, do kterého se cestující dohromady m-krát vrací.
2.4.4
Rozvozní problém
Rozvozní problém vznikne z m-TSP, pokud každému zákazníkovi přísluší ještě nějaká poptávka po zboží, zároveň rozvážející vozidla mají omezenou (ne nutně stejnou) kapacitu. Součet poptávek na trase vozidla nesmí překročit jeho kapacitu. Optimalizovat se zde nemusí jen ujetá vzdálenost, ale často i počet použitých vozidel. Podrobněji se budeme věnovat rozvoznímu problému a především verzi s časovými okny v následující kapitole. 15
3. Rozvozní problém Rozvozní problém (popř. problém okružních jízd), v literatuře známý častěji pod zkratkou VRP (vehicle routing problem), dostaneme v situaci, kdy je k obsluze zákazníků k dispozici více než jedno vozidlo. Aby se zároveň nejednalo jen o zvláštní případ TSP, přidávají se navíc další omezení. Nejčastěji to bývá kapacita vozidla, ale je možné uvažovat i další omezení, např. maximální ujetou vzdálenost vozidla nebo maximální počet zákazníků, které může dané vozidlo obsloužit. Obecně se za zkratkou VRP skrývá celá třída problémů. Praktické problémy totiž přináší mnoho dalších omezení. Podrobnější přehled problémů VRP nabízí [58], nejdůležitější a nejčastější druhy podmínek popíšeme i zde. Široké aplikace problémy mají samozřejmě v dopravě a distribuci zboží, běžnými příklady mohou být rozvoz novin, nápojů a potravin nebo sběr odpadu (viz např. [21]).
3.1
Obecně o rozvozních problémech
Struktura problémů VRP se opět většinou definuje pomocí orientovaného či neorientovaného grafu, jehož vrcholy představují umístění zákazníků a dep s vozidly a hrany cesty mezi dvojicemi vrcholů. Ke každé hraně je přiřazena cena, která obecně představuje vzdálenost. Rovněž bývá hranám přiřazen také čas potřebný k přesunu, který může záviset např. na typu vozidla. Vzhledem k běžnému předpokladu lineárního vztahu mezi těmito veličinami a předpokladu stejného typu vozidel stačí často uvažovat (vhodnou volbou jednotek) pouze jednu cenu hrany. Jednotliví zákazníci bývají nebo mohou být charakterizováni následující sadou vlastností: • vrchol, ve kterém jsou umístěni, • množství zboží (poptávaného či naopak odevzdávaného), povoleny jsou i různé druhy zboží, • časové okno, ve kterém z jakýchkoli důvodů musí být zákazník obsloužen, • čas potřebný k obsloužení zákazníka, může záviset i na typu vozidla, • podmnožina vozidel, které je možné použít k obsluze klienta. Občas ani nemusí být možné splnit požadavky všech zákazníků, v takovém případě je pak třeba vhodně nastavit priority či penalizace za případná nesplnění. Jednotlivé trasy začínají a končí v nějakém depu. Každé depo charakterizují počty různých typů vozidel. V reálných aplikacích zákazníci často náleží jednomu danému depu, které se nachází v jejich blízkosti, a problém pak lze rozdělit na několik menších nezávislých problémů. Vozy se od sebe mohou lišit vlastnostmi: • výchozí depo a depa, ve kterých je možné zakončit trasu, • kapacita vozu - maximální hmotnost, objem či počet kusů, které vůz uveze, • typy zboží, které může vůz převážet, • podmnožina hran, po kterých je vůz schopen jet, 16
• náklady spojené s provozem vozidla. Úloha si může rovněž klást různé cíle: • minimalizace nákladů, • minimalizace počtu použitých vozidel, • vyvážení tras, • minimalizace penalizací spojených s nesplněním požadavků, • různé kombinace uvedených cílů. Další podmínky mohou být kladeny i na řidiče (pracovní doba, povinné přestávky apod.), případně může být pro daného zákazníka nutné navštívit dřív jiné zákazníky stejným vozidlem. A nebylo by obtížné nalézt nebo i vymyslet další různé verze VRP a podmínky, které musí splňovat. V praktických aplikacích bývá často i tolik omezení, že žádné přípustné řešení ani neexistuje. Bohužel ale i ty nejjednodušší varianty VRP bývají výpočetně velmi náročné.
3.2
Kapacitně omezený rozvozní problém
Základní případ problému, ve kterém z možných podmínek uvažujeme pouze omezení na kapacitu vozidel, nazýváme kapacitně omezený rozvozní problém a značíme zkratkou CVRP (capacitated VRP). Poprvé jej navrhli Dantzig a Ramsey koncem 50. let minulého století ve svém článku [12]. Problém se stal velmi populárním díky širokým praktickým aplikacím, obtížné řešitelnosti a také proto, že přirozeně zobecňuje TSP. Poptávku po jednom druhu zboží známe od každého zákazníka předem, všechna vozidla jsou stejná (mají stejnou kapacitu) a jsou umístěna v jediné vozovně. Úkolem je obsloužit všechny zákazníky a přitom minimalizovat náklady. Zároveň každý zákazník musí být navštíven právě jednou (tzn. dodávku není možné rozdělit). Pokusme se nyní CVRP matematicky formulovat. Nechť je opět G = (V, E) úplný graf, kde V = {0, 1, . . . , n}, přičemž vrcholy 1, 2, . . . , n náleží zákazníkům a 0 výchozímu depu, cij je cena hrany (i, j) ∈ E a cii = ∞, ∀i ∈ V . V mnoha případech matice cen (cij ) splňuje trojúhelníkovou nerovnost cik + ckj ≥ cij , ∀i, j, k ∈ V,
(3.1)
což také bývá častý předpoklad pro různé algoritmy. Splnění (3.1) lze jednoduše docílit také přičtením vysokého čísla M > 0 k ceně každé hrany grafu, nicméně případná nějaká dolní či horní mez původního problému se může touto změnou značně zhoršit. Podobně jako u TSP můžeme s ohledem na vlastnosti matice (cij ) rozlišovat mezi nesymetrickou, symetrickou nebo přímo euklidovskou verzí problému CVRP. U každého klienta i ∈ {1, 2, . . . , n} je známa poptávka di ≥ 0. Pro depo případně definujeme d0 = 0. Dále je dán počet vozidel K, z nichž každé má stejnou kapacitu Q > di , ∀i ∈ V . Označme Kmin minimální počet vozidel, kterými je možné obsloužit všechny zákazníky. Pro existenci nějakého řešení je tedy nutné předpokládat K ≥ Kmin . Hodnotu Kmin lze pro malé úlohy získat postupným 17
zkoušením nebo přímo vyřešením tzv. bin packing problému (BPP) odpovídajícího daným poptávkám a kapacitě vozidel. Potom tedy Kmin je v úplném grafu rovno optimální hodnotě úlohy minimalizovat za podmínek
n X
yi
(3.2)
dj xij ≤ Qyi , i = 1, 2, . . . , n,
(3.3)
xij = 1, j = 1, 2, . . . , n,
(3.4)
yi ∈ {0, 1}, i = 1, 2, . . . , n, xij ∈ {0, 1}, i, j = 1, 2, . . . , n,
(3.5) (3.6)
i=1 n X j=1 n X i=1
kde xij = 1, pokud j-tý klient náleží vozidlu i, a yi = 1, pokud i-té vozidlo je použito. Podmínky (3.3) zajistí, že součet všech poptávek libovolně seřazených zákazníků na trase i-tého vozidla nepřekročí jeho kapacitu, dle (3.4) je každý zákazník součástí nějaké trasy. BPP je ale stále ještě silně NP-těžký problém (viz [18]). Ve své základní verzi hledá CVRP přesně K okruhů (tras příslušejících každému z K vozidel). Pokud je K > Kmin , lze některé vozy teoreticky ponechat nevyužity. Ve formulaci, která povoluje nevyužití všech vozů, se pak ale běžně ještě definují náklady na užití vozidla a přidávají se do účelové funkce. Z důvodu omezené kapacity vozidel totiž může nejkratší řešení zároveň potřebovat více vozidel než Kmin i v případě, že matice vzdáleností splňuje trojúhelníkovou nerovnost. Příklad je na obrázku 3.1, kde zákazníci ve vrcholech 2,4 požadují 3 jednotky zboží, ostatní požadují 2. Vozidla mají kapacitu 6. Zřejmě existuje řešení využívající pouze dvě vozidla 0 − 2 − 4 − 0, 0 − 3 − 5 − 1 − 0 s celkovými náklady 45, ale nejkratší přípustné řešení je 0 − 1 − 2 − 0, 0 − 3 − 4 − 0, 0 − 5 − 0 s celkovými náklady 30. 4 7
2 6
5
3
6 11
2
5
0
10
9
6 5
1
7
10
6
2
2
Obrázek 3.1: Ukázka grafu symetrického CVRP 18
CVRP vlastně spojuje dva NP-těžké problémy, což jej činí obzvlášť obtížným: • TSP - v případě neomezené kapacity vozidel Q = ∞ dostáváme m-TSP, který lze formulovat jako TSP, • BPP - otázka, zda existuje přípustné řešení je problém typu BPP, rozhodovací verze BPP je tak principiálně ekvivalentní rozhodovacímu CVRP s cij = 0, ∀i, j ∈ V . Nesymetrickou verzi CVRP lze formulovat jako úlohu smíšeného celočíselného programování minimalizovat za podmínek
n X n X
(3.7)
cij xij
i=0 j=0 n X i=0 n X j=0 n X i=1 n X
xij = 1, j = 1, 2, . . . , n,
(3.8)
xij = 1, i = 1, 2, . . . , n,
(3.9)
xi0 = K,
(3.10)
x0j = K,
(3.11)
j=1
ui − uj + dj ≤ Q(1 − xij ), i, j = 1, 2, . . . , n, di ≤ ui ≤ Q, i = 1, 2, . . . , n, xij ∈ {0, 1}, i, j = 0, 1, . . . , n.
(3.12) (3.13) (3.14)
Omezení (3.12) je obdobou podmínek k eliminaci subcyklů (2.10) navržených pro TSP [42]. Zde kromě eliminace subcyklů také spolu s (3.13) zamezuje vzniku tras s celkovou poptávkou převyšující Q. Je-li totiž xij = 1, pak uj ≥ ui + dj , naopak pokud xij = 0, podmínka (3.12) je díky (3.13) splněna automaticky. Proměnná uj tak představuje horní odhad aktuálně převezeného nákladu na trase po navštívení zákazníka j. Podmínky (3.8) a (3.9) zajistí, že do každého vrcholu vstupuje, resp. jej opouští právě jedna trasa a podmínky (3.11) a (3.10) zaručí, že z depa vyjede a navrátí se přesně K vozů. Odkázat se s touto formulací můžeme na původní článek [15] nebo [33]. Kromě proměnných xii = 0 se ještě běžně nevyužívají (pokládají rovny 0) proměnné xij , pro které platí di + dj > Q. Pokud nechceme nutně využít všechna vozidla, stačí nahradit (3.10), (3.11) podmínkami n X i=1 n X
xi0 ≤ K, x0j =
j=1
n X
(3.15) xi0 .
(3.16)
i=1
Problém pak bude minimalizovat čistě jen ujetou vzdálenost (tzn. počet vozidel má v účelové funkci nulovou váhu). Jiné formulace místo podmínek (3.12) a (3.13) uvažují nerovnosti XX
xij ≥ r(S), ∀S ⊆ V \{0}; S 6= ∅,
i∈S / j∈S
19
(3.17)
kde r(S) značí minimální počet vozidel potřebný k obsloužení všech zákazníků P z množiny S, přičemž r(S) stačí nahradit jednoduchou dolní mezí d ni=1 di / Qe. Počet těchto nerovností ale exponenciálně roste s n. Tuto a mnoho jiných základních formulací CVRP lze dohledat v již zmiňovaném příspěvku [58]. Z tohoto zdroje uvedeme ještě jeden pěkný model CVRP. Zaveďme binární proměnnou xijk , která představuje počet, kolikrát vozidlo k použilo hranu (i, j). Dále definujme yik = 1, pokud zákazník i je obsloužen vozem k, a yik = 0 jinak. Potom lze CVRP popsat úlohou minimalizovat
n X n X K X
(3.18)
cij xijk
i=0 j=0 k=1
za podmínek
K X k=1 K X k=1 n X j=0
yik = 1, i = 1, 2, . . . , n,
(3.19)
y0k = K,
(3.20)
xijk =
n X
xjik = yik , i = 0, 1, . . . , n, k = 1, 2, . . . , K, (3.21)
j=0
uik − ujk + dj ≤ Q(1 − xijk ), i, j = 1, 2, . . . , n, k = 1, 2, . . . , K, (3.22) di ≤ uik ≤ Q, i = 1, 2, . . . , n, k = 1, 2, . . . , K, yik ∈ {0, 1}, i = 0, 1, . . . , n, k = 1, 2, . . . , K, xijk ∈ {0, 1}, i, j = 0, 1, . . . , n, k = 1, 2, . . . , K.
(3.23) (3.24) (3.25)
Podmínky (3.19)–(3.21) zajistí, že každý klient je navštíven právě jednou, K vozů opouští depo a k daného zákazníkovi přijede a odjede od něj tentýž vůz. Model nalezne využití především u komplexnějších variant rozvozních problémů, kdy přípustnost či cena trasy nezávisí pouze na využitých hranách trasy. V případě různých vozidel například stačí jen přidat index k ke kapacitě Q nebo k ceně cij .
3.2.1
Clarkova-Wrightova heuristika
Clarkova-Wrightova heuristika [5] bývá prezentována také pod názvem savings, neboť v principu se snaží propojovat města i, j, jejichž spojením se ušetří nejvíce nákladů, než kdyby města i, j byla součástí rozdílných tras. j
j
i
i
0
0 Obrázek 3.2: Princip metody savings
20
Pokud i je poslední město jedné trasy a j první město jiné trasy, ušetřené náklady sij jsou definovány rozdílem (c0i + c0j + ci0 + cj0 ) − (c0i + cij + cj0 ), tedy sij = ci0 + c0j − cij . Takto se z matice (cij )ni,j=0 vypočtou prvky sij , i, j ≥ 1, i 6= j, které na začátku algoritmus sestupně seřadí a za počáteční řešení zvolí řešení s každým zákazníkem ve vlastní trase. Dále postupuje od nejvyšších sij , a je-li to možné (nová trasa dává smysl a celková poptávka nepřekročí kapacitu), trasy propojí hranou (i, j). Spojení měst i, j se obecně vyplatí, jen je-li sij kladné. Pokud ale chceme minimalizovat počet vozidel, můžeme povolit i spojení s sij < 0. Podle zvolené strategie lze ještě u Clarkovy-Wrightovy heuristiky rozlišovat mezi paralelní a sekvenční verzí. V sekvenční verzi je postupně budována vždy jen jedna trasa (v každém kroku jsou nejprve uvažovány pouze hrany, které lze připojit k poslední vylepšené trase), zatímco v paralelní se trasy spojují libovolně. Pokračujme v příkladu z obrázku 3.1. Vypočteme z matice vzdáleností C matici úspor S.
0 1 2 3 4 5
0
1
2
3
4
5
– 5 6 5 6 2
5 – 2 9 10 6
6 5 2 9 – 10 10 – 11 2 7 6
6 10 11 2 – 7
2 6 7 6 7 –
1 2 3 4 5
1
2
3
4
5
– 9 1 1 1
9 – 1 1 1
1 1 – 9 1
1 1 9 – 1
1 1 1 1 –
S
C
Nechť je ale nyní Q = 7. Paralelní verze spojí města 1, 2 a 3, 4, obojí s nejvyšší úsporou 9. Dále jakýmkoli způsobem k jedné z tras připojí město 5, všechny možnosti totiž ušetří 1 jednotku nákladů. Oproti tomu sekvenční verze nejprve spojí např. 1, 2 s nejvyšší úsporou a k této trase hned připojí další město s nejvyšší úsporou. V našem případě vybere jednu z možností s úsporou 1. Pokud v tomto kroku vytvoří trasu obsahující 3, již určitě neskončí u optimálního řešení, neboť z důvodu omezené kapacity přichází o možnost využití výhodné hrany (3,4). Paralelní přístup je tedy v tomto případě asi lepší volbou. Ke Clarkově-Wrightově heuristice bylo publikováno mnoho způsobů, jak zlepšit efektivitu algoritmu [1], [25], [59] aj. Zajímavou modifikací je například podobně jako v [1] definování ušetřených nákladů sij = t(Si ) + t(Sj ) − t(Si ∪ Sj ), kde Sk značí množinu vrcholů trasy k a t(Sk ) je délka optimálního (suboptimálního, pokud je hledáno čistě heuristicky) řešení TSP přes Sk . Za jiné zobecnění lze považovat Moleovu-Jamesonovu sekvenční heuristiku
21
[41], kde je na budovanou trasu umístěn zákazník k mezi vrcholy i a j podle kritéria minimálního α(i, k, j) = cik + ckj − λcij , popřípadě maximálního β(i, k, j) = µc0k − α(i, k, j), kde λ, µ jsou uživatelsky volitelné parametry. Po každém vložení nového zákazníka lze ještě pozměněnou trasu optimalizovat pomocí 3-opt kroků. Obsáhlý popis dalších klasických heuristik pro CVRP (konstrukčních, dvoufázových zahrnujících shlukování, ořezané metody větví a mezí - truncated branch and bound) nalezneme v [38]. Dvoufázové heuristiky obsahují dvě části, shlukování zákazníků a plánování tras. Typickým příkladem je heuristika nazvaná sweep, která nejprve rozdělí zákazníky na skupiny a potom v rámci skupin naplánuje trasy. Lze ji aplikovat na CVRP se zákazníky rozmístěnými v rovině. Algoritmus si nejprve vybere libovolného zákazníka a k němu do skupiny přiřazuje další, kterým například nejméně vzroste úhel v polárním systému souřadnic, samozřejmě dokud je možné obsloužit zákazníky jedním vozem. Ve druhé fázi pro každou skupinu zvlášť řeší problém obchodního cestujícího. Historie vývoje klasických heuristických algoritmů je jistě velice zajímavá, nicméně dnes již podobné algoritmy většinou naleznou nějaké přípustné řešení v minimálním čase a málokdy tak dokáží naplno využít možnosti dnešní výpočetní techniky. Proto se v posledních letech vývoj heuristických algoritmů ubírá směrem k metaheuristikám, které začínají právě tam, kde nějaká jiná jednoduchá heuristika skončila. Výchozí řešení jako takové samozřejmě má vliv na další průběh algoritmu, jeho kvalita by ovšem na kvalitu nejlepšího výsledku metaheuristiky téměř neměla mít vliv. V této práci se budeme zabývat tabu prohledáváním v rámci problému VRP s časovými okny. Protože VRP s časovými okny přímo zobecňuje CVRP, nebude problém algoritmus změnami parametrů přizpůsobit potřebám CVRP.
3.3
Rozvozní problém s časovými okny
Rozvozní problém s časovými okny (VRPTW - vehicle routing problem with time windows) je přímým zobecněním CVRP. Nově obsluha zákazníka i musí začít v daném časovém intervalu [ai , bi ], bi ≥ ai ≥ 0. Vozidlům je povolen příjezd před okamžikem ai , pak ale musí čekat, až bude klient k dispozici. Příjezdy později než v čase bi povoleny nejsou. Protože porušení časových oken není povoleno, jedná se o problém s tzv. tvrdými časovými okny. Měkká časová okna porušení povolují obvykle za cenu penalizace v účelové funkci. V praktických situacích se omezení na časová okna přirozeně objevují. Často mohou být zákazníci obslouženi jen v určitých časových intervalech jako např. provozní doba, doba před otevřením obchodu apod. Proto je VRPTW důležitý optimalizační problém. VRPTW přejde v CVRP, když ai = 0 a bi = ∞, ∀i ∈ V . Odtud je opět jasná NP-obtížnost problému. Odpověď na otázku, zda vůbec existuje přípustné řešení problému VRPTW (TSPTW) je samo o sobě silně NP-úplný problém [51].
22
Kvůli časovým oknům závisí přípustnost dané trasy na směru, kterým vozidlo projíždí. Proto se VRPTW téměř vždy definuje na orientovaném grafu G = (V, E). Předpokládejme nyní V = {0, 1, . . . , n, n + 1}, kde depo je reprezentováno dvěma vrcholy 0 a n + 1. Každá trasa je pak definována jako cesta v grafu G z vrcholu 0 do vrcholu n + 1. Podobně jako v CVRP počet vozidel se stejnou kapacitou Q je roven K, známou poptávku i-tého klienta značíme di . Pro každou hranu (i, j) ∈ E je dána kromě ceny cij také doba přesunu tij . Dále označme si , i ∈ V dobu trvání obsluhy i-tého klienta (s0 = sn+1 = 0). Časová okna definujeme také vrcholům, které náleží depu. Pokud nejsou přímo zadány podmínky na dostupnost vozidel, stačí za časová okna depa zvolit dostatečně malá resp. velká čísla, tj. např. a0 = min {ai − t0i },
b0 = max {bi − t0i },
1≤i≤n
1≤i≤n
an+1 = min {ai + si + ti,n+1 },
bn+1 = max {bi + si + ti,n+1 }.
1≤i≤n
1≤i≤n
Bez újmy na obecnosti uvažujme úplný graf G. Pod VRPTW pak rozumíme úlohu minimalizovat
n+1 X n+1 X
K X
cij
i=0 j=0
za podmínek
K n+1 X X
(3.26)
xijk
k=1
xijk = 1, i = 1, 2, . . . , n,
(3.27)
k=1 j=1 n+1 X
x0jk = 1, k = 1, 2, . . . , K,
(3.28)
j=1 n+1 X i=0 n X
xijk −
n+1 X
xjik = 0, j = 1, 2, . . . , n, k = 1, 2, . . . , K,
(3.29)
i=0
xi,n+1,k = 1, k = 1, 2, . . . , K,
(3.30)
i=0
xijk (wik + si + tij − wjk ) ≤ 0, i, j = 0, 1, . . . , n + 1, k = 1, 2, . . . , K, n+1 X i=0
di
n+1 X
xijk ≤ Q, k = 1, 2, . . . , K,
(3.31) (3.32)
j=0
ai ≤ wik ≤ bi , i = 0, 1, . . . , n + 1, k = 1, 2, . . . , K, xijk ∈ {0, 1}, i, j = 0, 1, . . . , n + 1, k = 1, 2, . . . , K.
(3.33) (3.34)
Binární proměnná xijk = 1, když vůz k využívá hranu (i, j), reálná proměnná wik představuje čas, ve kterém vůz k začne obsluhovat klienta i. Podmínka (3.31) je nelineární, ale existuje snadná linearizace, viz později (3.44). Tato formulace dodržuje zavedený jednoduchý styl značení celé této práce. V obecném grafu, pokud chceme vynechat zbytečné proměnné, se formulace problému (viz [7]) zkracuje pomocí značení N = V \{0, n + 1}, δ + (i) = {j ∈ V | (i, j) ∈ E}, δ − (j) = {i ∈ V | (i, j) ∈ E}, K = {1, 2, . . . , K} 23
na úlohu X
minimalizovat
cij
X
(3.35)
xijk
k∈K
(i,j)∈E
za podmínek
X
X
xijk = 1, ∀i ∈ N,
(3.36)
k∈K j∈δ + (i)
X
x0jk = 1, ∀k ∈ K,
(3.37)
X
(3.38)
j∈δ + (0)
X
xijk −
i∈δ − (j)
xjik = 0, ∀j ∈ N, ∀k ∈ K,
i∈δ + (j)
X
xi,n+1,k = 1, ∀k ∈ K,
(3.39)
i∈δ − (n+1)
X i∈N
di
X
xijk ≤ Q, ∀k ∈ K,
(3.40)
j∈δ + (i)
xijk (wik + si + tij − wjk ) ≤ 0, ∀k ∈ K, ∀(i, j) ∈ E, ai ≤ wik ≤ bi , ∀k ∈ K, ∀i ∈ V, xijk ∈ {0, 1}, ∀k ∈ K, ∀(i, j) ∈ E.
(3.41) (3.42) (3.43)
Podmínka (3.36) zajistí navštívení každého zákazníka právě jednou. Podmínky (3.37)–(3.39) určují, že vrchol 0 opustí právě K vozů, přijíždějící vůz k zákazníkovi se shoduje s odjíždějícím a do vrcholu n+1 se navrátí K vozů. Ve VRPTW obvykle povolujeme hranu (0, n + 1) s nulovou cenou. Její použití vozem k pak odpovídá nevyjetí vozu k z depa. Dle (3.40) nesmí součet všech poptávek přes klienty navštívené vozem k překročit kapacitu Q. Konečně (3.41) je vlastně implikace (xijk = 1) ⇒ (wik + si + tij ≤ wjk ), která zajišťuje časovou konzistenci a spolu s (3.42) splnitelnost časových oken. Rovněž zde plní funkci eliminace subcyklů. Kvůli (3.41) je uvedená formulace nelineární. Toto omezení lze ale snadno linearizovat pomocí wjk ≥ wik + si + tij − Mij (1 − xijk ), ∀k ∈ K, ∀(i, j) ∈ E,
(3.44)
kde Mij = max{0, bi + si + tij − aj }. Meze na proměnné času wik lze dle [7, 15] také ještě zesílit: wik ≥ ai +
X
max{0, aj − ai + sj + tji }xjik , ∀k ∈ K, i ∈ V,
(3.45)
max{0, bi − bj + si + tij }xijk , ∀k ∈ K, i ∈ V.
(3.46)
j∈δ − (i)
wik ≤ bi −
X j∈δ + (i)
3.4 3.4.1
Metody řešení rozvozních problémů Postup pomocí matematického programování
Jeden z běžných přístupů k řešení více či méně složitých optimalizačních problémů v praxi spočívá ve vhodné formulaci problému jako úlohy (celočíselného) lineárního programování a použití kvalitního optimalizačního software. Zbytek je pak už jen otázkou času v závislosti na složitosti problému, použitém softwaru 24
i hardwaru. Ne vždy, jak ukážeme později v numerické studii na VRPTW, nutně vede tento postup k výsledku. Nicméně uvedené formulace k použití technik celočíselného programování přímo vybízejí. Pro malé úlohy jde navíc asi o vůbec nejpohodlnější postup. Cílem je tedy řešit úlohu (MIP) např. ve tvaru minimalizovat c> x za podmínek Ax = b, x ≥ 0, xj ∈ Z, ∀j ∈ J, kde c ∈ Rn , b ∈ Rm jsou vektory, A ∈ Rm×n je matice, x ∈ Rn je vektor proměnných a J ⊂ {1, 2, . . . , n}. Obecně se úlohy MIP řeší metodou větví a mezí založené na lineárním relaxaci [39]. Postup je následující. Nejprve se odstraní podmínka na celočíselnost a vyřeší se zbylá úloha LP. Splňuje-li optimální řešení podmínky celočíselnosti, jsme hotovi. Pokud nikoliv, algoritmus vybere nějakou proměnnou, která podmínku porušuje, a rozdělí výpočet do dvou větví. Například bylo-li v optimálním řešení x1 = 1.7 a má platit x1 ∈ Z, v první větvi vznikne podmínka x1 ≤ 1, ve druhé x1 ≥ 2. Takto se původní problém rozdělí na dva problémy s jedním omezením navíc. Pokud se podaří vyřešit oba nově vzniklé problémy, lepší řešení bude i optimálním řešením původního problému. Stejný postup větvení se samozřejmě dále opakuje a vytváří se vyhledávací strom. Podproblémy se postupně stále zmenšují až nakonec i nějaká LP relaxace bude celočíselná. Jednotlivým problémům, které výpočet generuje, říkáme uzly stromu. Uzly, ze kterých zatím nepokračuje žádná větev, nazýváme listy. Je-li řešení problému v nějakém uzlu celočíselné, uzel již není třeba dále prohledávat. Hodnota nejlepšího nalezeného celočíselného řešení ze všech uzlů (tzv. incumbent) tvoří horní mez. Druhý případ, kdy se zkoumání daného uzlu zastaví, je, pokud optimum lineární relaxace je horší než nejlepší nalezená horní mez nebo přípustné řešení lineární relaxace neexistuje vůbec. Problémem rozvozních problémů je, že právě lineární relaxace bývá příliš slabá (viz [7, 40]), což vede k obrovskému množství prohledávaných uzlů. Protože předpokládáme minimalizační problém, dolní mez lze definovat jako minimum optimálních hodnot LP přes všechny listy. Rozdíl mezi horní a dolní mezí nazýváme gap. Optimalitu výsledku prokážeme, když dostaneme gap roven 0. Moderní řešiče obsahují navíc řadu dalších pokročilých funkcí, které mohou zrychlit výpočet. • Presolve - Presolve zpravidla označuje soubor procedur, které jsou schopny redukovat a zjednodušit úlohu ještě před startem metody větví a mezí. Modely často obsahují nadbytečné informace, které mohou zpomalovat výpočet prováděním zbytečných operací. Model může být buď zbytečně velký (nadbytečná omezení, fixované proměnné) nebo meze proměnných mohou být zbytečně slabé či omezení je možné zesílit použitím jiných koeficientů. Zatímco první možnost zmenšuje velikost úlohy, vhodné změny koeficientů napomáhají posílení lineárních relaxací (lépe aproximují konvexní obal celočíselných řešení). Uvažujme následující příklad podmínek x1 + x2 + x3 ≤ 6, x1 ≥ 1, x2 ≥ 2, 25
x3 ≥ 3. Zřejmě jediná možnost, jak je splnit, je volba xi = i, a tudíž lze tyto proměnné nahradit konstantami v celé formulaci a uvedené podmínky odstranit. Jiný příklad redukce, specifické pro MIP, je také jednoduchý. Uvažujme omezení 2x1 + 2x2 ≤ 1. Obě strany vydělíme 2: x1 + x2 ≤ 1/2, a protože předpokládáme x1 , x2 ∈ Z, můžeme druhou nerovnost nahradit x1 + x2 ≤ 0. Pokud navíc předpokládáme nezápornost, dostáváme rovnou x1 = x2 = 0. Dalším úkolem může být odhalení struktur (např. logické vztahy mezi proměnnými), které budou důležité později kvůli možnostem větvení nebo generování řezných rovin. Detailnější popis podobných přípravných výpočtů je popsán v [52]. • Cutting planes - Smyslem je kdykoli v průběhu řešení nalézt řezné roviny (sečné nadroviny), které zúží prostor řešení a odstraní tak v případě MIP nežádoucí neceločíselná řešení. Proto také podobné algoritmy k řešení MIP úloh patří do třídy tzv. branch and cut algoritmů a aplikace řezných rovin tvoří jednu z nejdůležitějších součástí algoritmů pro MIP. Jednotlivých řezů (nerovností) lze definovat velké množství (viz např. [8]), zde uvedeme dva příklady. Předpokládejme, že v lineární relaxaci problému s podmínkou x1 + 2x2 + 3x3 + 4x4 ≤ 6, x1 , x2 , x3 , x4 ∈ {0, 1} je optimální řešení problému x1 = 1, x2 = 0, x3 = x4 = 2/3. Protože ale 3 + 4 > 6, není možné mít x3 = x4 = 1, a tedy musí platit x3 + x4 ≤ 1. Přidáním tohoto omezení se zřejmě odřízne i aktuální optimální řešení, neboť 2/3 + 2/3 > 1. Nyní uvažujme úlohu (převzatou z [6]) maximalizovat 11x1 + 4.2x2 za podmínek − x1 + x2 ≤ 2, 8x1 + 2x2 ≤ 17, x1 , x2 ≥ 0, x1 , x2 ∈ Z. Přidáním skluzových proměnných a odstraněním podmínky celočíselnosti dostaneme úlohu maximalizovat 11x1 + 4.2x2 za podmínek − x1 + x2 + x3 = 2, 8x1 + 2x2 + x4 = 17, x1 , x2 , x3 , x4 ≥ 0
26
s optimálním řešením x1 = 1.3, x2 = 3.3, x3 = x4 = 0. Jeden z řádků výsledné simplexové tabulky udává x2 + 0.8x3 + 0.1x4 = 3.3, dostaneme jej vhodným sečtením násobků podmínek, a protože má platit x2 ∈ Z, musí také platit 0.8x3 + 0.1x4 = 0.3 + k, kde k ∈ Z. Z nezápornosti levé strany plyne k ≥ 0, tedy 0.8x3 + 0.1x4 ≥ 0.3. Tento typ nerovnosti se nazývá Gomoryho řez [22]. Všimněme si, že tato nerovnost nepřipustí současné optimální řešení. • Pokročilé strategie větvení - Především jde o výběr uzlu a výběr proměnné k rozvětvení. • Heuristiky - Heuristiky v souvislosti s MIP jsou různého typu. Patří sem různé zaokrouhlovací, které jednoduše s ohledem na přípustnost zaokrouhlí řešení lineární relaxace, a to buď najednou nebo iterativně. Dále sem patří i zlepšovací heuristiky a metaheuristiky, které prohledávají okolí nejlepšího nalezeného řešení s cílem nalézt řešení ještě lepší a jejichž přínosem je hlavně rychlejší nalezení kvalitního řešení. • Paralelní implementace • Automatické ladění parametrů Průběh a chování algoritmu lze v případě potřeby ovládat a upravovat nastavením mnoha dalších různých parametrů, případně přímo vstoupit do výpočtu pomocí tzv. callbacků. S modelováním problémů jako úloh MIP souvisí ale také řada úskalí. • Špatně navržené modely - Například některé proměnné zbytečně neomezené, velmi nízké nebo naopak velmi vysoké koeficienty (zbytečně vysoké konstanty M ), což celkově může vést k numerickým problémům. • Velikost problému - Velikost problému je důležitá. Mnoho proměnných a podmínek může vést k pomalému výpočtu lineárních relaxací, zároveň velké problémy často obsahují mnoho různých druhů podmínek, které obecně mohou lineární relaxace oslabovat. • Problém symetrie - Úloha MIP je symetrická, pokud její proměnné lze permutovat, aniž by se měnila struktura problému. Symetrické úlohy bývají vůbec jedny z nejobtížnějších k vyřešení, neboť podproblémy ve vyhledávacím stromu jsou často izomorfní a je prováděno mnoho opakovaných operací. Přirozeným způsobem odstraňování symetrie je přidávaní dalších vhodných podmínek, a to buď dynamicky během výpočtu nebo na začátku k výchozí
27
formulaci. Konkrétně v našem případě VRPTW lze značnou symetrii odstranit např. pomocí nerovností n X
x0jk ≥
j=1
X
n X
x0j,k+1 , k = 1, 2, . . . , K − 1,
(3.47)
j=1
cij xijk ≥
(i,j)∈E
X
cij xij,k+1 , k = 1, 2, . . . , K − 1.
(3.48)
(i,j)∈E
Protože součet nj=1 x0jk = 1, je-li použito k-té vozidlo, nerovnosti (3.47) zajistí, že všechny použité vozy budou náležet nízkým indexům. Nerovnostmi (3.48) lze dokonce docílit seřazení tras podle ujeté vzdálenosti. Podobně lze trasy seřadit podle rozváženého nákladu nebo čistě jen lexikograficky dle indexu prvního zákazníka. Bohužel pouhým statickým zařazením do základní formulace dostaneme spíše komplikovanější úlohu, neboť kromě zvětšení úlohy se také mění relativní důležitost proměnných, tudíž rychlé nalezení kvalitního řešení spíše stěžují. Na druhou stranu dnes již optimalizační softwary běžně mají také implementovány vlastní procedury k odhalení symetrie. P
Rozvozní úlohy většinou trpí podobnými problémy, což vede k tomu, že jsou jen málokdy vhodné k řešení univerzálními algoritmy pro MIP úlohy. Přítomnost podmínek, které lze přirozeně formulovat nelineárně, může být jedním z důvodů neefektivity postupu. Proto jsou u těchto úloh často vhodné různé dekompoziční metody či přeformulování.
3.4.2
Metoda generování sloupců
S problémem slabé dolní meze, který často souvisí s použitím vysokých konstant M ve formulaci celočíselného programování, může pomoci např. přeformulování problému do tvaru minimalizovat
X
cr yr
(3.49)
αir yr ≥ 1, i = 1, 2 . . . , n,
(3.50)
yr ≤ K,
(3.51)
r∈R
za podmínek
X r∈R
X r∈R
yr ∈ {0, 1}, ∀r ∈ R,
(3.52)
kde R značí množinu všech přípustných tras, cr náklady celé trasy r a αir , yr jsou parametry resp. binární proměnné, pro které platí αir = yr =
1, 0 1, 0
je-li zákazník i navštíven trasou r, jinak, je-li trasa r součástí optimálního řešení, jinak.
Poznamenejme jen, že za tímto přeformulováním je ve skutečnosti teoreticky skryta Dantzig-Wolfeho dekompoziční metoda [13] spolu s uplatněným předpokladem 28
homogenní skupiny vozidel. Zde je ale zřejmé, že úloha (3.49)–(3.52) z dostupných tras vybere maximálně K tras takových, že každého zákazníka navštíví minimálně jednou. Jedná se o tzv. pokrývací problém (set covering problem, SCP). Podmínka (3.50) je napsána formou nerovnosti, ale stejná podmínka s rovností by byla ekvivalentní (problém přejde v tzv. dělící problém - set partitioning problem, SPP), neboť zde předpokládáme platnost trojúhelníkové nerovnosti matice vzdáleností. Potom i v optimálním řešení SCP bude každý zákazník navštíven právě jednou. SCP přímo neurčuje řešení původního problému, protože pořadí zákazníků na trase není dáno, a tuto informaci je třeba předat odděleně. Zásadním problémem formulace ale je, že zde máme exponenciálně mnoho proměnných. Hlavní myšlenka metody generování sloupců je, že do modelu nepotřebujeme zahrnout všechny proměnné. Místo toho stačí pracovat pouze s redukovaným problémem, kde místo R uvažujeme pouze R0 ⊂ R a vhodné trasy přidáváme až v průběhu výpočtu. Jejich hledání odpovídá řešení nějakého subproblému. Vezměme lineární relaxaci úlohy (3.49)–(3.52) omezené na R0 ve tvaru minimalizovat
X
cr yr
(3.53)
αir yr ≥ 1, i = 1, 2 . . . , n,
(3.54)
yr ≤ K,
(3.55)
yr ≥ 0, ∀r ∈ R0 .
(3.56)
r∈R0
za podmínek
X r∈R0
X r∈R0
Označme y 0 její optimální řešení a nechť π 0 = (π10 , π20 , . . . , πn0 ) a θ0 tvoří optimální řešení duální úlohy. Duální proměnné π 0 odpovídají omezením (3.54) a θ0 přísluší (3.55). Nyní chceme zjistit, zda optimální řešení y 0 je také optimálním řešením celého relaxovaného problému minimalizovat
X
cr y r
(3.57)
αir yr ≥ 1, i = 1, 2 . . . , n,
(3.58)
yr ≤ K,
(3.59)
yr ≥ 0, ∀r ∈ R.
(3.60)
r∈R
za podmínek
X r∈R
X r∈R
Podobně jako simplexový algoritmus v každé iteraci vybírá nový sloupec ke vstupu do bazického řešení a zastaví se po konečně mnoha krocích s primárně přípustným bazickým řešením, jehož báze je zároveň duálně přípustná, stačí nahlédnout k duální úloze úlohy (3.57)–(3.60) maximalizovat za podmínek
n X i=1 n X
πi − Kθ
(3.61)
αir πi − θ ≤ cr , ∀r ∈ R,
(3.62)
i=1
πi ≥ 0, i = 1, 2 . . . , n, θ≥0
29
(3.63) (3.64)
a uvědomit si, že splňuje-li (π 0 , θ0 ) všechna omezení (3.62), pak y 0 tvoří optimální řešení (3.57)–(3.60). Pokud se tedy podaří nalézt omezení r, pro které platí n X
αir πi0 > cr + θ0 ,
i=1
řešení (π 0 , θ0 ) není přípustné. V důsledku toho hledáme sloupec (trasu) r, který minimalizuje cr −
n X
αir πi0 ,
(3.65)
i=1
a je-li tato hodnota menší než −θ0 , nalezli jsme porušující podmínku. Příslušný sloupec je následně přidán do redukovaného problému (3.53)–(3.56) a celý proces se opakuje, dokud lze nalézat porušující podmínky. Samotný postup generování sloupců není zcela zřejmý a nabízí různé možnosti. Například v případě VRPTW subproblém, který minimalizuje (3.65) odpovídá hledání nejkratší cesty v grafu s časovými okny a kapacitním omezením, přesněji jde o elementary shortest path problem with time windows and capacity constraints (ESPPTWCC), kde „elementary“ zastupuje podmínku, že každý zákazník může být trasou navštíven maximálně jednou. Formálně lze ESPPTWCC při zavedeném značení a dodefinování π00 = 0 zapsat jako úlohu minimalizovat
(cij − πi0 )xij
X
(3.66)
(i,j)∈E
za podmínek
X
X
di
xij ≤ Q,
(3.67)
j∈δ + (i)
i∈N
X
x0j = 1,
(3.68)
j∈δ + (0)
X
xij −
i∈δ − (j)
X
X
xji = 0, ∀j ∈ N,
(3.69)
i∈δ + (j)
xi,n+1 = 1,
(3.70)
i∈δ − (n+1)
wi + si + tij − Mij (1 − xij ) ≤ wj , ∀(i, j) ∈ E, ai ≤ wi ≤ bi , ∀i ∈ V, xij ∈ {0, 1}, ∀(i, j) ∈ E.
(3.71) (3.72) (3.73)
Z optimálního i z jakéhokoliv jiného řešení (3.66)–(3.73), jehož hodnota účelové funkce je menší než −θ0 dostáváme cestu v grafu z vrcholu 0 do vrcholu n + 1, tedy novou vhodnou trasu (sloupec) k zařazení do redukovaného problému. Novou trasu s indexem r pak definují cr =
X
cij xij ,
(i,j)∈E
αir =
X
xij , ∀i ∈ V
j∈V :(i,j)∈E
neboli αir =
1, 0
existuje-li j ∈ V : xij = 1, jinak. 30
Problém ESPPTWCC je silně NP-těžký (viz [17]), proto se častěji řeší jen verze bez podmínky maximálně jedné návštěvy zákazníků, ke které již za běžných dodatečných předpokladů existují pseudopolynomiální algoritmy založené na dynamickém programování (např. [14]). Proces hledání vhodných sloupců (tras) nazýváme jejich oceňováním, odtud anglický název metody branch and price. Generování sloupců se totiž kombinuje s algoritmem větví a mezí, neboť hlavní problém (3.49)–(3.52) obsahuje celočíselné proměnné a optimum relaxovaného problému poskytuje pouze dolní mez. Zde se opět nabízí různé strategie větvení. Asi k tomu není vhodné použít přímo proměnné yr , jelikož případ yr = 0 je mnohem častější. Existují modely větvící se podle počtu vozidel, proměnných xijk , součtu proměnných xijk aj. Různé způsoby větvení jsou popsány v [32]. Ani pokročilejší modifikace algoritmu, které kombinují navíc řezné roviny, nemusí stačit na praktické problémy. Nicméně u vzorových problémů v praktické části této práce, ke kterým známe již optimální hodnoty a budeme se jim snažit alespoň přiblížit pomocí heuristik, byla optimální řešení většinou nalezena právě algoritmy na principu generování sloupců. V praxi se ale přeci jen častěji využívají heuristické postupy. Formulaci pomocí SCP lze také použít pro heuristická řešení. Protože samotné generování sloupců není přesně definováno a lze jej provádět v podstatě libovolným způsobem, můžou vhodné sloupce obstarávat i heuristiky. Pouze nebude zaručena optimalita výsledku.
3.4.3
Heuristiky
Heuristické algoritmy se běžně rozdělují do tří kategorií: konstrukční heuristiky, zlepšovací heuristiky a metaheuristiky. V souvislosti s VRP je zvykem heuristiky klasifikovat trochu odlišně [38]: klasické heuristiky a metaheuristiky, přičemž mezi klasické heuristiky patří konstrukční, dvoufázové a zlepšovací. Zde popsané algoritmy se budou vztahovat hlavně k VRPTW. Konstrukční heuristiky Úkolem konstrukčních heuristik je postupně vybudovat přípustné řešení s ohledem na předpokládané náklady. Jsou výhodné zejména, pokud je třeba opravdu rychle nalézt nějaké řešení. Sem také patří heuristika savings, popsaná v části věnované CVRP, kterou lze obdobným způsobem aplikovat i na VRPTW, akorát je kvůli časovým oknům nutné brát v potaz orientaci tras. Dále bychom sem zařadili časově orientovanou metodu nejbližšího souseda [53], která kombinuje tři kritéria. K poslednímu zařazenému zákazníkovi i přidává zákazníka j tak, že nová trasa bude přípustná a zákazník j má nejmenší c∗ij = δ1 cij + δ2 Tij + δ3 vij , kde Tij = bj − (bi + si ), vij = aj − (bi + si + tij ) a δ1 , δ2 , δ3 jsou nezáporné váhy, vij lze interpretovat jako naléhavost navštívení klienta a Tij jako rozdíl mezi časem možného začátku obsluhy u j a dokončením 31
obsluhy u i. Jednou z nejpoužívanějších konstrukčních heuristik je Solomonova vkládací heuristika I1 [53]. Pracuje ve dvou krocích. Nejprve se pro každého dosud nezařazeného zákazníka k vypočte nejlepší dvojice sousedních vrcholů, mezi které jej lze zařadit, podle kritéria nejmenší přidané přidané vzdálenosti a potřebného času. Ve druhé fázi pak vybere a zařadí toho klienta, který má nejvyšší ušetřené náklady podobně jako u metody savings. Přesněji v první fázi se pro každého nezařazeného zákazníka k hledá minimum přes sousední vrcholy i, j α∗ (k) = min{w1 (cik + ckj − λcij ) + w2 (tjk − tj )}, w1 , w2 , λ ≥ 0, i,j
kde tjk označuje začátek obsluhy klienta j, je-li klient k součástí trasy, a tj začátek obsluhy klienta j, pokud k součástí trasy není. Ve druhé fázi se pak vybere zákazník k s maximálním µc0k − α∗ (k), µ ≥ 0 a je zařazen mezi i, j, pro které se nabývá α∗ (k), w1 , w2 , λ, µ jsou volitelné parametry. Zlepšovací heuristiky Zlepšovací heuristiky iterativně zlepšují výchozí přípustné řešení. Na řešení postupně aplikují řadu modifikací, přičemž zachovávají přípustnost řešení. Proces se zastaví, pokud nějaké řešení již nelze tímto způsobem vylepšit. Kromě běžně používaných k-opt se ještě často definují tzv. Or-opt kroky [45], které pouze přesunou po sobě jdoucí tři, dva nebo jeden vrchol v rámci jedné trasy. Heuristika nazvaná Or-opt začíná s přesouváním trojic vrcholů, při dosažení lokálního minima v takto definovaném okolí sníží počet přesouvaných na dva až nakonec i na jeden. 6
1
5
6
5
2
2
3
3 4
1
4
Obrázek 3.3: Ukázka kroku Or-opt přesouvajícího dva vrcholy Or-opt na obrázku 3.3 se zrovna shoduje s jedním propojením typu 3-opt, který jednoduše nahradí 3 hrany jinými hranami. V Or-opt kroku ale vždy zůstane nezměněna orientace průchodu hranami, což je často také důvod, proč se k-opt nehodí pro problémy s časovými okny. Or-opt i k-opt kroky mění strukturu vždy jen jedné trasy, v podstatě optimalizují jen problém obchodního cestujícího (ačkoli zrovna Or-opt krok lze snadno předefinovat a můžeme přesouvat vrcholy do libovolné trasy). Pro VRP je třeba definovat operátory, které budou schopny přesouvat zákazníky i v rámci různých tras. Jedna z možností jak definovat operátory kombinující dvě různé trasy je tzv. 32
2-opt∗ krok [49], který jednoduše vezme dvě trasy Rp , Rq , z každé odebere jednu hranu a opět propojí počáteční část Rp s koncovou částí Rq a obráceně. 2-opt∗ krok je zvláštním případem tzv. CROSS-exchange kroku [57], který nejprve pro dané dvě trasy odebere z každé z nich dvě hrany (u jedné trasy stačí odebrat i jen jednu) a následně jednoznačně propojí trasy tak, aby získal nové přípustné řešení a orientace průchodu hranami se nezměnila. Na obrázku 3.4 jsou odebrány křížící se hrany, zde jde dokonce o 2-opt∗ krok, neboť vrcholy 1,3 jsou napojeny přímo na depo d. Je-li z jedné trasy odebrána pouze jedna hrana, mezi její vrcholy se zařadí „odříznutí“ zákazníci z druhé trasy. Na CROSS-exchange krok lze také nahlížet jako na přesouvání resp. výměnu po sobě následujících zákazníků mezi trasami (zobecňuje Or-opt krok pro více tras). Počet takto vyměňovaných zákazníků v jedné trase se pak může shora omezit, aby okolí definované pomocí CROSS-exchange kroků nebylo příliš veliké. d
d
d
d
5
6
5
6
2
4
2
4
1
3
1
3
d
d
d
d
Obrázek 3.4: Ukázka CROSS-exchange kroku CROSS-exchange se často dále ještě zobecňuje na tzv. λ-interchange kroky [44]. Nechť je dáno přípustné řešení (R1 , R2 , . . . , Rp , . . . , Rq , . . . , Rm ), kde R1 , R2 , . . . , Rm značí jednotlivé trasy. λ-interchange krok pro každou dvojici tras Rp , Rq a každé jejich podmnožiny Sp ⊂ Rp , Sq ⊂ Rq takové, že |Sp | ≤ λ a |Sq | ≤ λ, vytvoří nové trasy skládající se z Rp \Sp ∪ Sq a Rq \Sq ∪ Sp . Okolí definované pomocí λ-interchange kroků pak obsahuje všechna přípustná řešení, která lze sestavit výběrem a výměnou množin zákazníků dané maximální mohutnosti. S rostoucím λ se rychle zvětšuje velikost okolí, nejčastější volby λ jsou tedy λ = 1, λ = 2. Volba λ = 1 obsahuje také dva nejjednodušší operátory: • relocate - přesun zákazníka z jedné trasy do druhé, • exchange - výměna dvou zákazníků z různých tras. 33
Přirozeně se definují relocate a exchange operátory i pro problém obchodního cestujícího. Poslední často zmiňované kroky definuje tzv. GEN I operátor (generalized insertion [19]), který zobecňuje relocate takovým způsobem, že přesouvaný zákazník nemusí být nutně přesunut mezi dva po sobě následující zákazníky. Místo toho je zákazník i vložen mezi dva nejbližší zákazníky j a k z druhé trasy pomocí hran (j, i) a (i, k) a zbytek této trasy je v případě potřeby přepojen tak, aby tvořila cyklus nebo cestu z depa do depa obsahující hrany (j, i), (i, k). Ukázka přepojení pomocí GEN I operátoru je na obrázku 3.5. v3
v4
v3
v4
i
i
d
d j
v1
d
d j
k
v2
v1
k
v2
Obrázek 3.5: Ukázka přepojení dvou tras GEN I-operátorem Uvedený výčet operátorů, které různě definují okolí nějakého přípustného řešení VRP, zdaleka není úplný. Pro trochu podrobnější přehled přímo pro VRPTW čtenáře odkážeme na [4]. Postup všech zlepšovacích heuristik bývá podobný. Vstupem je nějaké výchozí přípustné řešení. Poté postupně prohledávají okolní řešení s cílem nalézt lepší. Existují dvě typické strategie. První, jakmile objeví nějaké zlepšení, ihned jej prohlásí za nové řešení. Druhá nejprve prohledá všechna sousední řešení a za nové prohlásí nejlepší ze sousedních řešení, které zlepší hodnotu účelové funkce. Při použití pouze mezitrasových operátorů bývá také zvykem vždy reoptimalizovat nově vzniklé trasy. Algoritmus se zastaví, pokud žádné okolní řešení není lepší. Jednotlivé operátory je možné kombinovat. Dosáhne-li algoritmus lokálního minima v jedné definované struktuře okolních řešení, nemusí to být lokální minimum v struktuře jiné. Jediným problémem ale je, že z lokálního minima, které není globální, nemusí být cesty úniku pomocí definovaných operátorů. S tímto nedostatkem si umí poradit až metaheuristiky. Metaheuristiky V posledních desetiletích se mezi heuristickými algoritmy staly populárními metaheuristiky, protože obecně dokáží nalézt lepší řešení klasické heuristiky, a to za cenu větší časové i implementační náročnosti. Spíše než obecným popisem jednotlivých metaheuristik a jejich možností se budeme v další kapitole podrobně zabývat jedním typem - tabu prohledáváním, které lze úspěšně aplikovat nejen na rozvozní problémy. Součástí bude také praktická aplikace přímo na VRPTW. 34
4. Tabu prohledávání Tabu prohledávání (tabu search - TS) navrhl Glover [20] koncem osmdesátých let minulého století. Od této doby byly algoritmy na principu tabu prohledávání použity k řešení mnoha kombinatorických problémů včetně VRP. TS patří mezi algoritmy lokálního prohledávání, kde se uvíznutí v lokálním optimu zabraňuje různými druhy zapamatování si průběhu vyhledávacího procesu. Před vysvětlením samotného principu je třeba uvést některé základní definice.
4.1
Základní terminologie
• Krok - Modifikace neboli transformace řešení. Některé takové modifikace byly popsány v sekci 3.4.3. • Okolí - Intuitivně jsme již výraz okolí používali. Možná by bylo vhodnější jej označit jako množinu sousedních řešení. Jednoduše jde o všechna přípustná řešení, která lze vygenerovat pomocí nějakého definovaného kroku. • Krátkodobá paměť - Protože algoritmy lokálního prohledávání mají tendenci se v krátké době vracet do předcházejících nalezených řešení, je třeba si pamatovat již prozkoumaná řešení. K tomu slouží krátkodobá paměť. V krátkodobé paměti jsou uložena buď přímo řešení, nebo jen změny atributů, které vedli k opuštění nějakého řešení. Protože porovnávání a zapamatování přímých řešení může být výpočetně náročné, využití zde naleznou také různé hašovací funkce. • Tabu seznam - Seznam zakázaných kroků nebo změn, které by vedli zpět k již navštívenému nebo pravděpodobně nezajímavému řešení. • Délka tabu seznamu - Počet iterací, po který trvá zákaz modifikací uvedených v tabu seznamu. Příliš krátká délka tabu seznamu může vést k zacyklení prohledávání. Naopak příliš dlouhá délka může natolik modifikovat okolí, že mnoho potenciálně zajímavých řešení bude přeskočeno. • Aspirační kritérium - Kritérium, které povolí provést uvedený krok, přestože je daným tabu seznamem zakázaný. Typickou volbou aspiračního kritéria je případ, kdy nové řešení bude dosud vůbec nejlepší nalezené. • Dlouhodobá paměť - Dlouhodobá paměť slouží ke zlepšení inteligence algoritmu. Například často prováděné kroky, které nevedou k žádnému zlepšení, lze penalizovat a časem prozkoumávat i dosud opomíjené kroky nebo naopak preferovat slibné kroky. S dlouhodobou pamětí často pracují následující dva pojmy. • Zintenzivnění - Zintenzivnění prohledávání slouží k důkladnějšímu prohledávání okolí nejlepších řešení. • Diverzifikace - Diverzifikace se naopak snaží navést vyhledávací algoritmus k odlišným, dosud neprozkoumaným řešením.
35
Mnoho aplikací ani neobsahuje pokročilé možnosti TS algoritmu, neboť kvalitní řešení nalézají i jednodušší implementace. Nechť N (s) označuje množinu okolních přípustných řešení a f (s) účelovou funkci přípustného řešení s. Zcela základní minimalizační TS algoritmus na datech pro VRP vypadá následovně. Algoritmus 1: Základní algoritmus tabu prohledávání pro VRP Data: Instance problému VRP Result: Seznam přípustných cest pokrývající všechny zákazníky s=počáteční_řešení; s∗ = s; while není překročen předepsaný počet iterací do najdi nejlepší přípustné řešení s0 ∈ N (s), které není zakázané nebo splňuje aspirační kritérium; if f (s0 ) < f (s∗ ) then s∗ = s0 ; end s = s0 ; aktualizuj tabu seznam; end vypiš s∗ ; Hlavní a nejdůležitější myšlenkou algoritmu je tabu seznam. Při inicializaci je seznam prázdný. Po každé iteraci je do seznamu přidána inverzní transformace k transformaci, která vytvořila aktuální řešení. Je-li délka tabu seznamu L, po L iteracích transformace seznam opouští a každou novou přidanou transformaci doprovází vyloučení té nejstarší. Algoritmus při každém kroku nemusí nutně nalézt řešení s lepší hodnotou účelové funkce, proto se dokáže dostat i z lokálního optima. Pokud se algoritmus po nějaké době přeci jen vrátí do již navštíveného řešení, zpravidla okolí redukované skrze tabu seznam je jiné, čímž se zabrání dalšímu zacyklení. Koncept krátkodobé a dlouhodobé paměti můžeme demonstrovat na příkladě obchodního cestujícího. Předpokládejme problém o pěti městech. Nechť je úvodní řešení dáno posloupností 1–2–3–4–5 a zvolme exchange krok pro definování okolí, tj. prohození dvojice zákazníků. Délku tabu seznamu uvažujme 3. Provedeme postupně kroky 1-2, 3-4, 2-3, 2-4, 1-2, čímž dostaneme řešení 3–2–1–4–5. Maticově pak můžeme zapsat obě paměti v poslední iteraci například tabulkou 4.1.
1 2 3 4 5
1
2
3
4
5
– 2 0 0 0
3 – 1 1 0
0 1 – 1 0
0 2 0 – 0
0 0 0 0 –
Tabulka 4.1: Maticový zápis pamětí pro TS algoritmus TSP
36
Horní trojúhelníková matice představuje krátkodobou paměť, výměna měst 1,2 nepůjde použít v následujících třech iteracích, podobně města 2,4 v následujících dvou atd. Dolní trojúhelníková naopak představuje dlouhodobou paměť. Zde sčítá celkový počet provedených typů výměn. Města 1 a 2 byla prohozena dvakrát, ostatní provedené výměny jen jednou.
4.2
Aplikace tabu prohledávání na rozvozní problém s časovými okny
Nyní již budeme schopni přizpůsobit jednotlivé části algoritmu potřebám rozvozního problému s časovými okny. Popsán bude navrhovaný algoritmus tabu prohledávání pro VRPTW. Protože chceme výsledky algoritmu porovnávat s přesnými metodami řešení, budeme minimalizovat pouze celkovou ujetou vzdálenost, jak bývá zvykem u přesných metod. Při porovnávání heuristických algoritmů se totiž jinak běžně porovnává nejprve počet použitých vozidel a až poté ujetá vzdálenost. Výchozí řešení Základní věcí, kterou je třeba zvolit, je heuristika k vytvoření počátečního řešení. Zde tuto funkci bude plnit Solomonova vkládací heuristika I1. Okolí Dále je třeba zvolit operátory, které budou definovat množinu okolních řešení. Budeme používat CROSS-exchange kroky. Velkou výhodu mají tyto kroky i z implementačního hlediska, jelikož každý krok definují pouze dvě dvojice hran k prohození. Protože ale okolí definované pomocí CROSS-exchange kroků může být zbytečně příliš velké, budeme uvažovat pouze restrikci těchto kroků na λ − interchange kroky pro pevné λ neboli platným krokem bude pouze výměna či přesun posloupností po sobě jdoucích zákazníků délek maximálně λ. V případě extrémně krátkých tras, kdy by se jednalo pouze o jejich prohození, tedy o přechod k ekvivalentnímu přípustnému řešení, nejsou ani tyto kroky uvažovány. Tabu seznam Krátkodobou paměť algoritmu zajišťuje tabu seznam na principu zaznamenávání nedávného výskytu zákazníků na trase. Při každém opuštění nějaké trasy zákazníkem je zaznamenána poslední iterace, kdy byl tento zákazník její součástí. Po dobu délky tabu seznamu tt se zákazník stává pro tuto trasu tabu aktivní a má stíženou možnost návratu. Uvažovaný krok je zakázaný, jestliže všichni účastníci výměny míří do trasy, pro kterou jsou tabu aktivní. Naopak jestliže alespoň jeden z účastníků výměny míří do trasy, jíž nebyl součástí po dobu posledních tt iterací, krok je povolen. Diverzifikace Diverzifikace algoritmu funguje na principu náhodného pohybu po prostoru přípustných řešení. V momentě volání algoritmu diverzifikace se pouze provede předepsaný počet náhodných kroků bez ohledu na změny v účelové funkci. Kromě 37
toho, že tento typ diverzifikace často vede i k nalezení aktuálně nejlepšího řešení, má velký význam pro následující koncept dlouhodobé paměti a zintenzivnění, i pokud se hodnota nejlepšího nalezeného přípustného řešení neposouvá. Dlouhodobá paměť V rámci dlouhodobé paměti jsou přímo ukládána nejlepší nalezená přípustná řešení. První typ zintenzivnění Jediný příklad, kdy algoritmus uplatní koncept dlouhodobé paměti, je zintenzivnění skrze dělící problém. Ze všech tras uložených v dlouhodobé paměti se sestaví dělící problém (3.49)–(3.52) s podmínkou (3.50) ve tvaru rovnosti, kterým hledáme optimální dělení množiny zákazníků na přípustné trasy. Z jeho optimálního řešení pak dostaneme nové přípustné řešení, které nemůže být horší než nejlepší nalezené v průběhu prohledávání. V případě kvalitní diverzifikace a vysokého parametru velikosti dlouhodobé paměti jde o velmi účinný nástroj pro vyhledávání kvalitních řešení. Druhý typ zintenzivnění Druhý typ zintenzivnění pochází z myšlenky, že kvalitní řešení již často obsahuje trasy, které jsou součástí i optimálního řešení a na kterých není třeba nic měnit. Z toho důvodu se několik náhodně vybraných tras z nejlepšího nalezeného řešení pevně zafixuje a tabu prohledávání pokračuje na omezené množině bez zafixovaných tras po nějaký menší počet iterací a s kratší délkou tabu seznamu. Tento typ zintenzivnění je samozřejmě nutné několikrát opakovat, protože ne vždy jsou náhodně vybrány vhodné trasy. Nejvíce užitečný je tento postup, zejména pokud nejlepší řešení obsahuje větší množství tras. Změny pouze v rámci jedné trasy Okolí definované v tomto algoritmu využívá pouze změny vždy mezi dvojicí tras. V podstatě je tento postup plně dostačující. Nicméně po každém kroku je na pozměněné trasy ještě navíc aplikována jedna iterace jednoduchých exchange kroků v rámci jedné trasy, tzn. kdykoli při průchodu trasou je identifikován krok, který trasu zkrátí, je ihned proveden. Podobně funguje i poslední případ zlepšovací heuristiky, která optimalizuje jednotlivé trasy, ale již mimo proces tabu prohledávání. Kromě exchange kroku využívá i relocate krok a v případě nalezení nějakého zlepšení volá rekurzivně sama sebe, čímž zajišťuje optimalitu v rámci tohoto okolí. Parametry Nejdůležitějšími parametry, kterými lze ovládat průběh algoritmu jsou délka tabu seznamu, maximální počet přesouvaných po sobě jdoucích zákazníků λ a počet ukládaných elitních řešení. Dalším parametry jsou počet iterací algoritmu tabu prohledávání a parametry spojené s diverzifikací a zintenzivněním. Kromě toho lze různě poskládat uvedené součásti algoritmu a tím také ovlivnit jeho průběh.
38
Různé instance problému mohou vyžadovat různé parametry a k nalezení optimálních řešení je třeba parametry občas ladit. K odstranění vlivu náhody při různě zvolených parametrech ale pomáhají právě koncepty zintenzivnění a diverzifikace. Vlastního druhu zintenzivnění lze dosáhnout také právě volbou parametrů. Například zvýšením λ a snížením délky tabu seznamu lze docílit mnohem důkladnější prohledávání okolí nějakého řešení.
4.3
Implementace
Algoritmus byl implementován v jazyce C++ s použitím standardních knihoven STL. Celý kód je zabalen do jedné třídy a byl zkompilován pomocí nástroje SWIG [3] jako externí balíček skriptovacího jazyka Python, což umožňuje snadné interaktivní ovládání průběhu algoritmu. Za řešič úloh celočíselného programování byl zvolen komerční software Gurobi [23]. Protože použitý překladač GCC (resp. G++) není pod Windows přímo podporován Gurobi, algoritmus komunikuje s Gurobi přes příkazovou řádku a externí textové soubory. Díky tomu lze také případně snáze vyměnit stávající řešič za jiný, například nekomerční. Zdrojové kódy jsou součástí přiloženého CD.
4.3.1
Datové struktury
Základními datovými typy algoritmu jsou tři následující struktury. Struktura ROUTE spojuje informace spojené s danou trasou, tj. seznam zákazníků, jejich počet, pole, ve kterém jsou uloženy iterace posledního výskytu každého zákazníka, a index trasy pro její jednoznačné určení. Z praktických důvodů seznam zákazníků vždy končí 0.1 Struktura MOVE obsahuje informace o přípustném kroku, tj. redukce resp. zvýšení nákladů v případě provedení tohoto kroku, dva ukazatele na pozměňované trasy a čtyři ukazatele (iterátory) na některé zákazníky z těchto tras, které tento krok jednoznačně definují. Struktura SOLUTION obsahuje pouze seznam tras typu ROUTE a celkové náklady takového řešení a je využívána hlavně k ukládání nejlepších nalezených přípustných řešení. Proměnné Zde je uveden seznam všech proměnných zapouzdřených v objektu třídy Vrptw a jejich význam. Není-li uvedeno jinak, jedná se o proměnnou resp. pole proměnných typu integer. • saved - maximální počet uložených elitních řešení, • maxveh - maximální počet použitých vozů, • lambdai - maximální počet přesouvaných následujících zákazníků v jedné trase, • tt - délka tabu listu, 1
Důvodem je, že ukazatel na konec seznamu, kterým je definován nějaký krok, se nemusí zachovat při různých strukturních změnách. Za depem, označeným 0, žádná výměna proběhnout nemůže a ukazatel na konec seznamu není využíván.
39
• folder - řetězec s adresou složky pro ukládání souborů, • nn - celkový počet zákazníků, • c - dvourozměrné pole vzdáleností, • d - pole poptávek, • a - pole dolních mezí časových oken, • b - pole horních mezí časových oken, • s - pole délek obsluhy, • q - kapacita vozidel, • iteration - aktuální iterace, • best_obj - hodnota účelové funkce nejlepšího nalezeného řešení, • current_obj - hodnota účelové funkce aktuálního řešení, • enough_obj - hodnota účelové funkce nejhoršího uloženého řešení, • moves - seznam kroků typu MOVE, • route - seznam tras typu ROUTE, • best_solutions - seznam elitních řešení typu SOLUTION.
4.3.2
Metody
Konstruktor třídy Vrptw pouze nastaví přednastavené hodnoty proměnným iteration = 0, tt = 40, saved = 5000, lambdai = 2, folder = ”\\aktuální složka\\vrptw_files\\”. Součástí třídy Vrptw je také řada dalších různých metod, z nichž ty, které nejsou pomocné a je k nim je povolen přístup zvenčí, je třeba okomentovat. read_data V argumentu metody read_data je řetězec, který obsahuje adresu souboru instance problému, a počet zákazníků, které je třeba načíst. Maximální počet zákazníků je 100, ale lze jej snadno zvýšit před překladem zvýšením parametru velikosti statického pole. Načítaný soubor musí mít zavedený standardní formát z obrázku 4.1, kde na 5. řádku je maximální počet vozidel a jejich kapacita a řádky 10 a víc mají formát i x y d a b s, kde je označeno 40
• i - číslo vrcholu, • x - souřadnice x, • y - souřadnice y, • d - poptávka, • a - dolní mez časového okna, • b - horní mez časového okna, • s - doba obsluhy. R101 VEHICLE NUMBER 25
CAPACITY 200
CUSTOMER CUST NO.
XCOORD.
0 1 2 3 4 5
35 41 35 55 55 15
YCOORD. 35 49 17 45 20 30
DEMAND 0 10 7 13 19 26
READY TIME 0 161 50 116 149 34
DUE DATE 230 171 60 126 159 44
SERVICE TIME 0 10 10 10 10 10
Obrázek 4.1: Formát instancí problému VRPTW K numerickým výpočtům byly použity instance Solomonových problémů [53], kde vzdálenost dvou vrcholů je definována jako euklidovská vzdálenost zaokrouhlená dle konvence [36]: q 1 10 (xi − xj ) 2 + (yi − yj ) 2 . cij = 10
Kvůli možným zaokrouhlovacím chybám algoritmus pracuje rovnou s desetinásobkem této ceny a časových oken. Dále předpokládáme, že platí cij = tij . Výsledkem metody read_data je tedy pouze nastavení proměnných objektu z načtených dat. solomon_heuristic Jako základní heuristika k nalezení nějakého přípustného řešení2 byla zvolena Solomonova vkládací heuristika I1. Metoda solomon_heuristic sestaví nějaké řešení. Navíc je vždy přidána prázdná trasa, kam lze případně přesouvat zákazníky. Dle aktuální hodnoty účelové funkce sestaveného řešení jsou nastaveny proměnné best_obj, current_obj a enough_obj. Dále je třeba vygenerovat všechny kroky, které vedou k nějakému přípustnému řešení. Argumentem metody jsou váhy w1 , w2 a parametry λ, µ, případně lze metodu volat také bez argumentů, což odpovídá nastavení w1 = 1, w2 = 0.05, λ = µ = 1. 2
Protože není brána v úvahu podmínka max. počtu vozidel, nemusí jít teoreticky ani o přípustné řešení. Startu algoritmu to ale nijak nebrání.
41
tabu_search Metodu tabu_search je možné volat, pokud je sestaveno nějaké řešení a k němu jsou vygenerovány přípustné kroky. Jediným argumentem metody je počet iterací, které se mají provést. Jedna iterace spočívá ve vybrání nejlepšího kroku, který není zakázaný nebo splňuje aspirační kritérium, provedení tohoto kroku, aktualizace tabu seznamu, odstranění všech vygenerovaných kroků, které se týkaly pozměněných tras a vygenerování nových kroků, které se týkají pozměněných tras. Pokud byla zaplněna prázdná trasa, je přidána nová. Pokud výměnou vznikla nová prázdná trasa, nová prázdná trasa je odstraněna a její seznam tabu aktivních zákazníků je překopírován do té starší. Před generováním nových kroků je ještě pro obě pozměněné trasy zavolán cyklus, který prochází pozicemi a prohodí vždy dvojici zákazníků v jedné trase, kdykoli jejich prohozením vznikne přípustná kratší trasa. Je-li celková cena nového řešení menší než cena nejhoršího uloženého řešení enough_obj, je i toto řešení přidáno do seřazeného seznamu elitních řešení, který má ale omezenou délku parametrem saved. diversify Diverzifikaci algoritmu zajišťuje metoda diversify postupným aplikováním většího počtu náhodně vybraných přípustných kroků, které jsou generovány ze seznamu moves. Kroky zahrnující prázdnou trasu jsou vynechány. Poté je opět zavolána metoda tabu_search. Argumenty metody diversify jsou počet náhodných kroků a počet iterací metody tabu_search. intensify Zintenzivnění algoritmu je prováděno zafixováním náhodně vybraných tras. Argumenty metody intensify jsou délka tabu seznamu, velikost subproblému (počet nezafixovaných tras včetně prázdné trasy) a počet iterací metody tabu_search. Nejprve jsou uloženy informace o původním řešení, původním nastavení a seznam elitních řešení. Poté je odebrán příslušný počet náhodně vybraných tras, smazány všechny nevhodné kroky, vyprázdněn seznam elitních řešení a nastaveny nové parametry (délka tabu seznamu, nejlepší nalezená a nejhorší uložená hodnota účelové funkce). Na zbylý problém je následně volána metoda tabu_search pro daný počet iterací. Nakonec se k nejlepšímu nalezenému řešení přidají zafixované trasy, vygenerují vhodné nové kroky a je obnoveno původní nastavení. Je-li toto řešení lepší než nejlepší dosud nalezené, je toto řešení přidáno do původního seznamu elitních řešení. Metodu intensify je kvůli náhodnému výběru tras vetšinou potřeba volat v rámci cyklu několikrát. solve_spp Metoda solve_spp pracuje se seznamem elitních řešení. Ze všech existujících tras ze seznamu elitních řešení je sestaven dělící problém. Jako výchozí řešení a horní mez pro algoritmus celočíselného programování je zvoleno nejlepší dosud nalezené, čímž se urychlí celý výpočet. Z optimálního řešení dělícího problému dostaneme nové řešení, které je načteno a uloženo, pokud je lepší než nejlepší dosud nalezené. Řešič Gurobi je volán z příkazové řádky příkazem gurobi_cl.
42
Veškeré vygenerované soubory jsou uloženy do složky definované parametrem folder. print_solution Metoda print_solution jednoduše vypíše na výstup aktuální řešení. V případě zavolání metody print_solution s argumentem typu string, je aktuální řešení zapsáno do souboru s tímto názvem ve složce folder. load_best_solution Metoda load_best_solution pouze načte ze seznamu elitních řešení nejlepší nalezené řešení a aktualizuje vhodné kroky. clear_solutions Metoda clear_solutions smaže všechna elitní řešení a uloží do seznamu pouze aktuální. Mez pro uložení enough_obj nejhoršího kvalitního řešení je pak nastavena uměle na dvojnásobek účelové funkce aktuálního řešení. improve Metoda improve na každou trasu aktuálního řešení aplikuje nějaký relocate či exchange krok, dokud lze nalézat zlepšení. Význam metody je vhodný spíše k ověřování než ke hledání lepších řešení.
4.4
Obecný postup
Předpokládejme, že máme objekt třídy Vrptw, ve kterém jsou načtena data a zvoleny vhodné parametry. Obecně lze při řešení VRPTW pomocí tohoto algoritmu postupovat následovně. Nejprve se sestaví nějaké řešení pomocí metody solomon_heuristic, které může být vhodné ještě zoptimalizovat metodou improve. Následně se spustí tabu_search pro nějaký omezený počet iterací. Dále je vhodné diverzifikovat vyhledávací algoritmus opakovaným voláním metody diversify. Pokud se delší dobu neposouvá hodnota nejlepšího nalezeného řešení best_obj nebo hodnota nejhoršího uloženého řešení enough_obj, lze doporučit metodu solve_spp. Ta, pokud byl vyhledávací algoritmus dobře diverzifikován, již zpravidla nachází velmi kvalitní řešení. Na toto řešení bývá vhodné opakovaně použít metodu intensify, případně lze doporučit snížení parametru tt, zvýšení parametru lambdai, zvýšení parametru saved a opětovné volání metod tabu_search a solve_spp.
43
5. Numerická studie Testované problémy obsahují vždy 100 zákazníků a jsou rozděleny do tří kategorií. U problémů typu R jsou zákazníci rozmístěni rovnoměrně v rovině. Problémy typu C mají zákazníky rozmístěny do shluků v rovině a problémy typu RC kombinují oba typy rozmístění. V dané kategorii je vždy shodné rozmístění zákazníků, ale problémy se liší hodnotami časových oken, přičemž výpočetně nejjednodušší by měly být problémy s nejnižším číslem. Rozmístění zákazníků u jednotlivých typů vykreslují diagramy v přílohách B, C, D. Dále lze každou kategorii ještě rozdělit na dvě podskupiny podle kapacity vozidel. Problémy s číslem větším jak 200 mají vždy větší kapacitu vozidel, což obecně snižuje celkový počet použitých vozidel. Některé problémy jsou výpočetně velmi náročné, proto se často uvažují menší problémy jen pro vybraný počet zákazníků. Zvykem bývá řešit problémy o velikosti 25, 50 nebo 100 zákazníků. Optimální hodnoty účelových funkcí většiny problémů jsou k dispozici na webu [55], popř. [54]. Prakticky veškeré výpočty v této kapitole byly provedeny na počítači s dvoujádrovým procesorem AMD AthlonTM QL-62 2 GHz, pamětí 3GB a 64-bitovým operačním systémem Windows 7.
5.1
Přístup pomocí matematického programování
Některé problémy lze řešit metodami matematického programování. Kvůli obecně vysoké rychlosti výpočtu byl za řešič celočíselného programování opět zvolen software Gurobi verze 5.0.2. Pokud není uvedeno jinak, předpokládáme vždy základní nastavení parametrů softwaru. Jakýkoli uvedený čas je vždy skutečný uplynulý čas, nikoliv CPU čas. Uvažujme problém označený R101. Délka časového okna je u všech zákazníků problému R101 stejná. Navíc jsou tato okna velmi úzká. S použitím základní formulace (3.26)–(3.34), kde jsme nelineární podmínku nahradili (3.44), lze v krátkém čase vyřešit do optimality problémy o velikosti 25, 50 i 75 zákazníků. Dokonce i pro problém o 100 zákaznících algoritmus Gurobi nalezne do 30 minut optimální řešení, prokázat optimalitu se ale do předepsaných 2 hodin nepodařilo. Hledané optimum je 1637.7 a nejlepší dolní mez činila 1625.2, což odpovídá gap 0.76 %. Exponenciální trend závislosti délky doby řešení na velikosti problému ilustruje graf na obrázku 5.1. Problém R102 se liší od R101 pouze v hodnotách časových oken několika zákazníků. Mezi prvními 25 zákazníky je pouze v 8 případech přibližně dvacetkrát širší okno. Již toto činí problém obtížně řešitelným. Optimální řešení R102 s 25 zákazníky zvládne Gurobi nalézt do 1500 s, optimalitu výsledku ale prokázat nedokáže. Po 3000 s výpočtu činil gap ještě více než 30 % (horní mez 547.1, dolní mez 373.28), což svědčí o dalším potřebném obrovském množství času k prokázání optimality. Proto byl tento problém nahrán také na NEOS Server [10] s lepšími výpočetními možnostmi. Bohužel po dosažení gap 17 % software Gurobi přerušil výpočet z důvodu nedostatku paměti. Problematická je tak nejen časová, ale i paměťová složitost algoritmu v případě VRPTW.
44
Uplynulý čas (s)
1500
1000
500
0 n=25
n=50
n=75
n=100
Počet zákazníků n
Obrázek 5.1: Závislost doby potřebné k nalezení optimálního řešení na velikosti problému R101 Prokázání optimality mohou pomoci formulace zahrnující podmínky (3.45), (3.46) a vhodné podmínky k odstranění symetrie problému. Obecně tyto podmínky zpomalují výpočet a nalezení kvalitního řešení a jsou vhodné hlavně k iterativnímu přidávání během výpočtu, ale zadáme-li softwaru již při startu známé optimální řešení, postupný růst dolní meze dolní meze (pokles gap) lze takto mírně urychlit. Na obrázku 5.2 jsou zobrazeny vývoje gap pro základní formulaci a formulaci s (3.45), (3.46) a podmínkami n+1 X j=1
jx0jk ≤
n+1 X
jx0j,k+1 , k = 1, 2, . . . , K − 1,
j=1
které zajišťují lexikografické seřazení tras dle indexu prvního zákazníka. 35 %
Gap
33 %
31 %
Základní formulace
29 %
Formulace s odstraněním symetrie a zúžením oken 0
1000
2000
3000
Uplynulý čas (s)
Obrázek 5.2: Vývoj gap na různých formulacích problému R102.25 Ani ostatní problémy ze sady s rovnoměrně rozdělenými zákazníky nejsou řešitelné v rozumném čase pomocí standardních MIP nástrojů. Pouze snad problém R201 o 25 zákaznících lze snadno vyřešit do optima, ale v případě 50 zákazníků se již optimální řešení do 3000 s nalézt nepodařilo. 45
V případě problémů typu C je situace o trochu příznivější. Předpokládejme pouze problémy o velikosti 100 zákazníků. Bez problémů lze do optima vyřešit problémy C101 a C201. Dále pak lze vyřešit problém C105, ale je nutné nastavit parametr MIPFocus=1 (zaměření na rychlejší hledání nových přípustných řešení). Stejný parametr pomáhá i problému C107, u kterého je optimální řešení nalezeno do 1700 s, prokázat optimalitu se do 3000 s nepodařilo (gap ale jen 0.43 %). Optimální řešení ostatních problémů typu C o velikosti 100 zákazníků se nalézt nepodařilo. Problémy typu RC se zdají být nejobtížnější. Prokázat optimalitu se nepodařilo u žádného problému typu RC a optimální řešení byla do 2000 s nalezena pouze u problémů RC101 a RC201 s 25 zákazníky. U ostatních problémů s 25 zákazníky ani nebylo možné do 2000 s nalézt řešení, jehož hodnota účelové funkce nepřekračuje 1.25 násobek optima. V případě úloh s větším počtem zákazníků byly výsledky samozřejmě ještě mnohem horší. Vyladěním parametrů, zejména vhodným nastavením parametrů řezných nadrovin a poskytnutím většího množství času by asi bylo možné nalézt optimální řešení ještě u některých malých problémů, zejména typu C. Celkově jsou ale možnosti přístupu pomocí celočíselného programování značně omezené. Úlohy, které se podařilo úspěšně vyřešit, byly vždy v nějakém smyslu jednodušší. Buď byla úzká časová okna, zákazníci rozmístěni ve viditelných shlucích nebo byl vyřešen problém jen pro omezený počet zákazníků. Předpokládaným důvodem neúspěšnosti tohoto postupu je celkově slabá dolní mez lineární relaxace. Vraťme se k problému R101 a srovnejme klasickou lineární relaxaci problému s lineární relaxací přeformulování pomocí pokrývacího problému spočtenou postupem ze sekce 3.4.2. Za počáteční množinu tras vezměme všechny trasy přípustných řešení navštívených v průběhu prvních 5 tisíc iterací popsaného algoritmu tabu prohledávání. Díky úzkým oknům problému R101 můžeme snadno a rychle generovat nové trasy přímo řešením MIP formulace problému ESPPTWCC. Dostatečnou motivací k přeformulování problému by pak mohl být graf na obrázku 5.3, 1637.7
Optimální hodnota účelové funkce
1500.0
1000.0
500.0
576.00
1631.15
Klasická lineární relaxace
Lineární relaxace pokrývacího problému metodou generování sloupců
0.0
Obrázek 5.3: Porovnání lineárních relaxací problému R101 46
který porovnává oba typy lineárních relaxací, a kde je černou vodorovnou čarou vyznačeno skutečné optimum účelové funkce původního problému.
5.2
Heuristiky
Hlavním zaměřením práce je studium heuristických algoritmů, ke kterému nás motivuje nemožnost řešení problému standardním způsobem. Při porovnávání heuristik se budeme zabývat pouze problémy o velikosti 100 zákazníků, jelikož u menších problémů zpravidla nebude problém nalézt optimální řešení popsaným algoritmem tabu prohledávání.
5.2.1
Solomonova vkládací heuristika
Nejprve na vybraných problémech porovnáme výsledky jednoduché vkládací heuristiky I1 se skutečnými optimálními hodnotami. Aby byl zajištěn vhodnější výběr parametrů, pro každý problém vybereme nejlepší řešení nalezené heuristikou s parametry z množiny {(w1 , w2 , λ, µ) | w1 = 1; w2 ∈ {0, 0.05, 0.10, 0.15}; λ, µ ∈ {0, 0.1, . . . , 1}}. Výsledky tohoto postupu shrnují tabulky 5.1, 5.2, 5.3. Procentuální hodnoty v tabulkách vyjadřují poměr rozdílu nalezené a optimální hodnoty vzhledem k optimu. Instance Nalezená Optimum Rozdíl problému hodnota R101 R102 R103 R104 R201 R202 R203
1637.7 1466.6 1208.7 971.5 1143.2 1029.6 870.8
1894.7 1748.6 1537.3 1246.9 1459.0 1390.3 1291.4
257.0 282.0 328.6 275.4 315.8 360.7 420.6
(%) 15.69 19.23 27.19 28.35 27.62 35.03 48.30
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0.1, 0.4, 0.1) (w1 , w2 , λ, µ) = (1, 0.1, 0.8, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.4, 0.2) (w1 , w2 , λ, µ) = (1, 0, 1, 0.7) (w1 , w2 , λ, µ) = (1, 0, 0.3, 0.2) (w1 , w2 , λ, µ) = (1, 0, 0.8, 0.2) (w1 , w2 , λ, µ) = (1, 0, 0, 0.7)
Tabulka 5.1: Výsledky heuristiky I1 pro vybrané problémy typu R
Instance Nalezená Optimum Rozdíl problému hodnota C101 C102 C103 C104 C201 C202 C203
827.3 827.3 826.3 822.9 589.1 589.1 588.7
827.3 970.5 964.5 1015.5 634.1 801.5 813.3
0.0 143.2 138.2 192.6 45.0 212.4 224.6
(%) 0.00 17.31 16.73 23.41 7.64 36.05 38.15
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0, 0, 0) (w1 , w2 , λ, µ) = (1, 0, 0, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.2, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0, 0.7) (w1 , w2 , λ, µ) = (1, 0, 0.7, 0.9) (w1 , w2 , λ, µ) = (1, 0, 0.4, 0.8) (w1 , w2 , λ, µ) = (1, 0, 0.8, 0.3)
Tabulka 5.2: Výsledky heuristiky I1 pro vybrané problémy typu C 47
Instance Nalezená Optimum Rozdíl problému hodnota RC101 RC102 RC103 RC104 RC201 RC202 RC203
1619.8 1457.4 1258.0 1132.3 1261.8 1092.3 923.7
2065.4 1845.0 1652.3 1392.8 1811.7 1600.6 1289.5
445.6 387.6 394.3 260.5 549.9 508.3 365.8
(%) 27.51 26.60 31.34 23.01 43.58 46.53 39.60
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0, 1, 0) (w1 , w2 , λ, µ) = (1, 0.05, 0.3, 0.3) (w1 , w2 , λ, µ) = (1, 0.05, 0.7, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.9, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.4, 0.4) (w1 , w2 , λ, µ) = (1, 0, 0.4, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.1, 0)
Tabulka 5.3: Výsledky heuristiky I1 pro vybrané problémy typu RC Uvedené hodnoty účelových funkcí lze jen těžko označit za uspokojivé, známe-li optimální hodnoty. Pouze v jednom případě bylo dosaženo optima a v nejhorším případě byla nejlepší nalezená hodnota přípustného řešení téměř 3/2 optima. Jednotlivá řešení lze samozřejmě ještě optimalizovat hledáním lokálního minima svého okolí pomocí definovaných operátorů. Je-li na řešení nalezená heuristikou I1 zavolána metoda improve, která primitivním způsobem optimalizuje jednotlivé trasy řešení, dosáhneme mírného zlepšení, shrnutého v tabulkách 5.4, 5.5, 5.6. Instance Nalezená Optimum Rozdíl problému hodnota R101 R102 R103 R104 R201 R202 R203
1637.7 1466.6 1208.7 971.5 1143.2 1029.6 870.8
1894.7 1727.3 1493.9 1204.2 1358.6 1279.9 1063.0
257.0 260.7 285.2 232.7 215.4 250.3 192.2
(%) 15.69 17.78 23.60 23.95 18.84 24.31 22.07
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0.1, 0.4, 0.1) (w1 , w2 , λ, µ) = (1, 0.1, 0.8, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.4, 0.2) (w1 , w2 , λ, µ) = (1, 0, 1, 0.7) (w1 , w2 , λ, µ) = (1, 0, 0.3, 0.2) (w1 , w2 , λ, µ) = (1, 0, 0, 0.2) (w1 , w2 , λ, µ) = (1, 0, 0, 0.7)
Tabulka 5.4: Výsledky heuristiky I1 s metodou improve pro vybrané problémy typu R
Instance Nalezená Optimum Rozdíl problému hodnota C101 C102 C103 C104 C201 C202 C203
827.3 827.3 826.3 822.9 589.1 589.1 588.7
827.3 911.9 897.7 922.1 619.1 680.2 661.8
0.0 84.6 71.4 99.2 30.0 91.1 73.1
(%) 0.00 10.23 8.64 12.05 5.09 15.46 12.42
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0, 0, 0) (w1 , w2 , λ, µ) = (1, 0, 0, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0, 0.8) (w1 , w2 , λ, µ) = (1, 0, 0, 0.7) (w1 , w2 , λ, µ) = (1, 0, 0.2, 0.9) (w1 , w2 , λ, µ) = (1, 0, 0, 1) (w1 , w2 , λ, µ) = (1, 0, 0, 0.4)
Tabulka 5.5: Výsledky heuristiky I1 s metodou improve pro vybrané problémy typu C
48
Instance Nalezená Optimum Rozdíl problému hodnota RC101 RC102 RC103 RC104 RC201 RC202 RC203
1619.8 1457.4 1258.0 1132.3 1261.8 1092.3 923.7
2016.6 1795.5 1561.5 1365.4 1677.3 1371.6 1121.1
396.8 338.1 303.5 233.1 415.5 279.3 197.4
(%) 24.50 23.20 24.13 20.59 32.93 25.57 21.37
Parametry % % % % % % %
(w1 , w2 , λ, µ) = (1, 0.05, 0.2, 0.9) (w1 , w2 , λ, µ) = (1, 0.05, 0.3, 0.3) (w1 , w2 , λ, µ) = (1, 0.05, 0.7, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.9, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0.6, 0.8) (w1 , w2 , λ, µ) = (1, 0, 0.1, 0.5) (w1 , w2 , λ, µ) = (1, 0, 0, 0.7)
Tabulka 5.6: Výsledky heuristiky I1 s metodou improve pro vybrané problémy typu RC Mnohem lepších výsledků ale většinou dosáhneme použitím nalezeného řešení jako počáteční řešení nějakého metaheuristického algoritmu.
5.2.2
Tabu prohledávání
Popsaný algoritmus tabu prohledávání vyžaduje alespoň minimální uživatelskou znalost algoritmu a určitou zkušenost s jeho ovládáním a volbou parametrů. Nevhodnou volbou parametrů je možné jej i zcela znehodnotit. Základními a nejdůležitějšími parametry jsou délka tabu listu tt a parametr λ. Velmi nízká volba parametru tt způsobuje zacyklení, které je patrné například z průběhu aktuální hodnoty účelové funkce (obrázek 5.4).
Hodnota účelové funkce
1725.0
1720.0
1715.0
1710.0
1705.0
1700.0 0
25
50
Iterace
75
100
Obrázek 5.4: Průběh aktuální hodnoty účelové funkce algoritmu tabu prohledávání pro problém R101, tt=5, λ=2 Podobně může být hodnota tt jen nedostatečná, která sice algoritmus nezacyklí, ale nedovolí mu se dostat k dalším odlišným přípustným řešením (obrázek 5.5). Bez kvalitní diverzifikace pak algoritmus nemá mnoho příležitostí k nalezení optimálního řešení.
49
Hodnota účelové funkce
1725.0
1700.0
1675.0
1650.0 0
200
400
Iterace
600
Obrázek 5.5: Průběh aktuální hodnoty účelové funkce algoritmu tabu prohledávání pro problém R101, tt=15, λ=2 Průběhy pro vhodné volby parametru tt znázorňuje obrázek 5.6, kde se sice hodnota účelové funkce může pohybovat v průměru ve vyšších hodnotách, ale s přibývajícím počtem iterací algoritmus navštěvuje větší množství rozdílných kvalitních řešení. 1725.0
1700.0
1650.0 1725.0
1700.0 tt = 100
Hodnota účelové funkce
tt = 50
1675.0
1675.0
1650.0 0
200
400
Iterace
600
Obrázek 5.6: Průběh aktuálních hodnot účelové funkce algoritmu tabu prohledávání pro problém R101, tt∈ {50, 100}, λ=2 Je-li ale hodnota parametru tt nesmyslně vysoká, algoritmus se ke kvalitním řešením vůbec nemusí dostat (obrázek 5.7).
50
Hodnota účelové funkce
2250.0
2050.0
1850.0
1650.0 0
200
400
Iterace
600
Obrázek 5.7: Průběh aktuální hodnoty účelové funkce algoritmu tabu prohledávání pro problém R101, tt=1000, λ=2 Na vhodné hodnoty tt mají vliv parametry úlohy (především kapacita vozidel, která ovlivňuje jejich potřebný počet) i volba parametru λ. Vzhledem k definici zakázaných kroků parametr λ ovlivňuje proces prohledávání podobně jako tt a oba parametry spolu navzájem souvisí. S rostoucím λ má algoritmus k dispozici větší okolí a variabilita průběhu hodnoty účelové funkce se snižuje (obrázek 5.8). 1725.0
1700.0
1650.0 1725.0
1700.0 l = 10
Hodnota účelové funkce
l=3
1675.0
1675.0
1650.0 0
200
400
Iterace
600
Obrázek 5.8: Průběh aktuální hodnoty účelové funkce algoritmu tabu prohledávání pro problém R101, tt=50, λ ∈ {3, 10} Je na uživateli, jakou strategii volby parametrů zvolí. Pokud zvolí parametry pro důkladnější prohledávání okolních řešení, algoritmus je nutno častěji diverzifikovat. Naopak pokud zvolí agresivnější postup pohybu po prostoru přípustných řešení, algoritmus může vyžadovat nějaké formy zintenzivnění prohledávání.
51
Nicméně rozmezí pro vhodné volby parametrů je poměrně široké a případný negativní efekt špatné volby mohou zmírnit popsané metody zintenzivnění a diverzifikace. Poslední důležitý parametr je parametr saved, který představuje počet ukládaných nejlepších řešení. Je využíván výhradně při řešení dělícího problému a jeho volbu nelze přesně doporučit, neboť závisí na výkonu počítače, kvalitě nejlepšího nalezeného řešení i různorodosti všech uložených řešení. Často se opakující trasy v navštívených řešeních mohou dělící problém i značně zjednodušit. O identifikaci takových tras se úspěšně starají přípravné výpočty softwaru. V následujících srovnáních byly použity hodnoty parametru saved mezi 5 až 10 tisíci. Numerické výsledky Přistupme nyní ke srovnání nalezených řešení heuristikou se skutečnými optimálními. Porovnávat doby výpočtu nemá příliš význam, jelikož jsou často ovlivněny náhodou. Navíc nelze porovnávat vynaložené lidské úsilí při hledání správných parametrů a pořadí volaných metod. Zkoumat tak budeme pouze, jak často dokáže heuristika v nějakém rozumném časovém intervalu nalézt optimální řešení či nakolik je schopna se alespoň přiblížit. Nutno dodat, že i u problémů, ke kterým zde nejsou prezentována přímo optimální řešení, jich často bylo dosaženo při testování algoritmu. Nicméně v době sepisování práce se v krátké době nepodařilo vždy optimum nalézt, neboť předchozí zaznamenaný postup často závisel na nějakém pracovním počátečním řešení. Na druhou stranu kvalitní přípustná řešení nalezená v omezeném čase pro běžné volby parametrů mají možná větší vypovídající hodnotu. Často mohou existovat nelogické volby parametrů vedoucí k nalezení optimálního řešení a vzhledem k zahrnutí náhodného prvku lze alespoň intuitivně usuzovat, že algoritmus by měl v nekonečném čase optimum skutečně nalézt. Ze všech testovaných problémů byly vynechány ty, u nichž nebyla známa optimální hodnota v [55]. Pro srovnání obtížnosti jednotlivých problémů, zvolených parametrů a postupu nalezení co možná nejlepších přípustných řešení lze nahlédnout ke skriptům na přiloženém CD, jimiž byla tato řešení získána. Nejlepší nalezená řešení obsahuje příloha E. V tabulkách 5.7, 5.8, 5.9 jsou porovnány hodnoty nejlepších nalezených přípustných řešení s optimálními. Čtvrtý sloupec tabulek obsahuje rozdíl těchto hodnot, v posledním sloupci je tento rozdíl vyjádřen procentuálně vzhledem k optimu. Optimální řešení byla nalezena u třech čtvrtin problémů typu R, u všech problémů typu C a u poloviny problémů typu RC. V nejhorším případě (R207) je rozdíl účelových funkcí nalezeného a optimálního řešení stále menší než 1 % optimální hodnoty. Ve všech ostatních případech jsou výsledky ještě mnohem lepší a všechna nalezená řešení můžeme považovat za kvalitní. Algoritmus tabu prohledávání využívající dělící problém v rámci konceptu dlouhodobé paměti prokázal velmi slibné výsledky. Celkově horších výsledků, ale není to pravidlem, algoritmus dosahuje u problémů s vyšší kapacitou vozů, tj. menším počtem tras. To může být dáno například pomalejší implementací pro problémy obsahující delší trasy (a tedy nižším počtem provedených iterací) nebo jen nedostatečně bohatou strukturou definovaných operátorů.
52
Instance problému R101 R102 R103 R104 R105 R106 R107 R108 R109 R110 R111 R112 R201 R202 R203 R205 R206 R207 R209 R210
Optimum Nalezená hodnota 1637.7 1466.6 1208.7 971.5 1355.3 1234.6 1064.6 932.1 1146.9 1068.0 1048.7 948.6 1143.2 1029.6 870.8 949.8 875.9 794.0 854.8 900.5
1637.7 1466.6 1208.7 971.5 1355.3 1234.6 1064.6 936.7 1146.9 1068.0 1048.7 948.6 1143.2 1029.6 873.1 953.5 875.9 801.6 854.8 900.8
Rozdíl 0.0 0.0 0.0 0.0 0.0 0.0 0.0 4.6 0.0 0.0 0.0 0.0 0.0 0.0 2.3 3.7 0.0 7.6 0.0 0.3
(%) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.49 0.00 0.00 0.00 0.00 0.00 0.00 0.26 0.39 0.00 0.96 0.00 0.03
% % % % % % % % % % % % % % % % % % % %
Tabulka 5.7: Nejlepší nalezené hodnoty účelové funkce algoritmem tabu prohledávání pro problémy typu R
Instance problému C101 C102 C103 C104 C105 C106 C107 C108 C109 C201 C202 C203 C204 C205 C206 C207 C208
Optimum Nalezená hodnota 827.3 827.3 826.3 822.9 827.3 827.3 827.3 827.3 827.3 589.1 589.1 588.7 588.1 586.4 586.0 585.8 585.8
827.3 827.3 826.3 822.9 827.3 827.3 827.3 827.3 827.3 589.1 589.1 588.7 588.1 586.4 586.0 585.8 585.8
Rozdíl 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
(%) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
% % % % % % % % % % % % % % % % %
Tabulka 5.8: Nejlepší nalezené hodnoty účelové funkce algoritmem tabu prohledávání pro problémy typu C
53
Instance problému RC101 RC102 RC103 RC104 RC105 RC106 RC107 RC108 RC201 RC202 RC203 RC205 RC206 RC207
Optimum Nalezená hodnota 1619.8 1457.4 1258.0 1132.3 1513.7 1372.7 1207.8 1114.2 1261.8 1092.3 923.7 1154.0 1051.1 962.9
1619.8 1457.4 1261.4 1132.6 1513.7 1373.5 1207.8 1115.2 1261.8 1092.3 926.2 1154.0 1052.0 964.7
Rozdíl 0.0 0.0 3.4 0.3 0.0 0.8 0.0 1.0 0.0 0.0 2.5 0.0 0.9 1.8
(%) 0.00 0.00 0.27 0.03 0.00 0.06 0.00 0.09 0.00 0.00 0.27 0.00 0.09 0.19
% % % % % % % % % % % % % %
Tabulka 5.9: Nejlepší nalezené hodnoty účelové funkce algoritmem tabu prohledávání pro problémy typu RC
54
Závěr V práci byly popsány základní modely, kterými lze formulovat optimalizační úlohy týkající se rozvozu pomocí dopravních prostředků. Hlavní důraz byl kladen na rozvozní problém s časovými okny a uvedení souvislostí s problémem obchodního cestujícího a jinými rozvozními problémy. Dále byl popsán klasický postup řešení optimalizačních úloh s celočíselnými proměnnými, způsob přeformulování rozvozního problému na pokrývací problém a princip metody generování sloupců. Kromě těchto exaktních metod řešení byly vyloženy i různé heuristické metody řešení rozvozních problémů. Pro samotnou optimalizaci problému byl navržen a implementován vlastní algoritmus tabu prohledávání, diverzifikovaný pomocí náhodných kroků a se zintenzivněním pomocí náhodného zafixování tras. Navíc algoritmus využívá komerční software Gurobi při řešení dělícího problému sestaveného ze všech tras z omezeného počtu nejlepších navštívených řešení. V numerické studii bylo poukázáno na velmi omezené možnosti standardních metod při řešení rozvozních problémů, což motivuje ke zkoumání schopností heuristik, které pro velké úlohy mohou být také jediným východiskem. Srovnání schopností navrhovaného algoritmu bylo provedeno na již vyřešených instancích rozvozního problému s časovými okny o velikosti 100 zákazníků. Algoritmus dokázal nalézt optimální řešení 39 problémů z celkem 51 zkoumaných problémů (nejhorší případ do 1 % od optima), což vzhledem k jejich obecné obtížnosti svědčí o poměrně účinném nástroji pro řešení rozvozního problému s časovými okny. Největší nevýhodou popsaného algoritmu tabu prohledávání je podobně jako u každé heuristiky nemožnost prokázání optimality a kvalitu výsledku lze obhajovat pouze intuitivně. Do budoucna lze samozřejmě algoritmus dále vylepšovat. Největším možnosti ke zlepšení nabízí určitě doba běhu algoritmu. Při procesu generování nových kroků by mělo být například možné testovat přípustnost trasy v konstantním čase nezávisle na délce trasy. U krátkých tras se taková implementace příliš neprojeví, nicméně již u testovaných problémů, kde trasy obsahovaly v průměru více než 25 zákazníků, bylo pozorováno citelné zpomalení. Paralelní implementace by byla další možností urychlení výpočtu. Případně je možno uvažovat i jiná zobecnění problému, snadno lze algoritmus zobecnit například pro různé kapacity vozidel (s výjimkou zintenzivnění pomocí dělícího problému, jehož formulace přestane platit). Další vhodnou možností, jak upravit algoritmus, by mohla být automatizace výpočtu a vytvoření různých heuristik pro automatickou volbu vhodných parametrů.
55
Reference [1] Altinkemer K., Gavish B. Parallel savings based heuristics for the delivery problem Operations Research. 1991, 39(3), 456–469. [2] Applegate D., Bixby R., Chvátal V., Cook W. Concorde TSP Solver. 2006. URL
. [3] Beazley D. M. Automated scientific software scripting with SWIG. Future Gener. Comput. Syst. 2003, 19(5), 599–609. [4] Bräysy O., Gendreau M. Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation Science. 2005, 39(1), 104–118. [5] Clarke G., Wright J. W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research. 1964, 12(4), 568–581. [6] Conforti M., Cornuéjols G., Zambelli G. Polyhedral Approaches to Mixed Integer Linear Programming. In: Jünger M., Liebling T. M., Naddef D., Nemhauser G. L., Pulleyblank W. R., Reinelt G., Rinaldi G., Wolsey L. A. (eds). 50 Years of Integer Programming 1958-2008. Springer Berlin Heidelberg, 2010, 343–385. [7] Cordeau J. F., Laporte G., Savelsbergh M. W. P., Vigo D. Vehicle Routing. In: Barnhart C., Laporte G. (eds). Handbooks in Operations Research and Management Science: Transportation. Elsevier Science Publishers, 2007, 367–428. [8] Cornuéjols G. Valid inequalities for mixed integer linear programs. Mathematical Programming. 2007, 112(1), 3–44. [9] Croes G. A. A Method for Solving Traveling-Salesman Problems. Operations Research. 1958, 6(6), 791–812. [10] Czyzyk J., Mesnier M., Moré J. The NEOS Server. IEEE Journal on Computational Science and Engineering. 1998, 5(3), 68–75. [11] Dantzig G. B., Fulkerson R., Johnson S. Solution of a large-scale travelingsalesman problem. Operations Research. 1954, 2, 393–410. [12] Dantzig G. B., Ramser J. H. The Truck Dispatching Problem. Management Science. 1959, 6(1), 80–91. [13] Dantzig G. B., Wolfe P. Decomposition Principle for Linear Programs. Operations Research. 8(1), 101–111. [14] Desrochers M., Desrosiers J., Solomon M. A New Optimization Algorithm For The Vehicle Routing Problem With Time Windows. Operations Research. 1992, 40(2), 342–354.
56
[15] Desrochers M., Laporte G. Improvements and extensions to the MillerTucker-Zemlin subtour elimination constraints. Operations Research Letters. 1991, 10(1), 27–36. [16] Desrosiers J., Dumas Y., Solomon M. M., Soumis F. Time Constrained Routing and Scheduling. In: Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. (eds). Handbooks in Operations Research and Management Science: Network Routing. Elsevier Science Publishers, 1995, 35–139. [17] Dror M. Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research. 1994, 42(5), 977–978. [18] Garey M. R., Johnson D. S. "Strong" NP-Completeness Results: Motivation, Examples, and Implications. Journal of the ACM. 1978, 25(3), 499–508. [19] Gendreau M., Hertz A., Laporte G. A New Insertion and Postoptimization Procedure for the Traveling Salesman Problem. Operations Research. 1992, 40(6), 1086–1094. [20] Glover F. Tabu Search-Part I. INFORMS Journal on Computing. 1989, 1(3), 190–206. [21] Golden B. L., Assad A. A., Wasil E. A. Routing vehicles in the real world: Applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Toth P. and Vigo D. (eds) The vehicle routing problem. Philadelphia: Society for Industrial and Applied Mathematics, 2001, 245–286. [22] Gomory R. E. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society. 1958, 64, 275–278. [23] Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual. 2012. URL . [24] Held M., Karp R. M. A dynamic programming approach to sequencing problems. Journal of the Society of Industrial and Applied Mathematics. 1962, 10(1), 196–210. [25] Holmes R. A., Parker R. G. A Vehicle Scheduling Procedure Based Upon Savings and a Solution Perturbation Scheme. Operational Research Quarterly. 1976, 27(1), 83–92. [26] Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Pittsburgh, 1976. Technical Report 388. Graduate School of Industrial Administration, Carnegie-Mellon University. [27] Christofides N., Eilon S. Algorithms for large-scale travelling salesman problems. Operational Research Quarterly. 1972, 23(4), 511–518. [28] Johnson D. S., Gutin G., McGeoch L. A., Yeo A., Zhang W., Zverovitch A. Experimental Analysis of Heuristics for the ATSP. In: Gutin G., Punnen A. P. (eds). The Traveling Salesman Problem and Its Variations. Dordrecht: Kluwer Academic Publishers, 2002, 369–444. 57
[29] Johnson D. S., McGeoch L. A. Experimental Analysis of Heuristics for the STSP. In: Gutin G., Punnen A. P. (eds). The Traveling Salesman Problem and Its Variations. Dordrecht: Kluwer Academic Publishers, 2002, 445–488. [30] Johnson D. S., Papadimitriou C. H. Computational Complexity. In: Lawler E. L., Lenstra J. K., Kan A.H.G.R., Shmoys D.B. (eds). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: Wiley, 1985, 37–85. [31] Jonker R., Volgenant T. Transforming asymmetric into symmetric traveling salesman problems. Operations Research Letters. 1983, 2(4), 161–163. [32] Kallehauge B., Larsen J., Madsen O. B. G., Solomon M. M. Vehicle Routing Problem with Time Windows. In: Desaulniers G., Desrosiers J., Solomon M. M. (eds). Column Generation. Springer US, 2005, 67–98. [33] Kara I., Laporte G., Bektas T. A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem. European Journal of Operational Research. 2004, 158(3), 793–795. [34] Karmakar N. A new polynomial-time algorithm for linear programming. Combinatorica. 1984, 4(4), 373–395. [35] Karp R. M. Reducibility among combinatorial problems. In: Miller R. E., Thatcher J. W. (eds). Complexity of Computer Computations. New York: Plenum Press, 1972, 85–103. [36] Kohl N., Madsen O. B. G. An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation. Operations Research. 1997, 45(3), 395–406. [37] Kuhn H. W. The hungarian method for the assignment problem. Naval Research Logistics. 1955, 2(1-2), 83–97. [38] Laporte G., Semet F. Classical heuristics for the capacitated VRP. In: Toth P. and Vigo D. (eds) The vehicle routing problem. Philadelphia: Society for Industrial and Applied Mathematics, 2001, 109–128. [39] Land A. H., Doig A. G. An Automatic Method for Solving Discrete Programming Problems. Econometrica. 1960, 28(3), 497–520. [40] Lodi A. Mixed Integer Programming Computation. In: Jünger M., Liebling T. M., Naddef D., Nemhauser G. L., Pulleyblank W. R., Reinelt G., Rinaldi G., Wolsey L. A. (eds). 50 Years of Integer Programming 1958-2008. Springer Berlin Heidelberg, 2010, 619–645. [41] Mole R. H., Jameson S. R. A Sequential Route-Building Algorithm Employing a Generalised Savings Criterion. Operational Research Quarterly. 1976, 27(2), 503–501. [42] Miller C. E., Tucker A. W., Zemlin R. A. Integer Programming Formulation of Traveling Salesman Problems. J. ACM. 1960, 7(4), 326–329. 58
[43] Naddef D. Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP. In: Gutin G., Punnen A. P. (eds). The Traveling Salesman Problem and Its Variations. Dordrecht: Kluwer Academic Publishers, 2002, 29–116. [44] Osman I. H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research. 1993, 41(14), 421–451. [45] Or I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Evanston, 1976. Ph.D. dissertation. Department of Industrial Engineering and Management Sciences, Northwestern University. [46] Papadimitriou C. H. The Euclidean travelling salesman problem is NPcomplete. Theoretical Computer Science. 1977, 4(3), 237–244. [47] Papadimitriou C. H, Vazirani U. V. On two geometric problems related to the travelling salesman problem. Journal of Algorithms. 1984, 5(2), 231–246. [48] Picard J.-C., Queyranne M. The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling. Operations Research. 1978, 26(1), 86–110. [49] Potvin J.-Y., Rousseau J.-M. An Exchange Heuristic for Routeing Problems with Time Windows. The Journal of the Operational Research Society. 1995, 46(12), 1433–1446. [50] Punnen A. P. The Traveling Salesman Problem: Applications, Formulations and Variations. In: Gutin G., Punnen A. P. (eds). The Traveling Salesman Problem and Its Variations. Dordrecht: Kluwer Academic Publishers, 2002, 1–28. [51] Savelsbergh M. P. Local Search in Routing Problems with Time Windows. Annals of Operations Research. 1985, 4(1-4), 285–305. [52] Savelsbergh M. W. P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA Journal on Computing. 1994, 6, 445– 454. [53] Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research. 1987, 15(2), 254–265. [54] Solomon M. M. VRPTW BENCHMARK PROBLEMS [online]. [cit. 13. 3. 2013]. URL . [55] Spoorendonk S. Optimal Solution for the Solomon Instances [online]. [cit. 13. 3. 2013]. URL . [56] Svestka J. A., Huckfeldt V. E. Computational Experience with an MSalesman Traveling Salesman Algorithm. Management Science. 1973, 19(7), 790–799. 59
[57] Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.-Y. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft time Windows. Transportation Science. 1997, 31(2), 170–186. [58] Toth P., Vigo D. An Overview of Vehicle Routing Problems. In: Toth P. and Vigo D. (eds) The vehicle routing problem. Philadelphia: Society for Industrial and Applied Mathematics, 2001, 1–26. [59] Wark P., Holt J. A Repeated Matching Heuristic for the Vehicle Routeing Problem. The Journal of the Operational Research Society. 1994, 45(10), 1156–1167.
60
Seznam použitých zkratek ATSP - Asymmetric Traveling Salesman Problem (nesymetrický problém obchodního cestujícího) BPP - Bin Packing Problem (problém nakládání odpadu do košů) CVRP - Capacitated Vehicle Routing Problem (kapacitně omezený rozvozní problém) ESPPTWCC - Elementary Shortest Path Problem with Time Windows and Capacity Constraints LP - Linear Programming (lineární programování) m−TSP - Multiple Traveling Salesman Problem (problém s více obchodními cestujícími) MIP - Mixed Integer Programing (smíšené celočíselné programování) SCP - Set Covering Problem (pokrývací problém) SPP - Set Partitioning Problem (dělící problém) STSP - Symmetric Traveling Salesman Problem (symetrický problém obchodního cestujícího) TS - Tabu Search (tabu prohledávání) TSP - Traveling Salesman Problem (problém obchodního cestujícího) TSPTW - Traveling Salesman Problem with Time Windows (problém obchodního cestujícího s časovými okny) VRP - Vehicle Routing Problem (rozvozní problém) VRPTW - Vehicle Routing Problem with Time Windows (rozvozní problém s časovými okny)
61
Přílohy
62
A. Základní pojmy z teorie grafů Definice A.1. Neorientovaný graf G je uspořádaná dvojice (V, E), kde V je nějaká neprázdná množina a E je množina dvoubodových podmnožin množiny V . Prvky množiny V nazýváme vrcholy grafu G a prvky množiny E nazýváme hrany grafu G. Definice A.2. Orientovaný graf G je uspořádaná dvojice (V, E), kde V je nějaká neprázdná množina a E ⊂ V × V. Prvky množiny V nazýváme vrcholy grafu G a prvky množiny E nazýváme orientované hrany grafu G. Definice A.3. Neorientovaný graf G = (V, E) nazveme úplný, jestliže E tvoří množinu všech dvouprvkových podmnožin množiny E. Orientovaný graf G = (V, E) nazveme úplný, jestliže E = V × V. Pokud není zdůrazněna orientovanost grafu nebo není orientovanost z kontextu zřejmá, je předpokládán vždy neorientovaný graf. V dalším již budeme uvažovat pouze neorientované grafy. Definice A.4. Nechť G = (V, E) je graf. Posloupnost (v0 , e1 , v1 , e2 , . . . , en , vn ) nazveme cestou v grafu z v0 do vn , jestliže vrcholy v posloupnosti se neopakují a platí ei = {vi−1 , vi } ∈ E, i = 1, 2, . . . , n. Definice A.5. Řekneme, že graf G je souvislý, jestliže pro libovolné dva jeho vrcholy v1 , v2 existuje v grafu cesta z v1 do v2 . Definice A.6. Nechť G = (V, E) je graf a v ∈ V . Stupněm vrcholu v rozumíme počet hran grafu G obsahujících vrchol v. Definice A.7. Podgraf grafu (V, E) je každý graf (V 0 , E 0 ), pro který platí ∅= 6 V 0 ⊂ V a E 0 ⊂ E. Definice A.8. Graf C = (V, E), kde V = {v1 , v2 , . . . , vn }, E = {e1 , e2 , . . . , en } nazveme kružnicí (cyklem), pokud platí ei = {vi , vi+1 }, i = 1, 2, . . . , n − 1 a en = {vn , v1 }. Definice A.9. Hamiltonovská kružnice grafu je taková kružnice, která projde právě jednou všemi jeho vrcholy. Eulerovský cyklus grafu je cyklus, který projde všemi hranami grafu právě jednou. Definice A.10. Kostrou souvislého grafu G = (V, E) je podgraf v G, který je souvislý, neobsahuje kružnice a obsahuje všechny vrcholy. Je-li navíc definována funkce ohodnocení hran w : E → R, minimální kostrou grafu G nazveme kostru P (V, E 0 ), pro kterou nabývá e∈E 0 w(e) minimální hodnoty. Definice A.11. Nechť G = (V, E) je graf. Množinu M ⊂ E nazveme párováním grafu G, pokud žádné dvě hrany v M nemají společný vrchol. Řekneme, že párování grafu G je perfektní, pokud pokrývá všechny vrcholy grafu G. Věta A.12. Pro každý graf G = (V, E) je počet vrcholů lichého stupně sudé číslo. 63
Důkaz. Označme deg(v) stupeň vrcholu v ∈ V . Platí X
deg(v) = 2|E|,
v∈V
neboť každá hrana obsahuje dva vrcholy a sečteme-li všechny stupně, dostaneme dvojnásobek počtu hran. Tvrzení věty je pak jednoduchým důsledkem uvedené rovnosti.
64
B. Diagram rozmístění zákazníků problémů typu R 64
65
66
63
32
49
71 90 11
36
20
19
10
35
30
9
62
51
47
70 34 81 48
88
31
33
78
7 1 46
79 82
69
50 3
8
52
77 76
18
29
27 68
45 83
28 89
80
0
12
24
60 84 17
53 5
6
26 54
96
94
99
58 13
61
93
59
40
95 55
85
92 98 37
16
97 21
4
25
91 86
100
87 2
73 72
44 74 42
57
56
39
75 14
22 41
38
15
23
43
65
67
C. Diagram rozmístění zákazníků problémů typu C (otočeno o 90◦) 71
70 73
76 78
77 79
81
80
82 83 84 85
92 93
94
89
95 97
86 87
88
96
91
90
98 100
99
2 1
74
72
63
62
61
65 67
66
75
64
69
68
4 35 6
7
0
9 8 11
12 14 16
13 15
10
41 40 43
42
21 20
47
46 45
23
22
49
26
25 24
52
28
27
30
29
17 19
53 55
18
32 34 36
35 37
39
66
31
33
38
44 48
50
51
54
57
56
59
58 60
D. Diagram rozmístění zákazníků problémů typu RC (otočeno o 90◦) 27
26 28
29 31
30 32
34
33
50
35 36
89 37
71 72
38 40
63 85
93
39
76
41 43
62
67
94
44 42
54
84
95
96
51
92 81
56
91 80
61
64
68
66
0 90
83
70
98
99
45 4
7
52 86
53 6
23
77
2
8
21
24
57 82
88
46
48
22
25
69
55
1
5
49 19
65 100
3
18 20
74
60
58 87 10 78
79
12
13
47
15
17
16
67
59
11
14 73
9
97
75
E. Nejlepší nalezená řešení algoritmem tabu prohledávání Instance problému
R101
Nalezená hodnota
1637.7
Trasy
2, 21, 73, 41, 56, 4
Optimum
1637.7
5, 83, 61, 85, 37, 93 12, 76, 79, 3, 54, 24, 80 14, 44, 38, 43, 13 27, 69, 30, 51, 20, 32, 70 28, 29, 78, 34, 35, 77 31, 88, 7 33, 81, 50, 68 36, 47, 19, 8, 46, 17 39, 23, 67, 55, 25 40, 53, 26 45, 82, 18, 84, 60, 89 52, 6 59, 99, 94, 96 62, 11, 90, 10 63, 64, 49, 48 65, 71, 9, 66, 1 72, 75, 22, 74, 58 92, 42, 15, 87, 57, 97 95, 98, 16, 86, 91, 100
Instance problému
R102
Nalezená hodnota
1466.6
Trasy
18
Optimum
1466.6
27, 69, 88, 10, 31 28, 76, 79, 54, 24, 80, 12 30, 51, 9, 66, 1 36, 47, 19, 8, 46, 17, 93, 59 39, 23, 67, 55, 25, 26 40, 53 42, 15, 41, 75, 56, 4 50, 33, 29, 78, 34, 35, 77 62, 11, 90, 20, 32, 70 63, 64, 49, 48, 82, 7, 52 65, 71, 81, 3, 68 73, 22, 74, 72, 21 83, 45, 61, 84, 5, 60, 89 87, 57, 2, 58 92, 98, 85, 16, 86, 91, 97, 13 94, 96, 99, 6 95, 14, 44, 38, 43, 100, 37
68
Instance problému
R103
Nalezená hodnota
1208.7
Trasy
1, 30, 78, 34, 35, 81, 77, 28
Optimum
1208.7
2, 22, 74, 72, 73, 58 21, 39, 23, 67, 55, 25, 54 27, 69, 88, 8, 46, 17, 5, 60, 89 36, 64, 49, 19, 47, 48, 82, 18 40, 53 42, 43, 15, 57, 41, 75, 56, 4, 26 50, 33, 3, 76, 79, 29, 24, 68, 80, 12 51, 65, 71, 9, 66, 20, 32, 70 52, 7, 62, 11, 63, 90, 10, 31 83, 45, 84, 61, 85, 93, 59 92, 98, 14, 44, 38, 86, 16, 91, 100, 37 94, 95, 97, 87, 13 96, 99, 6
Instance problému
R104
Nalezená hodnota
971.5
Trasy
6, 96, 59, 93, 99, 84, 17, 45, 83, 5, 60, 89
Optimum
971.5
18, 82, 48, 46, 8, 47, 36, 49, 19, 7 27, 70, 30, 20, 66, 65, 71, 35, 34, 78, 50 28, 76, 79, 29, 24, 68, 80, 12, 26 42, 43, 15, 57, 2, 41, 22, 74, 73, 21, 40, 58 52, 88, 62, 11, 64, 63, 90, 32, 10, 31 53 69, 1, 51, 9, 81, 33, 3, 77 72, 75, 56, 23, 67, 39, 55, 4, 25, 54 92, 98, 14, 44, 38, 86, 16, 61, 85, 91, 100, 37 94, 95, 97, 87, 13
Instance problému
R105
Nalezená hodnota
1355.3
Trasy
2, 15, 57, 87, 97, 13
Optimum
1355.3
5, 45, 83, 99, 94, 6 21, 73, 75, 22, 41, 56, 74, 58 27, 69, 76, 50, 1 28, 12, 29, 79, 78, 34, 35, 77 31, 30, 51, 9, 81, 3, 68, 24, 80 33, 65, 71, 66, 20, 32, 70 42, 14, 44, 38, 86, 43, 100, 91, 93 47, 36, 19, 49, 46, 48 52, 82, 8, 84, 17, 60, 89 53, 40, 26 59, 95, 92, 98, 16, 61, 85, 37, 96 62, 88, 7, 18 63, 64, 11, 90, 10 72, 39, 23, 67, 55, 54, 4, 25
69
Instance problému
R106
Nalezená hodnota
1234.6
Trasy
12, 29, 78, 79, 68, 54, 24, 80
Optimum
1234.6
21, 72, 39, 23, 67, 55, 4, 25, 26 27, 62, 88, 18, 89 28, 76, 40, 53 48, 47, 36, 19, 49, 46, 82, 7, 52 50, 33, 65, 71, 66, 20, 32, 70, 1 59, 37, 14, 44, 38, 86, 43, 100, 98, 93 63, 64, 11, 90, 10, 31 69, 30, 51, 81, 9, 35, 34, 3, 77 73, 41, 22, 75, 56, 74, 2, 58 83, 45, 8, 84, 17, 5, 60 94, 92, 42, 15, 57, 87, 97, 95, 13 96, 85, 91, 16, 61, 99, 6
Instance problému
R107
Nalezená hodnota
1064.6
Trasy
2, 57, 15, 41, 22, 75, 56, 4, 74, 73, 58
Optimum
1064.6
21, 72, 39, 23, 67, 55, 25, 54, 26 27, 69, 30, 88, 31, 10, 70, 1 28, 76, 79, 78, 29, 24, 68, 80, 12 33, 81, 65, 71, 9, 35, 34, 3, 77 40, 53 42, 43, 14, 44, 38, 86, 16, 91, 100, 37, 98 48, 47, 36, 64, 49, 19, 82, 18, 89 52, 7, 62, 11, 63, 90, 32, 66, 20, 51, 50 60, 83, 45, 46, 8, 84, 5, 17, 61, 85, 93 94, 96, 92, 59, 99, 6, 87, 97, 95, 13
Instance problému
R108
Nalezená hodnota
936.7
Trasy
2, 57, 43, 15, 41, 22, 75, 74, 4, 21, 26
Optimum
932.1
6, 96, 5, 17, 84, 8, 46, 45, 83, 60, 89 27, 69, 1, 76, 3, 79, 29, 24, 80, 68, 77, 28 31, 88, 62, 10, 63, 90, 32, 66, 20, 30, 70 40, 73, 72, 56, 23, 67, 39, 55, 25, 54, 12 50, 33, 81, 51, 9, 71, 65, 35, 34, 78 52, 7, 19, 11, 64, 49, 36, 47, 48, 82, 18 53 95, 92, 98, 85, 93, 99, 59, 87, 13, 58 97, 42, 14, 44, 38, 86, 16, 61, 91, 100, 37, 94
Instance problému
R109
Nalezená hodnota
1146.9
Trasy
2, 42, 15, 57, 87, 94, 6, 96
Optimum
1146.9
5, 83, 8, 45, 84, 17, 60, 89 12, 29, 78, 79, 3, 50, 26 27, 69, 30, 51, 71, 65, 66, 20, 70, 1 28, 76, 33, 81, 9, 35, 34, 68, 77 31, 19, 47, 49, 36, 46, 48 40, 21, 73, 22, 41, 74, 56, 4 52, 88, 7, 82, 18 53 59, 99, 85, 61, 16, 86, 91, 37, 100, 93 62, 11, 64, 63, 90, 32, 10 72, 75, 23, 67, 39, 25, 55, 54, 24, 80 95, 92, 98, 44, 38, 14, 43, 97, 13, 58
70
Instance problému
R110
Nalezená hodnota
1068.0
Trasy
2, 57, 87, 94, 96, 6
Optimum
1068.0
21, 72, 75, 56, 23, 67, 39, 25, 55, 4 27, 31, 88, 7, 62, 63, 90, 32, 10 28, 12, 76, 29, 34, 78, 24, 54, 80, 68 33, 9, 35, 71, 65, 66, 20, 1 40, 73, 74, 22, 41, 15, 43, 42, 58 52, 18, 83, 8, 46, 45, 17, 60, 89 53, 26 59, 99, 5, 84, 61, 16, 85, 37, 97, 13 69, 70, 30, 51, 81, 79, 3, 77, 50 82, 47, 19, 11, 64, 49, 36, 48 95, 92, 98, 100, 14, 38, 86, 44, 91, 93
Instance problému
R111
Nalezená hodnota
1048.7
Trasy
2, 57, 15, 43, 41, 22, 74, 56, 72, 21, 58
Optimum
1048.7
6, 99, 84, 61, 85, 93, 96 7, 19, 64, 49, 36, 47, 48, 82, 52 18, 83, 45, 8, 46, 17, 5, 60, 89 27, 69, 30, 20, 65, 66, 32, 70, 1 28, 76, 79, 78, 29, 24, 68, 80, 12, 26 40, 87, 97, 95, 94, 13 50, 33, 81, 51, 9, 71, 35, 34, 3, 77 53 73, 75, 23, 67, 39, 55, 4, 25, 54 88, 62, 11, 63, 90, 10, 31 92, 42, 14, 44, 38, 86, 16, 91, 100, 37, 98, 59
Instance problému
R112
Nalezená hodnota
948.6
Trasy
2, 41, 22, 75, 56, 23, 67, 39, 25, 55, 54
Optimum
948.6
6, 94, 95, 87, 42, 43, 15, 57, 58 12, 80, 68, 24, 29, 3, 77, 50 18, 83, 60, 99, 93, 85, 98, 92, 59, 96 27, 69, 33, 81, 9, 51, 30, 32, 90, 10, 70 28, 76, 79, 78, 34, 35, 71, 65, 66, 20, 1 31, 62, 19, 11, 63, 64, 49, 36, 47, 48 52, 88, 7, 82, 8, 46, 45, 17, 84, 5, 89 53, 40, 21, 73, 74, 72, 4, 26 61, 16, 86, 38, 14, 44, 91, 100, 37, 97, 13
Instance problému
R201
Nalezená hodnota
1143.2
Trasy
5, 83, 45, 82, 47, 36, 49, 46, 48
Optimum
1143.2
27, 31, 63, 64, 11, 19, 62, 88, 7, 18, 8, 84, 17, 91, 100, 93, 60, 89 28, 12, 29, 76, 50, 3, 54, 26 33, 65, 71, 9, 51, 81, 79, 78, 34, 35, 68, 77 42, 15, 2, 73, 21, 40, 87, 57, 43, 37, 97, 96, 13, 58 52, 69, 30, 90, 10, 20, 66, 32, 70, 1 72, 39, 67, 23, 75, 22, 41, 56, 74, 4, 55, 25, 24, 80 95, 59, 92, 98, 14, 38, 44, 16, 61, 86, 85, 99, 94, 6, 53
71
Instance problému
R202
Nalezená hodnota
1029.6
Trasy
27, 69, 1, 30, 31, 88, 7, 18, 8, 84, 86, 91, 100, 37, 98, 93, 59, 94
Optimum
1029.6
28, 26, 21, 72, 75, 39, 67, 23, 56, 4, 54, 55, 25, 24, 80, 12 40, 73, 41, 22, 74, 2, 58 50, 33, 65, 71, 29, 76, 3, 79, 78, 81, 9, 51, 20, 66, 35, 34, 68, 77 52, 62, 63, 90, 10, 32, 70 53 83, 45, 82, 48, 47, 36, 19, 11, 64, 49, 46, 17, 5, 60, 89 95, 92, 42, 15, 14, 38, 44, 16, 61, 85, 99, 96, 96, 6, 87, 57, 43, 97, 13
Instance problému
R203
Nalezená hodnota
873.1
Trasy
26, 21, 73, 72, 39, 67, 23, 41, 22, 75, 56, 74, 4, 55, 25, 54, 24, 80, 12
Optimum
870.8
27, 69, 1, 76, 3, 79, 78, 81, 9, 66, 71, 35, 34, 29, 68, 77, 28 50, 33, 51, 65, 20, 30, 32, 90, 63, 64, 49, 10, 70, 31, 52
53, 40, 58 89, 18, 83, 45, 46, 36, 47, 19, 11, 62, 88, 7, 48, 82, 8, 60, 5, 84, 17, 61, 91, 100, 37, 98, 93, 59, 94 95, 92, 97, 42, 15, 43, 14, 44, 38, 86, 16, 85, 99, 96, 6, 87, 57, 2, 13
Instance problému
R205
Nalezená hodnota
953.5
Trasy
2, 15, 42, 14, 44, 38, 86, 16, 61, 85, 99, 6, 94, 97, 87, 57, 43, 91, 100, 37, 93,
Optimum
949.8
96, 13, 58 21, 73, 72, 39, 67, 23, 75, 41, 22, 74, 56, 4, 25, 55, 54, 24, 80, 68, 77 27, 52, 69, 31, 88, 62, 11, 63, 90, 64, 49, 19, 7, 48 28, 12, 29, 76, 33, 65, 71, 9, 81, 51, 30, 50, 3, 79, 78, 34, 35, 66, 20, 32, 10, 70, 1 53, 40, 26 95, 92, 98, 59, 5, 83, 45, 82, 47, 36, 46, 8, 18, 84, 17, 60, 89
Instance problému
R206
Nalezená hodnota
875.9
Trasy
21, 73, 72, 39, 67, 23, 41, 22, 74, 75, 56, 4, 25, 55, 54, 24, 80, 68, 77
Optimum
875.9
27, 69, 31, 88, 62, 63, 90, 30, 51, 9, 81, 78, 79, 76, 12, 26, 40, 53 28, 50, 33, 3, 29, 34, 71, 65, 35, 66, 20, 32, 10, 70, 1 52, 7, 82, 45, 48, 47, 36, 19, 11, 64, 49, 46, 8, 18, 83, 84, 17, 5, 60, 89 94, 92, 98, 37, 42, 15, 14, 44, 38, 86, 16, 61, 99, 96, 6, 95, 97, 87, 2, 57, 43, 100, 91, 85, 93, 59, 13, 58
Instance problému
R207
Nalezená hodnota
801.6
Trasy
26, 21, 73, 72, 23, 67, 39, 56, 75, 41, 22, 74, 4, 25, 55, 54, 80, 68, 24, 29, 3,
Optimum
794.0
77, 12, 28 27, 69, 1, 50, 76, 33, 71, 65, 20, 30, 51, 9, 81, 79, 78, 34, 35, 66, 32, 90, 10, 70, 31, 52 89, 18, 45, 46, 36, 47, 48, 7, 88, 62, 11, 63, 64, 49, 19, 82, 8, 83, 60, 5, 84, 17, 61, 91, 100, 37, 98, 93, 59, 13, 58 94, 92, 42, 15, 43, 14, 44, 38, 86, 16, 85, 99, 96, 6, 95, 97, 87, 57, 2, 40, 53
72
Instance problému
R209
Nalezená hodnota
854.8
Trasy
27, 69, 31, 88, 62, 47, 19, 11, 64, 63, 90, 30, 51, 71, 9, 81, 33, 79, 3, 77, 68,
Optimum
854.8
80, 24, 54, 26 28, 12, 76, 29, 78, 34, 35, 65, 66, 20, 32, 10, 70, 1, 50 40, 2, 73, 21, 72, 75, 23, 67, 39, 25, 55, 4, 56, 74, 22, 41, 58, 53 52, 7, 82, 83, 18, 6, 94, 13, 87, 57, 15, 43, 42, 97, 92, 37, 100, 91, 93, 96 95, 99, 59, 98, 85, 5, 84, 61, 16, 44, 14, 38, 86, 17, 45, 8, 46, 36, 49, 48, 60, 89
Instance problému
R210
Nalezená hodnota
900.8
Trasy
18, 83, 45, 86, 38, 44, 16, 61, 99, 96, 6, 94, 87, 2, 40, 53
Optimum
900.5
21, 73, 72, 23, 67, 39, 56, 75, 22, 41, 74, 4, 55, 25, 54, 26 27, 69, 1, 30, 51, 33, 71, 65, 66, 20, 32, 90, 10, 70, 31 28, 12, 76, 3, 79, 29, 78, 81, 9, 35, 34, 24, 80, 68, 77, 50 52, 7, 82, 48, 47, 36, 19, 88, 62, 11, 63, 64, 49, 46, 8, 84, 17, 85, 98, 37, 97, 13, 58 95, 59, 92, 42, 57, 15, 43, 14, 100, 91, 93, 5, 60, 89
Instance problému
C101, C102, C105, C106, C107, C108 ,C109
Nalezená hodnota
827.3
Trasy
5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75
Optimum
827.3
13, 17, 18, 19, 15, 16, 14, 12 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21 32, 33, 31, 35, 37, 38, 39, 36, 34 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47 57, 55, 54, 53, 56, 58, 60, 59 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69 81, 78, 76, 71, 70, 73, 77, 79, 80 90, 87, 86, 83, 82, 84, 85, 88, 89, 91 98, 96, 95, 94, 92, 93, 97, 100, 99
Instance problému
C103
Nalezená hodnota
826.3
Trasy
5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75
Optimum
826.3
13, 17, 18, 19, 15, 16, 14, 12 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21 32, 33, 31, 35, 37, 38, 39, 36, 34 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47 55, 54, 53, 56, 58, 60, 59, 57 67, 65, 62, 74, 72, 61, 64, 68, 66, 69 81, 78, 76, 71, 70, 73, 77, 79, 80, 63 90, 87, 86, 83, 82, 84, 85, 88, 89, 91 98, 96, 95, 94, 92, 93, 97, 100, 99
Instance problému
C104
Nalezená hodnota
822.9
Trasy
5, 3, 7, 8, 11, 9, 6, 4, 2, 1, 75
Optimum
822.9
13, 17, 18, 19, 15, 16, 14, 12, 10 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21 32, 33, 31, 35, 37, 38, 39, 36, 34 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47 57, 55, 54, 53, 56, 58, 60, 59 67, 65, 62, 74, 72, 61, 64, 68, 66, 69 81, 78, 76, 71, 70, 73, 77, 79, 80, 63 90, 87, 86, 83, 82, 84, 85, 88, 89, 91 98, 96, 95, 94, 92, 93, 97, 100, 99
73
Instance problému
C201, C202
Nalezená hodnota
589.1
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19,
Optimum
589.1
16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 43, 42, 41, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 84, 86, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
C203
Nalezená hodnota
588.7
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19,
Optimum
588.7
16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 84, 86, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
C204
Nalezená hodnota
588.1
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19,
Optimum
588.1
16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 41, 42, 45, 51, 50, 52, 47, 43, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 84, 86, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
C205
Nalezená hodnota
586.4
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19,
Optimum
586.4
16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 43, 42, 41, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 86, 84, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
C206
Nalezená hodnota
586.0
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19,
Optimum
586.0
16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 86, 84, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
C207
Nalezená hodnota
585.8
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 17, 18,
Optimum
585.8
19, 16, 14, 12, 15, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 86, 84, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
74
Instance problému
C208
Nalezená hodnota
585.8
Trasy
20, 22, 24, 27, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 17,
Optimum
585.8
19, 16, 14, 12, 15, 13, 25, 9, 11, 10, 8, 21 67, 63, 62, 74, 72, 61, 64, 66, 69, 68, 65, 49, 55, 54, 53, 56, 58, 60, 59, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48 93, 5, 75, 2, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 91, 88, 86, 84, 83, 82, 85, 76, 71, 70, 73, 80, 79, 81, 78, 77, 96, 87, 90
Instance problému
RC101
Nalezená hodnota
1619.8
Trasy
5, 45, 2, 7, 6, 8, 3, 1, 70
Optimum
1619.8
14, 47, 12, 73, 79, 46, 4, 100 23, 21, 18, 49, 22, 20, 25, 24 39, 42, 44, 61, 81, 68, 55 59, 75, 87, 97, 58, 77 63, 33, 28, 30, 34, 50, 91, 80 64, 51, 85, 84, 56, 66 65, 52, 99, 57, 86, 74 69, 98, 88, 53, 78, 60 72, 36, 38, 41, 40, 43, 37, 35 82, 11, 15, 16, 9, 10, 13, 17 83, 19, 76, 89, 48 90 92, 31, 29, 27, 26, 32, 93 95, 62, 67, 71, 94, 96, 54
Instance problému
RC102
Nalezená hodnota
1457.4
Trasy
1, 3, 45, 5, 8, 7, 6, 46, 4, 2
Optimum
1457.4
14, 47, 11, 15, 16, 9, 10, 13, 17, 12 19, 23, 21, 18, 48, 25, 77 33, 28, 27, 26, 31, 34, 50, 93, 94, 80 39, 36, 40, 38, 41, 43, 35, 37, 72 42, 44, 61, 81, 54 65, 99, 87, 59, 97, 75, 58 69, 88, 53, 55, 68 85, 63, 76, 51, 22, 49, 20, 24, 83 90 91, 64, 57, 86, 74, 52, 82 92, 95, 62, 29, 30, 32, 89 96, 71, 67, 84, 56, 66 98, 73, 79, 78, 60, 100, 70
Instance problému
RC103
Nalezená hodnota
1261.4
Trasy
2, 45, 46, 8, 7, 6, 4, 5, 3, 1, 100
Optimum
1258.0
20, 18, 48, 21, 23, 22, 49, 19, 25, 24 33, 27, 30, 32, 28, 26, 29, 31, 34 61, 39, 36, 35, 37, 43, 70 65, 83, 64, 51, 76, 89, 63, 85, 95, 91, 80 69, 88, 53, 12, 10, 13, 16, 17, 47 81, 54, 42, 44, 40, 38, 41, 72, 71, 93, 94, 96 82, 14, 15, 11, 9, 87, 59, 74, 86, 57, 52 90, 99, 97, 75, 58, 77 92, 62, 50, 67, 84, 56, 66 98, 60, 73, 79, 78, 55, 68
75
Instance problému
RC104
Nalezená hodnota
1132.6
Trasy
12, 14, 15, 11, 10, 9, 13, 16, 17, 47
Optimum
1132.3
24, 22, 49, 19, 23, 18, 48, 21, 25, 77 42, 44, 43, 38, 37, 35, 36, 40, 39, 41 61, 70, 1, 3, 5, 45, 8, 46, 4, 100, 68 69, 98, 53, 82, 52, 86, 74, 57, 83 80, 91, 56, 95, 62, 67, 94, 93, 71, 72, 54, 96, 81 85, 63, 89, 76, 84, 51, 20, 64, 66 88, 60, 78, 73, 79, 7, 6, 2, 55 90, 65, 99, 87, 59, 97, 75, 58 92, 50, 33, 32, 30, 28, 26, 27, 29, 31, 34
Instance problému
RC105
Nalezená hodnota
1513.7
Trasy
2, 45, 5, 3, 1, 8, 6, 55
Optimum
1513.7
12, 14, 47, 15, 16, 9, 10, 13, 17 31, 29, 27, 30, 28, 26, 32, 34, 50, 91 33, 63, 85, 84, 56, 66 39, 36, 37, 38, 41, 72, 54, 94, 80 42, 44, 40, 35, 43 51, 76, 89, 48, 21, 25, 24 64, 86, 87, 59, 97, 75, 58 65, 99, 52, 57, 74 69, 88, 79, 7, 46, 4, 70, 100 81, 61, 68 82, 11, 73, 78, 60 83, 19, 23, 18, 22, 49, 20, 77 90, 53, 98 92, 95, 62, 67, 71, 93, 96
Instance problému
RC106
Nalezená hodnota
1373.5
Trasy
2, 45, 5, 8, 7, 6, 46, 4, 3, 1, 100
Optimum
1372.7
11, 12, 14, 47, 15, 16, 9, 10, 13, 17 61, 42, 44, 43, 41, 70, 68 62, 33, 28, 26, 27, 34, 50, 91, 80 65, 52, 87, 59, 75, 97, 58, 74 69, 98, 53, 90 72, 38, 39, 40, 36, 35, 37, 54 81, 71, 94, 93, 96 82, 99, 86, 57, 22, 49, 20, 24 83, 64, 19, 23, 21, 18, 48, 25, 77 88, 78, 73, 79, 60, 55 92, 67, 31, 29, 30, 32, 89 95, 63, 85, 76, 51, 84, 56, 66
Instance problému
RC107
Nalezená hodnota
1207.8
Trasy
2, 6, 7, 8, 5, 3, 1, 45, 46, 4, 100
Optimum
1207.8
11, 12, 14, 47, 17, 16, 15, 13, 9, 10 31, 29, 27, 28, 26, 34, 32, 30, 33 41, 38, 42, 44, 43, 40, 37, 35, 36, 39 61, 81, 54, 96 64, 22, 19, 23, 21, 18, 48, 49, 20, 24 65, 83, 25, 77, 75, 97, 58, 74 69, 98, 88, 53, 78, 73, 79, 60, 55, 70, 68 72, 71, 93, 94, 67, 50, 62, 91, 80 82, 99, 52, 87, 59, 86, 57, 66 90 92, 95, 84, 85, 63, 51, 76, 89, 56
76
Instance problému
RC108
Nalezená hodnota
1115.2
Trasy
2, 6, 7, 8, 46, 4, 45, 5, 3, 1, 100
Optimum
1114.2
12, 14, 47, 17, 16, 15, 13, 9, 11, 10 33, 32, 30, 28, 26, 27, 29, 31, 34, 93 41, 42, 44, 43, 40, 38, 37, 35, 36, 39 61, 81, 94, 71, 72, 54, 96 64, 51, 76, 89, 49, 20, 22, 24, 66 65, 83, 57, 19, 18, 48, 21, 23, 25, 77 69, 98, 88, 53, 78, 73, 79, 60, 55, 70, 68 82, 99, 52, 86, 87, 59, 97, 75, 58, 74 90 92, 95, 67, 62, 50, 63, 85, 84, 56, 91, 80
Instance problému
RC201
Nalezená hodnota
1261.8
Trasy
5, 45, 2, 6, 7, 8, 46, 3, 1, 4, 100, 70
Optimum
1261.8
14, 47, 16, 15, 12, 11, 9, 99, 57, 86, 87, 97, 10, 17, 13, 74, 58, 77, 25 65, 59, 75, 23, 21, 18, 19, 49, 22, 20, 56, 66 69, 98, 88, 53, 73, 79, 78, 60, 55 72, 36, 39, 42, 44, 41, 38, 40, 43, 35, 37, 54 81, 61, 68 82, 52, 83, 64, 51, 76, 85, 84, 50, 34, 32, 26, 89, 48, 24, 91, 80 90 92, 95, 63, 33, 28, 27, 29, 31, 30, 62, 67, 71, 94, 96, 93
Instance problému
RC202
Nalezená hodnota
1092.3
Trasy
45, 5, 3, 1, 42, 39, 36, 44, 41, 38, 40, 43, 35, 37, 72, 54
Optimum
1092.3
65, 64, 23, 21, 48, 18, 19, 49, 22, 20, 24, 74, 58, 75, 77, 25, 83 69, 98, 88, 53, 73, 78, 79, 7, 8, 6, 46, 4, 2, 55 81, 61, 68 82, 12, 14, 47, 16, 15, 11, 9, 99, 52, 57, 86, 87, 59, 97, 10, 13, 17, 60, 100, 70 90 91, 92, 95, 85, 63, 33, 34, 31, 29, 27, 26, 28, 30, 32, 89, 50, 93, 94, 80 96, 71, 67, 62, 76, 51, 84, 56, 66
Instance problému
RC207
Nalezená hodnota
926.2
Trasy
1, 3, 5, 45, 60, 12, 11, 15, 16, 47, 78, 73, 79, 7, 6, 8, 46, 4, 2, 55, 100,
Optimum
923.7
70 69, 98, 88, 53, 82, 99, 52, 86, 87, 9, 10, 14, 17, 13, 74, 59, 97, 75, 58, 77, 25, 24, 57 81, 54, 72, 37, 36, 39, 42, 44, 43, 40, 41, 38, 35, 61, 68 90, 65, 83, 64, 85, 63, 89, 76, 23, 21, 48, 18, 19, 49, 22, 20, 51, 84, 56, 66 91, 92, 95, 62, 33, 32, 31, 29, 27, 26, 28, 30, 34, 50, 67, 94, 93, 71, 96, 80
Instance problému
RC205
Nalezená hodnota
1154.0
Trasy
2, 45, 5, 42, 39, 36, 44, 40, 38, 41, 43, 35, 37, 54, 93, 96
Optimum
1154.0
65, 83, 64, 19, 23, 21, 48, 18, 49, 22, 24, 20, 89, 26, 32, 34, 50, 91, 80 69, 98, 88, 53, 9, 10, 13, 17, 60 82, 11, 15, 16, 47, 14, 12, 78, 73, 79, 7, 6, 8, 46, 4, 3, 1, 70, 100 90, 99, 52, 57, 86, 87, 59, 75, 97, 74, 25, 77, 58 92, 95, 33, 28, 27, 29, 31, 30, 85, 63, 76, 51, 84, 56, 66 94, 62, 67, 71, 72, 81, 61, 68, 55
77
Instance problému
RC206
Nalezená hodnota
1052.0
Trasy
61, 5, 45, 2, 88, 53, 78, 73, 79, 7, 6, 8, 46, 4, 3, 1, 100, 70, 68
Optimum
1051.1
65, 83, 64, 95, 62, 63, 33, 30, 31, 29, 27, 28, 26, 32, 34, 50, 56, 91, 80 69, 98, 12, 14, 47, 16, 15, 11, 59, 75, 97, 87, 9, 13, 10, 17, 60, 55 81, 94, 67, 84, 85, 51, 76, 89, 48, 25, 77, 58, 74 82, 99, 52, 86, 57, 23, 21, 18, 19, 49, 20, 22, 24, 66 90 92, 71, 72, 42, 39, 38, 36, 40, 44, 43, 41, 37, 35, 54, 93, 96
Instance problému
RC207
Nalezená hodnota
964.7
Trasy
61, 72, 71, 93, 94, 81, 42, 44, 40, 36, 35, 37, 38, 39, 43, 41, 54, 96
Optimum
962.9
65, 83, 64, 84, 85, 63, 51, 76, 18, 19, 49, 20, 22, 24, 48, 89, 56, 66 69, 98, 53, 12, 14, 47, 17, 16, 15, 11, 9, 87, 59, 97, 13, 10, 60, 55 82, 99, 52, 21, 23, 25, 77, 75, 58, 74, 86, 57, 90 88, 78, 73, 79, 7, 6, 2, 8, 5, 3, 1, 45, 46, 4, 100, 70, 68 95, 67, 62, 33, 30, 31, 29, 27, 28, 26, 32, 34, 50, 92, 91, 80
78
