i

LỜI CAM ĐOAN
Tôi xin cam đoan luận án này là kết quả nghiên cứu của tôi. Các kết quả viết chung với các
tác giả khác đều đã được sự nhất trí của các đồng tác giả khi đưa vào luận án. Những kiến
thức tham khảo để hoàn thành luận án đều được trích dẫn đầy đủ từ danh mục tài liệu tham
khảo.
Người hướng dẫn khoa học

PGS.TS. Nguyễn Đức Nghĩa
Hà Nội, 04-2014

Tác giả luận án

Ban Hà Bằng iii

Mục Lục
LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
Tóm tắt v
Danh mục thuật ngữ vii
Danh mục bảng viii
Danh mục hình vẽ x
CHƢƠNG 1 TỔNG QUAN VỀ BÀI TOÁN 1
1.1 Mô hình toán học của bài toán cực tiểu hóa độ trễ 2
1.2 Một số hướng tiếp cận giải bài toán tối ưu hóa tổ hợp 5
1.2.1 Thuật toán nhánh cận 5
1.2.2 Thuật toán di truyền 8
1.2.3 Thuật toán đàn kiến 10
1.2.4 Thuật toán Tabu 10
1.2.5 Thuật toán lân cận biến đổi 11
1.3 Các nghiên cứu liên quan giải bài toán MLP 11
1.3.1 Thuật toán đúng 12
1.3.2 Thuật toán gần đúng cận tỷ lệ 12
1.3.3 Thuật toán meta-heuristic 13
1.4 Mục đích, phạm vi nghiên cứu 14
1.5 Dữ liệu thực nghiệm 15
1.6 Kết quả của luận án 18
1.7 Cấu trúc của luận án 20
CHƢƠNG 2 THUẬT TOÁN NHÁNH CẬN 21
2.1 Lược đồ thuật toán 22
v

Tóm tắt
Bài toán cực tiểu hóa độ trễ (Minimum latency problem - MLP) dưới dạng tổng quát có thể
phát biểu trong ngôn ngữ của lý thuyết đồ thị như sau: Cho G = (V, E) là đồ thị vô hướng có
trọng số không âm trên mỗi cạnh e  E. Giả sử, T là một hành trình xuất phát từ đỉnh s,
chúng ta định nghĩa độ trễ của một đỉnh v bất kỳ thuộc T là độ dài của đường đi từ đỉnh xuất
phát s đến v trên T. Độ trễ của hành trình T được định nghĩa như là tổng độ trễ của tất cả các
đỉnh
thuộc hành trình T.
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.

Bài toán MLP có nhiều ứng dụng trong thực tiễn. Cụ thể, trong lý thuyết lập lịch khi
một máy chủ hay một người thợ phải lên kế hoạch phục vụ một tập các yêu cầu sao cho tổng
(trung bình) thời gian chờ đợi của các yêu cầu là cực tiểu. Trong tìm đường đi trên mạng, bài
toán cũng được ứng dụng để tìm hành trình với tổng độ trễ là nhỏ nhất. Trong bài toán tìm
kiếm thông tin, bài toán MLP được ứng dụng để cực tiểu hóa độ trễ của việc tìm kiếm thông
tin trên mạng.
Mục đích nghiên cứu của chúng tôi trong luận án này 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 tốt hơn chất lượng lời giải của các thuật toán giải bài toán
MLP đã được công bố. Đối với một bài toán NP-khó như bài toán MLP, hiện tại có ba hướng
tiếp cận chính để phát triển thuật toán giải: 1) hướng tiếp cận đúng, 2) hướng tiếp cận gần
đúng cận tỷ lệ, 3) hướng tiếp cận meta-heuristic. Đóng góp của chúng tôi trong luận án là đề
xuất các thuật toán giải theo cả ba hướng tiếp cận:
vii

