公交線路乘車方案查詢系統(tǒng)設(shè)計與實現(xiàn)

1、 公交線路乘車方案查詢系統(tǒng)設(shè)計與實現(xiàn)一、實驗目的開發(fā)一個信息更新及時、界面友好、查詢優(yōu)化的公交查詢系統(tǒng)，系統(tǒng)具備的基本功能是：1、公交線路的數(shù)據(jù)輸入與維護：線路的錄入，修改，編輯功能；2、公交線路的查詢：自動，快速，靈活的查詢功能；3、乘車方案查詢：起始站點線路查詢，設(shè)定中轉(zhuǎn)站點查詢，最短路徑查詢功能。 在開發(fā)系統(tǒng)的過程中使學生能對以下知識進行鞏固和擴充：1，數(shù)據(jù)庫理論知識；應用數(shù)據(jù)庫理論對具體問題具體分析，設(shè)計出合理的數(shù)據(jù)庫結(jié)構(gòu)。2，數(shù)據(jù)結(jié)構(gòu)理論知識；根據(jù)具體問題提出合理的數(shù)據(jù)結(jié)構(gòu)，并使用相應處理方法,理解圖和和圖相關(guān)的搜索算法。3，算法設(shè)計與分析理論知識；對于不同的查詢優(yōu)化算法進行分析,選

2、用合適的算法。4，程序設(shè)計理論知識；系統(tǒng)的最終實現(xiàn)需要編程環(huán)境，不同程序語言的選用可以更好的理解程序設(shè)計的相關(guān)知識。二、實驗內(nèi)容1、數(shù)據(jù)庫結(jié)構(gòu)設(shè)計；由于公交線路查詢系統(tǒng)中所涉及的信息較多，它們之間的性質(zhì)并不完全相同或者類似，勢必造成信息冗余，但是為了系統(tǒng)提高查詢速度和便利，可以犧牲存儲空間，加快查詢速度的方法。表8-1公交線路表(line)字段中文名字段英文名字段類型字段長度容許空路線編號line_idint4路線名稱line_namevarchar50 始發(fā)車fristbusvarchar50末班車lastbusvarchar50站點1station1varchar50站點2station2

3、varchar50站點3station3varchar50varchar50varchar50varchar50站點45station45varchar50表8-2站點表（stop）字段中文名英文字段名字段類型長度容許空站點編號stop_idint4站點名稱stop_namevarchar50表8-3路線站點表(linestops)字段中文名英文字段名字段類型長度容許空路線編號line_idint4站點編號stop_idint4標記ordint42、數(shù)據(jù)結(jié)構(gòu)設(shè)計；1)通過程序?qū)ine表中的所有數(shù)據(jù)（站點）信息存放入一個一維數(shù)組中；2)編寫程序再將該數(shù)組中所有相同的數(shù)據(jù)刪除，這樣就有了站點(s

4、top)表；3)將line表中的每條線路的站點一個一個記錄下來存放入一個三列的二維數(shù)組中，如（1,火車站,1）表示：（線路編號：1；站名：火車站；線路所經(jīng)站號：1）；4)對二維數(shù)組的第二列值進行修改，參照stop表，將其字符全部換為stop_id。3、算法設(shè)計 ；1）起始站點查詢算法第一步：查詢經(jīng)過這兩個站點的所有公交線路，找出含有相同的線路編號的線路信息。第二步：判斷以上查詢中是否有滿足要求的記錄，若有，則記錄兩站點在線路中的位置，判斷是否滿足行駛方向的要求，通過定義一個數(shù)組，將線路信息中的線路名稱，起始和目的站點名稱以及兩站點之間的站點個數(shù)存入數(shù)組并輸出。若沒有滿足的記錄，證明查詢的站點之

