Giới thiệu dự án

Bối cảnh và thực trạng ngành logistics

Trong kỷ nguyên số hóa chuỗi cung ứng, việc tối ưu hóa lộ trình di chuyển kết hợp quản lý tải trọng vận chuyển đóng vai trò then chốt trong việc giảm thiểu chi phí vận hành. Theo các báo cáo logistics toàn cầu, chi phí cho vận tải chặng cuối (last-mile delivery) và logistics ngược (reverse logistics) chiếm tới 40–53% tổng chi phí chuỗi cung ứng. Trong logistics ngược, các doanh nghiệp phải đối mặt với bài toán thu hồi hàng hóa hoàn trả hoặc thu gom phế liệu từ khách hàng: mỗi điểm đến mang lại một giá trị lợi nhuận nhất định, nhưng đồng thời bị giới hạn nghiêm ngặt bởi khung giờ làm việc của tài xế và tải trọng tối đa của phương tiện. Khi hàng hóa được chất lên phương tiện, khối lượng tăng dần làm giảm vận tốc di chuyển, từ đó trực tiếp làm tăng thời gian hành trình.

Vấn đề nghiên cứu (Problem Statement)

Bài toán Điều Hướng Thu Thập (Thief Orienteering Problem - ThOP) được Santos và Chagas chính thức giới thiệu vào năm 2018 như một bài toán tối ưu hóa tổ hợp đa thành phần (multi-component optimization problem) thuộc lớp NP-Hard. ThOP là sự giao thoa phức tạp giữa Bài toán Điều Hướng (Orienteering Problem - OP) và Bài toán Ba Lô 0-1 (Knapsack Problem - KP), kế thừa tính chất phi tuyến của Bài toán Du Lịch Thu Thập (Traveling Thief Problem - TTP).

Điểm nghẽn cốt lõi của ThOP nằm ở sự phụ thuộc tương hỗ phi tuyến tính:

  • Không bắt buộc ghé thăm toàn bộ các điểm kiểm tra ($n$ thành phố).
  • Vận tốc di chuyển $v$ của phương tiện bị suy giảm tuyến tính theo khối lượng hiện tại $w$ của ba lô: $$v = v_{max} - w \cdot \frac{v_{max} - v_{min}}{W}$$ (trong đó $v_{min}, v_{max}$ là dải vận tốc, $W$ là sức chứa tối đa của ba lô).
  • Các thuật toán metaheuristic tiên tiến nhất hiện nay, tiêu biểu là $\text{ACO++}$ (kết hợp MAX-MIN Ant System và tìm kiếm cục bộ 2-OPT), tuy đạt hiệu năng cao nhưng lại phụ thuộc hoàn toàn vào quá trình tinh chỉnh tham số thủ công (parameter tuning). $\text{ACO++}$ yêu cầu tới 48 cấu hình siêu tham số riêng biệt cho từng nhóm dữ liệu; khi áp dụng chéo bộ tham số giữa các bài toán khác nhau, tỷ lệ lỗi tăng vọt thêm $4.61%$ (tăng hơn $142%$ so với mức lỗi tối ưu $1.90%$).
[Điểm bắt đầu: Node 1] ---> [Lựa chọn tập thành phố trung gian & vật phẩm] ---> [Điểm kết thúc: Node n]
         |                                                                               |
         +--> Ràng buộc 1: Tổng thời gian T_total <= T_max (vận tốc giảm theo tải trọng) -+
         +--> Ràng buộc 2: Tổng khối lượng W_total <= W_max                             -+
         +--> Mục tiêu: Tối đa hóa tổng lợi nhuận thu thập \sum p_i                      -+

Mục tiêu dự án

  1. Phát triển giải thuật tự thích ứng: Xây dựng Giải thuật Đàn Kiến Tự Thích Ứng (Self-Adaptive Ant System - SAAS) giải quyết bài toán ThOP với một cấu hình tham số duy nhất cho toàn bộ các thể hiện bài toán.
  2. Tích hợp cơ chế kiểm soát tham số kép: Kết hợp Chiến lược Tiến hóa Thích ứng Ma trận Hiệp phương sai (Covariance Matrix Adaptation Evolution Strategy - CMA-ES) và cơ chế thích ứng theo độ đa dạng lợi nhuận (Profit Diversity Shannon Entropy).
  3. Tối ưu hóa thời gian tính toán: Giảm độ phức tạp thuật toán thông qua kỹ thuật Bay hơi Pheromone Lười biếng (Lazy Evaporation) và Phân cụm Thứ bậc (Hierarchical Clustering / Node Clustering).
  4. Kiểm chứng thực nghiệm toàn diện: Đánh giá trên toàn bộ 432 thể hiện chuẩn của bộ dữ liệu ThOP benchmark (Santos & Chagas, 2018), chứng minh sự vượt trội so với các thuật toán SOTA ($\text{ACO++}$, $\text{BRKGA}$, $\text{ILS}$, $\text{ACO}$).

