Ola предлагает решения для мобильности, которые автоматически сопоставляют пассажиров с водителями. Он также включает в себя Ola Ride Share, который объединяет пассажиров с перекрывающимися маршрутами, что приводит к более дешевой поездке для всех клиентов. Чем больше пересечение между двумя маршрутами, тем большую скидку они могут предложить. Что, с другой стороны, делает хороший маршрут Ола? Они считают, что это недорогое, быстрое, эффективное и приятное путешествие. И как они могут узнать, подобрали ли пассажиру быстрый и эффективный маршрут? Как они могут определить, понравится ли выбранный ими маршрут группе из двух, трех или четырех человек? Это проблема, которую пытается решить их система сопоставления, над которой они работают более полутора лет.

Мотивация райдшеринга

Ola начала свою деятельность в декабре 2010 года. Перед запуском они следили за отраслью в течение нескольких лет, но хотели подождать, пока не будет достаточно плотности, прежде чем запускать настоящий сервис райдшеринга. В мае они провели симуляцию существующих поездок Ola Classic (не общих) и обнаружили, что более 80% поездок в Мумбаи делят большую часть своего маршрута с другой поездкой. Это была ошеломляющая цифра: лишь небольшой процент городских автомобилей обслуживал Ола, но большинство из них потенциально могли быть связаны с другими пассажирами. Это был большой потенциал для преобразования транспорта и предоставления его пассажирам более дешевых услуг.

Дизайнерские решения

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

Они также рассматривали возможность создания механизма группового сопоставления. Вместо того, чтобы находиться в соответствующем пуле в течение установленного периода времени (1 минута), все запросы будут храниться в пуле до следующего тактового интервала. С интервалом в 10 минут поездка, запрошенная в 8:03 или 8:09, останется в соответствующем пуле до 8:10, а поездка, запрошенная в 8:11, останется в пуле до 8:20. Имея больше времени в пуле сопоставлений, они смогут сопоставлять больше запросов одновременно, увеличивая вероятность нахождения совпадения. Кроме того, гибкий интервал между сегментами позволит нам адаптироваться к местам с более низкой плотностью, таким как Ахмадабад, при запуске, поскольку интервал между сегментами может быть увеличен до 15 или 20 минут. Однако у этой стратегии были существенные недостатки.

Если мы найдем водителей для всех пассажиров одновременно, это вызовет перебои с поставками, поскольку к десятиминутной отметке нам нужно будет иметь группу водителей. Десятиминутный перерыв означал, что пассажирам приходилось ждать дольше, прежде чем им показывали маршрут. Учитывая, что первоначальная реализация, вероятно, имела некоторые недостатки, десятиминутная задержка могла бы быть чрезмерной, если бы они затем были сопоставлены неправильно. Наконец, они определили, что одноминутный пул сопоставления обеспечит наилучшие впечатления для их пассажиров и является тем, чего ожидали пользователи Ola по требованию.

Наивное сопоставление

Они начали с простой жадной системы поиска совпадений из-за возможности трансформировать транспорт и инженерную философию маневренности. Жадная система — это система, в которой они выбирают первое совпадение, соответствующее их ограничениям, а не оптимальное совпадение для всей системы. Казалось разумным использовать жадную систему, потому что оптимизация для нескольких потенциальных совпадений невозможна, пока продукт не станет достаточно большим. Расстояния по гаверсинусу — это длины прямых линий между двумя сайтами, умноженные на среднюю скорость региона для получения оценки времени. Реализация гаверсинуса проста в настройке и с учетом подходящих ограничений (например, объездов, времени до посадки и т. д.) обеспечивает правильное сопоставление пользователей.

Первоначально каждый пассажир сравнивался с каждым другим пассажиром в системе (O(n2)), во всех возможных порядках. Пассажиры обозначались буквами алфавита, и у каждого пассажира было две остановки — посадка и высадка — А и А’, Б и Б’ и так далее. При сравнении пассажиров A и B они рассмотрели 24 возможных порядка: ABB'A', ABA'B', B'A'BA, B'AA'B, B'ABA', BAA'B', AA'B'. B, B'BAA' и т. д. Учитывая, что никогда не бывает высадки перед погрузкой, а порядок, подобный AA'BB', не перекрывается и, следовательно, не заслуживает рассмотрения, они смогли свести к минимуму количество перестановок до четырех. Они рассматривали все четыре перестановки и исключали те, которые не соответствовали всем требованиям. Затем они выбирали наилучший порядок, сопоставляли и предупреждали гонщика. Поскольку вторым A считается A’, теперь они будут называть маршрут ABA’B’ ABAB (высадка).

