Xếp tuyến giao hàng: 60 đơn, 4 shipper và bài toán người bán hàng

7:30 một sáng thứ Năm, kho tổng Hà Nội của BanHang có 60 đơn giao nhanh nội thành và 4 shipper xe máy, thùng mỗi xe chứa tối đa 18 đơn. 24 đơn thu COD, tổng 158.260.000 đ. Điều phối viên chia bản đồ thành bốn hướng, mỗi hướng 15 đơn, và shipper tự chọn điểm gần nhất để đi tiếp. Bốn tuyến cộng lại 124,23 km. Shipper hướng đông bắc chạy 36,57 km và mang về kho 67.920.000 đ tiền mặt. Cùng 60 đơn, thuật toán sweep cộng 2-opt xếp ra 103,51 km. Bài này đi từ bài toán người bán hàng (TSP) tới bài toán xếp xe có tải trọng (CVRP): vì sao không vét cạn được, lời giải tối ưu làm mốc cho bộ nhỏ, các heuristic đo trên 60 điểm bằng Python, và các ràng buộc thật cần tới bộ giải như OR-Tools.

1. Sáng thứ Năm ở kho tổng Hà Nội #

Dữ liệu là minh họa. Kho đặt ở tọa độ (21,0000; 105,8200), cách Hồ Gươm khoảng 4,6 km đường chim bay về phía tây nam. 60 điểm giao rải đều ngẫu nhiên trong hình tròn bán kính 6 km quanh kho, hạt giống 2026, mỗi điểm một đơn. Mỗi đơn thu COD với xác suất 35%, theo tỉ lệ vận đơn COD của BanHang; lần sinh này ra 24 đơn. Khoảng cách là haversine trên mặt cầu bán kính 6.371 km, tức đường chim bay, nhân hệ số đường vòng 1,3.

Hệ số 1,3 là giả định, không phải số đo đường phố Hà Nội. Tỉ số giữa quãng đường theo mạng đường và đường chim bay gọi là độ vòng (circuity); Giacomin và Levinson (2015) đo nó ở 51 vùng đô thị đông dân nhất nước Mỹ và thấy chuyến ngắn vòng hơn chuyến dài. Nhân mọi khoảng cách với cùng một hệ số thì tuyến tốt nhất không đổi và mọi tỉ lệ phần trăm trong bài giữ nguyên, chỉ số km đổi theo. Đường thật không co giãn đều như vậy: sang bờ bắc sông Hồng phải qua cầu, đường một chiều làm quãng A sang B khác quãng B sang A. Sản phẩm thật lấy ma trận quãng đường hoặc thời gian từ dịch vụ bản đồ.

# du_lieu.py: dữ liệu minh họa quanh kho tổng Hà Nội của BanHang
import math, random

KHO = (21.0000, 105.8200)        # vĩ độ, kinh độ; tọa độ minh họa
HE_SO_VONG = 1.3                 # giả định: đường đi dài hơn đường chim bay 30%

def sinh_diem(n=60, seed=2026, ban_kinh_km=6.0):    # chỉ số 0 là kho
    rng, diem = random.Random(seed), [KHO]
    for _ in range(n):           # rải đều trong hình tròn bán kính 6 km quanh kho
        r, goc = ban_kinh_km * math.sqrt(rng.random()), rng.uniform(0, 2 * math.pi)
        diem.append((KHO[0] + r * math.sin(goc) / 111.2,
                     KHO[1] + r * math.cos(goc) / (111.2 * math.cos(math.radians(KHO[0])))))
    return diem

def sinh_cod(n=60, seed=2026):   # khoảng 35% đơn thu COD, số tiền minh họa
    rng = random.Random(seed + 1)
    return [0] + [rng.choice([990_000, 2_490_000, 4_990_000, 8_990_000, 15_990_000])
                  if rng.random() < 0.35 else 0 for _ in range(n)]

def haversine_km(a, b, R=6371.0):
    p1, p2 = math.radians(a[0]), math.radians(b[0])
    h = (math.sin((p2 - p1) / 2) ** 2
         + math.cos(p1) * math.cos(p2) * math.sin(math.radians(b[1] - a[1]) / 2) ** 2)
    return 2 * R * math.asin(math.sqrt(h))

