Xem mẫu
- Công trình ñư c hoàn thành t i
B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG
Đ I H C ĐÀ N NG
Ngư i hư ng d n khoa h c: PGS. TS. Võ Trung Hùng
LÊ H NG DŨNG
Ph n bi n 1: PGS. TS. Tăng T n Chi n
XÂY D NG MÔ HÌNH H TH NG XE BUÝT
TRƯ NG H C TRÊN CƠ S BÀI TOÁN
PHÂN LU NG GIAO THÔNG Ph n bi n 2: PGS. TS. Lê M nh Th nh
Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p
Chuyên ngành: KHOA H C MÁY TÍNH th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 16 tháng 6
Mã s : 60.48.01 năm 2012.
TÓM T T LU N VĂN TH C SĨ K THU T
Có th tìm hi u lu n văn t i:
• Trung tâm Thông tin - H c li u, Đ i h c Đà N ng
• Trung tâm H c li u, Đ i h c Đà N ng
Đà N ng - Năm 2012
- 1 2
M Đ U ñón các em h c sinh trung h c cơ s (THCS) c a các b c ph huynh
c n ñư c gi m thi u. Đ ng trên phương di n các b c ph huynh h c
1. Lý do ch n ñ tài
sinh th y thành ph nên có ch trương xây d ng h th ng GTCC
Trên th gi i các nhà quy ho ch ñô th ñang n l c phát tri n
dành riêng cho c p h c này ñ ñ m b o an toàn, an ninh cho h c
h th ng giao thông công c ng (GTCC) ñ c nh tranh v i phương
sinh, gi m thi u ñư c th i gian ñưa ñón các em cũng như gi m thi u
ti n giao thông cá nhân. các qu c gia ñang phát tri n, phương ti n
các phương ti n giao thông cá nhân, gi m lưu lư ng xe tham gia giao
giao thông cá nhân ti p t c gia tăng th ph n và t o thêm s c ép c nh
thông trong gi cao ñi m và gi m lư ng khí th i ñ c h i gây ô nhi m
tranh lên GTCC. T i M , GTCC ch chi m 1,8% th trư ng v n
môi trư ng.
chuy n năm 1995, so v i năm 1977 là 2,4% và năm 1983 là 2,2%.
Xu t phát t lý do ñó, tôi ñã ch n th c hi n ñ tài: “Xây d ng
M c cho hàng ch c t USD ñ u tư vào xây d ng h th ng ñư ng s t
mô hình h th ng xe buýt trư ng h c trên cơ s bài toán phân lu ng
m i và chi phí v n hành ñư c tr giá ñ n 75%, ho t ñ ng kinh doanh
giao thông”.
c a GTCC v n không m y kh i s c. S suy gi m vai trò c a GTCC
2. M c ñích nghiên c u
là m t h i chuông c nh báo cho các thành ph l n vì quá ph thu c
Xây d ng h th ng các tuy n xe buýt ph c v cho vi c ñi l i
vào phương ti n giao thông cá nhân. Nguyên nhân c a s suy gi m
c a h c sinh THCS trên ñ a bàn thành ph Đà N ng. ng d ng bài
b t ngu n t r t nhi u y u t : vi c tăng thu nh p, gi m giá thành
toán phân lu ng, tìm lu ng c c ñ i ñ mô hình hóa bài toán phân
phương ti n và chi phí ñ u ñ d n ñ n tăng kh năng s h u phương
lu ng giao thông lên ñ th . Cài ñ t thu t toán cho bài toán phân
ti n giao thông cá nhân và gi m nhu c u s d ng GTCC.
lu ng giao thông. Đánh giá k t qu ñ t ñư c c a ñ tài.
Tuy nhiên, c n ph i tìm ra ñư c gi i pháp cân b ng gi a
3. Đ i tư ng và ph m vi nghiên c u
phương ti n GTCC và phương ti n giao thông cá nhân ñô th . Đi n
Đ ñ t ñư c m c ñích trên chúng tôi xác ñ nh ñ i tư ng và
hình là Singapore và Copenhagen, hai thành ph này ñã thay ñ i mô
ph m vi nghiên c u như sau. Đ i tư ng nghiên c u c a ñ tài g m:
hình ñô th ñ phù h p v i hình th c GTCC vì nguyên nhân khan
các lo i hình giao thông công c ng b ng xe buýt, sơ ñ ñư ng ñi c a
hi m ñ t ñai, b o t n các không gian m bên c nh vi c khuy n khích
thành ph Đà N ng và nhu c u ñi l i c a c p h c THCS. Ph m vi
phát tri n ñô th và giao thông b n v ng.
nghiên c u ñư c gi i h n trong thành ph Đà N ng.
nư c ta xe buýt hi n nay ñóng m t vai trò quan tr ng trong
4. Phương pháp nghiên c u
vi c di chuy n h ng ngày c a ngư i dân thành ph . Đây là m t
Nghiên c u lý thuy t v m t s thu t toán trên ñ th : ñ th
phương ti n v n t i hành khách công c ng v a kinh t v a thân thi n
liên thông, bài toán lu ng c c ñ i trong m ng, bi u di n bài toán trên
v i môi trư ng, góp ph n tích c c vào vi c h n ch n n k t xe trong
ñ th .
thành ph . Cùng v i s phát tri n nhanh c a nư c ta, th i gian ñưa
- 3 4
Kh o sát, phân tích d li u t nhi u ngu n khác nhau. T k t CHƯƠNG 1: CƠ S LÝ THUY T Đ TH
qu phân tích ti n hành xây d ng các gi i pháp và ng d ng trong h Chương này gi i thi u ñ i cương v lý thuy t ñ th , ñư ng ñi,
th ng xe buýt ñưa ñón h c sinh THCS, cu i cùng ch y th nghi m chu trình, ñ th liên thông, các thu t toán tìm ki m trên ñ th , tìm
và lưu tr các k t qu ñ t ñư c. ki m theo chi u r ng và theo chi u sâu, các thu t toán tìm ñư ng ñi
5. Ý nghĩa khoa h c và th c ti n c a lu n văn ng n nh t, thu t toán Ford - Fulkerson tìm lu ng c c ñ i trong m ng
Ý nghĩa khoa h c: Tri n khai vi c ng d ng công ngh thông làm cơ s tính toán, xây d ng các tuy n xe buýt ph c v ñưa, ñón các
tin trong vi c gi i quy t ñư c các bài toán v lu ng c c ñ i, l a ch n em h c sinh trung h c cơ s trên ñ a bàn thành ph Đà N ng.
ñư ng ñi ng n nh t, t t nh t, t ñó xây d ng l trình cho các tuy n xe 1.1. Đ NH NGHĨA VÀ PHÂN LO I
buýt trư ng h c. 1.1.1. Đ nh nghĩa ñ th , ñư ng ñi, chu trình, ñ th liên thông
Ý nghĩa th c ti n: T o ra h th ng GTCC riêng bi t cho các 1.1.1.1. Đ nh nghĩa ñ th
em h c sinh THCS bên c nh h th ng GTCC truy n th ng, ñ gi m Đ th (graph) là m t mô hình toán h c ñư c ng d ng trong
b t th i gian ñưa ñón con em c a các b c ph huynh, gi m thi u lưu nhi u lĩnh v c khoa h c, k thu t.
lư ng phương ti n giao thông cá nhân trên ñư ng ph . Gi i quy t 1.1.1.2. Đư ng ñi và chu trình
ñư c các v n ñ xã h i: như n n k t xe, ti t ki m nhiên li u, an toàn Gi s G = (V, E) là m t ñ th .
hơn khi tham gia giao thông và gi m ñư c lư ng khí th i gây ô Đ nh nghĩa 1.6: Đư ng ñi trong ñ th là m t dãy các ñ nh:
nhi m môi trư ng. sao cho, m i ñ nh trong dãy (không k
6. B c c lu n văn ñ nh ñ u tiên) k v i ñ nh trư c nó b ng m t c nh nào ñó, nghĩa là:
N i dung chính c a lu n văn ñư c chia thành 3 chương. Trong ∀ i = 2, 3,..., k-1, k : (xi-1, xi) ∈ E.
chương 1, trình bày nh ng ki n th c t ng quan bao g m gi i thi u v Ta nói r ng ñư ng ñi này ñi t ñ nh ñ u x1 ñ n ñ nh cu i xk. S
cơ s lý thuy t ñ th , các thu t toán trên ñ th . Chương 2, phân tích c nh c a ñư ng ñi ñư c g i là ñ dài c a ñư ng ñi ñó.
hi n tr ng GTCC hi n nay trên ñ a bàn thành ph Đà N ng, v n ñ 1.1.1.3. Đ th liên thông
ñưa ñón h c sinh THCS và ñưa ra gi i pháp lu ng c c ñ i ng d ng N u gi a hai ñi m b t kỳ c a m t ñ th ñ u có th thi t l p
trong h th ng xe buýt trư ng h c. Chương 3, xây d ng ng d ng m t ñư ng ñi t ñ nh này ñ n ñ nh kia, ñ th ñư c coi là liên thông;
các tuy n c a h th ng xe xuýt trư ng h c mà c th là các trư ng n u không, ñ th ñư c coi là không liên thông. M t ñ th ñư c coi
THCS trên ñ a bàn hai qu n trung tâm c a thành ph Đà N ng là là hoàn toàn không liên thông n u không có ñư ng ñi gi a hai ñ nh
qu n H i Châu và Thanh Khê. b t kỳ trong ñ th . Đây ch là m t cái tên khác ñ miêu t m t ñ th
r ng ho c m t t p ñ c l p.
- 5 6
1.1.2. M t s d ng ñ th ñ c bi t toán tìm thành ph n liên thông c a ñ th , thu t toán tìm ñư ng ñi
1.1.2.1. Đ th ñ y ñ c a hai ñ nh.
Đ th ñ y ñ n ñ nh, ký hi u b i Kn, là ñơn ñ th vô hư ng 1.2.1.1. Thu t toán tìm ki m theo chi u sâu
mà gi a hai ñ nh b t kỳ c a nó luôn có c nh n i. 1.2.1.2. Thu t toán tìm ki m theo chi u r ng
1.1.2.2. Đ th vòng 1.2.1.3. Bài toán tìm thành ph n liên thông c a ñ th
Đ th vòng Cn, n≥3, g m n ñ nh v1, v2,....vn và các c nh (v1, Cho m t ñ th G=(V.E). Hãy cho bi t s thành ph n liên
v2), (v2, v3)... (vn-1, vn), (vn, v1). thông c a ñ th và m i thành ph n liên thông g m nh ng ñ nh nào.
1.1.2.3. Đ th bánh xe Như ta ñã bi t, các th t c DFS(u) và BFS(u) cho phép vi ng thăm
Đ th Wn thu ñư c t Cn b ng cách b sung vào m t ñ nh m i t t c các ñ nh có cùng thành ph n liên thông v i u nên s thành ph n
n i v i t t c các ñ nh c a Cn. liên thông c a ñ th chính là s l n g i th t c trên.
1.1.2.4. Đ th l p phương 1.2.1.4. Bài toán tìm ñư ng ñi gi a hai ñ nh c a ñ th
n
Đ th l p phương n ñ nh Qn là ñ th v i các ñ nh bi u di n 2 xâu Cho ñ th G=(V,E). V i hai ñ nh s và t là hai ñ nh nào ñó c a
nh phân ñ dài n. Hai ñ nh c a nó g i là k nhau n u như hai xâu ñ th . Hãy tìm ñư ng ñi t s ñ n t.
nh phân tương ng ch khác nhau 1 bit cho th y Qn v i n=1,2,3 Do th t c DFS(s) và BFS(s) s thăm l n lư t các ñ nh liên
1.1.2.5. Đ th hai phía thông v i u nên sau khi th c hi n xong th t c thì có hai kh năng:
Đơn ñ th G=(V, E) ñư c g i là hai phía n u như t p ñ nh V - N u Daxet[t] = True thì có nghĩa: T n t i m t ñư ng ñi t
c a nó có th phân ho ch thành hai t p X và Y sao cho m i c nh c a ñ nh s t i ñ nh t.
ñ th ch n i m t ñ nh nào ñó trong X v i m t ñ nh nào ñó trong Y. - Ngư c l i, thì không có ñư ng ñi n i gi a s và t.
Khi ñó ta s s d ng ký hi u G=(X∪Y, E) ñ ch ñ th hai phía v i V n ñ còn l i c a bài toán là: N u t n t i ñư ng ñi n i ñ nh s
t p ñ nh X∪Y. và ñ nh t thì làm cách nào ñ vi t ñư c hành trình (g m th t các
1.1.2.6. Đ th ph ng ñ nh) t s ñ n t.
Đ th ñư c g i là ñ th ph ng n u ta có th v nó trên m t 1.2.2. M ng, lu ng trong m ng
ph ng sao cho các c nh c a nó không c t nhau ngoài ñ nh. Cách v 1.2.2.1. M ng lu ng
như v y s ñư c g i là bi u di n ph ng c a ñ th . M ng lu ng là m t ñ th có hư ng, trong ñó m i c nh có m t
1.2. CÁC THU T TOÁN CƠ B N TRÊN Đ TH ñ thông qua và m t giá tr lu ng. Lư ng lu ng trên m i c nh không
1.2.1. Thu t toán tìm ki m trên ñ th ñư c vư t quá ñ thông qua c a c nh ñó. Lư ng lu ng ñi vào m t
Gi i thi u m t s thu t toán tìm ki m trên ñ th : thu t toán ñ nh ph i b ng lư ng lu ng ñi ra kh i nó, tr khi ñó là ñ nh ngu n
tìm ki m theo chi u sâu, thu t toán tìm ki m theo chi u r ng, thu t (có nhi u lư ng lu ng ñi ra hơn), hay ñ nh ñích (có nhi u lư ng
- 7 8
lu ng ñi vào hơn). M ng lu ng có th dùng ñ mô hình hóa h th ng 1.2.3.3. Thu t toán Floyd
ñư ng giao thông, dòng ch y c a ch t l ng trong ng, dòng ñi n Thu t toán tìm ñ dài ñư ng ñi ng n nh t gi a m i c p ñ nh
trong m ch, hay b t kỳ các bài toán nào tương t khi có s di chuy n trong ñ th có hư ng liên thông có tr ng s (không b t bu c ≥ 0).
trong m t m ng các nút. 1.2.3.4. Thu t toán tìm lu ng c c ñ i (Ford-Fulkerson)
1.2.2.2. Bài toán lu ng c c ñ i trong m ng + Đ u vào. M ng G v i ngu n a, ñích z, kh năng thông qua C
T n t i m t ñư ng ñi t ngu n (nút b t ñ u) ñ n ñi m x (nút = (cij), (i,j)∈G.
cu i), v i ñi u ki n t t c các cung trên ñư ng ñi ñó v n còn kh Ký hi u a = v0, ... , vn = z.
năng thông qua, thì ta s g i ñi m t lu ng d c theo ñư ng ñi ñó. Sau + Đ u ra. Lu ng c c ñ i F = (fij), (i,j)∈G
ñó chúng ta tìm m t ñư ng ñi khác, và ti p t c như v y. M t ñư ng + Các bư c.
ñi còn kh năng thông qua là m t ñư ng ñi có kh năng m r ng Kh i t o lu ng xu t phát: fij := 0 ∀(i,j) ∈G
thêm hay m t ñư ng ñi mà lu ng qua ñó còn kh năng tăng thêm g i Đ t nhãn cho ngu n: Cho ngu n a mang nhãn a(, ∞)
t t là ñư ng tăng. Ki m tra nhãn c a ñích: N u ñích z có nhãn, sang bư c (6).
1.2.3. Các thu t toán tìm ñư ng ñi ng n nh t Ngư c l i sang bư c (4).
1.2.3.1. Phát bi u bài toán Xác ñ nh ñ nh ñánh d u: Trong s các ñ nh mang nhãn và chưa
Cho ñ th có tr ng s G=(V,E). Ký hi u w(i,j) là tr ng s c a ñư c ñánh d u ch n ñ nh vi v i ch s i nh nh t. N u không t n t i
c nh (i,j). Đ dài ñư ng ñi µ = v0→v1→v2→... →vn-1→vn là t ng các ñ nh như v y, k t thúc, lu ng F là c c ñ i. Ngư c l i gán v := vi và
tr ng s ñánh d u ñ nh v.
n Đ t nhãn các ñ nh chưa có nhãn, k ñ nh v: Gi s (α, ∆) là
L(µ) = ∑w(vi−1, vi ) nhãn c a ñ nh v. Xét các cung có d ng (v,w), (w,v) theo th t (v,v0),
i=1
(v0,v), (v,v1), (v1,v), ..., trong ñó w chưa ñư c mang nhãn.
Cho hai ñ nh a, z c a ñ th . Bài toán ñ t ra là tìm ñư ng ñi
V i cung d ng (v,w), n u fvw < cvw, ñ t nhãn ñ nh w là (v,
ng n nh t t a ñ n z.
min{∆, cvw - fvw}), n u fvw = cvw, không ñ t nhãn ñ nh w.
1.2.3.2. Thu t toán Dijkstra
V i cung d ng (w,v), n u fwv > 0, ñ t nhãn ñ nh w là (v,
Thu t toán tìm ñư ng ñi ng n nh t t ñ nh a ñ n ñ nh z trong
min{∆, fwv}), n u fwv = 0, không ñ t nhãn ñ nh w.
ñ th liên thông có tr ng s . Tr ng s c a c nh (i,j) là w(i,j) > 0 và
Sang bư c (3).
ñ nh x s mang nhãn L(x). Khi k t thúc thu t toán L(z) chính là chi u
Hi u ch nh lu ng: Gi s (β,δ) là nhãn c a ñích z. Đ t: w0 := z,
dài ng n nh t t a ñ n z .
w1 := β
- 9 10
N u nhãn c a wi là (β',∆'), thì ñ t wi+1 := β'. Ti p t c quá trình - xij = 1, n u b trí ti u ban i làm vi c phòng j.
cho ñ n khi wk = a. Đ n ñây ta nh n ñư c ñư ng ñi P t a ñ n z - xij = 0, n u ngư c l i.
P = (a= wk, wk-1, ... , w1, w0= z) V i i=1, 2,...,m ; j=1, 2,...,n, khi ñó d th y mô hình toán h c cho
Ký hi u δ là nhãn th hai nh nh t c a các ñ nh trên P. bài toán ñ t ra chính là bài toán (1)-(2), trong ñó pi =1, i=1, 2,...,m.
Ta hi u ch nh lu ng f trên P như sau: 1.4. T NG K T CHƯƠNG 1
Trong chương này ñã trình bày v lý thuy t ñ th : Chu trình,
ñ th liên thông, các thu t toán tìm ki m trên ñ th , tìm ki m theo
chi u r ng và theo chi u sâu, các thu t toán tìm ñư ng ñi ng n nh t
và thu t toán Ford - Fulkerson tìm lu ng c c ñ i trong m ng. M t s
Sau ñó xoá t t c nhãn c a các ñ nh trên P và quay l i bư c (2). ng d ng trong th c t c a thu t toán Ford – Fulkerson như t ch c
Đ nh lý 2. N u các giá tr thông qua cij là s nguyên, thì sau m ng v n chuy n bưu chính, bài toán l p l ch cho h i ngh . D a trên
m t s bư c h u h n quá trình gi i k t thúc. c s lý thuy t và th c ti n trên ta xây d ng tuy n xe buýt trong n i
H qu . N u giá tr thông qua cij là s h u t v i m i (i,j) ∈ E, ñô ñ ph c v v n chuy n ñưa ñón h c sinh c p trung h c cơ s .
thì sau m t s bư c h u h n quá trình gi i k t thúc. Trong chương 2 s gi i thi u v gi i pháp ng d ng lu ng c c
1.3. M T S NG D NG LÝ THUY T Đ TH ñ i trong qui ho ch h th ng xe buýt trư ng h c.
TRONG TH C T
1.3.1. ng d ng lý thuy t ñ th trong t ch c m ng v n
chuy n bưu chính
1.3.2. Bài toán ñám cư i vùng quê
1.3.3. Bài toán l p l ch cho h i ngh
M t h i ngh có m ti u ban, m i ti u ban c n sinh ho t trong
m t ngày t i phòng h p phù h p v i nó. Có n phòng h p dành cho
vi c sinh ho t c a các ti u ban. Bi t:
- aij = 1, n u phòng h p i là thích h p v i ti u ban j
- aij = 0, n u ngư c l i
V i i = 1, 2,...,m, j = 1, 2,..., n. Hãy b trí các phòng h p cho
các ti u ban sao cho h i ngh k t thúc sau ít ngày làm vi c nh t.
Đưa vào các bi n s :
- 11 12
2.1.2. Các tuy n xe buýt hi n t i trên ñ a bàn thành ph Đà N ng
CHƯƠNG 2: GI I PHÁP
NG D NG LU NG C C Theo s li u c a s giao thông v n t i thành ph Đà N ng,
Đ I TRONG QUY HO CH H TH NG XE BUÝT hi n nay trên ñ a bàn thành ph và vùng ph c n có các tuy n xe buýt
TRƯ NG H C sau:
Tuy n s 1: Đà N ng - H i An và ngư c l i
Trong chương này s phân tích hi n tr ng v h th ng xe buýt
Tuy n s 2: Kim Liên – Ch Hàn và ngư c l i
trên ñ a bàn thành ph Đà N ng và h th ng xe buýt ñưa ñón h c
Tuy n s 3: Đà N ng – Đ i L c
sinh c a m t s trư ng ph thông hi n nay. Th ng kê và phân tích
Tuy n s 4: Đà N ng – Tam Kỳ
các s li u v m t v trí ñ a lý, ñư ng ñi hi n t i, chi phí v n chuy n
Tuy n s 5: Đà N ng - M Sơn
và th i gian v n chuy n. Sau ñó ñ ra gi i pháp m i, tri n khai các
2.1.3. T i sao c n có h th ng xe buýt riêng cho h c sinh
gi i pháp m i, ñ th hóa v trí ñ a lý và chuy n hóa sơ ñ v d ng ký
Do s lư ng h c sinh ñ l n và có nhu c u ñi l i b ng h th ng
hi u, ng d ng các ký hi u v a chuy n hóa vào thu t toán Ford–
giao thông riêng. Gi m m t ñ giao thông b ng các phương ti n giao
Fulkerson tìm lu ng c c ñ i trong m ng.
thông cá nhân trong gi cao ñi m d n ñ n gi m thi u v n ñ k t xe.
2.1. PHÂN TÍCH HI N TR NG
Đ tin c y cao, an toàn, an ninh t t và ít tai n n hơn các lo i giao
2.1.1. Xu hư ng phát tri n v n t i hành khách công c ng
thông b ng phương ti n giao thông cá nhân. Xét v m t b o v môi
Đô th hoá là m t xu hư ng t t y u c a quá trình công nghi p
trư ng thì h th ng xe buýt ch y b ng năng lư ng khí thiên nhiên
hoá hi n ñ i hoá ñ t nư c. Đ i v i các nư c ñang phát tri n quá trình
nén (CNG) r t ít gây ô nhi m môi trư ng vì lư ng khí th i CO và No
ñô th hoá di n ra h t s c m nh m trong ñó có Vi t Nam. Xu hư ng
r t ít. V m t tiêu hao nhiên li u và kinh t thì chi phí nhiên li u cho
ñô th hoá ngày càng gia tăng s d n ñ n nh ng s c ép l n v nhi u
xe s d ng năng lư ng CNG giá thành th p hơn 35 ñ n 40% xe ch y
m t trong ñó có giao thông v n t i ñô th . Hi n t i Vi t Nam, giao
b ng xăng. V th i gian, ph huynh không ph i t n th i gian ñưa ñón
thông v n t i ñã ñang là m t yêu c u b c bách, m t thách th c l n
mà các em s t ñi h c ñư c.
ñ i v i các ñô th .
2.1.4. S lư ng h c sinh các trư ng THCS trên ñ a bàn thành
H th ng xe buýt công c ng hi n có chưa ñư c ph bi n, ch
ph Đà N ng
y u v n chuy n công c ng. Đ gi m b t phương ti n cá nhân và m t
Sau ñây là m t s th ng kê v s lư ng h c sinh và ñ a ñi m
ñ xe c tham gia giao thông, gi m ñư c th i gian ph i ñưa ñón các
c a các trư ng THCS trên thành ph Đà N ng. Các b ng s li u do
em h c sinh, gi m thi u r i ro. C n xây d ng thêm h th ng xe buýt
S Giáo D c và Đào T o thành ph Đà N ng cung c p d a theo danh
ñ ph c v ñưa ñón nh ng em h c sinh THCS.
sách nh p h c năm h c 2011-2012.
- 13 14
2.1.4.1. Qu n H i Châu Xác ñ nh ñi m Xác ñ nh l Xác ñ nh ñi m Ki m tra s
ñ u cu i trình tuy n ñ d c ñư ng phù h p
2.1.4.2. Qu n Thanh Khê
2.1.4.3. Qu n C m L
2.1.4.4. Qu n Ngũ Hành Sơn
Hình 2.1. Quy trình xây d ng các tuy n xe buýt
2.1.4.5. Qu n Sơn Trà
2.2.4. Xác ñ nh các ñi m ñ u cu i c a tuy n
2.1.4.6. Huy n Hòa Vang
Đi m ñ u và ñi m cu i c a tuy n ñóng vai trò quan tr ng cho
2.1.5. Đ xu t gi i pháp xây d ng h th ng xe buýt
ho t ñ ng c a tuy n. Ngoài ch c năng chung ñ h c sinh lên xu ng,
Xây d ng thêm m t h th ng xe buýt ch dành riêng cho vi c
b trí ñ xe còn có ch c năng ñ m b o quay tr ñ u xe d dàng, ñi u
ñưa ñón các em h c sinh THCS s mang l i ñ tin c y cao v an toàn,
ph i xe ki m tra hành trình ch y xe và ñ m b o không c n tr giao
an ninh hơn. Ch ñư c nhi u h c sinh, gi m di n tích chi m m t
thông. Thư ng ñư c b trí nh ng nơi có lưu lư ng h c sinh t p
ñư ng c a các phương ti n cá nhân tham gia giao thông, chi phí v n
trung cao ñ d dàng cho vi c di chuy n.
hành r , t o ñi u ki n cho vi c s d ng “nhiên li u xanh” góp ph n
Sau khi kh o sát và căn c vào các y u t trên tôi th y r ng có
ch ng ô nhi m môi trư ng. Thông tin tuyên truy n ñ ph huynh h c
th l a ch n ñi m ñ u và ñi m cu i như sau:
sinh ch p nh n cho con em s d ng xe buýt và giá vé phù h p.
Đi m ñ u: B n xe Trung tâm – Đi m cu i: Nguy n T t Thành.
2.2. Đ XU T GI I PHÁP
Đi m ñ u: Hà Huy T p (n i dài) – Đi m cu i: Nguy n H u
2.2.1. Danh sách các trư ng s d ng h th ng xe buýt trư ng h c
Th .
2.2.2. Sơ ñ v m t ñ a lý
Đi m ñ u: Nguy n T t Thành – Đi m cu i: Nguy n H u Th .
D a trên ñ a ch c a các trư ng ta ñánh d u ñư c các v trí
Đi m ñ u: Trung tâm tri n lãm – Đi m cu i: Siêu th Đà N ng.
c a trư ng lên b ng ñ b ng ñ google maps
2.2.5. Xác ñ nh l trình tuy n
2.2.3. Quy trình xây d ng các tuy n xe buýt
L trình tuy n ph i ñ m b o cho hành khách ñi l i theo các
Vi c xây d ng thi t k m t tuy n xe buýt bao g m r t nhi u
hư ng chính m t cách liên t c không ph i chuy n tuy n, hay s l n
n i dung và nhi u phương pháp khác nhau, trong m i phương pháp
chuy n tuy n là t i thi u.
l i có ưu như c ñi m khác nhau cho nên ñòi h i c n có s h p lí
N i li n các khu trung tâm thu hút hành khách v i c ly ñi l i
trong vi c l a ch n xây d ng m i tuy n xe buýt. Hi n nay vi c xây
bình quân c a hành khách là nh nh t.
d ng tuy n xe buýt Vi t Nam ch y u là theo phương pháp kinh
Đ m b o thu n ti n cho hành khách khi chuy n tuy n ho c khi
nghi m và tuỳ theo t ng ñ tài có th l a ch n nh ng phương pháp
chuy n phương th c v n t i (tính liên thông).
khác nhau. Nó ñư c ti n hành theo trình t sau.
Sơ ñ xây ñ ng tuy n xe buýt:
- 15 16
Đ tho mãn các yêu c u trên, thông thư ng khi xác ñ nh h c sinh c a m t s trư ng ph thông hi n nay. Th ng kê và phân
ñư ng ñi c a tuy n ph i căn c vào m t s ch tiêu ñ c trưng khi xây tích ñư c các s li u th c t v m t: V trí ñ a lý, ñư ng ñi, chi phí
d ng tuy n: v n chuy n và th i gian v n chuy n.
+ Chi u dài tuy n. Trong chương ti p theo, trình bày cách xây d ng ng d ng l
+ Kh i lư ng v n chuy n trên tuy n. trình tuy n xe buýt trư ng h c.
+ Kho ng th i gian v n chuy n trên tuy n. CHƯƠNG 3: XÂY D NG NG D NG ĐI U TI T
+ S phân b khách theo hành trình. H TH NG XE BUÝT TRƯ NG H C
2.2.5.1. L trình tuy n 1
Trong chương này chúng tôi xây d ng các tuy n xe buýt
2.2.5.2. L trình tuy n 2
trư ng h c d a trên nhu c u ñi l i c a c p h c THCS, qua quan tr c
2.2.5.3. L trình tuy n 3
các tuy n ñư ng, các ch s v s phân b h c sinh trên tuy n, áp
2.2.5.4. L trình tuy n 4
d ng thu t toán Ford - Fulkerson tìm lu ng c c ñ i trong m ng làm
2.2.5.5. L trình tuy n 5
cơ s tính toán, xây d ng các tuy n xe buýt ph c v ñưa, ñón các em
2.2.6. B trí các ñi m d ng d c ñư ng
h c sinh trung h c cơ s trên ñ a bàn thành ph Đà N ng nh m m c
Các ñi m d ng ñ d c ñư ng c a tuy n s ñư c b trí t i các
ñích xây d ng các tuy n c n thi t ñ ch ñư c nhi u h c sinh nh t,
v trí có s thu hút l n ñ i v i hành khách, hành khách lên xu ng
gi m ñư c lư ng xe cá nhân, gi m ùn t c giao thông trong gi cao
nhi u thu n l i cho vi c chuy n tuy n c a hành khách t tuy n này
ñi m. H c sinh có th l a ch n tuy n xe và th i gian phù h p t nhà
sang tuy n khác.
ñ n trư ng và ngư c l i.
Các ñi m ñ này ph i b trí ñ m b o an toàn v n hành cho
3.1. KI N TRÚC T NG TH C A H TH NG
phương ti n v n hành và ngư i ñi l i, nh hư ng ít nh t ñ n các
3.1.1. Ki n trúc t ng th
phương ti n ñi l i trên ñư ng.
Thành ph Đã N ng là thành ph phát tri n và ñông dân c a
S lư ng các ñi m d ng ñư c tính b ng công th c sau:
Vi t Nam, v i cơ s h t ng giao thông thông thoáng, thu n ti n. Do
N = L / l0 - 1.
ñó vi c phát tri n h th ng xe buýt r t thu n l i nh có h th ng
Trong ñó: L : Chi u dài tuy n.
ñư ng xá ñư c qui ho ch m t cách t ng th và an toàn cho vi c ñi b
L0: Kho ng cách gi a các ñi m ñ .
c a nh ng ngư i ñi xe buýt, nghĩa là ngư i ta có th ñi b trên v a hè
N : S lư ng các ñi m ñ .
ñ ñ n b n xe buýt ho c t b n xe buýt v nhà.
2.3. T NG K T CHƯƠNG 2
Trong chương này ñã phân tích ñư c hi n tr ng v h th ng
xe buýt trên ñ a bàn thành ph Đà N ng và h th ng xe buýt ñưa ñón
- 17 18
b t ñ u – b n xe trung tâm thành ph , ñi ñ n trư ng Phan Đình
Phùng” ñ minh h a.
V i ño n ñư ng ñi này, th c hi n chuy n sang mô hình ñ th
và áp d ng gi i thu t lu ng c c ñ i ñ xây d ng ñư ng ñi. Trong ñó:
- Đi m xu t phát: b t ñ u – b n xe trung tâm thành ph
- Đi m ñích: trư ng Phan Đình Phùng
T ñi m xu t phát ñ n ñi m ñích, xe buýt ph i ñi qua các tr m
d ng ñư c xây d ng trên các con ñư ng. M i tr m d ng là m t ñ nh
trên ñ th .
- Các c nh trên ñ th là ñư ng ñi n i gi a các ñ nh.
- Tr ng s c a ñ th ñư c tính toán d a trên các y u t : s
lư ng h c sinh phân b trên các tuy n, các cung ñư ng thư ng xuyên
x y ra k t xe, các cung ñư ng có m t ñ giao thông cao, ñ dài
Hình 3.1. Mô hình t ng quan các tuy n xe buýt trong h th ng ñư ng ñi. M c ñ ưu tiên c a tr ng s theo th t t l n t i nh như
3.1.2. Các thành ph n c a h th ng sau: s lư ng h c sinh phân b trên các tuy n ưu tiên trư c; các cung
Các thành ph n c a h th ng bao g m nh ng bãi ñ xe t i các ñư ng thư ng x y ra k t xe; ñư ng có m t ñ giao thông cao; ñ dài
tr m ñ u cu i c a tuy n, các tr m ñ trên tuy n, lo i xe s d ng ñư ng ñi.
trong h th ng. Các cung ñư ng thông qua các ñi m d ng ñ ñón h c
B ng 3.1. B ng th ng kê các tr ng s
sinh, các cung ñư ng thư ng x y ra k t xe ho c m t ñ giao thông
cao, các cung ñư ng ch y qua vùng ñông dân cư và có s lư ng h c S lư ng h c K t M t ñ giao Đ
sinh phân b nhi u. sinh phân b xe thông cao dài
3.2. TH NGHI M H TH NG (ngư i) (Km)
3.2.1. Mô t bài toán Tôn Đ c Th ng 32 2 4 1
Chúng ta th y, m i ño n ñư ng ñi c a xe buýt có ñi m b t ñ u Đi n Biên Ph 50 0 6 1,5
và ñi m ñích ñ n. Đ xây d ng tuy n xe buýt, chúng ta s mô hình Tr n Cao Vân 235 1 2 4
hóa vi c xây d ng tuy n xe buýt trên m t ño n c th . Các ño n còn Ông Ích Khiêm 75 1 2 2
l i áp d ng tương t . ñây, chúng ta ch n ño n “xu t phát t tr m Nguy n T t Thành 20 0 4 0,5
- 19 20
Gi i thích: Các tr ng s t nh ñ n l n th hi n m t ñ giao T k t qu trên, ta xây d ng tuy n xe buýt tương ng: ñi m
thông t th p ñ n cao, m c ñ k t xe t ít t i nhi u. xu t phát, b n xe trung tâm tr m d ng ñón khách t i ngã ba Hu
3.2.2. Mô hình bài toán tr m d ng ñón khách t i ngã tư Thanh Khê–Tr n Cao Vân
D a vào phân tích trên ta có mô hình ñ th cho bài toán như trư ng THCS Phan Đình Phùng.
sau: 3.2.5. Phân tích các ch tiêu kinh t
4
3 2 5 3.2.5.1. Xác ñ nh nhu c u v n ñ u tư phương ti n
Xu hư ng hi n nay c a hành khách là mu n ñi trên nh ng xe
1 1 thoáng mát, có ñ an toàn cao, trên xe không quá ñông ngư i, xe
2 2
ch y b ng nhiên li u khí nén thiên nhiên (CNG) ít gây ô nhi m môi
5 4 trư ng. Vì lí do trên và cũng qua kh o sát th c t cơ s h t ng trên
3 7 tuy n, ñ xu t dùng lo i xe buýt trung bình 80 ch , lo i xe ch y b ng
khí nén thiên nhiên CNG, ít t n chi phí nhiên li u, gi m lư ng khí
Hình 3.2. Mô hình các tuy n ñư ng lên ñ th th i gây ô nhi m môi. Giá c a lo i xe này là: 2.400.000.000VNĐ/xe.
Trong ñó các ñ nh ñ th ñư c mô t như sau: V y t ng chi phí ñ u tư cho phương ti n ho t ñ ng trên tuy n: Vpt =
- Đ nh (1): Đi m xu t phát, b n xe trung tâm 2.400.000.000 * 10 = 24.000.000.000 VNĐ.
- Đ nh (2): Tr m d ng ñón khách t i ngã ba Hu 3.2.5.2. Nhu c u v n ñ u tư cơ s h t ng
- Đ nh (3): Tr m d ng ñón khách t i Hà Huy T p Nhu c u ñ u tư xây d ng cơ b n
- Đ nh (4): Tr m d ng ñón khách t i ngã tư Thanh Khê – Tr n + Khu bãi ñ xe
Cao Vân + Khu b o dư ng s a ch a.
- Đ nh (5): Trư ng Phan Đình Phùng + Khu văn phòng.
Tr ng s các ñ nh ñư c thi t l p d a vào B ng 3.1. trên. 3.2.6. Đánh giá hi u qu c a d án
3.2.3. Thu t toán lu ng c c ñ i 3.2.6.1. Chi phí v n hành tuy n
Mã ngu n thu t toán tìm lu ng c c ñ i trong m ng xem ph Đ nh m c chi phí v n hành tuy n ti n lương lao ñ ng tham gia
l c A. trên tuy n:
3.2.4. K t qu th nghi m B ng 3.2. B ng chi phí ti n lương LĐ tr c ti p
Áp d ng gi i thu t trên ñ th ta thu ñư c giá tr lu ng c c ñ i TT Lo i lao ñ ng S Lương Lương năm
lư ng tháng
là 9. Tương ng v i ñư ng ñi trên ñ th : 1 2 4 5.
1 Lái xe 10 74.401.000 892.812.000
2 Ph xe 10 41.161.000 493.932.000
- 21 22
3 Giám sát 2 6.412.000 76.944.000 3.2.6.3. Hi u qu kinh t , xã h i và môi trư ng c a d án
4 Th b o dư ng 2 6.180.000 74.160.000 H u h t các nhà khoa h c, các nhà qu n lý và m i ngư i dân
5 Lao ñ ng qu n lí 3 7.763.000 93.156.000 ñ u hi u và kh ng ñ nh VTHKCC b ng xe buýt mang l i m t l i ích
T ng 27 135.917.000 1.631.004.000
kinh t xã h i r t l n. Tuy nhiên, cho ñ n nay t t c m i c g ng
V y chi phí ti n lương trong 1 năm là: 1.631.004.000 VNĐ.
nh m lư ng hóa nh ng giá tr l i ích này cũng m i ch d ng l i
3.2.6.2. Doanh thu
m c ñ xác l p ñư c nh ng công th c th c nghi m, phù h p v i
M i h c sinh ñăng ký ñi xe buýt ñư c tính như sau:
nh ng ñi u ki n riêng bi t, ñ c trưng c a t ng ñô th .
Vé h c kỳ: M i h c kỳ 19 tu n, m i tu n 5 bu i, m i bu i hai
Phát tri n lĩnh v c VTHKCC góp ph n:
lư t ñi xe (ñi và v ), m i lư t ñi xe có cư c 5.000 ñ ng.
- Gi m t c ngh n giao thông.
Vé năm h c: M i năm h c có 37 tu n và ñư c gi m 20% so
- Gi m thi u ô nhi m môi trư ng.
v i vé h c kỳ ta có b ng sau:
- Nâng cao an toàn giao thông ñô th .
B ng 3.3. Các hình th c vé
3.2.6.4. Đánh giá hi u qu phương án
Lo i vé Vé h c kỳ Vé năm
V y có th nói r ng vi c ñưa ñón h c sinh THCS b ng xe buýt
Đ i tư ng
là gi i pháp h u hi u nh t trong vi c gi i quy t nh ng v n ñ nan
H c sinh 950.000 1.520.000
gi i v giao thông v n t i như: ách t c giao thông, ô nhi m môi
D báo năm ñ u doanh thu cho 10 xe, vé lư t tính 7.000 ñ ng, trư ng, tai n n giao thông, cũng như ñem l i l i ích kinh t chung
vé tháng tính 6.000 ñ ng, vé h c kỳ tính 5.000 ñ ng, vé năm tính cho toàn xã h i. Thi t k m t tuy n xe buýt tiêu chu n trong giai
b ng vé h c kỳ gi m ñi 10%. D báo xe ho t ñ ng trên tuy n trung ño n hi n nay là m t ph n trong qui ho ch chung c a thành ph , nó
bình ch ñư c 75% công xu t chuyên ch c a xe (xe 80 ch ). Vé h c ñem l i hi u qu nh t ñ nh ñ i v i vi c ñưa ñón h c sinh THCS b ng
kỳ chi m 50% và vé năm chi m 50%. Ta có b ng doanh thu năm như xe buýt nói riêng và giao thông v n t i ñô th nói chung. Phương án
sau:
thi t k tuy n b ng xe buýt tiêu chu n ñã ñem l i hi u qu sau:
B ng 3.4. B ng d báo năm ñ u doanh thu Đ i v i s phát tri n h th ng xe buýt ñưa ñón h c sinh THCS
TT Các ch tiêu Đơn v Thành ti n trong thành ph hi n nay, phương án thi t k các tuy n xe buýt góp
1 Doanh thu vé h c kỳ VNĐ 660.000.000 ph n hoàn thi n m ng lư i và hoà m ng chung vào m ng lư i
2 Doanh thu vé năm h c VNĐ 594.000.000 VTHKCC trong thành ph , qui ho ch m ng lư i tuy n xe buýt là
3 Doanh thu bình quân 1 chuy n xe VNĐ 1.181.000.000 vi c thi t k ra nh ng tuy n xe buýt nh m ñáp ng nhu c u ñi l i c a
4 Doanh thu 1 năm/1 xe VNĐ 2.435.000.000 h c sinh ñang ngày m t gia tăng hi n nay.
- 23 24
V m t kinh t : Nó không ch mang l i hi u qu kinh t trong tuy n xe buýt th c t , mô ph ng mô hình tuy n xe buýt giúp d dàng
gi i h n ho t ñ ng s n su t kinh doanh c a công ty mà còn ñem l i trong công tác qu n lý.
hi u qu chung cho toàn xã h i. 2. Ph m vi ng d ng
+ Ti t ki m nh p kh u phương ti n cá nhân. Chương trình ñư c xây d ng ch y u ñ ph c v nhu ñ u ñi l i
+ Ti t ki m chi phí nhiên li u, gi m t c ñ tiêu dùng nhiên c a các em h c sinh THCS b ng h th ng giao thông công c ng là xe
li u. Ti t ki m chi phí xã h i. buýt. Chương trình có th phát tri n, m r ng cho các trư ng khác
V m t môi trư ng - xã h i: trên ñ a bàn thành ph Đà N ng.
+ Khi tuy n ñi vào ho t ñ ng s gi m ñư c tiêu hao nhiên li u 3. Hư ng phát tri n
do gi m lư ng khí th i và ti ng n, nâng cao s c kho cho con ngư i. Ti p t c nghiên c u nhu c u ñi l i và xây d ng l i m ng lư i
+ Vi c ñi l i b ng phương ti n VTHKCC trong ñô th là nét tuy n xe buýt trư ng h c cho xác v i th c t . Nghiên c u m i quan
văn minh trong ñi l i c a ngư i dân trong xã h i th hi n s phát h gi a hình th c t ch c giao thông b ng xe buýt ñưa ñón h c sinh
tri n c a ñô th . Nó t o nên m t n p s ng m i nét ñ c trưng trong THCS và hình th c giao thông công c ng ñ k t h p ph c v chung
sinh ho t ñ i s ng thư ng ngày. trong các tuy n có m t ñ phương ti n giao thông cao. Nghiên c u
3.3. T NG K T CHƯƠNG 3 m i quan h gi a hình th c t ch c giao thông b ng xe buýt v i các
Trong chương này tôi ñã xây d ng ñư c tuy n xe buýt t b n lo i hình giao thông công c ng khác.
xe trung tâm ñ n trư ng THCS Phan Đình Phùng trên cơ s ng Xây d ng chương trình qui ho ch m ng lư i giao thông công
d ng thu t toán Ford – Fulkerson tìm lu ng c c ñ i trong m ng. c ng ñ có th ñi u ch nh h th ng thích h p trong tình hình nhu c u
K t qu ñ t ñư c: Xây d ng ñư c tuy n kh d ng ñ ñưa ñón ñi l i gia tăng và m ng lư i giao thông thư ng xuyên thay ñ i, m
h c sinh. Xây d ng chương trình mô ph ng tuy n xe buýt giúp ñ nh r ng, phân lu ng l i các tuy n và h th ng ñư ng m i ñư c xây d ng
tuy n ñư c tr c quan và d dàng trong công tác qu n lý hay phát ñ nâng cao hi u qu kinh t , phát tri n xã h i, ñáp ng nhu c u ñi
tri n v sau. l i, an ninh, an toàn trong giao thông.
K T LU N Xây d ng h th ng phân lu ng giao thông, qu n lý tuy n có
th ch y ñư c trên môi trư ng m ng Internet, ñ phát tri n và tri n
1. Đánh giá k t qu
khai r ng. Phát tri n h th ng theo tiêu chu n chung ñ ph c v xã
Lu n văn ñã trình bày ñư c cơ s lý thuy t ñ th và m t s
h i.
thu t toán trên ñ th . Phân tích hi n tr ng v xe buýt công c ng trên
ñ a bàn thành ph t ñó phát tri n h th ng xe buýt dành riêng cho
h c sinh trung h c cơ s , tri n khai các gi i pháp, xây d ng ñư c
nguon tai.lieu . vn