Ограничения начались с самых очевидных проблем, таких как объезд и время посадки. Чтобы выполнить сопоставление, общий объезд каждого пассажира из-за совпадения должен быть меньше абсолютного порога, а также меньше пропорционального порога. Это имеет смысл, потому что 5-минутный объезд на 30-минутном маршруте гораздо удобнее, чем 5-минутная поездка. Объезды было легко вычислить, поскольку они сравнивали все время, которое потребовалось бы каждому пассажиру, чтобы добраться до пункта назначения без совпадения, с общим временем, которое им потребовалось бы, чтобы добраться туда, если бы они были сопоставлены. Объезд пассажира А был ABA минус AA, а объезд пассажира B был BAB минус BB в порядке ABAB.

Для маршрута ABAB (при условии, что | символизирует водителя) они имеют идентичные ограничения на дополнительное время до посадки пассажиров, и это будет рассчитываться следующим образом: |A представляет время посадки А, а |AB представляет время посадки В. То, что он был вторым пассажиром в поездке в Оле, явно сократило средний объезд для этого гонщика, поскольку ему не нужно было делать еще одну остановку между посадкой и высадкой (ABBA), но это произошло за счет увеличения времени посадки.
Они быстро осознали недостатки системы после ее запуска. Пассажиры делились примерами своих маршрутов, которые включали остановку на другой стороне горы или требовали дополнительного круга по перегруженным улицам с односторонним движением в центре города в час пик. Они начали замечать, что пассажиры не хотят ехать назад и что угол наклона линий на карте влияет на их радость от матча. Система в том виде, в каком она была создана, не собиралась обеспечивать желаемое качество езды способами, которые были очевидны во время их первоначальной установки, и другими, менее очевидными. Им нужно было внести некоторые изменения, и сделать это нужно было быстро, иначе потребители остались бы недовольны их опытом.

Гео-хэширование

Outside Lands дали понять, что им нужно отказаться от расчетов гаверсинуса, поскольку они были слишком неправильными. Они рассматривали возможность создания графа маршрутизации и использования алгоритма A*, аналогичного OSRM, и что-то, что они сделали для своих оценок цен, но они знали, что он не будет масштабироваться в алгоритме O (n2) без значительных инвестиций в автономные вычислительные методы, такие как как сокращение иерархий и много работы по построению масштабируемой системы. Вместо этого они разработали модель на основе геохеширования, потому что разработка продукта была слишком ранней, чтобы инвестировать в такой уровень труда.
Геохеширование — это метод группировки координат на основе их широты и долготы. Они могут записывать среднюю скорость поездок от одного геохэша к другому, используя исторические данные о предыдущих поездках Ola, и сохранять их в простом запросе хэш-таблицы, используя исторические данные о предыдущих поездках Ola. Затем они умножали гаверсинус расстояния между двумя точками на эту скорость, чтобы получить оценку времени. Этот метод оказался гораздо более точным, позволив им избежать сопоставления через горы и различия между шоссейным и уличным вождением. Он также был невероятно эффективен (поиск по вложенной хэш-таблице O(1)), но не очень хорошо справился с определением улиц с односторонним движением или трафика в час пик, потому что их прогнозы были одинаковыми в течение дня.

Геохеш Уровень 6

К счастью, геохэш-подход был прост в настройке и прекрасно функционировал. Они построили еще одну многоуровневую хеш-таблицу между пунктом отправления и пунктом назначения для каждого часа недели, что уменьшило неточности в час пик и позволило им повторять модель для улучшения оценок. Собрав больше данных, они смогли разбить свою модель на меньшие размеры геохэшей, сделав ее более точной. неблагоприятные матчи стали больше сосредотачиваться на эмпирических трудностях. Многие из них были незаметными, и в результате у пассажиров был негативный опыт. Они обнаружили, например, что пассажиры чрезвычайно чувствительны к движению назад, даже в большей степени, чем к пропорциональному увеличению времени объезда. Пользователи часто предпочитают 10-минутный обход без возврата, а не 5-минутный обход с возвратом. Они также обнаружили, что потребители предпочли бы быстрое время посадки, но большой объезд, а не наоборот, даже если для этого потребовалось бы более длительное путешествие.
Многие из этих уроков нельзя предсказать, пока вы не начнете строить продукта, но все они вносят свой вклад в то, что ожидают ваши пассажиры. Когда они впервые установили Ola, у них было два ограничения: объезд и время посадки. Сейчас их более 30.

