Celem projektu badawczego TRAVOLUTION była poprawa ruchu drogowego miasta Ingolstadt. W związku z tym przeprowadzono dwa działania: online-optymalizację całej sieci sygnalizacji ulicznej przy pomocy genetycznych algorytmów oraz komunikację pomiędzy sygnalizacją świetlną a pojazdem dla indywidualnej informacji kierowcy.

Jednym z dzisiejszych wyzwań jest walka ze wzrastającym obciążeniem miast ruchem drogowym i związanym z nim zanieczyszczeniem środowiska. Coraz wydajniejsza technika systemów sterowania ruchem drogowym w ostatnich latach i jednocześnie możliwość sieciowego komunikowania się pojazdów pozwala przyjmować to wyzwanie.

Sygnalizacje świetlne stanowią najważniejszy element w zarządzaniu ruchem drogowym w sieciach miast. Spowodowane przez sygnalizacje czasy postoju i zatrzymań odgrywają znaczącą rolę w przebiegu ruchu drogowego i korelują one bezpośrednio z wydzielaniem substancji szkodliwych poprzez pojazdy. Projekt badawczy TRAVOLUTION¹ miał na celu polepszenie ruchu drogowego dwoma sposobami:

• online-optymalizacja całej sieci sygnalizacji ulicznej przy pomocy genetycznych algorytmów,
• komunikacja pomiędzy sygnalizacją świetlną a pojazdem dla indywidualnej informacji kierowcy.

W pierwszym założeniu wynaleziono innowacyjną metodę optymalizacji w czasie rzeczywistym, która naśladuje proces ewolucji w przyrodzie. Stąd pochodzi nazwa projektu TRAVOLUTION, to kombinacja angielskich słów traffic i evolution.

Drugie założenie wykorzystuje komunikację sygnalizacji świetlnej z pojazdem w celu przekazania mu informacji o programie sygnalizacji świetlnej. Informacje te zostają w pojeździe przetwarzane i np. w formie polecenia optymalnej prędkości jazdy przekazane kierowcom,  aby zapobiec zbędnemu zatrzymaniu się. Temat komunikacji pomiędzy sygnalizacją świetlną a pojazdem nie będzie tu dalej rozpatrywany.

TRAVOLUTION był realizowany od kwietnia 2006 r. do czerwca 2008 r. Uczestnicy projektu to: AUDI AG (oddział Vorentwicklung Fahrzeugkonzepte), GEVAS software GmbH, Wydział Planowania i Techniki Ruchu Drogowego Uniwersytetu Technicznego w Monachium we współpracy z Urzędem do Spraw Zarządzania Ruchem Drogowym i Geoinformacji miasta Ingolstadt. Projekt ten wspierało bawarskie ministerstwo gospodarki, infrastruktury, ruchu drogowego i technologii.

Online-Optymalizacja

W ramach projektu badawczego TRAVOLUTION wynaleziono genetyczny algorytm (GA) do optymalizacji całej sieci sygnalizacji ulicznej, który został zaimplementowany do adaptacyjnego sieciowego sterowania ruchem BALANCE² i wprowadzony w mieście Ingolstadt.

Rysunek 1 przedstawia całość procesu optymalizacji. Proces składa się z następujących głównych elementów:

• Model ruchu drogowego i model działania
• Funkcja celu
• Metoda optymalizacji (GALOP)

Model ruchu drogowego tworzy, z mierzonych wartości natężeń ruchu na przekrojach pomiarów, wewnętrzną przestrzenno-czasową reprezentację aktualnego stanu ruchu drogowego. Model działania, który bazuje na modelu ruchu drogowego, służy do ustalenia wskaźników oddziaływania, które z kolei stanowią wartość wejściową dla funkcji celu. Ona dostarcza jako wynik kondycję jednego indiwiduum, tzn. jednej skalarnej wartości jakości dla jednej alternatywy sterowania (= plan sygnalizacyjny sieci). Kondycja jest natomiast wartością wejściową dla procesu optymalizacji (GALOP), który dla całej sieci optymalizuje plany sygnalizacji i jako wynik podaje najlepszy wariant sterowania (= najlepszy indywiduum) dla aktualnego przebiegu ruchu drogowego. Wszystkie te główne elementy wraz z ramowym planem sygnalizacji tworzą adaptacyjne sterowanie siecią BALANCE, które co 5 minut dostarcza nowy ramowy plan sygnalizacji (poziom taktyczny). Opierając się na nim, na pojedynczych węzłach, sterowanie akomodacyjne reaguje w interwałach sekundowych na krótkoterminowe zmiany zapotrzebowania w przebiegu ruchu drogowego (poziom lokalny).

