Tối ưu hoá 6 — Bài toán mạng, định tuyến & lịch

Khi bài toán có hình dạng của một tấm bản đồ

Ba bài trước xây bộ khung tổng quát: LP, MILP và solver thực hành. Bài này đi vào một họ bài toán có cấu trúc đặc biệt — chúng sống trên một mạng (graph: điểm và cạnh) hoặc một lịch (thời gian và nguồn lực). Điểm chung: chúng cực kỳ trực quan, vẽ được ra giấy, và xuất hiện dày đặc trong vận hành ngân hàng — tiếp quỹ ATM, xếp ca quầy, phân bổ cán bộ thẩm định, chuyển tiền giữa kho quỹ.

Vì có cấu trúc, nhiều bài toán mạng có thuật toán chuyên biệt cực nhanh (Dijkstra, Hungarian, thuật toán luồng) thay vì phải quăng vào solver MILP tổng quát. Nhưng khi thêm ràng buộc thực tế (tải trọng xe, khung giờ, kỹ năng nhân viên), chúng lại trở thành tổ hợp khó và cần solver chuyên như OR-Tools routing hoặc CP-SAT. Bài này giúp bạn nhận diện đúng dạng và chọn đúng công cụ.

1. Bài toán mạng (network / graph)

Mạng gồm nút (node/vertex — kho quỹ, chi nhánh, ATM, tài khoản) và cạnh (edge/arc — tuyến đường, kênh chuyển tiền) có trọng số (quãng đường, chi phí, công suất). Nhiều bài toán tối ưu kinh điển nằm trên cấu trúc này.

1.1 Shortest path — đường ngắn nhất

Tìm đường đi có tổng trọng số nhỏ nhất giữa hai nút. Trọng số có thể là km, thời gian, hoặc chi phí. Thuật toán kinh điển:

• Dijkstra — cho đồ thị trọng số không âm, độ phức tạp O(E log V). Rất nhanh, dùng khắp nơi (định tuyến GPS, mạng viễn thông).
• Bellman-Ford — chịu được cạnh trọng số âm, phát hiện chu trình âm; chậm hơn.
• A* — Dijkstra có thêm hàm heuristic ước lượng khoảng cách còn lại, tăng tốc khi có tọa độ địa lý.

Trong ngân hàng: tính tuyến đi ngắn nhất giữa các điểm ATM cho đội tiếp quỹ, hoặc tìm chuỗi trung gian rẻ nhất để định tuyến một giao dịch liên ngân hàng.

1.2 Max-flow / min-cut — luồng cực đại và lát cắt cực tiểu

Cho mạng có công suất trên mỗi cạnh (capacity — lượng tối đa chảy qua), tìm luồng lớn nhất từ nguồn (source) tới đích (sink). Định lý max-flow min-cut nói: luồng cực đại đúng bằng tổng công suất của lát cắt nhỏ nhất — tức "nút cổ chai" của hệ thống. Thuật toán: Ford-Fulkerson, Edmonds-Karp, Dinic.

Ứng dụng: đánh giá năng lực thông của mạng lưới xử lý giao dịch, tìm điểm nghẽn trong pipeline thanh toán, hoặc phân bổ băng thông/hạn mức.

1.3 Min-cost flow — luồng chi phí nhỏ nhất

Tổng quát hơn: đẩy một lượng luồng cho trước qua mạng sao cho tổng chi phí nhỏ nhất, mỗi cạnh có cả công suất lẫn chi phí đơn vị. Đây là khung sườn thống nhất — cả shortest path, max-flow, transportation, assignment đều là trường hợp riêng của min-cost flow.

Ví dụ ngân hàng: điều tiết tiền mặt giữa các kho quỹ và chi nhánh. Kho A dư tiền, chi nhánh B thiếu; mỗi tuyến vận chuyển có chi phí (thuê xe áp tải, bảo hiểm). Cần chuyển đủ để cân bằng với tổng chi phí thấp nhất — đúng dạng min-cost flow.