def ma_tran(diem):
    return [[HE_SO_VONG * haversine_km(a, b) for b in diem] for a in diem]

def do_dai(tuyen, d):            # tuyến dạng [0, ..., 0]: rời kho rồi về kho
    return sum(d[a][b] for a, b in zip(tuyen, tuyen[1:]))

Cách tay được mô hình thế này: xếp 60 điểm theo phương vị nhìn từ kho (0° là hướng Bắc, theo chiều kim đồng hồ), cắt mỗi 15 điểm thành một nhóm, trong nhóm luôn đi tới điểm chưa giao gần nhất. Bốn tuyến dài 36,57, 29,87, 29,03 và 28,76 km; code ở mục 5.

2. TSP, CVRP và vì sao không thử hết được #

Một shipper tìm thứ tự đi qua mọi điểm rồi về kho sao cho ngắn nhất: đó là bài toán người bán hàng (travelling salesman problem, TSP). Nhiều shipper, mỗi người chở có hạn, phải quyết định ai giao điểm nào và theo thứ tự nào: đó là bài toán định tuyến xe có tải trọng (capacitated vehicle routing problem, CVRP). Dantzig và Ramser đặt bài toán này năm 1959, cho xe chở nhiên liệu từ một kho trung tâm tới các trạm xăng. Với kho và n điểm, mỗi tuyến là một hoán vị của n điểm, đi ngược chiều cho cùng độ dài, nên có n!/2 tuyến.

Số lớn tự nó chưa chứng minh bài khó; điều làm bài khó là chưa ai biết cách tránh thử gần hết. Bản quyết định của TSP, "có tuyến nào dài không quá L không", là NP-đầy đủ. Karp (1972) chứng minh bài toán chu trình Hamilton NP-đầy đủ, và nó quy về TSP: cho cạnh có trong đồ thị dài 1, cạnh không có dài 2, rồi hỏi có tuyến dài không quá số đỉnh không. Khoảng cách trên mặt phẳng không làm bài dễ đi: Papadimitriou (1977) chứng minh TSP Euclid cũng NP-khó. CVRP chứa TSP như trường hợp một xe chở không giới hạn, nên cũng NP-khó. Nếu P ≠ NP thì không có thuật toán thời gian đa thức nào cho tuyến tối ưu ở mọi bộ dữ liệu: thuật toán chính xác trả giá theo hàm mũ, thuật toán nhanh chấp nhận gần đúng.

3. Mốc tối ưu: Held–Karp #

Held và Karp, và độc lập là Bellman, cùng công bố năm 1962 một lời giải chính xác bằng quy hoạch động. Gọi g(S, j) là quãng ngắn nhất rời kho, đi qua đúng tập điểm S và dừng ở j. Khi đó g({j}, j) = d(kho, j), g(S ∪ {k}, k) = min theo j ∈ S của g(S, j) + d(j, k), và tuyến tối ưu dài min theo j của g(mọi điểm, j) + d(j, kho). Thứ tự đi bên trong S không còn quan trọng, chỉ cần tập S và điểm cuối. Có n·2ⁿ trạng thái, mỗi trạng thái xét n điểm đi tiếp: Θ(n²·2ⁿ) thời gian, Θ(n·2ⁿ) bộ nhớ. Code dưới lưu S dạng bitmask và chỉ trả độ dài; muốn lấy cả tuyến thì lưu thêm điểm đứng trước của mỗi trạng thái rồi lần ngược.

# held_karp.py: độ dài tuyến tối ưu, O(n²·2ⁿ) thời gian, O(n·2ⁿ) bộ nhớ
import statistics, time
from du_lieu import sinh_diem, ma_tran

