Nghiên cứu ứng dụng thuật toán aco (ant colony optimization) tối ưu thời gian và chi phí cho dự án xây dựng

TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 17 
NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN ACO (ANT COLONY OPTIMIZATION) 
TỐI ƯU THỜI GIAN VÀ CHI PHÍ CHO DỰ ÁN XÂY DỰNG 
Phạm Hồng Luân (1), Dương Thành Nhân(2) 
(1) Trường Đại học Bách Khoa, ĐHQG-HCM 
(2) Công ty CP Tài trợ và Phát triển địa ốc R.C 
(Bài nhận ngày 30 tháng 09 năm 2009, hoàn chỉnh sửa chữa ngày 24 tháng 12 năm 2009) 
TÓM TẮT: Bài toán tối ưu thời gian - chi phí là một trong những khía cạnh quan trọng nhất của 
quản lý dự án xây dựng. Để cực đại hóa lợi nhuận, các nhà lập kế hoạch xây dựng phải cố gắng tìm 
cách tối ưu đồng thời thời gian và chi phí. Trong nhiều năm qua, nhiều nghiên cứu đã được thực hiện 
nhằm nghiên cứu mối quan hệ thời gian - chi phí, các kỹ thuật được ứng dụng từ phương pháp tìm kiếm, 
phương pháp toán học cho đến thuật giải di truyền. Trong bài báo này, một thuật toán tối ưu dựa trên 
nền tảng của sự tiến hóa, với tên gọi tối ưu đàn kiến (ACO) được ứng dụng để giải quyết bài toán tối ưu 
đa mục tiêu thời gian - chi phí. Bằng cách kết hợp với phương pháp trọng số thích ứng sửa đổi (MAWA), 
mô hình sẽ tìm ra các lời giải tối ưu. Mô hình ACO-TCO sẽ được pháp triển bằng một chương trình 
máy tính trên nền Visual Basic. Một ví dụ sẽ được phân tích để minh họa khả năng của mô hình cũng 
như so sánh với các phương pháp trước đây. Kết quả chỉ ra rằng phương pháp này có khả năng tìm ra 
những kết quả tốt hơn mà không cần sử dụng quá nhiều đến máy điện toán, từ đó cung cấp một phương 
tiện hữu hiệu để hỗ trợ các nhà lập kế hoạch và quản lý trong việc lựa chọn những quyết định về thời 
gian – chi phí một cách hiệu quả. 
Từ khóa: Ant colony optimization (ACO), genetic algorithm, GA, MAWA, ACO-TCO. 
1. GIỚI THIỆU 
Với sự ra đời của các sáng kiến cũng như 
các kỹ thuật xây dựng hiệu quả, các sáng kiến 
trong quản lý và các phương pháp phân phát, 
thời gian xây dựng đã được cải thiện một cách 
rõ rệt trong vòng vài thập kỷ gần đây. Trên 
quan điểm của chủ đầu tư, một dự án kết thúc 
sớm sẽ giúp giảm bớt khoản nợ về tài chính và 
cho phép họ thu lại nguồn vốn đầu tư sớm hơn. 
Mặt khác, các nhà thầu sẽ tiết kiệm được chi 
phí gián tiếp và giảm thiểu được nguy cơ lạm 
phát cũng như số lượng nhân công nếu thời 
gian của dự án có thể được rút ngắn. Trên cơ sở 
này, các nhà lập kế hoạch và quản lý dự án đều 
cố gắng bảo đảm rằng tất cả các hoạt động xây 
dựng đều phải hoàn thành không những đúng 
thời gian tiến độ mà phải vượt tiến độ đề ra . 
Bài toán tối ưu thời gian – chi phí (time-
cost optimization – TCO) là một trong những 
bài toán quan trọng nhất của việc lập và quản 
lý dự án. Các nhà quản lý dự án phải lựa chọn 
những nguồn tài nguyên thích hợp, bao gồm: 
kích cỡ tổ đội, vật tư thiết bị, máy móc cũng 
như phương pháp và kỹ thuật thi công để thực 
hiện các công tác của dự án. Nói chung, có một 
mối quan hệ tương quan giữa thời gian và chi 
phí để hoàn thành một công tác; chi phí thấp thì 
thời gian thực hiện công tác sẽ kéo dài, và 
ngược lại. Những bài toán loại này thường rất 
khó giải quyết bởi vì chúng không có một đáp 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 18 
án duy nhất. Vì vậy, nhiệm vụ của các nhà 
quản lý dự án là phải xem xét, đánh giá một 
cách kỹ lưỡng nhiều phương pháp khác nhau 
nhằm đạt được một kết quả cân bằng tối ưu 
giữa thời gian và chi phí. 
Các phương pháp để giải quyết bài toán 
TCO hiện tại có thể được chia thành ba nhóm: 
phương pháp tìm kiếm (heuristic methods), 
phương pháp quy hoạch toán học 
(mathematical programming models) và các 
thuật toán tối ưu dựa trên nền tảng của sự tiến 
hóa (evolutionary-based optimization 
algorithms_EOAs). Phương pháp tìm kiếm là 
một kỹ thuật tìm kiếm dựa trên ý kiến chủ quan 
của của người ra quyết định. Các phương pháp 
tìm kiếm tiêu biểu dùng để giải quyết bài toán 
TCO gồm : phương pháp Fondahl (1963), 
phương pháp khung (Prager 1963), phương 
pháp độ dốc chi phí hiệu quả (Siemens 
1971), Phương pháp quy hoạch toán học sử 
dụng các chương trình toán học như quy hoạch 
tuyến tính (linear programming_LP), được giới 
thiệu bởi Kelly (1961), Hendrickson and Au 
(1989) và Pagnoni (1990) để mô hình hóa mối 
quan hệ tuyến tính giữa thời gian – chi phí. 
Ngoài ra, quy hoạch số nguyên (integer 
programming_IP) được giới thiệu bởi Meyer & 
Shaffer (1963) để giải quyết cả mối quan hệ 
tuyến tính và rời rạc giữa thời gian – chi phí. 
Gần đây, Burns cùng các cộng sự (1996) đã 
phát triển một mô hình lai ghép LP/IP nhằm 
thiết lập đáp án chính xác cho bất kỳ khoảng 
thời gian mong muốn nào. 
Cả hai phương pháp tìm kiếm và quy 
hoạch toán học đều có những điểm mạnh cũng 
như nhược điểm riêng trong việc giải quyết bài 
toán TCO. Tuy nhiên, đối với các dự án lớn với 
sơ đồ mạng lớn, thì cả phương pháp tìm kiếm 
cũng như phương pháp quy hoạch toán học đều 
không thể đạt được lời giải tối ưu một cách 
hiệu quả. Với mục tiêu đạt được lời giải tối ưu 
cho bài toán TCO, nhiều nhà nghiên cứu đã bắt 
đầu khám phá khả năng sử dụng các phương 
pháp tiên tiến, như là EOAs. EOAs 
(evolutionary-based optimization algorithms) là 
phương pháp nghiên cứu dựa trên việc mô 
phỏng quá trình tiến hoá của thế giới tự nhiên 
hoặc hành vi xã hội của các loài. Trong số các 
EOAs, GAs (genetic algorithms) - thuật giải di 
truyền - được sử dụng rộng rãi nhất nhằm thu 
được lời giải tối ưu cho các bài toán tối ưu đa 
mục tiêu trong nhiều lĩnh. Chẳng hạn, Feng và 
các cộng sự (1997) đã phát triển một mô hình 
GA mà về cơ bản là sự cải thiện mô hình lai 
ghép được phát minh bởi Liu và các cộng sự 
(1995). Feng và các cộng sự (2000) phát triển 
một mô hình GA cho bài toán cân bằng thời 
gian-chi phí trong xây dựng. Bên cạnh thuật 
giải di truyền, nhiều kỹ thuật EOA khác lấy 
cảm hứng từ nhiều tiến trình khác nhau trong tự 
nhiên cũng đã được phát triển như thuật toán 
memetic (Moscato 1989), tối ưu bầy đàn 
(Kenedy và Eberhart 1995) 
Vào đầu thập niên 90, một thuật toán với 
tên gọi Tối ưu đàn kiến (Ant Colony 
Optimization_ACO) được đề xuất như là một 
phương pháp mới trong việc tìm kiếm lời giải 
tối ưu cho những bài toán tối ưu đa mục tiêu. 
ACO lần tiên được ứng dụng để giải quyết bài 
toán người thương gia TSP (Traveling 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 19 
Salesmen Problem), và gần đây nó đã được mở 
rộng và cải tiến để áp dụng cho nhiều bài toán 
tối ưu khác nhau. 
Bài báo này sẽ đi sâu nghiên cứu và ứng 
dụng thuật toán ACO - là một phương pháp tìm 
kiếm nên cũng là một dạng heuristic - để giải 
quyết bài toán tối ưu đa mục tiêu TCO trong 
một dự án xây dựng. Việc phát triển một 
chương trình máy tính dựa trên mô hình thuật 
toán được nghiên cứu, nhằm kiểm tra kết quả 
dựa trên số liệu của một dự án xây dựng thực tế, 
cũng như so sánh với những phương pháp 
trước đây, cũng sẽ được xem xét trong bài báo 
này. 
2. THUẬT TOÁN ACO 
ACO (Ant Colony Optimization – Tối ưu 
đàn kiến) là một phương pháp nghiên cứu lấy 
cảm hứng từ việc mô phỏng hành vi của đàn 
kiến trong tự nhiên nhằm mục tiêu giải quyết 
các bài toán tối ưu phức tạp. 
Được giới thiệu lần đầu tiên vào năm 1991 
bởi A. Colorni và M. Dorigo, Giải thuật kiến 
đã nhận được sự chú ý rộng lớn nhờ vào khả 
năng tối ưu của nó trong nhiều lĩnh vực khác 
nhau. Khái niệm ACO lấy cảm hứng từ việc 
quan sát hành vi của đàn kiến trong quá trình 
chúng tìm kiếm nguồn thức ăn. Người ta đã 
khám phá ra rằng, đàn kiến luôn tìm được 
đường đi ngắn nhất từ tổ của chúng đến nguồn 
thức ăn. Phương tiện truyền đạt tín hiệu được 
kiến sử dụng để thông báo cho những con khác 
trong việc tìm đường đi hiệu quả nhất chính là 
mùi của chúng (pheromone). Kiến để lại vệt 
mùi trên mặt đất khi chúng di chuyển với mục 
đích đánh dấu đường đi cho các con theo sau. 
Vệt mùi này sẽ bay hơi dần và mất đi theo thời 
gian, nhưng nó cũng có thể được củng cố nếu 
những con kiến khác tiếp tục đi trên con đường 
đó lần nữa. Dần dần, các con kiến theo sau sẽ 
lựa chọn đường đi với lượng mùi dày đặc hơn, 
và chúng sẽ làm gia tăng hơn nữa nồng độ mùi 
trên những đường đi được yêu thích hơn. Các 
đường đi với nồng độ mùi ít hơn rốt cuộc sẽ bị 
loại bỏ và cuối cùng, tất cả đàn kiến sẽ cùng 
kéo về một đường đi mà có khuynh hướng trở 
thành đường đi ngắn nhất từ tổ đến nguồn thức 
ăn của chúng (Dorigo và Gambardella 1996). 
Để bắt chước hành vi của các con kiến 
thực, Dorigo xây dựng các con kiến nhân tạo 
(artificial ants) cũng có đặc trưng sản sinh ra 
vết mùi để lại trên đường đi và khả năng lần vết 
theo nồng độ mùi để lựa chọn con đường có 
nồng độ mùi cao hơn để đi. Gắn với mỗi cạnh 
(i,j) nồng độ vết mùi τij và thông số heuristic 
ηij trên cạnh đó. 
Ban đầu, nồng độ mùi trên mỗi cạnh (i,j) 
được khởi tạo bằng một hằng số c, hoặc được 
xác định theo công thức : 
τij = τ0 = nnC
m
, ∀(i,j) (1) 
Trong đó : 
ƒ τij: nồng độ vết mùi trên cạnh i,j 
ƒ m : số lượng kiến 
ƒ Cnn: chiều dài hành trình cho bởi 
phương pháp tìm kiếm gần nhất. 
Tại đỉnh i, một con kiến k sẽ chọn đỉnh j 
chưa được đi qua trong tập láng giềng của i 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 20 
theo một quy luật phân bố xác suất được xác 
định theo công thức sau: 
k
ijp = ∑ ∈ βα
βα
ητ
ητ
][][
][][
ililNl
ijij
k
i
, j∈ kiN (2) 
Trong đó : 
ƒ kijp : xác suất con kiến k lựa chọn cạnh i,j 
ƒ α : hệ số điều chỉnh ảnh hưởng của τij 
ƒ ijη : thông tin heuristic giúp đánh giá 
chính xác sự lựa chọn của con kiến khi quyết 
định đi từ đỉnh i qua đỉnh j ; được xác định theo 
công thức : 
ijη = 1/dij (3) 
ƒ dij : khoảng cách giữa đỉnh i và đỉnh j 
ƒ β : hệ số điều chỉnh ảnh hưởng của ηij 
ƒ kiN : tập các đỉnh láng giềng của 
i mà con kiến k chưa đi qua 
Quy luật này mô phỏng hoạt động của một 
vòng quay xổ số nên được gọi là kỹ thuật bánh 
xe xổ số. 
Cho một hằng số 0≤q0≤1 và một số 0≤q≤1 
được tạo ra một cách ngẫu nhiên. Con kiến k ở 
đỉnh i sẽ lựa chọn đỉnh j kế tiếp để đi theo một 
quy tắc lựa chọn được mô tả bởi công thức 
sau : 
( ) ( )[ ]


 ×= ∈
J
j ililNl ki
βα ητmaxarg
 (4) 
Trong đó : 
ƒ q : giá trị được lựa chọn một cách ngẫu 
nhiên với một xác suất không thay đổi trong 
khoảng [0,1]. 
ƒ 0≤qo≤1: là một hằng số cho trước. 
ƒ J : là một biến số ngẫu nhiên được lựa 
chọn theo sự phân bố xác suất cho bởi quy luật 
phân bố xác suất theo công thức (2). 
Sau khi cũng như trong quá trình các con 
kiến tìm đường đi, các vết mùi (τi,j) trên mỗi 
cạnh sẽ được cập nhật lại, vì chúng bị biến đổi 
do quá trình bay hơi cũng như quá trình tích 
lũy mùi khi các con kiến đi trên cạnh đó. 
Sau mỗi vòng lặp, vết mùi trên mỗi cạnh 
được cập nhật lại theo công thức sau: 
τij(t+1) = (1-ρ)×τij(t) + ∑
=
∆
m
k
k
ij t
1
)(τ ∀(i,j) (5) 
Trong đó : 
ƒ 0<ρ≤1 : tỷ lệ bay hơi của vệt mùi. 
ƒ )(tkijτ∆ : lượng mùi mà con kiến k để 
lại trên cạnh ij, được xác định như sau : 



=∆
0
)(, kf
Q
k
jiτ (6) 
ƒ Q : là một hằng số. 
ƒ f(k) : giá trị mục tiêu trong mỗi vòng lặp. 
3. TỐI ƯU ĐA MỤC TIÊU (MULTI-
OBJECTIVE OPTIMIZATION) 
Bài toán TCO là một bài toán tối ưu đa 
mục tiêu. Không giống như những bài toán tối 
ưu đơn mục tiêu mà lời giải tối ưu tồn tại một 
Nếu q≤q0 
Ngược 
lại 
Nếu con kiến k đi 
qua cạnh (i,j) 
Ngược lại 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 21 
cách rõ ràng, tối ưu đa mục tiêu thích hợp đối 
với những bài toán có hơn một mục tiêu đối lập. 
Bài toán TCO được mô tả bởi một chuỗi lời 
giải mà ta không dễ so sánh, và rất khó nếu 
không muốn nói là không thể thu được lời giải 
tốt nhất một cách rõ ràng cho tất cả các mục 
tiêu. Mỗi một hàm mục tiêu có thể đạt được 
điều kiện tối ưu của nó tại những điểm khác 
nhau nhờ vào sự thiếu hụt tiêu chuẩn thống 
nhất về sự tối ưu. Do đó, các nhà lập kế hoạch 
và quản lý phải áp dụng sự đánh giá về mặt kỹ 
thuật của họ trong việc lựa chọn đáp án tốt nhất 
thu được từ một bộ các đáp án tối ưu dọc theo 
biên Pareto (Zheng và các cộng sự 2005). 
Được trình bày bởi Vilfredo Pareto vào thế 
kỷ 19, khái niệm tối ưu Pareto là một công cụ 
được chấp nhận trong việc so sánh giữa hai đáp 
án trong bài toán tối ưu đa mục tiêu mà không 
có tiêu chuẩn thống nhất về sự tối ưu. Các đáp 
án như thế đòi hỏi phải hy sinh ít nhất một mục 
tiêu khác khi muốn cải thiện bất kỳ một mục 
tiêu nào (Gen và Cheng 2000). Một đáp án (x*) 
không bị trội bởi một đáp án (x) khác nếu nó có 
ít nhất một tiêu chuẩn tốt hơn khi so sánh với 
(x). Vùng được định nghĩa bởi tối ưu Pareto 
được gọi là biên Pareto (Pareto front), và mục 
tiêu của tối ưu đa mục tiêu là thiết lập toàn bộ 
biên Pareto cho bài toán thay vì chỉ có một đáp 
án đơn tốt nhất. 
Để đánh giá sự phù hợp của lời giải thu 
được từ mô hình, một hàm thích nghi (fitness 
function) xem xét đến yếu tố thời gian và chi 
phí sẽ được áp dụng cho bài toán tối ưu đa mục 
tiêu TCO. 
Phương pháp được sử dụng có tên gọi là 
phương pháp trọng số thích ứng sửa đổi 
(Modified Adaptive Weight Approach – 
MAWA), được Zheng và các cộng sự (2004) 
phát triển từ phương pháp trọng số thích ứng 
(Adaptive Weight Approach – AWA) đề xuất 
bởi Gen và Cheng (2000), và được sử dụng 
trong việc áp dụng thuật giải di truyền cho bài 
toán TCO. 
Cụ thể, trong phương pháp MAWA, các 
trọng số thích ứng được tính toán theo bốn điều 
kiện sau: 
(1) Nếu minmax tt ZZ ≠ và minmax cc ZZ ≠ thì : 
minmax
min
cc
c
c ZZ
Z
−=ν (7) 
minmax
min
tt
t
t ZZ
Z
−=ν (8) 
ct ννν += (9) 
wt = ν
ν t (10) 
wc = ν
ν c (11) 
(2) Nếu minmax tt ZZ = và minmax cc ZZ = thì : 
wt =wc = 0.5 (12) 
(3) Nếu minmax tt ZZ = và minmax cc ZZ ≠ thì : 
wt = 0.9 (13) 
wc = 0.1 (14) 
(4) Nếu minmax tt ZZ ≠ và minmax cc ZZ = thì : 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 22 
wt = 0.1 (15) 
wc = 0.9 (16) 
Trong đó : 
ƒ maxtZ : giá trị cực đại theo mục tiêu thời 
gian trong tập hợp các đáp án Pareto thu được 
từ vòng lặp của thuật toán ACO. 
ƒ mintZ : giá trị cực tiểu theo mục tiêu thời 
gian trong tập hợp các đáp án Pareto thu được 
từ vòng lặp của thuật toán ACO. 
ƒ maxcZ : giá trị cực đại theo mục tiêu chi 
phí trong tập hợp các đáp án Pareto thu được từ 
vòng lặp của thuật toán ACO. 
ƒ mincZ : giá trị cực tiểu theo mục tiêu chi 
phí trong tập hợp các đáp án Pareto thu được từ 
vòng lặp của thuật toán ACO. 
ƒ tν : giá trị theo tiêu chuẩn về thời gian 
ƒ cν : giá trị theo tiêu chuẩn về chi phí 
ƒ ν : giá trị cho dự án 
ƒ wc : trọng số thích ứng theo tiêu 
chuẩn về chi phí 
ƒ wt : trọng số thích ứng theo tiêu chuẩn 
về thời gian 
Sau khi tính được các trọng số wt , wc tính 
hàm kết hợp thời gian & chi phí theo công 
thức : 
 γ
γ
γ
γ
+−
+−×++−
+−×= minmax
max
minmax
max
)(
cc
cc
c
tt
tt
t zz
zzw
zz
zzwxf (17) 
Trong đó : 
ƒ γ : hằng số dương ngẫu nhiên nằm trong khoảng [0,1]. 
4. MÔ HÌNH ACO CHO BÀI TOÁN TCO 
4.1 Mô tả bài toán 
Bài toán tối ư ... trên thuật toán ACO. 
Sự biểu diễn bài toán TCO dưới dạng TSP 
được mô tả trong hình (1) 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 23 
Hình 1. Biểu diễn bài toán TCO dưới dạng TSP 
Mỗi nút trong hình (1) biểu thị một phương 
án lựa chọn để thực hiện công tác. Ví dụ, nút 
thứ j trên cột i (i=0,1,2,) cho biết rằng công 
tác i thực hiện theo phương án lựa chọn j. Cột 0 
là một công tác ảo đại diện cho điểm bắt đầu 
của dự án. Các cạnh trên hình (1) được mô tả 
bởi một ma trận với 3 yếu tố, ví dụ (i, j1, j2) 
miêu tả công tác thứ i thực hiện theo lựa chọn 
j1, trong khi công tác i+1 thực hiện theo lựa 
chọn j2. Mỗi đường đi từ cột 0 đến cột num-act 
trình bày một phương án thực hiện của dự án. 
Trên thực tế, việc giải quyết bài toán TCO là 
tập trung tìm kiếm một đường đi có thể làm 
cho cực tiểu tổng thời gian cũng như tổng chi 
phí của dự án. 
Tổng thời gian và tổng chi phí của dự án 
có thể được tính toán lần lượt theo các công 
thức (18) và (19) sau đây : 
T = max 

∑
∈ kLi
k
i
k
i xt
)()( (18) 
Trong đó : 
ƒ )(kit : thời gian thực hiện công tác thứ i 
khi thực hiện theo lựa chọn thứ k. 
ƒ )(kix : biến số của công tác thứ i khi 
thực hiện theo lựa chọn thứ k. Nếu )(kix = 1 thì 
công tác i thực hiện theo lựa chọn thứ k ; và 
ngược lại nếu )(kix = 0. 
ƒ Tổng của các giá trị biến số của tất cả 
các lựa chọn phải bằng 1. 
ƒ Lk : chuỗi công tác trên đường 
đi thứ k ; Lk = {i1k, i2k, , ink} 
ƒ ijk : số của công tác j trên đường 
đi thứ k 
ƒ L : tập hợp tất cả các đường đi 
của sơ đồ mạng; L={Lkk=1,2,m} 
ƒ m : số của các đường đi trong 
sơ đồ mạng. 
1
Công tác i+1 
1 1 1
2 2 2 2
k1 ki ki+1 kn 
.
.
.
.
.
.
.
.
.
Công tác 1 Công tác num-act Công tác i 
1
Công tác 0 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 24 
C = ∑
∈Ni
k
i
k
i xdc
)()( + )(kiicT × (19) 
Trong đó : 
ƒ )(kidc : chi phí trực tiếp của công tác 
thứ i khi thực hiện theo lựa chọn thứ k, bằng 
với số lượng của các công tác nhân với đơn giá 
của chúng. 
ƒ )(kiic : chi phí gián tiếp của công tác 
thứ i khi thực hiện theo lựa chọn thứ k, có thể 
tính toán bởi các chuyên gia bằng cách ước 
lượng hoặc thu được từ việc chia chi phí gián 
tiếp của ngân sách theo tổng thời gian của hợp 
đồng. 
ƒ N : tập hợp các công tác trong sơ đồ 
mạng. 
4.2 Mô hình ACO-TCO 
Mô hình ACO-TCO được mô tả gồm các 
bước chính như sau : 
™ Bước 1 : Khởi tạo các đáp án ban đầu 
Trước tiên, tất cả các con kiến nhân tạo 
được đặt ở nút khởi đầu. Tiếp theo, tạo ra một 
cách ngẫu nhiên một đường đi từ nút khởi đầu 
đến nút kết thúc cho mỗi con kiến. Điều này 
có nghĩa là mỗi con kiến sẽ chọn lựa một cách 
ngẫu nhiên một phương án thực hiện cho mỗi 
công tác để tạo ra một đáp án khả thi cho bài 
toán TCO. 
™ Bước 2 : Tính toán tổng thời gian và 
chi phí của dự án 
Tính toán tổng thời gian hoàn thành và 
tổng chi phí dự án cho mỗi đường đi được tạo 
ra bởi mỗi con kiến theo các công thức (18) và 
(19). 
™ Bước 3 : Thiết lập vùng đáp án 
(solution pool) và tìm các đáp án tối ưu 
Pareto, đặt tên là E 
Mục đích của việc thiết lập vùng đáp án là 
làm giảm việc tính toán lặp lại một cách không 
cần thiết trong suốt quá trình chạy thuật toán. 
Khi tạo ra một đáp án mới, trước tiên sẽ tìm 
kiếm trong vùng đáp án. Nếu đáp án này đã 
xuất hiện trong vùng đáp án, thì loại bỏ nó, nếu 
không thì tính toán giá trị đó theo các công 
thức (18) và (19). Phù hợp với định nghĩa các 
đáp án tối ưu của Pareto, xóa đi các đáp án 
không trội từ vùng đáp án, phần còn lại sẽ tạo 
thành các đáp án tối ưu Pareto E. 
™ Bước 4 : Phân phối các trọng số cho 
mục tiêu thời gian và chi phí 
Tìm các giá trị maxtZ ,
min
tZ ,
max
cZ ,
min
cZ 
trong E, sau đó phân phối các trọng số theo 
mục tiêu thời gian và chi phí dựa vào các công 
thức từ (7) đến (16). 
™ Bước 5 : Tính toán giá trị kết hợp của 
mục tiêu thời gian và chi phí 
Trong quá trình chuyển đổi hai mục tiêu 
thời gian và chi phí thành đơn mục tiêu dưới 
dạng trọng số, ta sẽ thu được giá trị kết hợp của 
mục tiêu thời gian và chi phí, giá trị này được 
sử dụng để sửa đổi cường độ mùi trên đường đi. 
Giá trị kết hợp của mục tiêu thời gian và chi 
phí được tính theo công thức (17). 
™ Bước 6 : Tính toán giá trị cập nhật của 
vệt mùi trên mỗi đường đi sau một vòng lặp 
Sau mỗi vòng lặp, giá trị cập nhật của vệt 
mùi trên mỗi cạnh (i,j1,j2) được tính toán theo 
công thức sau : 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 25 
∑
=
∆=∆
antnum
k
k
jjijji
_
1
,,,, 2121
ττ (20) 
Trong đó : 
ƒ num_ant : tổng số lượng kiến 
ƒ 
21,, jji
τ∆ : giá trị cập nhật của vệt mùi 
trên cạnh (i,j1,j2) sau một vòng lặp 
ƒ k jji 21,,τ∆ : giá trị cập nhật của vệt mùi 
mà con kiến thứ k để lại trên cạnh (i,j1,j2), được 
xác định như sau : 



=∆
0
)(21 ,, kf
Q
k
jjiτ ( 21) 
ƒ Q : là một hằng số, đặc trưng cho lượng 
mùi mà một con kiến để lại trên đường đi. 
ƒ f(k) : giá trị kết hợp của mục tiêu thời 
gian và chi phí của đáp án thứ k, thu được từ 
công thức (17) 
™ Bước 7 : Cập nhật vệt mùi trên mỗi 
cạnh 
Cuối mỗi vòng lặp, cường độ của vệt mùi 
trên mỗi cạnh được cập nhật lại theo quy tắc 
sau: 
212121 ,,,,,,
)(.)1( jjijjijji ncnc ττρτ ∆+=+∆ (22) 
Trong đó : 
ƒ )(
21,,
ncjjiτ∆ : vệt mùi trên cạnh 
(i,j1,j2) sau vòng lặp nc 
ƒ )1(
21,,
+∆ ncjjiτ : vệt mùi trên cạnh 
(i,j1,j2) sau vòng lặp nc+1 
ƒ ρ ∈[0,1] : là một hằng số, đặc trưng 
cho tỷ lệ tồn tại của vệt mùi trước đó ; như vậy 
1-ρ đặc trưng cho sự bay hơi của vệt mùi. 
™ Bước 8 : Tính toán xác suất lựa chọn 
đường đi trên mỗi cạnh của các con kiến 
Kiến lựa chọn đường đi dựa trên cường độ 
mùi và tầm nhìn của mỗi cạnh. Do đó, xác suất 
lựa chọn cho mỗi cạnh được tính theo công 
thức sau : 
k
jjip 21 ,, = ∑
∈ )(
,,,,
,,,,
].[][
].[][
11
2121
iJu
ujiuji
jjijji
k
βα
βα
ητ
ητ
, nếu j∈Jk(i) (23) 
Ngược lại, k jjip 21 ,, = 0 
Trong đó : 
ƒ k jjip 21 ,, : xác suất để con kiến k lựa 
chọn cạnh (i,j1,j2) để đi 
ƒ α : thông số điều chỉnh ảnh hưởng của 
vệt mùi 
21,, jji
τ∆ 
ƒ β: thông số điều chỉnh ảnh hưởng của 
21 ,, jji
η 
ƒ Jk(i): tập hợp các nút mà con kiến k ở 
nút i chưa đi qua 
ƒ 
21 ,, jji
τ : nồng độ của vệt mùi trên cạnh 
(i,j1,j2) 
Nếu con kiến k đi 
qua cạnh (i,j1,j2) 
Ngược lại 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 26 
ƒ 
21 ,, jji
η : thông tin heuristic (hay còn gọi 
là tầm nhìn) giúp đánh giá chính xác sự lựa 
chọn của con kiến khi quyết định đi trên cạnh 
(i,j1,j2), tượng trưng cho thông tin cục bộ được 
xem xét trong quá trình ; được xác định theo 
công thức : 
 rtt
rttw
rdcdc
rdcdcw
ii
k
ii
t
ii
k
ii
cjji +−
+−×++−
+−×=
++
++
++
++
min
1
max
1
)(
1
max
1
min
1
max
1
)(
1
max
1
,, 21
η (24) 
Với : 
ƒ max1+idc : giá trị cực đại chi phí trực tiếp 
của công tác i+1 theo những lựa chọn khác 
nhau. 
ƒ min1+idc : giá trị cực tiểu chi phí trực tiếp 
của công tác i+1 theo những lựa chọn khác 
nhau. 
ƒ max1+it : giá trị cực đại về thời gian thực 
hiện công tác i+1 theo những lựa chọn khác 
nhau. 
ƒ min1+it : giá trị cực tiểu về thời gian thực 
hiện công tác i+1 theo những lựa chọn khác 
nhau. 
ƒ )( 1kidc + : chi phí trực tiếp của công tác i+1 
khi thực hiện theo lựa chọn thứ k 
ƒ )( 1kit + : thời gian thực hiện của công tác 
i+1 khi thực hiện theo lựa chọn thứ k 
™ Bước 9 : Lựa chọn đường đi cho mỗi 
con kiến 
Để lựa chọn thực hiện một công tác, con 
kiến sẽ sử dụng thông tin heuristic biểu thị bởi 
21 ,, jji
η cũng như là thông tin về vệt mùi biểu 
thị bởi 
21 ,, jji
τ∆ . Quy tắc lựa chọn được mô tả 
bởi công thức sau đây : 
( ) ( )[ ]


 ×= ∈
J
j ujiujiiJu k
βα ητ ,,,,)( 11maxarg (25) 
Trong đó : 
ƒ q : giá trị được lựa chọn một cách ngẫu 
nhiên với một xác suất không thay đổi trong 
khoảng [0,1]. 
ƒ 0≤qo≤1: là một tham số cho trước. 
ƒ J : là một biến số ngẫu nhiên được lựa 
chọn theo sự phân bố xác suất cho bởi công 
thức (23). 
™ Bước 10 : 
Thêm đáp án mới từ quá trình vào vùng 
đáp án, và cập nhật các đáp án tối ưu Pareto E. 
Lặp lại quá trình từ Bước 4 đến Bước 10 cho 
đến khi điều kiện kết thúc (phương trình (7), 
(16), (17), (20), (22), (23), (24), (25) ) được 
thỏa mãn. 
5. VÍ DỤ MINH HỌA 
Để minh họa cho tính hiệu quả của mô 
hình đề xuất, một chương trình máy tính ứng 
dụng các bước của mô hình trên đã được thực 
hiện. Chương trình được viết bằng ngôn ngữ 
lập trình Visual Basic 6.0. Việc thực hiện mô 
hình nhằm cố gắng tạo ra một chương trình 
thân thiện và dễ sử dụng. 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 27 
Để chứng minh tính chính xác của mô hình 
dựa trên thuật toán đã nghiên cứu, một ví dụ 
được xem xét giải quyết bằng chương trình này. 
Ví dụ này được trích từ tài liệu [11]. Ví dụ 
này được giới thiệu lần đầu tiên bởi Feng và 
các cộng sự (1997) và sau đó được giải lại bởi 
Zheng và các cộng sự (2004) bằng phương 
pháp GA. 
Dự án bao gồm 07 công tác, với quan hệ 
giữa các công tác, các phương án thực hiện 
cùng với thời gian và chi phí trực tiếp tương 
ứng cho từng phương án được cho trong bảng 
(1) sau: 
Bảng 1. Các thông số của dự án 
Công tác 
(Task) 
Công tác trước 
(Predecessor) 
Phương án 
(Options) 
Thời gian 
(Duration) 
Chi phí trực tiếp 
(Direct cost) 
1 – 
1 
2 
3 
14 
20 
24 
23000 
18000 
12000 
2 1 
1 
2 
3 
4 
5 
15 
18 
20 
23 
25 
3000 
2400 
1800 
1500 
1000 
3 1 
1 
2 
3 
15 
22 
33 
4500 
4000 
3200 
4 1 
1 
2 
3 
12 
16 
20 
45000 
35000 
30000 
5 2,3 
1 
2 
3 
4 
22 
24 
28 
30 
20000 
17500 
15000 
10000 
6 4 
1 
2 
3 
14 
18 
24 
40000 
32000 
18000 
7 5,6 
1 
2 
3 
9 
15 
18 
30000 
24000 
22000 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 28 
Trong đó, thời gian có đơn vị là ngày còn 
chi phí trực tiếp có đơn vị là ($). 
Ngoài ra, chi phí gián tiếp của dự án được 
cho là 1500$ / ngày. 
Ta giải bài toán với các thông số của thuật 
toán ACO nhập vào chương trình như sau : 
Bảng 2 Lựa chọn các thông số cho thuật toán ACO 
Thông số (Parameters) Giá trị (Value) 
Số lượng kiến k 40 
Số vòng lặp 50 
Hệ số α 1 
Hệ số β 2 
Thông số bay hơi ρ 0.9 
q0 0.9 
Q 1 
Nồng độ mùi ban đầu τ0 0 
Bảng (3) trình bày so sánh kết quả thu 
được từ chương trình ACO-TCO với kết quả 
thu được của phương pháp GA trong tài liệu 
[11]. 
Bảng 3 So sánh kết quả giữa ACO và GA 
GA-based TCO model ACO-TCO model 
STT 
Time (day) Cost($) Time (day) Cost($) 
1 73 251,500 62 233,000 
2 84 251,000 67 224,000 
3 66 236,500 63 225,500 
4 - - 60 233,500 
Từ kết quả so sánh, ta thấy lời giải thu 
được từ mô hình ACO-TCO là tốt hơn so với 
kết quả thu được từ [11], và có thể nói ACO-
TCO đã lựa chọn được những phương án thực 
hiện hợp lý cho bài toán. 
6. KẾT LUẬN 
Trong bài báo này, một thuật toán tối ưu 
được biết đến với tên gọi tối ưu đàn kiến ACO 
đã được sử dụng để thiết lập nên mô hình 
ACO-TCO, từ đó có thể tối ưu đồng thời tổng 
thời gian và tổng chi phí của dự án. Bằng cách 
sử dụng phương pháp trọng số thích ứng sửa 
đổi MAWA để kết hợp hai mục tiêu rời rạc thời 
gian và chi phí thành một mục tiêu, mô hình đề 
xuất đã tìm ra các tập hợp lời giải tốt nhất cho 
bài toán tối ưu thời gian – chi phí TCO. Lời 
giải cung cấp cho các nhà lập kế hoạch và quản 
TẠP CHÍ PHÁT TRIỂN KH&CN, TẬP 13, SỐ Q1 - 2010 
Trang 29 
lý dự án một công cụ hữu hiệu để có thể rút 
ngắn được tổng tiến độ cũng như tiết kiệm 
được một khoảng chi phí đáng kể cho dự án. 
STUDY AND APPLY ACO ALGORITHM IN TIME-COST OPTIMIZATION OF 
CONSTRUCTION PROJECT 
Pham Hong Luan(1), Duong Thanh Nhan(2) 
(1) University of Technology, VNU-HCM 
(2) Real-estate and Finance Development Joint-stock Company 
ABSTRACT: Time-cost optimization problem is one of the most important aspects of 
construction project management. In order to maximize the return, construction planners would strive 
to optimize the project duration and cost concurrently. Over the years, many researches have been 
conducted to model the time-cost relationships; the modeling techniques range from the heuristic 
method and mathematical approach to genetic algorithm. In this paper, an evolutionary-based 
optimization algorithm known as ant colony optimization (ACO) is applied to solve the multi-objective 
time-cost problem. By incorporating with the modified adaptive weight approach (MAWA), the 
proposed model will find out the most feasible solutions. The concept of the ACO-TCO model is 
developed by a computer program in the Visual Basic platforms. An example was analyzed to illustrate 
the capabilities of the proposed model and to compare against GA-based TCO model. The results 
indicate that ant colony system approach is able to generate better solutions without making the most of 
computational resources which can provide a useful means to support construction planners and 
managers in efficiently making better time-cost decisions. 
Key words: Ant colony optimization (ACO), genetic algorithm, GA, MAWA, ACO-TCO 
TÀI LIỆU THAM KHẢO 
[1]. Alaya, I., Solnon, C. and Ghédira, K. 
Ant Colony Optimization for Multi-
objective Optimization Problems. IEEE 
Computer Society, pp. 450-457, (2007). 
[2]. Angus, D. J. Niching Ant Colony 
Optimisation. Ph.D. thesis, Swinburne 
University of Technology, Melburne, 
Australia, (2008). 
[3]. Dorigo, M. and Di Caro, G. Ant Colony 
Optimization: A New Meta-Heuristic. 
IEEE Press, pp. 1470-1477, (1999). 
[4]. Dorigo, M., Di Caro, G. and 
Gambardella, L. Ant Algorithms for 
Discrete Optimization. Artificial Life 
Journal, pp. 137-172, (1999). 
[5]. Dorigo, M. and Gambardella, L. Ant 
colonies for the traveling salesman 
problem. BioSystems, 43, pp. 73–81, 
(1997) 
[6]. Dorigo, M. and Gambardella, L., Ant 
Colony System: A Cooperative Learning 
Approach to the Traveling Salesman 
Problem, IEEE Transactions on 
Evolutionary Computation, 1, pp. 53–66, 
(1997) 
[7]. Dorigo, M., Maniezzo, V. and Colorni, 
A. , The Ant Systems: Optimization by a 
colony of cooperating agents, IEEE 
Science & Technology Development, Vol 13, No.Q1- 2010 
Trang 30 
Transactions on Systems, Man and 
Cybernetics, Part B, 26(1):53–66, 
(1996) 
[8]. Dorigo, M. and Stützle, T. , The Ant 
Colony Optimization Metaheuristic: 
Algorithms, Applications and Advances. 
Technical Report, IRIDIA, (2000). 
[9]. Dorigo, M. and Stützle, T., Ant Colony 
Optimization, The MIT Press, 
Cambridge, MA,(2004) 
[10]. Stützle, T. and Hoos, H., MAX-MIN Ant 
System, Future Generation Computer 
Systems, 16(8), 889-914, (2000) 
[11]. Zheng, D. X. M., Ng, S. T. and 
Kumaraswamy, M. M., Applying a 
Genetic Algorithm-Based Multiobjective 
Approach for Time-Cost Optimization, 
Journal of Construction Engineering 
and Management, 130(2), pp. 168-176, 
(2004).