5、間不能直達，線路需要轉(zhuǎn)乘。第三步：查詢出兩站點之間所有線路的站點交集（中轉(zhuǎn)站點），將這些站點存放入一個一維數(shù)組中，查詢從起始站點到達中轉(zhuǎn)站點的所有公交線路，將線路信息中的線路名稱，起始和中轉(zhuǎn)站點名稱以及兩站點之間的站點個數(shù)存入一個二維數(shù)組；再查詢從中轉(zhuǎn)站點到達目的站點的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點和目的站點名稱以及兩站點之間的站點個數(shù)存入另一個二維數(shù)組。第四步：判斷兩組路線之間是否有相同的站點，相同的站點即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。2）指定中轉(zhuǎn)站點查詢算法：第一步：查詢經(jīng)過起始和中轉(zhuǎn)站點的所有公交線路，將符合查詢條件的線路信息中的線路名稱，起始和中轉(zhuǎn)站點名稱以及兩站點之間的站

6、點個數(shù)存入一個二維數(shù)組。第二步：再查詢從中轉(zhuǎn)站點到達目的站點的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點和目的站點名稱以及兩站點之間的站點個數(shù)存入另一個二維數(shù)組。第三步：判斷兩組路線之間是否有相同的站點，相同的站點即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。3）最短路線查詢算法最短路線查詢算法的思想是在起始點查詢的算法的基礎(chǔ)上，是對站點之間的個數(shù)加入了一段比較著站點個數(shù)代碼，通過三個臨時變量，用于記錄所有線路中的最短路徑和兩站點信息在數(shù)組中的位置，最后通過臨時變量記錄下來的信息，輸出數(shù)組中相應位置的信息。4、開發(fā)平臺選用本系統(tǒng)基于集成軟件開發(fā)平臺（Delphi）及數(shù)據(jù)庫管理系統(tǒng)軟件（SQL Server）

7、實現(xiàn)。三、實驗器材1、PC機（已安裝Delphi7.0和SQL Server2000） 1臺 四、實驗原理“乘車方案查詢系統(tǒng)的設(shè)計與實現(xiàn)”數(shù)據(jù)流程是：將用戶要查詢的公交線路信息、進行條件查詢，將查詢結(jié)果在界面上顯示。用戶需要查詢的公交線路信息的要求是：從數(shù)據(jù)庫中查詢每條滿足用戶要求的公交線路，包括每條線路的線路名稱及經(jīng)過的所有站點。錄入的信息進行條件查詢的要求是：利用算法算出最符合用戶需求的公交線路，在所輸入的條件沒有直達車的情況下，系統(tǒng)會自動給予轉(zhuǎn)乘方案。查詢結(jié)果顯示的要求是：直觀、簡單、快捷的輸出每條滿足條件的信息。1，公交線路網(wǎng)絡特點道路網(wǎng)絡一般是以交叉口為結(jié)點，各路段為弧段。對于公交網(wǎng)

8、絡，同一條路段上可以由很多公交線路，并且，每條線路都有固定的行車線路和發(fā)出頻率，乘客只能在具有相同站點的線路間換乘。因此，相對道路網(wǎng)絡來說，公交網(wǎng)絡更為復雜。其主要特點為：1）連通性：城市道路網(wǎng)絡的連通性和公交網(wǎng)絡的連通性含義不同。在道路網(wǎng)絡中，道路交叉點連接著與該交叉口相連的多條路段，車輛在交叉點可以從一條路段進入另一條路段。在公交網(wǎng)絡中，若幾條不同公交線路經(jīng)過空間上的同一站點，如果在該站點能夠換車，則這幾條公交線路是連通的，而且，換車存在換乘消耗，包括時間消耗、費用消耗等。另外多條公交線路雖然在空間上的同一點相交，但是該點不一定是公交站點，或不是同時有站點，此時，不同公交線路是不連通，的乘