Danh mục thuật ngữ
STT
Từ viết tắt
Giải nghĩa tiếng Anh
Giải nghĩa tiếng Việt
1
ACO
Ant conoly optimization
Tối ưu hoá đàn kiến
2
ACO-GA
-
Thuật toán di truyền lai ghép thuật
toán đàn kiến
3
GA
Genetic algorithm
Thuật toán di truyền
4
TS
Tabu search
Tìm kiếm Tabu
5

12
DP
Dynamic programming
Quy hoạch động
13
B&B
Branch and bound
Phương pháp nhánh cận
14
CP
Constraint programming
Quy hoạch ràng buộc
15
-
Approximation algoirthm
Thuật toán gần đúng
16
-
Simulated annealing algorithm
Thuật toán phỏng tôi luyện
17
-
Local search
Tìm kiếm địa phương
18
GRASP
Greedy randomized adaptive
search procedure
Thủ tục tìm kiếm tham lam ngẫu
nhiên tự thích nghi

Benchmark test
Bộ dữ liệu chuẩn
26
OPT
Best known solution
Lời giải tốt nhất hiện biết
27
SDT
Social disaster technique
Kỹ thuật hủy diệt
viii

Danh mục bảng
Bảng 1. 1 Mô tả các bộ dữ liệu 16
Bảng 2. 1 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 1 (tính theo phút) 30
Bảng 2. 2 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 2 (tính theo phút) 31
Bảng 2. 3 Thời gian chạy của thuật toán trong bộ dữ liệu thực 2 (tính theo phút) 32
Bảng 2. 4 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-10-Rx) (tính theo giây)
33
Bảng 2. 5 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-20-Rx) (tính theo giây)
34
Bảng 2. 6 Thời gian chạy của thuật toán cho các file dữ liệu nhỏ trong 34
Bảng 3. 1 Kết quả thực nghiệm các thuật toán trong các bộ dữ liệu nhỏ 49
Bảng 3. 2 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx) 50
Bảng 3. 3 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx) 51
Bảng 3. 4 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu thực 1 52
Bảng 3. 5 Kết quả thực nghiệm cho các bộ dữ liệu nhỏ 61
Bảng 3. 6 Kết quả thực nghiệm với bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx) 62
Bảng 3. 7 Mô tả
12

theo phút đối với các bộ dữ liệu lớn 82
Bảng 4. 13 Kết quả thực nghiệm của các thuật toán 90
Bảng 4. 14 Kết quả so sánh các thuật toán cho cho các bộ dữ liệu nhỏ 92
Bảng 4. 15 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx) 93
Bảng 4. 16 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx) 93
ix

Bảng 4. 17 Kết quả so sánh các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx) 94
Bảng 4. 18 Kết quả so sánh các thuật toán cho bộ dữ liệu thực 2 95
Bảng 4. 19 Mô tả
T
đối với các bộ dữ liệu lớn 95
Bảng 4. 20 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu nhỏ 107
Bảng 4. 21 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx) 108
Bảng 4. 22 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx) 108
Bảng 4. 23 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx) 109
Bảng 4. 24 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên 3 (TPR-500-Rx) 109
Bảng 4. 25 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu thực 1 110
Bảng 4. 26 So sánh độ lệch chuẩn độ trễ lời giải của các thuật toán 111
Bảng 4. 27 Mô tả
T
đối với các bộ dữ liệu lớn 111
Bảng 5. 1 Tổng hợp các thuật toán đề xuất 115


Hình 3. 6 Cận dưới trung bình của các thuật toán đối với các bộ dữ liệu nhỏ 47
Hình 3. 7 Thời gian chạy trung bình của các thuật toán đối với các bộ dữ liệu nhỏ 47
Hình 3. 8 Cận tỷ lệ trung bình của các thuật toán đối với các bộ dữ liệu lớn 47
Hình 3. 9 Thời gian chạy trung bình của các thuật toán đối với các bộ dữ liệu lớn 48
Hình 4. 1 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file test 1 trong bộ dữ liệu
ngẫu nhiên 1 qua các thế hệ 76
Hình 4. 2 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file test 1 trong bộ dữ liệu
ngẫu nhiên 2 qua các thế hệ 76
Hình 4. 3 Minh họa sự hội tụ của thuật toán GA−SDT và GA−no−SDT tại file KroA100 trong bộ dữ
liệu thực 2 qua các thế hệ 76
Hình 4.4 Minh họa hành trình MLP tốt nhất hiện biết trên một số file dữ liệu 106

