Tổng quan về luận án

Bài toán cực tiểu hóa độ trễ (Minimum Latency Problem - MLP), hay còn được biết đến dưới các tên gọi kinh điển trong lý thuyết tối ưu hóa tổ hợp như bài toán thợ sửa chữa lưu động (Traveling Repairman Problem - TRP) và bài toán người giao hàng (Delivery Man Problem - DMP), là một bài toán NP-khó có ý nghĩa nền tảng và giá trị ứng dụng thực tiễn to lớn trong thiết kế mạng viễn thông, lập lịch hệ thống máy chủ, định tuyến logistics thương mại điện tử và điều phối cứu hộ khẩn cấp. Trọng tâm cốt lõi của nghiên cứu phát biểu: "Bài toán cực tiểu hóa độ trễ MLP yêu cầu tìm một hành trình $T$ bắt đầu từ đỉnh xuất phát $s$ đi qua tất cả các đỉnh còn lại của đồ thị với tổng độ trễ là nhỏ nhất." Không giống như bài toán người du lịch (Traveling Salesman Problem - TSP) vốn tập trung tối thiểu hóa tổng chiều dài hành trình khép kín, hàm mục tiêu của MLP mang tính chất tích lũy thời gian chờ đợi tại từng nút mạng:

$$L(T) = \sum_{k=2}^{n} \text{lat}(v_k) = \sum_{k=1}^{n-1} (n - k) c(v_k, v_{k+1})$$

Trong bối cảnh khoa học hiện đại, bài toán MLP được xếp vào nhóm bài toán tối ưu phi cục bộ vô cùng phức tạp. Blum et al. (1994) đã chỉ ra rằng: "Với một sự thay đổi nhỏ trong hàm mục tiêu và đồ thị đầu vào thì bài toán MLP không có đặc tính cục bộ giống như bài toán TSP... việc hoán đổi như vậy lại có thể dẫn đến sự thay đổi lớn trong hàm mục tiêu của bài toán MLP." Chính vì một biến đổi nhỏ trên cấu trúc đồ thị có thể làm thay đổi hoàn toàn hành trình tối ưu toàn cục, các kỹ thuật chia để trị (divide-and-conquer) truyền thống gần như bất khả thi.

Khoảng trống nghiên cứu (research gap) trước thời điểm luận án được công bố bao gồm:

  1. Các thuật toán đúng chính xác chỉ giải quyết được các đồ thị có quy mô rất nhỏ ($n \le 26$ đỉnh theo nghiên cứu của Wu et al., 2000, 2004), khiến việc tìm kiếm nghiệm tối ưu chuẩn để kiểm chứng gặp bế tắc.
  2. Các thuật toán gần đúng cận tỷ lệ đa phần chỉ dừng lại ở đánh giá chặn trên lý thuyết trường hợp xấu nhất (worst-case bounds), hoàn toàn thiếu vắng các kiểm chứng thực nghiệm toàn diện về thời gian chạy thực tế và chất lượng của cận dưới.
  3. Các phương pháp meta-heuristic hiện hữu (như GRASP-VNS của Salehipour et al., 2011 hay ILS-RVND của Silva et al., 2012) đối mặt với chi phí tính toán biến thiên độ trễ theo bậc $O(n)$ mỗi khi đánh giá một phép chuyển đổi lân cận cục bộ.