1.4 Transportation & transshipment — bài toán vận chuyển

Transportation problem: có m nguồn cung (kho, cung s_i) và n điểm cầu (chi nhánh/ATM, cầu d_j), chi phí c_ij để chuyển một đơn vị từ nguồn i tới đích j. Tìm lượng chuyển x_ij ≥ 0 sao cho thỏa cung/cầu và tối thiểu tổng chi phí. Mô hình LP kinh điển:

min   Σ_i Σ_j  c_ij · x_ij
s.t.  Σ_j x_ij ≤ s_i     ∀ nguồn i   (không vượt cung)
      Σ_i x_ij ≥ d_j     ∀ đích  j   (đủ cầu)
      x_ij ≥ 0

Transshipment mở rộng cho phép điểm trung chuyển (hub) — hàng qua kho trung gian trước khi tới đích. Đây chính là min-cost flow trên mạng có nút trung gian.

Bối cảnh NCB: tiếp quỹ tiền mặt giữa kho quỹ trung tâm → kho vùng → chi nhánh/ATM. Đầu vào là dự báo nhu cầu rút tiền theo điểm, chi phí vận chuyển từng tuyến; đầu ra là kế hoạch điều tiết tối ưu.

1.5 Assignment — bài toán gán

Trường hợp đặc biệt của transportation với cung = cầu = 1: gán một-đối-một giữa hai tập bằng nhau (n người ↔ n việc), mỗi cặp có chi phí c_ij, tối thiểu tổng chi phí. Giải bằng thuật toán Hungarian (Kuhn-Munkres) trong O(n³) — rất nhanh, không cần solver MILP.

min   Σ_i Σ_j  c_ij · x_ij
s.t.  Σ_j x_ij = 1   ∀ i     (mỗi người nhận đúng 1 việc)
      Σ_i x_ij = 1   ∀ j     (mỗi việc gán đúng 1 người)
      x_ij ∈ {0,1}

Ngân hàng: gán cán bộ thẩm định cho từng hồ sơ theo mức phù hợp (chi phí = thời gian xử lý dự kiến hoặc "độ lệch kỹ năng"), gán quầy cho khách VIP, phân bổ ca trực cho nhân viên.

2. Định tuyến (routing)

Định tuyến là họ bài toán "đi thăm nhiều điểm" — khác shortest path (chỉ 2 điểm) ở chỗ phải ghé nhiều điểm và quay về, làm không gian nghiệm bùng nổ tổ hợp.

2.1 TSP — bài toán người bán hàng

Traveling Salesman Problem: một người xuất phát từ điểm gốc, thăm mọi điểm đúng một lần, quay về gốc, sao cho tổng quãng đường ngắn nhất. Nghe đơn giản nhưng là bài NP-hard kinh điển: với n điểm có (n-1)!/2 lộ trình khả dĩ — 20 điểm đã là hàng nghìn tỷ khả năng, không thể duyệt hết.

Thực tế giải bằng: MILP (mô hình với ràng buộc khử chu trình con — subtour elimination), heuristic (nearest neighbor, 2-opt, Lin-Kernighan), hoặc metaheuristic (simulated annealing, genetic). Solver chuyên như OR-Tools giải TSP vài trăm điểm trong vài giây với chất lượng gần tối ưu.

2.2 VRP — bài toán định tuyến đội xe

Vehicle Routing Problem là TSP mở rộng cho nhiều xe cùng xuất phát từ kho (depot), chia nhau phục vụ tập điểm, mỗi xe một lộ trình. Đây là bài toán vận hành cốt lõi cho đội tiếp quỹ ATM và giao nhận. Các biến thể quan trọng:

VRP là NP-hard và khó hơn TSP nhiều. OR-Tools Routing là công cụ mã nguồn mở mạnh nhất cho lớp này — nó có API chuyên biệt, hỗ trợ sẵn capacity, time windows, nhiều xe, và dùng metaheuristic (Guided Local Search) để tìm nghiệm tốt trong thời gian giới hạn.

