Tổng quan luận án

Luận án tiến sĩ chuyên ngành Khoa học máy tính (mã số: 62480101) với đề tài "Các thuật toán đúng gần đúng giải bài toán cực tiểu hóa độ trễ" được nghiên cứu sinh Ban Hà Bằng thực hiện tại Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội, dưới sự hướng dẫn khoa học của PGS. Nguyễn Đức Nghĩa, hoàn thành vào tháng 4 năm 2014.

Tính cấp thiết và khoảng trống nghiên cứu

Bài toán cực tiểu hóa độ trễ (Minimum Latency Problem - MLP), hay còn được gọi là bài toán thợ sửa chữa lưu động (Traveling Repairman Problem - TRP) hoặc bài toán người giao hàng (Delivery Man Problem - DMP), là một bài toán tối ưu hóa tổ hợp có nhiều ứng dụng thực tiễn trong lý thuyết lập lịch, định tuyến mạng máy tính và tìm kiếm thông tin trên mạng. Bài toán yêu cầu tìm một hành trình xuất phát từ một nút nguồn đi qua tất cả các nút còn lại của đồ thị sao cho tổng độ trễ (tổng thời gian chờ đợi) của tất cả các nút là nhỏ nhất.

MLP là bài toán thuộc lớp NP-khó trong trường hợp tổng quát và vẫn giữ nguyên tính chất NP-khó ngay cả trên đồ thị cây có trọng số. Khác với bài toán người du lịch (Traveling Salesman Problem - TSP), MLP không có tính chất cục bộ: một thay đổi nhỏ về thứ tự đỉnh trong hành trình hoặc cấu trúc đồ thị đầu vào có thể dẫn tới sự thay đổi lớn trong toàn bộ hàm mục tiêu, khiến các phương pháp tiếp cận chia để trị truyền thống không thể áp dụng hiệu quả.

Khoảng trống nghiên cứu được tác giả xác định gồm:

  1. Các thuật toán đúng hiện có (như phương pháp kết hợp quy hoạch động và nhánh cận của Wu et al.) mới chỉ xử lý được bài toán có kích thước tối đa 26 đỉnh; chưa có thuật toán đúng giải quyết được cho các bài toán quy mô lớn hơn để cung cấp nghiệm tối ưu đối chuẩn.
  2. Các thuật toán gần đúng cận tỷ lệ hiện biết hầu như chỉ được phân tích ở khía cạnh lý thuyết trường hợp tồi nhất, hoàn toàn thiếu vắng các khảo sát thực nghiệm toàn diện về cận tỷ lệ thực tế, thời gian thực thi và chất lượng của các cận dưới.
  3. Các thuật toán meta-heuristic đã công bố cho MLP còn hạn chế về số lượng công trình, chưa khai thác triệt để các kỹ thuật tăng tốc khảo sát lân cận và các cơ chế lai ghép nâng cao chất lượng tìm kiếm.

Mục tiêu và nhiệm vụ nghiên cứu

Mục tiêu tổng quát của luận án là đề xuất các thuật toán giải bài toán MLP với chất lượng lời giải và thời gian tính toán tốt hơn các thuật toán đã công bố, triển khai trên cả ba hướng tiếp cận:

  1. Phát triển thuật toán đúng dựa trên phương pháp nhánh cận với các tiêu chuẩn cắt nhánh mới, tìm lời giải tối ưu cho bài toán có kích thước lên đến 40 đỉnh.
  2. Khảo sát thực nghiệm toàn diện hiệu quả của các thuật toán gần đúng cận tỷ lệ hiện biết trên ba tiêu chí (cận tỷ lệ thực nghiệm, thời gian chạy và chất lượng cận dưới); trên cơ sở đó đề xuất thuật toán gần đúng mới dựa trên phương pháp Subgradient.
  3. Phát triển ba thuật toán meta-heuristic: thuật toán di truyền cải tiến tích hợp kỹ thuật hủy diệt (GA-SDT), thuật toán di truyền lai ghép đàn kiến (ACO-GA), và thuật toán lai ghép giữa tìm kiếm Tabu với tìm kiếm lân cận biến đổi (TS-VNS) có cơ chế tính độ trễ lân cận trong thời gian hằng số $O(1)$.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Bài toán cực tiểu hóa độ trễ (MLP) trên đồ thị vô hướng đầy đủ $K_n = (V, E)$ với tập đỉnh $V = {1, 2, \dots, n}$ và ma trận chi phí không âm $C = (c_{ij})$ thỏa mãn bất đẳng thức tam giác (không gian metric).
  • Phạm vi không gian dữ liệu: Bộ dữ liệu kiểm chuẩn (Benchmark test) gồm các file dữ liệu ngẫu nhiên Euclidean, phi Euclidean (kích thước từ 10 đến 500 đỉnh) và các file dữ liệu thực trích xuất từ thư viện TSPLIB.
  • Môi trường thực nghiệm: Hệ thống máy tính Intel Pentium Core 2 Dual 2.13 GHz, RAM 4GB (đối sánh với cấu hình Intel Pentium 2.4 GHz, RAM 256 MB theo nghiên cứu đối chuẩn của Wu et al.).