Luận án tiến sĩ của NCS. Ban Hà Bằng, dưới sự hướng dẫn khoa học của PGS. Nguyễn Đức Nghĩa tại Đại học Bách khoa Hà Nội (mã số chuyên ngành Khoa học máy tính: 62480101), đã giải quyết đồng bộ và toàn diện cả ba khoảng trống trên thông qua hệ thống câu hỏi và giả thuyết nghiên cứu được xác định tường minh:

  • Câu hỏi nghiên cứu 1 (RQ1): Làm thế nào để thiết lập các tiêu chuẩn cắt tỉa nhánh chặt chẽ nhằm mở rộng không gian giải chính xác của thuật toán nhánh cận lên quy mô $n \ge 40$ đỉnh?
  • Câu hỏi nghiên cứu 2 (RQ2): Mối quan hệ thực nghiệm giữa cận tỷ lệ lý thuyết, thời gian thực thi và chất lượng cận dưới của các thuật toán gần đúng là gì, và phương pháp Subgradient có thể tối ưu hóa cận dưới ra sao?
  • Câu hỏi nghiên cứu 3 (RQ3): Làm thế nào để thiết kế các thuật toán meta-heuristic lai ghép (ACO-GA, TS-VNS) kết hợp cơ chế đánh giá độ trễ lân cận trong thời gian hằng số $O(1)$ để cải thiện chất lượng nghiệm trên các không gian dữ liệu lớn lên tới $n = 500$ đỉnh?

Khung lý thuyết của luận án được xây dựng dựa trên sự giao thoa giữa Lý thuyết độ phức tạp tính toán (Computational Complexity Theory của Papadimitriou, 1991), Lý thuyết không gian metric đầy đủ (Metric Embedding của Wu et al., 2000), Kỹ thuật đối ngẫu nới lỏng Lagrange (Lagrangian Relaxation của Held & Karp, 1971; Archer et al., 2008), và Lý thuyết tìm kiếm tiến hóa - bầy đàn tự thích nghi (Genetic Algorithms của Holland, 1975; Ant Colony Optimization của Dorigo, 1992; Tabu Search của Glover, 1986; Variable Neighborhood Search của Mladenović & Hansen, 1997). Phạm vi thực nghiệm của công trình trải rộng từ tập dữ liệu ngẫu nhiên Euclid ($n = 30 \dots 40$), dữ liệu ngẫu nhiên phi Euclid thỏa mãn bất đẳng thức tam giác, bộ dữ liệu chuẩn quốc tế TSPLIB ($n = 22 \dots 500$) và bộ kiểm thử TPR-10-Rx đến TPR-500-Rx.

Literature Review và Positioning

Lịch sử nghiên cứu bài toán MLP ghi nhận ba trường phái học thuật chính với sự tham gia của các nhà khoa học hàng đầu thế giới:

                                 TIẾN TRÌNH LỊCH SỬ VÀ ĐỊNH VỊ HỌC THUẬT CỦA BÀI TOÁN MLP
Năm    Tác giả & Công trình                     Tiếp cận                 Đóng góp chính / Giới hạn
1991   Papadimitriou                            Lý thuyết độ phức tạp    Chứng minh MLP là NP-khó trên đồ thị tổng quát
1994   Blum, Chalasani, Coppersmith et al.      Gần đúng k-MST           Thuật toán gần đúng cận tỷ lệ 144 (metric: 16)
1998   Goemans & Kleinberg                      Đường đi Euler k-MST     Hạ cận tỷ lệ xuống 21 (trường hợp metric: 7.18)
2000   Wu, Chao & Tang                          Quy hoạch động & B&B     Thuật toán đúng đầu tiên giải được quy mô n = 26
2003   Arora & Karakostas                       Mở rộng không gian       Đưa ra thuật toán cận tỷ lệ 17
2003   Chaudhuri, Godfrey, Rao & Talwar         k-troll Bounding         Đạt cận tỷ lệ lý thuyết tốt nhất: 3.59
2008   Archer, Levin & Williamson               Lagrangian Relaxation    Cận lý thuyết 7.18; thực nghiệm TSPLIB đạt 3.01
2011   Salehipour, Sörensen, Goos et al.        Meta-heuristic           Thuật toán kết hợp GRASP và VNS
2012   Silva, Subramanian, Ochi et al.          Meta-heuristic           Thuật toán kết hợp ILS và RVND
2014   Ban Hà Bằng & Nguyễn Đức Nghĩa           Đa trường phái đồng bộ   • B&B với 2 quy tắc cắt nhánh phá vỡ mốc n = 40
       (Công trình Luận án Tiến sĩ)                                      • Kiểm chứng thực nghiệm 5 thuật toán cận tỷ lệ
                                                                         • Thuật toán Subgradient hạ thấp cận sai số
                                                                         • Đề xuất GA-SDT, ACO-GA và TS-VNS với O(1)

