Samochody stojące w długich kolejkach, sfrustrowani kierowcy, nerwowo szukający możliwości szybkiego dotarcia do celu podróży – oto obrazek spotykany w dużych miastach niemal codziennie. Korki drogowe to zmora mieszkańców wielu metropolii, szczególnie uciążliwe są dla podróżujących do pracy, którzy codziennie tracą czas, nerwy i pieniądze. Szacuje się, że w siedmiu największych miastach w Polsce kierowcy tracą rocznie z powodu korków aż 3,8 miliarda złotych. Poszkodowane jest właściwie całe społeczeństwo: marnowane paliwo, zanieczyszczane środowisko, smog wpływa negatywnie na zdrowie, do tego dochodzi szkodliwy hałas. Z powodu spóźnionych, zmęczonych psychicznie i fizycznie pracowników firmy nie funkcjonują z pełną wydajnością. Zagwozdkę mają też inżynierowie ruchu projektujący sieć drogową i transport publiczny. Czy nauka może pomóc wygrać trudną walkę z korkami?

Aby się o tym przekonać, należy się zagłębić w istotę problemu i zrozumieć, czemu tworzą się korki. Od razu nasuwa się przypuszczenie: pewnie jest za dużo samochodów w porównaniu do przepustowości dróg. Być może więc należy zredukować liczbę pojazdów na drogach? Można np. przekonywać ludzi, aby korzystali z komunikacji publicznej, wybrali spacer lub rower, z korzyścią dla zdrowia. Na pewno warto takie postawy promować, ale podróżnym często zależy na czasie i nie mogą sobie pozwolić na przejazd rowerem lub spacer do przystanku. W deszczową pogodę podróż samochodem jest przyjemniejsza. Ponadto wiele osób odczuwa potrzebę większego komfortu lub pochwalenia się swoim samochodem, więc niestety liczba pojazdów na drogach nie spada. Może więc podziałają bardziej rygorystyczne rozwiązania, np. wprowadzenie opłat za wjazd do pewnych obszarów miast i za parkowanie, czy wręcz zakaz wjazdu do niektórych stref w pewne godziny i dni tygodnia? Takie metody funkcjonują w miastach i są dość skuteczne, prowadzi się nawet prace badawcze na temat optymalnego wyznaczania płatnych stref. Mimo to liczba pojazdów na drogach wcale nie maleje, potrzeba komfortu wygrywa z drenażem portfela, a chcemy przecież, aby ludzie mogli komfortowo podróżować i nie trzeba było zakazywać używania pojazdów.

W takim razie może wybudować więcej dróg? To często pomaga, ale infrastrukturę drogową należy projektować z głową, najlepiej ze wsparciem profesjonalnych programów komputerowych, które korzystając z zaawansowanych modeli matematycznych potrafią symulować ruch w różnych warunkach i mogą np. przewidzieć, co dokładnie wydarzy się w sytuacji, gdy wybudowana zostanie nowa droga, gdy zmienimy ustawienia sygnalizacji świetlnej lub gdy wypadek zablokuje główną ulicę. Sytuacje te należy sta-rannie zbadać przed podjęciem decyzji o poświęceniu dużych środków na inwestycje infrastrukturalne. Znane są przypadki, gdy wybudowanie nowej drogi pogorszyło ruch, zamiast go poprawić. Większość kierowców zaczęła bowiem używać nowej drogi, pozornie lepszej, lecz przez to bardziej zatłoczonej. Zjawisko to jest znane jako Paradoks Braessa i może być matematycznie wyjaśnione dzięki teorii gier. Okazuje się, że równowaga Nasha (stan, w którym żadnemu kierowcy nie opłaca się zmienić trasy) nie musi być wcale optymalnym układem strategii z punktu widzenia globalnego ruchu.

Symulator ruchu drogowego

Sytuacja jest więc trudna i delikatna: nie można bez namysłu i starannych badań wprowadzać zmian w sieci drogowej – nawet mała, niepozorna zmiana może prowadzić do poważnych konsekwencji. Zjawisko to, znane jako „efekt motyla” lub „wrażliwość na warunki początkowe”, jest typowe dla złożonych systemów, w których wiele komponentów pozostaje w interakcji. Takim właśnie systemem jest ruch drogowy w mieście. Trzeba więc się wspierać profesjonalnymi analizami, a do takich badań przydają się zaawansowane programy komputerowe, np. Traffic Simulation Framework (TSF), który opracowuję w ramach badań naukowych. Sieć drogowa jest w nim reprezentowana jako graf skierowany: zbiór punktów i łączących je krawędzi, po których mogą się poruszać pojazdy zgodnie z określonymi regułami ruchu. Reguły te mogą być deterministyczne lub stochastyczne. Korzystam np. z probabilistycznych automatów komórkowych, ciekawych struktur matematycznych odkrytych przez Stanisława Ulama i Johna von Neumanna w czasie ich pobytu w Los Alamos.