Tổng quan tài liệu và vị trí của luận án

Luận án tổng hợp và phân loại các công trình nghiên cứu liên quan đến bài toán MLP theo từng hướng tiếp cận lý thuyết và thuật toán:

1. Tính phức tạp tính toán và các trường hợp đặc biệt

  • Sahni & Gonzalez (1976), Sitters (2002): Chứng minh MLP thuộc lớp NP-khó trong trường hợp tổng quát và trên đồ thị cây có trọng số; chỉ ra sự không tồn tại của lược đồ xấp xỉ thời gian đa thức (trừ khi P = NP).
  • Blum et al. (1994): Chứng minh bài toán giải được trong thời gian đa thức trên cây không trọng số với độ phức tạp $O(\max(n + m))$, trên đường thẳng với $O(n^2)$, và trên cây có đường kính bằng 3 với $O(n^2)$.
  • Wu (2000): Đưa ra thuật toán thời gian đa thức $O(n^k)$ cho trường hợp đồ thị cây có số lượng lá là hằng số $k$.
  • Wu et al. (2004): Đưa ra phép biến đổi quy bài toán MLP tổng quát về bài toán MLP trên đồ thị metric đầy đủ dựa trên ma trận đường đi ngắn nhất.

2. Các hướng tiếp cận thuật toán

  • Hướng tiếp cận đúng: Wu (2000) đề xuất thuật toán quy hoạch động; Wu et al. (2004) phát triển thuật toán kết hợp nhánh cận và quy hoạch động, giải được các bài toán đến 26 đỉnh trên bộ dữ liệu TSPLIB và dữ liệu ngẫu nhiên.
  • Hướng tiếp cận gần đúng cận tỷ lệ ($\alpha$-approximation):
    • Blum et al. (1994): Đề xuất thuật toán xấp xỉ với cận tỷ lệ 144 trong không gian metric (hoặc 16 nếu sử dụng thuật toán $k$-MST cận 2 của Garg).
    • Goemans & Kleinberg (1998): Cải tiến cận tỷ lệ xuống 21 (hoặc 7.18 khi kết hợp thuật toán $k$-MST cận 2).
    • Arora & Karakostas (2003): Thuật toán gần đúng với cận tỷ lệ 17.
    • Archer, Levin & Williamson (2008): Sử dụng kỹ thuật nới lỏng Lagrangian để tạo các cây $k$-MST, đạt cận tỷ lệ lý thuyết 7.18 với độ phức tạp $O(n^3 \log^2 n)$ và cận tỷ lệ thực nghiệm trung bình đạt 3.01 trên TSPLIB.
    • Chaudhuri, Godfrey, Rao & Talwar (2003): Sử dụng bài toán hành trình ngắn nhất qua $k$ đỉnh ($k$-troll) làm cận dưới, đạt cận tỷ lệ lý thuyết 3.59.
  • Hướng tiếp cận meta-heuristic:
    • Salehipour et al. (2011): Đề xuất thuật toán GRASP kết hợp VNS.
    • Silva et al. (2012): Đề xuất thuật toán kết hợp GRASP, ILS (Iterated Local Search) và RVND (Random Variable Neighborhood Descent).

Vị trí và khoảng trống luận án giải quyết