def held_karp(d):
    n, INF = len(d) - 1, float("inf")          # n điểm giao, không tính kho
    g = [[INF] * n for _ in range(1 << n)]      # g[S][j]: qua đúng tập S, dừng ở điểm j+1
    for j in range(n):
        g[1 << j][j] = d[0][j + 1]
    for S in range(1, 1 << n):
        for j in range(n):
            if (c := g[S][j]) == INF:
                continue
            for k in range(n):                 # đi tiếp tới điểm k+1 chưa có trong S
                if not S >> k & 1 and c + d[j + 1][k + 1] < g[S | 1 << k][k]:
                    g[S | 1 << k][k] = c + d[j + 1][k + 1]
    return min(g[-1][j] + d[j + 1][0] for j in range(n))

if __name__ == "__main__":
    diem = sinh_diem(60)
    for n in (8, 10, 12, 14, 16, 18):
        d, lan = ma_tran(diem[:n + 1]), []     # kho và n điểm giao đầu tiên
        for _ in range(3):
            t0 = time.perf_counter()
            km = held_karp(d)
            lan.append(time.perf_counter() - t0)
        print(f"n={n:2}: tối ưu {km:5.2f} km, trung vị 3 lần {statistics.median(lan):7.3f} s")

n= 8: tối ưu 30.48 km, trung vị 3 lần   0.002 s
n=10: tối ưu 30.83 km, trung vị 3 lần   0.012 s
n=12: tối ưu 33.07 km, trung vị 3 lần   0.066 s
n=14: tối ưu 43.17 km, trung vị 3 lần   0.295 s
n=16: tối ưu 45.32 km, trung vị 3 lần   1.897 s
n=18: tối ưu 48.42 km, trung vị 3 lần  10.416 s

Số đo trên Python 3.14.3, laptop Intel Core Ultra 5 125U, Windows 11, trong lúc máy chạy các việc khác. Mỗi lần thêm 2 điểm, thời gian tăng 4,5 đến 6,4 lần; công thức n²·2ⁿ dự đoán 4·((n+2)/n)², tức 5,1 đến 6,3 lần. Thời gian dao động: hai lần chạy khác ra 9,604 và 17,124 s ở n = 18. Bảng g ở n = 18 có 4.718.592 ô. Ngoại suy theo n²·2ⁿ từ 18 lên 60 điểm nhân thời gian khoảng 4,9·10¹³ lần: tính từ 10,416 s là khoảng 16 triệu năm (ước lượng), và bảng cần khoảng 6,9·10¹⁹ ô. Đối chiếu với vét cạn 9! = 362.880 hoán vị trên bốn bộ 9 điểm (hạt giống 1, 2, 3 và 2026) cho cùng độ dài tối ưu.

4. Gần nhất trước, sửa sau: 2-opt #

Láng giềng gần nhất bắt chước shipper: luôn đi tới điểm chưa giao gần nhất. Nó chạy O(n²) nhưng để sót các điểm lẻ, cuối tuyến phải chạy những quãng dài để gom lại. Với khoảng cách thỏa bất đẳng thức tam giác, Rosenkrantz, Stearns và Lewis (1977) chứng minh tuyến láng giềng gần nhất không dài quá ½(⌈log₂ n⌉ + 1) lần tối ưu, và có bộ dữ liệu làm tỉ số này tăng theo log n.

2-opt (Croes, 1958) sửa một tuyến có sẵn. Chọn hai cạnh (a, b) và (c, e), thay bằng (a, c) và (b, e), và đi ngược đoạn từ b tới c. Đổi khi hai cạnh mới ngắn hơn hai cạnh cũ, lặp tới khi không cặp nào làm tuyến ngắn đi. Với khoảng cách Euclid, hai cạnh cắt nhau luôn đổi được như vậy cho tuyến ngắn hơn, nên tuyến 2-opt không tự cắt.

# cai_tien.py: láng giềng gần nhất rồi 2-opt; chạy trực tiếp để so với tối ưu
def gan_nhat(d, diem):           # từ kho, luôn đi tới điểm chưa giao gần nhất
    con, t = set(diem), [0]
    while con:
        t.append(min(con, key=lambda j: d[t[-1]][j]))
        con.remove(t[-1])
    return t + [0]

