Bài 7: Shipper đi đường nào để giao hàng nhanh nhất? Bài toán người du lịch (TSP) trong đời sống

Một shipper nhận 30 đơn hàng mỗi sáng. Nên giao nhà nào trước, nhà nào sau? Nghe đơn giản, nhưng đây là một trong những bài toán nổi tiếng và "khó nhằn" nhất của khoa học máy tính: bài toán người du lịch (Travelling Salesman Problem – TSP).

Bài thứ bảy của chuyên mục "Thuật toán trong đời sống". Nếu bạn đã học quy hoạch động trạng thái (bitmask DP), bạn đã có trong tay công cụ để giải chính xác bài toán này với vài chục điểm.

1. Bài toán: đi qua tất cả các điểm, quãng đường ngắn nhất

Cho một kho hàng và n điểm giao, biết khoảng cách giữa mọi cặp điểm. Tìm thứ tự đi qua tất cả các điểm đúng một lần rồi quay về kho sao cho tổng quãng đường nhỏ nhất.

Với n điểm có (n − 1)! thứ tự khác nhau. 10 điểm đã có 362.880 cách; 20 điểm thì lên tới khoảng 1,2 × 10¹⁷ cách – thử hết là bất khả thi. Theo Britannica, TSP là một bài toán NP-đầy đủ: đến nay chưa ai tìm ra thuật toán thời gian đa thức cho nó.

Ví dụ nhỏ: kho và 4 điểm giao

km	Kho	A	B	C	D
Kho	–	12	10	19	8
A	12	–	3	7	2
B	10	3	–	6	20
C	19	7	6	–	4
D	8	2	20	4	–

• Chiến lược tham lam "luôn đi tới điểm gần nhất": Kho → D (8) → A (2) → B (3) → C (6) → Kho (19) = 38 km.
• Lộ trình tối ưu: Kho → B (10) → A (3) → C (7) → D (4) → Kho (8) = 32 km.

Bài học: chọn điểm gần nhất ở mỗi bước khiến shipper bị "kẹt" ở điểm C xa kho và phải chạy 19 km quay về. Tham lam cục bộ không đảm bảo tối ưu toàn cục.

2. Giải chính xác bằng quy hoạch động bitmask (Held–Karp)

Năm 1962, Bellman và độc lập là Held & Karp đề xuất thuật toán quy hoạch động cho TSP. Gọi f[mask][i] là quãng đường ngắn nhất xuất phát từ kho, đã đi qua đúng tập điểm mask (biểu diễn bằng dãy bit) và đang đứng ở điểm i:

f[mask ∪ {j}][j] = min( f[mask][i] + d[i][j] ) với j chưa thuộc mask. Đáp án = min( f[tất cả][i] + d[i][kho] ).

Độ phức tạp O(2ⁿ × n²): với n = 20 khoảng 4 × 10⁸ phép tính – chạy được trong vài giây, trong khi thử hết hoán vị phải mất hàng nghìn năm.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Held–Karp: shipper xuất phát từ kho (điểm 0), đi qua tất cả điểm giao rồi quay về kho
int main(){
    int n = 5; // kho + 4 điểm giao
    int d[5][5] = {{0,12,10,19,8},{12,0,3,7,2},{10,3,0,6,20},{19,7,6,0,4},{8,2,20,4,0}};
    const int INF = 1e9;
    // f[mask][i]: quãng đường ngắn nhất xuất phát từ 0, đã đi qua tập mask, đang đứng ở i
    vector<vector<int>> f(1 << n, vector<int>(n, INF));
    f[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++)
        for(int i = 0; i < n; i++){
            if(f[mask][i] == INF || !(mask >> i & 1)) continue;
            for(int j = 0; j < n; j++) if(!(mask >> j & 1))
                f[mask | 1 << j][j] = min(f[mask | 1 << j][j], f[mask][i] + d[i][j]);
        }
    int best = INF;
    for(int i = 1; i < n; i++) best = min(best, f[(1 << n) - 1][i] + d[i][0]);
    cout << "Quang duong toi uu: " << best << " km\n";
    // So sánh với chiến lược tham lam "luôn đi tới điểm gần nhất"
    vector<bool> seen(n); int cur = 0, total = 0; seen[0] = true;
    for(int step = 1; step < n; step++){
        int nx = -1;
        for(int j = 0; j < n; j++) if(!seen[j] && (nx < 0 || d[cur][j] < d[cur][nx])) nx = j;
        total += d[cur][nx]; seen[nx] = true; cur = nx;
    }
    total += d[cur][0];
    cout << "Tham lam (diem gan nhat): " << total << " km\n";
}