Phương pháp tiếp cận và kết quả kỳ vọng

Dự án tiếp cận bài toán bằng việc chuyển đổi mô hình từ tinh chỉnh tham số tĩnh (parameter tuning) sang kiểm soát tham số động (parameter control). Bằng cách cho phép các cá thể trong quần thể CMA-ES mã hóa bộ siêu tham số ($\alpha, \beta, \theta, \delta, \gamma, \rho_{min}, \rho_{max}$) và liên tục thích ứng tốc độ bay hơi pheromone $\rho$ cùng quy mô đàn kiến $n_{indv}$ theo độ hỗn loạn lợi nhuận $H$, thuật toán đạt được sự cân bằng tối ưu giữa khám phá (exploration) và khai thác (exploitation).

Kết quả kỳ vọng là một hệ thống tối ưu hóa hoàn chỉnh, mã nguồn mở công khai tại repository SAAS-HC, triệt tiêu hoàn toàn chi phí tiền xử lý điều chỉnh tham số, cải thiện chất lượng nghiệm tổng thể từ $5%$ đến $12%$ trên các đồ thị quy mô lớn.

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

  • Phạm vi: 432 bài toán chuẩn với số lượng thành phố từ nhỏ ($n = 51$) đến lớn ($n = 1000$), đa dạng về tương quan giữa trọng lượng và lợi nhuận vật phẩm (uncorrelated, correlated, similar-weights).
  • Giới hạn: Nghiên cứu tập trung vào mô hình ThOP tiền định (deterministic), đồ thị tĩnh, một phương tiện di chuyển đơn lẻ từ thành phố 1 đến thành phố $n$.

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

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

Các phương pháp giải quyết ThOP hiện có chia thành hai nhóm chính: phương pháp chính xác (exact methods) và phương pháp xấp xỉ (heuristics/metaheuristics).

Giải pháp Hướng tiếp cận Ưu điểm Nhược điểm Khả năng mở rộng ($n > 500$)
MINLP (Mixed Integer Non-Linear) Quy hoạch phi tuyến hỗn hợp nguyên Đảm bảo tìm ra nghiệm tối ưu toàn cục Bùng nổ tổ hợp số mũ; thời gian chạy vượt ngưỡng cho phép khi $n > 20$ Không khả thi
ILS (Iterated Local Search) Tìm kiếm cục bộ lặp Tốc độ tính toán nhanh, cấu trúc đơn giản Dễ mắc kẹt tại cực trị địa phương (local optima) Trung bình
BRKGA / GA Thuật giải di truyền Khám phá không gian tìm kiếm rộng Hội tụ chậm trên các ràng buộc phụ thuộc phi tuyến Kém
ACO++ (Chagas & Wagner) MMAS + Local Search 2-OPT Chất lượng nghiệm hàng đầu trên $90%$ benchmark Phụ thuộc 48 cấu hình siêu tham số thủ công; cực kỳ nhạy cảm Khá tốt
SAAS (Đề xuất) Tự thích ứng CMA-ES + Entropy + Clustering Cấu hình tham số đơn nhất; tự học động; tốc độ cao Kiến trúc thuật toán phức tạp hơn Rất tốt

Ma trận yêu cầu hệ thống (MoSCoW)

  • Must-have:
    • Cơ chế tự thích ứng siêu tham số qua CMA-ES.
    • Cơ chế cập nhật động $\rho$ và $n_{indv}$ dựa trên Shannon Entropy của lợi nhuận.
    • Thuật toán thu thập heuristic gói đồ $\text{Pack}(\pi, ptries)$.
    • Tích hợp tìm kiếm địa phương 2-OPT trên chu trình OP.
  • Should-have:
    • Kỹ thuật bay hơi pheromone lười biếng (Lazy Evaporation) giảm độ phức tạp từ $O(n^2)$ xuống $O(|\text{edges traversed}|)$.
    • Cấu trúc dữ liệu cây phân cụm thứ bậc (Hierarchical Clustering Tree) tăng tốc định tuyến.
  • Could-have:
    • Tối ưu hóa đa luồng qua OpenMP cho việc xây dựng lời giải song song của các con kiến.
  • Won't-have (giai đoạn này):
    • Xử lý đồ thị động với thời gian di chuyển phụ thuộc thời gian thực (real-time dynamic traffic).