def two_opt(t, d):               # bỏ (a,b), (c,e); nối (a,c), (b,e); đảo đoạn b..c
    t, tot_hon = t[:], True
    while tot_hon:
        tot_hon = False
        for i in range(1, len(t) - 2):
            for j in range(i + 1, len(t) - 1):
                a, b, c, e = t[i - 1], t[i], t[j], t[j + 1]
                if d[a][c] + d[b][e] < d[a][b] + d[c][e] - 1e-9:
                    t[i:j + 1], tot_hon = t[i:j + 1][::-1], True
    return t

if __name__ == "__main__":
    import statistics, timeit
    from du_lieu import sinh_diem, ma_tran, do_dai
    from held_karp import held_karp
    chenh = {"gần nhất": [], "+ 2-opt": []}
    for seed in range(1, 101):                 # 100 buổi sáng 12 đơn, mỗi buổi một hạt giống
        d = ma_tran(sinh_diem(12, seed=seed))
        toi_uu, t0 = held_karp(d), gan_nhat(d, range(1, 13))
        for ten, t in zip(chenh, (t0, two_opt(t0, d))):
            chenh[ten].append(do_dai(t, d) / toi_uu - 1)
    for ten, c in chenh.items():
        print(f"12 điểm, {ten:9} trúng tối ưu {sum(x < 1e-9 for x in c):3}/100, "
              f"chênh TB {statistics.mean(c):6.2%}, tệ nhất {max(c):6.2%}")
    d = ma_tran(sinh_diem(60))
    for ten, f in {"gần nhất": lambda: gan_nhat(d, range(1, 61)),
                   "+ 2-opt": lambda: two_opt(gan_nhat(d, range(1, 61)), d)}.items():
        ms = statistics.median(timeit.repeat(f, number=1, repeat=3)) * 1000
        print(f"60 điểm, {ten:9} {do_dai(f(), d):6.2f} km, trung vị 3 lần {ms:5.1f} ms")

12 điểm, gần nhất  trúng tối ưu   3/100, chênh TB  9.74%, tệ nhất 32.91%
12 điểm, + 2-opt   trúng tối ưu  56/100, chênh TB  1.35%, tệ nhất 10.74%
60 điểm, gần nhất   96.10 km, trung vị 3 lần   0.8 ms
60 điểm, + 2-opt    85.61 km, trung vị 3 lần   4.1 ms

Trên 100 bộ 12 điểm, láng giềng gần nhất chỉ trúng tối ưu 3 lần và có bộ dài hơn tối ưu 32,91%. Thêm 2-opt, 56 bộ trúng tối ưu, trung bình chỉ dài hơn 1,35%, tệ nhất 10,74%. Johnson và McGeoch (1997) đo trên bộ điểm ngẫu nhiên lớn hơn nhiều: láng giềng gần nhất dài hơn cận dưới Held–Karp (một cận khác của cùng hai tác giả, 1970–1971) từ 23 đến 26% với 100 tới 1 triệu điểm, và láng giềng gần nhất rồi 2-opt còn 6,6% ở 1.000 điểm. Số của bài nhỏ hơn, một phần vì mốc so ở đây là tối ưu thật chứ không phải cận dưới, một phần vì bộ 12 điểm nhỏ hơn nhiều. Ở 60 điểm, 2-opt rút tuyến từ 96,10 xuống 85,61 km trong vài mili giây.

5. Bốn shipper, mỗi người 18 đơn #

Clarke và Wright (1964) bắt đầu từ mỗi đơn một chuyến riêng: kho → i → kho. Ghép chuyến kết thúc ở i với chuyến bắt đầu ở j thì bớt được s(i, j) = d(kho, i) + d(kho, j) − d(i, j), gọi là tiết kiệm. Thuật toán duyệt các cặp theo tiết kiệm giảm dần, và ghép khi i, j còn là đầu mút kề kho của hai tuyến khác nhau và tổng số đơn không quá 18.

Sweep, thường gắn với Gillett và Miller (1974), quét một tia từ kho quanh bản đồ như kim đồng hồ, gom điểm vào xe hiện tại tới khi đủ 18 đơn rồi sang xe mới, sau đó xếp thứ tự trong từng xe. Tài liệu OR-Tools dẫn Wren và Holliday (1972) cho cùng ý tưởng. Code dưới thử cả 60 điểm bắt đầu quét và giữ cách có tổng km nhỏ nhất. Cả hai thuật toán chạy 2-opt trên từng tuyến.

