🚌 Прогнозатор Маршрутів і Часу Прибуття Транспорту

Модель EWMA може реагувати лише після того, як спостерігає завершену поїздку, тож вона за своєю природою є запізнілим (лагуючим) показником: вона описує нещодавні умови, а не ті, які автобус відчує під час руху. Коли повзунок волатильності збільшує різкість коливань коефіцієнтів трафіку на ребрах між оновленнями, розрив між «тим, що модель дізналась востаннє» і «тим, що відбувається просто зараз» зростає, тож середня абсолютна похибка між прогнозованим і фактичним часом прибуття збільшується. Зменшіть волатильність — і оцінка моделі зійдеться до справжнього поточного часу в дорозі протягом кількох проїздів автобуса, а ряд похибок помітно вирівняється.

Ця симуляція запускає Дейкстру, використовуючи для кожного ребра живий прогнозований EWMA час у дорозі, а не фіксовану фізичну відстань, тож запит для тих самих двох зупинок може повернути інший маршрут, щойно умови трафіку змінять вивчені ваги настільки, що раніше повільніший шлях стане швидшим. Це відображає те, як реальні навігаційні застосунки безперервно перераховують маршрути: топологія графа статична, але вартості ребер — рухома ціль, тож пошук найкоротшого шляху доводиться перезапускати (або оновлювати поступово) щоразу, коли ці вартості суттєво змінюються.

Промислові системи отримують GPS-сигнали від тисяч транспортних засобів, історичні розподіли часу в дорозі за часом доби й днем тижня, живі стрічки інцидентів і перекриттів, а також часто модель машинного навчання (градієнтний бустинг або графову нейронну мережу), а не одну EWMA-оцінку на ребро. Вони також прокладають маршрути графами з мільйонами вузлів, використовуючи заздалегідь обчислені скорочення, щоб запити поверталися за мілісекунди, і безперервно переоптимізовуються, а не лише коли користувач про це просить. Основні ідеї, продемонстровані тут — пошук найкоротшого шляху зваженим графом і адаптивна оцінка, що навчається з нещодавніх спостережень, — ті самі будівельні блоки, лише в значно більшому масштабі з набагато багатшим сигналом.

Фронт — це зростаюча множина зупинок, які алгоритм остаточно завершив, показана тут у порядку їх завершення. Оскільки Дейкстра завжди завершує наступну найближчу з решти зупинок, фронт розширюється назовні від початкової зупинки приблизно як хвиля, хоча його точна форма залежить від поточних вагів ребер, а не від суто геометричної відстані — зупинка, що близька на карті, може завершитися пізно, якщо дороги до неї зараз повільні. Спостереження за порядком розширення — це пряма візуалізація того, скільки зупинок алгоритму фактично довелося розглянути, перш ніж він зміг гарантувати, що найкоротший шлях до зупинки призначення знайдено.

Оцінка EWMA для кожного ребра покращується лише тоді, коли автобуси проїжджають ним, тож ребро, яким часто проїжджають кілька маршрутів, що перетинаються, накопичує спостереження — а отже, точну й актуальну оцінку — значно швидше, ніж ребро, яке торкається лише один маршрут. Автобус, що курсує завантаженими спільними коридорами, зазвичай показуватиме нижчу середню абсолютну похибку, ніж той, що їздить тихішою частиною мережі — так само як і в реальних системах, де високочастотні коридори отримують кращі прогнози прибуття в реальному часі, ніж ті, що обслуговуються рідко, просто тому що там більше свіжих даних для навчання.