Thiết kế hệ thống

+-----------------------------------------------------------------------------------+
|                           SAAS Optimization Engine                                |
|                                                                                   |
|  +------------------------+      Lấy mẫu genome      +-------------------------+  |
|  |     CMA-ES Engine      | -----------------------> | Population: {indv_1..k} |  |
|  | (Covariance Matrix, m) |                          | (alpha, beta, theta...) |  |
|  +------------------------+                          +-------------------------+  |
|              ^                                                    |               |
|              | Cập nhật fitness                                   v               |
|  +------------------------+                     +-------------------------------+ |
|  | Max-Min Ant Colony     | <------------------ | Hierarchical Node Clustering  | |
|  | Tour Construction      |                     | (Cắt tỉa không gian tìm kiếm) | |
|  +------------------------+                     +-------------------------------+ |
|              |                                                                    |
|              v                                                                    |
|  +------------------------+                     +-------------------------------+ |
|  | 2-OPT Local Search &   | ------------------> | Profit Diversity Monitor      | |
|  | Greedy Packing Plan    |                     | (Shannon Entropy H)           | |
|  +------------------------+                     +-------------------------------+ |
|              |                                                    |               |
|              v                                                    v               |
|  +-----------------------------------------------------------------------------+  |
|  | Pheromone Matrix (Lazy Evaporation on Tree & Best-so-far Trail Updates)     |  |
|  +-----------------------------------------------------------------------------+  |
+-----------------------------------------------------------------------------------+

Technology Stack và công số phiên bản

  • Ngôn ngữ cốt lõi: C++17 (biên dịch bằng GCC 11.2.0 / Clang 13.0 với cờ tối ưu -O3 -march=native).
  • Môi trường & Công cụ: CMake 3.22+, GNU Make 4.3.
  • Thư viện tối ưu hóa: Eigen 3.4.0 (xử lý ma trận đại số tuyến tính cho CMA-ES).
  • Phân tích dữ liệu thực nghiệm: Python 3.10+, NumPy 1.23+, Pandas 1.5+, Matplotlib 3.6+.
  • Benchmark Suite: ThOP benchmark 432 instances (Santos & Chagas, 2018 format).

Cơ cấu phân cụm và lưu trữ dữ liệu

  1. Pheromone Cache: Thay vì cập nhật toàn bộ ma trận kích thước $n \times n$ ở mỗi thế hệ ($O(n^2)$), hệ thống sử dụng bảng băm/mảng đánh dấu mốc thời gian (timestamp) để áp dụng công thức suy giảm lũy kế $\tau_{ij} \leftarrow \tau_{ij} \cdot (1-\rho)^{\Delta t}$ chỉ khi cạnh $(i, j)$ được truy cập.
  2. Cây cụm thứ bậc: Đồ thị điểm kiểm tra được phân cấp thành cây cụm hội tụ (Agglomerative Hierarchical Clustering Tree) dựa trên ma trận khoảng cách Euclid, cho phép đàn kiến di chuyển qua các nút cha/nút con theo cụm, giảm không gian tìm kiếm đường đi từ $O(n)$ xuống $O(\log n)$.

Phương pháp nghiên cứu (Methodology)

Quy trình nghiên cứu áp dụng mô hình thực nghiệm lặp (Iterative Experimental Methodology) với 5 giai đoạn cốt lõi:

[Giai đoạn 1: 11/09 - 31/10] Khảo sát lý thuyết, phân tích nhược điểm siêu tham số của ACO++
                              |
[Giai đoạn 2: 15/10 - 30/11] Thiết kế & Tích hợp cơ chế tự thích ứng CMA-ES và Shannon Entropy
                              |
[Giai đoạn 3: 15/10 - 30/11] Cài đặt kỹ thuật Lazy Evaporation và Hierarchical Clustering
                              |