Trong dòng chảy lý thuyết cận tỷ lệ, một cuộc tranh luận học thuật lớn xoay quanh việc lựa chọn cấu trúc đồ thị con để tạo cận dưới cho độ trễ đỉnh thứ $k$:

  • Nhóm nghiên cứu của Blum et al. (1994), Goemans & Kleinberg (1998) và Archer et al. (2008) bảo vệ quan điểm sử dụng chi phí cây khung nhỏ nhất đi qua $k$ đỉnh ($k$-MST) kết hợp nới lỏng Lagrange. Nếu bài toán $k$-MST có thuật toán xấp xỉ cận tỷ lệ $\beta = 2$ (Garg, 1996), cận tỷ lệ cho MLP lần lượt là $16$ (Blum et al.) và $7.18$ (Goemans et al., Archer et al.).
  • Ngược lại, Chaudhuri et al. (2003) phản biện rằng cây khung $k$-MST làm lỏng cận dưới do không tính đến cấu trúc tuyến tính của đường đi. Họ đề xuất bài toán đường đi ngắn nhất đi qua $k$ đỉnh ($k$-troll) để ép cận tỷ lệ xuống $3.59$. Tuy nhiên, cấu trúc $k$-troll làm bùng nổ thời gian tính toán, khiến thuật toán gần như không thể triển khai trên các tập dữ liệu thực nghiệm thực tế.

Đối chiếu với các công trình quốc tế điển hình:

  1. So sánh với Archer, Levin & Williamson (2008): Mặc dù Archer et al. đã ứng dụng nới lỏng Lagrange để giảm số lần gọi cây Steiner thu thập giải thưởng (Prize Collecting Steiner Tree - PCST) xuống $O(n \log n)$ và đo lường thực nghiệm trên TSPLIB đạt cận trung bình $3.01$, họ không đánh giá chất lượng cận dưới thực tế so với nghiệm tối ưu tuyệt đối do thiếu vắng công cụ giải chính xác tại thời điểm đó. Luận án của Ban Hà Bằng đã bù đắp khoảng trống này bằng cách dùng nghiệm đúng từ thuật toán nhánh cận để xác định chính xác độ lệch thực nghiệm.
  2. So sánh với Silva, Subramanian & Ochi (2012): Nghiên cứu của Silva et al. sử dụng phương pháp tìm kiếm lân cận ngẫu nhiên (RVND) kết hợp tìm kiếm địa phương lặp (ILS), đạt kết quả tốt trên bộ dữ liệu TPR nhưng tiêu tốn thời gian tính toán lớn ở các quy mô $n \ge 200$. Luận án đã vượt lên bằng cấu trúc thuật toán lai TS-VNS, trong đó kỹ thuật tính độ trễ lân cận trong thời gian hằng số $O(1)$ cho phép duyệt qua hàng triệu hoán vị cấu trúc chỉ trong vài giây.

Đóng góp lý thuyết và khung phân tích

                                          KHUNG PHÂN TÍCH TỔNG HỢP CỦA LUẬN ÁN

Đóng góp cho lý thuyết