1
CHƢƠNG 1
TỔNG QUAN VỀ BÀI TOÁN
Chương này giới thiệu bài toán cực tiểu hoá độ trễ (Minimum latency problem - MLP), trình
bày một số hướng tiếp cận để giải bài toán, các nghiên cứu liên quan, phạm vi nghiên cứu, bộ
dữ liệu thực nghiệm, đóng góp và cấu trúc của luận án.
Bài toán thiết kế mạng là một vấn đề được rất nhiều nhà nghiên cứu quan tâm. Việc
lựa chọn một cấu hình tối ưu hoặc thiết kế một mạng tối ưu có rất nhiều ứng dụng trong thực
tiễn như trong giao thông, mạng máy tính, … . Trong bài toán thiết kế mạng, nếu độ trễ của
một nút được hiểu là độ dài đường đi từ nút nguồn đến nút đó, thì mục đích đặt ra là tìm một
hành trình bắt đầu từ nút nguồn đến các nút còn lại trên mạng sao cho tổng độ trễ là cực tiểu.
Xét ví dụ minh họa, xét mạng gồm 6 nút, trong đó khoảng cách giữa các nút được cho bởi ma
trận trọng số C = (c
ij
) sau đây:

2
khoảng cách giữa hai đỉnh thứ i và đỉnh thứ (i + 1) trong hành trình cần được nhân với trọng
số w(i) trước khi chúng được cộng lại. Rõ ràng là bài toán người du lịch (Traveling salesman
problem – TSP) thu được từ bài toán TDTSP khi đặt w(i) = 1; còn nếu đặt w(i) = n – i, ta thu
được bài toán MLP. Chúng ta có thể thấy điểm giống nhau của hai bài toán TSP và MLP đều
là tìm một hành trình tối ưu. Tuy nhiên, Blum et al. [6] chỉ ra rằng bài toán MLP được xem là
khó hơn so với bài toán TSP. 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. Trong bài toán TSP, nếu
hoán đổi vị trí của một vài đỉnh trong hành trình thì sự thay đổi trong hàm mục tiêu chỉ mang
tính cục bộ. Trong khi đó, 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 [6]. Một đặc điểm khác nữa của bài toán MLP đó là chỉ cần một
thay đổi nhỏ trong đồ thị đầu vào, đã có thể dẫn đến sự thay đổi lớn trong hành trình tối ưu
của bài toán [43]. Điều này cho thấy, chúng ta khó có thể thiết kế một thuật toán theo hướng
chia để trị để giải bài toán MLP. Bởi vì các bài toán bộ phận có mối liên hệ với các bài toán
bộ phận khác, nên ta khó có thể tìm được cách chia bài toán cần giải ra thành các bài toán bộ
phận; sau đó, tìm lời giải tối ưu của từng bài toán bộ phận bằng cách trị đệ qui chúng, và cuối
cùng, cần xây dựng được phương pháp hiệu quả để tổng hợp lời giải tối ưu của các bài toán
bộ phận này để thu được lời giải tối ưu cho bài toán đặt ra.
Bài toán MLP có nhiều ứng dụng trong thực tiễn. Cụ thể, trong lý thuyết lập lịch khi
một máy chủ hay một người thợ phải lên kế hoạch phục vụ một tập các yêu cầu sao cho tổng
(trung bình) thời gian chờ đợi của các yêu cầu là cực tiểu [6, 41]. Trong tìm đường đi trên
mạng, bài toán cũng được ứng dụng để tìm hành trình với tổng độ trễ là nhỏ nhất [42]. Trong
bài toán tìm kiếm thông tin, bài toán MLP được ứng dụng để cực tiểu hóa độ trễ của việc tìm
kiếm thông tin trên mạng [42].
Bài toán MLP được chứng minh thuộc lớp bài toán NP-khó trong trường hợp tổng
quát [41] và thậm chí vẫn là NP-khó ngay cả với đồ thị là cây có trọng số [44]. Hơn thế nữa,
ngoại trừ P = NP, một lược đồ xấp xỉ với thời gian đa thức trong trường hợp tổng quát là
không tồn tại [41]. Bên cạnh đó, trong một số trường hợp đặc biệt, bài toán giải được bởi
thuật toán có độ phức tạp thời gian đa thức, được đề cập trong các công trình [6, 14, 31, 49].
1.1 Mô hình toán học của bài toán cực tiểu hóa độ trễ