from itertools import permutations
d = [[0,12,10,19,8],[12,0,3,7,2],[10,3,0,6,20],[19,7,6,0,4],[8,2,20,4,0]]
n = len(d)
INF = float('inf')
# Held–Karp: f[mask][i] = quãng đường ngắn nhất từ kho 0, đã thăm tập mask, đang ở i
f = [[INF] * n for _ in range(1 << n)]
f[1][0] = 0
for mask in range(1 << n):
    for i in range(n):
        if f[mask][i] == INF or not mask >> i & 1: continue
        for j in range(n):
            if not mask >> j & 1:
                nm = mask | 1 << j
                f[nm][j] = min(f[nm][j], f[mask][i] + d[i][j])
best = min(f[(1 << n) - 1][i] + d[i][0] for i in range(1, n))
print("Quang duong toi uu:", best, "km")
# Kiểm tra bằng cách thử hết (n-1)! thứ tự – chỉ khả thi khi n rất nhỏ
brute = min(sum(d[a][b] for a, b in zip((0,) + p, p + (0,))) for p in permutations(range(1, n)))
print("Thu het moi thu tu:", brute, "km")

Kết quả: tối ưu 32 km, tham lam 38 km – chênh gần 19%. Nhân lên với hàng nghìn shipper mỗi ngày, đó là một khoản xăng và thời gian khổng lồ.

3. Ngoài đời thực: hàng chục nghìn điểm thì sao?

Lịch sử giải TSP

• 1954: Dantzig, Fulkerson và Johnson giải chính xác bài toán 49 thành phố nước Mỹ (mỗi bang một thành phố, cộng Washington D.C.) – một kích thước "ấn tượng vào thời điểm đó", theo Đại học Waterloo.
• 2006: phần mềm Concorde (của Applegate, Bixby, Chvátal, Cook) giải chính xác bài toán 85.900 điểm phát sinh từ thiết kế chip máy tính. Riêng việc chứng minh lời giải là tối ưu đã tốn hơn 136 năm CPU.

Bài toán định tuyến xe (VRP)

Công ty giao hàng có nhiều xe, mỗi xe có tải trọng giới hạn, mỗi khách có khung giờ nhận hàng. Đây là bài toán định tuyến xe (Vehicle Routing Problem – VRP). Tài liệu của Google OR-Tools viết: khi chỉ có một xe, VRP thu gọn thành TSP. Người ta thường kết hợp:

• Thuật toán xây dựng nhanh (như tham lam) để có lời giải ban đầu;
• Tìm kiếm cục bộ: thử đảo ngược một đoạn đường (2-opt), chuyển đơn giữa các xe… để cải thiện dần;
• Metaheuristic (tìm kiếm tabu, mô phỏng luyện kim) để thoát khỏi "cực tiểu địa phương".

UPS và ORION

Theo thông cáo của UPS năm 2015, hệ thống định tuyến ORION dự kiến giúp công ty giảm 100 triệu dặm đường chạy mỗi năm, tiết kiệm 10 triệu gallon nhiên liệu và hơn 300 triệu USD, giảm khoảng 100.000 tấn CO₂. Trung bình mỗi tuyến bớt được 6–8 dặm.

Ở Việt Nam

• Tài liệu cho nhà phát triển của Ahamove mô tả công cụ "Route Optimization" để giải bài toán định tuyến xe, bao gồm cả biến thể có khung thời gian (TWVRP).
• Theo blog của Giao Hàng Nhanh (GHN), hệ thống hằng ngày đưa ra tuyến đường tối ưu để nhân viên đi lấy hàng và lộ trình giao hàng nhanh nhất cho shipper.

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

• Quy hoạch động bitmask – chủ đề nâng cao trong đề HSG – chính là thuật toán chính xác kinh điển cho TSP.
• Với bài toán NP-khó, thực tế thường dùng heuristic: chấp nhận lời giải "đủ tốt" trong thời gian ngắn.
• Tham lam dễ cài nhưng có thể sai – luôn tìm phản ví dụ trước khi tin vào nó.

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

• CSES – Hamiltonian Flights (đếm đường đi Hamilton bằng bitmask DP)
• AtCoder ABC180 E – Traveling Salesman among Aerial Cities

Thử thách: thêm điểm giao E vào bảng khoảng cách và chạy lại code. Chiến lược tham lam còn chênh bao nhiêu so với tối ưu? Chia sẻ trong phần bình luận nhé!

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

Bài 8: File ZIP nén dữ liệu như thế nào? Mã Huffman, LZ77 và thuật toán DEFLATE

Đọc tiếp: file ZIP & mã Huffman →

← Bài trước: sửa lỗi chính tả & DNAXem tất cả 27 bài →

Nguồn tham khảo

• Đại học Waterloo – Dantzig, Fulkerson, Johnson (1954)
• Đại học Waterloo – Các cột mốc giải TSP
• Concorde TSP Solver
• Applegate và cộng sự – Certification of an optimal TSP tour through 85,900 cities
• Britannica – Travelling salesman problem
• Wikipedia – Held–Karp algorithm
• Google OR-Tools – Vehicle Routing Problem
• UPS (2015) – UPS Accelerates Use of Routing Optimization Software
• Ahamove – Route Optimization
• GHN – CTO GHN: số hóa dây chuyền giao hàng