Xem mẫu
BÀI TOÁN PHÂN LUỒNG GIAO THÔNG VÀ ỨNG DỤNG
Trần Quốc Chiến1Hồ Văn Hùng2
Tóm tắt: Kết quả của công trình bao gồm: (1) Xây dựng mô hình mạng giao thông mở rộng, trong
đó chi phí tại một nút không giống nhau với mọi đường đi qua nút đó, mà còn phụ thuộc vào tuyến
đi đến và tuyến đi khỏi đỉnh đó, thậm chí có hướng còn bị cấm. (2) Xây dựng mô hình bài toán
luồng cực đại đồng thời chi phí giới hạn trên mạng giao thông mở rộng và phát triển thuật toán
xấp xỉ giải bài toán này trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính và thuật toán tìm
đường đi ngắn nhất trên đồ thị mở rộng. (3) Xây dựng mô hình bài toán phân luồng tối ưu trên
mạng giao thông mở rộng và phát triển thuật toán hữu hiệu tìm luồng tối ưu. Các thuật toán được
cài đặt bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng
trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
Từ khóa: Đồ thị, Mạng, Luồng đa phương tiện, Xấp xỉ, Tối ưu.
1 . Mở đầu
Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông,
công nghệ thông tin, kinh tế,…. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh,
các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và
các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không
giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh
đó. Ví dụ thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào hướng di chuyển của phương
tiện giao thông: rẽ phải, đi thẳng hay rẽ trái, thậm chí có hướng bị cấm. Vì vậy cần xây dựng một
mô hình đồ thị mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả
hơn.
Báo cáo trình bày kết quả khảo sát hạ tầng kỹ thuật mạng lưới giao thông khu vực trung tâm Đà
Nẵng, nhu cầu đi lại giữa các nút giao thông trong phạm vi đề tài NCKH cấp thành phố “Bài toán
mạng giao thông và ứng dụng quản lý quy hoạch phân luồng giao thông ở thành phố Đà Nẵng”
do Trường Đại học Sư phạm - ĐHĐN, Trường Đại học Bách khoa – ĐHĐN và Sở Giao thông Vận
tải TP. Đà Nẵng phối hợp thực hiện.
Tiếp theo, báo cáo xây dựng mô hình hai bài toán phân luồng giao thông đa phương
tiện tuyến tính trên mạng giao thông mở rộng:Bài toán luồng cực đại đồng thời chi phí giới hạn và
bài toán phân luồng tối ưu. Các thuật toán hữu hiệu phân luồng tối ưu được phát triển và cài đặt
bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng trong hệ
quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
2. Mạng giao thông Trung tâm Đà Nẵng
1
2
. PGS.TS. Khoa Tin học, trường ĐHSP Đà Nẵng
. ThS. Giám đốc Trung tâm TH-NN, trường ĐHQN
Mạng lưới giao thông Trung tâm Đà Nẵng (xem bản đồ khu vực khảo sát) có 120 nút và 209 đoạn
tuyến trên 49 tuyến phố và nhu cầu đi lại của 999 cặp nút nguồn và nút đích.
Hình 1. Bản đồ khu vực khảo sát
Mạng lưới giao thông trên được mô hình hóa bằng đồ thị mạng hỗn hợp mở rộng sau:
Hình 2. Đồ thị mạng giao thông Trung tâm Đà Nẵng
3. Khả năng thông hành và chi phí thời gian qua đoạn tuyến
Hệ thống các thông số biểu diễn khả năng thông hành (xe con quy đổi) và chi phí thời gian (phút)
trên các đoạn tuyến như sau:
Bảng 1. Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian trên các cung
đoạn tuyến lưu trong bảng SUBLINE
Mã số
Nút đầu Nút cuối Khả năng thông hành Thời gian Có hướng
00001a
1
2
4320
2.82
1
00001b
2
1
4320
2.82
1
00002a
2
3
4320
1.96
1
00002b
3
2
4320
1.96
1
00003
4
5
2880
2.63
0
00004
6
7
2880
0.34
0
00005
8
9
3703
0.95
0
…
…
…
…
…
…
00208
80
81
4320
0.33
0
00209
81
82
4320
0.34
0
00210
15
3
4320
2.50
1
00211
117
119
4320
1.00
1
4. Khả năng thông hành nút
Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian qua các nút giao thông
lưu trong bảng NODE.
5. Chi phí thời gian qua nút
Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông như sau:
Bảng 2. Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông lưu trong bảng
NODESUBTIME.
Node
chính
Node
trước
Node
sau
time
giây
1
2
35
11
2
1
3
8
3
4
10,2
3
2
5
5,2
4
2
5
8,5
bV
phút
Node
trước
Node
sau
time
giây
2
6,2
1
4
4
35
15
2
bV
phút
Node
trước
Node
sau
time
giây
6,7
3
1
7,8
1
10,3
4
3
5,9
2
13 ,
1
6
6,2
5
2
5,9
bV
phút
5
5
6
7,5
6
3
4
6,6
3
6,2
6
15
7,1
4
…
…
…
…
…
…
…
119
110
118
7,2
110
120
16 ,
9
117
120
8,5
120
118
10
119
106
15 ,
8
120
…
2
…
…
5
5,2
15
4
…
…
…
6. Nhu cầu đi lại
Hệ thống các nhu cầu đi lại cho bởi 999 cặp đỉnh nguồn nguồn đích và số xe lưu hành trong bảng
DEMAND.
7. Mô hình Mạng giao thông mở rộng
Cho đồ thị hỗn hợp G=(V, E) với tập đỉnh V và tập cạnh E. Các cạnh có thể có hướng hoặc vô
hướng. Có nhiều loại phương tiện giao thông lưu hành trên mạng. Những cạnh vô hướng biểu diễn
tuyến hai chiều, trong đó các phương tiện trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ
khả năng thông hành của tuyến. Trên mạng cho các hàm sau.
Hàm khả năng thông hành cạnh cE:E→R*, với cE(e) là khả năng thông hành cạnh e ∈ E.
Hàm khả năng thông hành đỉnh cV:V→R*, với cV(u) là khả năng thông hành đỉnh u ∈ V.
Hàm chi phí cạnh bE:E→R*, với bE(e) là chi phí phải trả để chuyển một đơn vị phương tiện qua
cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí hai hướng có thể khác nhau.
Với mỗi đỉnh v∈V, ký hiệu Ev là tập các cạnh liên thuộc đỉnh v.
Hàm chi phí đỉnhbV: V×Ev×Ev→R*, với bV(u,e, e’) là chi phí phải trả để chuyển một đơn vị phương
tiện qua đỉnh u từ tuyến e sang tuyến e’.
Bộ (V, E,
c c b b
E, V, E, V) gọi là mạng giao thông mở rộng.
Cho p là đường đi từ đỉnh u đến đỉnh v qua các cạnh ei, i = 1, …, h+1, và các đỉnh ui, i = 1, …, h,
như sau p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v]
Định nghĩa chi phí vận chuyển một đơn vị phương tiện qua đường đi p, ký hiệu b(p) , theo công
thức sau :
h+1
h
b(p) = ∑bE(ei ) + ∑bV (ui,ei,ei+1)
i=1
(1)
i=1
Cho mạng giao thông mở rộng G=(V, E,
c c b b
E, V, E, V).
nguon tai.lieu . vn
Trần Quốc Chiến1Hồ Văn Hùng2
Tóm tắt: Kết quả của công trình bao gồm: (1) Xây dựng mô hình mạng giao thông mở rộng, trong
đó chi phí tại một nút không giống nhau với mọi đường đi qua nút đó, mà còn phụ thuộc vào tuyến
đi đến và tuyến đi khỏi đỉnh đó, thậm chí có hướng còn bị cấm. (2) Xây dựng mô hình bài toán
luồng cực đại đồng thời chi phí giới hạn trên mạng giao thông mở rộng và phát triển thuật toán
xấp xỉ giải bài toán này trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính và thuật toán tìm
đường đi ngắn nhất trên đồ thị mở rộng. (3) Xây dựng mô hình bài toán phân luồng tối ưu trên
mạng giao thông mở rộng và phát triển thuật toán hữu hiệu tìm luồng tối ưu. Các thuật toán được
cài đặt bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng
trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
Từ khóa: Đồ thị, Mạng, Luồng đa phương tiện, Xấp xỉ, Tối ưu.
1 . Mở đầu
Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông,
công nghệ thông tin, kinh tế,…. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh,
các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và
các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không
giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh
đó. Ví dụ thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào hướng di chuyển của phương
tiện giao thông: rẽ phải, đi thẳng hay rẽ trái, thậm chí có hướng bị cấm. Vì vậy cần xây dựng một
mô hình đồ thị mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả
hơn.
Báo cáo trình bày kết quả khảo sát hạ tầng kỹ thuật mạng lưới giao thông khu vực trung tâm Đà
Nẵng, nhu cầu đi lại giữa các nút giao thông trong phạm vi đề tài NCKH cấp thành phố “Bài toán
mạng giao thông và ứng dụng quản lý quy hoạch phân luồng giao thông ở thành phố Đà Nẵng”
do Trường Đại học Sư phạm - ĐHĐN, Trường Đại học Bách khoa – ĐHĐN và Sở Giao thông Vận
tải TP. Đà Nẵng phối hợp thực hiện.
Tiếp theo, báo cáo xây dựng mô hình hai bài toán phân luồng giao thông đa phương
tiện tuyến tính trên mạng giao thông mở rộng:Bài toán luồng cực đại đồng thời chi phí giới hạn và
bài toán phân luồng tối ưu. Các thuật toán hữu hiệu phân luồng tối ưu được phát triển và cài đặt
bằng ngôn ngữ Java với cơ sở dữ liệu mạng giao thông trung tâm thành phố Đà Nẵng trong hệ
quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
2. Mạng giao thông Trung tâm Đà Nẵng
1
2
. PGS.TS. Khoa Tin học, trường ĐHSP Đà Nẵng
. ThS. Giám đốc Trung tâm TH-NN, trường ĐHQN
Mạng lưới giao thông Trung tâm Đà Nẵng (xem bản đồ khu vực khảo sát) có 120 nút và 209 đoạn
tuyến trên 49 tuyến phố và nhu cầu đi lại của 999 cặp nút nguồn và nút đích.
Hình 1. Bản đồ khu vực khảo sát
Mạng lưới giao thông trên được mô hình hóa bằng đồ thị mạng hỗn hợp mở rộng sau:
Hình 2. Đồ thị mạng giao thông Trung tâm Đà Nẵng
3. Khả năng thông hành và chi phí thời gian qua đoạn tuyến
Hệ thống các thông số biểu diễn khả năng thông hành (xe con quy đổi) và chi phí thời gian (phút)
trên các đoạn tuyến như sau:
Bảng 1. Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian trên các cung
đoạn tuyến lưu trong bảng SUBLINE
Mã số
Nút đầu Nút cuối Khả năng thông hành Thời gian Có hướng
00001a
1
2
4320
2.82
1
00001b
2
1
4320
2.82
1
00002a
2
3
4320
1.96
1
00002b
3
2
4320
1.96
1
00003
4
5
2880
2.63
0
00004
6
7
2880
0.34
0
00005
8
9
3703
0.95
0
…
…
…
…
…
…
00208
80
81
4320
0.33
0
00209
81
82
4320
0.34
0
00210
15
3
4320
2.50
1
00211
117
119
4320
1.00
1
4. Khả năng thông hành nút
Hệ thống các thông số biểu diễn khả năng thông hành và chi phí thời gian qua các nút giao thông
lưu trong bảng NODE.
5. Chi phí thời gian qua nút
Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông như sau:
Bảng 2. Hệ thống các thông số biểu diễn chi phí thời gian qua các nút giao thông lưu trong bảng
NODESUBTIME.
Node
chính
Node
trước
Node
sau
time
giây
1
2
35
11
2
1
3
8
3
4
10,2
3
2
5
5,2
4
2
5
8,5
bV
phút
Node
trước
Node
sau
time
giây
2
6,2
1
4
4
35
15
2
bV
phút
Node
trước
Node
sau
time
giây
6,7
3
1
7,8
1
10,3
4
3
5,9
2
13 ,
1
6
6,2
5
2
5,9
bV
phút
5
5
6
7,5
6
3
4
6,6
3
6,2
6
15
7,1
4
…
…
…
…
…
…
…
119
110
118
7,2
110
120
16 ,
9
117
120
8,5
120
118
10
119
106
15 ,
8
120
…
2
…
…
5
5,2
15
4
…
…
…
6. Nhu cầu đi lại
Hệ thống các nhu cầu đi lại cho bởi 999 cặp đỉnh nguồn nguồn đích và số xe lưu hành trong bảng
DEMAND.
7. Mô hình Mạng giao thông mở rộng
Cho đồ thị hỗn hợp G=(V, E) với tập đỉnh V và tập cạnh E. Các cạnh có thể có hướng hoặc vô
hướng. Có nhiều loại phương tiện giao thông lưu hành trên mạng. Những cạnh vô hướng biểu diễn
tuyến hai chiều, trong đó các phương tiện trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ
khả năng thông hành của tuyến. Trên mạng cho các hàm sau.
Hàm khả năng thông hành cạnh cE:E→R*, với cE(e) là khả năng thông hành cạnh e ∈ E.
Hàm khả năng thông hành đỉnh cV:V→R*, với cV(u) là khả năng thông hành đỉnh u ∈ V.
Hàm chi phí cạnh bE:E→R*, với bE(e) là chi phí phải trả để chuyển một đơn vị phương tiện qua
cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí hai hướng có thể khác nhau.
Với mỗi đỉnh v∈V, ký hiệu Ev là tập các cạnh liên thuộc đỉnh v.
Hàm chi phí đỉnhbV: V×Ev×Ev→R*, với bV(u,e, e’) là chi phí phải trả để chuyển một đơn vị phương
tiện qua đỉnh u từ tuyến e sang tuyến e’.
Bộ (V, E,
c c b b
E, V, E, V) gọi là mạng giao thông mở rộng.
Cho p là đường đi từ đỉnh u đến đỉnh v qua các cạnh ei, i = 1, …, h+1, và các đỉnh ui, i = 1, …, h,
như sau p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v]
Định nghĩa chi phí vận chuyển một đơn vị phương tiện qua đường đi p, ký hiệu b(p) , theo công
thức sau :
h+1
h
b(p) = ∑bE(ei ) + ∑bV (ui,ei,ei+1)
i=1
(1)
i=1
Cho mạng giao thông mở rộng G=(V, E,
c c b b
E, V, E, V).