UNIVERZITA PARDUBICE FAKULTA ELEKTROTECHNIKY A INFORMATIKY
DIPLOMOVÁ PRÁCE
2012
Bc. Jiří Popelka
Univerzita Pardubice Fakulta elektrotechniky a informatiky
Agentově orientovaný simulační model pro distribuci zboží Bc. Jiří Popelka
Diplomová práce 2012
Prohlášení autora
Prohlašuji: Tuto práci jsem vypracoval samostatně. Veškeré literární prameny a informace, které jsem v práci využil, jsou uvedeny v seznamu použité literatury. Byl jsem seznámen s tím, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorský zákon, zejména se skutečností, že Univerzita Pardubice 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, a s tím, že pokud dojde k užití této práce mnou nebo bude poskytnuta licence o užití jinému subjektu, je Univerzita Pardubice oprávněna ode mne požadovat přiměřený příspěvek na úhradu nákladů, které na vytvoření díla vynaložila, a to podle okolností až do jejich skutečné výše. Souhlasím s prezenčním zpřístupněním své práce v Univerzitní knihovně. V Pardubicích dne 24.8.2012
Jiří Popelka
Poděkování Touto cestou bych chtěl poděkovat svému vedoucímu práce Ing. Michaelu Bažantovi Ph.D., který mi umožnil toto zajímavé téma zpracovat a také za jeho odbornou pomoc a rady při psaní této diplomové práce.
Anotace Cílem práce je vytvořit agentově orientovaný simulační model pro experimentování s distribučním systémem v rámci vybraného fragmentu silniční sítě. Vytvořený simulační model poslouží k získání výsledků, které budou uplatněny v rámci projektu Green Logistics s primárním zaměřením na zkoumání produkce škodlivin produkovaných nákladními vozidly do ovzduší a vyhodnocení vybraných algoritmů v rámci simulačního modelu.
Klíčová slova lantime, dálniční hierarchie, agent, agentově orientovaná simulace, repast, plánování cest
Title Agent based simulation model for the distribution of goods.
Annotation The aim is to create an agent-based simulation model for experimenting with the distribution system within the selected fragment of the road network. The simulation model will be used to obtain results that will be applied within the project Green Logistics with primary focus on exploring production of pollutants produced by trucks into the air and evaluation of selected algorithms in the simulation model.
Keywords lantime, highway hierarchies, agent, agent-based simulation, repast, routing
Obsah 1
Úvod ........................................................................................................................12
2
Agentově orientované programování....................................................................13
3
2.1
Agent .................................................................................................................13
2.2
Vlastnosti agenta ...............................................................................................13
2.3
Druhy agentů .....................................................................................................14
2.4
Prostředí ............................................................................................................15
2.5
Agenti v simulacích ............................................................................................16
2.6
Agentově orientovaná architektura simulačního modelu ....................................16
2.7
Multiagentní přístup ...........................................................................................18
2.7.1
Komunikace................................................................................................20
2.7.2
Architektura ABASim ..................................................................................21
RepastSuite .............................................................................................................25 3.1
Základní koncept frameworku Repast Simphony ...............................................25
3.2
Repast Simphony 2 ...........................................................................................27
3.2.1
Repast Java ...............................................................................................28
3.2.2
ReLogo .......................................................................................................29
3.2.3
Repast Flowchart........................................................................................29
3.3 4
Repast HPC.......................................................................................................30
LANTIME .................................................................................................................32 4.1
Úvod ..................................................................................................................32
4.2
Road Timetable .................................................................................................33
4.2.1
Vytvoření Road Timetable ..........................................................................33
4.2.1.1 Nejrychlejší cesta ....................................................................................33 4.2.1.2 Časové intervaly .....................................................................................34 4.2.1.3 Vlastnost First-In First-Out ......................................................................34 4.3
Formulace a návrh algoritmu .............................................................................35
4.3.1 5
Souhrn celého algoritmu .............................................................................39
Nejrychlejší cesta pomocí dálniční hierarchie ......................................................41
5.1
Předpoklady.......................................................................................................41
5.1.1
Grafy a cesty ..............................................................................................41
5.1.2
Dijkstrův algoritmus ....................................................................................41
5.2
Obecný popis techniky.......................................................................................43
5.2.1
Lokalita .......................................................................................................43
5.2.2
Dálniční hierarchie ......................................................................................44
5.3
Konstrukce.........................................................................................................44
5.3.1
Fáze 1 – Konstrukce stromu částečných cest .............................................44
5.3.1.1 Ukončovací kritérium...............................................................................45 5.3.1.2 Příklad fáze 1 ..........................................................................................45 5.3.2
Fáze 2 – Výběr dálničních hran ..................................................................46
5.3.2.1 Popis algoritmu .......................................................................................46 5.3.3
Zrychlení konstrukce...................................................................................47
5.3.4
Kontrakce dálniční sítě ...............................................................................48
5.4
Nalezení nejkratší cesty .....................................................................................49
5.4.1 6
Algoritmus výběru nejkratší cesty ...............................................................50
Realizace modelu....................................................................................................51 6.1
Vstupní data ......................................................................................................51
6.1.1
Datové úložiště ...........................................................................................53
6.1.2
Oracle Database 11g Express Edition ........................................................53
6.1.3
Struktura databáze .....................................................................................54
6.1.3.1 Tabulka network......................................................................................54 6.1.3.2 Tabulka default_speed ............................................................................54 6.1.3.3 Tabulka speed ........................................................................................54 6.1.3.4 Tabulka timetable ....................................................................................55 6.1.4
Problémy s daty ..........................................................................................56
6.1.5
Použitá dopravní síť....................................................................................56
6.1.6
Vytvoření Road Timetable ..........................................................................57
6.2
Model.................................................................................................................57
6.2.1
Popis ..........................................................................................................57
6.2.1.1 Agent Controller ......................................................................................58 6.2.1.2 Agent Depo .............................................................................................58 6.2.1.3 Agent Customer ......................................................................................58 6.2.1.4 Agent Vehicle ..........................................................................................59 6.2.1.5 Agent Scheduler .....................................................................................59 7
8
Experimenty ............................................................................................................60 7.1
Scénář 1: Jedno vozidlo s kapacitou 50 jednotek...............................................60
7.2
Scénář 2: Jedno vozidlo s kapacitou 100 jednotek.............................................61
7.3
Scénář 3: Dvě vozidla s kapacitou 50 jednotek ..................................................62
7.4
Scénář 4:Čtyři vozidla s kapacitou 20 jednotek ..................................................63
7.5
Scénář 5: Šest vozidel s kapacitou 20 jednotek .................................................64
7.6
Scénář 6: Deset vozidel s kapacitou 10 jednotek ...............................................65
Závěr ........................................................................................................................66
Seznam použité literatury..............................................................................................67 9
Přílohy .....................................................................................................................69
Seznam obrázků Obrázek 1Interakce agenta s okolím. Zdroj:[1].................................................................13 Obrázek 2Klasifikace agentů. Zdroj:[2]. ...........................................................................14 Obrázek 3Funkce agenta. Zdroj: [2]. ................................................................................17 Obrázek 4Schopnosti agenta. Zdroj:[2]. ...........................................................................17 Obrázek 5Hierarchická struktura agentů a modelů. Zdroj: [2]...........................................19 Obrázek 6Vrstvy simulačního modelu. Zdroj: [2]. .............................................................22 Obrázek 7Příklad implementace agenta chodce. Zdroj: [5] ..............................................26 Obrázek 8Běhové prostředí Repast Simphony s 2D a 3D pohledem. Zdroj: [5]. ..............27 Obrázek 9Ukázka prostředí flowchart. Zdroj: [5]. .............................................................30 Obrázek 10 Časové intervaly. Zdroj: [7]. ..........................................................................34 Obrázek 11 Pseudokód výpočtu času příjezdu. Zdroj: [7]. ...............................................35 Obrázek 12 Čtyři druhy přesunu v sousedství. Zdroj: [6]. .................................................38
Obrázek 13 Neorientovaný graf s cestou a podcestou. Zdroj:[12]. ...................................41 Obrázek 14 Prohledávací prostor Dijkstrova algoritmu. Zdroj: [12]. ..................................43 Obrázek 15 Dvojsměrný Dijkstrův algoritmus. Zdroj: [12]. ................................................43 Obrázek 16 Sousedství vrcholu s o velikosti 5. Zdroj:[12]. ...............................................44 Obrázek 17 Částečná nejkratší cesta. Zdroj: [12].............................................................44 Obrázek 18 Ukončovací kritérium. Zdroj:[12]. ..................................................................45 Obrázek 19 Konstrukce - fáze 1. Zdroj: [12]. ....................................................................45 Obrázek 20 Konstrukce - fáze 2. Zdroj: [12]. ....................................................................46 Obrázek 21 Konstrukce – „Slacková“ metoda. Zdroj: [12]. ...............................................47 Obrázek 22 Porovnání konstrukčních metod. Zdroj: [12]..................................................47 Obrázek 23 Dálniční síť a přiložený strom se zkratkami. Zdroj: [12]. ................................48 Obrázek 24 Dálniční hierarchie. Zdroj: [12]. .....................................................................49 Obrázek 25 Pseudokód vyhledávání nejkratší cesty. Zdroj: [11]. .....................................50 Obrázek 26 Architektura JDBC ........................................................................................53 Obrázek 27 Struktura tabulky „network“. ..........................................................................54 Obrázek 28 Struktura tabulky „default_speed“. ................................................................54 Obrázek 29 Struktura tabulky „speed“..............................................................................55 Obrázek 30 Struktura tabulky „timetable“. ........................................................................55 Obrázek 31 Dopravní síť použitá v modelu ......................................................................57 Obrázek 32 Náhled zobrazení modelu .............................................................................59 Obrázek 33Scénář 1 – průměrné vzdálenosti. .................................................................60 Obrázek 34 Scénář 1- produkce CO2 podle metody plánovaní tras..................................60 Obrázek 35 Scénář 2 – průměr vzdálenosti. ....................................................................61 Obrázek 36 Scénář 2 - produkce CO2 podle metody plánovaní tras.................................61 Obrázek 37Scénář 3 – průměr vzdálenosti. .....................................................................62 Obrázek 38 Scénář 3 - produkce CO2 podle metody plánovaní tras.................................62 Obrázek 39Scénář 4 – průměr vzdálenosti. .....................................................................63 Obrázek 40Scénář 4 - produkce CO2 podle metody plánovaní tras..................................63
Obrázek 41 Scénář 5 – průměr vzdálenosti. ....................................................................64 Obrázek 42Scénář 5 - produkce CO2 podle metody plánovaní tras..................................64 Obrázek 43 Scénář 6 – průměr vzdálenosti. ....................................................................65 Obrázek 44Scénář 6 - produkce CO2 podle metody plánovaní tras..................................65
Seznam tabulek Tabulka 1Defaultní rychlosti podle úrovně silnici a timeslotu. ...........................................51 Tabulka 2 Data soubor s dopravní sítí. ............................................................................51 Tabulka 3 Struktura souboru upravující rychlost hrany.....................................................52 Seznam zkratek ACL
jazyk pro komunikaci v prostředí multiagentních systémů
KQML
jazyk a protokol pro výměnu informací a znalostí
FIPA
sdružení fyzikcé inteligentní agenty
ABAsim
agentově orientovaná simulace
C++
programovací jazyk
Java
programovací jazyk
IDE
vývojové prostředí
GUI
grafické uživatelské prostředí
2D, 3D dvou a tří rozměrný prostor XML
rozšiřitelný značkovací jazyk (Extensible Markup Language)
CSV
jednoduchý souborový formát pro výměnu tabulkových hodnot
JGAP
Java balíček genetických algoritmů (Java genetic algorithms package)
MPI
knihovna pro podporu paralelního řešení výpočetních problémů v clusterech
mph
míle za hodinu
FIFO
datová struktura typu fronta, (first-in-firtst-out)
API
aplikační informační rozhraní
JDBC
Java Database Connectivity
OJDBS
JDBC API pro Oracle
CPU
procesor
GHz
Giga Hertz, jednotka frekvence
RAM
operační paměť
m/s
metr za sekundu
1 Úvod Diplomová práce je primárně zaměřená na ověření algoritmu LANTIME a následné simulování pohybu vozidel po reálné dopravní síti, za účelem zjištění možné minimalizace množství vypouštěného oxidu uhličitého do ovzduší. Téma jsem si vybral, neboť mi přišlo zajímavé a zaujala mě také možnost podílet se na projektu Green Logistics a získat nové zkušenosti s frameworkem Repast Suite, ve kterém je agentově orientovaný model realizovaný. V této práci nejprve vysvětlím, co je agentově orientované programování a jaké základní prvky ho tvoří. Následně naznačím principy agentově orientovaného simulačního modelu. Ve třetí kapitole Vás obeznámím s frameworkem Repast Suite, který slouží k vytváření agentově orientovaných simulačních modelů. Ve čtvrté kapitole je popsaný plánovací algoritmus LANTIME. Je zde popsána metodika vytváření Road Timetables a způsob, jakým algoritmus přiřazuje zakázky na doručení zásilek jednotlivým automobilům tak, aby vypouštěly co nejmenší množství oxidu uhličitého. V páté kapitole popíši, jakým způsobem efektivně vypočítat nejkratší cestu na rozsáhlé dopravní síti (resp. orientovaném grafu). Zaměřím se na tvorbu úrovní potřebných pro dálniční hierarchii a hned po té na algoritmus pro vyhledávání nejkratší cesty. Po teoretické části se dostávám k implementaci konkrétního simulačního modelu. Jsou zde hlavně popsána data potřebná pro simulační model a vyskytlé problémy s těmito daty. Po implementaci agentově orientovaného simulačního modelu je připraveno několik experimentů k ověření funkčnosti. V závěru své diplomové práce se zamýšlím nad možností rozšíření simulačního modelu a zhodnotím průběh její tvorby a její přínos.
12
2 Agentově orientované programování Tato kapitola se věnuje definici základních pojmů agentově orientovaného programování, jako je agent, prostředí či komunikace mezi agendy. Je zde také popsán princip agentově orientované simulace.
2.1 Agent V 60. letech 20. století se v počítačové terminologii poprvé objevil pojem agent. Agent je definovaný jako autonomní systém, který je schopný vnímat okolí ve kterém se nachází, dokáže s ním komunikovat a dokonce je schopný samostatného rozhodování, jaké další akce vykoná. V nynější době se v souvislosti pojmu agent představují multiagentní systémy.[1] Agenty můžeme nalézt téměř kdekoliv, nejen v počítačové terminologii. Může jím být člověk, jakož to biologický agent, robot jako technická agent atd. Agentem proto můžeme nazvat cokoliv, co dokáže vnímat své okolí a následně reagovat. Pro vnímání okolí používá agent senzory, pomocí nichž dostává zprávy. Pro ovlivnění okolí, používá agent efektory (obr. 1). Pro dosažení daného cíle je agent schopný samostatného rozhodování, jakých akcí pro to použije.[1]
Obrázek 1Interakce agenta s okolím. Zdroj:[1]
2.2 Vlastnosti agenta Mezi základní vlastnosti agenta patří dle [2]:
Autonomie - jeli agent cílově orientovaný modul, schopný samostatného řešení určitých úloh bez nezbytné komunikace s okolím, avšak schopný komunikace, koordinace činnosti či kooperace s jinými agenty v rámci určité komunity. Mají možnost dobrovolně vstupovat a opouštět komunitu, poskytovat či požadovat výsledky.
Reaktivita - znamená to, že je agent schopen adekvátní reakce na změny ve svém okolí.
Společenské chování - spočívá v tom, že je agent schopen komunikace s jiným agentem nebo člověkem pomocí nějaké formy komunikace. 13
Iniciativnost - agent by měl mít schopnost reakce na změny ve svém okolí, ale měl by mít i chování zaměřené na dosažení cíle, který ovlivňuje akce agenta.
Podle potřeb jednotlivých aplikací, ve kterých mají být agenti použiti, je i ovlivněna realizace agenta. Podle toho na jakou vlastnost je kladen důraz, vychází i samotná technická realizace agenta.
2.3 Druhy agentů Klasifikace druhů agentů není v dnešní době jednoznačná, avšak pomocí tří kritérií, můžeme agenty rozdělit na základní skupiny. Těmito kritérii jsou dle[2]:
Mobilita - schopnost jejich pohybu v prostředí. Podle tohoto kritéria se agenti děli na statické a mobilní. Statičtí agenti setrvávají na jednom místě v rámci prostředí nebo v počítačové síti na jednom počítači. Oproti tomu mobilní agenti se mohou pohybovat.
Míra iniciativnosti - rozlišujeme uvažující a reaktivní agenty. Uvažující agenti jsou založeni na logickém uvažování nebo v sobě zahrnují model okolního prostředí, jsou tedy schopni kdykoliv rozhodnout o tom jakou činnost v daném momentu vykonávat. Reaktivní agenti fungují na principu podnět→odezva. Jejich rozhodnutí tedy vyplývá z aktuálního stavu prostředí, v němž jsou umístěni. Reaktivní agenti tedy pouze reagují na podněty z okolí.
Autonomnost, kooperace a schopnost učit se - rozlišujeme tedy kooperativní agenty, agenty rozhraní, kooperativní učící se agenty a inteligentní agenty.
Na obrázku (Obr. 2) jsou znázorněné vzájemné průniky dle uvedených vlastnosti agentů.
Obrázek 2Klasifikace agentů. Zdroj:[2].
Kromě těchto základních uvedených členění je možné dále klasifikovat podle jejich konkrétního aplikačního poslání (například internetový agent působí v 14
prostředí internetu, informační agent pracuje ve spojení s určitým informačním systémem atd.) anebo podle použitého koncepčního přístupu (filozofie), který je při konstrukci agenta uplatněný. V případě, že je při tvorbě jednotlivého agenta použita kombinace vícerých koncepčních přístupů, které byly diskutované, tak hovoříme o hybridním agentovi (ten může například kombinovaně využívat principy uvažujících a reaktivních agentů apod.)[1] Existuje i důsledná klasifikace, jež určí přesné začlenění agenta. Já zde však uvedu pouze jednodušší klasifikaci zdůrazňující nejvíce používané typy agentů. Agenti se tedy člení dle [2] na:
Kooperativní agenty.
Agenty rozhraní.
Mobilní agenty.
Informační/internetové agenty.
Reaktivní agenty.
Hybridní agenty.
Inteligentní agenty.
V případě, že aplikace kombinuje použití dvou nebo více z výše uvedených druhů agentů, říkáme, že se jedná o heterogenní (různorodý) systém agentů.[2]
2.4 Prostředí Prostředí je vše, s čím agent přichází během své činnosti do styku. Je to tedy agentní systém bez jediného svého prvku - agenta. Prostředí z hlediska agenta pak může být dle [2]:
Plně pozorovatelné/Částečně pozorovatelné. Prostředí je pro agenta plně pozorovatelné, pokud může svými senzory sledovat jeho kompletní stav.
Statické/Dynamické. Prostředí je pro agenta statické, pokud se může měnit pouze jeho akcemi.
Deterministické/Nedeterministické. Prostředí je deterministické, jestliže je jeho stav po vykonání nějaké akce dán pouze touto akcí a předcházejícím (původním) stavem tohoto prostředí.
Diskrétní/Spojité. Prostředí je diskrétní, pokud má konečně nebo spočetně mnoho stavů. Pro agenta založeného na číslicových počítačích/procesorech je každé prostředí diskrétní. Údaje ze senzorů se totiž ukládají do konečného binárního řetězce, a proto existuje pouze konečná množina stavů tohoto prostředí.
15
2.5 Agenti v simulacích Co vlastně přináší uplatnění agentů v oblasti simulací? Za prvé to je vysoký stupeň decentralizace z toho vyplývá, že není potřeba tvořit žádný globální model řízení celého společenství agentů, neboť každý z nich je autonomní. Za druhé je to vysoká životaschopnost systému. Uvedené rysy by mohly být poměrně zajímavé pro tvorbu komplexních simulačních modelů (např. území rozsáhlých obslužných systémů anebo biologických společenstev), pro které by bylo možné navrhnout dobře udržovatelnou a srozumitelnou strukturu členěnou například na přirozené autonomní jednotky řazení (např. při složitých obslužných systémech) anebo na jednotlivé autonomní jedince (např. u biologických společenstev). Právě agenti se jeví jako dobří kandidáti na realizaci takovýchto autonomních řídících jednotek, resp. autonomních jedinců.[1] Pokud již existuje implementačně-technická podpora, třeba specializovaný software pro tvorbu agentově-orientovaného programování, je možné ji použít. Pokud není dostupná nebo nevyhovuje daným potřebám, pak nezbývá, nežli navrhnout a realizovat vlastní. Zde se řeší především to, jakým způsobem mají být implementováni jednotliví agenti, jak má být zabezpečený mechanizmus jejich komunikace a jaká koncepce bude použita na synchronizaci simulačního výpočtu.
2.6 Agentově orientovaná architektura simulačního modelu Zatím pojem architektura simulačního modelu je dosti volné téma, proto uvedu alespoň dva základní prvky, na kterých tato architektura stojí. Za prvé, základní strukturální anebo funkčně-akční jednotky, s jejichž pomocí je simulační model postavený (např. událost, aktivita, proces, agent apod.). Za druhé je to rozdělení simulačního výpočtu na výpočtové jednotky. Z tohoto hlediska existují dva druhy. Pokud je simulační model realizován na jednoprocesorovém počítači jedná se o monolitickou architekturu. V opačném případě se jedná o paralelní (distribuovanou) architekturu, která je realizována na víceprocesorovém počítači, nebo v počítačové síti. Každý typ architektury má možnost různým způsobem implementovat synchronizaci simulačního výpočtu. Následuje popis specifických funkcí agenta v architektuře simulačního modelu inspirovaného filozofii reaktivních agentů (Obr. 3). Každý agent má zadán určitý cíl, jež má plnit. Tento cíl mu je buď zadán, nebo v případě inteligentních agentů si jej identifikuje sám. V souladu s tím, pro co je agent zkonstruován, realizuje svůj životní cyklus a to následovně: rozpoznání situace − rozhodování o řešení − výkon řešení. Život a tedy rozhodování agenta je dáno také tím v jakém se nachází prostředí, to zahrnuje všechny ostatní agenty a také tu část prostoru simulačního modelu, ve kterém je agent oprávněný vykonávat změny. Prostředí působení agenta může být buď vymezené, nebo se v případě mobilních agentů může dle potřeby měnit. 16
Pokud se agent rozhoduje, pak používá funkci návrhu řešení problémů a komunikace s jinými agenty. Dostane-li agent podnět a řešení dané situace, které je v jeho kompetenci, pak pomáhá řešit problém jiným agentům tím, že je na tuto skutečnost upozorní.
Obrázek 3Funkce agenta. Zdroj: [2].
K tomu, aby mohl agent efektivně vykonávat výše uvedené funkce, je nutné, aby disponoval jistými schopnostmi (Obr. 4.).
Obrázek 4Schopnosti agenta. Zdroj:[2].
17
Pro komunikaci agentů s jinými agenty nebo s člověkem mu slouží komunikační mechanizmus. Agent má schopnost navrhovat jednorázové řešení problémů (např. volání optimalizačních algoritmů), dále má schopnost sestavovat dlouhodobější plány k vykonávání obslužných činností jako je např. rozvržení zdrojů. Tato činnost však není vyjádření o tom, jak se bude chovat agent v budoucnosti. Senzorická činnost umožňuje agentovi se ptát na stav systému či snímat části svého okolního prostředí. Svou výkonnou funkcí realizuje buď aktivací akce, která okamžitě mění stav systému nebo spustí proces, který mění stav systému v určitém časovém intervalu v jistých časových okamžicích bez jakýchkoliv vnějších zásahů. Schopnosti agenta je vhodné rozdělit do skupin a každou takovouto schopnost implementovat jako samostatnou interní komponentu. Hlavními důvody pro tuto dekompozici agenta jsou:
Možnost případného sdílení komponenty vícero agenty a její opakované použití.
Možnost implementace vícerých alternativních verzí jedné komponenty, ze které si uživatel vybere jeden vhodný při sestavování scénáře simulačního experimentu.[1]
2.7 Multiagentní přístup V nejjednodušším případě modelování reálného světa můžeme pracovat i jen s jediným agentem, popisujícím jediný systém. Nicméně běžnější je situace, kdy reálný svět modelujeme prostřednictvím sady agentů, modelujících různé relativně samostatné podsystémy a také relace a interakce mezi nimi. V takovém případě mluvíme o multiagentních systémech. Teorie multiagentních systémů je poměrně mladou vědeckou oblastí, zatím v ní nejsou ustálená jasná pravidla. Multiagentní systém je tvořen skupinou agentů, kteří představují aktivní prvky, dále zde mohou být objekty, které žádnou aktivitu nevyvíjejí, ale svojí existencí ovlivňují chování agentů. Toto vše je zasazeno do určitého prostředí, které zprostředkovává interakci mezi agenty i objekty. Prostředí má rovněž vliv na chování agentů, respektive je jimi ovlivňováno. Prostředí rovněž svými vlastnostmi vymezuje možnou interakci mezi agenty navzájem stejně jako interakci agentů s objekty. Agenti a objekty zde vstupují do celé řady vzájemných vztahů. Multiagentní systémy většinou pracují v diskrétních časových krocích. Za multiagentní lze považovat takový systém, který se skládá z následujících komponent dle[1]:
Prostředí E, jehož jednou z vlastností může být i prostorovost, tj. může se jednat o prostor, který je obecně n-rozměrný.
Množina objektů O. Tyto objekty jsou situované, tj. v kterémkoliv okamžiku je možné k objektu přiřadit polohu v E. Objekty jsou zpravidla pasivní, mohou být vnímány, vytvářeny, odstraňovány a modifikovány agenty. 18
Množina agentů A. Agenti jsou podmnožinou objektů a jsou schopné vykonávat určité akce. Představují aktivní entity systému.
Množina polí F. Agenti mohou šířit do svého okolí prostřednictvím prostředí E signály v podobě polí a jiná pole mohou naopak vnímat.
Množina míst L určujících možné polohy objektů (z množiny O) v prostoru, tj. v prostředí E.
Množina relací R, které vzájemně spojují objekty a také agenty.
Množina operací Op, dávajících agentům schopnost vnímat, manipulovat, vytvářet, odstraňovat objekty z O, a reprezentujících především akce agentů.
Množina operátorů U, reprezentujících aplikace operací z Op na prostředí a reakcí světa na tento pokus o jeho modifikaci. Operátory U jsou nazývány zákony univerza. Takto lze definovat obecný multiagentní systém, který může být i prostorový. [3]
Multiagentní hierarchický systém můžeme demonstrovat na ilustračním příkladě (Obr. 5), kde A0 (např. agent dopravní sítě) rozděluje správu celé sítě S0 na dvě částečné správy regionů S1 a S2 . Hovoříme, že agent A0 delimituje správu sítě na dva rovnocenné „regionální“ agenty A1 a A2, přičemž od nich může být informovaný o závažných skutečnostech, tykající se celé sítě a též jim může sám odevzdávat pro ně důležité regionální informace.[1]
Obrázek 5Hierarchická struktura agentů a modelů. Zdroj: [2]
Předpokládá se, že v každém ze dvou regionů se budou vykonávat stejné správní činnosti. Každý z regionálních agentů používá na plnění svých cílů dalších úzce specifikovaných agentů, na kterých deleguje část svých kompetencí. Z uvedeného obrázku je zřejmé, že regionální agent A1 využívá pro splnění daných úloh jinou strukturu podřadných agentů než jeho „kolega“ A2. Z jiného pohledu je možné na hierarchickou strukturu agentů (množinu A) pohlížet jako na hierarchickou strukturu modelů (množinu M, |M|=|A|), přičemž každý model Mi ∈M, 19
(Mi ⊆ A) sestavenou ze stromu agentů s kořenem/agentem Ai∈A, i=0,..., |A|-1. Agenta Ai nazýváme představitelem (bossem) modelu Mi, přičemž Mi alternativně označujeme jako model Ai.[1] Modely na nejnižší úrovni hierarchie jsou jednoagentní modely. V algebraickém vyjádření můžeme potom strukturu modelů M0 z obrázku vyjádřit výrazem M0[M1(M3, M4, M5 ),M2(M6,M7(M8, M9 ))], přičemž modely v hranatých závorkách vznikli delimitací a modely v kulatých závorkách vznikly delegováním funkcí jejich nadřízeného modelu.[1]
2.7.1 Komunikace Akce, které agent vykonává, transformují stav prostředí. V multiagentním systému však tvoří agentovo okolí i ostatní agenti, kteří se nachází v tomto systému. Z hlediska agenta je proto každý agent pouze dalším prvkem systému, vůči kterému může působit – vykonávat akce. Podobně jako v případě neagentních prvků okolí, může být agentovým záměrem změnit vnitřní (mentální) stav jiného agenta. Obecně se rozlišují dva přístupy, kterými může agent mentální stav jiného agenta změnit.[4]
Nepřímé ovlivnění: Agent nepůsobí přímo na jiného agenta, ale mění stav jeho okolí tak, aby ten při kontaktu s tímto okolím změnil svůj postoj žádaným směrem.
Přímé ovlivnění: Agent působí na jiného agenta přímo a jediným možným způsobem tohoto ovlivnění je komunikace.
Důvodů ke komunikaci může mít agent několik. Já zde uvádím šest základních typů dialogu.[4]
Dotazování: Agent hledá nějakou informaci a dotazuje se jiného agenta, o kterém věří, že mu tuto informaci může poskytnout.
Hledání informace: Agenti společně pátrají po informaci, která není známá žádnému z nich.
Přesvědčování: Agent se snaží přesvědčit jiného agenta, aby přijal některé z jeho záměrů.
Vyjednávání: Agenti vyjednávají o podmínkách sdílení prostředků, nebo o poskytnutí služeb tak, aby všichni zúčastnění dosáhli maximálního zisku.
Porada: Cílem porady je nalézt řešení problému, které je v zájmu všech zúčastněných. Agenti poskytují své znalosti a schopnosti a usnáší se na dalším postupu.
Eristický dialog: Eristický dialog je dialog, během kterého si agenti vyměňují expresivně informace za účelem dosažení svých záměrů. Tyto informace nejsou ani logickou podporou argumentu, ani vyjednáváním či dotazováním. Typickým takovým dialogem je hádka.
Vlastní komunikace je proces, během kterého si dva nebo více agentů vyměňují informace ve formě elementárních komunikačních zpráv. Každá 20
elementární komunikační zpráva má odesílatele, příjemce, obsah a informaci o typu, který určuje význam obsahu zprávy. [4] Pokud agent chce komunikovat, musí mít schopnost nalézt partnera vhodného pro záměry, kterých hodlá touto komunikací dosáhnout. Řešení nastíněného problému může vycházet z nástrojů, které jsou již nyní využívány pro distribuované systémy, jako například vysílání (broadcasting) nebo nástěnky. Jiné přístupy nabízí výsledky bádání přímo v oblasti agentních systémů. Hledání vhodného partnera pro komunikaci může být řešeno například přes adresáře služeb, nebo adresáře agentů, přítomných na agentních platformách. Dále lze využít speciálních agentů pro zprostředkovávání komunikace nebo pro vyhledávání služeb, ti se nazývají mediátoři, brokeři, nebo facilitátoři. Posledním známým přístupem jsou sociální modely. Komunikace v sociálních modelech je založena na vysílání požadavku uvnitř skupiny a teprve v případě neúspěchu se požadavek vysílá i k ostatním skupinám v systému.[4] Posledním tématem agentní komunikace jsou interakční protokoly. Tyto protokoly udávají pravidla komunikace mezi agenty. Komunikační protokoly se liší podle druhu komunikace a částečně kopírují rozdělení typů dialogu uvedené výše. Každý komunikační jazyk pro komunikaci agentů je, stejně jako všechny ostatní jazyky, dán abecedou, syntaxí a sémantikou. V současné době je hlavním jazykem pro komunikaci agentů ACL (Agent Communication Language). ACL vychází z jazyka KQML (Knowledge Query Manipulation Language), řeší některé nedostatky, kvůli kterým býval KQML kritizován a jeho standardizace je uvedená ve specifikacích FIPA.[4]
2.7.2 Architektura ABASim ABASim (Agent-Based Architecture of Simulation model) architektura byla vyvinutá kolektivem pracovníků na Fakultě řízení a informatiky na Žilinské univerzitě. Tato architektura umožňuje tvořit flexibilní simulační modely komplexních obslužných systémů. Simulační model je složen z kooperujících reaktivních agentů, kteří jsou organizování v hierarchické struktuře. Hierarchická struktura je typická pro obslužné systémy. Každý agent této architektury se skládá z komponent, které zabezpečují senzorickou, výkonnou a komunikační činnost agenta. Následující text se bude podrobně věnovat této architektuře. V abasie architektuře jsou systémy modelované z hlediska rozhodování a řízení. Jak bylo uvedeno výše, řídící prvky mají určité kompetence a jsou hierarchicky organizované. Řídící prvek má zabezpečit předem definovaný cíl. Při plnění cíle se rozhoduje, zda bude spolupracovat se svými podřízenými řídícími prvky nebo zda danou úlohu zpracuje sám. Řídící prvky se modelují pomocí agentů. Agent tvoří základní stavební a funkční jednotku v modelu obsahuje totiž funkce potřebné prořízení a aplikaci svých rozhodnutí. Každý model se skládá z jednoho nebo více kooperujících agentů. Agent má několik hlavních funkcí jako je identifikace cíle, rozpoznává situaci, rozhoduje o řešení a vykonává řešení. Agent při rozhodování o řešení může použít funkce návrhu řešení problému a kooperaci s jinými agenty nebo s člověkem.
21
Obrázek 6Vrstvy simulačního modelu. Zdroj: [2].
Rozklad agenta na jeho jednotlivé vnitřní součásti do dvou skupin (manažeři a asistenti) nastiňuje myšlenku dívat se na celý model jako na systém založený z jednotlivých vrstev (Obr. 6). Jednak je to vrstva managementu, která se rozhoduje a vydává pokyny pro realizaci svých rozhodnutí. Potom je zde vrstva zpracování, kde její součásti asistují managementu a realizují požadované výkony ve vymezeném prostoru simulačního modelu. V modelu je možné uvažovat také o další vrstvě. Vrstva entit vytváří stavový prostor simulačního modelu a nese informační a fyzické entity. Fyzické entity odpovídají všem prvkům simulovaného modelu. Všechny fyzické entity jsou modelovány komplexní modelovou strukturou, která odráží stav simulovaného modelu. Informační entity nesou informace, které nejsou přímo součástí fyzických entit, ale jsou potřebné k řízení systému nebo popisují chování modelu v čase. V popisované architektuře existuje komunikace jednak mezi agenty a jednak vnitřní komunikace mezi manažerem a jeho asistenty. Oba dva druhy jsou v abasie architektuře realizované pomocí zasílání zpráv a z tohoto hlediska je možné označit abasie architekturu jako zprávou orientovanou. Existují zde tři vrstvy, na kterých probíhá komunikace. Následuje přehled, jaké zprávy se používají v jaké vrstvě.
22
Pro komunikaci mezi agenty (mezi jejich manažery) se používají typy zpráv dle [2]:
Gotice (oznámení), je zpráva, na kterou se neočekává žádná odpověď.
Regest (žádost) je zpráva obsahující určitý požadavek (na poskytnutí služby či informace), přičemž odesílatel očekává na ni od adresáta odpověď.
Response (reakce/odezva), která reprezentuje povinnou odpověď na zprávu typu Regest, přičemž může být doručená pouze jejímu odesílateli.
Pokyny, které může manažer dávat svým asistentům, jsou realizované pomocí následujících typů zpráv dle [2]:
Start, po přijetí zprávy tohoto druhu začne adresát (musí to být kontinuální asistent) svojí autonomní činnost.
Brek, představuje jediný způsob, jak může manažer ovlivnit autonomní běh kontinuálního asistenta, který je po přijetí této zprávy nezvratně ukončen (tento typ se používá jen ve výjimečně a to v případech, kdy nastaly v simulačním modelu takové podmínky, při kterých již nemá smysl, aby kontinuální asistent dokončil svoji činnost).
Exekute, je specifickým typem zprávy, určené pro promptního asistenta, který okamžitě vykoná odpovídající činnost a obratem zprávu vrátí svému manažeru (odesílateli) s vyznačeným výsledkem svoji činnosti.
Posledním druhem zpráv, které se v architektuře ABAsim používají, jsou zprávy, které odesílají kontinuální asistenti v čase svojí autonomní činnosti dle [2]:
Finish je zpráva, kterou každý z kontinuálních asistentů povinně zašle svému manažerovi v okamžiku své činnosti.
Notice jsou zprávy, které mohou být zaslané v zásadě kdykoliv v průběhu činnosti kontinuálního asistenta, kdy kontinuální asistent potřebuje oznámit svému manažeru výskyt pro něho důležité situace.
Hold je jedinou zprávou, která obsahuje tzv. časovou pečeť určující čas na její dokončení, přičemž tuto zprávu si kontinuální asistent zásadně posílá sám sobě (kontinuální asistent může po odeslání této zprávy opět pokračovat ve svojí činnosti až od toho okamžiku simulačního času, kdy je mu tato zpráva doručena. Do té doby je neaktivní).
V ABAsim architektuře se běh simulačního času zabezpečuje výlučně zasláním zpráv typu Hold, a tedy časová synchronizace modelu se vlastně realizuje synchronizací činností kontinuálních asistentů. Ve vrstvě managementu se zprávy s časovými pečetěmi nepoužívají, a tedy zde se simulační čas neovládá a nesynchronizuje. V případě aplikace architektury v distribuovaném prostředí je 23
nutné vybavit i zprávy managementu časovými pečetěmi pro případ, že jsou tyto zprávy zasílané do jiného uzlu v síti s jiným lokálním simulačním časem, než má odesílatel. Po vysvětlení zásad komunikace v ABAsim architektuře je zřejmé, že popsaná komunikace slouží hlavně pro realizaci diskrétních simulačních modelů. Nicméně je možné rozšířit mechanizmus komunikace tak, aby se dal použít i při tvorbě diskrétně-spojitých simulačních modelů.
24
3 RepastSuite Repast Suite1 je skupina pokročilých, zdarma šiřitelných, open source softwarů. Tyto softwary jsou určeny pro podporu a vývoj agentově orientovaného modelování a simulace. Všechny součásti jsou kolektivně vyvíjeny více než 10 let skupinou z Chicagské univerzity v Illinois (USA). Mezi původní vývojáře patří David Sallach, Nick Collier, Tom Howe, Michael North. Tito lidé vytvořili první koncept původního frameworku Repast (z angl. „The Recursive Porous Agent Simulation Toolkit“). Celá tato kapitola je převzata z [5]. Repast Simphony je rozšíření původního frameworku Repast a přináší nový přístup k vývoji a provádění agentově orientovaných simulací. Zahrnuje navíc i mnoho pokročilých výpočetních technik pro aplikace, které simulují například sociální modely. Framework v aktuální verzi nabízí dva základní softwary a to Repast HPC (High Performance Computing) a Repast Simphony 2. První zmíněný software je implementován v C++a je určen pro simulaci masivního množství agentů. Druhý zmíněný je implementován v jazyku Java a je určen pro široké uplatnění. Umožňuje využívat všechny nativní možnosti jazyka Java a je možné do něj i integrovat knihovny třetích stran (tím využít jejich funkčnost). Repast Simphony má další podružené softwary (ReLogo, Flowchart), které usnadňují návrh, modelování a simulaci. ReLogo na rozdíl od Repast Java má již předpřipravené abstraktní třídy (Turtle, Patch, Observer) pro základní implementaci agentů. Pro vývoj se využívá jazyka Groovy2, ten by měl značně urychlit samotné kódování modelu. Dále existuje Repast Flowchart, který dále usnadňuje výstavbu modelu. Pro výstavbu modelu se používá vestavěný grafický editor, který umožňuje skládat agenta z grafických komponent (Property, Behavior, Task, Decision, Join, Loop, End).
3.1 Základní koncept frameworku Repast Simphony Všechny Repast softwary respektují stejné koncepty a vlastnosti. Tím je zjednodušeno používání celé platformy, případný přechod mezi platformami Repastu. Nejobecnějším konceptem je, že agenti jsou implementováni jako Objekty (pro Javu i C++ to jsou instance tříd). Stav agenta je reprezentován jeho vnitřními atributy a agentovo chování představují instanční metody. Například agent chodec v simulaci davu, může být implementován s atributy, jako je rychlost a směr. Metoda pohyb může pohnout chodcem v zadaném tiku o vektor odpovídající jeho směru a aktuální rychlosti.
1
Framework je dostupný na webové adrese: http://repast.sourceforge.net Groovy je objektově orientovaný programovací jazyk pro platformu Java. Jde o alternativu k programovacímu jazyku Java. Můžeme se na něj dívat jako na skriptovací jazyk pro javovskou platformu. Inspiraci čerpal z jazyků Python, Ruby, Perl a Smalltalk. [zdroj wikipedie] 2
25
Obrázek 7Příklad implementace agenta chodce. Zdroj: [5]
Simulace postupuje v čase pomocí plánovače (kalendáře událostí). Plánovač má interní frontu událostí, ze které se v každém kroku vybírají události a zároveň se provádějí. Konkrétně Repast HPC vlastní diskrétní kalendář událostí s konzervativní metodou synchronizace. Uživatel plánuje události na specifický „tik“, kde tik udává relativní pořadí, ve kterém se mají události provést. Například můžeme mít tvrzení, že událost A je naplánována na tik = 3 a událost B je naplánována na tik = 5. Z tohoto tvrzení a dřívějšího popisu tedy vyplývá, že se událost A provede dříve než událost B. Kontext je další pojem, který se ve frameworku používá k zapouzdření populace agentů. Jedno z implementačně hlídaných pravidel je, že každá instance kontextu může obsahovat pouze jedinou instanci každého agenta (nelze do Kontextu přidat stejný objekt dvakrát). Když jsou agenti vytvořeni, lze je přidat do Kontextu a pokud se jejich životní cyklus ukončí, lze je z Kontextu odebrat. Kontext je asociován s tzv. projekcí. Projekce předepisuje relační strukturu mezi agenty v Kontextu. Pro příklad můžeme uvést mřížkovou projekci (grid projection), která vkládá agenty do maticové struktury (typicky mřížka), kde každý agent zabírá nějakou buňku (buňka má navíc atribut udávající pozici buňky v maticové struktuře). Síťová projekce dovoluje agentům definovat síť, ve které může uchovávat informace o relacích mezi agenty. Další vlastností Kontextu je, že po přidání agenta do Kontextu se agent automaticky stává i součástí všech projekcí, které jsou s Kontextem asociovány. Příklad: Kontext je asociován se síťovou projekcí, tedy po přidání agenta do kontextu se agent stane novým vrcholem v síťové projekci. Následně má možnost si dynamicky, dle svého chování, dále vytvářet spojení k ostatním agentům. Repast disponuje 5 základními projekcemi (z toho 3 jsou implementované i v HPC). Dostupné projekce jsou:
ContinousSpace / projekce souvislého (reálného) prostoru (HPC)
Geography / geografická projekce
Grid / maticová projekce (HPC)
Network / síťová projekce (HPC)
PhysicsSpace / fyzikální projekce
26
Simulace v Repast frameworku je složena z množiny agentů, jednoho nebo více kontextů, které obsahují zmíněnou množinu agentů a žádné nebo více projekcí. Kontexty se mohou hierarchicky větvit a tím vytvářet různé podmnožiny projekcí a agentů. Uživatel je zodpovědný za psaní kódu agenta a framework poskytuje implementace kontextů a projekcí. Každý simulační výpočet typicky vybírá z kalendáře událostí následující událost, která byla uživatelem naplánována pro provedení. Událost vyvolá specifikované chování agenta, který je zařazen aspoň do jednoho kontextu a užívá žádnou nebo více projekcí. Například každou simulační iteraci může každý agent vytvořit nové spojení s agenty, kteří jsou dostupní v jeho lokálním okolí (okolní buňky) v maticové projekci.
3.2 Repast Simphony 2 Je inovovaný framework založený na koncepci původního frameworku Repast. V první finální verzi byl uvolněn 5. března 2012 a je to interaktivní, multi – platformní modelovací systém založený na jazyku Java. Podporuje vývoj extrémně flexibilních agentově orientovaných modelů. Software je určen pro simulace na stolních počítačích nebo malých výpočetních clustrech. Repast Simphony podporuje vývoj modelů několika různými formami zahrnující prototypování modelů pomocí nadstavby ReLogo nebo využití grafického modelování ve vizuálním prostředí pomocí Flowcharts. Pro nejflexibilnější modely je k dispozici vývoj přímo v jazyce Java nebo Groovy. Všechny tyto přístupy jsou úzce propojeny vývojovým prostředím Eclipse IDE, který je dodáván již předinstalovaný a přednastavený v základním instalačním balíčku Repast Simphony 2.
Obrázek 8Běhové prostředí Repast Simphony s 2D a 3D pohledem. Zdroj: [5].
27
Běhové prostředí Repast Simphony poskytuje GUI aplikaci, která je připravena pro vizuální konfiguraci modelu a jeho spouštění. Běhové prostředí poskytuje:
GUI aplikaci pro vizuální nastavení prostředí a provádění operací s modelem
Integrované 2D, 3D a mnoho dalších vizualizačních pohledů, které mohou zobrazovat aktuální stavové informace modelu
Automatické připojení na zdroje dat různého typu (XML, CSV)
Automatické propojení s externími programy třetích stran pro statistické zpracování, analýzu a vizualizaci výsledků modelu
Distribuování modelu i s běhovým prostředím jako spustitelné aplikace, pro další osoby, které mohou s modelem dále experimentovat.
Repast Simphony byl úspěšně využit v mnoha aplikačních doménách jako například sociální vědy, podpora prodeje produktů, zásobovací řetězce, model budoucí vodní infrastruktury a mnoho dalších. Jednou z dalších mnohých výhod je, že k této verzi frameworku je dostupné velké množství již hotových modelů. Například model CA, Game of Life, Sugarscape a mnoho dalších. Výhodou je i částečná kompatibilita s modely, které byly vytvořené v dřívějších verzích frameworku a lze je konvertovat a využít i ve stávající verzi frameworku.
3.2.1 Repast Java Repast Java je pouze označení, ale ve své podstatě je to základní implementace Repast Simphony 2. Je to tedy nejnižší a nejflexibilnější přístup pro modelování a vývoj vlastních modelů. Na této úrovni může být agentem instance každé obyčejné třídy. To přináší obrovské možnosti implementace. Na druhou stranu je to i úskalí, protože není připravený žádný prototyp agenta a agent musí být vystavěn od samého základu. Základní množství dostupných knihoven je velké a již v základu nám framework nabízí pomocné implementace pro nativní použití genetických algoritmů (framework JGAP3), neuronových sítí (framework Joone4), anebo regresní analýzy (framework OpenForecast5). Navíc je možné využívat vlastních knihoven nebo knihoven třetích stran, pro dosažení požadované funkcionality.
3
JGAP, Java genetic algorithms package je rozšíření pro aplikaci genetických algoritmů v Javě. Informace a celá knihovna je dostupná na adrese: http://jgap.sourceforge.net/ 4 Java Object Oriented Neural Engine (joone) je nadstavba pro realizaci neuronových sítí. Knihovna je dostupná na adrese: http://www.jooneworld.com/ 5 OpenForecast je rozšíření pro použití regresní analýzy. Knihovna je dostupná na adrese: http://openforecast.sourceforge.net/
28
3.2.2 ReLogo Rozšíření ReLogo je nadstavba nad Repast Java. V základu poskytuje předem připravené abstraktní třídy pro snadnější implementaci a prototypování agentů. ReLogo je dostupné, ve vývojovém prostředí dodávaným v instalačním balíčku, při založení ReLogo projektu. Vývojáři poskytují také možnost konvertovat starší modely typu NetLogo pomocí průvodce dostupného v nabídce vývojového prostředí. ReLogo poskytuje tyto typy předpřipravených tříd, které pocházejí z původního programovacího jazyka Logo:
Turtles / Želvy – jsou mobilní agenti
Patches / Místa – jsou fixní agenti
Links / Propojení – spojují želvy, aby vytvářeli sítě
Observer / Pozorovatel – poskytuje celkové řízení modelu
Logo modely jsou realizovány vždy ve dvou – dimenzionálním spojitém prostoru. Např. Želvy mohou být lokalizovány na jakémkoliv místě v prostoru, zato Místa se mohou vyskytovat pouze na diskrétních celočíselných lokacích a to pouze po jednom na dané lokaci. Modely fungují tak, že Želvy představují hlavní agenty, kteří mají chování a provádějí interakce mezi sebou a Místy.
3.2.3 Repast Flowchart Repast flowchart je další rozšíření, které umožňuje vizuální tvorbu agenta v grafickém prostředí pomocí skládání a propojování grafických komponent (ukázka na obrázku 9). Grafické prostředí je založené na frameworku Flow4J6 od vývojářů prostředí Eclipse. Prostředí je schopné na základě definic v grafickém prostředí generovat na pozadí Java nebo Groovy kód. Ten je dále použit v běhovém prostředí. Proto jsou ve vývojovém prostředí vždy dva soubory a to například Chodec.agent (soubory s příponou agent je možné upravovat právě pomocí editoru flowcharts) a automaticky generovaný soubor Chodec.groovy, kde se při uložení flowchart souboru automaticky vygeneruje příslušný kód.
6
Framework je dostupný na webové adrese http://flow4jeclipse.sourceforge.net
29
Obrázek 9Ukázka prostředí flowchart. Zdroj: [5].
3.3 Repast HPC Repast HPC (High Performance Computing) je druhá implementace Repast Simphony frameworku (je založen na stejných principech a vývojovém konceptu jako Repast Simphony). Je určen pro vysoce náročné distribuované výpočty a paralelní operace. Software je implementován v programovacím jazyce C++ s využitím MPI (Message Passing Interface), rozhraní pro paralelní operace. Výhodou je jeho možné rozšíření pomocí boost7 knihovny. MPI je standardizované
7
Knihovna boost je dostupná z adresy: http://boost.org
30
rozhraní pro předávání zpráv a lze ho tedy jednoduše rozšířit i jinými nástroji. Typickými kandidáty pro Repast HPC jsou simulační modely s masivními lokálními interakcemi a velkým počtem agentů. Repast HPC momentálně podporuje pouze tři výše zmíněné projekce a to: Grid, ContinousSpace a Network. Jak již bylo řečeno v úvodu, Repast HPC disponuje dynamickým diskrétním kalendářem událostí, který využívá konzervativní metody synchronizace.
31
4 LANTIME Je heuristicky algoritmus, který je určen pro plánování nejrychlejších tras pro distribuční automobily, přitom zohledňuje proměnlivost průměrné rychlosti na silnicích, podle toho v jaký čas automobil vyjede. Variabilita je způsobena kongescí, které jsou typicky největší během ranní a večerní dopravní špičky. Algoritmus se používá pro obsazování flotily distribučních automobilů na jihozápadě Spojeného Království. Konvenční metody, které nepočítají se změnou rychlosti v průběhu času, když plánují, můžou vést k tomu, že některé cesty zaberou příliš dlouho dobu na přejetí. Výsledky ukazují, že použitím algoritmu LANTIME vede k úspoře vylučování oxidu uhličitého okolo 7%.[6]
4.1 Úvod Algoritmy pro plánování tras jsou většinou vyvíjeny pro dopravní sítě, které berou průměrnou rychlost vozidla jako konstantní pro jednotlivé úseky sítě. Někdy jsou různé průměrné rychlosti použity pro různé typy silnic nebo pro cesty v částech nějakého území, ale často průměrná rychlost není měněna v průběhu plánování. V praxi plynulost dopravy může podléhat přetížení, které vede ke snížení průměrné rychlosti v jednotlivých částech dne nebo noci. Průměrná rychlost velmi často také závisí na dni v týdnu, ročním období či jiném vlivu, jako třeba podnebí.[6] Nyní máme k dispozici o mnoho více dopravních informací, které umožňují plánovat cesty s přihlédnutím ke kongesci, které jsou předvídatelné z historických údajů. Tento přístup nepočítá s možností vzniku neočekávané situace, která může způsobit kongesci, jako je například dopravní nehoda, ale běžnou kongesci způsobenou objemem dopravy nebo dlouhotrvající prací na silnici mohou být předvídatelné ze získaných dat z dřívějška.[6] Tato data mohou být použita k vytvoření Road Timetable8, který ukazuje nejkratší dobu mezi zákazníky v různých časech zahájení jízdy. Nejkratší cesta může být v některých případech změněna, v závislosti na kongesci vznikající v průběhu dne.[6] Tato práce popisuje plánovací algoritmus pro distribuční vozy zvaný „LANTIME“, který je schopný přijímat data z Road Timetable a vykonstruuje množinu cest pro distribuční vozy s minimálním celkovým časem potřebným pro doručení zboží z depa k množině zákazníkům s ohledem na některá omezení. Možná omezení zahrnují:
8
kapacitu vozidla,
doby přípustné pro každého řidiče a vozidlo
nebo časové okno, kdy má být zboží doručeno zákazníkovi.[6]
TM
Road Timetable (silniční harmonogram) je obchodní značkou, proto v textu nebude překládáno
32
4.2 Road Timetable Většina operátorů komerčních vozidel rozpozná (např. z analýzy tachografu), že rychlost na silnici se mění individuálně z hodiny na hodinu, podle dne v týdnu a ročního období. Studie provedená pro jednoho velkého britského komerčního operátora, provedena pomocí analýzy tachometrů a s pomocí stopovacího systému zjistila, že na jednom úseku dálnice v Severní Anglii se rychlost vozidla měnila v jednom týdnu od 5 mph(v pondělí 08.45) do 55 mph (ve středu v 20.15). Avšak když se porovnaly uložené hodnoty rychlostí za období deseti týdnů, proměnlivost rychlosti v ten samy čas byla s rozdílem menším než 5%. Z toho vyplývá, že rychlost můžeme pro každou silnici v kterýkoliv čas předpovědět. Z toho můžeme také dojít k závěru, že čím větší je odchylka rychlosti vozidel na silnicích během dne, tím větší je nepřesnost plánovacích systémů, které využívají k výpočtu doby trasy rychlost vozidla podle kategorie silnice.[7] Jednou překážkou k zahrnutí časově závislé doby trasy v minulosti byla nedostupnost dat. Ovšem takováto data nyní začínají být dostupná prostřednictvím několika dopravních monitorovacích systémů. Buď mohou být nainstalované statické radary k monitorování rychlosti vozidel na různých místech dopravní sítě, anebo využitím alternativních systémů, které monitorují pozici a rychlost vozidla, které jsou umístěny ve sledovacích zařízeních. Společnost ITIS FloatingVehicle Data poskytuje monitorovací systém nad národní dopravní sítí. Tento systém může být použit pro aktualizaci času trasy založené na současných dopravních podmínkách, ale také poskytuje zaznamenaná dřívější data, takže dopravní podmínky mohou být rozřazeny podle částí dne, dne v týdnu a ročního období. Tato data jsou použita k vytvoření informací pro časově závislé doby tras na dopravní síti. Těmto informacím říkáme Road Timetable.[7]
4.2.1 Vytvoření Road Timetable Road Timetable obsahuje obrovské množství dat. Z každého počátečního místa dopravní sítě je určen minimální čas a nejrychlejší čas do každého cílového místa na dopravní síti, pro různou počáteční dobu zahájení trasy. [7] Pro každou hranu v dopravní síti potřebujeme potřebná data pro patřičný čas, ve kterém chceme hranu přejíždět. V praxi bude čas potřebný na přejetí hrany různý pro různé typy vozidel. Proto musíme v datech upravit rychlosti, které přesahují maximální přípustnou rychlost požadovaného typu vozidel. I když je čas spojitou veličinou, většina dopravních informací je udávána v časových úsecích. Proto čas potřebný na přejetí hrany je krokovou funkcí v průběhu dne. Tato časově závislá data můžeme uložit buď jako rychlosti nebo jako časy potřebné na přejetí hrany.[7]
4.2.1.1 Nejrychlejší cesta Výpočet nejrychlejší cesty a její doby může být efektivně uděláno pomocí Dijkstrova algoritmu[8] využívající časově závislé doby cest. Některé adaptace Dijkstrova algoritmu můžete nalézt ve zdroji [9],[7]. V případech, kdy počátky a cíle cest jsou známy předem, může být síť konstruována tak, že všechny počátky a cíle odpovídají uzlům sítě. Pokud není síť 33
příliš velká, můžeme vypočítat pro všechny páry počátků a cílů Road Timetable na standardním PC v rozumném čase. Nejkratší cesta v časově závislé dopravní síti závisí na počátečním čase jízdy a může se měnit, i když je počáteční čas v jednom stejném časovém úseku. To protože příjezdy do vrcholů mezi počátkem a cílem mohou být v různých časových intervalech. Protože nejsme schopní získat z Road Timetable nejkratší cestu pro jakýkoliv počáteční čas, musíme si pomoc pomocí aproximace a uložit nejkratší cesty, pro které jejich počáteční čas spadá do předem určeného časového intervalu.[7] V kapitole 5 se zaměřím na efektivní výpočet nejkratší cesty pro rozsáhlé dopravní sítě, které obecný Dijkstrův algoritmus není schopen spočítat v přijatelném čase.
4.2.1.2 Časové intervaly ITIS FloatingVehicle Data poskytují reálná data rychlostí každého úseku v dopravní síti v intervalu patnácti minut. Avšak hodnoty sousedících intervalů se příliš nemění, například pozdě v noci a brzy ráno, kdy jsou silnice většinou prázdné. Porovnáním průměrné rychlosti po sobě jdoucích časových úseků je možné zredukovat na přijatelné množství těchto úseků. Pro můj model bylo rozhodnuto použití 15 časových intervalů, které pokryjí 24 hodin. Nejmenší má 30 minut v průběhu dopravní špičky a nejširší má 8 hodin, který pokrývá noční provoz. Časové úseky jsou znázorněné na obrázku 10.[7]
Obrázek 10 Časové intervaly. Zdroj: [7].
4.2.1.3 Vlastnost First-In First-Out Pokud používáme časově závislá data, je třeba zvážit, zda funkce pro určení doby jízdy má vlastnost konzistence FIFO. To znamená, pokud vozidlo cestuje z vrcholu i* do vrcholu j*, kde oba vrcholy náleží jedné dopravní síti, začínaje v jakýkoliv čas T z vrcholu i*, pak dorazí do vrcholu j* později, než kterékoliv vozidlo stejného typu, které vyjelo z vrcholu i* dříve než v čase T. Tato vlastnost znázorňuje to samé, jako když po silnici jedou auta za sebou se stejnou rychlostí, pak dosáhnou cíle ve stejném pořadí, v jakém vyjely.[7] Předpokládejme, že chceme najít čas příjezdu do vrcholu j, aj, poté co cestoval z vrcholu i do vrcholu j přes jednu hranu ij, s počátečním časem jízdy si. Nechť čas potřebný na přejetí z i do j je uložen jakoTk v databázi, když tk≤ t
úseků. Vzdálenost z vrcholu i do vrcholu j je dij. Čas příjezdu do vrcholu j, aj, spočítáme podle procedury, kterou znázorňuje pseudokód na obr. 11.[7]
Obrázek 11 Pseudokód výpočtu času příjezdu. Zdroj: [7].
Například předpokládejme, že hrana ij je dlouhá 2km a máme dva časové úseky. První je od 8.00 do 9.00 hodin, ve kterém platí, že čas potřebný na přejetí této hrany je T1 = 4 minuty. Druhý časový úsek je od 9.00 do 10.00 a čas potřebný na přejetí je T2 = 2 minuty. Pokud čas výjezdu je si≤ 8.56, pak čas na konci hrany bude si + 4. Avšak pokud čas výjezdu bude 8.56 <si≤ 9.00, pak počítáme podle kódu, ve větvi else na obrázku 11. Pokud čas výjezdu si = 8.58, pak d:=2km, t:=8.58 a v1 = 0.5km/min. Přepočítáním proměnných dostaneme:
d := 2 - 0,5(9.00 - 8.58) = 1 km,
time:=9.00,
v2 = 2/2 = 1 km/min,
t‘:= 9.00+1/1=9.01,
k :=2,
aj:= 9.01.[7]
4.3 Formulace a návrh algoritmu Jedná se o konvenční rozvozní problém s časovými okny, kde rychlosti každé hrany sítě nejsou proměnné v čase. Bude zde popsána formulace, která může být rozšířena o více praktických požadavků a rutin nebo proměnné informace, jako jsou například doby trvání trasy.[6] Mějme N – množina zákazníků, K – množina vozidel, s(i) – doba obsluhy zákazníka, w(i) – požadová poptávka, [ei, li] – časové okno.
35
Množina K reprezentuje homogenní flotilu vozidel. Každé vozidlo k z K má kapacitu W, nástupní čas t a maximální pracovní dobu D. Dopravní časy mezi lokacemi jsou pro všechny známy a pevně definovány jako c(i, j), kde {i, j}⊂ N U{0}, kde podle konvence 0 reprezentuje depo. Ohodnocení hrany je v jednotkách času.[6] Pro každé vozidlo k, definujeme cestu lokací = ,…, , které mají být obslouženy, kde ∈ pro = 1, … , −1 a a jsou 0. Takto je definovaná trasa začínající a končí v depu. reprezentuje počet zastávek na kompletní cestě, včetně depa, pro vozidlo k.[6] Čas začátku obsluhy zákazníka ∈ je označen jako a(i) a čekací doba před obsluhou je označena jako b(i). Počáteční čas je definovaný jako maximum z času opuštění z předchozí zastávky plus doba cesty a z počátku časového okna ei. Dle konvencí a(0) = t a s(0) =0. Doba čekání je závislá na počátečním čase a začátku časového okna.[6] =
(
,
(1)
)
(2)
=
Jediné omezení, které je použito přímo na každého zákazníka je to, že obsluha začíná v daném časovém okně. To je časové okno na začátku obsluhy a ne po dokončení.[6] ≤ ( ) ≤ ,∀ ∈
(3)
Čas potřebný na vykonání práce pro každou cestu musí být menší než pracovní doba D. Ta zahrnuje čas přesunu, obslužný čas a čekací doba.[6] ∑
(
)+∑
,
(
)+∑
≤
∀ ∈
(4)
Omezení (4) zajistí, že se vozidlo vrátí zpět do depa včas. Rovnice (5) říká, že je cesta míst, která mají být obsloužena vozidlem k, ze které jsou vymazány zastávky v depu.[6] = ⋃
∈
\{
,
}∀ ∈
(5)
=
(6)
Rovnost omezení (6) zajišťuje, že všichni zákazníci N jsou řešeni individuální množinou zákazníku .[6] ∑ =1 (
)≤
∀ ∈
(7)
36
Omezení (7) zabraňuje přečerpání kapacity vozidla. Účelová funkce (8), platí pouze pro verzi s flotilou stejných aut, kde se minimalizují náklady na cestu pro všechny vozidla.[6] ∑
∈
∑
(
,
(8)
)
Počáteční řešení najdeme pomocí paralelního vkládacího algoritmu obsaženého v [8]. Z tohoto počátečního řešení, pomocí tabu search algoritmu, najdeme řešení v sousedství. Vkládací algoritmus musí zajistit, aby řešení bylo v souladu se všemi omezeními a má pět kroků dle [6]: 1) Vložit do cesty každého vozidla nejvzdálenější zakázku od depa (s ohledem na vkládací kritéria) 2) Ohodnotit každou zbývající zakázku tak, jakoby vozidlo, které ji bude vyřizovat, jelo přímo z depa k ní bez žádné další zakázky po cestě. 3) Najít každé zbývající zakázce umístění do takového vozidla, aby bylo nejlepší. 4) Udělat nejlepší vložení na základě úsporných kritérií. 5) Pokud jsou všechny trasy plně obsazené nebo zakázky přidělené, pak ukončit, jinak pokračovat od bodu 3. Počáteční řešení bude nyní vylepšeno použitím tabu search algoritmu. Algoritmus popsaný níže využívá čtyři možné sousedské operace, znázorněné na obrázku 12 dle [6]:
CROSS Exchange
insertion/removal
one exchange
swap
37
Obrázek 12 Čtyři druhy přesunu v sousedství. Zdroj: [6].
Insertion/removal, one exchange a swap operátory můžou být považovány za speciální případy adaptovaného Cross Exchange operátoru. Ve všech těchto přesunech, když se přesunuje množina zakázek společně se zjišťuje, zda je lepší obrátit pořadí těchto zakázek.[6] Algoritmus náhodně vybere, které okolí prozkoumá v každé úrovní, podle předem zadaných pravděpodobností.[6] Tabu seznam není pevný, ale proměnný, jak uvádí [10]. Přesun přidaný do tabu seznamu v čase zustává omezen, dokud není + , kde je nahodné číslo z intervalu [ , ]. Toto řešení eliminuje pravděpodobnost vzniku cyklace mezi řešeními. Standardní aspirační kritérium přepíše omezení naznačené tabu listem, pokud vede k novému nejlepšímu řešení. Struktura dlouhodobé paměti je využita k diverzifikaci hledání do nových míst. Cíl tabu search má další komponentu k reprezentaci nákladů dlouhodobé paměti M(xtrial) navrhovaného kroku, který vede k řešení xtrial.[6] =
(
) (
(9)
)
Faktor dlouhodobé paměti vyznačuje, kolikrát každá zakázka, která je zapojena do přesunu vedoucí ke zkušebnímu řešení xtrial., byla zapojena v předchozích dokončených přesunech. Struktura paměti udržující záznam kolikrát 38
zakázka byla zapojena v dokončeném přesunu (dále jen tally). Pro přesun tykající se pouze jedné zakázky je přičtena do tally hodnota 1, pro přesun zahrnující více než jednu zakázku je všem zakázkám v tomto přesunu přidána do tally hodnota 1/(počet zahrnutých zakázek).[6] Složka M(xtrial) pro rovnici (9) se spočítá použitím součtu počtu výskytu zakázek (tally_count), které byly zahrnuty v přesunu, vyděleny počtem zahrnutých zakázek v přesunu, pak je tato hodnota vydělena celkovým počtem iterací. β je konstanta použita ke kontrole efektu, který má dlouhodobá paměť na hodnotu funkce.[6] (
)={
∑
č ý
ý č
á
+ 1}
(10)
í
Nákladová funkce paměti je nastavena na hodnotu 1 když posoudí, že možně řešení splňuje aspirační kriteria.[6] Cílem tabu search je nalézt takové řešení, které vede k minimalizaci nákladu na vyhledání. Vyhledávací náklady zahrnují původní účelovou funkci f(x), náklady paměti M(x) a funkci P(x), která měří neproveditelnost řešení x.[6] ( ) ( )+
(11)
( )
Parametr α se mění dynamicky v průběhu vyhledávání. Na začátku inicializujeme α na 1. Každou ξ iteraci nastavíme α=2α, pokud všechny předchozí ξ iterace byly neproveditelné, a α=α/2, pokud všechny předchozí operace byly proveditelné.[6] Ve výrazu (11) se náklady řešení f(x) spočítají pomocí rovnice (8) a paměťové náklady se spočítají pomocí (10). Penalizační náklady P(x) udávají, kolik času navíc je potřebné pro dokončení řešení (časové okno pro každou zakázku a pracovní doba navíc pro každé vozidlo).[6]
4.3.1 Souhrn celého algoritmu Krok 1: Inicializace
Vygenerování počátečního řešení, xnow
Překopírování počátečního řešení do dočasně nejlepšího možného řešení, x* = xnow
Vyprázdnit tabu seznam a nastavit hodnoty dlouhodobé paměti defaultně na nulu
Krok 2: Výběr sousedství a ukončení IF je splněna podmínka ukončení THEN RETURN x* ELSE Náhodně vybrat sousedství N k použití v této iteraci. END IF 39
KROK 3: Výběr Náhodně generuj xtrial z N(xnow) První hodnotu v sousedství přiřadíme do nejlepšího řešení xbest = xtrial IF P(xtrial) = 0 and f(xtrial) < f(x*) f(xbest) = f(xtrial) P(xbest) = P(xtrial) xbest = xtrial Jdi na krok 4 ELSE IF přesun z xnow do xtrial nenastavuj tabuTHEN IF M(xtrial)f(xtrial)+αP(xtrial) < M(xnow)f(xnow)+αP(xnow) THEN f(xbest) = f(xtrial) P(xbest) = P(xtrial) xbest = xtrial Pokračuj krokem 4 ELSE IF (xtrial)f(xtrial)+αP(xtrial)<M(xbest)f(xbest)+αP(xbest) THEN M(xbest) = M(xtrial) f(xbest) = f(xtrial) P(xbest) = P(xtrial) xbest=xtrial END IF END IF END IF Pokračuj krokem 3, dokud nebude prohledané celé sousedství N(xnow). Krok 4: Aktualizace xnow = xbest Aktualizovat paměťovou tabulku a tabu seznam, zvýšit počet iterací. IF P(xbest) = 0 and f(xnow)
40
5 Nejrychlejší cesta pomocí dálniční hierarchie Hledání nejrychlejší cesty v dopravních sítích je pro dnešní aplikace, zabývající se tímto problémem, běžná věc. V principu můžeme použít Dijkstrův algoritmus, ale pro obrovské dopravní sítě by byl příliš pomalý. Proto je veliký zájem o techniky, které dokáží tyto výpočty urychlit. Komerční systémy využívají k urychlení hledání informace o kategoriích silnic. V této kapitole je představena nová technika, která urychlí vyhledávání nejrychlejších cest. Tato technika dokáže automaticky spočítat dálniční hierarchie9 dopravní sítě. Jako první tato technika dokázala přepočítat dopravní síť celého kontinentu v reálném čase, tj. několika tisíckrát rychleji než Dijkstrův algoritmus.[11]
5.1 Předpoklady V následujících podkapitolách jsou uvedeny základní předpoklady, které vedou k úspěšnému sestrojení dálničních hierarchií.
5.1.1 Grafy a cesty Očekáváme orientovaný graf G=(V, E) s n vrcholy a m hran (u, v) s kladnými hodnotami w(u, v), jako vstupní data. V tomto grafu se nesmějí objevit žádné smyčky, paralelní hrany nebo hrany s nulovou váhou. Délka w(P) cesty P je součtem délek hran, které patří do této cesty P. P* = (s, …, t)10je nejkratší11 cestou, pokud neexistuje žádná jiná cesta P‘ z počátečního vrcholu s (source) do koncového vrcholut (target), pro kterou platí w(P‘) < w(P*). Vzdálenost d(s, t) mezi s a t je délka nejkratší cesty z s do t. Pokud P = (s,…, s‘,u1,u2,…,uk,t‘,…,t) je cesta z s do t, pak P|s‘→t‘ = (s‘,u1,u2,…,uk,t‘) označuje podcestu cesty P z s‘ do t‘.[12]
Obrázek 13 Neorientovaný graf s cestou a podcestou. Zdroj:[12].
5.1.2 Dijkstrův algoritmus Dijkstrův algoritmus může být použit k řešení nejkratší cesty z jednoho výchozího vrcholu. Například k vypočítání nejkratších cest z výchozího vrcholu
9
Dálniční hierarchie - z angl. Highway hierarchies s – počáteční vrchol z anglického „source“, t – cílový vrchol z anglického target. 11 Nejkratší cesta je nejrychlejší cesta, pokud ohodnocení hran je v jednotkách času. 10
41
s do všech ostatních vrcholů grafu. Tento algoritmus najdete snad v jakékoliv základní literatuře o algoritmech. Například uvedu [9]. V každé literatuře je popsaný trochu jinak, proto si zde upřesníme terminologii, která bude používání v následujících podkapitolách. Začněme s počátečním vrcholem s, který je kořenem, neboť Dijkstrův algoritmus se rozrůstá do stromu nejkratších cest, který obsahuje nejkratší cesty z vrcholu s do jakéhokoliv vrcholu v grafu. Během tohoto procesu každý vrchol grafu je buď „nedosažený“, „dosažený“ nebo „probraný12“ dle
[11]:
Vrchol, který patří do stromu, je „probraný“. Pokud je vrchol u „probraný“, nejkratší cesta P* z s do u byla nalezena a její vzdálenost jed(s, u) = w(P*).
Vrchol, který sousedí s probraným vrcholem je „dosažený“. Pokud vrchol u je „dosažený“, cesta P z s do u, která nemusí být nejkratší je nalezena a její odhadovaná vzdálenost je δ(u) = w(P).
Vrcholy, které nejsou „dosažené“, jsou „nedosažené“. Vrcholy, které jsou „dosaženy“, ale nejsou „probrané“, spravovány v prioritní frontě, která podporuje operace dle [12]:
jsou
Vlož – vloží element do prioritní fronty. VyberNejmenší – vrátí element s nejmenším klíčem a odstraní z prioritní fronty. SnižKlíč – nastaví klíč elementu, který už náleží prioritní frontě, na novou hodnotu, která je menší než původní. Klíčem vrcholu v prioritní frontě je odhadovaná vzdálenost. Na začátku je vrchol s vložen do prioritní fronty s hodnotou klíčem 0. Tím pádem je s „dosažený“ a ostatní zbylé vrcholy jsou „nedosažené“. Dokud prioritní fronta není prázdná, vybíráme z prioritní fronty prvky s nejmenším klíčem a přidáváme je do stromu nejkratších cest, čímž se stanou „probranými“. Následně jsou hrany z prvku u „uvolněné“ dle [12]: Pokud hrana (u, v) vede k „nedosaženému“ vrcholu v, pak je v přidaný do prioritní fronty a stane se „dosaženým“. Pokud hrana (u, v) vede k „dosaženému“, ale ne k „probranému“ vrcholu v, je hodnota klíče vrcholu v snížena, jestliže vzdálenost z vrcholu s do vrcholu v přes vrchol u je menší, než původní hodnota klíče. Pokud hrana (u, v) vede k „probranému“ vrcholu v, pak je ignorována.
12
názvy „nedosažený“, „dosažený“ a „probraný“ převzaty ze zdroje [21]
42
Na obrázku 14 je schematicky znázorněný prohledávací prostor Dijkstrova algoritmu.
Obrázek 14 Prohledávací prostor Dijkstrova algoritmu. Zdroj: [12].
Dvojsměrná (bidirectional) verze Dijkstrova algoritmu může být použita k nalezení nejkratší cesty z vrcholu s do daného vrcholu t. Zahájíme dvojité paralelní hledání. Jedno hledání z výchozího vrcholu s v originální grafu G=(V, E), také zvaný jako „dopředný“ graf s označením jako G→=(V, E→). Druhé hledání z cílového vrcholu t pomocí „zpětného“ grafu G←=(V, E←), kde E← = {(v,u) | (u,v) naleží E}.Jakmile se oboje prohledávání setkají, je nejkratší cesta z vrcholu s do vrcholu t nalezena.[11] Prohledávací prostor dvojsměrného Dijkstrova algoritmu je na obrázku 15.
Obrázek 15 Dvojsměrný Dijkstrův algoritmus. Zdroj: [12].
5.2 Obecný popis techniky 5.2.1 Lokalita Nejprve upravíme pravidlo, které rozhoduje, který element Dijkstrův algoritmus vyjme z prioritní fronty, pokud se v ní nachází více prvků s nejmenším klíčem. Poté během prohledávání Dijkstrova algoritmu z daného vrcholu jsou všechny vrcholy „probrány“ v pevném pořadí. Dijkstrovo pořadí (rank)rs(v) vrcholu v je pořadí vrcholu v s ohledem na toto řazení. Vrchol s má Dijkstrovo pořadí rs(s)=0, nejbližší sousední v1 vrcholu s má Dijkstrovo pořadí rs(v1)=1 atd. Pro daný počáteční vrchol s určíme vzdálenost H-nejbližšího vrcholu z vrcholu s, jako dH(s). Například dH(s) = d(s,v), kde rs(v)=H. Pak sousedství NH(s) je dáno, jako ( ) = { | ( , ) ≤ ( )}.[12] Na obrázku 16 je znázorněn graf s vrcholy, které jsou očíslovány Dijkstrovým pořadím s vyznačeným sousedstvím vrcholu s o velikosti 5. 43
Obrázek 16 Sousedství vrcholu s o velikosti 5. Zdroj:[12].
5.2.2 Dálniční hierarchie Pro zadaný parametr H definujeme dálniční síť G1=(V1,E1) z originálního grafu G jako množinu hran E1, kde hrana (u,v) náležící E patří do E1, jestliže a právě tehdy, pokud její vrcholy s, t náleží množině vrcholů V takové, že hrana (u,v) patří do podcesty (s,…,u,v,…,t) z s do t s vlastností, že v nepatří do N→H(s) a u nepatří do N←H(t). Množina V1 je maximální podmnožina V grafu G1, která obsahuje neizolované vrcholy. Na obrázku 17 je znázorněna tato definice.
Obrázek 17 Částečná nejkratší cesta. Zdroj: [12].
5.3 Konstrukce Začínáme s prázdnou množinou dálničních hran E1. Pro každý počáteční vrchol sítě s0 se provedou dvě fáze. Dopředná konstrukce stromu částečných nejkratších cest B a zpětné ověření stromu B. Konstrukce se provede pomocí prohledávání Dijkstrovým algoritmem z vrcholu s0. Během ověřovací fáze jsou procházeny cesty z listů stromu B do kořenu s0 a pro každou hranu v této cestě se rozhodne, zda ji přidat do množiny hranE1 nebo ne. Rozhodující část je specifikace ukončovacího kritéria pro Dijkstrův algoritmus, aby se omezil jen na „lokální hledání“.[12]
5.3.1 Fáze 1 – Konstrukce stromu částečných cest Zahájíme hledání podle Dijkstrova algoritmu z počátečního vrcholu s0. Během hledání je každý z dosažených vrcholů buď v „aktivním“ nebo „pasivním“ stavu. Počáteční vrchol s0 je „aktivní“. Každý vrchol, který je „dosažen“ poprvé a každý vrchol, kterému je snížena hodnota klíče, zdědí stav z jeho rodiče ve stromu nejkratších cest B. Když je vrchol p „probraný“ a ukončovací kritérium je kompletně splněno, stav vrcholu p je nastaven na „pasivní“. Pokud nezbývá žádný 44
aktivní vrchol v prioritní frontě, pak je hledání ukončeno a růst stromu B zastaven.[12]
5.3.1.1 Ukončovací kritérium Pokud je vrchol p „probraný“ použitím v cestě P‘, jako je znázorněno na obrázku 18, je mu nastaven stav na pasivní, jestliže průnik sousedství s1 a p je menší než jedna, tj. |N→(s1)∩N←(p)|≤1.[12]
Obrázek 18 Ukončovací kritérium. Zdroj:[12].
5.3.1.2 Příklad fáze 1 Příklad první fáze konstrukce je znázorněný na obrázku č. 19. Ohodnocení hran je dáno délkou úsečky, která reprezentuje hranu. Velikost sousedství je H=3. Dijkstrův algoritmus je zahájený z počátečního vrcholu s0. Ukončovací kritérium se aplikuje třikrát. Zahrnuté vrcholy s1 a p a odpovídající sousedství jsou vyznačeny modře, resp. fialově a hnědě. V případě hnědé, průnik zahrnutých sousedství obsahuje přesně jeden element. V ostatních případech je průnik prázdný. Všechny hrany, které patří do stromu částečných nejkratších cest, jsou vyznačeny barevně. Hrany, které opouští aktivní vrcholy, jsou modré a hrany, které opouští vrcholy s pasivním stavem, jsou zelené.[12]
Obrázek 19 Konstrukce - fáze 1. Zdroj: [12].
45
5.3.2 Fáze 2 – Výběr dálničních hran Během fáze 2 přidáme všechny hrany (u, v), které leží na cestě (s0,…,u,v,…,t0) ve stromě částečných nejkratších cest B s vlastností, že vrchol v neleží v dopředném sousedství N→(s0) a vrcholu neleží ve zpětném sousedství N←(t0), kde t0 je list stromu B.[12]
Obrázek 20 Konstrukce - fáze 2. Zdroj: [12].
Na obrázku 20 je znázorněn výsledek druhé fáze konstrukce. Strom částečných nejkratších cest vrcholu s0 má pět listů t0, které jsou označeny různými barvami. Červeně vyznačené hrany jsou přidány do E1.[12] Pro každý vrchol u ze stromu částečných nejkratších cest B definujeme jako Lu, množinu listů t0 stromu B, které jsou koncovými body cest (s0,…,u,…, t0). Dále má každý vrchol u definovaný atribut „slack“ ∆( ) = ( ( ) − ( , )). Pro list t0 máme Lt0 = {t0} a ∆(t0) = dH(t0). „Slack“ vnitřního vrcholu u může být spočítaný pomocí „slacků“ potomků Cu. ∆( ) = ∆ ( ),kde ∆ ( ) = ∆( ) − ( , ). [12]
5.3.2.1 Popis algoritmu „Slack“ ∆(t0) všech listů t0 stromu B nastavíme na dH(t0). Odhadované „slacky“ ∆( ) všech ostatní vrcholu u, ze stromu B, nastavíme na +∞. Frontu Q naplníme listy stromu B (v libovolném pořadí). Všechny elementy fronty Q jsou předány do procesu jeden po druhém, dokud není fronta prázdná. Když vybereme vrchol u z fronty Q, spočítáme ∆ ( ) = ∆( ) − ( , ), kde p je rodič vrcholu u ve stromě B. Když ∆ ( ) < 0, přidáme hranu (p, u) do množiny hranE1. Když ∆( ) = +∞ a vrchol p nepatří do N→(s0), pak přidáme p do fronty Q. Jestliže ∆ ( ) < ∆( ), nastavíme odhadovaný „slack“ ∆( ) na hodnotu ∆ ( ).[12]
46
Na obrázku 21 je příklad „slackové“ metody k realizaci fáze 2 konstrukce. Proces je znázorněn pouze pro část stromu. Jako předtím je ohodnocení hran dáno délkou úsečky představující hranu mezi vrcholy na obrázku. V zájmu přehlednosti jsou ohodnocení hran zaokrouhlena. “Slacky“ jsou vyznačeny ve vrcholech. Hrany, které jsou přidány do E1, jsou vyznačeny červeně, oproti tomu hrany, které nejsou přidány, jsou vyznačeny modře.[12]
Obrázek 21 Konstrukce – „Slacková“ metoda. Zdroj: [12].
5.3.3 Zrychlení konstrukce V optimálním případě velikost stromu částečných nejkratších cest B je ohraničen malým násobkem velikosti sousedství H. Avšak v méně vyvážených případech může strom nabývat větších rozměrů. S cílem vypořádat se s tímto problémem je představen pojem „maverick“. Vrchol s aktivním stavem se stane „maverickem“, pokud ( , ) > ∙ ( ), kde f je parametr. Jestliže jsou všechny vrcholy s aktivním stavem „maverickové“, hledání v pasivních vrcholech nepokračuje.[12] Parametr f nám umožní nastavit kompromis mezi časem konstrukce a časem na nalezení nejkratší cesty. Na obrázku 22 je znázornění precizní konstrukční metody (vlevo), tj. tak dlouho dokud je nějaký aktivní vrchol, hledání z pasivních vrcholů pokračuje. Oproti tomu je zrychlená konstrukční metoda pomocí „mavericku“ (vpravo).[12]
Obrázek 22 Porovnání konstrukčních metod. Zdroj: [12].
47
5.3.4 Kontrakce dálniční sítě Za účelem zjištění jádra grafu GL, použijeme zjednodušenou verzi algoritmu představeného v[14]. Odstraníme vrcholy se stupněm 1 (vždy stejného stupně, jako je úroveň L dálniční hierarchie) a jejich incidenční hrany, dokud nezbývají vrcholy mající stupeň nejméně stupně L+1. Musíme zohlednit, že odebrání takového vrcholu a jeho incidenčních hran, vede k redukci stupně sousedního vrcholu. Během tohoto procesu, spravujeme seznam, který obsahuje kořeny přiložených stromů. Poté, co je určeno jádro, každý z kořenů inicializuje procházení odpovídajícího stromu. Každý vrcholu stromu, vyjímaje kořen, vytvoří přímou zkratku ke kořenu, tj. orientovanou hranu (u, r), která má ohodnocení odpovídající délce již existující cesty z u do r, jako je znázorněno na obrázku 23.[12]
Obrázek 23 Dálniční síť a přiložený strom se zkratkami. Zdroj: [12].
Pro každý vrchol, který má stupeň L+1, ale nebyl přiřazen do řady, pak je procházena řada v libovolném směru, dokud nedojde na koncový bod (vrchol větší než stupeň L+1). Poté je řada procházena v opačném směru. Každý vrchol vytvoří zkratku do již známého koncového bodu. Poté, co je druhý koncový bod dosažen, řada je procházena v jiný čas. Každý vrchol vytvoří zkratku k druhému koncovému bodu. Dále je také vytvořena neorientovaná zkratka mezi těmito koncovými vrcholy. Také je nutné ošetřit vrcholy, které nemají výjezdy nebo vjezdy.[12] Výsledkem kontrakce dálniční sítě vznikne jádro grafu G’L, které může být použito jako vstupní graf pro další úroveň v konstrukční proceduře.
48
5.4 Nalezení nejkratší cesty Vyhledávání nejkratší cesty v dálniční hierarchii je modifikací dvojsměrného Dijkstrova algoritmu. Kromě vzdálenosti klíč každého vrcholu zahrnuje také úroveň a mezeru k hranici dalšího použitelného sousedství. Vyhledávání začíná v počátečním vrcholu s v úrovni 0. Nejprve je zahájeno lokální hledání v sousedství. Mezera k další hranici je nastavena na hodnotu sousedského rádiusu na úrovni 0. Jakmile je vrchol v „probraný“, získá hodnotu mezery z jeho rodiče u mínus délka hrany (u, v). Tak dlouho, dokud zůstáváme uvnitř současného sousedství, pokračujeme stejně. Naproti tomu, když hrana (u, v) překročí hranici sousedství, například délka hrany je větší než mezera, přepneme vyhledávání do vyšší úrovně. Vrchol se stane vstupním bodem na vyšší úroveň. Pokud je úroveň hrany (u, v) menší než nová úroveň prohledávání, není hrana použita. To je jedno ze dvou omezení, které způsobuje zrychlení v porovnání s Dijkstrovým algoritmem. Pokud je hrana použitelná, pak vrchol v převezme novou úroveň vyhledávání a mezeru k hranici sousedství vrcholu u na úrovni l, dokud je odpovídajícím vstupním bode k úrovni l.[11] Můžeme se setkat se speciálním případem vstupního bodu do úrovně l, který nepatří do jádra úrovně l. V tomto případě, než bude dosaženo jádro úrovně l, přiřadíme hodnotu mezery vrcholu u, jako vzdálenost k hranici sousedství na současné vyhledávací úrovni l. Než dosáhneme jádra, je hodnota mezery rovna nekonečnu. Druhým omezením, které vede k zrychlení je, že nepoužíváme hrany, jejíž koncový vrchol nepatří do jádra dálniční sítě úrovně l.[11]
Obrázek 24 Dálniční hierarchie. Zdroj: [12].
Znázornění dálniční hierarchie na obrázku 24 zobrazuje dvě úrovně. Úroveň 0 jsou šedé vrcholy. Červené vrcholy patří do jádra úrovně 1 a společně s modrými tvoří vrcholy úrovně 1. 49
5.4.1 Algoritmus výběru nejkratší cesty Používají se dvě prioritní fronty ⃗ a ⃐ . Jedna pro dopředné vyhledávání a ( )), kde jedna pro zpětné vyhledávání. Klíčem vrcholu u je trojice( ( ), ( ), ( ) je odhadovaná vzdálenost z vrcholu s (nebo t) do vrcholu u. ( ) je ( ) je mezera k hranici do dalšího aplikovaného vyhledávací úroveň a sousedství. Klíč ( , , ) je menší než jiný klíč ( ′, ′, ′), jestliže < ′ nebo < > ′ nebo < > < ′. Pseudokód je na obrázku 25.
Obrázek 25 Pseudokód vyhledávání nejkratší cesty. Zdroj: [11].
Více podrobností můžete nalézt v [11], [12] a [13].
50
6 Realizace modelu V následující kapitole popisuji, s jakými daty model pracuje, jak jsou uchovávány a co za problémy se vyskytlo při jejich zpracování.
6.1 Vstupní data Jako zdroje dat mi byly poskytnuty tři „csv“ soubory. První obsahoval informace o defaultních rychlostech (v km/h), podle úrovně vozovky a timeslotu13, jak je uvedeno v tabulce 1. Timeslot\Úroveň
1
2
3
4
5
1 2
83.1265 75.8461
54.5688 48.6391
37.8961 31.9919
38.4688 34.2414
26.8008 25.4742
3
74.869
47.1766
29.6246
32.4438
24.5743
4
75.8449
47.1964
29.0601
31.921
24.0802
5 6
80.128 83.3284
50.1641 52.1954
31.427 33.1314
33.9394 35.5908
24.7695 25.3665
7
86.6216
53.3974
33.9523
35.5779
25.3644
8
86.5838
51.8566
34.7432
36.962
25.9285
9 10
87.6295 81.2419
52.5663 49.7885
32.8057 32.3535
35.5994 35.5497
25.8943 26.5389
11
81.2521
50.1887
30.4691
32.9929
24.9181
12
84.8225
52.6876
32.8286
34.2026
25.1647
13 14
90.3132 90.0275
55.0462 56.8857
33.3177 36.6718
33.1786 35.2769
24.5586 24.92
15
87.8952
58.6668
40.0879
37.0861
24.1993
Tabulka 1Defaultní rychlosti podle úrovně silnici a timeslotu.
Druhý soubor obsahoval informace o dopravní síti. Obsahoval 257 531 řádků, kde každý řádek znamenal jednu nebo dvě hrany v závislosti na označení jejího směru. Pokud má směr „B“, znamená to, že je hrana neorientovaná. Jelikož, ale potřebuji pracovat s plně orientovaným grafem, je třeba tuto neorientovanou hranu převést na dvě orientované. Proto se každé z těchto nových hran přiřadí hodnota „F14“, nebo „T“, v závislosti na tom, z jakého bodu vychází. Strukturu tohoto souboru naznačuji v tabulce 2. A B C
D
E
F
G
LEVEL 3 47600 36983 47606 LEVEL 5 41627 47744 41668 … … … … … … … LEVEL 5 44617 47548 44617
H
I JK
14
M
37004 LEVEL 3 F 47781 LEVEL 5 B … … …… … … 47597 LEVEL 5 T
Tabulka 2 Data soubor s dopravní sítí.
13
L
reprezentuje časový úsek popsaný ve 4.2.1.2 F z anglického forward, T z anglického toward
51
N
O
P
25454132 25296945 … 25297204
1 7 … 15
2 8 … 16
Jednotlivé sloupce tabulky 2 obsahují tyto informace: A. *15Název hrany. B. *Název referenčního vrcholu. C. *Název nereferenčního vrcholu. D. *Úroveň hrany. E. Souřadnice x referenčního vrcholu. F. Souřadnice y referenčního vrcholu. G. Souřadnice x nereferenčního vrcholu. H. Souřadnice y nereferenčního vrcholu. I. Délka hrany – v metrech, pokud není uvedena, vypočítává se ze souřadnic. J. *Ignorování referenčního vrcholu. K. *Ignorování nereferenčního vrcholu. L. Úroveň hrany. M. Orientace hran – „F“, z referenčního do nereferenčního vrcholu, „T“ z nereferenčního do referenčního vrcholu, „B“, obojí. N. Identifikátor hrany. O. Identifikátor referenčního vrcholu P. Identifikátor nereferenčního vrcholu. Třetí soubor obsahoval informace upravující rychlost hran v jednotlivých „timeslotech“ a dnech. Soubor obsahoval 1 907 832 záznamů. Jeho struktura je uvedena v tabulce 3. ID hrany
Směr
25296896 25296896 25296896 25296896 25296896
T T T T T
Den
Timeslot Rychlost (km/h) 2 2 2 2 2
1 5 8 9 10
30 12 13.4 14 8.5
1 1 5 1 6
Tabulka 3 Struktura souboru upravující rychlost hrany.
Význam poslední hodnoty mi není znám, ale v modelu se nijak nepoužívá. Domnívám se, že to budou počty vozidel, ze kterých se pak zprůměrovala rychlost.
15
* znamená domyšlený význam hodnoty, protože bližší informace nebyly specifikovány, avšak tyto hodnoty nejsou zatím v modelu nijak použity
52
6.1.1 Datové úložiště V zadání diplomové práce bylo, že model by měl preferovat xml soubory, jako zdroj dat. Avšak po zjištění množství dat a po dohodě jsem vyměnil xml soubory za databázi. Kdybychom používali xml soubory a chtěli hledat jednu hodnotu ve skoro 10 milionech řádcích, asi bychom se nedočkali výsledku. Tím pádem byla i celkem ulehčena práce s převáděním csv souborů na xml soubory. V databázi stačilo vytvořit tři tabulky, odpovídající jednotlivým sloupcům csv souborů. Máme potom tedy tabulky:
network
default_speed
speed
a timetable, která reprezentuje Road Timetable.
6.1.2 Oracle Database 11g Express Edition Ze všech možných volně dostupných databází, jsem si vybral Oracle 11g Express Edition16, neboť v ní mám nejvíce zkušeností a znalostí v dotazování se do tabulek. Tato databáze může být nainstalována na jakýkoliv počítač s libovolným počtem procesoru, avšak nemůže uložit více jak 11GB uživatelských dat, využije maximálně 1GB paměti a použije pouze 1 procesor. Abychom mohli používat tuto databázi společně s vyšším programovacím jazykem Java, musíme si sehnat správný ovladač JDBC. JDBC API poskytuje základní rozhraní pro unifikovaný přístup k databázím. Základem konceptu JDBC je využití funkčnosti poskytované JDBC ovladačem, který je následně překládá do nativních volání dané databáze. Díky tomu je aplikační programátor odstíněn od specifického API databáze a může se naučit jednotné rozhraní JDBC, které pak použije pro přístup do libovolné databáze, která poskytuje JDBC ovladač. V dnešní době to jsou prakticky všechny hlavní systémy a ovladače jsou optimalizované a vyvíjené samotnými výrobci databázových strojů. Architektura JDBC je poměrně přímočará a je zobrazena na obrázku 26. Přestože je schéma zjednodušené, naznačuje základní princip JDBC, jak jej vnímá aplikační programátor. Logika JDBC je ale složitější v závislosti na vlastnostech JDBC ovladače.[15] Obrázek 26 Architektura JDBC
Pro spojení s databází Oracle Database 11g Express Edition používám verzi ovladače ojdbc6.jar17.
16 17
Oracle Database 11g Express Edition naleznete volně ke sažení na http://www.oracle.com/index.html ojdbc6.jar je volně ke stažení na http://www.oracle.com/technetwork/java/javase/jdbc/index.html
53
6.1.3 Struktura databáze V textu níže uvádím struktury tabulek, ve kterých jsou uloženy data pro model. Tyto tabulky nemají mezi sebou žádnou referenční integritu.
6.1.3.1 Tabulka network Slouží k uchovávání informací o dopravní síti. V modelu se z této tabulky berou informace o vrcholech a hranách, které poté slouží k jejich zobrazení ve dvourozměrném virtuálním prostoru. Struktura tabulky je zobrazena na obrázku 27. Sloupce tabulky, vypsané na obrázku pod sebou v řádcích, odpovídají jednotlivým sloupcům csv souboru, popsaného v 6.1.
Obrázek 27 Struktura tabulky „network“.
6.1.3.2 Tabulka default_speed Tato tabulka uchovává data o defaultních rychlostech hran každé úrovně, v každém „timeslotu“. Data zodpovídajícího datového soboru musela být upravena pro zápis do databázové struktury, která je znázorněna na obrázku 28. Úrovni odpovídá sloupec „LEVEL_ID“, „timeslot“ je stejný a rychlost v kilometrech za hodinu je uložena ve sloupci speed.
Obrázek 28 Struktura tabulky „default_speed“.
6.1.3.3 Tabulka speed V této tabulce jsou uchovávány změny rychlostí hran, v daném dnu a „timeslotu“, oproti defaultní rychlosti. Tyto rychlosti jsou velmi důležité, kvůli rychlosti přesunu po hraně. Struktura této tabulky je uvedena na obrázku 29. 54
Obrázek 29 Struktura tabulky „speed“
6.1.3.4 Tabulka timetable Tato tabulka reprezentuje popisovanou Road Timetable v části 4.2. Její struktura je znázorněna na obrázku 30.
Obrázek 30 Struktura tabulky „timetable“.
Source – uchovává hodnotu identifikátoru pro výchozí vrcholy sítě.
Target – uchovává hodnotu identifikátoru pro koncové vrcholy sítě.
Starttime – počáteční čas výjezdu z výchozího vrcholu sítě, v sekundách.
Day – den v týdnu (označený 1-7, kde 1 je pondělí), ve kterém je zahájen výjezd z výchozího vrcholu.
Length – celková vzdálenost trasy udávaná v metrech.
Traveltime – celková doba na projetí trasy v sekundách.
Route – uložená cesta vrcholů, které projde z výchozího vrcholu do cílového. Je reprezentována, jako znakový velký objekt, kde jsou jednotlivé identifikátory vrcholů, kterými se prochází, odděleny středníkem.
55
6.1.4 Problémy s daty Při práci s daty se vyskytnul problém při zjištění, že obyčejný Dijkstrův algoritmus nebude stačit na spočítání všech nejkratších cest v reálném čase, neboť dopravní síť, kterou popisují tato data, obsahuje přibližně 208 tisíc vrcholu a 257 tisíc hran. A to i při použití Fibonacciho haldy, jako prioritní fronty v Dijkstrově algoritmu, nebyla doba spočítání reálná. Další problém nastal poté, co jsem našel techniku, která slibovala spočítání obrovských dopravních sítí v reálném čase, popsaná v kapitole 5. Tím bylo zjištění, že tento algoritmus selhává při konstrukci. Objevil jsem, že obdržená data netvoří souvislý graf, ale nacházejí se i takové hrany, které nejsou s grafem vůbec spojeny. Dále se také objevovali „slepé“ vrcholy, do kterých se nedalo vjet nebo z nich vyjet, což bylo způsobeno vyříznutím části dopravní sítě a tyto vrcholy byly odmazány. Po odstranění těchto slepých bodů, přišel další problém. Doba potřebná na vytvoření Road Timetableje závislá na době nalezení nejkratší cesty. I kdyby doba pro nalezení nejkratší cesty, pomocí techniky dálniční hierarchie trval na běžném počítači 0.0001 sekundy, pak doba potřebná na spočítání celé Road Timetable je daná jako: ší
∙
č Č
ů ý
∙
č
ů∙
č
ž ý ℎ
ℎ ů.
To ve výsledku znamená 0.0001*96*7*(207000*206999)
= 2879438889.6 sekund
= 47990648.16 minut
=799844.136 hodin
= 33326.839 dnů
= 1110.894633 měsíců
= 92.57let
Dále pak jestli vůbec, při takovém množství dat v Road Timetable, by bylo možné ji vytvořit, neboť by tabulka potřebovala 96*7*(207000*206999) řádku, což je rovno 28 794 388 896 000 a k tomu nějaké místo na indexy, přitom povolené množství uživatelských dat je ve zvoleném DB systému omezeno na 11GB. Po těchto zjištěních jsem se rozhodnul, že omezím data jen na silnice úrovně 1 a silnice úrovně 2. Ty obsahovali něco kolem 3 tisíc vrcholů. Jenže dalším problémem, který se vyskytnul, byl samotný framework Repast Simphony 2.0. Ukázalo se totiž, že framework při předávání vrcholů do kontextu značně ztrácí výkon a není schopný v rozumném čase tyto vrcholy načíst.
6.1.5 Použitá dopravní síť Po všech problémech, které se vyskytly s daty, jsem se rozhodnul nadefinovat menší dopravní síť. Pro přehlednost, jsem zvolil dopravní síť, která byla použita v kapitole 5 na obrázku 23. Definoval jsem si vlastní csv soubory a zadal délky hran, aby nebyly vypočítávány ze souřadnic. Vzniklá dopravní síť je znázorněna na obrázku 3. Ohodnocení hran je v kilometrech. Defaultní rychlosti 56
jsem zachoval z původního souboru a upravené rychlosti, přepisující tyto defaultní náhodně vytvořil, také z existujících dat, ale nejsou požadovány.
Obrázek 31 Dopravní síť použitá v modelu
6.1.6 Vytvoření Road Timetable Pro účel vytvoření Road Timetable byla vytvořena malá konverzní konzolová aplikace, která načte údaje o síti uložené v tabulce v databázi a pak, pomocí algoritmu na hledání nejkratších cest, zjišťujeme pro každý čas výjezdu v každém dni dobu trvání cesty, délku cesty a konkrétní cestu přes které vrcholy. Trasy počítáme po 15 minutách výjezdu a musíme zohledňovat dobu přejezdu hrany, pokud se během přejezdu změní „timeslot“ a s tím související rychlost podle pseudokódu na obrázku 11. Celková doba potřebná na vytvoření Road Timetable pro 27 vrcholů a 70 orientovaných hran byla mezi 21-25 minutami s počítačem o parametrech: Intel Core2 Duo CPU 2.00 GHz, 3GB RAM a 32-bitový Windows 7 Professional.
6.2 Model V této kapitole je popsán koncept modelu. Zaměřím se na použité agenty a jejich význam v modelu.
6.2.1 Popis Simulační model má sloužit pro experimentování s distribučním systémem na silniční síti s primárním zaměřením na sledování produkce oxidu uhličitého od nákladních vozidel do ovzduší. Oxid uhličitý je totiž jednou z hlavních látek, díky které vzniká skleníkový efekt. Proto se tento model zaměřuje právě na ni. Vypouštění oxidu uhličitého závisí na rychlosti vozidla, kterou se pohybuje. Na stránkách http://naei.defra.gov.uk/, můžeme najít závislostní rovnici pro různé typy 57
vozidel. Pro svůj model jsem použil vozidlo pro distribuci zboží s dieselovým motorem splňující emisní normu Euro 2. Pro tento typ vozidla pak platí emisní rovnice ve tvaru: 10,19250646 + 0,026883951 ∙
− 5,68171 ∙ 10
∙
.
Výsledek rovnice nám udává produkci oxidu uhličitého v g/km, při rychlosti x. V modelu jsem zavedl, že každý tik simulačního času znamená jednu sekundu. Proto rychlosti uložené v databázi, převádím v modelu na m/s a vzdálenosti jsou v metrech tak, abychom nějakým způsobem stanovili jednotky, se kterými bude pracováno. V tiku 0, který znamená půlnoc a den 1, tedy 00.00 hodin v pondělí, a pak v každém následujícím 84000 tiku, což znamená každých 24 hodin, se generují nová řešení pro nový den. V modelu je 5 agentů:
Controller,
Depo,
Customer,
Vehicle,
a Scheduler.
6.2.1.1 Agent Controller Má na starosti správu času v modelu. S každým tikem zajišťuje, že se správně posune den pokud se má posunout, anebo změní „timeslot“, pokud se má změnit. Dále také zajišťuje, že vrátí výsledek na to, kolik je zrovna hodin v modelu, podle aktuálního tiku. Tedy udržuje vnitřní hodnotu tiku, který se pohybuje od 0 – 86399, tj. 24 hodin.
6.2.1.2 Agent Depo Při spuštění modelu se náhodně vygeneruje pozice na dopravní síti a je výchozím a posledním bodem naplánované trasy v daný den. Dále taky drží hodnotu o tom, v kolik nejdříve mohou vyjet a v kolik se mají vrátit. Má tedy vlastní časové okno. V modelu je depo znázorněno červeným trojúhelníkem. Pro model má depo časové okno od 5.00. do 22.00 hod.
6.2.1.3 Agent Customer Tento agent je zákazník obsluhovaný vozidly. Drží údaje o kapacitě, která je významná pro plánování vozidel a také má své časové okno, ve kterém může být obsloužen. Pokud vozidlo přijede dříve, tak musí počkat, pokud přijede pozdě, nemá šanci zákazníka už obsloužit. Každý zákazník má individuální dobu obsluhy, v závislosti na množství zboží, které musí vozidlo naložit nebo vyložit. V modelu je zobrazený jako zelený a modrý trojúhelník. Oba to jsou ti samí zákazníci ve stejném vrcholu, ale zelené obsluhuje vozidlo, které má plánované nejrychlejší cesty a modré obsluhují vozidla, která mají nejkratší cesty. Počet zákazníků je náhodně generován mezi 40% - 60% z jedné třetiny všech vrcholů. A jejich začátky časových oken jsou od 7.00 do 22.00, přičemž mají 58
trvání od 20 do 60 minut. Pokud zákazník není obsloužen, je to tím, že má časové okno podobné jako ostatní zákazníci, anebo je možná obsluha až v čase, kdy by se nestihlo vozidlo vrátit zpět do depa. Množství kapacity potřebné na obsloužení se generuje v rozmezí 1 – 20 jednotek.
6.2.1.4 Agent Vehicle Je vozidlo, které se pohybuje po dopravní síti rychlostí odpovídající toku dopravy každé hrany v daném „timeslotu“ a dnu. Vozidlo vyrazí z depa v čase takovém, aby stihl dojet k prvnímu zákazníkovi včas s minimální dobou čekání. Jakmile vozidlo dorazí k zákazníkovi, zákazník z modelu zmizí, což indikuje stav obsloužení zákazníka. Vozidlo čeká na místě, dokud není dokončena obsluha zákazníka. Poté vyráží k dalšímu cílu cesty. Vozidel jsou v modelu dva druhy. Zelené, které má plánovanou trasu jako nejrychlejší možnou a oproti tomu modré, které využívá nejkratší cesty. Poté co má vozidlo obsloužené všechny naplánované vrcholy, může se vrátit do depa. Pro vozidlo, které se řídí nejkratší cestou, jsem použil při vypočítávání odhadované doby cesty, tak jak to dělají jiné systémy, maximální povolené rychlosti. Ty jsem vzal ze serveru www.smartdriving.co.uk a jsou následující podle úrovně silnice.
Úroveň 1 – 112 km/h
Úroveň 2 – 96 km/h
Úroveň 3 – 80 km/h
Úroveň 4 a 5 – 48 km/h
V případě, že vozidla vyjedou z depa ve stejný čas, jejich animace splývají. To má za důsledek, že se více aut jeví jako jedno. Takto cestují po hraně, až dorazí do vrcholu, kde se jejich cesty liší.
6.2.1.5 Agent Scheduler Je plánovač, který má na starosti opakovat každý den generování nových zákazníků, vytvoření vozidel a naplánování tras k zákazníkům pro tato vozidla. Během simulace se hodnoty za každý den ukládají do definovaného data setu, který je součástí frameworku a následně se pak zapisují do souboru. Data z toho souboru je pak možno analyzovat například v tabulkovém editoru nebo podobně.
Obrázek 32 Náhled zobrazení modelu
59
7 Experimenty Následně se budeme zabývat experimenty s modelem, kde budeme měnit některé parametry. Budeme sledovat, jakým způsobem se bude měnit počet neobsloužených zákazníků, celkový počet najetých kilometrů, celkovou pracovní dobu všech vozidel i pracovní dobu jednotlivých vozidel a celkové vypouštění oxidu uhličitého do ovzduší. V jednotlivých podkapitolách budou popsány scénáře a jejich výsledky, přičemž detailnější výsledky naleznete v přílohách kvůli rozsáhlým datům. Model nechávám běžet po 28 dní simulačního času a ze získaných dat vybírám potřebné součty a hodnoty k uvedení závěru experimentu.
7.1 Scénář 1: Jedno vozidlo s kapacitou 50 jednotek
Najeté kilometry
Při tomto scénáři je skoro 40% zákazníků neobslouženo. Vozidlo s plánovanými nejrychlejšími trasami, najede průměrně každý den 508 km s celkovou pracovní dobou skoro 750 minut. Přitom vyprodukuje průměrně 103,8 kg oxidu uhličitého do ovzduší. Oproti tomu vozidlo, které se pohybuje po nejkratších trasách, najede průměrně každý den 499 km s pracovní dobou 772 minut a vyprodukuje kolem 111kg oxidu uhličitého za den. Z uvedených dat vyplývá, že vozidlo s nejrychlejšími trasami najede sice více kilometrů, avšak sníží produkci oxidu uhličitého o 6,6%.
650
Průměr celkově najetých km
550 450 350
Den v týdnu
Nejrychlejší cesta Nejkratší cesta
Obrázek 33Scénář 1 – průměrné vzdálenosti.
60%
Porovnání produkce CO2
50%
40%
Den v týdnu
Nejkratší trasa Nejrychlejší trasa
Obrázek 34 Scénář 1- produkce CO2 podle metody plánovaní tras.
60
7.2 Scénář 2: Jedno vozidlo s kapacitou 100 jednotek S takto nastavenými parametry modelu vozidlo dokáže obsloužit přibližně 75% ze všech zákazníků. Vozidlo pohybující se nejkratší cestou vyprodukuje při průměrně najetých 536 km asi 117 kg oxidu uhličitého denně za dobu 878 minut. Vozidlo s nejrychlejšími trasami vyprodukuje průměrně 109 kg oxidu uhličitého denně za dobu 866 minut a ujetou průměrnou vzdáleností 542 km. Tím vyprodukovalo o 6,4% méně oxidu uhličitého.
km
Průměr celkově najetých km 670 620 570 520 470 420 370
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Obrázek 35 Scénář 2 – průměr vzdálenosti.
Porovnání produkce CO2 60%
50%
40%
Nejkratší trasa Den v týdnu
Nejrychlejší trasa
Obrázek 36 Scénář 2 - produkce CO2 podle metody plánovaní tras.
61
7.3 Scénář 3: Dvě vozidla s kapacitou 50 jednotek Dvě vozidla s kapacitou 50 jednotek dokážou obsloužit 85% zákazníků. Vozidla používající nejrychlejší trasy dokážou tyto zákazníky obsloužit průměrně za 1430 minut a najedou při tom průměrně 830 km a vyprodukují společně v průměru 170 kg oxidu uhličitého do ovzduší. Vozidla s nejkratší cestou obslouží tyto zákazníky a vrátí se do depa po 1449 minutách, průměrně najezdí 791 km a vyprodukují 180 kilogramů CO2, to je více o 5.2% než vozidla s nejrychlejšími trasami.
km
Průměr celkově najetých km 990 940 890 840 790 740 690
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Obrázek 37Scénář 3 – průměr vzdálenosti.
Porovnání produkce CO2 60%
50%
40%
Nejkratší trasa Den v týdnu
Nejrychlejší trasa
Obrázek 38 Scénář 3 - produkce CO2 podle metody plánovaní tras.
62
7.4 Scénář 4:Čtyři vozidla s kapacitou 20 jednotek V tomto scénáři má depo k dispozici čtyři vozidla s kapacitou 20 jednotek a nezvládnou obsloužit pouze 3% zákazníků. S tím jsou spojené náklady, kdy vyprodukují v průměru 213 kilogramů oxidu uhličitého denně při použití nejrychlejších tras. Při těchto parametrech denně najedou v průměru 952 kilometrů za dobu 1987 minut. Nejkratší cestou však vozidla najedou průměrně 941 km za 2009 minut a vyprodukují 229 kilogramů oxidu uhličitého denně. Rychlejší cestou ušetříme vyprodukování CO2 o 7,21%.
Průměr celkově najetých km 1100
km
1050 1000 950 900 850
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Obrázek 39Scénář 4 – průměr vzdálenosti.
Porovnání produkce CO2 60%
50%
40%
Nejkratší trasa Den v týdnu
Nejrychlejší trasa
Obrázek 40Scénář 4 - produkce CO2 podle metody plánovaní tras.
63
7.5 Scénář 5: Šest vozidel s kapacitou 20 jednotek V šestém scénáři je použito šest vozidel o kapacitě 20 jednotek. Ve výsledných datech je vidět, že ve třech případech bylo použito jen 4 vozidel a ve 3 případech 5 vozidel. Vozidla s nejkratšími cestami průměrně denně najezdí dohromady 1124 km, s pracovní dobou 1950 minut a vyprodukují 270 kg oxidu uhličitého. Vozidla s nejrychlejšími trasami najezdí 1157 km za 1902 minut a vyprodukují denně v průměru 252kg škodlivin. V tomto případě je úspora produkce škodlivých látek 6,6%.
Průměr celkově najetých km 1300
km
1250 1200 1150 1100 1050
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Obrázek 41 Scénář 5 – průměr vzdálenosti.
Porovnání produkce CO2 60%
50%
40%
Nejkratši trasa Den v týdnu
Nejrychlejší trasa
Obrázek 42Scénář 5 - produkce CO2 podle metody plánovaní tras.
64
7.6 Scénář 6: Deset vozidel s kapacitou 10 jednotek Poslední scénář obsahuje tolik aut, kolik může být na této síti maximálně zákazníků. To vede k 100 % obsloužení zákazníků. Z výsledných dat je však vidět, že bylo použito maximálně 8 vozidel. V této situaci vozidla najezdila nejvíce ze všech dní a to 2136 km za 2259 minut a vyprodukovala 391 kg oxidu uhličitého, pokud používala nejrychlejší cestu. Nejkratší cestou by to bylo1839km za 2269 minut a emise by byly 390 kg, což jsou v podstatě hodně podobné výsledky. Z celého scénáře je úspora produkce oxidu uhličitého pouze 2,93 %.
km
Průměr celkově najetých km 1200 1100 1000 900 800 700 600 500 400 300
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Obrázek 43 Scénář 6 – průměr vzdálenosti.
Porovnání produkce CO2 60%
50%
40%
Nejkratší trasa Den v týdnu
Nejrychlejší trasa
Obrázek 44Scénář 6 - produkce CO2 podle metody plánovaní tras.
65
8 Závěr Všechny cíle diplomové práce byly splněny. V první teoretické části je uvedena terminologie agentově orientovaného programování a nástroj, který umožňuje vytvářet agentově orientované simulační modely, a to Repast Suite. V další části jsem se seznámil s projektem Green Logistics, kde je popisován algoritmus nazývaný LANTIME, který využívá dlouhodobé informace o dopravních tocích na pozemních komunikacích k efektivnímu plánování tras nákladním vozidlům, přepravující zboží od (nebo k) zákazníkům. V praktické části byl vytvořen model, který měl ověřit funkčnost tohoto algoritmu, a to tak, že bude sledovat produkci oxidu uhličitého do ovzduší od těchto vozidel v důsledku jejich pohybu po naplánované trase. Pro vytvoření takového modelu jsem obdržel data sítě, pro kterou by se měl algoritmus ověřovat. Tato síť byla natolik obsáhlá, že pro běžný studentský hardware a software, i přes vyzkoušení několika technik, nebyla zpracovatelná. Proto byla použita abstraktní síť, na které bylo umožněno model otestovat. Společně s modelem byl vyhotoven konverzí program, pro vytvoření tabulky, obsahující údaje o časech dojezdů z jakéhokoliv vrcholu dopravní sítě, do jakéhokoliv jiného vrcholu, libovolný čas a den. Z výsledků scénářů aplikovaných na model je zřejmě, že naplánování tras za použití algoritmu LANTIME dosáhneme pokaždé snížení produkce oxidu uhličitého do ovzduší, než kdybychom plánovali trasy pomocí nejkratších cest. I když nejrychlejší cestou můžeme najet více kilometrů, než kdybychom použili nejkratší, ušetříme tím tak čas, i životní prostředí. V současné době je vyvíjena modifikace tohoto algoritmu a to takové, že by měl zahrnovat legislativní omezení. Ty zahrnuji povinné přestávky řidiče po určité době. Dále by také mohl zohledňovat vyšší produkci škodlivin, při větším množství přepravovaného nákladu. Dále by byla vhodná implementace nejnovějších optimalizačních metod, pro plánování cest. Díky této diplomové práci jsem získal nové zkušenosti s velmi efektivními algoritmy pro problémy týkající se dopravní sítě. V první řadě jsem poznal algoritmus, který dokáže spočítat nejkratší cestu na dopravní síti celého kontinentu v reálném čase. Následně jsem se seznámil s algoritmem pro plánování tras, který dokáže redukovat produkci škodlivých látek. Celou práci hodnotím jako velký přínos pro mé „know how“ a v budoucnu snad i pro životní prostředí. Pravděpodobně se tímto problémem budu zabývat i v budoucnu.
66
Seznam použité literatury 1. RAPANT, Petr. Prostor v multiagentových systémech modelujících prostorové procesy. Acta MontanisticaSlovaca. 2007, roč. 12, č. 2, s. 84-97. Dostupný z WWW:
. 2. KAVIČKA, A., KLIMA, V., ADAMKO N.: Agentovo orientovaná simulacia dopravných uzlov. Žilina: EDIS, 2005. 206 s. ISBN808070-477-5 3. LEKÝR, Michal. SOFTVÉROVÉ PROSTREDIE. Žilinská univerzita v Žiline, 2006. 93 s. , obr.příl. Fakulta riadenia a informatiky. Žilinská univerzita v Žiline. Katedra dopravných sietí. Vedoucí dizertační práce Doc. Mgr. Valent Klima, Csc. 4. VOLNÁ, Eva. VYBRANÉ PARTIE UMĚLÉ INTELIGENCE: Multiagentové systémy. Úvod do memetiky. [online]. Ostrava, 2005 [cit. 2012-08-06]. Dostupné z: http://www1.osu.cz/~volna/Vybrane_partie_UI_1_dil_skripta.pdf. Studijní materiály pro distanční kurz. Ostravská univerzita v Ostravě. 5. MARIŠKA, Martin. Agentově orientované simulační modely provozu obslužných systémů. Pardubice, 2012. Diplomovápráce. Univerzita Pardubice. Vedoucí práce prof. Ing. Antonín Kavička, PhD. 6. MADEN, W, R EGLESE a D BLACK. Vehiclerouting and schedulingwithtime-varying data: A case study. JournaloftheOperationalResearch Society [online]. 2010, s. 515-522, 2009-08-14 [cit. 2012-08-08]. Dostupné z: http://www.greenlogistics.org/SiteResources/91cf0308-f5de-46269b31-fa48c5a33c65_Lancaster-VehicleRoutingAndScheduling2009.pdf 7. Eglese RW, Maden W and Slater A (2006). A RoadTimetableTM to aidvehiclerouting and scheduling. ComputOpns Res 33: 3508-3519. 8. Potvin J-Y and Rousseau J-M (1993). A parallel route building algorithm for the vehicle routing and scheduling problem with timewindows. Eur J Opl res 66: 331–340. 9. Horn MET. Efficient modeling of travel in networks with time-varying link speeds. Networks 2000;36:80–90. 10. Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristicfor the vehicle routing problem. Mngt Sci 40: 1276–1290. 11. Sanders, P., Schultes, D.: Engineering highway hierarchies. In: Azar, Y., Erlebach,T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 804–816. Springer, Heidelberg (2006) 12. Schultes, D.: Fast and exact shortest path queries using highway hierarchies. Master’s thesis, Universit¨ at des Saarlandes (2005). 67
13. Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In:13th European Symposium on Algorithms (ESA). Volume 3669 of LNCS., Springer(2005) ;568–579. 14. V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS/0310049, 2003. 15. ŠEDA, Jan. Úvod do JDBC. In: Interval.cz [online]. 2003 [cit. 201208-27]. Dostupné z: http://interval.cz/clanky/uvod-do-jdbc/ 16. Solomon, M.M. (1987), "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations Research 15/2, 254-265. 17. Ahn B-H, Shin J-Y.Vehicle-routeing with time windows and time varying congestion. Journal of the Operational ResearchSociety 1991;42:393–400. 18. B. Ding, J. X. Yu, and L. Qin. Finding time-dependent shortest paths over large graphs. In Proc. of EDBT-2008. 19. B. Ding, J. X. Yu, and L. Qin. Finding time-dependent shortest paths over large graphs. In Proc. of EDBT-2008. 20. Campbell, A., Savelsbergh, M.: Efficient insertion heuristics for vehicle routing and scheduling problems. Transportation Science 38(3), 369–378 (2004) 21. Dijkstrův algoritmus. [online]. s. 6 [cit. 2012-08-29]. Dostupné z: http://kam.mff.cuni.cz/~ludek/NTIN060texty/Dijkstra.pdf
68
9 Přílohy Příloha A – Obsah přiloženého datového média Přiložené datové médium obsahuje:
Elektronickou verzi této práce ve formátu PDF, DOC a DOCX.
DDL skripty pro vytvoření potřebných tabulek.
CSV soubory s dopravní sítí.
Simulační model distribuční sítě.
Konverzní program pro vytvoření Road Timetable.
69
Příloha B – Další zpracované výsledky ze scénářů Scénář 1) Nejrychlejší trasa
900 850 800 750 700 650
Průměrná doba (min) 773.75 755 762.75 661.25 697.5 842.25 756.25
Průměrná celková pracovní doba vozidel
Nejrychlejší trasa Nejkratší trasa
kg
minuty
Průměrná Počet Počet vzdálenost zákazníků neobsloužených (km) Monday 8.5 4.25 398 Tuesday 8 4 439 Wednesday 8.5 2.75 549 Thursday 8.25 3.75 460 Friday 8.5 3.5 537.25 Saturday 8.5 3 633.25 Sunday 7.5 1.75 540
Nejkratší trasa CO2 (kg) 84.5 89.5 114.25 96.25 110.75 124 107.25
140 130 120 110 100 90 80
Průměrná vzdálenost (km) 398.25 438.75 540.25 458.75 537.25 602 520.25
Průměrná doba (min) 810 775.5 796.25 665.25 728 861.5 765.25
CO2 (kg) 91.25 97.75 124.75 103.25 119.75 128 113.25
Průměrná celková produkce CO2
Nejrychlejší trasa Den v týdnu
Den v týdnu
70
Nejkratší trasa
Scénář 2)
Monday Tuesday Wednesday Thursday Friday Saturday Sunday
Počet zákazníků 9 9 9.5 7.5 8.25 8.25 8.75
Nejrychlejší trasa Průměrná Počet vzdálenost Průměrná neobsloužených (km) doba (min) CO2 (kg) 2 601.5 896 125.25 2.75 530 797 111.75 2.25 635 1001.25 121.5 0.75 533 816.25 114 3 406.5 777 77.25 1.5 506.5 828.5 101.5 2.5 585.25 951 114.5
Průměrná vzdálenost (km) 593.5 524 627.75 526.25 399.5 510 574
1020 970 920 870 820 770
135 125 115 105 95 85 75
Nejrychlejší trasa
Nejrychlejší trasa Den v týdnu
Průměrná doba (min) 917.5 820.5 1003.25 835.25 779.75 826.5 968
Průměrná celková produkce CO2 kg
minuty
Průměrná celková pracovní doba vozidel
Nejkratší trasa
Den v týdnu
Nejkratší trasa
71
Nejkratší trasa
CO2 (kg) 132 119 131.25 117.25 82.5 108.25 128
Scénář 3)
Počet Počet zákazníků neobsloužených Monday 9 0.75 Tuesday 9.5 1.75 Wednesday 9 1.5 Thursday 8 1.75 Friday 8.5 2 Saturday 8.75 1 Sunday 7.5 0.5
Nejrychlejší trasa Průměrná Průměrná vzdálenost doba (km) (min) CO2 (kg) 842.5 1458.75 170 816.25 1579 167.75 943.5 1386.5 187 725 1440.5 148.75 831.25 1292.5 173.75 846.75 1414 179.75 807.5 1437.5 164.25
Průměrná Průměrná doba CO2 vzdálenost (km) (min) (kg) 786.75 1481.5 182.75 785.75 1596 179.75 891.5 1406.25 195.75 691.5 1437.75 154.25 815.5 1323 182.25 807.25 1439.75 186 757.75 1458.75 176
Průměrná celková produkce CO2
1530 1480 1430 1380 1330 1280
kg
minuty
Průměrná celková pracovní doba 1630 vozidel 1580
Nejkratší trasa
200 190 180 170 160 150 140
Nejrychlejší trasa Den v týdnu
Nejkratší trasa
Nejrychlejší trasa Den v týdnu
72
Nejkratší trasa
Scénář 4) Nejrychlejší trasa Počet Průměrná Průměrná neobsloužených vzdálenost (km) doba (min)
Počet zákazníků
1820.5 234.25
9.5
0.5
1041.25
Tuesday
8.25
0.25
861.75
1508.75
190
848
1528.25
200.5
9
0.25
1029.75
2067.75
230.5
1022
2077.75
251
Thursday
9.25
0.25
878.25
2285.5 196.25
860
Friday
8.25
0.25
897.5
1887.75
204
883.75
Saturday
8.75
0.5
970
2093.5
215
972.25
Sunday
8.25
0
986
2247.5
218.5
963.75
Průměrná celková pracovní doba 2500 vozidel
265
2300
245 kg
2100 1900
205
1500
185
Den v týdnu
73
1865.5 255.75
2304.5 208.75 1895.5 2261
Průměrná celková produkce CO2
Nejrychlejší trasa Den v týdnu
217
2132.75 240.75
225
1700
Nejrychlejší trasa Nejkratší trasa
1036
CO2 (kg)
Monday Wednesday
minuty
CO2 (kg)
Nejkratší trasa Průměrná Průměrná vzdálenost (km) doba (min)
Nejkratší trasa
230.5
Scénář 5)
2200 2100 2000 1900 1800 1700 1600
Průměrná celková pracovní doba vozidel
CO2 (kg) 245.25 252 240.75 243.5 269 276.5 240.25
Nejkratší trasa Průměrná Průměrná vzdálenost (km) doba (min) 1075.75 1945.25 1114.25 2027.75 1098 1735.25 1087.5 1883.5 1197.25 1847.75 1230.75 2117 1065.25 2094.25
310 300 290 280 270 260 250 240 230
Nejrychlejší trasa Den v týdnu
CO2 (kg) 256.25 266.75 267 260 288.25 300 254.5
Průměrná celková produkce CO2 kg
Minuty
Počet Počet zákazníků neobsloužených Monday 8.5 0 Tuesday 9 0.25 Wednesday 8 0.25 Thursday 8.5 0.25 Friday 8.5 0 Saturday 9.5 0.25 Sunday 9.5 0
Nejrychlejší trasa Průměrná Průměrná vzdálenost (km) doba (min) 1112.5 1921.75 1143.5 1967 1128.25 1673.25 1128 1849.5 1230 1800.25 1267.25 2038 1090 2068
Nejrychlejší trasa Dny v týdnu
Nejkratší trasa
74
Nejkratší trasa
Scénář 6) Nejrychlejší trasa Průměrná Průměrná vzdálenost (km) doba (min)
Počet Počet zákazníků neobsloužených
Nejkratší trasa Průměrná Průměrná vzdálenost (km) doba (min)
CO2 (kg)
Monday
8.5
0
640.5
704
123.5
549.75
724.5
125.5
Tuesday
9
0
1101.5
1299
216.5
984.75
1306.5
219
Wednesday
8
0
689
778 136.75
644.75
811.25 144.25
Thursday
8
0
930
1125.5
189.5
853.5
1143 194.75
Friday
8.5
0
393
511.75
84.75
394.25
Saturday
8.5
0
842.5
1015.75
168
759.5
1022.5 169.25
Sunday
7.5
0
549.5
686.25
115.5
533
725.5 123.25
Průměrná celková pracovní doba vozidel 1400
528.75
Průměrná celková produkce CO2
260 210
1200 1000 800 600 400
kg
minuty
CO2 (kg)
160 110 60
Den v týdnu
Nejrychlejší trasa
75
Den v týdnu
Řady 1
89.75