Luận án định vị nghiên cứu tại điểm giao của cả ba hướng: mở rộng giới hạn kích thước giải chính xác của thuật toán đúng lên 40 đỉnh; thiết lập hệ thống thực nghiệm đối sánh đa chiều cho các thuật toán cận tỷ lệ và đề xuất thuật toán Subgradient; đồng thời xây dựng các thuật toán meta-heuristic lai (ACO-GA, TS-VNS) với thuật toán tính độ trễ lân cận tối ưu $O(1)$ vượt trội về chất lượng nghiệm so với các công bố trước đó.

Cơ sở lý thuyết và phương pháp nghiên cứu

Mô hình toán học và công thức hàm mục tiêu

Cho đồ thị đầy đủ $K_n = (V, E)$ với $V = {1, 2, \dots, n}$ và ma trận khoảng cách $C = (c_{ij})$. Một hành trình xuất phát từ đỉnh $v_1$ qua tất cả các đỉnh đúng một lần được biểu diễn bằng $T = (v_1, v_2, \dots, v_n)$. Độ trễ của đỉnh $v_k$ ($k = 2, 3, \dots, n$) trên hành trình $T$ là: $$\text{lat}(v_k) = \sum_{i=1}^{k-1} c(v_i, v_{i+1})$$

Tổng độ trễ của hành trình $T$, ký hiệu $L(T)$, được tính bằ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 biểu thức trên, cạnh thứ $k$ trên hành trình được nhân với trọng số giảm dần $(n - k)$.

Cơ sở phương pháp luận

  1. Phương pháp Nhánh cận (Branch and Bound): Sử dụng chiến lược duyệt quay lui kết hợp hàm đánh giá cận dưới $LB(F)$ và các quy tắc cắt tỉa dựa trên các bất đẳng thức hình học và đại số.
  2. Phương pháp Nới lỏng Lagrangian và Subgradient: Tối ưu hóa hàm đối ngẫu Lagrangian để tìm cận dưới chặt cho độ trễ từng bước của hành trình qua $k$ đỉnh.
  3. Các thuật toán Meta-heuristic:
    • Thuật toán di truyền (GA) kết hợp kỹ thuật hủy diệt xã hội (Social Disaster Technique - SDT) để tái tạo đa dạng quần thể khi hội tụ sớm.
    • Thuật toán đàn kiến (Ant Colony Optimization - ACO) mô phỏng vết mùi pheromone $\tau$ định hướng đường đi.
    • Thuật toán tìm kiếm Tabu (Tabu Search - TS) sử dụng danh sách cấm (tabulist) tránh lặp lại trạng thái đã duyệt.
    • Thuật toán tìm kiếm lân cận biến đổi (Variable Neighborhood Search - VNS) thực hiện tìm kiếm qua nhiều cấu trúc lân cận liên tiếp.

Phân loại dữ liệu thực nghiệm và chỉ số đánh giá

Bộ dữ liệu chuẩn được chia thành các nhóm kích thước:

  • File dữ liệu nhỏ ($n \le 40$): Dùng để tìm nghiệm tối ưu $OPT$ và kiểm thử tham số.
  • File dữ liệu lớn ($n > 40$): Kiểm thử hiệu năng thuật toán gần đúng và meta-heuristic.

Chỉ số đánh giá độ lệch nghiệm:

  • Đối với dữ liệu nhỏ (đã biết $OPT$): $$\text{gap}_1 [%] = \frac{\text{Best_Sol} - OPT}{OPT} \times 100%$$
  • Đối với dữ liệu lớn (so với nghiệm khởi tạo lân cận gần nhất $UB$): $$\text{gap}_2 [%] = \frac{|\text{Best_Sol} - UB|}{UB} \times 100%$$

Nội dung chính theo từng chương

CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN

Chương 1 thiết lập cơ sở hình thức cho toàn bộ luận án:

  • Định nghĩa bài toán MLP và mô hình hóa trong không gian metric; phân tích mối quan hệ giữa MLP với TSP, TRP, DMP và TDTSP (với hàm trọng số $w(i) = n - i$).
  • Phân tích nguyên nhân khiến MLP không có tính chất cục bộ và khó áp dụng phương pháp chia để trị.
  • Trình bày lược đồ nguyên lý của 5 hướng tiếp cận tối ưu tổ hợp kinh điển: Thuật toán nhánh cận, Thuật toán di truyền, Thuật toán đàn kiến, Thuật toán Tabu, và Thuật toán lân cận biến đổi.
  • Điểm luận chi tiết các nghiên cứu liên quan theo 3 nhóm: thuật toán đúng, thuật toán gần đúng cận tỷ lệ ($\alpha$-approximation) và thuật toán meta-heuristic.
  • Xây dựng hệ thống bộ dữ liệu kiểm chuẩn:
