Prírodou inšpirované algoritmy

Projekt - Ženeva

Jednými z konkrétnych príkladov využitia CA v oblasti dopravy je model simulujúci premávky v Ženeve. Model, ktorý bol aplikovaný dokáže simulovať pomerne realistické správanie sa jednotlivých vozidiel. Model obsahuje križovatky, ktoré sú reprezentované kruhovými objazdmi, pretože táto reprezentácia umožňuje vytvárať križovatky s ľubovoľným počtom pripojených komunikácií a je zároveň dobre numericky spracovateľná prostredníctvom paralelných výpočtových systémov. Túto reprezentáciu je ďalej ľahko možné skombinovať so svetelnou signalizáciou čo rozširuje a skvalitňuje simuláciu a správanie sa modelu.

Model, ktorý autori použili sa zakladá na tom, že každé vozidlo môže nadobúdať dve rýchlosti a to 0 alebo 1. Viacrýchlostné model sú totiž dôležité najmä pri simuláciách ciest akými sú napr. diaľnice, avšak sú zbytočne príliš zložité v prípade, že nás zaujíma napr. len poradie vozidiel pred križovatkou.

Pravidlom pohybu pre tento model hovorí o tom, že vozidlo sa pohne na najbližšiu voľnú pozíciu ak je táto voľná. Ak nie je voľná tak sa vozidlo nepohne. Tento pohyb môže byť popísaný vzťahom:

ni(t+1)=nini(t)(1-ni(t))+ni(t)nouti(t)

pričom ni(t) udáva prítomnosť resp. neprítomnosť vozidla na danej pozícii i, nini(t) označuje stav bunky z ktorej vozidlo môže prísť a nouti označuje stav cieľovej bunky.

Pravidlo hore teda znamená, že nasledujúci stav bunky i je 1 ak je zistená prítomnosť vozidla a ďalšia bunka je obsadená, alebo že auto sa na bunke nenachádza ale približuje sa z predchádzajúcej bunky. Pre jednoduchú jednorozmernú cestu s periodickými hranicami, platí v tomto prípade nasledovné:

nini = n i-1

nouti = ni+1

Rozšírenie do plnohodnotného 2D modelu je riešené spôsobom popísaným v predchádzajúcej časti.

Nasleduje zobrazenie klasického rozloženia dopravy v meste typu-manhattan

Rozloženie vozidiel po 600 iteráciách pre 30 % hustotu vozidiel. Ulice sú zobrazené bielou farbou, budovy sú šedé a čierne body zobrazujú vozidlá. Časť (a) zodpovedá rovnocennému správaniu sa vozidiel na každej križovatke, pričom (b) zobrazuje prítomnosť svetelnej signalizácie na križovatkách. V druhom prípade je vidieť väčší počet čakajúcich vozidiel pred križovatkami a tým pádom aj zníženie globálnej mobility oproti prípadu (a).

Dopravné zápchy

V tejto časti sa autori pokúsili o podrobný pohľad na správanie sa mesta typu Manhattan s ohľadom na rôzne počty vozidiel v systéme a vznik dopravných zápch. Najväčšia pozornosť sa venuje priemernej rýchlosti v ako funkcii priemernej hustoty ρ (napr. celkový počet vozidiel podelený počtom prístupných cestných buniek). S postupným pridávaním vozidiel dochádza v systéme k stavu, že časť vozidiel sa nepohne v každom časovom kroku pretože sú blokované vozidlami pred nimi.

Križovatky môžeme chápať ako brzdiace elementy, ktoré redukujú kapacitu cestného segmentu, a preto ak je hustota premávky väčšia ako určitý prah, začínajú vznikať rady vozidiel čakajúcich pred križovatkou. Zaujímavým aspektom tejto dynamiky je, že systém sa samo-organizuje do troch oblasti z rôznou hustotou vozidiel:

1. veľkosť radu vozidiel pred križovatkou hustoty ρj ( j označuje zápchu ) a vj= (1- ρj)/ ρj ( pretože rýchlosť v rade je riadená hustotou resp. množstvom voľných pozícií)
2. prázdne pozície cesty, ktoré sú za križovatkou s hustotou ρj a rýchlosťou vj= 1 (všetky vozidlá sa môžu pohybovať)
3. oblasť vnútri križovatky

Ak je prúdenie premávky J = ρ v je konštantná po celú dobu kedy pre systém, resp. rozhrania platí

z toho vyplýva

Pre Jinrotary a Joutrotary (ktoré označujú pravdepodobnosti vstupov a výstupov križovatiek) môžeme na základe použitého modelu 1 resp. 2 napísať

Označenie ρj (resp. 1-ρf) označuje pravdepodobnosť, že máme vozidlo pripravené na vstup do križovatky (resp. je pripravené ju opustiť).

ρ_r označuje pravdepodobnosť, že sa na križovatke nachádza vozidlo, ½ naznačuje, že vozidlo s 50 % pravdepodobnosťou križovatku opustí. Následne môžeme napísať

S narastajúcim počtom vozidiel v systéme, sa hodnoty ρj, ρf, ρr nemenia, ale narastá dĺžka l zápchy pred križovatkou. Za predpokladu že všetky zápchy pre križovatkami sú rovnakej dĺžky, vzťah medzi l a separácia L medzi dvomi po sebe nasledujúcimi križovatkami je

pričom L je merané ako perióda siete. V prípade, že L je veľké, môžme tento výsledok aproximovať ako

Toto sa rovná výsledku pre 1D model premávky s redukovanou kapacitou.