9、客不能在該點換乘。2）節(jié)點的特性：由于公交車只能在行駛線路上的相應站點停靠，因此，不同的公交線路，其行駛線路在空間上可能有重疊，但?？空军c不可能完全重疊。實際上，公交乘客在換乘時通常要步行一段距離才能到達另外一條公交線路的站點，達到換乘的目的。此時，換乘的兩條公交線路的站點并不重疊。因此，在進行公交網(wǎng)絡建模時，要把空間上相近的不同線路上的站點，合理抽象成公交網(wǎng)絡圖上的相關(guān)節(jié)點，來模擬不同公交線之間的換車情況。公交車只能按既定的順序?？空军c，每條公交線路都有規(guī)定的方向，因此，由實際公交網(wǎng)絡抽象的拓撲網(wǎng)絡圖是一個有向圖，在拓撲網(wǎng)絡圖上不同屬性的邊在節(jié)點處連通，表示乘客可以在該節(jié)點處換乘換。乘必須在

10、公交站點進行，不同公交線的站點在空間上并不一定完全相同，乘客在換乘時，一般需要步行一段距離，才能完成換乘。因此，需要將空間位置鄰近的站點抽象成網(wǎng)絡圖中的一個節(jié)點。將公交站點抽象成網(wǎng)絡節(jié)點后，接下來要做的工作是將公交線路的各站點間的路段抽象成網(wǎng)絡圖中的邊。公交網(wǎng)絡圖是一個賦權(quán)有向圖，邊的權(quán)值可以是路段的長度、路段通行時間，或其它的含義。通常一條公交線路有兩個行駛方向，當兩個方向的行駛線路重合時，網(wǎng)絡圖上的節(jié)點在兩個方向上各有一條出邊和入邊；當兩個方向的行駛線路不重合時，網(wǎng)絡圖上的節(jié)點在每個方向上只有一條出邊或入邊。如果一個節(jié)點是多條公交線路的交匯點，則該節(jié)點處的邊數(shù)等于各條公交線路在該節(jié)點處的出

11、邊和入邊之和。如圖1，此公交網(wǎng)由7 各節(jié)點A、B、C、D、E、F、G；3 條線路L1：ABDEG；L2：BDEF；L3：CDEG。在公交網(wǎng)中經(jīng)過節(jié)點B的線路是L1、L2在線路L1中B為第二站在線路L2中B為起始站節(jié)點B的入邊數(shù)是1，出邊數(shù)為2。圖8-1 公交網(wǎng)絡圖例最短路徑算法研究在設(shè)計最短路線算法時，考慮到公交線路的線路搜索與數(shù)據(jù)結(jié)構(gòu)中賦權(quán)值圖的搜索算法很相近，進行了相關(guān)資料和算法的研究。圖是一些點和一些連接兩點之間的連線所組成的圖形的抽象，一個圖由節(jié)點集邊集，和節(jié)點與邊的對應關(guān)系構(gòu)成。設(shè)有圖G, 對G中的每一條邊(Vi，Vj)，相應地有一個數(shù)L(Vi,Vj)稱為邊的權(quán)。圖G連同在它邊上的權(quán)

12、被稱為賦權(quán)圖。一條邊的權(quán)也說成它的長。一條道路u=V1,V2,Vm的長是u上所有長的和，即L (V1, V2) +L (V2, V3) +L (Vm-1, Vm)。在賦權(quán)圖中給定一個始點Vi及終點的所謂最短路徑問題就是在(Vi,Vj)道路集合Pij中，尋求長為最小的路徑，這樣的路徑稱為從Vi到Vj的最短路徑。從Vi到Vj的最短路徑長度即最短距離記作d(Vi,Vj)。賦權(quán)圖中的權(quán)可以表示兩個頂點間的距離，或者途中所經(jīng)的時間，或者交通費用等。此時路徑長度的度量不是路徑上邊的數(shù)目，而是路徑上邊的權(quán)(距離、時間、費用等)之和。例如 圖2每個頂點表示城市兩個頂點構(gòu)成的邊表示兩城市間的道路，邊上的數(shù)字也就

