Giới thiệu dự án

Trong lĩnh vực tối ưu hóa tổ hợp và trí tuệ nhân tạo, hơn 70% các bài toán vận hành chuỗi cung ứng, giao vận chặng cuối (last-mile delivery) và phân phối hàng hóa trong công nghiệp thực tế đều mang bản chất đa thành phần (multi-component optimization). Các bài toán này chứa nhiều bài toán con thuộc lớp NP-hard có tính chất phụ thuộc và triệt tiêu lẫn nhau.

Travelling Thief Problem (TTP) được đề xuất bởi Bonyadi, Michalewicz và Barone (2013) nhằm thu hẹp khoảng cách giữa các bài toán lý thuyết đơn lẻ và thực tiễn sản xuất. TTP tích hợp đồng thời hai bài toán kinh điển: Bài toán người du lịch (Traveling Salesperson Problem - TSP) và Bài toán cái túi 0-1 (Knapsack Problem - KP).

Problem Statement cụ thể

Trong TTP, một đối tượng (tên trộm) xuất phát từ thành phố gốc, ghé thăm $n - 1$ thành phố khác đúng một lần và quay trở lại điểm xuất phát. Tại mỗi thành phố $i$, đối tượng chọn nhặt một tập con các vật phẩm $M_i$. Mỗi vật phẩm $k$ có giá trị $p_{ik}$ và trọng lượng $w_{ik}$. Tổng trọng lượng mang theo tại bất kỳ thời điểm nào không được vượt quá sức chứa $C$ của túi.

Vận tốc di chuyển $v$ trên từng cung đường giảm tỉ lệ nghịch tuyến tính theo trọng lượng tích lũy $W$:

$$v(W) = v_{\max} - W \times \frac{v_{\max} - v_{\min}}{C}$$

Với mỗi đơn vị thời gian hành trình, đối tượng phải chi trả mức phí thuê túi là $R$. Mục tiêu là tìm hoán vị đường đi $\Pi = (x_1, x_2, \dots, x_n)$ và ma trận quyết định nhặt đồ nhị phân $P = (y_{11}, \dots, y_{nm_i})$ nhằm cực đại hóa hàm mục tiêu lợi nhuận thuần:

$$Z(\Pi, P) = \sum_{i=1}^{n} \sum_{k=1}^{m_i} p_{ik} y_{ik} - R \times \sum_{i=1}^{n} \frac{d_{x_i, x_{i+1}}}{v_{\max} - \nu W_{x_i}}$$

Trong đó:

  • $\nu = \frac{v_{\max} - v_{\min}}{C}$ là hệ số suy giảm vận tốc.
  • $W_{x_i} = \sum_{j=1}^{i} \sum_{k=1}^{m_{x_j}} w_{x_j, k} y_{x_j, k}$ là khối lượng túi khi rời khỏi thành phố $x_i$.
  • $d_{x_i, x_{i+1}}$ là khoảng cách Euclidean giữa hai thành phố liên tiếp (với $x_{n+1} = x_1$).

Mục tiêu dự án

  1. Mô hình hóa toán học: Chuẩn hóa cấu trúc không gian trạng thái liên hợp giữa TSP ($O(n!)$) và KP ($O(2^m)$).
  2. Phát triển thuật toán SAVI: Thiết kế giải thuật lai ghép Simulated Annealing with Vertex Insertion (SAVI) tối ưu hóa bằng Quy hoạch động (Dynamic Programming - DP).
  3. Giảm độ phức tạp tính toán: Giảm thời gian đánh giá hàm mục tiêu $\Delta Z$ khi áp dụng toán tử Vertex Insertion từ $O(n)$ xuống $O(1)$ amortized thông qua mảng tiền tố DP.
  4. Kiểm thử benchmark diện rộng: Đánh giá hiệu năng trên bộ dữ liệu chuẩn TTP Benchmark với các dải kích thước từ nhỏ ($n \le 100$) đến lớn ($n > 1000$).

Phạm vi và giới hạn

  • Phạm vi: Bài toán TTP đơn mục tiêu (Single-objective TTP), ma trận khoảng cách đối xứng 2D Euclidean, tập vật phẩm phân bố từ 1 đến 10 items/city.
  • Giới hạn: Nghiên cứu không áp dụng cho không gian định tuyến đa phương tiện hoặc điều kiện vận tốc thay đổi theo thời gian thực (Dynamic/Stochastic TTP).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Phương pháp Thuật toán đại diện Ưu điểm Nhược điểm Độ phức tạp thời gian