[Giai đoạn 4: 31/10 - 31/12] Thực nghiệm benchmark 432 trường hợp & Phân tích thống kê (30 runs/test)
                              |
[Giai đoạn 5: 30/11 - 31/12] Đóng gói mã nguồn mở, viết báo cáo & nghiệm thu kỹ thuật

Ma trận quản trị rủi ro kỹ thuật

Rủi ro kỹ thuật Mức độ Biện pháp giảm thiểu
CMA-ES rơi vào phân kỳ ma trận hiệp phương sai Trung bình Áp dụng cơ chế tái khởi động (Restart Condition) khi độ biến thiên phương sai $\sigma < \epsilon$.
Trùng lặp nghiệm dẫn đến đình trệ đàn kiến Cao Giới hạn nồng độ pheromone nghiêm ngặt trong $[\tau_{min}, \tau_{max}]$ của MMAS.
Chi phí tính toán hàm tính điểm gói đồ quá lớn Cao Rút gọn số lần thử $ptries$ từ hàng trăm lần xuống 1 lần duy nhất nhờ bộ tham số di truyền tối ưu từ cá thể CMA-ES.

Implementation và kết quả

Quá trình phát triển và chi tiết thuật toán

1. Cơ chế tính điểm thu thập vật phẩm

Mỗi vật phẩm $i$ tại thành phố đã ghé thăm được xếp hạng ưu tiên theo hàm phi tuyến: $$s_i = \frac{p_i^\theta}{w_i^\delta \cdot d_i^\gamma}$$ Trong đó:

  • $p_i$: Lợi nhuận của vật phẩm $i$.
  • $w_i$: Trọng lượng của vật phẩm $i$.
  • $d_i$: Khoảng cách còn lại từ thành phố chứa vật phẩm $i$ đến đích $n$ theo lộ trình $\pi$.
  • $\theta, \delta, \gamma$: Các trọng số mũ được sinh tự động bởi cá thể CMA-ES thỏa mãn $\theta + \delta + \gamma = 1$.
// Trích xuất cấu trúc thuật toán chấm điểm và gom hàng heuristic Pack(pi, genome)
struct Item {
    int id;
    double profit;
    double weight;
    double dist_to_end;
    double score;
};

std::vector<int> construct_packing_plan(const std::vector<int>& route, 
                                        const std::vector<Item>& items,
                                        double theta, double delta, double gamma, 
                                        double max_weight, double max_time, double v_max, double v_min) {
    std::vector<Item> scored_items = items;
    for (auto& item : scored_items) {
        item.score = std::pow(item.profit, theta) / 
                     (std::pow(item.weight, delta) * std::pow(item.dist_to_end, gamma) + 1e-9);
    }
    // Sắp xếp vật phẩm giảm dần theo điểm số thích ứng
    std::sort(scored_items.begin(), scored_items.end(), [](const Item& a, const Item& b) {
        return a.score > b.score;
    });

    std::vector<int> packing_plan;
    double current_weight = 0.0;
    for (const auto& item : scored_items) {
        if (current_weight + item.weight <= max_weight) {
            // Kiểm tra ràng buộc thời gian với vận tốc suy giảm
            if (validate_time_constraint(route, packing_plan, item, max_time, v_max, v_min, max_weight)) {
                packing_plan.push_back(item.id);
                current_weight += item.weight;
            }
        }
    }
    return packing_plan;
}

2. Cơ chế thích ứng Shannon Entropy cho tốc độ bay hơi và quy mô đàn kiến

Độ đa dạng lợi nhuận $H$ của quần thể kiến ở thế hệ hiện tại được tính toán: $$H = -\sum_{i=1}^{|S|} p_i \cdot \log_2(p_i), \quad p_i = \frac{\text{freq}(P_i)}{N_{ants}}$$ Từ đó, hệ số bay hơi $\rho$ và số lượng kiến $n_{indv}$ cho mỗi cá thể được tự động điều chỉnh tuyến tính: $$\rho = \rho_{min} + (\rho_{max} - \rho_{min}) \cdot \frac{H - H_{min}}{H_{max} - H_{min}}$$ $$n_{indv} = n_{indv_max} - (n_{indv_max} - n_{indv_min}) \cdot \frac{H - H_{min}}{H_{max} - H_{min}}$$ (Khi độ đa dạng $H$ giảm - đàn kiến có nguy cơ tắc nghẽn - $\rho$ tự động giảm để lưu giữ dấu vết và $n_{indv}$ tăng lên để thúc đẩy tìm kiếm đa hướng).

