METAHEURISTICKÉ METÓDY NA RIEŠENIE VYBRANÝCH DOPRAVNÝCH PROBLÉMOV RNDr. Mária Vojteková, PhD., RNDr. Oľga Blažeková, PhD. FPEDAS, Žilinská univerzita v Žiline Univerzitná 1, 010 26 Žilina, SR maria.vojtekova@fpedas.uniza.sk, olga.blazekova@fpedas.uniza.sk Abstrakt: Mnohé optimalizačné dopravné úlohy sú NP zložité a nevieme nájsť riešenie exaktnými metódami v požadovanom čase. Z praktického hľadiska je užitočné nájsť aspoň riešenie, ktoré je blízke optimálnemu. To umožňujú rôzne heuristické a metaheuristické metódy. V našom článku sa venujeme stručnému opisu metaheuristických metód: simulované chladenie, zakázané prehľadávanie, genetické algoritmy a kolónie mravcov, ktoré sú použiteľné pri riešení vybraných dopravných problémov. Kľúčové slová: dopravná úloha, metaheuristická metóda, simulované chladenie, metóda kolónie mravcov. ÚVOD V našom prehľadovom článku sa venujeme stručnému opisu metaheuristických metód, ktoré môžu byť použité pri riešení vybraných dopravných problémov. Pri jednotlivých metódach tiež uvádzame odkazy na literatúru, v ktorej je pomocou daného algoritmu vybraný dopravný problém riešený. 1. ÚLOHA OBCHODNÉHO CESTUJÚCEHO A ÚLOHA OKRUŽNÝCH JÁZD Úloha obchodného cestujúceho sa často vyskytuje pri určovaní trás dopravných prostriedkov, ktorých kapacita je neobmedzená. Túto úlohu možno formulovať nasledovne: obchodný cestujúci musí navštíviť každé mesto v pridelenej oblasti práve raz a vrátiť sa do východiskového mesta tak, aby precestovaná vzdialenosť bola minimálna. Úloha okružných jázd čiastočne pripomína úlohu obchodného cestujúceho. Ak berieme do úvahy kapacitné obmedzenia vozidiel, tak túto úlohu (Capacitated vehicle routing problem CVRP) možno formulovať nasledovne: Je dané centrálne depo (zdroj) a množina zákazníkov, pričom poznáme umiestnenie jednotlivých zákazníkov (vzdialenosti od zdroja k nim ako i vzájomné vzdialenosti medzi zákazníkmi) a veľkosť ich požiadaviek na obsluhu. K obsluhe zákazníkov je k dispozícii množina vozidiel s určenými kapacitami. Každé vozidlo vyjde z depa a musí sa tam vrátiť, každé vozidlo môže byť použité len raz a každý zákazník musí byť uspokojený jedinou jazdou vozidla. Cieľom úlohy je obslúžiť všetkých zákazníkov s minimálnymi nákladmi, pričom veľkosť nákladov je priamo úmerná prejdenej vzdialenosti. Niekedy je potrebné zohľadniť aj počet použitých vozidiel. Takéto úlohy predstavujú NP zložité úlohy, už z ich podstaty vyplýva, že pre veľký počet zákazníkov nie je možné nájsť optimálne riešenie pomocou exaktných metód. Pri riešení praktických problémov sa často používa heuristická Clarke – Wrightova metóda, ako aj dvojfázové prístupy, ktoré dekomponujú úlohu na dve časti: úlohu zhlukovania (clustering), ktorá sa zaoberá zaradením zákazníkov do trasy, a úlohu zostavenia trás (routing). 2. HEURISTIKA A METAHEURISTIKA Heuristika nemá presnú definíciu; dá sa charakterizovať ako kritérium, metóda alebo princíp pre rozhodnutie, ktoré z viacerých alternatívnych aktivít vyzerá ako najefektívnejšie pre dosiahnutie určitého cieľa. Heuristiky sa viažu ku konkrétnemu problému, zatiaľ čo metaheuristiky sú všeobecné postupy (napr. z fyziky, biológie,...), ktoré sú aplikované na daný problém. V poslednej dobe klasické heuristiky ustupujú metaheuristickým metódam, ktoré sa začali masívne používať s nárastom výpočtového výkonu počítačov. Výhodou metaheuristických metód je schopnosť, za určitých okolností, opustiť nájdený lokálny extrém účelovej funkcie a prejsť postupnosťou iteračných krokov do iných častí množiny prípustných riešení, kde je nádej nájsť riešenie s lepšou hodnotou účelovej funkcie, čo klasické heuristiky neumožňujú. Rovnako ako heuristické metódy ani metaheuristiky nezaručujú nájdenie optimálneho riešenia. Medzi tieto metódy patria:  Simulované chladenie (Simulated Annealing)  Zakázané prehľadávanie (Tabu Search)  Genetické algoritmy (Genetic Algorithms)  Kolónie mravcov (Ant systems). 2.1 Simulované chladenie (žíhanie) Inšpiráciou metódy je fyzikálny dej prebiehajúci pri žíhaní tuhého telesa, ktoré sa používa k odstráneniu vnútorných defektov. Na myšlienku, že tento dej by sa dal použiť na hľadanie globálneho minima, prišli na začiatku osemdesiatych rokov nezávisle na sebe S. Kirkpatrick, C. D. Gelatt a M. P. Vecchi z výskumného centra IBM v USA a V. Černý z FMFI Bratislava. Teleso sa zahreje na vysokú teplotu, ktorá sa postupne pomaly znižuje, čo má za následok, že rovnovážne polohy atómov sa stabilizujú, takže pri konečnej teplote žíhania, ktorá je podstatne nižšia ako počiatočná, sú všetky atómy v rovnovážnych polohách a teleso neobsahuje žiadne vnútorné defekty. Metóda simulovaného žíhania má teda fyzikálny základ a inšpiruje sa tzv. horolezeckým algoritmom [2], ktorý prehľadáva množinu všetkých riešení. Aby bolo možné posúdiť, ako je určité riešenie dobré, vytvoríme účelovú funkciu f, ktorá je schopná ohodnotiť ľubovoľné riešenie patriace do množiny všetkých riešení. Táto funkcia je zobrazením z množiny všetkých riešení X do množiny reálnych čísel V horolezeckom algoritme sa na začiatku náhodne vygeneruje počiatočné riešenie . V ďalších krokoch sa postupne generuje použitím konečného súboru transformácií konečný počet riešení ležiacich v určitom okolí počiatočného riešenia. Z nich sa potom vyberie to, ktoré je z hľadiska účelovej funkcie najlepšie. Nevýhodou tohto prístupu je, že sa počas výpočtu akceptujú riešenia buď rovnako dobré alebo lepšie, ako je počiatočné riešenie. Preto sa môže stať, že sa metóda dostane k nevýraznému lokálnemu minimu od počiatočného riešenia a už nikdy nedosiahne optimálne riešenie. Tento nedostatok sa odstraňuje opakovaným spúšťaním algoritmu, a tým aj náhodnou voľbou počiatočného riešenia. Stochastickosť tejto metódy je teda len v hľadaní počiatočného riešenia. Uviaznutie v lokálnom minime úspešne rieši metóda simulovaného žíhania, ktorá prijíma s určitou pravdepodobnosťou aj horšie riešenie, ako bolo počiatočné. Podstatou metódy je numerická simulácia situácie. Vychádzame z určitého počiatočného riešenia a postupne v iteráciách hľadáme ďalšie riešenia, ktoré porovnávame s aktuálne najlepším. Toto porovnanie obsahuje stochastický operátor, ktorým sa transformuje aktuálne riešenie na nové. To, či bude nové riešenie akceptované, sa rieši pomocou Metropolisovho kritéria, ktoré určuje pravdepodobnosť nahradenia starého riešenia novým. Nech je aktuálne najlepšie riešenie získané predchádzajúcou iteráciou (alebo počiatočné riešenie). Nech x je riešenie náhodne vybrané v okolí , potom: ak , nové riešenie ; ak , nové riešenie s pravdepodobnosťou , kde parameter je teplota v t-tej iterácii, ktorá výrazne ovplyvňuje hodnotu pravdepodobnosti prijatia nového riešenia. Pre veľké hodnoty je táto pravdepodobnosť blízka jednej, takže sa akceptujú takmer všetky horšie riešenia. Ak sa blíži k nule, tak sa len výnimočne akceptuje horšie riešenie. Spôsob znižovania teploty sa nazýva plán chladenia. Zvyčajne je stupňovito klesajúca funkcia; počiatočná hodnota je zvolená a po každej iterácii sa vynásobí hodnotou ; čo znamená, že pravdepodobnosť prijatia horšieho riešenia klesá s časom. V praxi najčastejšie . Nevýhodou simulovaného žíhania je veľa nastaviteľných parametrov (k predstavuje maximálny počet iterácií; môže byť stanovený číselne alebo určitou podmienkou). Ukázalo sa, že lepšie výsledky možno dosiahnuť v spojení s genetickými algoritmami. Pre riešenie úlohy okružných jázd pomocou simulovaného žíhania možno v nájsť popis algoritmov: Two Early Simulated Algorithms, Osman´s Simalated Annealing Algorithms a Van Breedam´s Experiments. 2.2 Zakázané prehľadávanie Túto metódu navrhol a prvýkrát použil F. W. Glover v r. 1986, a formalizoval ju v roku 1989. Stala sa jednou z najrozšírenejších metód založených na metóde lokálneho prehľadávania. Vychádzame z počiatočného riešenia, ktoré sa postupne vylepšuje modifikovaním za pomoci lokálnych zmien. Prehľadávame priestor riešení problému; z riešenia získaného v iterácii do najlepšieho možného riešenia v množine susedov riešenia označovanej . Množinu susedov možno definovať ako množinu riešení, ktoré môžeme získať aplikáciou lokálnych zmien alebo posunov na aktuálne riešenie . Konkrétne, pre problém okružných jázd, ide o množinu možných riešení problému, pričom každý bod v tomto priestore reprezentuje množinu vozidiel a ich ciest spĺňajúcich všetky definované obmedzenia. Jednoduchá štruktúra množiny susedov obsahuje riešenia, ktoré získame v iterácii presunom jedného zákazníka z jeho pôvodného miesta v danej ceste riešenia . Tento zákazník môže byť následne vložený do tej istej cesty alebo do inej cesty s dostatočnou kapacitnou rezervou vo vozidle, ktoré je k danej ceste priradené. Zložitejšou štruktúrou množiny susedov je -medzivýmena, riešenia vzniknú presunom až zákazníkov medzi dvoma cestami v riešení . Aby sme zabránili zacykleniu iterovania, teda návratu k už preskúmanému riešeniu, využívame tzv. mechanizmus krátkodobej pamäti. Ide o to, že niektoré vlastnosti riešenia sú zapamätané a žiadne riešenie majúce niektorú zo zapamätaných vlastností nie je prípustné pre iterácií. Napríklad, pri probléme okružných jázd, ak zákazník bol práve presunutý z cesty do cesty (v iterácii ), tak zadefinujeme tabu presun pre návrat zákazníka späť do cesty aspoň iterácií ( má konštantnú hodnotu). Algoritmus pracuje s „tabu listom“, do ktorého najčastejšie ukladá transformácie inverzné k zakázaným presunom. Ak dosiahne tabu list svoju maximálnu kapacitu, automaticky sa z neho vylúči najstaršia transformácia. Tabu list sa teda cyklicky obnovuje. Zastavenie výpočtu môže byť nastavené na základe časového obmedzenia alebo počtom transformácií bez zlepšenia dosiahnutého riešenia. Do algoritmu bývajú implementované ďalšie vlastnosti, a to rôznotvárnosť a zosilnenie. Zosilnenie pozostáva z výraznejšieho prehľadávania priestoru okolo najlepších známych riešení. Cieľom rôznotvárnosti je zaistiť, aby v procese prehľadávania priestoru riešení neostala pomerne veľká vôbec nepreskúmaná podmnožina k sebe blízkych riešení. To býva docielené zapamätávaním postupnosti posledných riešení a následným penalizovaním často uskutočňovaných zmien. Tento mechanizmus je nazývaný dlhodobou pamäťou. Pre riešenie úlohy okružných jázd pomocou zakázaného prehľadávania možno v nájsť popis algoritmov: Two Early Tabu Search Algorithms, Osman´s Tabu search Algorithm, Taburoute Algorithm, Taillard´s Algorithm, Xu and Kelly´s Algorithm, Rego and Roucairol´s Algorithms, Barbarosoglu and Ozgur´s Algorithm, Adaptive Memory Procedure of Rochat and Taillard, Granular Tabu Search of Toth and Vigo. 2.3 Genetické algoritmy Genetický algoritmus je postupnosť krokov vedúca k nájdeniu optimálneho (blízkeho k optimálnemu) riešeniu na základe počítačovej simulácie darwinovskej evolúcie. Genetické algoritmy simulujú proces ustavičného vývoja prírody, ktorý je založený na výbere, krížení a mutáciách v priebehu jednotlivých generácií (populácií). Základnou myšlienkou tohto prístupu je, že jedinec s lepšími schopnosťami než bežná populácia má väčšiu šancu prežiť a stať sa rodičom. Potomkovia, ktorí vzniknú v tomto procese, majú ešte lepšie schopnosti prežiť ako ich rodičia. Na to, aby sme mohli genetický algoritmus použiť, musíme každé riešenie zakódovať do genetického reťazca, ktorý sa v súlade s genetickou terminológiou nazýva chromozóm. Jednotlivé položky tohto reťazca sa nazývajú gény a zvyčajne sa reprezentujú dvoma hodnotami 0 alebo 1. Počiatočná populácia vznikne náhodným vygenerovaním množiny chromozómov. Následne genetický algoritmus generáciu za generáciou zlepšuje tieto chromozómy až dovtedy, pokiaľ nebude splnené určité pravidlo zastavenia. Prvýkrát opisuje genetický algoritmus J. Holland v knihe Adaptation in Natural and Artificial Systems v r. 1975. Použitie tejto metódy pre riešenie problému okružných jázd je zriedkavejšie, napr. [3], [4], častejšie je používané na riešenie problému obchodného cestujúceho. 2.4 Kolónie mravcov Optimalizácia pomocou metódy kolónie mravcov je založená na odpozorovanom správaní sa mravčích kolónií pri hľadaní najkratšej cesty z mraveniska k potrave a späť. Na začiatku jednotlivé mravce hľadajú cestu k zdroju potravy náhodne. Každý mravec po objavení potravy zanecháva na ceste späť pachovú stopu (čiastočky feromónov), aby aj ďalšie mravce našli cestu k potrave. Teda kumulované množstvo feromónu určuje výhodnosť cesty. Čím je trasa pre mravca kratšia, tým menej času mu trvá ju prejsť, tým viac pachovej stopy na nej zanechá. Čím viac mravcov prejde po určitej ceste, tým má väčšiu feromónovú hodnotu a tým je atraktívnejšia. Časom feromón vypŕcha a príslušná menej navštevovaná cesta sa stáva menej atraktívnou, čo umožňuje preskúmať aj iné alternatívy. Keby feromón nevypŕchal, mravce by sa po krátkom čase pohybovali len po jednej ceste, ktorá by nebola optimálna. A. Colorni, M. Dorigo, V. Maniezzo v deväťdesiatych rokoch použili tento princíp odpozorovaný z prírody na riešenie úlohy obchodného cestujúceho. Algoritmus iteratívne konštruuje cesty pre každého mravca. Mravce sa pohybujú po vrcholoch a je nutné, aby si pamätali doposiaľ navštívené vrcholy. Mravce pri prechádzaní vrcholov majú informácie o vzdialenostiach do susedných vrcholov a o množstve feromónu, ktorý sa na hrane medzi danými vrcholmi nachádza. Na základe týchto dvoch informácií si mravec k vyberie hranu z vrcholu s do susedného nenavštíveného vrcholu q na základe pravdepodobnosti [8]: , kde je množstvo feromónu na príslušnej hrane, je atraktívnosť - funkcia vzdialenosti vrcholov (zvyčajne prevrátená hodnota ich vzdialenosti) a a,b sú konštanty, pričom a predstavujú vplyv atraktívnosti a množstva feromónu na výber hrany. Ak všetky mravce ukončili cesty, je upravené množstvo feromónu na hrane: , kde je konštanta vyparovania feromónu (používanou je hodnota ), je pridané množstvo feromónu mravcom k na príslušnej hrane. Zvyčajne, ak mravec k použil hranu na svojej ceste, tak , kde sú náklady na cestu k-tého mravca (zvyčajne dĺžka cesty) a Q je konštanta; to znamená, že najkratšia cesta pridá najväčšie množstvo feromónu. Ak mravec k nepoužil hranu, tak . Algoritmus pokračuje v ďalších iteráciách, pokiaľ nie je splnená ukončovacia podmienka. Uplatnenie algoritmu pri riešení problému okružných jázd možno nájsť v [5], [6], [7]. ZÁVER V článku je podaný len prehľad metaheuristických metód, ktoré sú použiteľné pri riešení dopravných problémov. Konkrétne použitie jednotlivých algoritmov je možné len po podrobnom štúdiu metódy a vyžaduje využitie simulačných programov. Dôležitá je vhodnosť metódy a nastavenie používaných parametrov tak, aby vyhovovalo daným špecifickým požiadavkám. Praktická aplikácia určitej metaheuristickej metódy je predmetom našej budúcej činnosti. LITERATÚRA [1] TOTH, P., VIGO, D. The Vehicle Routing Problem, SIAM Philadelphia, 2001, ISBN 0- 89871-579-2. [2] VAŠÍČEK, Z. Simulované žíhaní. Dostupné na : http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CDQQFjAA &url=http%3A%2F%2Ffeldocuments.googlecode.com%2Fsvn- history%2Fr127%2Ftrunk%2FNS%2Fmsi.pdf&ei=MuI9UbHSIPKM4gThvoGICg&usg=AF QjCNHaI54POzxZMS-JeksIth0_6ZPLXg&bvm=bv.43287494,d.bGE [3] BJARNADÓTTIR, A. S. Solving the Vehicle Routing Problem with Genetic Algorithms, Technical University of Denmark. Dostupné na http://etd.dtu.dk/thesis/154736/imm3183.pdf [4] NURFAHIZUL IFWAH. WA, W., SHAIFUL, M., SHAMSUNARNIE, M.Z., ZAINUDDIN, Z. M., FUAD, M. Genetic Algorithm for Vehicle Routing Problem with Backhauls. Dostupné na: http://penerbit.uthm.edu.my/ojs/index.php/JST/article/viewFile/463/313 [5] TOTH, P., VIGO, D. Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Applied Mathematics, vol.123, pp.487-512, 2002. [6] BELENGUER, J. M. AND BENAVENT, E. A cutting plane algorithm for capacitated arc routing problem. Computers & Operations Research, vol.30, no.5, pp.705-728, 2003. [7] RALPHS, T. K. Parallel branch and cut for capacitated vehicle routing. Parallel Computing, vol.29, pp.607-629, 2003. [8] DORIGO, M., STUTZLE, T. Ant Colony Optimization. The MIT Press, Massachusetts, 2004, ISBN 0-262-04219-3. [9] ZARE MEHRJERDI, Y. Vehicle Routing Problem: Meta-heuristic Approaches. In: International Journal of Applied Operational Research Vol. 2, No. 3, pp. 55-68, Autumn 2012. [10] COUSINEAU-QUIMET, K. A Tabu Search Heuristic for the Inventory Routing Problem, Montreal, 2002. Tento článok je súčasťou riešenia inštitucionálneho výskumu 1/KKMaHI/2013, F-PEDAS, Žilinská univerzita v Žiline.