AI-система матчингу водіїв та пасажирів у райдшерингу

Чому матчинг у райдшерингу — це нетривіальне завдання?

Водій їде 15 хвилин до пасажира, а потім везе його 5 хвилин — знайома ситуація? Причина — неоптимальний матчинг. Коли алгоритм просто призначає найближчого водія, ігноруються майбутній попит, завантаженість водія та можливість об'єднання поїздок. У результаті пасажири чекають довше, водії простоюють, а платформа втрачає прибуток. Ми — команда AI/ML-інженерів із сумарним досвідом 40+ років у райдшерингу, виконали понад 20 проєктів з матчингу. Наш підхід поєднує комбінаторну оптимізацію та машинне навчання, що дозволяє знизити ETA на 30–40% і підвищити utilization водіїв до 72%, одночасно знижуючи операційні витрати платформи на 25%.

На одному з проєктів ми зіткнулися з ситуацією, коли жадібний матчинг давав match rate лише 85% і utilisation 55% через ігнорування прогнозу попиту. Після впровадження батч-матчингу з heatmap попиту через 2 тижні match rate виріс до 96%, а середній дохід водія збільшився на 18% — до 500$ на місяць на водія.

Для покращення якості матчингу ми використовуємо embeddings для представлення запитів і водіїв у векторному просторі. Алгоритм матчингу враховує коефіцієнт динамічного ціноутворення (surge), щоб у години пік призначати пріоритетні поїздки.

Як ми розробляємо алгоритм матчингу?

Для батч-матчингу ми використовуємо угорський алгоритм на матриці вартості, обчисленої на основі ETA, якості водія та коефіцієнта детуру. Наводимо повний код двигуна, який передаємо клієнту:

import numpy as np
from scipy.optimize import linear_sum_assignment
from dataclasses import dataclass
from typing import Optional
import heapq

@dataclass
class Driver:
    id: str
    lat: float
    lon: float
    current_passengers: int
    max_passengers: int
    rating: float
    acceptance_rate: float
    vehicle_type: str  # economy, comfort, xl

@dataclass
class RideRequest:
    id: str
    pickup_lat: float
    pickup_lon: float
    dropoff_lat: float
    dropoff_lon: float
    passenger_count: int
    vehicle_preference: str
    max_wait_seconds: int
    surge_accepted: bool