Tên bộ dữ liệu Kích thước ($n$) Đặc tính cấu trúc Trạng thái nghiệm tối ưu
Bộ dữ liệu ngẫu nhiên 1 $30 - 40$ Euclidean, chi phí nguyên $1 - 100$ Đã có nghiệm $OPT$ từ luận án
Bộ dữ liệu ngẫu nhiên 2 $30 - 40$ Phi Euclidean, thỏa mãn bất đẳng thức tam giác Đã có nghiệm $OPT$ từ luận án
Bộ dữ liệu ngẫu nhiên 3 $10 - 500$ Euclidean (TPR-10 đến TPR-500) $n=10, 20$ có $OPT$; $n \ge 50$ chưa có
Bộ dữ liệu thực 1 $22 - 500$ Bộ dữ liệu gốc từ TSPLIB Ulysses22, Gr24, Gr26 có $OPT$
Bộ dữ liệu thực 2 $30 - 40$ Trích xuất từ TSPLIB (3 nhóm: cụm, thưa, đặc biệt) Đã có nghiệm $OPT$ từ luận án

CHƯƠNG 2: THUẬT TOÁN NHÁNH CẬN

Chương 2 tập trung xây dựng thuật toán đúng dựa trên phương pháp nhánh cận để giải quyết bài toán MLP cho đồ thị lên đến 40 đỉnh.

Các kết quả lý thuyết và tiêu chuẩn cắt nhánh