Эффективность и повышение эффективности

В этот момент они потратили много времени, сосредоточившись на опыте пассажиров, но не так много усилий, направленных на повышение эффективности продукта, что позволило бы им предоставлять более высокие скидки. До сих пор они рассматривали возможность объединения двух пассажиров на одном маршруте. Это привело к потере большей эффективности: большее количество людей в машине означало большую экономию средств, которую они могли передать своим клиентам. Следующим логическим шагом для них было внедрение Triple Matching, которое позволяет добавить в транспортное средство третьего и четвертого пассажира.

Тройное соответствие

Увеличивая среднюю скорость совпадения, тройное сопоставление повысило эффективность системы, но также создало кошмар с масштабируемостью. Им нужно было изучить четыре перестановки с двумя людьми в машине, но с четырьмя пассажирами теперь они могли исследовать такие маршруты, как ABCBCA или даже ABACBDCD, всего 1776 перестановок. Это повлекло за собой быстрое масштабирование эффективности системы для управления трафиком, а также новый набор требований для обеспечения положительного впечатления пассажиров.

Пример тройного совпадения — ABCABC

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

Горизонтальное масштабирование системы без четкого шаблона разделения затруднено — древовидные структуры (BSP, quadtrees и т. д.) не работают, когда два пикапа могут находиться в разных разделах и при этом отлично совпадать (например, райдеры могут начинаться с разницей в 15 минут). ), и они работали над тем, чтобы в будущем обеспечить непрерывное сопоставление в любой точке маршрута. Продольная сортировка была одной из оптимизаций, которые они выполнили. Решение этой проблемы было сложным и выходило за рамки этого поста, но это была одна из оптимизаций, которые они сделали.

Продольная сортировка

Время, которое требовалось, чтобы подобрать пассажира, было одним из их ограничений в создании хорошей пары. Неважно, насколько быстрой была оставшаяся часть поездки, если на то, чтобы забрать вас, ушло 15 минут; пассажиры не сочли бы это приемлемым маршрутом. Это означало, что при рассмотрении вопроса о соединении А и В существовал предел того, насколько далеко они могут быть друг от друга. Они обнаружили, что могут использовать это во внешней петле: отсортировав внешнюю и внутреннюю петлю по долготе, они смогли выйти из этой петли, как только мы достигли максимального расстояния. Им не нужно было сравнивать кого-то в Тане с кем-то в Боривали, если они сортировали всех пассажиров в Мумбаи с запада на восток. Это не повлияло на сложность системы; он по-прежнему был O(n2), но значительно повысил эффективность. Это пример ограничения, предназначенного для удобства пассажиров, которое действительно помогает масштабировать систему за счет уменьшения проблемного пространства.

Перенаправление

Затем они смогли решить еще одну веху в повышении эффективности Ola Line: изменение маршрута благодаря улучшениям в производительности системы, таким как продольная сортировка. Они согласились добавить пассажира на маршрут только при условии, что он не изменит следующую остановку водителя до этого момента. Это означало, что они не могли изменить маршрут |AA (где вертикальная черта представляет водителя) на маршрут |BABA, потому что первый посадку водителя пришлось бы изменить с пассажира A на пассажира B. Точно так же они не могли добавить пассажир C, чтобы сделать это AB|CABC на маршруте AB|AB, если оба пассажира уже были подобраны, однако они могли сделать это AB|ACBC.

Перенаправление было запрещено по целому ряду причин, как технических, так и связанных с пользовательским опытом. Представьте, что вы находитесь в одном квартале от точки высадки и вам говорят повернуть направо, чтобы забрать другого пассажира. Хуже того, водитель мог подобрать первого пассажира и выехать на съезд на шоссе только для того, чтобы получить указание съехать с автострады, двигаться в обратном направлении и подобрать второго пассажира. Это был опасный шаг, но преимущества были слишком привлекательными, чтобы отказываться от них такие энтузиасты эффективности, как мы. Они провели A/B-тестирование, как и большинство вещей в Ola, и позаботились о том, чтобы включить меры безопасности, чтобы предотвратить негативное взаимодействие с пользователем. Они использовали изобретательную тактику, чтобы распознавать, когда автомобиль вот-вот въедет на въезд, чтобы маршруты не менялись, если водитель должен был высадить пассажира. В целом, изменение маршрута значительно повысило эффективность, и они смогли перевозить его с минимальными помехами для пассажиров.
Они реализовали некоторые из наиболее очевидных аспектов эффективности (многие из которых они не обсуждали) и приближались к пределы жадной системы в этой точке. Они выигрывали по-крупному с Triple Matching и Rerouting, но не могли в полной мере воспользоваться растущим количеством поездок. Поскольку количество пассажиров Line превзошло количество пассажиров Ola Classic в Мумбаи, они стремились оптимизировать всю систему, а не просто выбрать первое приемлемое совпадение для гонщика.