class RideshareMatchingEngine:
    """Матчинг водій-пасажир з урахуванням багатьох критеріїв"""

    EARTH_RADIUS_KM = 6371.0

    def haversine_distance(self, lat1: float, lon1: float,
                            lat2: float, lon2: float) -> float:
        """Відстань у км"""
        dlat = np.radians(lat2 - lat1)
        dlon = np.radians(lon2 - lon1)
        a = (np.sin(dlat/2)**2 +
             np.cos(np.radians(lat1)) * np.cos(np.radians(lat2)) * np.sin(dlon/2)**2)
        return 2 * self.EARTH_RADIUS_KM * np.arcsin(np.sqrt(a))

    def estimated_pickup_time(self, driver: Driver, request: RideRequest) -> float:
        """ETA у хвилинах (спрощено через дистанцію, в production — OSRM/Google Maps)"""
        dist_km = self.haversine_distance(
            driver.lat, driver.lon,
            request.pickup_lat, request.pickup_lon
        )
        # Середня швидкість з урахуванням міського трафіку: 20-25 км/год
        return dist_km / 22 * 60

    def compute_match_score(self, driver: Driver,
                             request: RideRequest) -> float:
        """
        Складний скор для матчингу. Мінімізуємо ETA + максимізуємо
        utilization + враховуємо вподобання та якість водія.
        """
        eta_min = self.estimated_pickup_time(driver, request)

        # Жорсткі обмеження
        if driver.vehicle_type != request.vehicle_preference and request.vehicle_preference != 'any':
            if not (request.vehicle_preference == 'economy' and driver.vehicle_type == 'comfort'):
                return -1.0  # Неприпустимий збіг

        if driver.current_passengers + request.passenger_count > driver.max_passengers:
            return -1.0  # Немає місць

        if eta_min > request.max_wait_seconds / 60:
            return -1.0  # Занадто довго чекати

        # Нормалізація компонент (менше ETA = вищий скор)
        eta_score = max(0, 1.0 - eta_min / 10)  # 0 хв = 1.0, 10+ хв = 0

        # Якість водія
        quality_score = (driver.rating - 4.0) / 1.0 * 0.5 + driver.acceptance_rate * 0.5

        # Коефіцієнт детуру для пул-поїздок (якщо водій уже везе пасажирів)
        if driver.current_passengers > 0:
            detour_factor = 0.7  # Пул-поїздка менш приваблива для пасажира
        else:
            detour_factor = 1.0

        return eta_score * 0.55 + quality_score * 0.25 + detour_factor * 0.20

    def batch_match(self, drivers: list[Driver],
                     requests: list[RideRequest]) -> dict:
        """
        Оптимальний батч-матчинг через угорський алгоритм.
        Запускається кожні 30 секунд для накопичених запитів.
        """
        n_drivers = len(drivers)
        n_requests = len(requests)

        if n_drivers == 0 or n_requests == 0:
            return {'matches': [], 'unmatched_requests': [r.id for r in requests]}

        # Матриця вартості (угорський алгоритм мінімізує, тому інвертуємо скор)
        cost_matrix = np.full((n_drivers, n_requests), 1000.0)

        for i, driver in enumerate(drivers):
            for j, request in enumerate(requests):
                score = self.compute_match_score(driver, request)
                if score >= 0:
                    cost_matrix[i, j] = 1.0 - score  # Інверсія для мінімізації

        # Угорський алгоритм O(n³)
        driver_indices, request_indices = linear_sum_assignment(cost_matrix)

        matches = []
        matched_request_ids = set()

        for d_idx, r_idx in zip(driver_indices, request_indices):
            if cost_matrix[d_idx, r_idx] < 900.0:  # Не фіктивне призначення
                matches.append({
                    'driver_id': drivers[d_idx].id,
                    'request_id': requests[r_idx].id,
                    'eta_min': round(self.estimated_pickup_time(drivers[d_idx], requests[r_idx]), 1),
                    'score': round(1.0 - cost_matrix[d_idx, r_idx], 3)
                })
                matched_request_ids.add(requests[r_idx].id)

        unmatched = [r.id for r in requests if r.id not in matched_request_ids]

        return {
            'matches': matches,
            'unmatched_requests': unmatched,
            'match_rate': len(matches) / max(len(requests), 1)
        }


class DriverPositioningAdvisor:
    """Рекомендації водію куди переїхати для наступного замовлення"""

    def suggest_repositioning(self, driver: Driver,
                               demand_heatmap: dict,
                               nearby_drivers: list[Driver],
                               radius_km: float = 3.0) -> dict:
        """
        demand_heatmap: {(lat, lon): expected_requests_next_30min}
        Шукаємо зону з високим попитом і малою конкуренцією серед водіїв.
        """
        best_zone = None
        best_score = -1.0

        for (zone_lat, zone_lon), expected_demand in demand_heatmap.items():
            dist_to_zone = self.haversine_distance(
                driver.lat, driver.lon, zone_lat, zone_lon
            )
            if dist_to_zone > radius_km:
                continue

            # Скільки водіїв уже в цій зоні
            competing_drivers = sum(
                1 for d in nearby_drivers
                if self.haversine_distance(d.lat, d.lon, zone_lat, zone_lon) < 1.0
            )

            # Попит на водія = demand / (drivers + 1)
            demand_per_driver = expected_demand / (competing_drivers + 1)

            # Штраф за дистанцію переміщення
            relocation_cost = dist_to_zone / radius_km * 0.3

            score = demand_per_driver - relocation_cost

            if score > best_score:
                best_score = score
                best_zone = (zone_lat, zone_lon, dist_to_zone, expected_demand)

        if best_zone:
            return {
                'suggest': True,
                'target_lat': best_zone[0],
                'target_lon': best_zone[1],
                'distance_km': round(best_zone[2], 1),
                'expected_wait_min': round(best_zone[2] / 22 * 60, 0),  # Час дістатися
                'expected_demand': best_zone[3]
            }

        return {'suggest': False, 'reason': 'Already in optimal zone'}

    def haversine_distance(self, lat1, lon1, lat2, lon2) -> float:
        dlat = np.radians(lat2 - lat1)
        dlon = np.radians(lon2 - lon1)
        a = np.sin(dlat/2)**2 + np.cos(np.radians(lat1)) * np.cos(np.radians(lat2)) * np.sin(dlon/2)**2
        return 2 * 6371.0 * np.arcsin(np.sqrt(a))