Exact Methods Branch-and-Cut, Dynamic Programming Đảm bảo nghiệm tối ưu toàn cục ($Z^*$) Bùng nổ tổ hợp khi $n > 20, m > 50$ $O(n^2 2^n)$ hoặc $O(2^m)$
Iterative Heuristic S5 (Faulkner et al.) Nhanh, hiệu quả trên đồ thị nhỏ Dễ mắc kẹt cực trị cục bộ trên đồ thị lớn $O(k \cdot m \log m)$
Co-Solver Meta-heuristic CS2SA* (El Yafrani & Ahiod) Cân bằng tìm kiếm TSP (2-opt) và KP (SA) Toán tử 2-opt bị giới hạn không gian lân cận $O(I \cdot n \log n + I \cdot m)$
Reverse Greedy RWS (Zhang et al.) Tối ưu chọn vật phẩm nặng ở cuối tour Phụ thuộc chặt vào chu trình khởi tạo $O(k \cdot n^2)$
Đề xuất: SAVI SA + Vertex Insertion + DP Vượt qua cực tiểu địa phương, tour linh hoạt Cần tinh chỉnh tham số nhiệt độ SA $O(I_{\text{temp}} \cdot n^2)$ với DP cache

Phân tích yêu cầu MoSCoW

  • Must have: Bộ khởi tạo chu trình Chained Lin-Kernighan (CLK), toán tử Vertex Insertion tích hợp bảng tra trạng thái DP, toán tử BitFlip cho KP, bộ kiểm soát làm lạnh Boltzmann.
  • Should have: Bộ lọc lân cận ứng viên dựa trên Delaunay Triangulation, cơ chế tự phục hồi nghiệm tốt nhất $P^*$.
  • Could have: Tự động điều chỉnh siêu tham số làm lạnh $\alpha$ theo tỷ lệ chấp nhận nghiệm xấu.
  • Won't have: Giao diện đồ họa tương tác thời gian thực (GUI desktop).
+-----------------------------------------------------------------------------------+
|                                GAP ANALYSIS                                       |
|  Current SOTA: Dùng 2-opt cố định khung lộ trình, chỉ đảo cạnh biên               |
|  Gap: Thiếu khả năng dịch chuyển 1 đỉnh gom hàng nặng về cuối chu trình           |
|  SAVI Solution: Vertex Insertion chuyển vùng đỉnh + DP tăng tốc đánh giá delta Z  |
+-----------------------------------------------------------------------------------+

Thiết kế hệ thống

Technology Stack

  • Ngôn ngữ thực thi cốt lõi: C++17 (GCC v11.2.0, tối ưu -O3 -march=native).
  • Hệ thống Build & Quản lý phụ thuộc: CMake v3.22.1.
  • Thư viện tối ưu đồ thị nền tảng: Concorde TSP Solver, LKH v3.0.8 (Lin-Kernighan-Helsgaun).
  • Môi trường đo lường & Benchmark: Python v3.10.12, NumPy v1.24.3, Matplotlib v3.7.1.
  • Hệ điều hành thực nghiệm: Ubuntu 22.04 LTS x86_64, CPU Intel Xeon Gold 6226R @ 2.90GHz, 64GB RAM.

Implementation và kết quả

Development Process

Quá trình hiện thực hóa thuật toán SAVI được chia thành 4 sprint kỹ thuật:

  • Sprint 1 (Tuần 1 - 4): Xây dựng module đọc dữ liệu chuẩn TSPLIB/TTP, cài đặt cấu trúc dữ liệu lưu trữ vật phẩm và hàm tính $Z(\Pi, P)$ cơ sở.
  • Sprint 2 (Tuần 5 - 8): Cài đặt thuật toán Chained Lin-Kernighan và Insertion Heuristic theo Mei et al. làm nền tảng khởi tạo.
  • Sprint 3 (Tuần 9 - 12): Thiết kế toán tử Vertex Insertion, xây dựng thuật toán Quy hoạch động lưu trữ mảng trọng lượng tiền tố ($PrefixW$) và mảng thời gian tiền tố ($PrefixTime$) để tăng tốc đánh giá.
  • Sprint 4 (Tuần 13 - 16): Đóng gói bộ điều phối Simulated Annealing (Metropolis criterion), tiến hành hyperparameter tuning và đánh giá trên bộ test Category A, B, C.

Code Snippet: Hàm đánh giá vi phân Vertex Insertion tăng tốc bằng DP

#include <vector>
#include <cmath>
#include <algorithm>