Luận án đã làm sâu sắc thêm lý thuyết bài toán người du lịch phụ thuộc thời gian (TDTSP) khi thiết lập các tính chất toán học đặc thù cho vector trọng số tuyến tính giảm dần $w(i) = n - i$. Đóng góp lý thuyết then chốt nằm ở việc chứng minh ba định lý toán học nền tảng tạo tiền đề cho chiến lược cắt nhánh:

  • Định lý 2.1 (Tính tối ưu của đường đi con): Nếu $T = (v_1, v_2, \dots, v_n)$ là hành trình MLP tối ưu thì mỗi đoạn đường con $P(v_{k-1}, v_k)$ bắt buộc phải là đường đi ngắn nhất giữa hai đỉnh $v_{k-1}$ và $v_k$.
  • Định lý 2.2 (Quy tắc chèn đơn đỉnh): Giả sử $F = (v_1, v_2, \dots, v_k)$ là một hành trình bộ phận cấp $k$. Nếu tồn tại một đỉnh chưa duyệt $v_p \in V \setminus F$ và một chỉ số $j$ ($1 < j < k$) thỏa mãn bất đẳng thức: $$(n - j)c(v_j, v_{j+1}) > (n - j)c(v_j, v_p) + (n - j - 1)c(v_p, v_{j+1})$$ thì hành trình bộ phận $F$ chắc chắn không thể mở rộng thành hành trình tối ưu toàn cục và bị cắt tỉa ngay lập tức.
  • Định lý 2.3 (Quy tắc chèn tích lũy đường đi): Mở rộng Định lý 2.2 bằng việc tính đến toàn bộ độ dài đường đi tích lũy $l(P(v_{j+1}, v_k))$. Nếu thỏa mãn: $$(n - j)c(v_j, v_{j+1}) + l(P(v_{j+1}, v_k)) + c(v_k, v_p) > (n - j)c(v_j, v_p) + (n - j - 1)c(v_p, v_{j+1})$$ thì toàn bộ nhánh tìm kiếm xuất phát từ $F$ bị loại bỏ.

Dựa trên các định lý trên, hàm ước lượng cận dưới $LB(F)$ được chuẩn hóa toán học như sau:

$$LB(F) = L(F) + (n - k) \cdot l(P(v_1, v_k)) + \sum_{i=1}^{n-k} (n - k - i + 1) e_i$$

trong đó $e_1 \le e_2 \le \dots \le e_{n-k}$ là các cạnh có trọng số nhỏ nhất trong ma trận chi phí của tập đỉnh chưa được duyệt.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp thành công ba chiều kích phương pháp luận:

  1. Cơ chế đánh giá lân cận thời gian hằng số $O(1)$: Trong các thuật toán hoán vị kinh điển cho TSP (như 2-opt, relocate, swap), biến thiên chi phí được tính trong $O(1)$. Tuy nhiên, đối với MLP, việc hoán đổi vị trí của hai đỉnh tại vị trí $i$ và $j$ làm thay đổi thời gian chờ đợi của tất cả các đỉnh phía sau nó, đòi hỏi chi phí tính toán $O(n)$. Luận án đã xây dựng công thức giải tích phân rã sự biến thiên tổng độ trễ $\Delta L$, chuyển đổi toàn bộ các phép biến đổi lân cận trong Tabu Search và Variable Neighborhood Search về độ phức tạp $O(1)$.
  2. Kỹ thuật thảm họa xã hội (Social Disaster Technique - SDT): Tích hợp vào thuật toán di truyền (GA-SDT) nhằm giải quyết hiện tượng suy thoái đa dạng di truyền (premature convergence). Khi quần thể bị kẹt tại cực trị địa phương qua $NGD$ thế hệ liên tiếp, một cơ chế "thảm họa" được kích hoạt để xóa bỏ phần lớn các cá thể kém thích nghi và tái tạo các cá thể ngẫu nhiên có định hướng.
  3. Điều kiện biên (Boundary conditions): Toàn bộ các định lý và thuật toán được chứng minh trên không gian đồ thị metric đầy đủ $K_n$, thỏa mãn bất đẳng thức tam giác $c_{ij} \le c_{ik} + c_{kj}, \forall i, j, k \in V$.

Phương pháp nghiên cứu tiên tiến

                                         QUY TRÌNH THỰC NGHIỆM VÀ PHÂN TÍCH DỮ LIỆU

Thiết kế nghiên cứu

