Два незнакомца, одно такси и алгоритм В математике есть известная задача коммивояжёра — прокладка оптимального маршрута по нескольким городам для бродячего торговца. Её решение сложнее, чем кажется на первый взгляд. Интуитивно представляется, что задачу можно решить простым подбором правильной последовательности остановок. Но количество возможных комбинаций растёт с каждым новым пунктом, и перебор вариантов быстро становится не под силу даже компьютеру. Математики, логисты и инженеры — во всех этих сферах можно встретить свою версию задачи коммивояжёра — придумывают разные решения. Один из вариантов этой задачи решает тариф «Вместе» в Яндекс Go, который позволяет совмещать поездки незнакомых людей, экономя деньги пассажиров (в среднем 22%) и снижая нагрузку на водителей. За прошлый год пользователи совершили несколько десятков миллионов поездок по тарифу, а с сегодняшнего дня он расширился на 31 новый город. Для того чтобы алгоритм работал, разработчикам Яндекс Go пришлось решать усложнённую версию задачи коммивояжёра, где ищется оптимальный маршрут не по заранее заданному списку точек, а со множеством возможных пар пассажиров. Поэтому они разбили задачу на два этапа: подбор и прокладка пути. Сначала ML-алгоритм оценивает совместимость заказов разных людей. Для этого он учитывает время, локацию, статистику похожих поездок, трафик, частые маршруты и т. д. Это позволяет предсказывать удачные пары попутчиков ещё до прокладки маршрута, а оценка пересчитывается регулярно при отмене заказов или изменении дорожной ситуации. Когда пара подобрана, происходит роутинг: расчёт оптимального маршрута по четырём точкам — две посадки и две высадки. Алгоритм ищет такой маршрут, в котором не будет больших крюков, чтобы не задерживать ни пассажиров, ни водителя. И всё это — за доли секунды, пока вы смотрите на крутящийся индикатор поиска. Подписывайтесь 👉 @techno_yandex