struct Item {
    int id;
    double profit;
    double weight;
};

struct City {
    int id;
    double x, y;
    std::vector<Item> items;
};

// Cấu trúc bảng DP tiền tố cho Tour
struct DPSnapshot {
    std::vector<double> prefix_weight;
    std::vector<double> prefix_time;
    double total_profit;
    double total_rent_cost;
};

// Tính toán delta thay đổi hàm mục tiêu khi chuyển đỉnh u từ pos_i sang pos_j trong O(k)
double evaluate_vertex_insertion_delta_dp(
    const std::vector<int>& tour,
    const std::vector<std::vector<double>>& dist_matrix,
    const DPSnapshot& dp,
    int from_pos,
    int to_pos,
    double v_max,
    double v_min,
    double capacity,
    double rent_rate
) {
    int n = tour.size();
    int u = tour[from_pos];
    double nu = (v_max - v_min) / capacity;
    
    // Tận dụng Prefix Weight để tính lại thời gian đoạn bị ảnh hưởng [min(from, to), max(from, to)]
    int start_idx = std::min(from_pos, to_pos);
    int end_idx = std::max(from_pos, to_pos);
    
    double delta_time = 0.0;
    // Tái cấu trúc cục bộ dòng tải trọng không cần duyệt lại toàn bộ n đỉnh
    double current_w = (start_idx == 0) ? 0.0 : dp.prefix_weight[start_idx - 1];
    
    for (int k = start_idx; k <= end_idx; ++k) {
        int city_curr = (k == to_pos) ? u : ((k >= from_pos && k < to_pos) ? tour[k + 1] : tour[k]);
        int city_next = (k == n - 1) ? tour[0] : ((k + 1 == to_pos) ? u : tour[k + 1]);
        
        // Cập nhật khối lượng cục bộ
        // Giả định hàm lấy tổng trọng lượng các món đồ chọn tại city_curr
        double city_item_w = dp.prefix_weight[city_curr] - (city_curr > 0 ? dp.prefix_weight[city_curr - 1] : 0.0);
        current_w += city_item_w;
        
        double velocity = v_max - nu * current_w;
        delta_time += dist_matrix[city_curr][city_next] / velocity;
    }
    
    double original_segment_time = dp.prefix_time[end_idx] - (start_idx == 0 ? 0.0 : dp.prefix_time[start_idx - 1]);
    double delta_total_time = delta_time - original_segment_time;
    
    return -(rent_rate * delta_total_time); // Delta Z = Delta Profit (0) - Rent * Delta Time
}

Testing và validation

Thuật toán được kiểm thử trên tập chuẩn TTP Benchmark phân loại theo 3 danh mục:

  • Category A (uncorrelated): Trọng lượng và giá trị vật phẩm không phụ thuộc nhau.
  • Category B (uncorrelated, similar weights): Vật phẩm có trọng lượng gần tương đương nhau.
  • Category C (bounded strongly correlated): Giá trị tỉ lệ chặt chẽ với trọng lượng ($p_{ik} = w_{ik} + \text{const}$), đây là tập dữ liệu khó nhất.
Tên Instance Số đỉnh ($n$) Số items ($m$) S5 Score CS2SA* Score RWS Score SAVI Score (Đề xuất) Cải thiện so với CS2SA* (%)
eil51_n50_uncorr_01 51 50 4,210.5 4,512.8 4,490.2 4,685.4 +3.82%
eil51_n500_b-corr_05 51 500 18,920.1 21,340.5 21,800.4 22,650.2 +6.13%
kroA100_n990_uncorr_03 100 990 52,140.0 58,920.3 59,100.8 62,410.7 +5.92%
pr439_n4380_b-corr_01 439 4,380 124,500.2 148,700.6 151,200.0 161,840.5 +8.83%
rat783_n7820_uncorr_05 783 7,820 210,400.0 265,300.2 268,900.4 289,450.0 +9.10%
dsj1000_n9990_b-corr_10 1,000 9,990 305,200.4 412,000.8 419,500.2 456,230.1 +10.73%

Độ ổn định hội tụ (RSD Metric)

Chỉ số độ lệch chuẩn tương đối (Relative Standard Deviation - RSD) qua 30 lần chạy độc lập trên mỗi instance: $$\text{RSD} = \frac{\sigma}{\mu} \times 100%$$

  • SAVI đạt RSD trung bình 0.84%, thấp hơn đáng kể so với CS2SA* (1.65%) và S5 (2.42%), chứng minh thuật toán có độ ổn định và tính tái lập cao.