Nghiên cứu tuân thủ chặt chẽ thế giới quan thực chứng (positivism) và phương pháp luận tính toán thực nghiệm (computational experimental methodology). Cấu trúc thực nghiệm đa tầng bao gồm:

  • Tầng kiểm chứng tối ưu tuyệt đối ($n \le 40$): Sử dụng thuật toán B&B để thiết lập giá trị $OPT$ nền tảng cho 30 file ngẫu nhiên Euclid (Bộ ngẫu nhiên 1), 30 file ngẫu nhiên phi Euclid (Bộ ngẫu nhiên 2), 40 file trích chọn từ TSPLIB (Bộ thực 2) và các file nhỏ trong TSPLIB (Ulysses22, Gr24, Gr26).
  • Tầng đánh giá tiệm cận và nới lỏng ($n = 50 \dots 100$): Kiểm tra sự suy giảm chất lượng cận dưới và sự tăng trưởng thời gian chạy của các giải thuật xấp xỉ cận tỷ lệ.
  • Tầng mở rộng quy mô lớn ($n = 100 \dots 500$): Đánh giá năng lực tối ưu của các thuật toán meta-heuristic lai trên bộ dữ liệu TPR ($n = 100, 200, 500$) và các bài toán lớn từ TSPLIB (kroA100, berlin52, tsp225, lin105).

Quy trình nghiên cứu rigorous

Quy trình thu thập và xử lý dữ liệu được chuẩn hóa cao độ:

  • Phân nhóm dữ liệu thực 2: Phân loại dựa trên mật độ tọa độ không gian $\Delta x = \frac{x_{\max} - x_{\min}}{n}$ và $\Delta y = \frac{y_{\max} - y_{\min}}{n}$:
    • Nhóm 1 (Phân bố tập trung, cụm): $\Delta x, \Delta y \le 3$ (eil51, st70, eil76, rat195).
    • Nhóm 2 (Phân bố thưa thớt): $\Delta x, \Delta y \ge 9$ (kroA100, kroB100, kroC100, berlin52).
    • Nhóm 3 (Phân bố hình học đặc biệt): Các điểm cách đều, thẳng hàng hoặc lưới (tsp225, tss225, pr76, lin105).
  • Quy chuẩn độ tin cậy: Mỗi thuật toán meta-heuristic được thực thi $10$ lần độc lập trên từng file dữ liệu với các hạt giống ngẫu nhiên (random seeds) khác nhau. Kết quả báo cáo thể hiện giá trị trung bình, độ lệch chuẩn và giải pháp tốt nhất ($Best Sol$).
  • Môi trường phần cứng: Hệ thống Intel Core 2 Duo 2.13 GHz, RAM 4GB chạy trên nền Linux. Riêng các thử nghiệm đối chuẩn với thuật toán BA của Wu et al. (2000) được thực hiện trên cấu hình đồng nhất Intel Pentium 2.4 GHz, RAM 256MB để đảm bảo tính khách quan tuyệt đối của thước đo thời gian.

Data và phân tích

Hai chỉ số đo lường chất lượng giải pháp được thiết lập tường minh:

$$\text{gap}_1 [%] = \frac{\text{Best Sol} - \text{OPT}}{\text{OPT}} \times 100% \quad (\text{đối với } n \le 40)$$

$$\text{gap}_2 [%] = \frac{\text{UB} - \text{Best Sol}}{\text{UB}} \times 100% \quad (\text{đối với } n > 40)$$

trong đó $\text{UB}$ là cận trên khởi tạo từ thuật toán lân cận gần nhất (Nearest Neighbor).

Phát hiện đột phá và implications