Путь к тому, чтобы стать менее жадным

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

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

Замена маршрута (также известная как экспресс-перенаправление)

Смена маршрута — это функция, которая позволяла велосипедисту переключаться с одного маршрута на другой. Перед посадкой пассажира можно было переключить и сообщить через SMS, что для него определен более эффективный маршрут. Это позволило им повторно сопоставить клиентов после того, как они уже были сопоставлены, если они нашли лучшее совпадение, тем самым увеличив окно сопоставления с 60 секунд до нескольких минут, потому что они могли продолжить поиск лучшего маршрута, даже если они ранее выбрали водителя. . Пример этого показан на анимации ниже, где пассажир А переключается с маршрута 2 на маршрут 1 после того, как его система определила, что это соединение обеспечивает наилучшую общую эффективность.

Маршрут Замена пассажира А на Маршрут 1

Замена маршрута уменьшила нагрузку по прогнозированию будущего спроса, но также привела к собственным проблемам. Например, если они сказали пассажиру, что его заберут через шесть минут во время первого матча, они использовали это время, чтобы приготовить завтрак или почистить зубы. Они могут быть недоступны и пропустить поездку, если их затем переведут на новый маршрут с 30-секундным временем посадки. Точно так же, если они обнаружили первоначальное совпадение с коротким временем посадки (например, одна минута), но впоследствии нашли лучшее совпадение с четырехминутным временем посадки (и, возможно, гораздо более коротким объездом), теперь пассажиру, возможно, придется ждать три минуты. на обочине — не лучший пользовательский опыт. Во всех случаях они меняли пассажира только в том случае, если новый маршрут сокращал время их посадки или объезда, но они должны были быть осторожны при внесении серьезных изменений. У замены маршрута, конечно, были свои недостатки, но она привела к огромным преимуществам в эффективности и, что более важно, к более быстрой поездке для пассажиров.

Подходящая биржа

Они начали откусывать более идеальный подход после того, как у них появилась замена маршрутов. Как указывалось ранее, это задача взвешенного максимального сопоставления, которая потребовала многочисленных изменений в их подходе. Раньше их система сопоставления постоянно сравнивала гонщиков, чтобы увидеть, может ли непревзойденный гонщик быть размещен на маршруте. Они начали сравнивать подходящих райдеров с другими существующими маршрутами в своей системе, когда запустили обмен маршрутами. Они выполняли это в очень узком цикле, выполняя миллионы сравнений в секунду в надежде, что обновление местоположения водителя выявит ранее не обнаруженное совпадение. Они не хотели так часто сравнивать гонщиков при переходе к более идеальному решению; вместо этого они намеревались «накапливать» поездки в течение определенного периода времени, прежде чем пытаться решить более полным методом. Они просматривали все возможные совпадения и выбирали идеальный набор совпадений, чтобы сократить общее количество обходов, время посадки и стоимость всей системы после того, как мы накопим большое количество поездок. Это похоже на описанную ранее схему сопоставления с сегментами, за исключением того, что окно сегмента намного меньше (например, 30 секунд).

Несмотря на то, что этот метод более эффективен, он все же создает существенные вычислительные и технологические препятствия. Построить идеальное распределенное решение сложно, поскольку для этого требуется возможность разбивать граф на более мелкие компоненты в режиме реального времени без ущерба для производительности системы. Попытка провести статическое разбиение по районам в таком городе, как Мумбаи, будет означать, что пассажиры, путешествующие из Тане и Бандры на работу в Андхери, не смогут быть сопоставлены, несмотря на то, что они знают, что это одни из наиболее подходящих маршрутов. Секретный секрет, лежащий в основе их Matching Exchange, заключается в определении правильного шаблона разбиения и обеспечении максимальной эффективности системы.

Дорога впереди

Они проводят A/B-тестирование большинства модификаций своей системы, как и в прошлом, и основываются на том, что они узнали из предыдущих тестов. Они также уточняют, что является хорошим соответствием для их пассажиров, и учатся на полученной информации, корректируя веса своих ограничений в соответствии со своими потребностями.

Это все на данный момент! Спасибо за чтение!!