Батч-матчинг кожні 30 секунд (проти жадібного онлайн-матчингу) знижує average ETA на 15–20%. Рекомендації позиціонування для водіїв підвищують їхні earnings per hour на 10–15% і покращують покриття районів з високим попитом. Угорський алгоритм гарантує глобально оптимальне призначення в межах батча.

Що входить до роботи

Порівняння нашого підходу з класичним

Порівняння ETA за часом доби

Як ми прогнозуємо попит?

Для прогнозування попиту використовуємо ансамбль моделей: XGBoost та LSTM. Вхідні ознаки — історичні дані про замовлення з прив'язкою до координат (grid 500x500 метрів), час доби, день тижня, погодні умови. Модель видає heatmap очікуваної кількості запитів у кожній клітинці на найближчі 30 хвилин. Ця heatmap використовується модулем позиціонування водіїв і батч-матчингом для прийняття рішень. Приклад формату heatmap:

{
  "(55.751, 37.617)": 12,
  "(55.753, 37.620)": 8
}

Які метрики ми відстежуємо?

Окрім ETA та match rate, ми моніторимо економічні метрики: середній дохід водія на годину (earnings per hour), частку порожнього пробігу (deadhead miles), а також задоволеність пасажирів (оцінка поїздки). Наші системи дозволяють знизити операційні витрати платформи приблизно на $0.15 за поїздку за рахунок зменшення дистанції подачі.

Типові помилки при впровадженні

• Ігнорування demand heatmap — нерівномірне завантаження, зростання ETA в пікові години.
• Відсутність ML для прогнозу попиту — низька utilization, водії стоять у порожніх зонах.
• Занадто частий перерахунок (кожні 5 сек) — надмірне навантаження без покращення якості.
• Неврахування обмежень місткості — помилки при пул-поїздках.
• Нехтування динамічним ціноутворенням — платформа втрачає прибуток у години пік.

Процес впровадження

1. Аналітика — аудит поточних метрик (ETA, match rate, utilization), аналіз історичних даних, виявлення вузьких місць.
2. Проєктування — архітектура (мікросервіси: FastAPI, Redis, Kafka), вибір версій пакетів.
3. Реалізація — написання коду з unit-тестами (coverage > 90%), code review.
4. Інтеграція — підключення через REST/gRPC, налаштування CI/CD.
5. Навантажувальне тестування — симуляція 10k+ водіїв та 100k+ запитів, p99 latency < 1 с.
6. Деплой та моніторинг — розгортання у вашому контурі, дашборди Grafana, алерти.

Терміни та вартість

Орієнтовні терміни — від 3 до 6 тижнів залежно від обсягу даних і складності інтеграції. Вартість розраховується індивідуально після аналізу вашого завдання. Зв'яжіться з нами для отримання консультації — оцінимо ваш обсяг даних і запропонуємо рішення протягом 3–5 днів.

Ми гарантуємо прозорість вихідного коду та можливість подальшої модифікації вашою командою. Замовте розробку системи матчингу — допоможемо зробити матчинг ефективнішим і підвищити дохід вашої платформи.

Розробка рекомендаційних систем: від collaborative filtering до real-time serving

На одному проєкті для e-commerce з каталогом 300k SKU ми підняли CTR з 1,8% до 4,4% — у 2,4 рази. Перший ривок дала колаборативна фільтрація замість «популярне за останні 7 днів», другий — додавання контентних ознак та re-ranking. Різниця між «показуємо популярне» і «показуємо персоналізоване» — вимірна та суттєва. Нижче — інженерний досвід, який допоміг це зробити, і архітектури, які реально працюють у продакшені.

Collaborative Filtering: матрична факторизація та нейронні підходи

Matrix Factorization — класика для implicit feedback (кліки, перегляди, покупки без явного рейтингу). ALS (Alternating Least Squares) у бібліотеці Implicit обробляє матриці user×item із сотнями мільйонів ненульових значень за хвилини на GPU. Latent factors 64–256, регуляризація λ=0.01–0.1 — стартові параметри. Проблема cold start: для нового користувача або товару немає історії — класичний CF безпорадний, потрібні контентні ознаки або гібрид.