trễ MLP yêu cầu tìm một hành trình T bắt đầu từ đỉnh xuất phát 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.
Sau đây, chúng ta đưa ra một số ví dụ minh họa về bài toán MLP trên một số dạng đồ
thị đặc biệt:
Ví dụ 1: Xét bài toán MLP trên cây như hình 1.1, giả sử, T là một hành trình xuất phát từ đỉnh
s (s = 1) đi qua các đỉnh còn lại trên cây. Chúng ta định nghĩa lat(v) là độ dài đường đi từ
đỉnh 1 đến đỉnh v trên T và được tính bằng tổng trọng số của các cạnh nằm trên đường đi từ
đỉnh 1 đến đỉnh v trên T. Chúng ta cũng giả sử rằng độ trễ của việc quay ngược trở lại từ đỉnh
hiện tại đến đỉnh trước đó là bằng 0, thì khi đó tổng độ trễ của một hành trình MLP trên cây
được tính như sau:
T = (1, 2, 3, 4, 7, 8, 5, 9, 6) và L(T) =
lat(1) + lat(2)
+
lat(3)
+
lat(4)
+
lat(7)
+
lat(8)
+
lat(5)
+
lat(9) + lat(6)
= 0 + 1 + 2 + 4 + 5 + 7 + 13 + 18 + 25 = 75.
4
Ví dụ 2: Xét bài toán MLP khi mà các đỉnh của đồ thị nằm trên một đường thẳng như Hình
1.2. Chúng ta thấy rằng hành trình MLP có thể duyệt qua duyệt lại các đỉnh của đồ thị với số
lần không xác định. Điều đó cho thấy đặc tính không phẳng của hành trình MLP và đây cũng
là một điểm thể hiện sự khác biệt với hành trình của bài toán TSP.

ij
| i, j=1, 2, …, n}, với c
ij
là khoảng cách giữa hai
đỉnh i và j. Giả sử, T = (v
1
,

v
2
, …, v
n
) là một hành trình xuất phát từ v
1
(đường đi xuất phát từ
v
1
đi qua mỗi đỉnh của đồ thị đúng một lần) trên K
n
. Ký hiệu
P
(v
1
, v
k
) là đoạn đường đi từ v
1

đến v
k

2
( ) ( ).
n
k
k
L T lat v




Giả sử, v
1
là đỉnh cho trước, bài toán MLP yêu cầu tìm hành trình xuất phát từ v
1
với độ trễ là nhỏ
nhất.
5
1.2 Một số hƣớng tiếp cận giải bài toán tối ƣu hóa tổ hợp
Đối với bài toán thuộc lớp NP – khó như bài toán MLP, hiện tại có một số hướng tiếp cận
thường được áp dụng để phát triển thuật toán sau đây:
 Phát triển thuật toán đúng tìm lời giải tối ưu. Các thuật toán theo hướng này có độ
