497
MÔ HÌNH QUI HOẠCH TUYẾN TÍNH
CHO BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT CÓ RÀNG BUỘC
Bùi Thanh Khiết 1
1. Ban Đề án Chuyển đổi số, Trường Đại học Thủ Dầu Một
TÓM TẮT
Bài toán đường đi ngắn nhất được nghiên cứu và áp dụng rộng rãi từ khi nó được ra đời.
Cho tới nay có nhiều biến thể từ bài toán đường đi ngắn nhất gốc, đa phần đường đi ngắn nhất
sẽ có thêm nhiều ràng buộc làm cho bài toán trở nên phức tạp. Để giải quyết bài toán đường
đi ngắn nhất có ràng buộc đã có nhiều đề xuất thuật toán để giải quyết nhưng đa phần đều
dành riêng cho từng ràng buộc cụ thể. Trong bài báo này, chúng tôi trình bày phương pháp mô
hình hóa bài toán đường đi ngắn nhất có ràng buộc dựa trên mô hình qui hoạch tuyến tính.
Theo đó, việc thêm ràng buộc cho bài toán sẽ đơn giản và linh hoạt có thể đáp ứng việc tìm
đường đi ngắn nhất thõa các ràng buộc như bắt buộc đi qua một số đỉnh trong đồ thị hoặc bắt
buộc không đi qua một số đỉnh trong đồ thị hoặc ràng buộc đường đi ngắn nhất bao gồm/không
bao gồm một đường con cho trước. Chúng tôi đã cài đặt thực nghiệm trên công cụ nguồn mở
LP Solve IDE, kết quả cho thấy các ràng buộc cho bài toán được xây dựng tùy biến để tìm
nghiệm của bài toán.
Từ khoá: đường đi ngắn nhất, quy hoạch tuyến tính.
1. GIỚI THIỆU
Bài toán đường đi ngắn nhất (shortest path problem – viết tắt SPP) từ một đỉnh đến tất cả
các đỉnh là một trong số những bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thực
tế. Giải quyết bài toán này giúp chúng ta tìm kiếm phương án tiết kiệm nhất về chi phí, thời
gian, quãng đường có thể áp dụng trong giao thông, lập lịch thi công, … Để giải quyết bài toán
này nhà khoa học máy tính người Hà Lan Edsger Dijkstra đã đề xuất thuật toán Dijkstra[1].
Thuật toán có độ phức tạp là O(n2). Tuy nhiên trong thực tế, bài toán đường đi ngắn nhất lại
phát sinh thêm nhiều nhu cầu từ người dùng, họ cần nhiều lựa chọn hơn cho đường đi. Đã có
nhiều nghiên cứu mở rộng bài toán SPP gốc, các biến thể của bài toán SPP gốc đa số được mở
rộng bằng cách thêm vào ràng buộc (gọi tắt là cSPP) [2]. Ví dụ trên đường đi cần phải bao gồm
có một số nút được chỉ định trước hoặc chỉ định trước số lượng nút [3] hoặc đường đi không
bao gồm những đường bị cấm cho trước [4, 5] hoặc đường đi từ hai đỉnh cho trước phải chứa
tất cả các đỉnh của đồ thi (bài toán phủ đỉnh) – bài toán phủ đỉnh có ý nghĩa trong vấn đề phân
cấp mạng, định tuyến [6, 7]. Bài toán đường đi ngắn nhất có ràng buộc trong trường hợp tổng
quát là bài toán thuộc lớp NP-Hard [8]. Năm 1980, Handler và đồng nghiệp đã đề xuất thuật
toán cho bài toán đường đi có ràng buộc, theo đó thuật toán được phát triển dựa trên Lagrangian
ralaxation để tìm hai tìm đường đi ngắn nhất giữa hai nút trong mạng đồng thời thõa mãn ràng
buộc kiểu Knapsack [9]. Năm 1988, Desrochers và đồng nghiệp đề xuất thuật toán dựa trên gán
nhãn cho tài nguyên và sử dụng luật Dominace cho những nhãn ứng viên [10][11] – được xem
như mở rộng của thuật toán Bellman–Ford. Năm 1996, Jaumard đề xuất mô hình quy hoạch
động cho vấn đề đường đi ngắn nhất ràng buộc tài nguyên hai pha trong đồ thị phi chu trình
498
[12]. Năm 2007, Santos và đồng nghiệp đề xuất dùng giải pháp k đường đi ngắn nhất để giải
quyết bài toán đường đi ngắn nhất có ràng buộc[13]. Bài toán đường đi ngắn nhất có nhiều hơn
một ràng buộc được diễn tả như bài toán đường đi ngắn nhất có có tài nguyên ràng buộc –
Elementary Shortest Path Problem with Resource Constraints (ESPPRC), Feillet và đồng
nghiệp đề xuất mở rộng thuật toán đánh nhãn truyền thống cho phiên bản đường không phải
đường chính (nonelementary) và được thực nghiệm cho vấn đề định hướng xe với Time
Windows [14]. Năm 2013 Gabrel và đồng nghiệp [15] đã đưa ra mô hình mới cho bài toán
đường đi ngắn nhất theo đó đưa ra tiêu chí đánh giá cho mô hình mới được gọi là bw-robustness
và đưa ra mô hình tối ưu tổng quát cho bài toán tìm đường đi ngắn nhất. Tuy nhiên, nhóm của
Gabrel chỉ tập trung việc đo tính hiểu quả của của các giải thuật giải quyết bài toán nhưng chưa
đưa ra mô hình chi tiết, cách xây dựng ràng buộc phức tạp cho bài toán tìm đường đi ngắn nhất.
Để giải quyết bài toán đường đi ngắn nhất có ràng buộc đã có nhiều đề xuất thuật toán để giải
quyết nhưng đa phần đều dành riêng cho từng ràng buộc cụ thể. Trong bài báo này trình bày
một cách tiếp cận theo mô hình qui hoạch tuyến tính cụ thể là quy hoạch nguyên cho bài toán
tìm đường đi ngắn nhất theo đó có thể thêm ràng buộc một cách tổng quát.
Phần còn lại, mô hình qui hoạch nguyên cho bài toán đường đi ngắn nhất được trình bày
trong phần II. Ràng buộc cho bài toán đường đi ngắn nhất được trình bày trong phần III. Phần
IV trình bày thực nghiệm. Kết luận được trình bày trong phần V.
2. MÔ HÌNH QUI HOẠCH NGUYÊN CHO BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
PHƯƠNG PHÁP NGHIÊN CỨU
Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường
đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Cho
trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trong số có
giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi
đỉnh v' thuộcV sao cho
∑𝑓(𝑝)
𝑝∈𝑃
(1)
là nhỏ nhất trong tất cả các đường nối từ v tới v' . Bài toán đường đi ngắn nhất giữa mọi cặp
đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp
đỉnh v và v' .
Mô hình hóa bài toán đường đi ngắn nhất dưới dang qui hoạch nguyên như sau:
▪ Giả sử cho đồ thị G(V, E, c) là đồ thị có trọng số không âm, trên mỗi cạnh (i,j) gán
một số nguyên không âm c(i, j). Nhãn c(i,j) biểu diễn “chi phí” thực tế qua cạnh này.
▪ Trọng số trên đồ thị của bài toán này sẽ xoay quanh các yếu tố ảnh hưởng như quãng
đường, vận tốc tối đa cho phép xe di chuyển, mật độ xe trong các khung giờ trong ngày, số
lượng đèn đỏ trên đoạn đường cần di chuyển, … Trong khuôn khổ báo cáo này chúng tôi chỉ
quan tâm đến thời gian di chuyển trên đoạn đường là bao nhiều và cần tìm ra đoạn đường có
thời gian di chuyển thấp nhất. Do vậy, chúng tôi biểu diễn trọng số thời gian cho cạnh của đồ
thị theo công thức sau:
𝑐𝑖𝑗 =𝛼𝑖𝑗 𝑠𝑖𝑗
𝑣𝑖𝑗
(2)
trong đó 𝑐𝑖𝑗 trọng số đại diện cho thời gian xe di chuyển từ i đến j; 𝑠𝑖𝑗 là quãng đường từ từ đỉnh
i đến đỉnh j; 𝑣𝑖𝑗 là vận tối tối đa cho phép xe di chuyển trên đoạn đường i đến j; 𝛼𝑖𝑗 ∈[1;2] là
499
hệ số đại diện cho đại lượng lưu lượng xe vào các khung giờ trong ngày, vào giờ cao điểm lưu
lượng xe nhiều thì 𝛼 càng lớn ngược lại lưu lượng xe ít thì 𝛼 nhỏ. Các khung giờ trong ngày sẽ
được chi làm 5 mức độ khác nhau của tình trạng lưu thông xe, với 𝛼 được chọn như sau:
𝛼𝑖𝑗 =
{
2 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑟ấ𝑡 𝑛ℎ𝑖ề𝑢 𝑥𝑒
1.7 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑛ℎ𝑖ề𝑢 𝑥𝑒
1.5 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑏ì𝑛ℎ 𝑡ℎườ𝑛𝑔
1.3 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 í𝑡 𝑥𝑒
1 𝑛ế𝑢 đ𝑜ạ𝑛 đườ𝑛𝑔 𝑖𝑗 𝑟ấ𝑡 í𝑡 𝑥𝑒
(3)
Gọi v là đỉnh nguồn, v’ là đỉnh đích. Tìm đường đi ngắn nhất (nếu có) từ đỉnh v tới v’
trong đồ thị G được mô hình hóa như sau:
𝑚𝑖𝑛 ∑ 𝑐𝑖𝑗
𝑖𝑗 ∈ 𝐸 ∗𝑥𝑖𝑗,(1)
𝑥𝑖𝑗 = {1 𝑛ế𝑢 𝑐ạ𝑛ℎ (𝑖,𝑗)∈𝑃
0 𝑛𝑔ượ𝑐 𝑙ạ𝑖
(4)
trong đó c(i,j) là trọng số chi phí, xij là biến quyết định nhị phân bằng 1 nếu cạnh (i,j) thuộc
đường đi ngắn nhất P và ngược lại bằng 0.
Nếu một đỉnh được chọn cho đường đi ngắn nhất thì tổng số cạnh đi vào đỉnh đó bằng
tổng số bằng tổng số lượng cạnh đi ra khỏi đỉnh đó và bằng 1. Gọi m là đỉnh trên đường đi từ v
đến v’, K’ là tập đỉnh có cạnh đi tới m và T’ là tập đỉnh có cạnh đi từ m tới.
∑ 𝑥𝑘𝑚
𝑘 ∈𝐾′ = ∑𝑥𝑚𝑡
𝑡 ∈𝑇′=1
(5)
Đặt v là đỉnh nguồn, K là tập các đỉnh kề với đỉnh nguồn có nghĩa là từ đỉnh nguồn sẽ có
cạnh nối tới các đỉnh trong tập K. Trong tập các cạnh từ đỉnh nguồn đến các đỉnh kề trong K –
gọi là cạnh ra khỏi đỉnh nguồn sẽ có một cạnh được chọn, nên ta có:
∑𝑥𝑖𝑗
𝑗 ∈ 𝐾 −1=0 𝑣ớ𝑖 𝑖 ≡𝑣 𝑣à 𝑗 ∈𝐾
(6)
Đặt v’ là đỉnh đích, T là tập các đỉnh kề với đỉnh đích có nghĩa là từ đỉnh đích có cạnh nối
tới các đỉnh trong tập T. Trong tập các cạnh từ đỉnh trong tập T đến đỉnh đích – gọi là cạnh vào
đỉnh đích sẽ có 1 cạnh được chọn, nên ta có:
1−∑𝑥𝑖𝑗
𝑖 ∈ 𝑇 =0 𝑣ớ𝑖 𝑗 ≡𝑣′𝑣à 𝑖 ∈𝑇 (4)
(7)
Mô hình Bài toàn đường đi ngắn nhất cơ bản được áp dụng công thức (1) đến (4), thêm
vào đó để giải quyết bài toán đường đi ngắn nhất có ràng buộc chúng ta cần mô hình hóa các
ràng buộc đi kèm. Chúng tôi chia các ràng buộc thành các dạng: ràng buộc trên cạnh của đồ thị,
ràng buộc trên đỉnh của đồ thị, ràng buộc đường trên đồ thị.
Bài toán tìm đường đi ngắn nhất từ v đến v' trong đồ thị G nhưng buộc đi qua/không đi qua
một hay một số cạnh cho trước. Đối với loại ràng buộc này ta cần thiết lập biến quyết định (1’)
𝑥𝑖𝑗 = {1 𝑛ế𝑢 𝑐ạ𝑛ℎ (𝑖,𝑗)∈𝑃
0 𝑛𝑔ượ𝑐 𝑙ạ𝑖
(8)
500
Bài toán tìm đường đi ngắn nhất từ v đến v' trong đồ thị G nhưng buộc đi qua/không đi
qua một hay một số đỉnh cho trước. Đối với loại ràng buộc này ta áp dụng theo công thức (2)
∑ 𝑥𝑘𝑚
𝑘 ∈𝐾′ = ∑𝑥𝑚𝑡
𝑡 ∈𝑇′= {1 𝑛ế𝑢 đỉ𝑛ℎ 𝑚∈𝑃
0 𝑛𝑔ượ𝑐 𝑙ạ𝑖
(9)
Theo [4] trên đường đi ngắn nhất từ v đến v’ ràng buộc đường cấm có hai trường hợp:
• Cấm tất cả các đường từ đỉnh y đến đỉnh k, hay nói cách khác trên đường đi ngắn nhất
từ v đến v’ sẽ không đi qua hai đỉnh y và k. Do đó, chỉ cần áp dụng công thức (6) cho hai đỉnh
y và k để mô hình ràng buộc này.
∑ 𝑥𝑘𝑚
𝑘 ∈𝐾′ = ∑𝑥𝑚𝑡
𝑡 ∈𝑇′=0
(10)
Với m là đỉnh y và đỉnh k.
• Trường hợp từ k đến y có nhiều đường đi nhưng chỉ cấm một/một vài đường đi từ đỉnh
k đến đỉnh y. Hay nói cách khác tổng các cạnh trên đường cấm nhỏ hơn tổng số đỉnh thuộc
đường cấm trừ 1, mô hình ràng buộc như sau:
∑ 𝑥𝑖𝑗 <𝑆−1
𝑖𝑗 ∈ 𝐸
(11)
• Đồ thị có đường đi từ đỉnh k đến đỉnh y thì tổng số cạnh được chọn cho đường đi lớn
hơn hoặc bằng tổng số đỉnh của đường đi trừ một, được mô hình như sau:
∑ 𝑥𝑖𝑗 ≥𝑆−1
𝑖𝑗 ∈ 𝐸
(12)
trong đó S là tổng số đỉnh thuộc đường đi P.
3. THỰC NGHIỆM
Trong phần này, chúng tôi trình bày các thực nghiệm xung quanh các ràng buộc được
trình bày trong phần III. Bên cạnh đó, để giải mô hình qui hoạch nguyên chúng tôi sử dụng
công cụ LP Solve IDE để tìm nghiệm cho bài toán. Thực tế áp dụng, chỉ cần định nghĩa mô
hình của bài toán và áp dụng công cụ Solver để tìm nghiệm sẽ giúp người sử dụng không cần
lập trình cũng có thể giải được bài toán.
Cho đồ thị như hình sau:
Hình 1. Đồ thị thực nghiệm.
501
Thực nghiệm 1 (TN1): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8.
Thực nghiệm 2 (TN2): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không qua nút 5.
Thực nghiệm 3 (TN3): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 phải qua nút 4.
Thực nghiệm 4 (TN4): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và nếu đi qua nút 7
phải qua nút 3.
Thực nghiệm 5 (TN5): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi qua tất cả
các đường từ 3 tới 7.
Thực nghiệm 6 (TN6): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi đường từ
3 tới 5 tới 7.
Thực nghiệm 7 (TN7): tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và phải đi qua đường
từ 3 tới 5 tới 7.
Biến quyết định: xij: xác định có hay không một liên kết từ nút i đến nút j.
Hàm mục tiêu:
100x12 + 151x13 + 150x26 + 75x25 + 42x35 + 67x34 + 22x45 + 11x57 + 25x67 + 71x68
+ 52x78 → Min (cực tiểu chi phí đường đi)
Các ràng buộc cho đồ thị:
{
xij [0,1]
x12 + x13 − 1 = 0
x25 + x26 − x12 = 0
x34 + x35 − x13 = 0
x45 + x47 − x34 = 0
x57 − x25 − x35 − x45 = 0
x67 + x68 − x26 = 0
x78 − x47 − x57 − x67 = 0
1 − x68 − x78 = 0
Bên cạnh đó, để thõa ràng buộc của các thực nghiệm 2, 3, 4, 5, 6, 7 thêm ràng buộc sau :
• Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không qua nút 5 :
x25 = x35 = x45 = x57 = 0
• Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 phải qua nút 4:
x45 + x47 = 1
• Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và nếu đi qua nút 7 phải qua nút 3.
x25 + x26 - x78 ≥ 0
• Ràng buộc không đi qua tất cả các đường từ đỉnh 3 tới đỉnh 7
x13=x35=x34=x57=x47=x78=0
• Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và không đi đường từ 3 tới 5 tới 7
x35+x57 < 2
• Ràng buộc đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 và phải đi qua đường từ 3 tới 5 tới 7.
x35+x57 >= 2