Приложения от диспетчеров такси, автоматически выбирающие машины по заказу клиентов, переживают взрывной рост популярности. Ученые МТИ, Корнельского университета и итальянского Института информатики и телематики подсчитали, какую экономию могли бы получить операторы подобных систем, если бы добавили в свои приложения кнопку «Я не против ехать вместе с другими пассажирами».

Исследователи обработали данные по 150 млн поездкам, совершенным 13 тыс. такси по Нью-Йорку за год. Основные выводы: почти 95% поездок можно было совместить, а при оптимальном их сочетании общий пробег автомобилей уменьшился бы на 40%.

Для максимальной оптимизации нужно заранее знать стартовое время поездок, но это возможно только когда машину заказывают на определенное время. Поэтому исследователи также проанализировали данные, исходя из предположения, что комбинировать можно только поездки, начинающиеся в пределах минуты друг от друга. Даже в этом случае сокращение общего пробега составило 32%. Авторы полагают, что это вполне позволит предлагать пассажирам поездки по меньшей стоимости.

Анализ проводился следующим образом — каждая поездка характеризовалась временем и GPS-координатами посадки и высадки. Для каждого маршрута был найден набор поездок, перекрывающихся с ним. После этого определялись маршруты, которые можно скомбинировать, не превышая порога задержки. В итоге был составлен граф по всем 150 млн поездок, вершины которого обозначали поездки, а ребра — сочетаемость. Исследователи также выяснили, что их алгоритм подбора совместных поездок, работающий на стандартной машине с Linux, способен находить оптимальные сочетания для 100 тыс. поездок всего за десятую долю секунды.