phức tạp bùng nổ tổ hợp trong trường hợp tồi nhất, mặc dù trong thực tế chúng
thường chạy nhanh hơn đánh giá lý thuyết này. Thuật toán quy hoạch động
(Dynamic programming – DP) [7], thuật toán nhánh cận (Branch and bound –
B&B), quy hoạch có ràng buộc (Constraint programming – CP), quy hoạch tuyến
tính dựa trên nhánh cận (Linear programming based branch and bound – LP),
Branchcut, Branchprice, và Branchcutprice [29, 38] thuộc lớp thuật toán này.
 Phát triển thuật toán gần đúng cận tỷ lệ α (α – approximation algoirthm). Ưu điểm
của lớp thuật toán là nó đảm bảo đưa ra lời giải với chi phí không lớn hơn α lần
chi phí của lời giải tối ưu [19, 47, 48].

2
, , A
n
là các tập hữu hạn và P là tính chất cho trên tích Đề–các A
1
× A
2
× ×
A
n
. Mỗi phần tử x  D được gọi là một phương án (hay còn gọi là lời giải chấp nhận được),
còn tập D được gọi là tập các phương án của bài toán.
6
Thuật toán nhánh cận bao gồm hai thủ tục: Phân nhánh (Branching procedure) và tính cận
(Bounding procedure).
Phân nhánh: Thủ tục này thực hiện việc phân hoạch tập các phương án ra thành các
tập con với kích thước càng ngày càng nhỏ cho đến khi thu được phân hoạch tập các phương
án ra thành các tập con một phần tử. Quá trình phân nhánh được thực hiện nhờ thuật toán
quay lui. Thoạt tiên, trên cơ sở tính chất P, ta có thể xác định được tập


1
12
1 1 1 1
, , ,
n
S a a a

những phần tử của tập A
1

1
, , a
k
) = {x

D: x
i
= a
i
, i = 1, , k}.
Ở bước tổng quát của thuật toán quay lui, ta sẽ làm việc với phương án bộ phận (a
1
, a
2
, , a
k
)
và xét các cách tiếp tục phát triển phương án này. Điều đó tương đương với việc phân hoạch
tập D ra thành các tập con nhỏ hơn. Giả sử
1
11
, ,
p
kk
aa

là các khả năng lựa chọn thành phần
thứ k+1 của lời giải, quá trình phân hoạch tập D(a
1
, …, a

i
, i = 1, , k}
( ) D
- Hình 1. 3 Quá trình phân nhánh









1
1
1
()
n
Da


1
1
()

tập D ra thành các tập con nhỏ hơn. Giả sử
1
11
, ,
p
kk
aa

là các khả năng lựa chọn thành phần
thứ k+1 của lời giải, quá trình phân hoạch tập D(a
1
, …, a
k
) được thực hiện như sau: Ta có
phân hoạch:
1 1 1
1
( , , ) ( , , , )
p
i
k k k
i
D a a D a a a



. Thay biểu diễn của D(a
1
, …, a
k


D: x
i
= a
i
, i = 1, , k},
nghĩa là g(a
1
, a
2
, , a
k
) là cận dưới cho giá trị hàm mục tiêu trên tập D(a
1
, a
2
, , a
k
). Vì lẽ
đó, hàm g được gọi là hàm cận dưới và giá trị g(a
1
, a
2
, , a
k
) được gọi là cận dưới của tập
D(a
1
, a
2

 

   

 





 

   

 







 

   


    

 

3. if (a
k


S
k
) then
4. x
k
:= a
k
;
5. if (k == n) then < Cập nhật kỉ lục>
6. else
7. If (g(x
1
, , x
k
) ≤
f
) then Branch(k + 1);
8. end if
9. end for
10. END phương án có thể đã thu được một số phương án của bài toán. Gọi
x

là phương án với giá trị


D(a
1
, a
2
, , a
k
)}. Vì thế
tập D(a
1
, a
2
, , a
k
) chắc chắn không chứa phương án tối ưu và có thể loại bỏ khỏi quá trình
duyệt. Lược đồ của thuật toán nhánh cận được trình bày chi tiết ở Thuật toán 1.1 và 1.2.
1.2.2 Thuật toán di truyền
Lược đồ tổng quát của thuật toán di truyền [13, 32] đòi hỏi xác định phương pháp mã hóa lời
giải và xây dựng các toán tử: ước lượng, lựa chọn, lai ghép và đột biến. Đầu tiên, ta khởi tạo
quần thể của các cá thể ban đầu. Sau đó, trong mỗi bước lặp, các thể cha mẹ được lựa chọn từ
quần thể để thực hiện lai ghép tạo ra các cá thể con cháu. Các cá thể con cháu sẽ được đột
9
Thuật toán 1.3. Lược đồ tổng quát của thuật toán di truyền
1. BEGIN
2. Khởi tạo quần thể ban đầu SP;
3. while (Điều kiện kết thúc chưa thỏa) do
4. (TP, TM) = Lựa chọn từ SP; //TP và TM là cá thể cha và mẹ
5. TC = Lai ghép TP và TM; //TC là cá thể con cháu được lai ghép từ TP và TM
6. TCˊ = Đột biến cá thể con cháu TC; //TCˊ là cá thể sau khi đột biến
7. SP = SP  TCˊ; //Bổ sung cá thể TCˊ vào trong quần thể