1. pre ρ<ρf máme 1 < 0, čo znamená, že nevznikajú žiadne zápchy a systéme sa nachádza v stave voľnej premávky
2. pre ρf<ρ<ρj , l nadobúda hodnoty od 0 po L. V tomto prípade ide o stav maximálneho nasýtenia premávky ( čo nastane ak ρ rastie, v klesá takže j = ρ v = 1/5 teda konštantné). Poradie teda zohráva úlohu rezervoáru, ktorý môže absorbovať nadmernú premávku.
3. pre ρ>ρj máme l > L čo naznačuje, že rady narastajú až po predchádzajúcu križovatku. Tento režim sa vyznačuje množstvom dopravných zápch.

Cestná sieť v Ženeve

Skôr spomínaný model je teda aplikovaný na cestnú sieť v predmestí Ženeve. Premávka je reprezentovaná ako graf (viď obrázok dole), v ktorom uzly reprezentujú križovatky. Zahŕňa 3145 cestných segmentov a 1066 križovatiek. Niektoré segmenty majú viacnásobné jazdné pruhy a na niektorých križovatkách sú signály zakazujúce otáčanie. Cestný úsek je diskretizovaný do 5M veľkých buniek a čas jednej iterácie je 0.36 s, takže povolená rýchlosť je 50 km/h. Celková dĺžka celej cestnej siete je približne 4000 km a na reprezentáciu tohto priestoru je potrebné mať 800765 buniek.

Cestná sieť Ženevy použitá v opisovanom modeli

Kvôli potrebe kvalitnej simulácie premávky v takomto systéme, bolo nutné zaviesť niekoľko všeobecných pravidiel:

1. vozidlo smie používate viacero jazdných pruhov. Ak sa vozidlo ocitne v rade na križovatku, môže použiť na jej opustenie ďalší jazdný pruh ak je tento voľný.
2. je použitý dvoj rýchlostný model umožňujúci vozidlám mimo mestskú časť jazdiť rýchlosťou 100 km/h.
3. informáciu o smerovaní vozidiel má každé vozidlo pre seba a je tak možné sledovať určitú cestu každým vozidlom zvlášť. Model počíta s 50000 vozidlami pohybujúcimi sa v rámci modelu v čase špičky.
4. je možné odoberať a pridávať vozidlá kvôli modelovaniu prichádzajúcich a odchádzajúcich vozidiel
5. pridanie istej (malej) pravdepodobnosti, že vozidlo nevstúpi na križovatku (za predpokladu, že je voľná) za účelom simulácie zaváhania niektorých vodičov. Takto predídeme vzniknutiu súvislého toku vozidiel prichádzajúcich z prehustenej lokality.

V dátach, ktoré boli použité nebol daný žiadny bližší popis križovatiek (napríklad prítomnosť resp. neprítomnosť svetelnej signalizácie). Práve z tohto dôvodu sú všetky križovatky reprezentované ako kruhové podľa skôr uvedeného modelu 1. Zároveň bol zistený vplyv veľkosti kruhového objazdu na maximálny počet vozidiel prechádzajúcich križovatkou. Z tohto dôvodu boli v simulácii realizované dostatočne veľké križovatky na dosiahnutie primeraných podmienok.

Matica štartovacích a cieľových pozícií

Veľmi dôležitú úlohu pri simulácii má matica štartovacích a cieľových pozícií. Pokiaľ sa chceme zaoberať realistickou simuláciou dopravy je nevyhnutné vedieť trasy uprednostňované jednotlivými vodičmi a podobne aj čas na ich prekonanie.

Na vyriešenie tohto problému sa dajú použiť isté čiastkové informácie. Počiatočno-cieľová ( ďalej PC) matica pre prípad mesta Ženeva, obsahuje 49418 párov AB lokalít v cestnej sieti, teda vlastne vozidiel cestujúcich z A do B. Na základe týchto údajov sa dá určiť cestu každého vozidla. Ide tu o veľmi náročný optimalizačný problém.

V prípade Ženevy bol na určenie vyťaženia každého cestného segmentu použitý program EMME2. Použitá metóda je založená na predpoklade, že každá cesta z A do B zaberie rovnaký čas. Inač povedané, ak je niektorá s ciest menej zaťažená tak ju niektorý vodiči nájdu a tak vyrovnajú celkové nasýtenie premávky.

Postup je nasledovný. Najprv sa vypočíta najkratšia cesta medzi všetkými PC bodmi. Pre túto potrebu bola modifikovaná metóda so štandartným grafovým algoritmom aby tak boli do úvahy brané aj signály zabraňujúce otáčanie. Váha každej hrany je nainicializovaná na počiatku na hodnotu rovnú dĺžke cestného úseku. Potom použitím PC matice sa vypočíta kumulatívne využitie každej hrany (počet vozidiel, ktoré ju používajú). Hrany, na ktorých je premávka prehustená sú penalizované zväčšením ich efektívnej dĺžky. Všetky cestu sú potom opätovne prepočítané s týmito novými váhami. Spomenutá procedúra sa opakuje niekoľko krát až pokiaľ nie je dosiahnuté vyhovujúce využitie jednotlivých cestných segmentov. Je treba si ešte uvedomiť, že tento algoritmus umožňuje použitie viacerých ciest medzi pármi pozícií v PC matici.

Obrázok zobrazuje nasýtenie premávky vyrátané na základe PC matice a toto sa ďalej bude používať ako smerovacia informácia pre vozidlá pri simulácii.