13、是上面說的權(quán)表示兩個城市之間的距離(公里)，如果用汽車運輸貨物從A城到H城，司機就會考慮走路程最短的道路，那么最短路徑是哪一條呢?應該是A-B-D-H, 而且最短距離d (A, H)=L (A, B)十L(B ,D )+ L (D,H )= 100+100+100=300公里。圖8-2 賦權(quán)值圖的最短路徑 迪杰斯特拉(Dijksrta)最短路徑算法尋找兩頂點間的最短路徑的算法很多，目前公認最好的算法是迪杰斯特拉(Dijksrta)在1959年提出的，它不僅求出從始點到終點的最短路徑，而且最后所得到的實際上是始點到各頂點的最短路徑。對 Dijkstra算法進行補充得出的步驟如下:第一步：初始化。

14、V=1,2 , N ， S = F，D I=LF, I ，Y I=F，其中I=1,2, N。F表示路徑的始點，I表示某一頂點，N表示網(wǎng)絡中所有頂點的數(shù)目，V是所有頂點的集合，LF, I表示從F點到I點的距離，S是頂點的集合，D為N個元素的數(shù)組用來存儲頂點F到其它頂點的最短距離，Y為N個元素的數(shù)組用來存儲最短路徑中在頂點I之前經(jīng)過的最近頂點。第二步：從VS集合中找一個頂點T使得DT是最小值，并將T加入到S集合中。如果VS是空集合則結(jié)束運算。第三步：調(diào)整Y、D數(shù)組中的值：在VS集合中對于頂點T的鄰接各頂點I，如果DI> DT+LI, T，那么令YI=T, DI=DT+LI, T。繼續(xù)執(zhí)行第二

15、步。Dijksrta最短路徑算法由于其穩(wěn)定性、能適應網(wǎng)絡拓撲的變化，同時對系統(tǒng)的內(nèi)存空間占用少，因而在計算機網(wǎng)絡拓撲路徑選擇中得到廣泛的應用。但是對公交線路來說，Dijkstra算法所采用的數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)方法總體上說是比較復雜的，其缺點也是明顯的，難以應付公交線路的網(wǎng)絡拓撲中的復雜性。主要表現(xiàn)如下：(1)數(shù)據(jù)結(jié)構(gòu)復雜；(2)算法時間長；(3)Dijksrta最短路徑算法對于網(wǎng)絡拓撲圖要求簡捷，對于復雜的公交網(wǎng)絡拓撲，必須對其進行復雜的抽象、合并成簡捷的網(wǎng)絡拓撲圖，這無疑增加了程序的復雜性。(4)公交轉(zhuǎn)車中的特殊性并不一定要求用Dijkstra算法算出一條最短路徑。求乘客從A站到B站的最短路徑

16、，將每個公交站點均看作網(wǎng)絡上的頂點，每相鄰站點間的路段看作一條邊，假設(shè)乘客每到一個公交站點都考慮轉(zhuǎn)車，才可用Dijkstra算法計算最短路徑。用Dijkstra算法計算出來的結(jié)果可能是:從A站到B站需要轉(zhuǎn)好幾次車或十幾次車才能到達。這樣的計算結(jié)果是沒有什么意義的。五、實驗步驟1、起始站點查詢算法實現(xiàn)第一步：通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name)轉(zhuǎn)換成站點編號(stop_id)，以站點編號為條件，查詢線路站點關(guān)聯(lián)(linestops)表中對應的記錄，并記錄下它們的線路編號(line_id)，對經(jīng)過這兩個站點的所以公交線路進行比較，記錄下相同的線路編號；第二步：判斷

17、以上查詢中是否有滿足要求的記錄，若recordcount<>0，則記錄兩站點在線路中的位置，判斷是否滿足行駛方向的要求，通過定義一個數(shù)組，將線路信息中的線路名稱，起始和目的站點名稱以及兩站點之間的站點個數(shù)存入數(shù)組并輸出。若recordcount=0，證明查詢的站點之間不能直達，需要轉(zhuǎn)乘；第三步：查詢出兩站點之間所有線路的站點交集（中轉(zhuǎn)站點），通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name)轉(zhuǎn)換成站點編號(stop_id)，這里定義為id1,id2；以它們?yōu)闂l件，搜尋線路站點關(guān)聯(lián)(linestops)表中兩個站點通過直達方式各自能夠到達的站點集合，最后他們的交集