Ký hiệu $F = (v_1, v_2, \dots, v_k)$ là hành trình bộ phận cấp $k$ và $B = (v_{k+1}, \dots, v_n)$ là tập các đỉnh còn lại:

  1. Định lý 2.1: Nếu $T$ là hành trình MLP tối ưu thì $l(P(v_{k-1}, v_k))$ phải là độ dài đường đi ngắn nhất giữa $v_{k-1}$ và $v_k$.
  2. Định lý 2.2 (Tiêu chuẩn cắt nhánh 1): Nếu tồn tại $v_p \in V \setminus F$ ($k+1 \le p \le n$) và chỉ số $j$ ($1 < j < k$) thỏa mãn: $$(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$ không thể phát triển thành lời giải tối ưu và bị loại bỏ.
  3. Định lý 2.3 (Tiêu chuẩn cắt nhánh 2): Nếu tồn tại $v_p \in V \setminus F$ và chỉ số $j$ ($1 < j < k$) 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ì hành trình bộ phận $F$ bị cắt nhánh.

Công thức hàm đánh giá cận dưới

Hàm cận dưới $LB(F)$ được xây dựng bằng cách sắp xếp các cạnh chưa duyệt theo thứ tự trọng số tăng dần $c(e_1) < c(e_2) < \dots < c(e_{n-k})$: $$LB(F) = L(F) + (n - k) l(P(v_1, v_k)) + (n - k)e_1 + (n - k - 1)e_2 + \dots + e_{n-k}$$

Kết quả thực nghiệm

Tác giả so sánh thuật toán đề xuất với hai cận trên: $EA_1$ (sử dụng cận trên $UB_1$ từ thuật toán lân cận gần nhất) và $EA_2$ (sử dụng cận trên $UB_2$ từ thuật toán ACO-GA), đồng thời đối sánh với thuật toán $BA$ của Wu et al.

Bộ dữ liệu / File test Kích thước ($n$) $OPT$ Thời gian $EA_1$ Thời gian $EA_2$ Thời gian $BA$ (Wu et al.)
Ulysses22 22 4171 4.12 s 2.15 s 4.80 s
Gr24 24 - 15.30 s 8.40 s 21.60 s
Gr26 26 - 28.50 s 14.20 s 38.40 s
Ngẫu nhiên 1 (TB) 30 - 2.89 phút 1.85 phút Không giải được
Ngẫu nhiên 1 (TB) 35 - 19.90 phút 15.80 phút Không giải được
Ngẫu nhiên 1 (TB) 40 - 111.30 phút 91.60 phút Không giải được
Ngẫu nhiên 2 (TB) 35 - 19.70 phút 15.60 phút Không giải được
Ngẫu nhiên 2 (TB) 40 - 108.40 phút 89.20 phút Không giải được
Thực 2 - Nhóm 1 (TB) 40 - 74.50 phút 54.00 phút Không giải được
Thực 2 - Nhóm 2 (TB) 40 - 86.25 phút 61.75 phút Không giải được
Thực 2 - Nhóm 3 (TB) 40 - 88.50 phút 64.50 phút Không giải được

Kết quả chỉ ra rằng việc sử dụng cận trên chặt từ ACO-GA ($EA_2$) giúp giảm đáng kể thời gian duyệt nhánh. Thuật toán giải chính xác toàn bộ các bài toán lên đến 40 đỉnh, và trên các file thực nghiệm nhỏ ($n=22, 24, 26$), tốc độ thực thi của $EA_1$ và $EA_2$ đều nhanh hơn thuật toán $BA$ của Wu et al.

CHƯƠNG 3: CÁC THUẬT TOÁN GẦN ĐÚNG CẬN TỶ LỆ

Chương 3 thực hiện hai nhiệm vụ: đánh giá thực nghiệm 5 thuật toán cận tỷ lệ tiêu biểu hiện có và đề xuất thuật toán gần đúng mới dựa trên Subgradient.

Đánh giá thực nghiệm các thuật toán hiện biết

Năm thuật toán được khảo sát gồm:

  1. Thuật toán Blum et al. (1994): Cận tỷ lệ lý thuyết 16, độ phức tạp $O(n^3(n + \log c_{\max}) \log^2 n)$, sử dụng chu trình Euler nhân đôi cạnh trên cây $k$-MST.
  2. Thuật toán Goemans et al. (1998): Cận tỷ lệ lý thuyết 7.18, kết nối các hành trình con $T_j$ bằng đường đi ngắn nhất trên đồ thị phụ trợ.
  3. Thuật toán Archer et al. (2008): Cận tỷ lệ lý thuyết 7.18, giảm độ phức tạp xuống $O(n^3 \log^2 n)$ nhờ tạo cây $k$-MST bằng kỹ thuật nới lỏng Lagrangian và thủ tục nội suy Get_k_Tree.
  4. Thuật toán Arora et al. (2003): Cận tỷ lệ lý thuyết 17.
  5. Thuật toán Chaudhuri et al. (2003): Cận tỷ lệ lý thuyết 3.59, sử dụng cận dưới $k$-troll.

Kết quả thực nghiệm cho thấy cận tỷ lệ thực tế của các thuật toán tốt hơn nhiều so với cận lý thuyết trường hợp tồi nhất (ví dụ thuật toán Archer et al. đạt cận thực nghiệm trung bình khoảng 3.01 trên TSPLIB), tuy nhiên sai số vẫn còn lớn đối với yêu cầu ứng dụng thực tiễn.

Thuật toán gần đúng dựa trên phương pháp Subgradient

Luận án đề xuất quy trình tính toán vector bước nhảy Subgradient để tối ưu hóa nhân tử Lagrange, tạo ra các cận dưới chặt hơn cho từng cây $k$-MST và hành trình bộ phận. Kết quả thực nghiệm trên các bộ dữ liệu ngẫu nhiên và TSPLIB chứng minh thuật toán Subgradient cho cận tỷ lệ thực nghiệm trung bình và chất lượng nghiệm cải thiện rõ rệt so với các thuật toán của Blum et al., Goemans et al. và Archer et al.

CHƯƠNG 4: CÁC THUẬT TOÁN META-HEURISTIC

Chương 4 phát triển ba thuật toán meta-heuristic chuyên sâu:

1. Thuật toán di truyền cải tiến (GA-SDT)

  • Cấu trúc: Tích hợp kỹ thuật hủy diệt xã hội (Social Disaster Technique - SDT). Khi quần thể rơi vào trạng thái trì trệ (không cải thiện nghiệm sau $NGD$ thế hệ), SDT sẽ giữ lại một số cá thể tốt nhất và khởi tạo lại ngẫu nhiên các cá thể còn lại để thoát khỏi cực tiểu địa phương.
  • Khảo sát tham số: Luận án tiến hành chuỗi thực nghiệm xác định quy mô quần thể, xác suất lai ghép, xác suất đột biến, tỷ lệ $\alpha_1$, giá trị ngưỡng $NGD$ và số thế hệ $NGT$.

2. Thuật toán di truyền lai ghép đàn kiến (ACO-GA)

  • Kết hợp cơ chế học phân tán dựa trên vết mùi pheromone của ACO với khả năng tìm kiếm toàn cục của GA.
  • Quá trình di chuyển của đàn kiến tạo ra quần thể ban đầu có chất lượng cao; sau đó các toán tử lai ghép và đột biến của GA tiếp tục tối ưu hóa hành trình.

3. Thuật toán lai Tabu và lân cận biến đổi (TS-VNS)

  • Kết hợp danh sách cấm của Tabu Search với cấu trúc đa lân cận của VNS.
  • Kỹ thuật tăng tốc then chốt: Tác giả chứng minh và cài đặt công thức cập nhật độ trễ hành trình khi thực hiện các phép biến đổi lân cận (hoán vị 2 đỉnh, chèn đỉnh, đảo đoạn) với độ phức tạp thời gian $O(1)$ thay vì phải duyệt lại toàn bộ hành trình với chi phí $O(n)$.

Kết quả đối sánh tổng hợp

  • Trên bộ dữ liệu nhỏ ($n \le 40$): Thuật toán TS-VNS và ACO-GA đạt $\text{gap}_1 = 0%$ (tìm ra nghiệm tối ưu tuyệt đối trên $100%$ các file thử nghiệm).
  • Trên bộ dữ liệu lớn ($n = 50 \div 500$): Cả ba thuật toán đề xuất đều vượt trội so với các thuật toán meta-heuristic của Salehipour et al. (GRASP+VNS) và Silva et al. (GRASP+ILS+RVND) về chỉ số $\text{gap}_2$, độ ổn định (độ lệch chuẩn thấp) và thời gian thực thi.

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả khoa học chính sau:

  1. Về mặt lý luận và thuật toán đúng:

    • Chứng minh 3 định lý toán học xác lập các tính chất của hành trình tối ưu và đưa ra 2 tiêu chuẩn cắt nhánh hiệu quả cho bài toán MLP.
    • Xây dựng thành công thuật toán nhánh cận có khả năng giải chính xác bài toán MLP với kích thước lên đến 40 đỉnh, vượt qua giới hạn 26 đỉnh của thuật toán đúng tốt nhất trước đó (Wu et al., 2004).

  2. Về mặt đánh giá và phát triển thuật toán gần đúng:

    • Thực hiện nghiên cứu thực nghiệm đầu tiên đánh giá toàn diện 5 thuật toán gần đúng cận tỷ lệ hiện biết trên cả ba khía cạnh: cận tỷ lệ thực tế, thời gian thực thi và chất lượng cận dưới.
    • Đề xuất thuật toán gần đúng mới dựa trên phương pháp Subgradient, đạt cận tỷ lệ thực nghiệm tốt hơn các thuật toán gần đúng hiện có trên nhiều bộ dữ liệu chuẩn.

  3. Về mặt phát triển thuật toán meta-heuristic:

    • Đề xuất thuật toán GA tích hợp kỹ thuật hủy diệt SDT giải quyết hiện tượng hội tụ sớm.
    • Đề xuất thuật toán lai ACO-GA kết hợp thế mạnh tìm kiếm của thuật toán di truyền và thuật toán tối ưu hóa đàn kiến.
    • Đề xuất thuật toán lai TS-VNS với cơ chế tính toán độ trễ lân cận trong thời gian hằng số $O(1)$, nâng cao tốc độ khảo sát không gian trạng thái.

  4. Công bố khoa học:

    • Toàn bộ các kết quả nghiên cứu chính của luận án đã được công bố trong 07 công trình khoa học tại các tạp chí và kỷ yếu hội thảo khoa học chuyên ngành quốc gia và quốc tế.

Kiến nghị và giải pháp ứng dụng

  • Ứng dụng thuật toán nhánh cận để giải chính xác các bài toán lập lịch cho hệ thống máy chủ đơn hoặc điều phối sửa chữa quy mô nhỏ ($n \le 40$).
  • Áp dụng các thuật toán meta-heuristic lai (TS-VNS và ACO-GA) cho các bài toán định tuyến gói tin, lập lịch truy vấn máy tìm kiếm và tối ưu hóa logistics giao hàng quy mô lớn ($n \ge 100$) đòi hỏi thời gian phản hồi nhanh và nghiệm tiệm cận tối ưu.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án

  • Thuật toán nhánh cận vẫn chịu giới hạn bùng nổ tổ hợp khi kích thước đồ thị vượt quá 40 đỉnh ($n > 40$).
  • Chất lượng nghiệm của các thuật toán gần đúng cận tỷ lệ trên thực nghiệm tuy có bảo đảm lý thuyết nhưng vẫn có khoảng cách khá lớn so với nghiệm thu được từ các thuật toán meta-heuristic.
  • Hiệu năng của các thuật toán meta-heuristic phụ thuộc vào quá trình thử nghiệm điều chỉnh bộ tham số ban đầu.

Hướng nghiên cứu tiếp theo

  • Nghiên cứu các hàm cận dưới chặt hơn kết hợp quy hoạch nguyên (Integer Programming) hoặc Branch-and-Cut để nâng quy mô giải chính xác của thuật toán đúng lên trên 50 đỉnh.
  • Tiếp tục nghiên cứu giảm cận tỷ lệ lý thuyết cho các thuật toán gần đúng giải bài toán MLP xuống dưới ngưỡng 3.59.
  • Thiết kế các toán tử lân cận song song và cài đặt các thuật toán meta-heuristic lai trên kiến trúc tính toán phân tán/GPU để xử lý bài toán quy mô hàng nghìn đỉnh.

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho:

  • Nghiên cứu sinh, học viên cao học và giảng viên: Chuyên ngành Khoa học máy tính, Toán tin ứng dụng và Vận trù học; có thể tham khảo phương pháp mô hình hóa bài toán tối ưu tổ hợp NP-khó, kỹ thuật chứng minh định lý cắt nhánh trong thuật toán nhánh cận, và kỹ thuật thiết kế thuật toán meta-heuristic lai.
  • Kỹ sư và nhà phát triển hệ thống: Trong các lĩnh vực mạng máy tính, giao thông thông minh, logistics và tối ưu hóa công cụ tìm kiếm; có thể khai thác thuật toán TS-VNS với kỹ thuật tính độ trễ $O(1)$ để tích hợp vào các module điều độ và tìm đường thời gian thực.
  • Hệ thống dữ liệu kiểm chuẩn: Bộ dữ liệu nhỏ ($n \le 40$) kèm nghiệm tối ưu $OPT$ được luận án công bố là nguồn dữ liệu chuẩn xác thực để các nhóm nghiên cứu sau kiểm nghiệm và đánh giá chất lượng các thuật toán xấp xỉ mới.

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

1. Bài toán cực tiểu hóa độ trễ (MLP) khác biệt căn bản với bài toán người du lịch (TSP) ở những điểm nào?

Cả hai bài toán đều tìm hành trình đi qua tất cả các đỉnh của đồ thị, nhưng hàm mục tiêu của TSP tính tổng độ dài các cạnh trên chu trình, trong khi hàm mục tiêu của MLP tính tổng độ trễ từ nút xuất phát đến từng đỉnh. Do trọng số của cạnh thứ $k$ trong MLP bị nhân với thừa số $(n - k)$, MLP không có tính chất cục bộ: hoán đổi vị trí hai đỉnh có thể làm thay đổi toàn bộ chi phí của các đỉnh phía sau. Ngoài ra, chỉ một thay đổi nhỏ trong đồ thị đầu vào cũng có thể làm thay đổi hoàn toàn cấu trúc hành trình tối ưu của MLP, khiến bài toán có độ phức tạp cao hơn TSP và không thể giải hiệu quả bằng phương pháp chia để trị.

2. Hai tiêu chuẩn cắt nhánh trong thuật toán nhánh cận (Chương 2) được thiết lập dựa trên nguyên lý nào?

Hai tiêu chuẩn cắt nhánh được xây dựng dựa trên phép so sánh chi phí khi chèn một đỉnh $v_p$ chưa duyệt vào giữa hai đỉnh liên tiếp $(v_j, v_{j+1})$ của hành trình bộ phận $F$. Dựa trên bất đẳng thức tam giác trong không gian metric, nếu việc chèn đỉnh này tạo ra một hành trình mới có tổng độ trễ nhỏ hơn hành trình hiện tại (thỏa mãn bất đẳng thức tại Định lý 2.2 hoặc Định lý 2.3), điều đó chứng minh hành trình bộ phận $F$ không thể phát triển thành lời giải tối ưu và nhánh duyệt tương ứng sẽ bị cắt tỉa ngay lập tức.

3. Thuật toán của Archer et al. (Chương 3) đã cải tiến điều gì so với thuật toán của Goemans et al. và Blum et al.?

Thuật toán của Archer et al. không sử dụng thuật toán giải $k$-MST truyền thống vốn có chi phí tính toán cao, mà áp dụng kỹ thuật nới lỏng Lagrangian để sinh ra tập các cây $k$-MST thông qua thủ tục nội suy Get_k_Tree. Cải tiến này giúp giảm số lần gọi thủ tục PCST (Prize Collecting Steiner Tree) xuống còn $O(n \log n)$, qua đó giảm độ phức tạp thời gian tổng thể xuống $O(n^3 \log^2 n)$ thay vì phụ thuộc vào tham số trọng số cạnh $c_{\max}$, trong khi vẫn duy trì được cận tỷ lệ lý thuyết 7.18.

4. Thuật toán meta-heuristic TS-VNS đạt được ưu thế vượt trội về tốc độ tính toán nhờ cơ chế nào?

Ưu thế tốc độ của thuật toán TS-VNS xuất phát từ việc tác giả đã thiết lập công thức tính toán biến thiên độ trễ khi thực hiện các phép chuyển lân cận (như 2-opt, insert, swap) trong thời gian hằng số $O(1)$. Thay vì phải duyệt lại toàn bộ $n$ đỉnh để tính lại hàm mục tiêu với độ phức tạp $O(n)$ cho mỗi lời giải lân cận, thuật toán chỉ tính toán sự thay đổi cục bộ của các đoạn đường bị tác động, giúp quá trình duyệt toàn bộ không gian lân cận của Tabu Search và VNS diễn ra nhanh chóng.

5. Luận án sử dụng các tiêu chí nào để đánh giá độ chính xác của nghiệm trên các tập dữ liệu thực nghiệm?

Luận án sử dụng hai tiêu chí:

  • Với tập dữ liệu nhỏ ($n \le 40$): Sử dụng chỉ số $\text{gap}_1 = \frac{\text{Best_Sol} - OPT}{OPT} \times 100%$, đo khoảng cách phần trăm trực tiếp giữa nghiệm tìm được và nghiệm tối ưu tuyệt đối $OPT$ do thuật toán đúng cung cấp (giá trị càng nhỏ càng tốt, bằng 0 tức là đạt tối ưu).
  • Với tập dữ liệu lớn ($n > 40$, chưa biết $OPT$): Sử dụng chỉ số $\text{gap}_2 = \frac{|\text{Best_Sol} - UB|}{UB} \times 100%$, đo mức độ cải thiện phần trăm của nghiệm so với nghiệm xuất phát $UB$ từ thuật toán lân cận gần nhất (giá trị càng lớn chứng tỏ nghiệm càng được cải thiện nhiều).

Kết luận

Luận án của nghiên cứu sinh Ban Hà Bằng đã giải quyết bài toán cực tiểu hóa độ trễ (MLP) thông qua việc phát triển hệ thống thuật toán trên cả ba hướng tiếp cận: đúng, gần đúng cận tỷ lệ và meta-heuristic. Công trình đã mở rộng giới hạn giải chính xác của bài toán MLP lên 40 đỉnh bằng phương pháp nhánh cận với các tiêu chuẩn cắt tỉa mới, đồng thời cung cấp bức tranh thực nghiệm toàn diện đầu tiên về các thuật toán gần đúng cận tỷ lệ và đề xuất thuật toán Subgradient cải tiến. Bên cạnh đó, các thuật toán meta-heuristic lai (ACO-GA, TS-VNS) với kỹ thuật cập nhật độ trễ trong thời gian $O(1)$ đã nâng cao chất lượng nghiệm và tốc độ xử lý trên các tập dữ liệu chuẩn quy mô lên đến 500 đỉnh, đóng góp thiết thực cho lý thuyết tối ưu hóa tổ hợp và các bài toán ứng dụng thực tế.