Model ruchu drogowego i model działania
Na początku procesu sterowania występuje rejestrowanie aktualnego stanu ruchu drogowego poprzez prowadzenie pomiarów w sieci drogowej. Dla aktualnego interwału obliczeń detektory rejestrują ruch drogowy w obszarze sterowania w postaci pomiarów przekrojowych. Wartości zmierzone przez detektory poddawane są testowi zasadności i agregowane w odniesieniu do obszaru.

Z wyniku pomiarów detektorów tworzy się przy pomocy makroskopicznego modelu ruchu drogowego (makromodel) wewnętrzną przestrzenno-czasową reprezentację aktualnego natężenia ruchu drogowego. Następnie z makroskopiczych parametrów ruchu tworzy się przy pomocy mesoskopicznego modelu ruchu strumienia (mesoodel) dla wszystkich tras sieci sterowanej cyklicznie, rasterowane co sekundę profile strumieni.

Przy pomocy modelu działania prognozuje się wpływ poszczególnych alternatyw sterowania dla następnego interwału czasowego. Jako istotne parametry działania można obliczyć czasy postoju, ilość zatrzymań i długość korków. Parametry działania są tworzone poprzez dwa modele częściowe: z profilów strumieni ruchu, które zostały stworzone przy pomocy mesomodeli, oblicza się, z uwzględnieniem wpływu sygnalizacji świetlnych, czasu przejazdu i rozproszenia potoków, deterministyczny udział tych parametrów działania. Stochastyczne wahania i przeciążenia odtwarza się przy pomocy modelu kolejek. Poprzez czasową rozdzielczość w interwałach sekundowych możliwe jest modelowanie wpływów długości czasów zielonych na ruch i czasów przesunięć pomiędzy sąsiednimi sygnalizacjami. Suma działań z deterministycznego i stochastycznego modelu wchodzi do funkcji celu.

Funkcja celu
W funkcji celu odwzorowuje się cele optymalizacji. Obejmuje ona parametry działania grup sygnalizacji, które pochodzą z modelu ruchu i działania oraz dostarcza jako wynik kondycję (= wartość funkcji celu) indywiduum, tzn. skalarną wartość jakości dla jednej alternatywy sterowania.
W ramach projektu badawczego jako cel ustalono minimalizację czasów postoju. Odpowiednio zdefiniowano funkcję celu:

przy czym
Α = waga dla grupy sygnalizacyjnej sg
W = czas postoju przed grupą sygnalizacyjną sg

Poprzez ustalenie wag czasów postoju można uwzględnić polityczne dyrektywy jak np. ze względu na ustalony kierunek koordynacji. Wykorzystuje się dodatkowo ilość zatrzymań, można dobierać wagi w ten sposób, że wartość funkcji celu odzwierciedla zużycie paliwa albo emisji.

Metoda optymalizacji GALOP
BALANCE wykorzystywał dotychczas algorytm Hill-Climbing (HC) jako metodę optymalizacji. W ramach projektu TRAVOLUTION i GALOP stworzono nową metodę optymalizacji, która została zaimplementowana do BALANCE. Wyróżniającą się zaletą genetycznego algorytmu jest możliwość jednoczesnej optymalizacji wszystkich parametrów sterowania.

Kodowanie parametrów sterowania ma wyjątkową ważność dla jakości i funkcjonowania optymalizacji. Pod pojęciem kodowania rozumie się przy algorytmach genetycznych tłumaczenie (w naszym przypadku) planów sygnalizacyjnych na indiwiduum, które algorytm genetyczny jest w stanie przetwarzać. Dla danego zadania istotne dla kodowania są następujące warunki brzegowe:

• Wytyczne pod względem planowania (dozwolone czasy trwania cyklów, dozwolone kolejności faz)
• Obowiązujące warunki (czasy międzyzielone, minimalne czasy zielonego)
• Uwarunkowania lokalnego sterowania akomodacyjnego

Na rysunku 2 przedstawiono warunki brzegowe sterowania luką czasową na podstawie wartości zmierzonej, które w Niemczech jest często spotykane.

Ramowy plan sygnalizacyjny dla lokalnego sterowania luką czasową na podstawie  wartości zmierzonej ustala się poprzez granice T-czasów (T_iA , T_iB).

Dla całej sieci optymalizuje się najpóźniejsze punkty startu przejść faz  T_iB dla wszystkich sygnalizacji świetlnych w obszarze sterowania. Aby zapewnić funkcjonalność lokalnego sterowania, podano dla T_iB interwał [T_iB^min ; T_iB^max], w którym musi się zmieścić  T_iB .

W metodzie optymalizacji GALOP alternatywy sterowania są reprezentowane poprzez tzw. kodowanie w postaci indiwiduów. Jedno indiwiduum ma następującą postać:

Zawiera ono jeden gen φ dla wspólnego czasu trwania cyklu, jak i n tzw. chromosomy dla n punktów węzłów sieci, która ma być optymalizowana. Każdy chromosom składa się z genu σ do ustalenia kolejności faz, z genu ω dla globalnego offsetu, z genu ο dla lokalnego offsetu, jak i z m genów θ dla czasów trwania faz albo punktów startu przejść faz. Każdy gen przyjmuje wartość rzeczywistą pomiędzy 0 i 1.

Z powodu ograniczeń czasów przesunięć i warunków lokalnych sterowań akomodacyjnych, geny dla globalnego i lokalnego offsetu w realizowanej implementacji algorytmu w TRAVOLUTION nie zostały uaktywnione. Stworzono specjalne sekwencyjne kodowanie, którego zasada działania jest opisana w BRAUN i KEMPER (2008) oraz w BRAUN (2008). Ta metoda integruje ponad obowiązującymi warunkami, jak przestrzeganie czasów międzyzielonych, również bezpośrednio warunki lokalnego sterowania, poprzez co powstają tylko ważne indywidua.

Konstrukcja operatorów genetycznego algorytmu i ich parametryzacja mają duży wpływ na jakość procesu optymalizacji. Ze względu na to, że jedno indiwiduum reprezentuje wszystkie węzły, operatory muszą być dopasowane do kodowania. Jeden węzeł w indywiduum jest przedstawiony jako zestaw genów (chromosomów). Przy rekombinacji standardowo wykorzystuje się losowo wybrane, pojedyncze geny chromosomów indiwiduów rodzicielskich do stworzenia indiwiduów potomstwa. Operatora rekombinacji rozszerzono w ten sposób, że przeprowadzi on rekombinację z prawdopodobieństwem p także na wszystkich chromosomach (węzłach). Przy mutacji genów trzeba zwrócić uwagę na to, że mutacja odbywa się w granicach T-czasów. Z tego powodu można ustawić długość kroku mutacji dla każdego genu indywidualnie albo dla całego indiwiduum. W razie potrzeby długość kroku mutacji może się dostosować w sposób adaptacyjny.

W przeciwieństwie do algorytmu genetycznego, który optymalizuje wszystkie parametry jednocześnie, algorytm Hill-Climbing przetwarza parametry sterowania w sposób sekwencyjny. Tak stworzona alternatywa sterowania zależy od wybranej kolejności. Jeżeli tylko dla jednego parametru sterowania nie znajdzie się lepszej alternatywy sterowania, to szukanie przeprowadzone jest w innym kierunku. Przykład dla odmiennego zachowania algorytmu Hill-Climbing i algorytmu ewolucyjnego dla tej samej sieci przy dokładnie tym samym zapotrzebowaniu komunikacyjnym przedstawia rysunek 3.

Algorytm Hill-Climbing rozpoczyna obliczenia planami sygnalizacyjnymi sterowania bazowego, stanowiącymi wynik startowy, który osiągnął już relatywnie dobrą jakość. W przeciwieństwie do HC algorytm ewolucyjny startuje z przypadkową populacją. Najlepsze indiwiduum pierwszej generacji jeszcze nie osiąga takiej jakości (po 175 ocenianych indiwiduach), przy czym algorytm Hill-Climbing po 2 404 ocenianych alternatywach sterowania skończy jednak obliczenia przy wartości jakości 241 742, ze względu na to, że nie znajdzie lepszej alternatywy (zahaczył sie w lokalnym optimum). Ewolucyjny algorytm osiągał już po 2 300 indiwiduach w 18 generacji kondycję o wartości 236 556. Po 80 generacjach i 10 050 ocenianych alternatywach sterowania, GALOP osiągał kondycję o wartości 186 559.

Herwig Wulffius

Przypisy:
¹ TRAVOLUTION jest projektem badawczym wspieranym przez Republikę Bawarską, zakończony powodzeniem w czerwcu 2008 r. Partnerami projektu są: miasto Ingolstadt, Urząd do Spraw Zarządzania Ruchem Drogowym i Geoinformacji, GEVAS software,  Audi AG oddział Ruch Drogowy i Środowisko, Uniwersytet Techniczny w Monachium, Wydział Planowania i Techniki Ruchu Drogowego.
² BALANCE jest oprogramowaniem firmy GEVAS software GmbH, Monachium. BALANCE (BALancing Adaptive Network Control mEthod) pierwotnie wynaleziono na TU Monachium (FRIEDRICH, 1999) w ramach unijnych projektów badawczych Munich Comfort i TABASCO. W roku 2002 firma  GEVAS software GmbH przejmowała dalszy rozwój BALANCE i wprowadziła produkt do zastosowań w praktyce.

Tweet