TSF, dzięki efektywnej implementacji, jest w stanie symulować w czasie rzeczywistym ruch setek tysięcy pojazdów w sieci drogowej dużych miast (np. Warszawa, Pekin), wizualizując jednocześnie przebieg symulacji (Rys. 1), dzięki czemu można obserwować miejsca powstawania korków i ewolucję ruchu drogowego. Program znalazł już wiele zastosowań, m.in. w pracach dotyczących predykcji i analizy ruchu drogowego. W przyszłości może on służyć m.in. do projektowania sieci drogowej, planowania objazdów, remontów, imprez masowych, komunikacji publicznej, scenariuszy ewakuacji, do znajdowania optymalnych lokalizacji parkingów, stacji ładowania pojazdów elektrycznych, budynków użyteczności publicznej (np. szpitali, szkół, remiz strażackich). W pewnym sensie można byłoby dzięki niemu projektować miasta, podobnie jak np. w grze Sim City. Można będzie doradzać, gdzie opłaca się wybudować siedzibę dużej firmy (np. logistycznej) lub centrum handlowe, aby zapewnić efektywny dojazd i dużą liczbę klientów, nie korkując nagle połowy miasta. Mając odpowiednie dane na temat bieżącego ruchu, da się w czasie rzeczywistym prognozować jego ewolucję, co może się przydać do lepszego szacowania czasów dojazdu i znaleźć zastosowanie w systemach nawigacji samochodowej, systemach informowania podróżnych (np. Google Maps, JakDojade.pl) i w korporacjach taksówkarskich, do lepszego zarządzania flotą. Ciekawym zastosowaniem może być też szacowanie ryzyka wystąpienia korków na potrzeby modeli ubezpieczeń przed korkami – takie rozwiązania już się pojawiają.

Obecnie TSF służy mi w pracy naukowej głównie do oceny jakości konfiguracji sygnalizacji świetlnej, a więc: do zadanych ustawień uruchamiana jest symulacja komputerowa, która może obliczyć np., ile będą wynosiły czasy czekania pojazdów na czerwonym świetle. Dzięki temu można porównywać różne ustawienia sygnalizacji i wybierać najlepsze.

Algorytmy i sieci neuronowe

Czy właśnie znaleźliśmy idealne rozwiązanie do zarządzania ruchem drogowym w miastach? Jest tu pewien problem: możliwych konfiguracji sygnalizacji świetlnej mamy bardzo dużo, w mieście takim jak Warszawa to liczba rzędu 120800, znacznie więcej niż szacowana liczba atomów w obserwowalnym Wszechświecie (1080), liczba możliwych rozgrywek w grze w szachy (10120) lub w Go (10700). Wydaje się, że znalezienie optymalnej konfiguracji to szukanie igły w stogu siana. W istocie jest to jeszcze trudniejszy problem, gdyż stóg siana ma mniej ździebeł niż liczba atomów w obserwowalnym Wszechświecie, a więc też mniej niż liczba możliwych konfiguracji sygnalizacji świetlnej. Być może jednak istnieje jakiś sprytny sposób, aby tę jedną konfigurację znaleźć szybko? Okazuje się, że może być z tym kłopot, bo dla prostych matematycznych modeli ruchu udowodniono, że zagadnieniejest NP-trudne, co implikuje, że najprawdopodobniej taki szybki algorytm nie istnieje.

Być może nie potrzebujemy jednak rozwiązania optymalnego? Może zadowoli nas rozwiązanie suboptymalne, trochę gorsze niż to najlepsze, ale nieznacznie (np. o 0,1%), a za to wystarczająco dobre (np. gwarantujące niemalże, że nie powstanie korek), a do tego łatwe do znalezienia? Tu możliwości są znacznie większe, a z pomocą mogą przyjść tzw. metaheurystyki - algorytmy przeszukiwania przestrzeni możliwych rozwiązań. Właśnie takie metody badam w mojej pracy naukowej, a przykładem jest algorytm genetyczny, inspirowany procesem doboru naturalnego. Podobne metody stosowane były w programach komputerowych, które potrafiły wygrywać w szachy lub Go z arcymistrzami. Do gry w szachy takie programy pojawiły się w latach 90. XX wieku, w przypadku gry w Go dopiero w 2016 roku powstał program AlphaGo, który po raz pierwszy pokonał najlepszego na świecie gracza. Jak długo trzeba będzie czekać, aż programy komputerowe zaczną skutecznie radzić sobie z zarządzaniem ruchem drogowym? Biorąc pod uwagę jedynie rozmiar przestrzeni możliwych rozwiązań, otrzymujemy problem trudniejszy od gry w Go.

