🚙 Вычисляем расчетное время прибытия Uber

На собесах по ML System Design могут предложить построить сервис оценки времени поездки Uber, от момента до его вызова до момента прибытия. Здесь нам пригодится теория графов.

1️⃣ Для начала разбиваем расчетное время на 4 этапа
- Eyeball. Старт: когда водитель вводит пункт назначения в приложении.
- Dispatch. Найти машину и забрать пассажира в кратчайшие сроки ожидания
- Pickup. Забрать пассажира: найти время, необходимое для того, чтобы забрать пассажира.
- On-trip. Время поездки: своевременно предоставлять обновления в режиме реального времени, чтобы добраться до места назначения.

2️⃣ Далее нам нужен алгоритм маршрутизации. Для этогопредставляем карту города в виде графа, где каждый перекресток представляем, как узел. Поскольку в городе перекрестков очень много, то разделим весь граф на партиции и будем строить маршрут внутри одной партиции. При этом свяжем партиции теми узлами, которые лежат на ее контуре. Чтобы построить оптимальный маршрут воспользуемся алгоритмом Дейкстры.

3️⃣ После того как маршрут построен, нам нужно обогатить информацию о нем данными о дорожном движении. Для этого используем скор загруженности трафика (можем брать скоры исторический и онлайн) в качестве весов между ребрами.

4️⃣ И наконец, для борьбы с неточностями в сигналах GPS в городе делаем сопоставлениые карты с GPS с реальным сегментом дороги. Для этой задачи можно применить фильтр Калмана, где мы с определенной периодичностью делаем предположение о нашей позиции и сверяем его с реальной дорогой.

source: uproger

#base