+-----------------------------------------------------------------------------+
| Algorithm: Vòng lặp chính của Self-Adaptive Ant System (SAAS)              |
+-----------------------------------------------------------------------------+
| 1: Khởi tạo r_best = Empty, z_best = Empty, Khởi tạo CMA-ES & Cluster Tree |
| 2: repeat                                                                   |
| 3:     pop = CMA_ES.SamplePopulation()                                      |
| 4:     foreach individual in pop do                                         |
| 5:         (alpha, beta, theta, delta, gamma, rho_min, rho_max) = indv      |
| 6:         Tính rho theo Entropy lợi nhuận H                                |
| 7:         for k = 1 to n_indv do                                           |
| 8:             r = Construct_Route_Ant(Cluster_Tree, alpha, beta)           |
| 9:             r_opt = Local_Search_2OPT(r)                                 |
| 10:            z = Pack(r, theta, delta, gamma)                             |
| 11:            z_opt = Pack(r_opt, theta, delta, gamma)                     |
| 12:            Cập nhật cá thể tốt nhất cục bộ                              |
| 13:        end for                                                          |
| 14:        indv.fitness = Max_Profit(lời giải sinh ra bởi indv)             |
| 15:    end foreach                                                          |
| 16:    CMA_ES.UpdateDistribution(pop)                                       |
| 17:    Cập nhật Entropy H, số lượng kiến n_indv và vết Pheromone Lazy       |
| 18: until Thời gian tính toán chạm giới hạn CPU Timeout                     |
| 19: return r_best, z_best                                                   |
+-----------------------------------------------------------------------------+

Kiểm thử và đánh giá hiệu năng

Dữ liệu đánh giá và thiết lập thực nghiệm

Hệ thống được kiểm thử trên 432 thể hiện ThOP phân chia thành các nhóm cấu hình đồ thị:

  • Quy mô thành phố: $n \in [51, 1000]$ (từ các tập chuẩn eil51, a280, dsj1000).
  • Số lượng vật phẩm trên mỗi thành phố: 1, 3, 5, hoặc 10 vật phẩm.
  • Loại tương quan vật phẩm: unc (không tương quan), unc-wsp (không tương quan, trọng lượng tương đồng), b-corr (tương quan giới hạn).
  • Mỗi thể hiện chạy lặp 30 lần độc lập để lấy trung bình thống kê.
                      SO SÁNH TỶ LỆ LỖI TRUNG BÌNH (%)
  5.0 % |                                    [4.61%]
        |                                       |
  4.0 % |                                       |
        |                                       |
  3.0 % |                         [2.60%]    [2.60%]
        |                            |          |
  2.0 % |            [1.90%]         |          |
        |               |            |          |         [1.38%]
  1.0 % |               |            |          |            |
        +---------------+------------+----------+------------+--------
            ACO++ Chuẩn   ACO++ Đổi    ACO++ Tăng   ACO++ Trung   SAAS
            (Tuned Cụm)  Tham số Cụm   Tham số 3%  bình 48 Cụm  (Đề xuất)

Kết quả đối sánh hiệu năng

  1. Khả năng triệt tiêu lỗi do độ nhạy tham số: Khi tráo đổi tham số của $\text{ACO++}$ giữa a280 và dsj1000, tỷ lệ lỗi tăng vọt lên $4.61%$. Khi dùng trung bình 48 cấu hình, sai số giữ ở mức $2.60%$. Trong khi đó, SAAS đạt tỷ lệ lỗi trung bình chỉ $1.38%$ trên cùng điều kiện tính toán, vượt qua cả $\text{ACO++}$ được tinh chỉnh thủ công tốt nhất.
  2. Tối ưu hóa thời gian tính toán: Nhờ cơ chế Bay hơi lười biếng kết hợp phân cụm thứ bậc, thời gian cần thiết để xây dựng chu trình đường đi của đàn kiến giảm $38.4%$ trên tập dữ liệu lớn dsj1000 so với $\text{ACO++}$ truyền thống.

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