;
3. s = s
o
;
*
s
= s
o
;
4. tabulist = Ø; //tabulist là danh sách tabu
5. while (Điều kiện kết thúc chưa thỏa) do
6. M = Ø; //M là tập các bước chuyển ứng viên
7.
s
sN


(là lân cận của s):
8. m = move (s,
);s


9. if (m


tabulist) M = M

{m};
10. if (m


14. Cập nhập tabulist;
15. Tăng cường hóa lời giải;
16. Đa dạng hóa lời giải;
17. end while
18. Đưa ra lời giải tốt nhất;
19. END
10
Thuật toán 1.6. Lược đồ tổng quát của thuật toán lân cận biến đổi
1. BEGIN
2.
*
;T 

3.
//thực hiện lần lượt k thuật toán lận cận

4. for i =1 to k do
5.
()
argmin ( )
i
T N T
T L T





6. if ((L(
'

tại mỗi bước lặp, ta tạo ra một cá thể kiến và cho kiến dò đường dựa trên vết mùi do các cá
thể kiến trước đó để lại trên đường đi. Khi cá thể kiến này di chuyển, thì bản thân nó cũng để
lại vết mùi trên đường đi nó đi qua. Vết mùi này sẽ được cập nhập và bay hơi để các cá thể
kiến theo sau lần theo vết mùi đó. Thuật toán sẽ thực hiện các bước lặp cho đến khi điều kiện
kết thúc được thỏa mãn. Mã giả của thuật toán được trình bày trong Thuật toán 1.4.
1.2.4 Thuật toán Tabu
Từ một lời giải ban đầu, thuật toán tabu [20, 46] lặp đi lặp lại việc tìm kiếm nhằm cải thiện
dần lời giải tốt nhất của bài toán. Tại mỗi bước lặp, thuật toán duyệt trong lân cận của lời giải
11
hiện tại để chọn ra lời giải tốt nhất và lời giải này thay thế cho lời giải hiện tại ở bước lặp kế
tiếp. Mỗi lời giải trong lân cận của lời giải hiện tại được gọi là một lân cận của lời giải hiện
tại. Việc thực hiện tác động lên lời giải hiện tại để biến nó thành một lân cận được gọi là một
bước chuyển (move). Điểm khác biệt căn bản của tìm kiếm tabu so với các thuật toán tìm
kiếm địa phương khác là: Tại mỗi bước lặp, để tránh việc duyệt trở lại những lời giải đã từng
được khảo sát, thuật toán tabu sử dụng một danh sách (được gọi là danh sách tabu) để lưu trữ
một số bước chuyển đã từng được sử dụng. Danh sách tabu sẽ chứa một số bước chuyển vừa
được thực hiện trong một số bước lặp ngay trước đó và các bước chuyển nằm trong danh
sách tabu được gọi là các bước chuyển tabu. Các bước chuyển tabu sẽ bị cấm sử dụng lại khi
nó còn nằm trong danh sách tabu. Mỗi bước chuyển tabu sẽ được cập nhập vào trong danh
sách tabu khi thực hiện bước lặp. Sau đó, các bước chuyển này có thể được loại khỏi danh
sách tabu và tái dụng lại. Mã giả của thuật toán được trình bày trong Thuật toán 1.5.
1.2.5 Thuật toán lân cận biến đổi
Ý tưởng của thuật toán lân cận biến đổi (Variable neighborhood search-VNS) [21, 22, 23,
33] là thực hiện lần lượt từng thuật toán lân cận, hết thuật toán lân cận này đến thuật toán lân
cận khác. Trong quá trình thực hiện thuật toán VNS, ta luôn ghi nhận lời giải tốt nhất (kỉ
lục). Khi thực hiện một thuật toán lân cận, nếu tìm được kỉ lục mới thì ta quay trở lại thực
hiện thuật toán VNS từ đầu. Ngược lại, ta chuyển sang thuật toán lân cận tiếp theo. Quá trình
được tiếp tục cho đến khi thực hiện hết tất cả các thuật toán lân cận mà lời giải tốt nhất không
được cải thiện. Mã giả của thuật toán được trình bày trong Thuật toán 1.6.
1.3 Các nghiên cứu liên quan giải bài toán MLP

ngẫu nhiên và một số file dữ liệu được trích rút từ bộ dữ liệu TSPLIB [51]. Kết quả thực
nghiệm chỉ ra rằng thuật toán của Wu et al. có thể giải bài toán MLP với kích thước lên đến
26 đỉnh. Tuy nhiên, hiệu quả của thuật toán trong các trường hợp có kích thước lớn hơn chưa
được xem xét.
1.3.2 Thuật toán gần đúng cận tỷ lệ
Các thuật toán gần đúng cận tỷ lệ α (α – approximation algoirthm) có ưu điểm là nó đảm bảo
đưa ra lời giải với chi phí không lớn hơn α lần chi phí của lời giải tối ưu.
Hiện nay, có một vài thuật toán gần đúng cận tỷ lệ được đề xuất. Blum et al. [6] đưa
ra một thuật toán với cận tỷ lệ là 144 trong trường hợp metric. Goemans et al. [18] đưa ra cận
tỷ lệ 21.55. Sau đó, Arora et al. [3] đề xuất thuật toán gần đúng với cận tỷ lệ là 17.24. Thuật
toán gần đúng của Archer et al. [1] có cận tỷ lệ 7.18 trong trường hợp metric và 3.01 trong bộ
dữ liệu TSPLIB [51]. Gần đây, K.Chaudhuri et al. [9] đưa ra thuật toán gần đúng với cận tỷ lệ
là 3.59. Cận tỷ lệ này được biết là cận tỷ lệ nhỏ nhất hiện nay cho bài toán MLP.
Hiện tại, trong hướng tiếp cận gần đúng cận tỷ lệ, phần lớn các công trình chỉ ra rằng
chi phí tối ưu của bài toán k-MST được xem như cận dưới cho độ trễ đỉnh thứ k trong hành
trình tối ưu MLP [1, 6, 18]. Blum et al. [6] chỉ ra rằng nếu có thuật toán gần đúng với cận tỷ
13
lệ β cho bài toán k-MST (k = 2, 3, , n), thì ta có thuật toán gần đúng với cận tỷ lệ 8×β cho
bài toán MLP. Sau đó, Goeman et al. [18] giảm cận tỷ lệ bài toán MLP xuống còn 3.59×β.
Nếu sử dụng thuật toán gần đúng có cận tỷ lệ nhỏ nhất là 2 cho bài toán k-MST [15], thì thuật
toán gần đúng cho bài toán MLP của Blum et al. và Goeman et al. có cận tỷ lệ lần lượt là 16
và 7.18. Gần đây, Archer et al. [1] trình bày thuật toán tạo ra các k-MST (k = 2, 3, , n) bằng
việc sử dụng kỹ thuật nới lỏng lagrange thay vì sử dụng thuật toán giải bài toán k-MST như
trong [15]. Tuy không giảm được cận tỷ lệ 7.18 nhưng thời gian chạy thuật toán được giảm
đáng kể. Khác với các cách tiếp cận trên, K.Chaudhuri et al. [9] chỉ ra rằng lời giải tối ưu của
bài toán đường đi ngắn nhất đi qua k đỉnh (ta gọi là bài toán k-troll) là một cận dưới tốt hơn
cho độ trễ đỉnh thứ k trong hành trình tối ưu MLP. Tuy nhiên, bài toán k-troll cũng khó tương
tự như bài toán k-MST, bởi vậy họ đưa ra thuật toán cho bài toán tìm cây khung đi qua k đỉnh
có chi phí bị chặn bởi chi phí tối ưu của bài toán k-troll. Để thu được lời giải cho bài toán
MLP, họ chuyển các cây khung này thành các hành trình đi qua k đỉnh và kết nối các hành

nhất, mặc dù trong thực tế chúng thường chạy nhanh hơn đánh giá lý thuyết này. Tuy vậy,
thuật toán đúng cũng chỉ có thể giải bài toán MLP với kích thước nhỏ. Trong cách tiếp cận
thứ hai, các thuật toán gần đúng với cận tỷ lệ

có ưu điểm lớn là về mặt lý thuyết chúng đảm
bảo đưa ra lời giải có chi phí không vượt quá

lần chi phí của lời giải tối ưu. Cuối cùng, các
thuật toán meta-heuristic là những thuật toán có độ phức tạp tính toán thường là không quá
lớn và khá hiệu quả đối với lớp bài toán NP-khó như bài toán MLP, nhưng chất lượng lời giải
tìm được bởi các thuật toán này chỉ có thể đánh giá thông qua thực nghiệm.
Trong luận án này, chúng tôi nghiên cứu việc phát triển các thuật toán hiệu quả để
giải bài toán cực tiểu hóa độ trễ, là một bài toán tối ưu hóa tổ hợp có nhiều ứng dụng trong
thực tiễn:
 Phát triển thuật toán đúng cho phép giải bài toán với kích thước lớn hơn. Hiện tại,
hầu hết lời giải tối ưu của các bộ dữ liệu được nhiều tác giả sử dụng trong thực
nghiệm xác định hiệu quả của các thuật toán giải bài toán MLP là chưa biết. Điều
này gây khó khăn cho việc đánh giá một cách chính xác hiệu quả của các thuật
toán. Chúng tôi sử dụng các bộ dữ liệu có lời giải tối ưu thu được nhờ thuật toán
đúng để phân tích thêm về hiệu quả của các thuật toán đề xuất và để khảo sát lựa
chọn các tham số trong các thuật toán meta-heuristic.
 Khảo sát thực nghiệm về hiệu quả của các thuật toán gần đúng cận tỷ lệ hiện biết,
là cơ sở để đề xuất thuật toán gần đúng mới với cận tỷ lệ tốt hơn. Theo hướng tiếp
cận thuật toán gần đúng cận tỷ lệ, hiện nay một số thuật toán gần đúng cận tỷ lệ
giải bài toán MLP đã được công bố. Tuy nhiên, hiệu quả của các thuật toán này
15
chỉ được đánh giá trên khía cạnh lý thuyết. Chúng tôi đã tiến hành nghiên cứu
thực nghiệm để đánh giá hiệu quả thực tế của các thuật toán gần đúng. Chúng tôi
tập trung vào phân tích ba khía cạnh chính là cận tỷ lệ, thời gian chạy thực tế và
chất lượng của cận dưới. Nhằm giảm cận tỷ lệ cho thuật toán gần đúng giải bài