# nhieu_shipper.py: 60 đơn, 4 shipper, mỗi người chở tối đa 18 đơn
import math
from du_lieu import KHO, sinh_diem, sinh_cod, ma_tran, do_dai
from cai_tien import gan_nhat, two_opt

SUC_CHUA = 18
diem, cod = sinh_diem(60), sinh_cod(60)
d, khach = ma_tran(diem), list(range(1, 61))     # mỗi điểm một đơn

def phuong_vi(i):                                 # góc nhìn từ kho: 0 độ là Bắc, theo chiều kim đồng hồ
    dx = (diem[i][1] - KHO[1]) * math.cos(math.radians(KHO[0]))
    return math.degrees(math.atan2(dx, diem[i][0] - KHO[0])) % 360

def chia_doan(vong, co):
    return [vong[k:k + co] for k in range(0, len(vong), co)]

def sweep(suc_chua):                              # quét theo phương vị, đầy xe thì sang xe mới
    xep = sorted(khach, key=phuong_vi)
    ung_vien = ([two_opt(gan_nhat(d, g), d) for g in chia_doan(xep[s:] + xep[:s], suc_chua)]
                for s in range(len(xep)))         # thử mọi điểm bắt đầu quét
    return min(ung_vien, key=lambda ts: sum(do_dai(t, d) for t in ts))

def clarke_wright(suc_chua):                      # mỗi đơn một tuyến, ghép theo tiết kiệm giảm dần
    tuyen, thuoc = {i: [i] for i in khach}, {i: i for i in khach}
    for _, i, j in sorted(((d[0][i] + d[0][j] - d[i][j], i, j)
                           for i in khach for j in khach if i < j), reverse=True):
        a, b = thuoc[i], thuoc[j]
        if a == b or len(tuyen[a]) + len(tuyen[b]) > suc_chua:
            continue
        ta = tuyen[a] if tuyen[a][-1] == i else tuyen[a][::-1]   # i, j phải là đầu mút kề kho
        tb = tuyen[b] if tuyen[b][0] == j else tuyen[b][::-1]
        if ta[-1] == i and tb[0] == j:
            tuyen[a] = ta + tb
            thuoc.update({k: a for k in tb})
            del tuyen[b]
    return [two_opt([0] + t + [0], d) for t in tuyen.values()]

def in_kq(ten, cac_tuyen):
    km = [do_dai(t, d) for t in cac_tuyen]
    tien = [round(sum(cod[i] for i in t) / 1e6, 1) for t in cac_tuyen]
    print(f"{ten:16} tổng {sum(km):6.2f} km, dài nhất {max(km):5.2f} km, "
          f"đơn {[len(t) - 2 for t in cac_tuyen]}, COD triệu {tien}")

if __name__ == "__main__":
    thu_cong = [gan_nhat(d, g) for g in chia_doan(sorted(khach, key=phuong_vi), 15)]
    in_kq("Thủ công", thu_cong)
    in_kq("Thủ công + 2-opt", [two_opt(t, d) for t in thu_cong])
    in_kq("Clarke-Wright", clarke_wright(SUC_CHUA))
    in_kq("Sweep", sweep(SUC_CHUA))

Thủ công         tổng 124.23 km, dài nhất 36.57 km, đơn [15, 15, 15, 15], COD triệu [67.9, 27.4, 30.9, 31.9]
Thủ công + 2-opt tổng 111.78 km, dài nhất 32.29 km, đơn [15, 15, 15, 15], COD triệu [67.9, 27.4, 30.9, 31.9]
Clarke-Wright    tổng 105.11 km, dài nhất 32.84 km, đơn [12, 18, 18, 12], COD triệu [31.0, 31.9, 60.4, 35.0]
Sweep            tổng 103.51 km, dài nhất 33.30 km, đơn [18, 18, 18, 6], COD triệu [71.4, 44.9, 40.9, 1.0]