Pseudocode minh hoạ (OR-Tools Routing, KHÔNG phải SQL chạy được):

# MINH HOẠ — VRP tiếp quỹ ATM với OR-Tools Routing
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# data: ma trận khoảng cách/thời gian giữa depot + các ATM,
#       nhu cầu tiền mỗi ATM, tải trọng mỗi xe, số xe
manager = pywrapcp.RoutingIndexManager(
    len(data["distance_matrix"]), data["num_vehicles"], data["depot"])
routing = pywrapcp.RoutingModel(manager)

# hàm chi phí cạnh = khoảng cách/thời gian
def dist_cb(i, j):
    return data["distance_matrix"][manager.IndexToNode(i)][manager.IndexToNode(j)]
transit = routing.RegisterTransitCallback(dist_cb)
routing.SetArcCostEvaluatorOfAllVehicles(transit)

# ràng buộc TẢI TRỌNG: tổng tiền tiếp mỗi xe ≤ sức chở
def demand_cb(i):
    return data["demands"][manager.IndexToNode(i)]
demand = routing.RegisterUnaryTransitCallback(demand_cb)
routing.AddDimensionWithVehicleCapacity(
    demand, 0, data["vehicle_capacities"], True, "Cash")

# chiến lược tìm nghiệm: dựng ban đầu + local search có hướng dẫn
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
params.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
params.time_limit.seconds = 30   # cắt theo cửa sổ thời gian

solution = routing.SolveWithParameters(params)
# đọc solution → lộ trình từng xe, tổng quãng đường

Điểm mấu chốt: với VRP thực tế bạn không tìm nghiệm tối ưu tuyệt đối mà đặt time_limit và lấy nghiệm tốt nhất tìm được — đủ tốt hơn hẳn xếp tuyến thủ công.

3. Lập lịch (scheduling)

Lập lịch phân bổ nguồn lực theo thời gian: máy móc, ca làm, nhân sự. Đây là mảnh đất của Constraint Programming (CP) hơn là LP thuần, vì ràng buộc rời rạc và logic (không trùng ca, đủ kỹ năng, tuân luật lao động) diễn đạt tự nhiên bằng ngôn ngữ ràng buộc.

3.1 Các dạng lập lịch

• Job scheduling / job-shop: xếp thứ tự và thời điểm chạy các công việc trên tập máy hạn chế, tối thiểu tổng thời gian hoàn thành (makespan) hoặc trễ hạn. Ví dụ: xếp lịch chạy batch job trong cửa sổ đêm.
• Staff rostering / xếp ca nhân sự: gán nhân viên vào ca sao cho đủ người mỗi ca, đúng kỹ năng, tôn trọng luật lao động (nghỉ giữa ca, số giờ tối đa/tuần, ngày nghỉ). Ví dụ: xếp ca giao dịch viên quầy, xếp ca tổng đài (call center) theo dự báo lưu lượng cuộc gọi.
• Resource scheduling: phân bổ chung nguồn lực khan hiếm (phòng, thiết bị, cán bộ chuyên môn) theo thời gian.

3.2 Constraint Programming & CP-SAT

CP (Constraint Programming) là mô hình hoá bài toán bằng biến rời rạc + các ràng buộc logic (all-different, no-overlap, cumulative...) rồi để solver tìm cấu hình thỏa mãn/tối ưu bằng propagation + tìm kiếm có backtracking. CP-SAT của OR-Tools là solver CP hiện đại (lai giữa CP và SAT/MILP), rất mạnh cho lập lịch và bài toán tổ hợp — thường vượt MILP thuần trên các bài scheduling.

Pseudocode minh hoạ (CP-SAT xếp ca — KHÔNG phải SQL chạy được):

# MINH HOẠ — xếp ca giao dịch viên với OR-Tools CP-SAT
from ortools.sat.python import cp_model
model = cp_model.CpModel()

