Всем привет, меня зовут Оля, и я работаю аналитиком в команде распределения заказов Ситимобил. Наша задача — оптимально находить водителей и предлагать им заказы с учетом ряда ограничений и пожеланий. Поэтому у нас есть разные режимы работы, в том числе «домой»: в этом режиме водителям предлагаются заказы только по пути домой.

Нам жаловались на некоторые предложения: водители считали, что им предлагают заказы не по пути. Поэтому они часто отказывались от заказа после подачи автомобиля, что приводило к плохому пользовательскому опыту и у водителей, и у пассажиров. Мы решили пересмотреть алгоритм. Самый сложный вопрос в этой задаче — «что такое по пути?». Оказалось, каждый водитель понимает это по-своему.

Мы поделимся опытом решения этой аналитической задачи с геоданными. Расскажем, как мы собирали информацию, какие алгоритмы легли в основу текущей версии и с какими сложностями сталкивались в процессе.

Сбор данных

Как и в любой аналитической задаче, первым делом нужно собрать данные. Сложности начались с самого начала, так как ранее такую разметку мы не собирали.

Первый способ

В качестве разметки данных решили использовать реакции водителей на предложение заказа. Довольно быстро всплыло много недостатков: данные оказались сильно смещенными.  Водителям невыгодно отказываться от заказа, к тому же из-за сложных дорожных сетей и пробок в больших городах водителям тяжело понять, по пути ли предложенный заказ. Дополнительно всё усложнило нецелевое использование режима «‎домой»‎ некоторыми водителями.

Новое решение

Мы решили спросить водителей напрямую. Чтобы не усложнять процесс завершения заказа, провели опрос сторонними инструментами. Мы хотели предложить водителям посмотреть на карту с маршрутом до дома и с точками предлагаемого заказа. Далее надо было ответить, по пути ли заказ, и написать комментарий. Но мы столкнулись с ограничениями вставки карт в опрос, и пришлось делать выборку из фотографий карт.  Набор из нескольких тысяч примеров по всей России собрали с помощью скрипта на Python. Затем на подложку OpenStreetMap с помощью библиотеки Folium добавляли маршрут от водителя до дома и координаты точек заказа. В Folium можно сохранять карты только в виде HTML-страниц, и для преобразования в jpeg, пришлось делать скрины карт с помощью webdriver.PhantomJS.

После первой итерации стало понятно, что не все водители поняли суть опроса и далеко не все отвечали по существу. Например, некоторые писали про качество маршрутизации.

Для получения объективного результата мы стали использовать агрегированную оценку от нескольких водителей. Из-за небольшой активности водителей в опросе (13-19 %) мы собирали ответ на один вопрос не более трёх раз.

Итоговая выборка получилась небольшая и тоже достаточно зашумленная, потому что разные водители по-разному воспринимают режим домой:

• кто-то хотел с его помощью оставаться в одном районе;

• некоторые ожидают много маленьких заказов;

• другим хочется сразу отправиться домой с одним крупным заказом.

Также во время опроса всплыло много сложных нюансов, вот некоторые из них:

1. Многие водители любят ездить по определенным трассам, и маршрут, проложенный по альтернативной дороге, они воспринимают негативно.

2. Водители измеряют близость по времени в пути, а не по расстоянию. В опросе некоторые отвечали с учетом знаний о трафике в этом месте, а некоторые отвечали на основании визуальной оценки маршрута.

3. Если заказ визуально был не по пути домой, водителям он не нравится, даже если добавочное время относительно невелико.

Оставалось понять, что такое «в сторону дома» и где же эти границы «добавочного времени».

Разметка данных

После опроса и фильтрации данных у нас получилось всего ~300 размеченных примеров. Для выработки алгоритма нужно было больше данных, поэтому мы решили использовать идеи алгоритмов с частичным привлечением учителя (semi-supervised learning).

Соединили две разметки с разными весами. Взяли опрос водителей с агрегированными оценками и реакции водителей на предложенные заказы. Предложение, от которого водитель отказался, считали как «точно не по пути». Если большинство водителей проголосовали за какой-нибудь заказ положительно, то его считали как «точно по пути» и в таких случаях увеличивали вдвое вес наблюдений.

В качестве модели решили использовать Catboost, потому что она дает хорошие результаты на табличных данных «из коробки» и хорошо работает с категориальными фичами. После обучения классификатора отбирали данные с маленьким весом, на которых ошибся классификатор. Эти данные частично проверяли вручную и заново обучали классификатор. В итоге мы получили достаточно сбалансированную выборку, информация в которой менее зашумлена, чем в исходной выборке.

Первая версия алгоритма

При создании алгоритма нужно было учитывать несколько требований.

Во-первых, алгоритм маршрута домой должен быть несложным и интерпретируемым. Интерпретируемость была критичным требованием, потому что часть обращений от водителей приходит отделу поддержки, и для быстрой и правильной реакции им нужно понимать алгоритм.

Во-вторых, нужно было учесть требования по скорости и ресурсные ограничения высоконагруженных серверов. Частые обращения к геосервису сильно утяжеляли алгоритм, поэтому мы уменьшили их количество. У нас была информация только о кратчайшем маршруте до дома, маршруте до клиента и конца заказа, и от конца заказа до дома.

