Одна з головних завдань в Таксі Київ – як зробити так, щоб до користувача швидко приїжджала машина, а у водія скорочувався час «холостого пробігу» (тобто час, коли він на лінії без пасажира). Здавалося б, все просто: користувач вибирає тариф, вказує додаткові побажання (дитяче крісло, наприклад). Залишається відфільтрувати водіїв на лінії за цими критеріями, вибрати найближчого і запропонувати йому замовлення. Однак все так просто тільки на перший погляд.
Коли користувач натискає кнопку «Викликати таксі», в бекенд створюється об’єкт замовлення і починається його обробка відповідно до кінцевим автоматом. Щоб замовлення перейшов зі стану «В очікуванні» в «Водій призначений» – потрібно знайти водія, запропонувати йому замовлення та дочекатись підтвердження, що замовлення прийняте.
При підвищеному попиті, коли починається конкуренція за виконавців, підхід не годиться. Щоб максимально задовольнити попит навіть в самі навантажені годинник, ми використовуємо безліч підходів і алгоритмів. Один з них – буферне призначення водіїв на замовлення. В його основі лежить добре відома задача з області комбінаторної оптимізації – завдання про призначення. Потрібно призначити кожній задачі такого виконавця, щоб скоротити сумарний час виконання всіх робіт (при цьому один виконавець може взятися тільки за одну роботу).
При вирішенні такого завдання про призначення наша «вартість» виконання роботи (замовлення) виконавцем (таксопарків і водієм) – значення функції скорингу від часу подачі автомобіля до користувача. Завдання можна описати в термінах дводольних графів: з одного боку – замовлення, з іншого – виконавці. Між замовленнями і виконавцями є зважені ребра (скоринг). Таким чином, одна з наших цілей – мінімізувати сумарний час подачі автомобілів, максимізуючи кількість виконаних замовлень (максимальне паросполучення). Один з найбільш відомих способів вирішити таке завдання – угорський алгоритм.
Очевидно, що при буферном призначення ми не можемо дати водія за запитом, як при жадібному підході. Спочатку потрібно покласти замовлення в чергу, потім розіграти, а після цього повідомити про знайдений водія. Це зовсім не вписувалося в кінцевий автомат обробки замовлення, і його довелося трохи вдосконалити. Він стане приймати замовлення, класти до себе в чергу, знаходити водіїв і зберігати результати розіграшів.
Насамперед нам треба було підготувати до нового профілю навантаження. Якщо при жадібному підході запити на водіїв просто індивідуально потрапляли на балансувальник Tracker’a і перенаправлялись на його інстанси з розподілом навантаження, то в буферному призначення всі запити були з однієї машини: індивідуальні запити просто забили б пул з’єднань. Тому ми додали в трекер можливість батчевой обробки запитів, які всередині трекера оброблялися паралельно.
Таким чином нам вдалося поєднати основний кінцевий автомат обробки замовлення з кінцевим автоматом обробки в буферному діспатче без впливу на працюючу логіку і без гонок між станами. Можна запускати перші експерименти на живих користувачів.
Це все дуже здорово, але як же час пошуку виконавця, запитаєте ви. Якщо пошук відбувається не відразу після надходження замовлення, значить, час пошуку збільшується і в результаті компенсується більш швидкою подачею? Це не зовсім так: за допомогою різних методик (в т.ч. за допомогою машинного навчання), ми змогли виділити кейси, коли очікування має сенс, в інших же випадках час очікування не змінюється.
Ще один спосіб знайти виконавця швидше – почати шукати його ДО створення замовлення. Коли з’являється новий пін (тобто користувач тільки вводить дані про замовлення в додаток), алгоритми машинного навчання оцінюють ймовірність того, що далі піде замовлення, і вирішують, чи враховувати його при буферном пошуку водіїв. Ми можемо знайти машину заздалегідь, а коли користувач натисне кнопку замовлення – тут же зробити пропозицію невластивому водієві.