# biến nhị phân: nhân viên e làm ca s ngày d
x = {(e, d, s): model.NewBoolVar(f"x_{e}_{d}_{s}")
     for e in employees for d in days for s in shifts}

# đủ người mỗi ca theo nhu cầu dự báo
for d in days:
    for s in shifts:
        model.Add(sum(x[e, d, s] for e in employees) >= demand[d, s])

# mỗi nhân viên tối đa 1 ca/ngày
for e in employees:
    for d in days:
        model.Add(sum(x[e, d, s] for s in shifts) <= 1)

# ràng buộc luật lao động: ≤ 5 ngày làm / tuần
for e in employees:
    model.Add(sum(x[e, d, s] for d in days for s in shifts) <= 5)

# ràng buộc kỹ năng: chỉ ai đủ skill mới xếp ca chuyên
for e in employees:
    for d in days:
        for s in skilled_shifts:
            if not has_skill[e, s]:
                model.Add(x[e, d, s] == 0)

# mục tiêu: tối thiểu tổng ca cuối tuần (công bằng) — minh hoạ
model.Minimize(sum(x[e, d, s] for e in employees
                   for d in weekend_days for s in shifts))

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60
solver.Solve(model)

4. Vì sao nhóm này khó — và chọn công cụ nào

Điểm chung khiến routing/scheduling khó là bản chất tổ hợp: số phương án khả dĩ tăng theo giai thừa/hàm mũ, không thể vét cạn. Bảng dưới tóm tắt lựa chọn công cụ:

Nguyên tắc: bài có cấu trúc mạng "thuần" (không ràng buộc rắc rối) → dùng thuật toán chuyên cực nhanh, đừng phí công dựng MILP. Bài định tuyến có tải/khung giờ → OR-Tools Routing. Bài lập lịch rời rạc → CP-SAT. Chỉ khi bài nhỏ hoặc cần diễn đạt linh hoạt mới quay lại MILP tổng quát. Với quy mô rất lớn, mọi công cụ đều dựa vào heuristic/metaheuristic đặt time_limit để lấy nghiệm "đủ tốt".

Ràng buộc thực tế phải luôn tính đến

Mô hình sách vở thường bỏ sót; thực chiến phải mã hoá cho được:

• VRP: tải trọng và số tiền tối đa mỗi xe (quy định an ninh), khung giờ mở cửa điểm, giờ làm tài xế + áp tải, ưu tiên ATM sắp hết tiền.
• Rostering: nghỉ tối thiểu giữa hai ca, số giờ tối đa/tuần theo luật, kỹ năng bắt buộc, nguyện vọng/công bằng ca cuối tuần, dự phòng nghỉ ốm.

Use case thực tế

Bài toán: tối ưu tuyến tiếp quỹ ATM cho khu vực Hà Nội.

NCB có 1 kho quỹ trung tâm (depot) và 40 điểm ATM cần tiếp quỹ trong ngày, 4 xe áp tải, mỗi xe chở tối đa 3 tỷ đồng và chạy tối đa 8 giờ. Mỗi ATM có nhu cầu tiền dự báo và khung giờ được phép tiếp (tránh giờ cao điểm giao dịch).

Quy trình 5 bước:

1. Chuẩn bị dữ liệu: từ hệ thống monitoring lấy số dư/tốc độ rút của từng ATM → dự báo nhu cầu tiền hôm nay. Từ transactions, tổng hợp khối lượng theo điểm để ước lượng mức độ khẩn (xem SQL bên dưới cho phần ước lượng nhu cầu theo điểm).
2. Dựng ma trận khoảng cách/thời gian giữa depot và 40 ATM (từ Google Maps API hoặc OSRM).
3. Mô hình CVRP + Time Windows bằng OR-Tools Routing: 4 xe, tải 3 tỷ, ràng buộc khung giờ, time_limit=30s.
4. Giải & đọc nghiệm: 4 lộ trình, tổng quãng đường ~180 km (so với ~260 km khi xếp tay), mỗi xe 9-11 điểm, đều dưới 8 giờ.
5. Đưa vào vận hành: xuất lộ trình cho từng xe kèm bản đồ, lượng tiền đóng gói theo điểm. Chạy lại hằng ngày với dữ liệu nhu cầu mới.

