Bài 3: Vì sao Grab không luôn gọi tài xế gần nhất? Bài toán ghép cặp trên đồ thị hai phía

Bạn đặt xe và thấy tài xế được gán cho mình lại ở xa hơn một chiếc xe khác ngay đầu ngõ? Đó không phải lỗi. Grab cho biết họ cân nhắc hơn 40 yếu tố theo thời gian thực chứ không chỉ khoảng cách – và bên dưới là một bài toán kinh điển của tin học: ghép cặp trên đồ thị hai phía.

Bài thứ ba của chuyên mục "Thuật toán trong đời sống". Qua câu chuyện gọi xe, bạn sẽ thấy vì sao thuật toán tham lam "chọn gần nhất" không phải lúc nào cũng tốt, và thuật toán tìm đường tăng giải quyết vấn đề thế nào.

1. Tham lam "gần nhất" có vấn đề gì?

Cách đơn giản nhất: khách nào đặt trước thì gán tài xế gần nhất. Uber cũng từng làm vậy, nhưng trang giới thiệu về cơ chế ghép cặp của họ viết rằng "gần nhất không phải lúc nào cũng nhanh nhất". Xét ví dụ:

	Khách X	Khách Y
Tài xế 1	2 phút	3 phút
Tài xế 2	4 phút	15 phút

• Tham lam: khách Y đặt trước → nhận tài xế 1 (3 phút). Khách X còn lại tài xế 2 (4 phút). Tổng thời gian chờ: 7 phút. Vẫn ổn.
• Nhưng nếu X đặt trước → X nhận tài xế 1 (2 phút), Y phải chờ tài xế 2 tới 15 phút. Tổng: 17 phút!
• Tối ưu chung: X ← tài xế 2, Y ← tài xế 1, tổng 7 phút, không ai phải chờ 15 phút.

Vì vậy, thay vì gán ngay lập tức, các nền tảng gọi xe gom yêu cầu trong vài giây rồi ghép cùng lúc. Uber viết rằng họ chờ "chỉ vài giây sau yêu cầu" để ghép cả nhóm khách và tài xế trong "một đợt" (batch), giúp giảm thời gian chờ trung bình. Kỹ sư Lyft mô tả việc này là bài toán ghép cặp trọng số lớn nhất trên đồ thị hai phía, chạy lại sau mỗi vài giây. Cửa sổ gom càng dài thì ghép càng tốt, nhưng khách phải chờ được gán lâu hơn và dễ hủy chuyến – một sự đánh đổi điển hình.

2. Mô hình hóa: đồ thị hai phía

• Bên trái: các tài xế đang rảnh. Bên phải: các khách đang chờ.
• Có cạnh giữa tài xế i và khách j nếu tài xế đến được trong thời gian cho phép (ví dụ 5 phút). Trọng số cạnh có thể là thời gian đón, chiều dài chuyến, đánh giá tài xế…
• Ghép cặp (matching): chọn các cạnh sao cho mỗi tài xế nhận tối đa một khách và mỗi khách có tối đa một tài xế.

Hai câu hỏi kinh điển:

1. Ghép cặp cực đại: phục vụ được nhiều khách nhất.
2. Bài toán phân công (assignment): mọi khách đều được phục vụ, với tổng thời gian chờ nhỏ nhất – giải bằng thuật toán Hungarian. Thuật toán được Harold Kuhn công bố năm 1955, đặt tên để ghi nhận công trình của hai nhà toán học Hungary là Dénes Kőnig và Jenő Egerváry.

3. Thuật toán đường tăng (Kuhn)

Ý tưởng rất đẹp: lần lượt xét từng tài xế i, thử gán cho một khách j kề. Nếu j đã có tài xế k, ta hỏi "tài xế k có thể chuyển sang khách khác không?" – một cách đệ quy. Nếu tìm được một chuỗi chuyển đổi như vậy (gọi là đường tăng – augmenting path), số cặp tăng thêm 1.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Ghép tài xế với khách: cạnh (i, j) nếu tài xế i đến được khách j trong 5 phút
int nD, nK;
vector<vector<int>> can;      // can[i] = danh sách khách tài xế i đón được
vector<int> matchK;           // matchK[j] = tài xế đang nhận khách j (-1 nếu chưa)
vector<bool> seen;

bool tryAssign(int i){        // tìm đường tăng (augmenting path) từ tài xế i
    for(int j : can[i]){
        if(seen[j]) continue;
        seen[j] = true;
        if(matchK[j] == -1 || tryAssign(matchK[j])){
            matchK[j] = i;
            return true;
        }
    }
    return false;
}

int main(){
    nD = 3; nK = 3;
    can = {{0, 1}, {0}, {1, 2}};  // tài xế 0 đón được khách 0,1; tài xế 1 chỉ đón khách 0; ...
    matchK.assign(nK, -1);
    int served = 0;
    for(int i = 0; i < nD; i++){
        seen.assign(nK, false);
        if(tryAssign(i)) served++;
    }
    cout << "So khach duoc phuc vu: " << served << "\n";
    for(int j = 0; j < nK; j++)
        cout << "Khach " << j << " <- tai xe " << matchK[j] << "\n";
}