18、就是我們所需要的換乘站點，將這些站點存放入一個一維數(shù)組中；第四步：重復第一、二步的操作，查詢從起始站點到達中轉(zhuǎn)站點的所有公交線路，將線路信息中的線路名稱，起始和中轉(zhuǎn)站點名稱以及兩站點之間的站點個數(shù)存入一個二維數(shù)組；第五步：再重復第一、二步的操作，查詢從中轉(zhuǎn)站點到達目的站點的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點和目的站點名稱以及兩站點之間的站點個數(shù)存入另一個二維數(shù)組。第六步：判斷兩組路線之間是否有相同的站點，相同的站點即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。主要代碼：第一步：查詢兩站點之間在直達情況下的所有線路。select * from line where line_id in ( selec

19、t A.line_id from(select line_id from linestops where stop_id in (select stop_id as id1 from stop where stop_name=' edit1.text ') A,(select line_id from linestops where stop_id in (select stop_id as id2 from stop where stop_name=' edit2.text ') Bwhere A.line_id = B.line_id);第二步：輸出線路名稱

20、，起始和目的站點名稱以及兩站點之間的站點個數(shù)。if recordcount<>0 thenMyArrayP,3:=inttostr(y-x);MyArrayP,1:=edit1.Text;MyArrayP,2:=FieldValues'line_name'MyArrayP,4:=edit2.Text;P:=P+1; for i:=1 to P-1 dobeginmemo1.Lines.add(MyArrayi,1+'>>'+MyArrayi,2+'('+MyArrayi,3+'站'+')'+

21、'>>'+MyArrayi,4);end;第三步： 查詢兩站點之間不能直達的情況下，可選擇的中轉(zhuǎn)站點。select stop_name from stop where stop_id in(select A.stop_id from ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id in (select stop_id as id1 from stop where stop_name=' edit1.te

22、xt ')A, ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id in (select stop_id as id2 from stop where stop_name=' edit2.text ')B where A.stop_id = B.stop_id); /*得到中轉(zhuǎn)站點名稱*/第四步：重復第一、二步的操作，查詢起點到中轉(zhuǎn)站點的線路信息；第五步：重復第一、二步的操作，查詢中轉(zhuǎn)站到目的站點的線路信息；第六步：判

23、斷兩組路線之間是否有相同的中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。指定中轉(zhuǎn)站點查詢算法實現(xiàn)第一步：查詢出兩站點之間所有線路的站點交集（中轉(zhuǎn)站點），通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name)轉(zhuǎn)換成站點編號(stop_id)，這里定義為id1,id2；以它們?yōu)闂l件，搜尋線路站點關(guān)聯(lián)(linestops)表中兩個站點通過直達方式各自能夠到達的站點集合，最后他們的交集就是我們所需要的換乘站點，將這些站點存放入一個一維數(shù)組中；第二步：對從起點到中轉(zhuǎn)站的線路進行查詢，通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name)轉(zhuǎn)換成站點編號(stop_id)，以站點編號為條件，查詢線路站點關(guān)聯(lián)(linestops)表中對應的記錄，并記錄下它們的線路編號(line_id)，對查詢出的所有公交線路進行比較，將線路信息中的線路名稱，起點和中轉(zhuǎn)站名稱以及兩站點之間的站點個數(shù)存入一個二維數(shù)組；第三步：對從中轉(zhuǎn)站到終點的線路進行查詢，采用和第二步相同的操作，將線路信息中的線路名稱，中轉(zhuǎn)站和目的站點名稱以及兩站點之間的站點個數(shù)存入另一個二維數(shù)組；第四步：判斷兩組路線之間是否有相同的中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。最短路線查詢算法實現(xiàn)最短路線查詢算法的實現(xiàn)與起始站點查詢算法的實現(xiàn)相似，只是在記錄站點之間的個