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 днів.

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