Những phát hiện then chốt

                     SO SÁNH THỜI GIAN CHẠY GIỮA CÁC THUẬT TOÁN ĐÚNG TRÊN BỘ DỮ LIỆU THỰC NHỎ
  1. Vượt qua giới hạn kích thước giải chính xác: Thuật toán nhánh cận đề xuất giải chính xác toàn bộ các bài toán có quy mô lên tới $n = 40$ đỉnh. Trên các file dữ liệu chuẩn, thời gian thực thi của thuật toán đề xuất (EA1 và EA2) vượt trội hoàn toàn so với thuật toán BA của Wu et al. (2000). Cụ thể tại file Ulysses22, EA2 chỉ mất $2.8$ giây so với $12.1$ giây của BA (nhanh hơn $76.8%$). Tại Gr24, EA2 mất $8.3$ giây so với $24.3$ giây của BA (nhanh hơn $65.8%$). Tại Gr26, EA2 hoàn thành trong $16.5$ giây so với $38.6$ giây của BA (nhanh hơn $57.2%$).
  2. Tác động vượt bậc của cận trên khởi tạo (Upper Bound Impact): Việc tích hợp lời giải từ thuật toán lai ACO-GA làm cận trên ($UB_2$) giúp thuật toán nhánh cận cắt tỉa không gian trạng thái nhanh hơn từ $20%$ đến $35%$ so với cận khởi tạo từ Nearest Neighbor ($UB_1$). Tại tập ngẫu nhiên 1 với $n = 40$, thời gian chạy trung bình giảm từ $111.4$ phút ($UB_1$) xuống còn $91.6$ phút ($UB_2$). Tại tập dữ liệu thực 2 với $n = 40$, thời gian giảm mạnh từ $83.2$ phút xuống $60.9$ phút.
       HIỆU NĂNG THỜI GIAN TRUNG BÌNH CỦA THUẬT TOÁN NHÁNH CẬN THEO QUY MÔ ĐỈNH (TÍNH BẰNG PHÚT)
  1. Hiện tượng cấu trúc mật độ không gian: Hiệu năng thuật toán nhánh cận phụ thuộc chặt chẽ vào độ phân tán hình học của các đỉnh. Các đồ thị thuộc Nhóm 1 ($\Delta x, \Delta y \le 3$) có thời gian giải trung bình nhanh hơn đáng kể so với Nhóm 2 ($\Delta x, \Delta y \ge 9$). Nguyên nhân do các đỉnh phân bố gần nhau giúp hàm cận dưới $LB(F)$ phản ánh chính xác hơn chi phí thực tế, kích hoạt điều kiện cắt nhánh sớm tại các tầng cây đệ quy thấp.
  2. Hiệu năng đột phá của thuật toán lai TS-VNS: Thuật toán TS-VNS kết hợp đánh giá $O(1)$ đạt độ chính xác tuyệt đối $\text{gap}_1 = 0.0%$ trên $100%$ các bộ dữ liệu nhỏ ($n \le 40$). Đối với các bộ dữ liệu lớn ($n = 500$), TS-VNS vượt qua các thuật toán của Salehipour et al. (2011) và Silva et al. (2012) cả về chỉ số cải thiện $\text{gap}_2$ và tốc độ hội tụ.

Implications đa chiều

  • Về mặt lý thuyết: Cung cấp cơ sở toán học chứng minh mối liên hệ hữu cơ giữa kỹ thuật nới lỏng Subgradient và bài toán cực tiểu hóa độ trễ; mở rộng biên giới hiểu biết về hành vi của các hàm mục tiêu phi cục bộ.
  • Về mặt phương pháp luận: Chuẩn hóa khung thực nghiệm đánh giá ba trục (Cận tỷ lệ - Thời gian thực thi - Chất lượng cận dưới) cho các bài toán tối ưu tổ hợp thuộc lớp NP-khó; cung cấp thư viện mã nguồn và mẫu hình thiết kế $O(1)$ lân cận cho cộng đồng nghiên cứu.
  • Về mặt ứng dụng thực tiễn: Giải quyết trực tiếp bài toán kinh tế trong logistics giao hàng chặng cuối (last-mile delivery) và thương mại điện tử, giúp giảm thiểu trung bình $15% - 22%$ tổng thời gian chờ đợi của khách hàng so với việc sử dụng lộ trình tối ưu theo chiều dài TSP truyền thống.

Limitations và Future Research

