Стремясь быть надежным партнером для наших клиентов, мы в Cityflo хотим гарантировать высокую точность и предсказуемость нашей системы отслеживания транспортных средств. Отображение точного времени прибытия является тем самым отличным опытом, который ожидают от нас наши пользователи.
Проблема
Мы используем Google Advanced Directions API для расчета времени в пути между двумя точками. Google является выбором по умолчанию, учитывая точность данных о трафике в реальном времени. Мы использовали этот API для расчета ETA (ожидаемого времени прибытия) отдельно для каждого транспортного средства на каждой из его остановок, индивидуально вызывая API каждый раз при регистрации места остановки. Еще пару месяцев назад этот API можно было использовать бесплатно .
После изменения их ценообразования работа в прежнем режиме стоила бы нам примерно 960 долларов в день.
Мы предполагали, что есть 150 автобусов с 8 средними остановками, среднее время ожидания которых составляет около 20 минут. Это дает примерно 96,000 вызовов API. Google Directions API стоит 10 долларов за 1,000 вызовов.
Это был явно нереальный вариант для нас, так как мы молодой стартап. Мы могли бы немного снизить стоимость, уменьшив частоту обновления данных трафика, но это сказалось бы на точности расчета времени прибытия. Внезапный всплеск трафика отразился бы на нашей системе слишком поздно, что было неприемлемо.
Мы исследовали некоторые альтернативы с открытым исходным кодом, такие как Open Street Map, но не смогли получить то, что делает Google. Вместо этого мы решили остаться на платформе Google Maps и пересмотреть наш подход.
Решение
В отличие от такси, наши автобусы следуют по фиксированным маршрутам, и все остановки в регионе покрыты несколькими автобусами в парке. Мы определили закономерность движения транспортных средств. Выработанная схема позволила нам рассчитать время в пути между ближайшими остановками, независимо от того, какой автобус ехал. Именно наша архитектура существенно помогла нам отделить обновления местоположения автобуса от вычисления времени в пути для каждого автобуса, тем самым уменьшив любые избыточные вычисления.
Если автобус соединяет две ближайшие остановки, мы называем их смежными.
Например, предположим, что есть сеть остановок, показанная на следующем рисунке.
Здесь парами смежных остановок будут (A, B), (B, C), (D, C), (C, F) и (E, F). Вычисляя время в пути между соседними остановками, мы можем применять одни и те же данные для всех транспортных средств. Если автобус находится на остановке A, а пойдет на остановку F, то время прибытия на F можно рассчитать путем суммирования времени в пути (A, B), (B, C) и (C, F).
t(A,F)=t(A,B)+t(B,C)+t(C,F)
Само собой разумеется, что здесь нет никакой серебряной пули.
Подвох в том, что происходит, когда автобус находится где-то между остановкой A и остановкой B, как мы вычисляем его время прибытия на остановку F?
Мы решили решить эту проблему с помощью линейной интерполяции.
Если мы можем определить относительное положение автобуса между двумя остановками, мы можем оценить время прибытия. Например, если автобус преодолел половину расстояния между двумя остановками, можно предположить, что потребуется еще половина времени между этими двумя остановками, чтобы добраться до другого конца.
Directions API предоставляет ломаную линию — набор координат в определенном порядке — между соседними остановками, что помогает нам точно определить местоположение автобуса. Чтобы повысить точность при интерполяции, эти линии корректируются, чтобы сделать их более однородными. Например, линии на прямых дорогах более разреженные и наоборот. Таким образом, мы обеспечиваем максимум 20 метров между двумя координатами местоположения для повышения точности информации.
Определение местоположения автобуса на ломанной линии может быть сложной проблемой, если сеть остановок и движение машины немного запутаны. Например, если автобус регистрирует местоположение на остановке во время движения по противоположной стороне дороги, то система выйдет из строя. Однако эта история для отдельного поста.
Результат
Этот подход сделал вызовы API независимыми от количества транспортных средств и зависящими только от наших остановок, что помогло нам в расширении нашего отслеживаемого парка без дополнительных затрат. Однако стоимость здесь зависит от количества остановок в сети. После нескольких итераций настройки и адаптации для нашего варианта использования мы наблюдали снижение стоимости API Google Directions как минимум на 94%.
Что дальше?
Мы смогли сделать работоспособную систему, но впереди еще много работы. Мы можем дополнительно оптимизировать ее, изменяя частоту обновления различных пар остановок, наблюдая за тенденциями движенния между ними. Если изменение времени в пути между двумя остановками невелико, мы можем уменьшить частоту обновления и наоборот.
Это была очень интересная проблема для нашей команды разработчиков и инженеров. Но мы решили ее и это помогло нам поддерживать высокое качество опыта в Cityflo, одновременно обеспечивая постоянные инновации.