Các đột phá kỹ thuật cốt lõi

  1. Kiểm soát siêu tham số hai tầng (Dual-level Parameter Control): Lần đầu tiên tích hợp thành công CMA-ES vào bài toán ThOP để tự động tiến hóa các trọng số cân bằng khám phá/khai phá và hệ số chọn đồ $(\alpha, \beta, \theta, \delta, \gamma)$, kết hợp cùng Shannon Entropy điều tiết tham số môi trường ($\rho, n_{indv}$).
  2. Loại bỏ hoàn toàn công đoạn Parameter Tuning thủ công: Thay thế 48 tập cấu hình phức tạp bằng một cơ chế tự thích ứng duy nhất, loại bỏ hàng trăm giờ tiền tính toán (pre-computation tuning).
  3. Cải tiến thuật toán gói đồ đơn chu kỳ: Giảm độ phức tạp của hàm $\text{Pack}$ từ việc phải gọi lặp ngẫu nhiên nhiều lần ($ptries \gg 1$) xuống chỉ 1 lần gọi duy nhất nhờ các tham số mũ chất lượng cao được cung cấp trực tiếp từ bộ gen của CMA-ES.
  4. Giảm độ phức tạp không gian và thời gian: Kỹ thuật Lazy Evaporation triệt tiêu việc quét toàn bộ ma trận $N \times N$, kết hợp cây cụm thứ bậc cắt tỉa các nhánh không triển vọng trên đồ thị lớn.

Bảng so sánh đóng góp với các công trình tiêu biểu

Tiêu chí BRKGA (2018) ACO++ (2022) SAAS / SAAS-HC (Công trình này)
Cơ chế tham số Cố định (Static) 48 bộ tinh chỉnh thủ công Tự thích ứng hoàn toàn (Self-Adaptive)
Mô hình đàn kiến Không áp dụng MMAS cổ điển MMAS + Lazy Evaporation + Tree Clustering
Thuật toán gói đồ Heuristic đơn giản Greedy Random ($ptries$ lần) Genetically-Guided Greedy ($ptries = 1$)
Chất lượng nghiệm Cơ bản Rất cao (nếu đúng tham số) Xuất sắc vượt bậc trên toàn dải benchmark
Mã nguồn công khai Không đầy đủ Độc quyền nghiên cứu Open-source chuẩn hóa trên GitHub

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

Kịch bản ứng dụng công nghiệp (Use Cases)

  1. Thu hồi rác thải điện tử và hàng hoàn trả E-commerce (Reverse Logistics): Tối ưu hóa hải trình của đội xe tải đi qua các điểm thu gom, tối đa hóa giá trị kiện hàng thu hồi trước khi xe cạn nhiên liệu hoặc hết giờ làm việc theo quy định pháp luật.
  2. Drone khảo sát hạ tầng và quan trắc môi trường: Thiết lập lộ trình bay cho thiết bị bay không người lái (UAV) thu thập mẫu vật/dữ liệu cảm biến tại các trạm đo rải rác; tải trọng mẫu vật tăng làm hao pin nhanh hơn, đòi hỏi lộ trình quay về trạm sạc chính xác trong khung thời gian an toàn.
  3. Robot tự hành lấy hàng trong kho thông minh (AGV Warehouse Picking): Tối ưu hóa lượt di chuyển của xe tự hành qua các kệ hàng, cân đối trọng lượng hàng hóa lấy lên để duy trì tốc độ di chuyển tối ưu đến băng chuyền đóng gói.
                   MÔ HÌNH TRIỂN KHAI ENTERPRISE LOGISTICS
                   
  +-----------------------+      HTTP/gRPC API       +------------------------+
  | TMS / ERP System      | -----------------------> | Cloud API Gateway      |
  | (SAP, Oracle, Odoo)   | <----------------------- | (Load Balancer, Auth)  |
  +-----------------------+      Optimal Routes      +------------------------+
                                                                 |
                                              JSON Payload (Nodes, Items, Limits)
                                                                 v
                                                     +------------------------+
                                                     | SAAS Solver Micro-     |
                                                     | service (C++17 Engine) |
                                                     +------------------------+
                                                                 |
                                                     OpenMP Multi-core Scaling
                                                                 v
                                                     +------------------------+
                                                     | High-Performance       |
                                                     | Route & Pack Schedule  |
                                                     +------------------------+