Phần lớn chênh lệch đến từ thứ tự đi: giữ nguyên bốn nhóm của điều phối viên, chỉ chạy 2-opt đã bớt 12,45 km. Chia nhóm lại bớt thêm 6,67 km với Clarke–Wright và 8,27 km với sweep. Sweep có tổng nhỏ nhất nhưng chia 18, 18, 18 và 6 đơn, và tuyến dài nhất của nó, 33,30 km, dài hơn của mọi cách khác trừ cách tay. Ca sáng chỉ xong khi tuyến dài nhất xong, nên tổng km nhỏ nhất chưa chắc là phương án nên chọn. Cột COD cho thấy điều các thuật toán không biết: sweep để một shipper cầm 71,4 triệu, Clarke–Wright 60,4 triệu. Cả script chạy dưới 1 giây.

6. Ràng buộc thật: COD, khung giờ, kẹt xe, khách vắng #

Bài toán ở mục 5 chỉ có một ràng buộc là số đơn mỗi xe. Ca giao thật có thêm:

• Tiền COD. Shipper cầm tiền mặt tới lúc nộp và đối soát cuối ca, nên công ty đặt trần tiền cho mỗi người, ở đây minh họa 50 triệu. Đây là tải trọng thứ hai, cộng dồn dọc tuyến như số đơn.
• Khung giờ. Khách hẹn 9:00 đến 10:00 biến bài toán thành VRP có khung giờ (VRPTW). Trong OR-Tools, đó là một dimension thời gian cho phép chờ (slack), cộng CumulVar(index).SetRange(...) tại từng điểm.
• Kẹt xe theo giờ. Ma trận trong bài không đổi theo giờ. Đường thật thì đổi: cùng một cặp điểm, lúc 7:30 và lúc 10:00 đi hết thời gian khác nhau. Bài này không mô hình phần đó.
• Khách vắng, giao lại. Xếp lại giữa ca là bài toán mới, xuất phát từ vị trí hiện tại của từng shipper; OR-Tools nhận điểm đầu và điểm cuối riêng cho từng xe. AddDisjunction kèm một mức phạt cho phép bộ giải bỏ một điểm khi không xếp kịp và cộng mức phạt đó vào hàm mục tiêu.

Google OR-Tools có bộ giải định tuyến dựng sẵn các ràng buộc này. Bản 9.15.6755 có wheel cho Python 3.14 trên Windows x64: pip install ortools==9.15.6755. Code dưới giải lại 60 đơn ở mục 5 với trần COD. Lời giải đầu theo Clarke–Wright (SAVINGS), sau đó là guided local search, metaheuristic mà tài liệu OR-Tools gọi là thường hiệu quả nhất cho định tuyến xe, dừng sau 30 giây. Bộ giải chỉ nhận chi phí nguyên, nên ma trận đổi ra mét.

# ortools_vrp.py: cùng 60 đơn, thêm trần 50 triệu tiền COD mỗi shipper
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
from nhieu_shipper import d, cod, SUC_CHUA, in_kq

SO_XE, TRAN_COD = 4, 50_000_000
met = [[round(x * 1000) for x in hang] for hang in d]      # bộ giải chỉ nhận số nguyên: đổi ra mét
qly = pywrapcp.RoutingIndexManager(len(met), SO_XE, 0)      # nút 0 là kho
mh, nut = pywrapcp.RoutingModel(qly), qly.IndexToNode
mh.SetArcCostEvaluatorOfAllVehicles(mh.RegisterTransitCallback(lambda a, b: met[nut(a)][nut(b)]))
don = mh.RegisterUnaryTransitCallback(lambda a: 0 if nut(a) == 0 else 1)
mh.AddDimensionWithVehicleCapacity(don, 0, [SUC_CHUA] * SO_XE, True, "SoDon")
tien = mh.RegisterUnaryTransitCallback(lambda a: cod[nut(a)])
mh.AddDimensionWithVehicleCapacity(tien, 0, [TRAN_COD] * SO_XE, True, "TienCOD")