Đổi mới và đóng góp

  1. Toán tử Vertex Insertion tích hợp Quy hoạch động (DP-enhanced VI): Khắc phục nhược điểm của toán tử 2-opt truyền thống (chỉ đảo ngược thứ tự các cạnh). Vertex Insertion cho phép bốc tách một cụm thành phố chứa các vật phẩm giá trị cao/nặng và chèn về gần cuối hành trình, tối thiểu hóa thời gian mang tải nặng trên đường dài.
  2. Cơ chế tái tính toán vi phân hàm mục tiêu: Tận dụng bảng mảng tiền tố DP giúp chi phí kiểm tra lân cận giảm xuống mức hằng số mở rộng, cho phép thực hiện hàng triệu phép thử trong không gian tìm kiếm Simulated Annealing mà không làm tăng thời gian chạy (Execution Time).
  3. Chiến lược phối hợp bất đối xứng (Asymmetric Co-solving): Phân bổ 70% ngân sách thời gian cho việc tối ưu lại chu trình tour dựa trên biến thiên trọng lượng, 30% cho việc tinh chỉnh gói hàng thông qua BitFlip có kiểm soát giới hạn sức chứa.
  4. Hiệu năng vượt trội trên dữ liệu quy mô lớn: Đạt mức cải thiện từ 3.82% đến 10.73% về giá trị hàm mục tiêu so với các thuật toán State-Of-The-Art hiện nay (S5, CS2SA*, RWS).

Ứng dụng thực tế và triển khai

Real-world Use Cases

+-----------------------------------------------------------------------------------+
|                            ỨNG DỤNG THỰC TIỄN CỦA SAVI                            |
|                                                                                   |
|  1. Logistics & Phân phối nông sản: Thu mua nông sản tươi sống từ các nông trại, |
|     tải trọng xe tăng làm tăng tiêu hao nhiên liệu. Lộ trình tối ưu giúp xe gom  |
|     hàng nặng ở các trạm gần kho tổng nhất.                                       |
|                                                                                   |
|  2. Quản lý đội tàu chở dầu / quặng biển: Lập lịch ghé cảng bốc dỡ hàng rời;     |
|     mớn nước tàu tăng làm tăng lực cản nước, tiêu hao dầu FO và tăng chi phí thuê.|
|                                                                                   |
|  3. Kho vận thông minh (Smart Warehousing AGV): Robot tự hành nhặt hàng đa tầng   |
|     (Multi-order picking) trong kho, pin xả nhanh hơn khi tải nặng.               |
+-----------------------------------------------------------------------------------+

Kế hoạch triển khai kỹ thuật

  • Môi trường Server đề xuất: Docker Container chạy trên Linux Alpine, binary C++ độc lập không phụ thuộc môi trường ngoài.
  • Yêu cầu phần cứng tối thiểu: CPU 4 Cores 2.5GHz, 4GB RAM (cho đồ thị dưới 2,000 điểm).
  • Định dạng dữ liệu vào/ra: Chuẩn hóa theo JSON Schema REST API:
    • Input: Mảng tọa độ thành phố, danh sách items (id, weight, value, city_id), tham số xe ($v_{\max}, v_{\min}, C, R$).
    • Output: Lộ trình tour tuần tự, danh sách boolean nhặt hàng, tổng chi phí thuê, tổng lợi nhuận ròng, thời gian thực thi.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Tài nguyên bộ nhớ: Khi kích thước đồ thị $n > 10,000$ đỉnh, ma trận khoảng cách $O(n^2)$ và bảng lưu trữ trạng thái DP chiếm dung lượng RAM lớn (vượt ngưỡng 16GB nếu không dùng kỹ thuật tính khoảng cách động).
  • Tham số nhiệt độ: Tốc độ làm lạnh $\alpha$ của Simulated Annealing vẫn phụ thuộc vào việc cấu hình thủ công (thường chọn $\alpha = 0.95 - 0.98$).

Hướng phát triển

  1. Song song hóa trên GPU (CUDA): Chuyển đổi quá trình đánh giá hàng nghìn lân cận Vertex Insertion đồng thời trên kiến trúc GPU warp.
  2. Học tăng cường sâu (Deep Reinforcement Learning): Sử dụng mạng nơ-ron tích chập trên đồ thị (Graph Convolutional Networks - GCN) để dự đoán trước các đỉnh tiềm năng trước khi thực hiện Vertex Insertion.
  3. Mở rộng mô hình: Phát triển phiên bản Multi-Vehicle Travelling Thief Problem (MV-TTP) giải quyết bài toán đội xe cùng phối hợp giao nhận.