Перед созданием первой версии алгоритма мы искали статьи на похожие темы. Публикации на тему ridesharing оказались очень ценными, но зачастую не подходили нам из-за ограничений в постановке задачи. Обычно рассматривают несколько заранее планируемых заказов и ищут среди них оптимальный. В нашем случае заказы поступают последовательно, и надо уметь останавливаться на оптимальном предложении. Но идеи некоторых работ мы всё-таки использовали в своём алгоритме. Например, в статье "A Matching Algorithm for Dynamic Ridesharing" (MaximilianSchreieck, 2016) предложен необычный способ нахождения поездок по пути с помощью проекций. Авторы разбирают несколько алгоритмов с дополнительными условиями. Суть алгоритма в случае с одним водителем и одним заказом:

Пусть — начальная точка маршрута, — конечная точка маршрута. Между ними строится кратчайший путь с помощью API для маршрутизации CraphHopper и алгоритма Дейкстры. В результате получается упорядоченное множество точек :

Пусть — потенциальный заказ по пути. Для точек заказа и доставки ищутся ближайшие точки маршрута в радиусе R см — .

Затем проверяется, что лежит в последовательности маршрута левее :

Кроме правила из статьи мы использовали модели с другими геофичами. Рассчитывали проекции точек заказа на маршрут водителя до дома, а затем вычисляли, например, расстояние от начала пути до проекции или расстояние от точки заказа до его проекции на маршрут. Дополнительно экспериментировали с альтернативным маршрутами до дома.

Чтобы вычислять длины кривых на карте нужно было использовать проекции. Первым делом надо изменить систему координат из географической в метрическую. А потом выбрать тип проекции, так как в ходе проецирования любая карта будет иметь искажения углов, расстояний или площадей. В нашем случае было важно сохранить расстояния между объектами, поэтому выбрали эквидистантную проекцию. Для подсчета длин полилиний на карте использовали проекцию Asia North Equidistant Conic (ESRI:102026) с маленькой погрешностью в России . Для проецирования точек на маршрут тоже использовали эквидистантную проекцию, потому что в Shapely проекция определяется как наименьшее расстояние от точки до кривой. Кстати, подобрать вариант оптимальной проекции можно тут.

#импорт библиотек
import pandas as pd
import geopandas as gpd
from shapely.geometry import Point, LineString
from haversine import haversine, Unit

def change_crs_array(arr, crs0 = 'epsg:4326'
                     
                     , crs1= 'esri:102026' 
                    ):
    '''Меняем crc у GeoSeries '''
    gpd_pr_o = gpd.GeoSeries(arr, crs = crs0)
    return gpd_pr_o.to_crs(crs1)[0]

#вводим данные для примера
#маршрут от водителя до дома
track = ['53.2026837,50.1749808', '53.2032251,50.1766205', '53.2033217,50.1768029', '53.2036436,50.1782835', '53.2097375,50.175848', '53.2158852,50.1857078', '53.2343924,50.1990867', '53.2409155,50.207305', '53.248018,50.2177334', '53.2506466,50.2227116', '53.245765,50.2354681', '53.2452285,50.2361119', '53.2450032,50.2372599', '53.2453573,50.2381074']

#массив координат lat,lon
points = []
points = list(map(lambda x: tuple(list(map(lambda y: float(y), x.split(',')))), track))

#для shapely нужны координаты в обратном порядке :lon, lat
points_revers = list(map(lambda x: x[::-1], points))

#координаты заказа
order = [53.25, 50.2067]
delivery = [53.246, 50.26]

home = points[-1]
driver = points[0]

#меняем СК Меркатора (epsg:4326) на эквидистантную метрическую (esri:102026)
line = change_crs_array(LineString(points_revers), crs0 = 'epsg:4326', crs1= 'esri:102026')
#расстояние от водителя до проекции точки заказа
line_o = line.project(change_crs_array(Point(order[::-1]), crs0 = 'epsg:4326' , crs1= 'esri:102026'))
#координата проекции
pr_o_revers = line.interpolate(line_o)
#переводим обратно в проекцию Меркатора 
#и реверсируем координаты для отображения
pr_o = change_crs_array(pr_o_revers, crs0 = 'esri:102026'
                                   , crs1 = 'epsg:4326').coords[0][::-1]
#расстояние от точки заказа до маршрута до дома
dist_o_track = haversine(order, pr_o, unit='m')

Наконец-то немного и про ML.

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

Вот несколько правил итогового алгоритма:

1. Точка O заказа не должна лежать в противоположной стороне от дома. Проекция точки А на маршрут не должна совпадать с координатой водителя.

   где — небольшое расстояние в метрах, чтобы учесть маршруты с поворотами.

2. Доля пути с заказом от общего расстояния до дома должна быть не меньше порогового значения.

   Коэффициент подбирали с помощью решающих деревьев и AB-тестов.

Результат

При тестировании нового алгоритма заметили, что водители стали реже пользоваться режимом домой, потому что алгоритм предлагал заказы слишком редко. Тогда мы пришли к компромиссу между точностью и полнотой и стали предлагать больше заказов на коротких дистанциях, сократив правила. В финальном эксперименте доля положительных реакций водителей на предложенные заказы выросла на ~3п.п., аналогично выросла конверсия из заказа в предложение водителям.

У алгоритма много возможностей для улучшения, таких как оптимизация сбора разметки данных, более персонализированные предложения, оптимизация обращений к геосервисам. Мы работаем над ними и, надеемся, вернёмся с обновлённой версией :)