Mặc dù đạt được những kết quả đột phá, luận án thẳng thắn thừa nhận các giới hạn học thuật:

  1. Rào cản bùng nổ tổ hợp ngoài mốc $n > 40$: Thuật toán nhánh cận dù đã tối ưu hóa vẫn chịu sự chi phối của độ phức tạp hàm mũ trong trường hợp xấu nhất, chưa thể mở rộng việc giải đúng lên quy mô $n \ge 50$ đỉnh trên phần cứng tuần tự đơn nhân.
  2. Giới hạn không gian metric vô hướng: Nghiên cứu tập trung vào đồ thị vô hướng thỏa mãn bất đẳng thức tam giác. Các trường hợp đồ thị có hướng không đối xứng (Asymmetric MLP) hoặc có ràng buộc khung thời gian (Time Windows) chưa được mô hình hóa sâu trong luận án này.
  3. Môi trường tĩnh (Deterministic & Static Networks): Toàn bộ chi phí cạnh $c_{ij}$ được giả định là hằng số cố định, chưa phản ánh đầy đủ yếu tố tắc nghẽn giao thông ngẫu nhiên trong thời gian thực.

Các hướng phát triển nghiên cứu tương lai bao gồm:

  • Thiết kế thuật toán nhánh cận song song (Parallel Branch and Bound) tận dụng năng lực tính toán phân tán và siêu máy tính đa lõi/GPU.
  • Phát triển các mô hình MLP ngẫu nhiên (Stochastic MLP) và MLP động (Dynamic MLP) ứng dụng trong điều vận xe tự hành thông minh.
  • Ứng dụng mạng nơ-ron đồ thị (Graph Neural Networks - GNN) kết hợp học tăng cường sâu (Deep Reinforcement Learning) để sinh nghiệm khởi tạo thông minh cho TS-VNS.

Tác động và ảnh hưởng

Luận án đã tạo ra những tác động học thuật và thực tiễn sâu rộng:

  • Tác động học thuật: Các kết quả nghiên cứu là nền tảng cho $07$ công trình khoa học được công bố trên các tạp chí và kỷ yếu hội nghị quốc tế uy tín. Bộ nghiệm tối ưu $OPT$ cho các đồ thị $n = 30 \dots 40$ do luận án thiết lập đã trở thành bộ dữ liệu chuẩn (ground truth benchmarks) phục vụ việc đánh giá các giải thuật xấp xỉ trên toàn thế giới.
  • Tác động công nghiệp và chuyển giao: Khung thuật toán TS-VNS và ACO-GA cung cấp lõi thuật toán tối ưu cho các hệ thống điều hành logistics thông minh, hệ thống định tuyến xe cứu thương trong đô thị và thuật toán lập lịch thu thập dữ liệu tự động (web crawling) của các công cụ tìm kiếm mạng.

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

                                            MA TRẬN ĐỐI TƯỢNG HƯỞNG LỢI

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nền tảng nào?

Đóng góp độc đáo nhất là việc phát triển và chứng minh hình thức hai định lý cắt nhánh (Định lý 2.2 và Định lý 2.3) cùng công thức cận dưới tích lũy $LB(F)$ trong không gian metric. Nghiên cứu đã mở rộng trực tiếp Lý thuyết bài toán người du lịch phụ thuộc thời gian (TDTSP) của Picard & Queyranne (1978) và giải quyết rào cản tính toán phi cục bộ của bài toán MLP do Blum et al. (1994) đặt ra.

2. Phương pháp luận có điểm gì đổi mới khi so sánh với ít nhất hai nghiên cứu quốc tế trước đó?

So với thuật toán nhánh cận kết hợp quy hoạch động của Wu et al. (2000) (vốn dừng lại ở $n = 26$), luận án đã nâng giới hạn giải đúng lên $n = 40$ đỉnh nhờ kỹ thuật cắt nhánh tiên tiến và tích hợp cận trên chất lượng cao từ ACO-GA. So với công trình của Archer et al. (2008) (chỉ đo lường cận trên TSPLIB), luận án đã thiết lập quy trình kiểm chứng thực nghiệm 3 chiều (Cận tỷ lệ - Thời gian - Cận dưới) và đề xuất thuật toán Subgradient giải quyết triệt để vấn đề chất lượng cận dưới.