Sytuacja jest jeszcze bardziej skomplikowana, bo w przypadku rzeczywistego ruchu pojawia się filozoficzne pytanie: co to dokładnie znaczy, że dana konfiguracja jest optymalna? Możemy przecież znaleźć jakieś pozornie dobre ustawienie sygnalizacji świetlnej, które będzie świetne w przypadku typowego, regularnego ruchu z powtarzalnymi wzorcami zachowań (np. w dni robocze rano kierowcy jadą do pracy, po południu wracają do domu lub jadą na zakupy), ale jeśli nagle wypadek zablokuje przejazd przez ważną ulicę? Ruch drogowy w mieście może się diametralnie zmienić, kierowcy zaczną szukać alternatywnych przejazdów, duże natężenie ruchu pojawi się w innym miejscu, aktualne ustawienie sygnalizacji świetlnej przestanie być optymalne. Czy będziemy w stanie poradzić sobie w takiej sytuacji?

Jest to bardzo duże wyzwanie, algorytmy metaheurystyczne cechują się bowiem dużą złożonością obliczeniową, a na dodatek każdą konfigurację sygnalizacji świetlnej należy zbadać za pomocą symulacji komputerowej. W istocie jest to skomplikowany problem. Do jego rozwiązania stosuję m.in. sieci neuronowe (ta metoda z kolei jest inspirowana procesem uczenia się ludzkiego mózgu) oraz klastry o dużej mocy obliczeniowej. Wyniki są bardzo obiecujące (m.in. skracanie czasu czekania na czerwonym świetle o ponad 18% w przypadku sieci drogowej Warszawy), ale nawet jeśli uda się pokonać aktualne problemy związane z dużą złożonością obliczeniową, pojawi się kolejny dylemat, czy wyniki symulacji komputerowej są zgodne z rzeczywistością. W szczególności, czy konfiguracja sygnalizacji świetlnej, optymalna w symulacji komputerowej, okaże się dobra w rzeczywistym ruchu drogowym.

Pojazdy autonomiczne

Jest to kolejne wyzwanie, gdyż zachowanie kierowcy bywa trudne do przewidzenia i zamodelowania matematycznego. Nadzieja w tym, że interesują nas głównie wartości zagregowane, zachowanie dużej liczby pojazdów, na które pojedynczy samochód może nie mieć wpływu (istnieje np. pewien przedział gęstości pojazdów, powyżej którego droga zawsze się korkuje, a poniżej którego ruch jest swobodny). „Efekt motyla” pokazuje jednak, że nie zawsze musi tak być, wystarczy bowiem, że kierowca spowoduje wypadek i proces optymalizacji ruchu drogowego należałoby rozpocząć od nowa.

Są to bardzo skomplikowane problemy. Dużą nadzieję na ich uproszczenie zapowiadają pojazdy autonomiczne, sterowane przez komputer, a nie przez człowieka, działające zgodnie z określonym algorytmem (uwzględniającym również interakcje z otoczeniem), więc ich zachowanie można by łatwiej przewidzieć poprzez symulację komputerową. Pod wieloma względami takie pojazdy są przyszłością transportu, mogą zapewnić znacznie większy poziom bezpieczeństwa (będą jeździć zgodnie z przepisami, mieć więcej „sensorów” niż człowiek, ich czas reakcji będzie krótszy, nie zmęczą się i nie zdekoncentrują), umożliwią transport osobom niepełnosprawnym, starszym i dzieciom, a także szybsze dostarczanie przesyłek. Właśnie pojawiają się na świecie pierwsze autonomiczne taksówki, realizacja idei „mobilności na żądanie”, która może sprawić, że posiadanie pojazdów stanie się nieopłacalne, co zredukuje liczbę potrzebnych miejsc parkingowych (a szacuje się, że ruch w centrach miast jest generowany w ok. 30% przez kierowców szukających miejsca parkingowego). Pojazdy autonomiczne będą mogły się również komunikować między sobą, aby synchronizować pewne manewry, np. wyprzedzanie i bezkolizyjny przejazd przez skrzyżowanie, co może sprawić, że sygnalizacje świetlne przestaną być potrzebne. Do tego jednak jeszcze daleka droga.

Mgr Paweł Gora, matematyk, informatyk, doktorant informatyki na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego