B GIÁO DC VÀ ĐÀO TO
ĐI HC ĐÀ NNG
LÊ HNG DŨNG
XÂY DNG MÔ HÌNH H THNG XE BUÝT
TRƯNG HC TRÊN CƠ S BÀI TOÁN
PHÂN LUNG GIAO THÔNG
Chuyên ngành: KHOA HC MÁY TÍNH
Mã s : 60.48.01
TÓM TT LUN VĂN THC SĨ K THUT
Đà Nng - Năm 2012
Công trình ñưc hoàn thành ti
ĐI HC ĐÀ NNG
Ngưi hưng dn khoa hc: PGS. TS. Võ Trung Hùng
Phn bin 1: PGS. TS. Tăng Tn Chin
Phn bin 2: PGS. TS. Lê Mnh Thnh
Lun văn ñưc bo v ti Hi ñng chm Lun văn tt nghip
thc sĩ k thut hp ti Đi hc Đà Nng vào ngày 16 tháng 6
năm 2012.
Có th tìm hiu lun văn ti:
• Trung tâm Thông tin - Hc liu, Đi hc Đà Nng
• Trung tâm Hc liu, Đi hc Đà Nng
1
M ĐU
1. Lý do chn ñ tài
Trên th gii các nhà quy hoch ñô th ñang n lc phát trin
h thng giao thông công cng (GTCC) ñ cnh tranh vi phương
tin giao thông cá nhân. các quc gia ñang phát trin, phương tin
giao thông cá nhân tip t!c gia tăng th ph"n và to thêm s#c ép cnh
tranh lên GTCC. Ti M, GTCC ch$ chim 1,8% th trưng vn
chuyn năm 1995, so vi năm 1977 là 2,4% và năm 1983 là 2,2%.
M%c cho hàng ch!c t$ USD ñ"u tư vào xây dng h thng ñưng s&t
mi và chi phí vn hành ñưc tr giá ñn 75%, hot ñng kinh doanh
c'a GTCC vn không my kh(i s&c. S suy gim vai trò c'a GTCC
là mt hi chuông cnh báo cho các thành ph ln vì quá ph! thuc
vào phương tin giao thông cá nhân. Nguyên nhân c'a s suy gim
b&t ngun t) rt nhi*u yu t: vic tăng thu nhp, gim giá thành
phương tin và chi phí ñu ñ dn ñn tăng kh năng s( h+u phương
tin giao thông cá nhân và gim nhu c"u s, d!ng GTCC.
Tuy nhiên, c"n phi tìm ra ñưc gii pháp cân b-ng gi+a
phương tin GTCC và phương tin giao thông cá nhân ( ñô th. Đin
hình là Singapore và Copenhagen, hai thành ph này ñã thay ñ.i mô
hình ñô th ñ phù hp vi hình th#c GTCC vì nguyên nhân khan
him ñt ñai, bo tn các không gian m( bên cnh vic khuyn khích
phát trin ñô th và giao thông b*n v+ng.
nưc ta xe buýt hin nay ñóng mt vai trò quan trng trong
vic di chuyn h-ng ngày c'a ngưi dân thành ph. Đây là mt
phương tin vn ti hành khách công cng v)a kinh t v)a thân thin
vi môi trưng, góp ph"n tích cc vào vic hn ch nn k/t xe trong
thành ph. Cùng vi s phát trin nhanh c'a nưc ta, thi gian ñưa
2
ñón các em hc sinh trung hc cơ s( (THCS) c'a các bc ph! huynh
c"n ñưc gim thiu. Đ#ng trên phương din các bc ph! huynh hc
sinh thy thành ph nên có ch' trương xây dng h thng GTCC
dành riêng cho cp hc này ñ ñm bo an toàn, an ninh cho hc
sinh, gim thiu ñưc thi gian ñưa ñón các em cũng như gim thiu
các phương tin giao thông cá nhân, gim lưu lưng xe tham gia giao
thông trong gi cao ñim và gim lưng khí thi ñc hi gây ô nhi1m
môi trưng.
Xut phát t) lý do ñó, tôi ñã chn thc hin ñ* tài:
“
Xây dng
mô hình h thng xe buýt trưng hc trên cơ s bài toán phân lung
giao thông”.
2. Mc ñích nghiên cu
Xây dng h thng các tuyn xe buýt ph!c v! cho vic ñi li
c'a hc sinh THCS trên ña bàn thành ph Đà Nng. 2ng d!ng bài
toán phân lung, tìm lung cc ñi ñ mô hình hóa bài toán phân
lung giao thông lên ñ th. Cài ñ%t thut toán cho bài toán phân
lung giao thông. Đánh giá kt qu ñt ñưc c'a ñ* tài.
3. Đi tư ng và phm vi nghiên cu
Đ ñt ñưc m!c ñích trên chúng tôi xác ñnh ñi tưng và
phm vi nghiên c#u như sau. Đi tưng nghiên c#u c'a ñ* tài gm:
các loi hình giao thông công cng b-ng xe buýt, sơ ñ ñưng ñi c'a
thành ph Đà Nng và nhu c"u ñi li c'a cp hc THCS. Phm vi
nghiên c#u ñưc gii hn trong thành ph Đà Nng.
4. Phương pháp nghiên cu
Nghiên c#u lý thuyt v* mt s thut toán trên ñ th: ñ th
liên thông, bài toán lung cc ñi trong mng, biu di1n bài toán trên
ñ th.
3
Kho sát, phân tích d+ liu t) nhi*u ngun khác nhau. T) kt
qu phân tích tin hành xây dng các gii pháp và #ng d!ng trong h
thng xe buýt ñưa ñón hc sinh THCS, cui cùng chy th, nghim
và lưu tr+ các kt qu ñt ñưc.
5. Ý nghĩa khoa hc và th#c ti$n c%a lu&n văn
Ý nghĩa khoa hc: Trin khai vic #ng d!ng công ngh thông
tin trong vic gii quyt ñưc các bài toán v* lung cc ñi, la chn
ñưng ñi ng&n nht, tt nht, t) ñó xây dng l trình cho các tuyn xe
buýt trưng hc.
Ý nghĩa thc ti1n: To ra h thng GTCC riêng bit cho các
em hc sinh THCS bên cnh h thng GTCC truy*n thng, ñ gim
bt thi gian ñưa ñón con em c'a các bc ph! huynh, gim thiu lưu
lưng phương tin giao thông cá nhân trên ñưng ph. Gii quyt
ñưc các vn ñ* xã hi: như nn k/t xe, tit kim nhiên liu, an toàn
hơn khi tham gia giao thông và gim ñưc lưng khí thi gây ô
nhi1m môi trưng.
6. B cc lu&n văn
Ni dung chính c'a lun văn ñưc chia thành 3 chương. Trong
chương 1, trình bày nh+ng kin th#c t.ng quan bao gm gii thiu v*
cơ s( lý thuyt ñ th, các thut toán trên ñ th. Chương 2, phân tích
hin trng GTCC hin nay trên ña bàn thành ph Đà Nng, vn ñ*
ñưa ñón hc sinh THCS và ñưa ra gii pháp lung cc ñi #ng d!ng
trong h thng xe buýt trưng hc. Chương 3, xây dng #ng d!ng
các tuyn c'a h thng xe xuýt trưng hc mà c! th là các trưng
THCS trên ña bàn hai qun trung tâm c'a thành ph Đà Nng là
qun Hi Châu và Thanh Khê.
4
CHƯƠNG 1: CƠ S LÝ THUY'T Đ TH(
Chương này gii thiu ñi cương v* lý thuyt ñ th, ñưng ñi,
chu trình, ñ th liên thông, các thut toán tìm kim trên ñ th, tìm
kim theo chi*u rng và theo chi*u sâu, các thut toán tìm ñưng ñi
ng&n nht, thut toán Ford - Fulkerson tìm lung cc ñi trong mng
làm cơ s( tính toán, xây dng các tuyn xe buýt ph!c v! ñưa, ñón các
em hc sinh trung hc cơ s( trên ña bàn thành ph Đà Nng.
1.1. Đ(NH NGHĨA VÀ PHÂN LOI
1.1.1. Đ)nh nghĩa ñ* th), ñư+ng ñi, chu trình, ñ* th) liên thông
1.1.1.1. Đnh nghĩa ñ th
Đ th (graph) là mt mô hình toán hc ñưc #ng d!ng trong
nhi*u lĩnh vc khoa hc, k thut.
1.1.1.2. Đưng ñi và chu trình
Gi s, G = (V, E) là mt ñ th.
Đnh nghĩa 1.6: Đưng ñi trong ñ th là mt dãy các ñ$nh:
<
x
1
,
x
2
,
.
..
,
x
i
,
x
j+1
,
.
..
,
x
k-1
,
x
k
>
sao cho, mi ñ$nh trong dãy (không k
ñ$nh ñ"u tiên) k* vi ñ$nh trưc nó b-ng mt cnh nào ñó, nghĩa là:
∀
i
=
2
,
3,
.
..
,
k
-1,
k
:
(
x
i-1
,
x
i
)
∈
E.
Ta nói r-ng ñưng ñi này ñi t) ñ$nh ñ"u x
1
ñn ñ$nh cui x
k
. S
cnh c'a ñưng ñi ñưc gi là ñ dài c'a ñưng ñi ñó.
1.1.1.3. Đ th liên thông
Nu gi+a hai ñim bt kỳ c'a mt ñ th ñ*u có th thit lp
mt ñưng ñi t) ñ$nh này ñn ñ$nh kia, ñ th ñưc coi là liên thông;
nu không, ñ th ñưc coi là không liên thông. Mt ñ th ñưc coi
là hoàn toàn không liên thông nu không có ñưng ñi gi+a hai ñ$nh
bt kỳ trong ñ th. Đây ch$ là mt cái tên khác ñ miêu t mt ñ th
rng ho%c mt tp ñc lp.
5
1.1.2. M,t s dng ñ* th) ñ-c bi.t
1.1.2.1. Đ th ñy ñ
Đ th ñ"y ñ' n ñ$nh, ký hiu b(i K
n
, là ñơn ñ th vô hưng
mà gi+a hai ñ$nh bt kỳ c'a nó luôn có cnh ni.
1.1.2.2. Đ th vòng
Đ th vòng Cn, n≥3, gm n ñ$nh v1, v2,....vn và các cnh (v1,
v2), (v2, v3)... (vn-1, vn), (vn, v1).
1.1.2.3. Đ th bánh xe
Đ th W
n
thu ñưc t) C
n
b-ng cách b. sung vào mt ñ$nh mi
ni vi tt c các ñ$nh c'a C
n
.
1.1.2.4. Đ th lp phương
Đ th lp phương n ñnh Q
n
là ñ th vi các ñnh biu din 2
n
xâu
nh phân ñ dài n. Hai ñnh ca nó gi là k nhau nu như hai xâu
nh phân tương ng ch khác nhau 1 bit cho thy Q
n
vi n=1,2,3
1.1.2.5. Đ th hai phía
Đơn ñ th G=(V, E) ñưc gi là hai phía nu như tp ñ$nh V
c'a nó có th phân hoch thành hai tp X và Y sao cho mi cnh c'a
ñ th ch$ ni mt ñ$nh nào ñó trong X vi mt ñ$nh nào ñó trong Y.
Khi ñó ta s6 s, d!ng ký hiu G=(X∪Y, E) ñ ch$ ñ th hai phía vi
tp ñ$nh X∪Y.
1.1.2.6. Đ th phng
Đ th ñưc gi là ñ th ph7ng nu ta có th v6 nó trên m%t
ph7ng sao cho các cnh c'a nó không c&t nhau ngoài ( ñ$nh. Cách v6
như vy s6 ñưc gi là biu di1n ph7ng c'a ñ th.
1.2. CÁC THUT TOÁN CƠ B/N TRÊN Đ TH(
1.2.1. Thu&t toán tìm kim trên ñ* th)
Gii thiu mt s thut toán tìm kim trên ñ th: thut toán
tìm kim theo chi*u sâu, thut toán tìm kim theo chi*u rng, thut
6
toán tìm thành ph"n liên thông c'a ñ th, thut toán tìm ñưng ñi
c'a hai ñ$nh.
1.2.1.1. Thut toán tìm kim theo chiu sâu
1.2.1.2. Thut toán tìm kim theo chiu rng
1.2.1.3. Bài toán tìm thành phn liên thông ca ñ th
Cho mt ñ th G=(V.E). Hãy cho bit s thành ph"n liên
thông c'a ñ th và mi thành ph"n liên thông gm nh+ng ñ$nh nào.
Như ta ñã bit, các th' t!c DFS(u) và BFS(u) cho phép ving thăm
tt c các ñ$nh có cùng thành ph"n liên thông vi u nên s thành ph"n
liên thông c'a ñ th chính là s l"n gi th' t!c trên.
1.2.1.4. Bài toán tìm ñưng ñi gia hai ñnh ca ñ th
Cho ñ th G=(V,E). Vi hai ñ$nh s và t là hai ñ$nh nào ñó c'a
ñ th. Hãy tìm ñưng ñi t) s ñn t.
Do th' t!c DFS(s) và BFS(s) s6 thăm l"n lưt các ñ$nh liên
thông vi u nên sau khi thc hin xong th' t!c thì có hai kh năng:
- Nu Daxet[t] = True thì có nghĩa: Tn ti mt ñưng ñi t)
ñ$nh s ti ñ$nh t.
- Ngưc li, thì không có ñưng ñi ni gi+a s và t.
Vn ñ* còn li c'a bài toán là: Nu tn ti ñưng ñi ni ñ$nh s
và ñ$nh t thì làm cách nào ñ vit ñưc hành trình (gm th# t các
ñ$nh) t) s ñn t.
1.2.2. Mng, lu*ng trong mng
1.2.2.1. Mng lung
Mng lung là mt ñ th có hưng, trong ñó mi cnh có mt
ñ thông qua và mt giá tr lung. Lưng lung trên mi cnh không
ñưc vưt quá ñ thông qua c'a cnh ñó. Lưng lung ñi vào mt
ñ$nh phi b-ng lưng lung ñi ra kh8i nó, tr) khi ñó là ñ$nh ngun
(có nhi*u lưng lung ñi ra hơn), hay ñ$nh ñích (có nhi*u lưng
7
lung ñi vào hơn). Mng lung có th dùng ñ mô hình hóa h thng
ñưng giao thông, dòng chy c'a cht l8ng trong ng, dòng ñin
trong mch, hay bt kỳ các bài toán nào tương t khi có s di chuyn
trong mt mng các nút.
1.2.2.2. Bài toán lung cc ñi trong mng
Tn ti mt ñưng ñi t) ngun (nút b&t ñ"u) ñn ñim x (nút
cui), vi ñi*u kin tt c các cung trên ñưng ñi ñó vn còn kh
năng thông qua, thì ta s6 g,i ñi mt lung dc theo ñưng ñi ñó. Sau
ñó chúng ta tìm mt ñưng ñi khác, và tip t!c như vy. Mt ñưng
ñi còn kh năng thông qua là mt ñưng ñi có kh năng m( rng
thêm hay mt ñưng ñi mà lung qua ñó còn kh năng tăng thêm gi
t&t là ñưng tăng.
1.2.3. Các thu&t toán tìm ñư+ng ñi ng0n nht
1.2.3.1. Phát biu bài toán
Cho ñ th có trng s G=(V,E). Ký hiu w(i,j) là trng s c'a
cnh (i,j). Đ dài ñưng ñi µ = v
0
→v
1
→v
2
→... →v
n-1
→v
n
là t.ng các
trng s
L(µ) =
∑
=−
n
i
ii
vvw
1
1
),(
Cho hai ñ$nh a, z c'a ñ th. Bài toán ñ%t ra là tìm ñưng ñi
ng&n nht t) a ñn z.
1.2.3.2. Thut toán Dijkstra
Thut toán tìm ñưng ñi ng&n nht t) ñ$nh a ñn ñ$nh z trong
ñ th liên thông có trng s. Trng s c'a cnh (i,j) là w(i,j) > 0 và
ñ$nh x s6 mang nhãn L(x). Khi kt thúc thut toán L(z) chính là chi*u
dài ng&n nht t) a ñn z .
8
1.2.3.3. Thut toán Floyd
Thut toán tìm ñ dài ñưng ñi ng&n nht gi+a mi c%p ñ$nh
trong ñ th có hưng liên thông có trng s (không b&t buc ≥ 0).
1.2.3.4. Thut toán tìm lung cc ñi (Ford-Fulkerson)
+ Đu vào. Mng G vi ngun a, ñích z, kh năng thông qua C
= (c
ij
), (i,j)∈G.
Ký hiu a = v
0
, ... , v
n
= z.
+ Đu ra. Lung cc ñi F = (f
ij
), (i,j)∈G
+ Các bưc.
Kh(i to lung xut phát: f
ij
:= 0 ∀(i,j) ∈G
Đ%t nhãn cho ngun: Cho ngun a mang nhãn a(, ∞)
Kim tra nhãn c'a ñích: Nu ñích z có nhãn, sang bưc (6).
Ngưc li sang bưc (4).
Xác ñnh ñ$nh ñánh du: Trong s các ñ$nh mang nhãn và chưa
ñưc ñánh du chn ñ$nh v
i
vi ch$ s i nh8 nht. Nu không tn ti
ñ$nh như vy, kt thúc, lung F là cc ñi. Ngưc li gán v := v
i
và
ñánh du ñ$nh v.
Đ%t nhãn các ñ$nh chưa có nhãn, k* ñ$nh v: Gi s, (α, ∆) là
nhãn c'a ñ$nh v. Xét các cung có dng (v,w), (w,v) theo th# t (v,v
0
),
(v
0
,v), (v,v
1
), (v
1
,v), ..., trong ñó w chưa ñưc mang nhãn.
Vi cung dng (v,w), nu f
vw
< c
vw
, ñ%t nhãn ñ$nh w là (v,
min{∆, c
vw
- f
vw
}), nu f
vw
= c
vw
, không ñ%t nhãn ñ$nh w.
Vi cung dng (w,v), nu f
wv
> 0, ñ%t nhãn ñ$nh w là (v,
min{∆, f
wv
}), nu f
wv
= 0, không ñ%t nhãn ñ$nh w.
Sang bưc (3).
Hiu ch$nh lung: Gi s, (β,δ) là nhãn c'a ñích z. Đ%t: w
0
:= z,
w
1
:= β