ts = pywrapcp.DefaultRoutingSearchParameters()
ts.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.SAVINGS
ts.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
ts.time_limit.seconds = 30
kq = mh.SolveWithParameters(ts)
if kq is None:
    raise SystemExit("Không tìm được lời giải thỏa mọi ràng buộc")

cac_tuyen = []
for xe in range(SO_XE):
    i, t = mh.Start(xe), []
    while not mh.IsEnd(i):
        t.append(nut(i))
        i = kq.Value(mh.NextVar(i))
    cac_tuyen.append(t + [0])
in_kq("OR-Tools", cac_tuyen)

OR-Tools         tổng 103.82 km, dài nhất 31.50 km, đơn [17, 18, 9, 16], COD triệu [47.0, 38.9, 26.0, 46.4]

Năm lần chạy ra 102,80, 103,31, 103,82, 103,82 và 103,91 km; khối trên là một lần ra đúng trung vị. Dừng theo thời gian thì số bước tìm kiếm phụ thuộc tốc độ và độ bận của máy, nên kết quả đổi theo lần chạy. Ở cả năm lần, không shipper nào cầm quá 47,9 triệu, và tổng km ngang sweep (103,51 km) dù có thêm ràng buộc. Với lời giải đầu PATH_CHEAPEST_ARC như ví dụ CVRP trong tài liệu, bản thử có trần COD không tìm được lời giải nào và SolveWithParameters trả None, nên code kiểm trường hợp này.

Những chỗ hay hiểu sai #

• "NP-khó nghĩa là không giải được." 12 điểm giải đúng trong khoảng 0,1 giây. NP-khó nói về tốc độ tăng: thêm 2 điểm, Held–Karp chậm đi khoảng 5 lần.
• "Đi điểm gần nhất là đủ tốt." Trên 100 bộ 12 điểm, nó dài hơn tối ưu trung bình 9,74%, tệ nhất 32,91%. Thêm 2-opt tốn vài mili giây.
• "Tổng km nhỏ nhất là phương án tốt nhất." Sweep có tổng nhỏ nhất trong ba heuristic nhưng chia 18, 18, 18 và 6 đơn và để một shipper cầm 71,4 triệu tiền COD.
• "2-opt dùng nguyên được với ma trận đường thật." Đường một chiều làm d(i, j) khác d(j, i). 2-opt đảo chiều cả đoạn b…c, nên với ma trận không đối xứng phải tính lại cả đoạn bị đảo, không chỉ hai cạnh.

Đọc tiếp #

• Bài toán hai vị tướng và giới hạn của "gửi đúng một lần": sự kiện "đã giao, đã thu COD" từ app shipper đi qua broker có thể tới hai lần; consumer đối soát phải khử trùng như mục 6 của bài đó.
• Consistent hashing: một bài toán kinh điển khác đo trên dữ liệu BanHang, nơi cách chia đơn giản nhất tốn hơn hẳn cách chia có cấu trúc.
• Chia tiền không lệch một đồng: mỗi vận đơn thu COD bao nhiêu khi một đơn giảm giá bị tách ra nhiều vận đơn.

Nguồn #

• Held, Karp. A Dynamic Programming Approach to Sequencing Problems. Journal of SIAM 10(1), 1962. Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM 9(1), 1962.
• Karp. Reducibility among Combinatorial Problems. Complexity of Computer Computations, 1972. Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science 4(3), 1977.
• Dantzig, Ramser. The Truck Dispatching Problem. Management Science 6(1), 1959.
• Clarke, Wright. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research 12(4), 1964. Gillett, Miller. A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operations Research 22(2), 1974.
• Croes. A Method for Solving Traveling-Salesman Problems. Operations Research 6(6), 1958. Rosenkrantz, Stearns, Lewis. An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing 6(3), 1977.
• Johnson, McGeoch. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization, 1997: bảng 1 và 4.
• Giacomin, Levinson. Road network circuity in metropolitan areas. Environment and Planning B 42(6), 2015.
• Google OR-Tools: CVRP, VRPTW, bỏ điểm với mức phạt, tùy chọn tìm kiếm, điểm đầu và cuối riêng cho từng xe, ortools 9.15.6755 trên PyPI.