Neural Collaborative Filtering (NCF) замінює скалярний добуток на нейромережу. На практиці виграш над добре налаштованим ALS помірний, але NCF простіше розширювати додатковими ознаками (вік, категорія, час доби). Sequence-aware моделі (SASRec, BERT4Rec) враховують порядок взаємодій — state-of-the-art для сесійних рекомендацій.

Як вибрати архітектуру рекомендаційної системи?

Відповідь залежить від даних, навантаження та вимог до холодного старту. Нижче — три основні підходи з критеріями вибору.

Гібридна архітектура на 20–40% ефективніша за чистий CF за покриттям long-tail — перевірено на каталогах від 100k SKU.

Content-Based Filtering: коли історії взаємодій мало

Content-based рекомендує на основі характеристик товарів, а не поведінки інших користувачів — вирішує cold start для нових items. Текстові ембединги через sentence-transformers (multilingual-e5-base, BGE-M3) → пошук схожих через FAISS IndexFlatIP — запит за <5 ms на 100k товарів. Item2Vec (Word2Vec на послідовностях переглядів) дає інтерпретовані «схожі товари» за пару годин навчання.

Структуровані ознаки (категорія, бренд, ціна) подаються через embedding layers або в gradient boosting — CatBoost працює з категоріями без ручного кодування.

Чому гібридні моделі працюють краще?

Production-системи майже завжди дворівневі. Stage 1 (Retrieval) — швидкий відбір 100–500 кандидатів із 300k товарів через ALS або Two-Tower модель з векторним пошуком (FAISS, Qdrant). Stage 2 (Ranking) — важкий ранжувальник на LightGBM або нейромережі з cross-features, часом, пристроєм та контекстом сесії. LightFM — хороша відправна точка для середнього масштабу без важкої інфраструктури. Наша практика показує: перехід від single-stage до two-stage дає приріст точності на 15–25% при зростанні latency всього на 20–30 мс.

Real-Time Serving: архітектура під навантаження

Latency SLA — 50–100 ms при тисячах запитів на секунду. Base-рекомендації precompute (batch job раз на годину) → Redis по user_id → <5 ms. Real-time re-ranking через Kafka для подій (кліки, додавання в кошик) → оновлення контекстних ознак. Feature serving — Redis з TTL (кількість переглядів за 24 години, останній клікнутий item). При навантаженні 10k req/s ставимо Redis Cluster з реплікацією.

A/B тестування — єдиний достовірний спосіб оцінити покращення. Офлайн-метрики корелюють з онлайн не завжди. Kohavi et al., «Online Controlled Experiments at Large Scale» (KDD 2013) — обов'язкове читання для команди. Тест з 5–10% трафіку, моніторинг CTR, конверсії, revenue per session. Одна з наших клієнтських систем після гібридизації збільшила виручку на 18% за місяць A/B.

Терміни розробки рекомендаційної системи

Етапи та типові часові витрати — у таблиці нижче. Вартість розраховується індивідуально під масштаб каталогу та вимоги до latency.

Що входить у розробку під ключ

1. Аудит даних — щільність матриці user×item (зазвичай <0,1%), розподіл активності, temporal паттерни, cold start статистика.
2. Baseline — «популярне» як простий поріг, який часто важко перевершити.
3. Ітеративне покращення — ALS → контентні ознаки → two-stage → sequence-aware. Кожен крок з A/B.
4. Інфраструктура serving — batch precomputation, Redis, real-time re-ranking, моніторинг у Grafana.
5. Документація — model card з метриками, інструкція з деплою, опис ознак.
6. Навчання команди — сесія з інтерпретації результатів та донавчання моделі.
7. Підтримка — 1 місяць після запуску (фікс інцидентів, доналаштування pipeline).

Ми — команда з 7+ роками досвіду в рекомендаційних системах, реалізували понад 30 проєктів для e-commerce та медіа. Гарантуємо прозоре A/B-тестування та фіксацію покращення метрик.

Хочете оцінити потенціал зростання вашого каталогу? Зв'яжіться з нами для безкоштовного аудиту даних. Замовте розробку рекомендаційної системи — перший прототип протягом двох тижнів.

from implicit.als import AlternatingLeastSquares

model = AlternatingLeastSquares(
    factors=64,
    regularization=0.05,
    iterations=15,
    use_gpu=True
)
model.fit(user_item_matrix)

Більше про математику рекомендаційних систем — у Wikipedia.