def max_matching(can, n_khach):
    match = [-1] * n_khach            # match[j] = tài xế nhận khách j

    def try_assign(i, seen):
        for j in can[i]:
            if j in seen:
                continue
            seen.add(j)
            if match[j] == -1 or try_assign(match[j], seen):
                match[j] = i
                return True
        return False

    served = sum(try_assign(i, set()) for i in range(len(can)))
    return served, match

can = [[0, 1], [0], [1, 2]]
print(max_matching(can, 3))   # (3, [1, 0, 2])

Trong ví dụ: tài xế 0 đón được khách 0 hoặc 1, tài xế 1 chỉ đón được khách 0, tài xế 2 đón được khách 1 hoặc 2. Tham lam "gán khách đầu tiên" sẽ cho tài xế 0 nhận khách 0, rồi tài xế 1 không còn ai. Thuật toán đường tăng tự "dời" tài xế 0 sang khách 1 để tài xế 1 nhận khách 0 – kết quả phục vụ đủ cả 3 khách. Độ phức tạp O(V × E).

4. Grab làm gì trong thực tế?

• Tìm tài xế gần theo đường đi, không phải đường chim bay: trên blog kỹ thuật, Grab giới thiệu hệ thống Pharos (2020) tìm K tài xế gần nhất theo khoảng cách trên mạng lưới đường từ bản đồ OpenStreetMap, với độ trễ P99 khoảng 50 ms cho mỗi truy vấn. Một tài xế cách bạn 200 m nhưng ở bên kia dải phân cách có thể mất 10 phút để quay đầu!
• Hơn 40 yếu tố: Grab cho biết hệ thống ghép cặp dùng hơn 40 yếu tố theo thời gian thực ngoài khoảng cách, chia bản đồ bằng geohash, thậm chí tính cả quy định biển số chẵn – lẻ ở Jakarta, và gom các đơn đồ ăn gần nhau.
• Đi chung xe (GrabShare): Grab mô tả việc ghép chuyến đi chung là một bài toán tối ưu có ràng buộc (ví dụ số ghế trống). Trong ví dụ của họ, một lộ trình đi chung dài 23,72 km thay vì 39,13 km nếu hai chuyến đi riêng.
• Giá theo nhu cầu (surge): khi số người đặt xe nhiều hơn số tài xế, giá tăng để thu hút thêm tài xế vào khu vực – một vòng điều chỉnh cung cầu bằng thuật toán.

Giao hàng: bài toán người du lịch

Với shipper giao 30 đơn hàng một ngày, câu hỏi trở thành thứ tự giao nào ngắn nhất – bài toán người du lịch (TSP) và bài toán định tuyến xe (VRP), vốn là bài toán NP-khó. Năm 2021, Amazon và MIT tổ chức Amazon Last Mile Routing Research Challenge với dữ liệu 9.184 tuyến giao hàng thật; hơn 2.000 người đăng ký, 229 đội tham gia, và giải nhất 100.000 USD thuộc về nhóm nghiên cứu từ ĐH Waterloo, ĐH Bonn và ĐH Roskilde. Mục tiêu đặc biệt là đưa "kinh nghiệm của tài xế" vào thuật toán tối ưu lộ trình.

5. Bạn học được gì từ đây?

• Tham lam không phải lúc nào cũng đúng – luôn thử tìm phản ví dụ, như bảng 2 tài xế ở trên.
• Ghép cặp hai phía, luồng cực đại, bài toán phân công là những chủ đề nâng cao trong chương trình chuyên Tin và ICPC – và chúng đang vận hành các ứng dụng hàng triệu người dùng.
• Thực tế luôn có đánh đổi: chất lượng lời giải và thời gian phản hồi.

Bài tập luyện tập

• CSES – School Dance (ghép cặp cực đại trên đồ thị hai phía)
• CSES – Download Speed (luồng cực đại)

Bạn đã từng gặp trường hợp được gán tài xế ở xa hơn chưa? Giờ bạn đã biết lý do – hãy chia sẻ câu chuyện trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 4: TikTok, YouTube, Netflix biết bạn thích gì? Thuật toán gợi ý hoạt động ra sao

Đọc tiếp: thuật toán gợi ý →

← Bài trước: PageRank của GoogleXem tất cả 27 bài →

Nguồn tham khảo

• Uber – How Uber matches riders and drivers
• Lyft Engineering – Solving Dispatch in a Ridesharing Problem Space
• Kuhn (1955) – The Hungarian method for the assignment problem
• Wikipedia – Jenő Egerváry
• Grab Engineering – Pharos: Searching Nearby Drivers on Road Network at Scale
• Grab – Grab doesn't always assign the nearest driver to you, here's why
• Grab Engineering – The Data and Science Behind GrabShare Part I
• Grab – Surge pricing explained
• MIT News – Amazon Last Mile Routing Research Challenge (2021)
• MIT CTL – Bộ dữ liệu Amazon Last Mile Routing