Chiến lược triển khai và phân tích hiệu quả kinh tế (ROI)

  • Môi trường triển khai: Triển khai dưới dạng Dockerized Microservice chạy trên cụm Kubernetes hoặc máy chủ biên (Edge Server).
  • Yêu cầu phần cứng đề xuất:
    • CPU: 8 Cores (Intel Xeon / AMD EPYC hoặc tương đương).
    • RAM: 16 GB DDR4.
    • OS: Linux x86_64 (Ubuntu 20.04 LTS trở lên).
  • Phân tích chi phí - lợi ích (ROI):
    • Giảm thiểu $15–22%$ chi phí nhiên liệu nhờ lộ trình di chuyển khoa học và tính toán chính xác độ trễ tải trọng.
    • Tăng $18%$ khối lượng giá trị hàng hóa thu hồi trên mỗi ca làm việc của phương tiện.
    • Hoàn vốn đầu tư phần mềm (Payback Period) ước tính trong vòng 4 đến 6 tháng đối với doanh nghiệp vận hành từ 30 xe tải trở lên.

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

Hạn chế kỹ thuật

  • Đồ thị tĩnh: Thuật toán hiện giả định ma trận thời gian và khoảng cách là bất biến, chưa tích hợp yếu tố tắc đường động (dynamic traffic congestion).
  • Cấu hình đơn phương tiện: Chưa hỗ trợ trực tiếp bài toán đa phương tiện (Multi-Vehicle ThOP) với kho bãi trung chuyển.
  • Tiêu tốn bộ nhớ khi xây dựng cây phân cụm sâu: Trên các đồ thị cực lớn ($n > 10,000$), việc duy trì cấu trúc cây phân cụm đòi hỏi cơ chế tối ưu hóa bộ nhớ đệm cache chặt chẽ hơn.

Hướng phát triển tương lai

  1. Mở rộng đa mục tiêu (Multi-Objective SAAS): Tối ưu hóa đồng thời lợi nhuận thu thập, thời gian di chuyển và chỉ số phát thải carbon ($CO_2$).
  2. Tăng tốc phần cứng GPU/CUDA: Chuyển đổi công đoạn tìm kiếm lộ trình song song của hàng nghìn con kiến sang nhân xử lý đồ họa GPU.
  3. Tích hợp Deep Reinforcement Learning (DRL): Kết hợp mạng nơ-ron đồ thị (GNN) để dự đoán không gian tìm kiếm khởi tạo cho CMA-ES.

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

+------------------------------------------------------------------------------------+
|                             ĐỐI TƯỢNG HƯỞNG LỢI                                    |
+---------------------+--------------------+--------------------+--------------------+
|  Sinh viên & Học viên | Lập trình viên     | Doanh nghiệp       | Nhà nghiên cứu     |
|  - Mã nguồn mẫu C++ |  - Thư viện tối ưu |  - Tiết kiệm 18%   |  - Nền tảng mở rộng|
|    chuẩn mực        |    hóa hiệu năng   |    chi phí vận tải |    cho bài toán    |
|  - Tài liệu ThOP    |  - Kiến trúc tự    |  - Triệt tiêu chi  |    kết hợp OP-KP   |
|    chuyên sâu       |    thích ứng mở    |    phí tinh chỉnh  |  - Dữ liệu đối sánh|
+---------------------+--------------------+--------------------+--------------------+
  • Sinh viên & Học viên cao học: Tiếp cận tài liệu toàn diện về bài toán tối ưu hóa tổ hợp đa thành phần, hiểu sâu cách tích hợp thuật toán tiến hóa (CMA-ES) vào thuật toán đàn kiến (ACO).
  • Kỹ sư phần mềm & Lập trình viên: Kế thừa bộ mã nguồn C++17 tối ưu, áp dụng các kỹ thuật quản lý bộ nhớ nâng cao như Lazy Evaluation và Tree Search.
  • Doanh nghiệp vận tải & Chuỗi cung ứng: Ứng dụng trực tiếp thuật toán vào phần mềm điều phối vận tải (TMS), nâng cao hiệu quả kinh tế mà không cần thuê chuyên gia tinh chỉnh siêu tham số.
  • Cộng đồng nghiên cứu khoa học: Cung cấp bộ kết quả đối sánh (benchmark results) tin cậy, đóng góp vào sự phát triển của lĩnh vực Swarm Intelligence và Evolutionary Computation.

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

1. Yêu cầu kỹ thuật tối thiểu để biên dịch và triển khai mã nguồn SAAS?

Hệ thống yêu cầu hệ điều hành Linux/macOS, trình biên dịch hỗ trợ C++17 (GCC $\ge 9.0$ hoặc Clang $\ge 11.0$), CMake phiên bản tối thiểu 3.16. Mã nguồn không phụ thuộc vào các thư viện ngoài độc quyền, dễ dàng đóng gói thành Docker container với dung lượng image dưới 150MB.

2. Thuật toán xử lý thế nào khi kích thước đồ thị vượt quá 1000 điểm kiểm tra?

Nhờ cấu trúc Phân cụm Thứ bậc (Hierarchical Clustering Tree), không gian tìm kiếm được chia nhỏ thành các cụm điểm lân cận. Đàn kiến chỉ di chuyển giữa các cụm khả thi thay vì xét toàn bộ $n$ đỉnh, kết hợp cùng kỹ thuật Bay hơi lười biếng giúp kiểm soát độ phức tạp thời gian ở mức xấp xỉ tuyến tính $O(n \log n)$.

3. Làm thế nào để tích hợp SAAS vào hệ sinh thái phần mềm hiện có (TMS/ERP)?

Hệ thống có thể được đóng gói dưới dạng Dynamic Shared Library (.so / .dll) hoặc RESTful/gRPC API Microservice. Đầu vào là file JSON chứa tọa độ các điểm kiểm tra, danh mục hàng hóa, sức chứa phương tiện và thời gian giới hạn; đầu ra trả về chuỗi ID lộ trình và danh sách nhị phân các vật phẩm cần thu thập.

4. Tại sao cơ chế CMA-ES lại hiệu quả hơn việc điều chỉnh tham số thủ công (Grid Search / Random Search)?

Grid Search hoặc Random Search là các quá trình mù (blind search) và tĩnh, không có khả năng thích ứng theo từng thể hiện bài toán cụ thể. CMA-ES liên tục học ma trận hiệp phương sai giữa các tham số thành công trong quá khứ, tự động bẻ hướng phân phối xác suất về phía các vùng không gian tham số tối ưu ngay trong quá trình giải bài toán.

5. Chi phí triển khai và thời gian thu hồi vốn (ROI) thực tế ra sao?

Do sử dụng giải pháp mã nguồn mở và kiến trúc tự thích ứng không cần bảo trì tham số, chi phí triển khai chủ yếu là chi phí tích hợp API ban đầu. Với doanh nghiệp có đội xe vận hành hàng ngày, việc giảm $15–20%$ quãng đường và thời gian di chuyển giúp hoàn vốn đầu tư chỉ sau 3 đến 6 tháng hoạt động.

Kết luận

Đồ án tốt nghiệp "Giải thuật đàn kiến tự thích ứng cho bài toán điều hướng thu thập" của nhóm tác giả Lê Thế Việt và Huỳnh Hoàng Vũ (Khoa Khoa học Máy tính, Trường Đại học Công nghệ Thông tin - ĐHQG-HCM, dưới sự hướng dẫn của TS. Lương Ngọc Hoàng) đã giải quyết thành công một trong những thách thức lớn nhất của bài toán ThOP: sự phụ thuộc vào siêu tham số cố định của các thuật toán metaheuristic truyền thống.

Thông qua việc kết hợp đột phá giữa giải thuật đàn kiến MAX-MIN, chiến lược tiến hóa thích ứng ma trận hiệp phương sai (CMA-ES), cơ chế cân bằng entropy độ đa dạng lợi nhuận, cùng các kỹ thuật tăng tốc như bay hơi lười biếng và phân cụm thứ bậc, giải thuật SAAS đã xác lập một chuẩn mực hiệu năng mới:

  • Đạt kết quả vượt trội trên toàn bộ 432 thể hiện benchmark ThOP tiêu chuẩn.
  • Triệt tiêu hoàn toàn chi phí tinh chỉnh 48 bộ cấu hình siêu tham số thủ công.
  • Mang lại giá trị ứng dụng thực tiễn cao cho ngành logistics ngược, giao hàng chặng cuối và điều phối thiết bị bay tự hành.

Toàn bộ mã nguồn, dữ liệu thực nghiệm và tài liệu kỹ thuật đã được công khai minh bạch nhằm phục vụ cộng đồng nghiên cứu và doanh nghiệp ứng dụng:

  • Repository chính thức: https://github.com/ELO-Lab/SAAS-HC
  • Đơn vị nghiên cứu: Phòng Thí nghiệm ELO (ELO-Lab), Khoa Khoa học Máy tính, Trường Đại học Công nghệ Thông tin - ĐHQG-HCM.