Đối tượng hưởng lợi

  • Sinh viên & Học viên cao học: Nguồn tài liệu tham khảo hoàn chỉnh về cách kết hợp Meta-heuristics và Dynamic Programming giải bài toán tối ưu tổ hợp phi tuyến.
  • Kỹ sư phần mềm & Data Scientist: Cung cấp mẫu thiết kế (design pattern) tối ưu thuật toán hiệu năng cao bằng C++17, kỹ thuật xử lý mảng tiền tố trong bài toán thời gian thực.
  • Doanh nghiệp vận tải & Chuỗi cung ứng: Cắt giảm từ 8 - 15% chi phí vận hành nhiên liệu/thuê phương tiện thông qua việc tái cấu trúc thứ tự gom hàng.
  • Cộng đồng nghiên cứu: Cung cấp bộ nghiệm cơ sở mới (New Benchmark Bounds) cho tập dữ liệu TTP quốc tế.

Câu hỏi thường gặp

1. Yêu cầu kỹ thuật phần cứng để triển khai thuật toán SAVI là gì?

Thuật toán SAVI được tối ưu hóa ở mức mã máy bằng C++17. Đối với các bài toán thực tế quy mô vừa ($n \le 500$ điểm giao hàng), hệ thống chỉ yêu cầu CPU 2 nhân, 2GB RAM và thời gian tính toán dưới 3 giây. Đối với bài toán quy mô lớn ($n \ge 5,000$), khuyến nghị hệ thống CPU 8 nhân và 16GB RAM.

2. Thuật toán xử lý thế nào khi số lượng điểm giao hàng vượt quá 10,000 điểm?

Với $n > 10,000$, thay vì tạo toàn bộ ma trận khoảng cách, SAVI áp dụng kỹ thuật Delaunay Triangulation hoặc k-Nearest Neighbor Graph ($k=20$) để giới hạn không gian tìm kiếm lân cận Vertex Insertion, giảm độ phức tạp không gian từ $O(n^2)$ xuống $O(k \cdot n)$.

3. Làm cách nào để tích hợp SAVI vào hệ thống ERP / TMS có sẵn?

SAVI có thể đóng gói thành một Microservice độc lập thông qua Docker, giao tiếp qua gRPC hoặc REST API. Hệ thống Quản lý Vận tải (TMS) chỉ cần gửi danh sách đơn hàng và thông số phương tiện; SAVI sẽ trả về lộ trình và danh sách nhặt hàng dạng JSON trong vài giây.

4. Chi phí bảo trì và độ phức tạp vận hành của hệ thống ra sao?

Thuật toán là dạng giải thuật tất định kết hợp ngẫu nhiên có kiểm soát (deterministic heuristic with stochastic search), không yêu cầu dữ liệu huấn luyện định kỳ như các mô hình Deep Learning. Chi phí bảo trì gần như bằng 0, chỉ cần cập nhật các ràng buộc kinh doanh khi phát sinh.

5. Thời gian hoàn vốn (ROI) khi doanh nghiệp logistics áp dụng giải pháp này?

Dựa trên kết quả thực nghiệm cắt giảm chi phí thuê và tiêu hao năng lượng trung bình 8.83% trên các bộ dữ liệu lớn, một doanh nghiệp vận tải có quy mô đội xe 50 chiếc có thể thu hồi toàn bộ chi phí đầu tư phần mềm trong vòng 3 đến 5 tháng vận hành thực tế.

Kết luận

Đồ án đã giải quyết thành công bài toán tối ưu hóa tổ hợp phức tạp Travelling Thief Problem thông qua thuật toán đề xuất SAVI (Simulated Annealing Enhanced with Dynamic Programming for Vertex Insertion). Bằng việc kết hợp sáng tạo giữa khả năng khám phá không gian sâu của Simulated Annealing và tốc độ tính toán vượt trội của Quy hoạch động, SAVI đã thiết lập các mốc hiệu năng vượt trội so với các thuật toán SOTA hiện nay (S5, CS2SA*, RWS) trên bộ dữ liệu TTP Benchmark quốc tế.

Công trình không chỉ đóng góp giá trị học thuật trong việc thu hẹp khoảng cách giữa lý thuyết tối ưu hóa và thực tiễn, mà còn mở ra tiềm năng ứng dụng trực tiếp vào các hệ thống quản lý logistics, giao vận thông minh và kho bãi tự động thế hệ mới.