3. Phát hiện bất ngờ nhất từ dữ liệu thực nghiệm là gì?

Phát hiện bất ngờ nhất nằm ở cấu trúc hình học của dữ liệu: Các đồ thị có đỉnh phân bố tập trung thành cụm ($\Delta x, \Delta y \le 3$) cho tốc độ hội tụ nhánh cận nhanh hơn gấp nhiều lần so với các đồ thị phân bố thưa thớt ($\Delta x, \Delta y \ge 9$). Về mặt trực giác, việc các đỉnh tập trung dễ gây bùng nổ hoán vị, nhưng trên thực tế tính chất metric chặt chẽ đã giúp hàm $LB(F)$ loại bỏ sớm hàng triệu nhánh tìm kiếm vô nghiệm.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) hoàn chỉnh không?

Quy trình tái lập được mô tả chi tiết và chuẩn hóa cao độ: Định nghĩa rõ ràng 5 bộ dữ liệu benchmark, công thức toán học tường minh cho các toán tử di truyền, tham số xác suất lai ghép/đột biến, danh sách cấm Tabu, thứ tự chuyển đổi lân cận VNS và cấu hình môi trường phần cứng đối chuẩn.

5. Chương trình nghị sự nghiên cứu 10 năm (10-year research agenda) được vạch ra như thế nào?

Lộ trình 10 năm tập trung vào 4 hướng chiến lược: (1) Mở rộng lý thuyết sang bài toán MLP đa phương tiện và đa phương tiện ngẫu nhiên; (2) Phát triển các thuật toán xấp xỉ phân tán trên kiến trúc GPU/Cloud; (3) Tích hợp học máy tự động (AutoML) và Graph Neural Networks để học cấu trúc đồ thị; (4) Chuyển giao công nghệ vào các nền tảng logistics quốc gia.

Kết luận

Luận án tiến sĩ của NCS. Ban Hà Bằng đã giải quyết xuất sắc và trọn vẹn bài toán cực tiểu hóa độ trễ (MLP) thông qua sáu đóng góp mang tính đột phá:

  1. Phát triển thuật toán nhánh cận chính xác: Phá vỡ giới hạn tính toán tồn tại hơn một thập kỷ, giải quyết thành công và đưa ra nghiệm tối ưu chuẩn cho các bài toán quy mô lên tới $n = 40$ đỉnh trên đồ thị metric.
  2. Chứng minh hệ thống định lý cắt nhánh độc bản: Xây dựng cơ sở lý thuyết toán học vững chắc cho việc loại bỏ các nhánh tìm kiếm không triển vọng dựa trên tính chất tích lũy độ trễ.
  3. Thực nghiệm toàn diện các thuật toán gần đúng: Lần đầu tiên cung cấp bức tranh thực nghiệm hoàn chỉnh về cận tỷ lệ, thời gian chạy và chất lượng cận dưới của 5 thuật toán xấp xỉ hàng đầu thế giới.
  4. Đề xuất thuật toán cận tỷ lệ Subgradient: Tối ưu hóa hàm đối ngẫu Lagrange, mang lại cận tỷ lệ thực nghiệm vượt trội so với các thuật toán xấp xỉ hiện biết trên nhiều tập dữ liệu.
  5. Sáng tạo các giải thuật meta-heuristic lai (ACO-GA, TS-VNS): Kết hợp thành công kỹ thuật thảm họa xã hội (SDT) và cơ chế đánh giá biến thiên độ trễ trong thời gian hằng số $O(1)$, đạt độ chính xác tối ưu tuyệt đối trên các không gian nhỏ và dẫn đầu về chất lượng nghiệm trên các không gian lớn ($n = 500$).
  6. Công bố học thuật và di sản dữ liệu chuẩn: Đóng góp 07 công trình khoa học chuyên ngành và bộ dữ liệu nghiệm chuẩn $OPT$, tạo nền tảng vững chắc cho các thế hệ nghiên cứu tiếp theo trong lĩnh vực tối ưu hóa tổ hợp và khoa học máy tính.