PL 
EnglishDomyślny
Українська🚌 Predyktor trasy i ETA transportu publicznego
Interaktywny symulator transportu publicznego: autobusy poruszają się po rzeczywistej sieci tras, gdy algorytm Dijkstry oblicza najkrótsze ścieżki, a model na żywo przewiduje czas przyjazdu względem rzeczywistości — obserwuj, jak błąd przewidywania maleje w miarę zbliżania się autobusów.
O tej symulacji
Za każdym razem, gdy aplikacja transportowa mówi ci, że autobus jest „4 minuty od ciebie”, za kulisami współpracują ze sobą dwie bardzo różne dziedziny informatyki. Pierwsza to przeszukiwanie najkrótszej ścieżki: mając sieć przystanków i czasów przejazdu, znajdź najszybszą trasę z A do B. Druga to przewidywanie przyjazdu na żywo: mając informację o tym, jak faktycznie zachowywał się ruch ostatnio, oszacuj, ile naprawdę zajmie kolejny odcinek podróży — ponieważ drukowany rozkład jazdy jest zawsze tylko wstępnym przypuszczeniem. Ta symulacja implementuje obie te rzeczy naprawdę, na sieci tras z 16 przystankami. Kliknij dowolne dwa przystanki, aby uruchomić prawdziwe przeszukiwanie najkrótszej ścieżki algorytmem Dijkstry między nimi: obserwuj, jak front „ustalonych” przystanków rozszerza się na zewnątrz, a ostateczna trasa podświetla się po znalezieniu. Tymczasem do czterech autobusów krąży nieprzerwanie po stałych trasach. Każda krawędź w sieci ma losowo zmieniający się współczynnik ruchu, a model wykładniczej ważonej średniej kroczącej na żywo uczy się bieżącego czasu przejazdu dla każdej krawędzi od każdego autobusu, który ją przemierza — więc przewidywane ETA dostosowują się do warunków zamiast podążać za stałym harmonogramem. Bieżący wykres śledzi, jak daleko przewidywania odbiegają od rzeczywistości w miarę zmiany zmienności ruchu.
Najczęściej zadawane pytania
Jak algorytm Dijkstry faktycznie oblicza najkrótszą trasę?
Algorytm Dijkstry utrzymuje bieżącą najlepszą znaną odległość do każdego przystanku, zaczynając od 0 dla źródła i nieskończoności wszędzie indziej. Na każdym kroku wybiera nieodwiedzony przystanek o najmniejszej znanej odległości, oznacza go jako ustalony i relaksuje każdą krawędź z niego wychodzącą: jeśli przejście przez ustalony przystanek daje krótszą ścieżkę do sąsiada niż jego obecna najlepsza, ta najlepsza odległość i jej poprzednik są aktualizowane. Ponieważ przystanki są zawsze ustalane w kolejności rosnącej odległości, po ustaleniu przystanku jego odległość nigdy nie może się już poprawić, a algorytm zatrzymuje się, gdy tylko cel zostanie ustalony. Cofnięcie się przez wskaźniki poprzedników od celu odtwarza faktyczną najkrótszą ścieżkę.
Czym jest model ETA oparty na wykładniczej ważonej średniej kroczącej i dlaczego bije statyczny rozkład jazdy?
Statyczny rozkład jazdy zakłada, że każda podróż wzdłuż odcinka trwa taki sam zaplanowany czas niezależnie od warunków. Wykładnicza ważona średnia krocząca (EWMA) zamiast tego utrzymuje jedno bieżące oszacowanie na krawędź i aktualizuje je za każdym razem, gdy autobus faktycznie przemierza tę krawędź: nowe_oszacowanie = α · zaobserwowany_czas + (1 − α) · stare_oszacowanie. Ponieważ α mieści się między 0 a 1, niedawne obserwacje liczą się bardziej niż stare, więc oszacowanie śledzi bieżące warunki, jednocześnie wygładzając jednorazowy szum z pojedynczej niezwykle szybkiej lub wolnej podróży. Ta symulacja używa α = 0,3.
Dlaczego błąd przewidywania rośnie gwałtownie, gdy zmienność ruchu jest zwiększana?
Model EWMA może reagować dopiero po zaobserwowaniu zakończonej podróży, więc jest z natury wskaźnikiem opóźnionym. Gdy suwak zmienności zwiększa gwałtowność wahań współczynników ruchu poszczególnych krawędzi, luka między „tym, czego model ostatnio się nauczył” a „tym, co dzieje się właśnie teraz” się poszerza, więc średni błąd bezwzględny między przewidywanymi a rzeczywistymi czasami przyjazdu rośnie.
Dlaczego najkrótsza ścieżka się zmienia, mimo że sama mapa nigdy się nie porusza?
Ta symulacja uruchamia Dijkstrę, używając na żywo przewidywanego przez EWMA czasu przejazdu każdej krawędzi zamiast jej stałej odległości fizycznej, więc zapytanie o te same dwa przystanki może zwrócić inną trasę, gdy warunki ruchu przesunęły wyuczone wagi na tyle, że wcześniej wolniejsza ścieżka staje się szybszą.