Dopravně závislé řízení silničního provozu ve městech (2. část)

Dopravně závislé řízení silničního provozu ve městech (2. část)

Ivan Nagy, Jitka Homolová, Pavla Pecherková
(dokončení z minulého čísla)

5. Lokální řízení

Dostáváme se k našemu hlavnímu cíli, kterým je řízení. Jak jsme se již zmínili, nejprve se budeme zajímat o lokální řízení uvnitř jednotlivých mikrooblastí, kde cílem bude dosáhnout co nejkratších a po ramenech vyvážených kolon. Potom přistoupíme k řízení mikrooblastí tak, aby dopravní situace byla dobrá i z globálního pohledu.

5.1 Formulace úlohy pro lineární programování
Základem pro syntézu optimálního řízení je kritérium optimality a odpovídající model. Konstrukce modelu a jeho přiblížení k realitě v procesu odhadování byly obsahem předchozích odstavců. Nyní přistoupíme k volbě vlastního kritéria řízení. Toto kritérium musí mít solidní praktický (rozuměj z praxe vycházející) základ a vést k rozumně složitému výpočtu, řešitelnému v potřebném časovém intervalu.

5.1.1 Praktický základ kritéria
Nejčastěji používaným kritériem pro kvalitu dopravy ve městech je tzv. doba jízdy, resp. doba zdržení řidiče mezi dvěma pevně definovanými body (často se definuje jako doba jízdy z okraje města do centra). Doba zdržení je kromě jiného závislá také na délkách kolon na ramenech, kterými řidič projíždí. Proto bude kritérium, které je zapotřebí minimalizovat, uvažováno v podobě váženého součtu délek kolon v mikrooblasti, tj. ve tvaru

kde N_ξ je počet kolon v mikrooblasti, ω_i jsou váhy pro jednotlivé kolony, ξ_i délky kolon v mikrooblasti.

Váhy ω_i mohou být nastaveny pevně nebo mohou být i datově závislé. Tyto váhy mají zaručit, že kolony nebudou pouze minimalizovány, ale že budou mít také přibližně stejnou délku, bude-li to možné a žádoucí. S využitím těchto vah lze preferovat důležité směry v dopravní síti, a používat je tak i k řízení některých výjimečných stavů v dopravě. Například pohyb preferovaného vozidla (sanitka, požární vůz apod.) může být i ve zcela saturovaném prostředí upřednostněn tak, že bude uměle nastavena váha pro příslušný jízdní pruh na značně velkou hodnotu a tak bude urychlen pohyb celé kolony v daném jízdním pruhu.

5.1.2 Úloha lineárního programování
Pro úlohu lineárního programování je třeba kromě kritéria ještě stanovit všechna omezení pro používané veličiny a vymezit tak plochu mnohoúhelníku, na které se nalézá řešení úlohy. Systém omezení pro optimalizaci lineárním programováním je dán jednak modelem (7), (8), jednak dalšími podmínkami, jako jsou nezápornost všech veličin, jejich minimální a maximální hodnoty apod. Jedním omezením, které plyne čistě z dopravní podstaty řešené úlohy, je omezení signálním plánem. To říká, že celkový součet dob zelených je pro jednu křižovatku konstantní a roven době cyklu zmenšené o dobu, která je nutná z hlediska bezpečnosti při průjezdu jednotlivých toků křižovatkou (lze si je přibližně představit jako žlutý signál; jejich výpočet je vždy přesně vymezen a váže se k vlastní stavební úpravě křižovatky). Uváděná úloha je tedy vlastně úloha přerozdělení celkové doby cyklu vymezené pro průjezd vozidel mezi jednotlivé fáze, tj. signální skupiny.

Pro formulaci úlohy lineárního programování definujeme nový stav sestavený z původního stavu a poměru zelené coby optimalizované veličiny:

X_t = [x^T_t+1, z^T_t]^T          (9)

(připomeňme, že T v horním indexu značí transpozici).

Z kritéria (9) úpravou modelu (7), (8) a z dalších omezujících podmínek se získá úloha lineárního programování ve tvaru

J = c^TX_t→ min          (11)

QX_t = q           (12)

X Î (0, r)          (13)

Jednotlivé, nově zavedené matice (vektory) mají takovýto význam:

c je vektor korespondující se stavem X a má váhy ω_i tam, kde stav X má délky kolon, tj. v první části stavu x_t+1 (viz (10)), jinde má nuly, Q matice, složená z matic původního modelu (7), (8), tj. [I, -B], kde I je jednotková matice odpovídajícího rozměru; v další řádcích je vyjádřením podmínky konstantního součtu relativních zelených pro jednotlivé křižovatky, q vektor tvořený Ax^_t – F, kde x^_t je bodový odhad původního stavu x_t; zbývající část, odpovídající počtu křižovatek, je doplněna zmíněnou celkovou dobou zeleného signálu pro jednotlivé křižovatky.

Výsledkem optimalizace je vektor X_t, který minimalizuje kritérium (11) a splňuje uvedená omezení (12) a (13). Pro nás to znamená, že dostaneme nastavení zelených, které minimalizuje délky kolon a přitom zachovává fyzikální i dopravní smysluplnost.

5.1.3 Jednoduchost výpočtů
Kritérium navržené podle (9) je lineární a spolu s lineárním modelem (7), (8) s dosazenými bodovými odhady parametrů a neměřených vstupů tvoří lineární optimalizační problém, pro který lze dobře použít jednoduchou a numericky stabilní metodu lineárního programování. Touto metodou je optimální řešení nalezeno v konečném počtu kroků, který nepřesáhne počet omezení pro danou úlohu. Jde o tzv. simplexovou metodu, kdy na dané ploše simplexu vygenerovaného na základě daných omezení je vyhledáno řešení, tj. bod na hranici simplexu, který minimalizuje stanovené kritérium (9).

Profesionální sady softwaru obsahují funkce pro lineární programování, které pracují v mnohem menším počtu kroků tak, že mnohoúhelník prohledávají efektivněji než vrchol po vrcholu. Tyto metody jsou rovněž odolné proti stavům, kdy je optimum mnohoznačné nebo cykluje (tj. přeskakuje mezi několika stavy). Jestliže má mnohoúhelník omezení nulovou plochu, řešení neexistuje. To je ale závada v zadání, a nikoli v řešení. Tato situace v našem případě může nastat pouze výjimečně, např. při počátečním ladění parametrů v identifikaci. Experimenty ukázaly, že potom zcela postačí ponechat řešení z minulého kroku. Parametry se doladí a zadání je opět v pořádku.

5.2 Řízení na ustupujícím horizontu
Naznačené řízení, kdy v každém časovém kroku proběhne optimalizace, ale může být nebezpečné. To, co je optimální pro přítomnost, nemusí být optimální z hlediska budoucího vývoje. Jednoduše řečeno, statické optimální řízení může být takové, že ve snaze dosáhnout všeho v jednom kroku připraví pro další vývoj systému tak nepříznivé podmínky, že může dojít až k jeho nestabilitě. Proto je vhodné počítat řízení ne pouze pro jeden, ale pro několik kroků dopředu. Potom je možné realizovat právě jen první krok ze spočítané posloupnosti řídicích zásahů, opravit nově odhadnuté parametry a pokračovat stejným způsobem dále. Tomuto způsobu optimalizace se říká řízení na ustupujícím horizontu, kdy se konečný horizont pro optimalizaci postupně sune před aktuálním okamžikem.

V popisovaném případě byla pro postup zvolena nejjednodušší cesta, tedy s využitím stávajícího modelu. Pro výpočty délek kolon v budoucích okamžicích jsou však třeba budoucí hodnoty dat (vstupních intenzit dopravních toků). Jejich vývoj jsme popsali pomocí regresního modelu druhého řádu a tímto modelem jsme je na uvažovaném horizontu predikovali. Řízení pro budoucí okamžiky jsme potom počítali s použitím těchto predikcí (bodových odhadů) a stávajícího modelu (resp. s parametry aktuálními v daném čase). Zvolený postup je tedy pouze určitým přiblížením k optimálnímu postupu, ukazuje se ale, že zcela postačujícím. Efekt řízení na horizontu, přestože ani nešlo o udržení stability, se prokázal ve výsledných charakteristikách řízených dat.

6. Nadřazené řízení

Lokální řízení v jednotlivých mikrooblastech může vyvolávat akce, kterými si mikrooblasti mezi sebou vzájemně „škodí“. Pro to, aby se tomuto zabránilo, je třeba nad lokální řídicími systémy postavit globální (koordinační) řídicí systém, který by dohlížel nad jednotlivými mikrooblastmi a usměrňoval jejich činnost tak, aby nebyla proti zájmu celé dopravní oblasti, kterou jednotlivé mikrooblasti tvoří. Za tímto účelem je nejprve třeba vytvořit model oblasti.

6.1 Model pro nadřazené řízení
Jde o model popisující dopravní zátěž určité oblasti tvořené několika mikrooblastmi. Dopravní zátěží je zde myšleno množství vozidel, která jsou v kolonách v jednotlivých mikrooblastech. Cílem nadřazeného řízení je zabránit nerovnoměrnosti počtu vozidel v jednotlivých mikrooblastech, s vytěsněním nadbytečných vozidel za hranice dopravní makrooblasti.

Takový model je možné vytvořit v analogii s modelem lokálním, a to s následujícím přibližným vyjádřením jeho jednotlivých prvků. Mikrooblasti představují ramena křižovatky a vozidla v celé mikrooblasti potom kolonu na tomto rameni. SSZ jsou reprezentovány SSZ těch křižovatek jednotlivých mikrooblastí, které zprostředkovávají přechod mezi sousedními mikrooblastmi, příp. mezi mikrooblastí a návazným neřízeným okolím. Pro celý makroregion je tedy nutné stanovit tzv. kritické křižovatky, které se nacházejí buď na vnitřních rozhraních mezi mikrooblastmi, nebo jsou vstupy do celé makrooblasti. Pouze tyto křižovatky ovlivňují celkové vstupy a výstupy jednotlivých mikrooblastí a jsou tedy analogií vstupních ramen mikrooblasti.

Počty vozidel v jednotlivých mikrooblastech je možné určit jako součet vozidel ve všech kolonách mikrooblasti. K tomu lze využít bodových odhadů z lokálních úrovní, které považujeme za dostatečně přesné, a tedy za známé. V nadřazené úrovni řízení tak odpadá úloha odhadování.

6.2 Nadřazené řízení
Řízení v nadřazené úrovni je opět víceméně analogií lokálního řízení, vzhledem k nepotřebnosti odhadovací fáze je však mnohem jednodušší. Na druhé straně je ale obtížnější určit rozumnou strategii pro řízení. Jsme si vědomi, že v současnosti navržená strategie rovnoměrné dopravní zátěže po celé oblasti (v analogii s lokální úrovní) nemusí být zdaleka jediná a vždy vhodná.

Nic ale nebrání formulaci několika dalších strategií a přípravě optimálního řízení pro každou z nich. Dopravní operátor by potom mohl sám volit strategii, která se mu zdá v daném okamžiku nejlepší. Jediným omezením tedy prozatím zůstává požadavek na linearitu kritéria řízení i všech omezujících podmínek, aby bylo možné opětovně využít optimalizační metodu lineárního programování.

7. Experimenty

V této kapitole ukážeme výsledky několika experimentů s výslednými odhadovacími a řídicími algoritmy. Experimenty jsou prováděny na pokusné testovací oblasti deseti křižovatek na obr. 3. Křižovatky jsou zde označeny čísly a směr jízdy v ramenech šipkami. V oblasti je celkem sedm měřených vstupů a osm měřených výstupů. Měřené vstupy jsou označeny kroužkem u příslušné šipky a měřené výstupy čtverečkem.

Obr. 3. Testovací oblast – deset křižovatek

Dopravní oblast na obr. 3 lze také chápat jako soustavu dvou mikrooblastí. První mikrooblast je tvořena křižovatkami 1 až 4, druhá křižovatkami 5 až 10. Proto jsou mezi křižovatkami 4 a 5, resp. 3 a 6 rovněž umístěny měřicí detektory. Vstupem (přesněji vstupními intenzitami) jsou v našem experimentu reálná data měřená v devadesátisekundovém intervalu v jedné z pražských oblastí. Data poskytla firma Eltodo, a. s., Praha. Systém je pod vlivem poruch v podobě šumů s nenulovými středními hodnotami, jež představují i drifty, které jsou pro systém s integračním charakterem nepříjemné.

7.1 Odhad
Pro demonstraci kvality odhadu stavu jsme pro přehlednost vybrali křižovatky 1 a 5 (obr. 3). V křižovatce 1 je sledováno rameno vstupující shora, v křižovatce 5 rameno vstupující zleva. „Reálné“ průběhy délek kolon, neboli délky získané digitální simulací dopravy v oblasti, jsou na obr. 4 vyznačeny plnou tenkou čárou. Ačkoliv se oba průběhy dosti liší, jejich tvar je snadno zdůvodnitelný. Rameno v křižovatce 1 je vstupní rameno, kam se vozidla sjíždějí v daném případě v podstatě volným proudem. Proto je v koloně dobře viditelný typický denní průběh (dopolední a odpolední špička, sedlo v poledne). Rameno z křižovatky 5 je vstupem pouze do druhé mikrooblasti dané testovací dopravní oblasti a vstupují do něj pouze vozidla z výstupního ramene křižovatky č. 4. Její vstupní rameno (zleva), které do ní jako jediné přivádí vozidla, je téměř celý den saturované, a tedy propouští vozidla v konstantním toku, který se rovná její kapacitě. Odtud plyne víceméně rovnoměrný nárůst kolony na grafu vpravo na obr. 4.

Obr. 4. Korekce odhadu po poruše (vlevo kolona na vjezdu, vpravo kolona uprostřed oblasti, odhad označen křížkem

Při experimentu byly odhadovány délky kolon s periodou pět minut, a to v celé oblasti. Bez poruch se samozřejmě kolony počítaly zcela správně podle vztahu (1). Předmětem testu byla otázka, co se stane, jestliže přijde porucha, o které se vztah (1) „přímo nedozví“, např. vynulování části stavu (tj. délek kolon), nebo velká porucha průběžného odhadu stavu. V tomto okamžiku má přispět na pomoc vztah (3). Podle něj potom neodpovídá obsazenost na strategickém detektoru odhadu délky kolony (právě vynulovanému), a přes Kalmanův filtr má dojít k jeho korekci. K vynulování stavu došlo při experimentu kolem kroku 150, jak je patrné na průběhu odhadů délek kolon, které jsou označeny na obrázku (4) křížky. Navíc odhady byly vynulovány v celé oblasti. Z obrázku je také vidět, že ke korekci podle očekávání dochází okamžitě a odhad opět pokračuje na správných hodnotách.

7.2 Řízení
Testy řízení byly provedeny opět na celé testovací oblasti podle obr. 3. Pro přehlednost však jsou ukázány výsledky jen v první mikrooblasti, která zahrnuje křižovatky 1 až 4 (viz obr. 5). Každá křižovatka je reprezentována čtyřmi obrázky. Obrázek uprostřed s kroužkem naznačuje vždy střed křižovatky, obrázky kolem (jsou tři, protože všechny křižovatky jsou tříramenné) reprezentují vstupní ramena této křižovatky. Obrázek s křížkem označuje jednosměrné výjezdní rameno, kde se kolona nemůže tvořit, obrázek s grafem představuje vstupní rameno, kde se kolona v důsledku SSZ vyskytuje.

Obr. 5. První testovací oblast – pevné a optimální řízení

V grafu je zachycen denní průběh délky kolony: přerušovanou tmavší čárou je zachycena délka kolony s konstantním řízením, plná světlejší čára představuje délku kolony při řízení navrženým řídicím systémem. Všimněme si zejména ramen první křižovatky. Při řízení s konstantní zelenou bylo vodorovné rameno celý den volné a svislé rameno zahlcené. Navržené řízení se snaží velké kolony zmenšovat. To ale nelze absolutně. Jediným možným řešením je přerozdělit zelené mezi obě ramena tak, aby celková situace byla příznivější. Výsledkem je sice určité zvětšení kolon ve vodorovném rameni, avšak doprovázené výrazným zmenšením kolon v rameni svislém.

8. Závěr

Popsaný systém dopravního řízení, určený pro městský provoz, je zatím jen prvním krokem v tomto směru. Jako takový byl záměrně volen co možná nejjednodušeji. Volba fyzikálního modelování vedoucí na velmi jednoduché vztahy (1) a (3), s jejichž pomocí je následně sestaven stavový model křižovatky (7) a (8), jeho odhad pomocí Kalmanova filtru a následná optimalizace pomocí lineárního programování jsou velmi jednoduchými a stabilními postupy.

Snad jediná, zatím ne zcela jasná záležitost, jsou nelineární odhady. Ty z větší části řadíme do oblasti budoucího výzkumu a vývoje.

V současném stádiu lze jednoznačně konstatovat, že pro dopravní oblasti s dostatkem strategických detektorů na vstupních ramenech do řízené oblasti pracuje navržené řízení dobře a spolehlivě. Při znalosti dopravních parametrů oblasti toto řízení vyžaduje ladění jen uživatelských parametrů, a to v minimálním počtu.

Ačkoli je řízení zvoleno jako velmi jednoduché, je celý systém řízení značně složitý. Je to především tím, že samotný dopravní systém je složitý. Je třeba si uvědomit, že oblast je složena z křižovatek, křižovatky z ramen, ramena z pruhů (vstupních a výstupních, různých směrů) atd. A navíc napříč vším jdou fáze cyklu SSZ. Toto optimálně naprogramovat představuje poměrně náročnou úlohu, která vyžaduje velkou míru opatrnosti a důsledné testování. Potom je možné získat jednoduše ovladatelný systém, který se z dosavadních simulačních experimentů zdá být účinným.

Literatura:
[1] De FREITAS, J. F. G. – NIRANJAN, M. – GEE, A. H. – DOUCET, A.: Sequential Monte Carlo methods for optimisation of neural network models. Technical report, Cambridge, England, 1998. CUED/F-INFENG/TR-328.
[2] HOMOLOVÁ, J. – NAGY, I: Traffic model of a microregion. In: Preprints of the 16^th World Congress of the International Federation of Automatic Control, Prague, July 2005 (ed.: Horáček, P. – Šimandl, M. – Zítek, P.) s. 1–6.
[3] KALMAN, R. E.: New results in linear filtering and prediction theory. Journal of Basic Engineering, Transactions ASME, 1960, s. 34–45.
[4] KRATOCHVÍLOVÁ, J. – NAGY, I.: Traffic control of microregion. In CMP ’04 Multiple Participant Decision Making, Theory, algorithms, software and applications (ed.: Andrýsek, J. – Kárný, M. – Kracík, J.) Advanced Knowledge International, Adelaide, May 2004, s. 161–171.
[5] NORGAARD, M. – POULSEN, N. K. – RAVN, O.: New developments in state estimation for nonlinear systems. In Automatica, 36 (11), 2000, s. 1627–1638.
[6] PECHERKOVÁ, P. – DUNÍK, J.: Setting of covariance for Kalman filter. In Proceedings of the 11^th International Conference of Hong Kong Society for Transportation Studies, Sustainable Transportation, Hong Kong, December 2006, p. 739.
[7] PŘIKRYL, J. – NAGY, I. – HOMOLOVÁ, J.: Probabilistic model of a traffic network. In Modelling 2005, Book of Abstracts. University of West Bohemia in Pilsen, Plzeň 2005, s. 1–2.
[8] ROBERT, C. P. – CASELLA, G.: Monte Carlo Statistical Methods. Springer Verlag, 1999.
[9] ŠIMANDL, M. – DUNÍK, J.: Multi-step prediction and its application for estimation of state and measurement noise covariance matrices. Technical report. University of West Bohemia in Pilsen, Faculty of Applied Scienses, Department of Cybernetics, Plzeň 2006.
[10] ŠIMANDL, M. – STRAKA, O.: Nonlinear estimation by particle filters and cramérrao bound. In Preprints of the 15^th Triennial World Congress of the IFAC, Barcelona, July 2002.

doc. Ing. Ivan Nagy, CSc., Ing. Jitka Homolová, Ing. Pavla Pecherková,
ústav aplikované matematiky, Fakulta dopravní ČVUT v Praze

lektoroval: doc. Ing. Pavel Drdla, Ph.D.,
Dopravní fakulta Jana Pernera, Univerzita Pardubice