Kết quả: giảm ~30% quãng đường và số giờ xe, giảm chi phí nhiên liệu + áp tải, tránh ATM hết tiền nhờ ưu tiên theo mức khẩn.

Block SQL dưới đây (chạy được trên sandbox) minh hoạ bước 1 — ước lượng "khối lượng rút" theo từng nhóm điểm/thành phố để feed vào phân bổ nhu cầu tiền mặt. Ở đây ta dùng thành phố khách hàng làm proxy cho cụm địa lý:

-- ▶ Chạy được
WITH rut_30d AS (
  SELECT
    a.id AS account_id,
    c.city AS cum_diem,
    ABS(t.amount) AS so_tien
  FROM transactions t
  JOIN accounts a  ON a.id = t.account_id
  JOIN customers c ON c.id = a.customer_id
  WHERE t.kind = 'withdrawal'
    AND t.created_at >= NOW() - INTERVAL '30 days'
)
SELECT
  cum_diem,
  COUNT(*)                                   AS so_lan_rut,
  ROUND(SUM(so_tien)::numeric, 0)            AS tong_tien_rut,
  ROUND(AVG(so_tien)::numeric, 0)            AS binh_quan_moi_lan,
  ROUND((SUM(so_tien) / 30.0)::numeric, 0)   AS nhu_cau_tien_moi_ngay
FROM rut_30d
GROUP BY cum_diem
ORDER BY nhu_cau_tien_moi_ngay DESC;

Cột nhu_cau_tien_moi_ngay chính là cầu đầu vào cho bài transportation/VRP: mỗi cụm điểm cần tiếp bao nhiêu tiền mỗi ngày, dùng để phân bổ từ kho quỹ.

Sơ đồ mạng tiếp quỹ (transportation/VRP)

Mỗi xe xuất phát từ depot, đi theo một lộ trình con ghé vài ATM (tổng cầu ≤ tải), rồi quay về — đúng cấu trúc CVRP.

Ghi nhớ

• Bài toán mạng sống trên graph (nút + cạnh có trọng số): shortest path (Dijkstra), max-flow/min-cut (nút cổ chai), min-cost flow (khung tổng quát), transportation/transshipment (điều tiết cung→cầu), assignment (gán 1-1, Hungarian).
• Nhiều bài mạng "thuần" có thuật toán chuyên cực nhanh — đừng phí công dựng MILP tổng quát. Assignment dùng scipy linear_sum_assignment, luồng dùng networkx.
• Định tuyến: TSP (1 xe thăm mọi điểm) và VRP (đội xe, có tải/khung giờ) đều NP-hard; dùng OR-Tools Routing với time_limit + metaheuristic, lấy nghiệm "đủ tốt".
• Lập lịch (job/staff/resource) hợp với Constraint Programming; OR-Tools CP-SAT rất mạnh cho xếp ca, mã hoá được kỹ năng, luật lao động, no-overlap.
• Với quy mô lớn không tìm tối ưu tuyệt đối — đặt cửa sổ thời gian và lấy nghiệm tốt nhất, vẫn vượt xa xếp tay.
• Ràng buộc thực tế mới là phần khó: tải xe, khung giờ, kỹ năng, luật lao động, mức khẩn — bỏ sót là mô hình vô dụng.
• Ứng dụng NCB: tối ưu tiếp quỹ ATM (VRP), xếp ca giao dịch viên/tổng đài (CP-SAT), gán cán bộ thẩm định (assignment), điều tiết tiền mặt giữa kho (min-cost flow), định tuyến logistics chứng từ.
• Quy trình luôn bắt đầu bằng chuẩn bị dữ liệu bằng SQL (nhu cầu/khối lượng theo điểm) rồi mới feed vào solver — xem solver & thực hành.