公交查詢系統(tǒng)報告資料

1、北京化工大學(xué)北方學(xué)院課程設(shè)計報告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目公交查詢系統(tǒng)專業(yè)、班級軟件工程0901學(xué)號090203018姓名直度指導(dǎo)教師周建敏老師設(shè)計時間2012年9月10日-2012年9月23日2012年9月25日一、引言（簡要說明設(shè)計題目的目的、意義、內(nèi)容、主要任務(wù)等）設(shè)計解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)系統(tǒng)，其核心是線路選擇的模型與算法，特別是滿足不同乘客的查詢需求。而我，依據(jù)對公交乘客出行心理調(diào)查的統(tǒng)計結(jié)果，指出換乘次數(shù)最少是乘客出行時考慮的首要因素，所以這里提出一種基于換乘次數(shù)最少的公交短路徑算法，并根據(jù)公交系統(tǒng)的特點，以圖的鄰接表作為數(shù)據(jù)結(jié)構(gòu)。至于公交車的調(diào)度，需要同時

2、考慮到公車公司和乘客的利益，必須盡量在滿足雙方的利益上做出合理的調(diào)度。所以這是一個多目標(biāo)最優(yōu)的問題，一是公車公司的成本低，即提高每輛車的滿載率，或者說發(fā)車的車次盡量少；二是等待時間過長的乘客所占的比例盡量少；三是超載的情況盡量不發(fā)生，讓乘客盡量感到舒適。關(guān)鍵詞：公交路線網(wǎng)絡(luò)化，圖的鄰接表，公交查詢，乘客的需求，換乘次數(shù)，廣度搜索，公交調(diào)度，分時段調(diào)度，公交公司與乘客的利益關(guān)系公交的調(diào)度系統(tǒng)：公共交通是城市交通的重要組成部分，作好公交車的調(diào)度對于完善城市交通環(huán)境、改進(jìn)市民出行狀況、提高公交公司的經(jīng)濟(jì)和社會效益，都具有重要意義。為了建立一個有效的公交調(diào)度，我需要采集需要調(diào)度的線路的相關(guān)數(shù)據(jù)。根據(jù)采

3、集到的數(shù)據(jù)，我的公交調(diào)度系統(tǒng)就可以為這條線路設(shè)計一個全天的公交調(diào)度方案。二、正文（課程設(shè)計的主要內(nèi)容，包括實驗與觀測方法和結(jié)果、儀器設(shè)備、計算方法、編程原理、數(shù)據(jù)處理、設(shè)計說明與依據(jù)、加工整理和圖表、形成的論點和導(dǎo)出的結(jié)論等。正文內(nèi)容必須實事求是、客觀真切、準(zhǔn)確完備、合乎邏輯、層次分明、語言流暢、結(jié)構(gòu)嚴(yán)謹(jǐn)，符合各學(xué)科、專業(yè)的有關(guān)要求。）1、課程設(shè)計的主要內(nèi)容設(shè)計解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)系統(tǒng)，其核心是線路選擇的模型與算法，特別是滿足不同乘客的查詢需求。通常乘客選擇出行路線時受到以下幾個因素的作用：“換乘次數(shù)”、“出行距離”、“出行耗時”、“出行費用”。換乘次數(shù)是指乘客在完成一次出

4、行過程中所換車的次數(shù)。實際上這幾個出行因素是相互影響的，如換乘次數(shù)和出行費用就是相關(guān)聯(lián)的，特別是在一些實行一票制的城市中，這兩個因素可以說是一致的。根據(jù)早期的測試的結(jié)果發(fā)現(xiàn)的確如此，所用的費用基本都是以換乘次數(shù)為界劃分的。測試方法描述傳統(tǒng)的Dijkstra算法無疑是解決一般最短路徑問題的最優(yōu)算法，但接下來我們會看到傳統(tǒng)的Dijkstra算法在公交查詢系統(tǒng)是不適合的。依據(jù)對公交乘客出行心理調(diào)查的統(tǒng)計結(jié)果，指出換乘次數(shù)最少是乘客出行時考慮的首要因素，所以這里提出一種基于換乘次數(shù)最少的公交最短路徑算法，并根據(jù)公交系統(tǒng)的特點，以圖的鄰接表作為數(shù)據(jù)結(jié)構(gòu)。編譯原理數(shù)據(jù)分析根據(jù)經(jīng)驗表明，在北京這樣的大都市的

5、公交網(wǎng)絡(luò)上，換3次車即乘坐4條線路的公交車，方可到達(dá)目的地的情況都是很少發(fā)生的。所以本文認(rèn)為兩次以內(nèi)的轉(zhuǎn)車是比較合理的。換乘次數(shù)為2次及以下的情況中，會產(chǎn)生出行時間最小和費用最低等相應(yīng)情形。有些乘客可能有急事所以較為傾向時間最小，有些乘客因為經(jīng)濟(jì)上的考慮會選擇費用最低，有些乘客就會做出折中的選擇。為滿足各種乘客的需求，我提出了基于廣度優(yōu)先搜索，求解所有的換乘次數(shù)為2次及以下的路線。并根據(jù)乘客的需求判斷出最優(yōu)選擇。針對考慮公交的換乘情況,(2)主要算法描述如下。輸入乘車的起始站點A及目的站點B;求經(jīng)過站點A的所有線路集S(I)和經(jīng)過站點B判斷有S(I)=T(J)嗎？如果有，則找到了從站點A到站點

6、B的直達(dá)線路S(I)(4)求線路S(I)上的站點E(I,U)以及線路T(J)判斷是否存在相同站點，即E(I,U)=F(J,V)線路S(I),T(J)即為一次轉(zhuǎn)車的線路，E(I,U)面。(6)求經(jīng)過E(I,U)的線路集R(K),判斷有R(K)=Y(O)嗎？如果有，則線路S(I),R(K),T(J)輸出結(jié)果。繼續(xù)執(zhí)行下面。(8)求線路R(K)上的站點G(K,W)經(jīng)過F(J,V)的所有線路集T(J);即T(J),輸出結(jié)果，進(jìn)行下一步。上的站點F(J,V);。如果滿足E(I,U)=F(J,V),則即為轉(zhuǎn)車站點；輸出結(jié)果。再執(zhí)行下的線路集Y(O);為兩次換車的線路，換車站點為E(I,U)和5(J,V),

7、和線路Y(O)上的站點L(O,X);(9)判斷是否存在相同站點，即G(K,W)=L(O,X),如果滿足G(K,W)=L(O,X),則線路S(I),R(K),Y(O),T(J)即為三次轉(zhuǎn)車的線路，E(I,U),G(K,W),F(J,V)即為轉(zhuǎn)車站點。公交調(diào)度：通過對分析我覺得公車的調(diào)度問題是一個雙方利益兼顧的問題，乘客的利益是超時等待的比例盡量少和超載的情況盡量少發(fā)生，公交公司的利益則是滿載率盡量高，以提高效益。接下來我將這三個目標(biāo)量化，化為目標(biāo)函數(shù)，以得到最優(yōu)調(diào)度。根據(jù)數(shù)據(jù)大家可以看出在一定的時段里乘客的人數(shù)有一定的相似性，這也比較容易理解，因為大家上班的時間大都集中在8：00-9:00,下班

8、時間也集中在16:00-18:00左右。所以我以乘客的人數(shù)多少將公車的運行時間分為幾個時段。一是早上平峰時段，二是早上高峰時段，三是中午平峰時段，四是傍晚的高峰時段，五是晚上的平峰時段。這樣我可以分別對每一時段單獨進(jìn)行分析求解，使得問題簡化。我只采用了上行的測試數(shù)據(jù)，下行同樣可求。下面是線路上行時段劃分。上行:15:00-6:0026:00-9:0039:00-16:00416:00-18:00518:00-23:00因為在我劃分的一個時段里，情形都是相近的。每個乘客到達(dá)車站又是相互獨立事件,所以我可以認(rèn)為在我劃分的每個時間段里到達(dá)車站的乘客人數(shù)是均勻的。由于乘客到達(dá)的均勻性，則一個時間段里發(fā)

9、車也可以看成是均勻的。而總?cè)藬?shù)Pi除以時間段Ti的運力，就可以得到滿載率的目標(biāo)函數(shù)。下面我們先來求解上行路線。時間段i的平均發(fā)車時間間隔為：bi=Ti/Bi;第k輛車到達(dá)站點j時，站點j上的等待上車的人數(shù)PW(i,k,j)=Pl(i,k-1,j)+bi*Kij而設(shè)Pl(i,0,j)=0,當(dāng)k=1時PW(i,1,j)、*Kij;第k輛車到達(dá)站點j時，下車人數(shù)D(i,k,j)=bi*JiI而D(i,k,0)=0,即起點站沒人下車。第k輛車到達(dá)站點j時，車上乘客下車后車上的最大容量為：On(i,k,j)=Max120-(PLB(i,k,j-1)-D(i,k,j),0;第k輛車離開站點j后車上的人數(shù)P

10、LB(i,k,j)=PLB(i,k,j-1)-D(i,k,j)+maxO(i,k,j),PW(I,j,k)第k輛車離開站點j后車上的超載人數(shù)C(i,k,j)=maxPLB(i,k,j)-100,0第k輛車離開站點j后，站點上還剩下的等待人數(shù)PL(i,k,j)=maxPA(i,j,k)-On(i,k,j),0時間段i車上的總?cè)藬?shù)Y黑印第k輛車到達(dá)站點j時超額等待的乘客人數(shù)為平峰期：If(T(i,k,j)-10>T(i,k-1,j)W(i,k,j)=maxKij*(T(i,k,j)-10-T(i,k-1,j),PL(i,k-1,j)高峰期：If(T(i,k,j)-5>T(i,k-1,j

11、)W(i,k,j)=maxKij*(T(i,k,j)-5-T(i,k-1,j),數(shù)據(jù)及類型描述下面是公交查詢里用到的數(shù)據(jù)和函數(shù)ElemTypevtail,vhead;/要查詢的起點和終點，作為全局變量boolev600100,fv600100;/eij為線路i會進(jìn)入站點j,fij為線路i會從站點j出來structARcType/弧結(jié)點：弧頭在頂點數(shù)組中的序號，權(quán)值，指向下一條弧結(jié)點的指針structVErtexType/頂點結(jié)點：結(jié)點名字，指向第一條弧結(jié)點的指針classGraph/公交線路圖類VErtexTypegraph4100;存儲公交線路圖的鄰接表VErtexTypegraph1410

12、0;/公交線路圖的逆鄰接表intvertexnum,arcnum;/頂點數(shù)和弧定點數(shù)intL550;/記錄線路i能經(jīng)過幾次換乘到達(dá)終點ElemTypee600100,f600100;/eij為線路i會進(jìn)入站點j,fij為線路i會從站點j出來inten600,fn600;/ei有多少個站點boolticket550;/0為單一票制，1為分段計價boolround550;/是環(huán)形路為真，否則為假voidinitiate。;/初始化en,fnvoidinitiate2();ElemTyper6000,y6000;/從E(I,U)站點發(fā)出的線路集R(K),進(jìn)入立點F(J,V)的線路集Y(O);intg

13、etdata();/從文件中讀入數(shù)據(jù)intLocateVertex(ElemTypestr);/查找名為str的頂點在數(shù)組graph中的序號，返回。沒有返回-1intfindpathout(ElemTypes100,ElemTypea);/求出經(jīng)過站點a的所有線路名字，復(fù)制到si中intfindpathout(ElemTypes100,ElemTypea,ElemTypehi);intfindpathin(ElemTypes100,ElemTypea);/求出經(jīng)過站點a的所有線路名字，復(fù)制到si中intCreateDN();/創(chuàng)建有向有權(quán)圖的鄰接表voidInsertarc(inti,intj

14、,ElemTypelinename,ElemTypestrh,ElemTypestrt);/在圖中加入一條弧，由序號i的點指向序號j的點voidInsertarc(inti,intj,ElemType&linename,ElemTypestrh,ElemTypestrt,charch);voidShowUDN();/顯示圖的領(lǐng)接表的結(jié)構(gòu)intdirectpath(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有直接路線intispath(ElemTypevhead,ElemTypevtail,ElemTypehi);/判斷vhea

15、d和vtail是不是線路hi上的先后兩點intoncepath(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有轉(zhuǎn)一次車路線，即看線路i和j有沒有公共的站點voidoncepathtime(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有轉(zhuǎn)一次車路線，輸出最小時間voidoncepathsometime(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有轉(zhuǎn)一次車路線，輸出最小時間inttwiceandthreepath(ElemT

16、ypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1);/看是否有轉(zhuǎn)2次車路線，即看線路i和j有沒有公共的站點voidtwiceandthreepathtime(ElemTypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1);/看轉(zhuǎn)兩次車的最快時間voidtwiceandthreepathsometime(ElemTypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1

17、);/看轉(zhuǎn)兩次車的最快幾次時間intnum1(intfasttime5,inttime,intcount)看time在fasttime數(shù)組中是第幾快的，返回數(shù)組中的序號，如果不能入前3快，返回-1,如果count沒有3個，則前count快。voidnames(ElemTypes,intn)/給公交站點命名intcheckarcname(ElemTypestr)/檢查輸入的弧名是否正確："L+三位數(shù)字"，正確就返回1,否則0intchangel(ElemTypestr)/將站點名轉(zhuǎn)為相應(yīng)的數(shù)字intchange(ElemTypestr)/將弧名轉(zhuǎn)為相應(yīng)的數(shù)字voidnamel

18、(ElemTypelinename,intbusline)/根據(jù)線路的號碼給線路命名voidShowall()/顯示所有線路的情況GRaphnet;/全局變量，存儲站點信息下面是公交調(diào)度的相關(guān)數(shù)據(jù)和函數(shù)描述：intB6;/Bi,時間段Ti內(nèi)發(fā)出的車輛數(shù)floatb6;/時間段i的平均發(fā)車時間間隔為floatPL69020;/PL(i,k,j)時間段i內(nèi)第k輛車離開第j個站點時，站點j上的人數(shù)floatPW69020;/PW(i,k,j)時間段Ti內(nèi)第k輛車到達(dá)站點j時，站點j的等待上車人數(shù)floatC69020;/時間段i第k輛車離開站點j時的超載人數(shù)floatK620;/時間段i內(nèi)單位時間平

19、均到站j的人數(shù)floatL620;/時間段i內(nèi)單位時間平均在站j下車的人數(shù)floatT6;/時間段i的長度intstart6;/5個時段的開始時刻floatt14;/起點到各個站點的時間floatD69020;/D(i,k,j),時間段Ti內(nèi)第k輛車到達(dá)站點j時，下車的人數(shù)floatOn69020;/On(i,k,j),時間段Ti內(nèi)第k輛車到達(dá)站點j時，乘客下車后，車能容納上車的最大人數(shù)floatPLB69020;/PLB(i,k,j)時間段i內(nèi)第k輛車離開第j個站點時，車上的人floatW69020;/時間段Ti內(nèi)第k輛車到達(dá)站點j時，等待時間過長的乘客floatw6,c6,z6;/記錄各個

20、目標(biāo)函數(shù)的數(shù)值。intb1;/全局變量，要調(diào)度的線路的站點數(shù)voidinitiate1()/劃分各個時段intchange(intn)/看開始時間n是第幾時段intlarger(inta,intb)/比較，返回大數(shù)intless(inta,intb)/比較，返回小數(shù)voidgetdata()/從要調(diào)度的線路讀出文件，并初始化相關(guān)數(shù)據(jù)voidfindbestBi(inti,intb1)/求時段i最佳發(fā)車數(shù)數(shù)量Biintcusmenu()/乘客菜單函數(shù)intguanli()/管理員菜單測試方法描述(1)輸入密碼進(jìn)入管理員菜單，進(jìn)行相關(guān)操作，先是初始化公交查詢系統(tǒng)。(2)然后測試函數(shù)：查看某站點的出

21、入站的線路的情況(3)查看所有線路的情況。由于數(shù)據(jù)太多，近500多條線路，所以一開始會出現(xiàn)類似閃屏的情況。運行過程如下。匕：，F(xiàn)門教據(jù)結(jié)杓、融據(jù)結(jié)構(gòu)大作業(yè)UuCDMusMju-me*什：S277B-S1717-S0404-S005-S3B78-S3443-SB9e4-S2354-SB907-S25Bl-S3757-S294B-SlJi；S2890-S2778-S2353-S3947-S2567-S3740-S3718-S1747-S2302行；S2302-S3718-S3740-S2967-S347-S2353-S2778-S2890rb_£1&-T_u3-£-79

22、g29g1,2-2611W3s9£2is一TiJJ。w;?=彳0<10Vr-£3749-Si465一StmifiG-S154-S22S-S11R9-E2RO1-S241-S17R4-S17R3-K1671-K2(4)接著是根據(jù)文件的數(shù)據(jù)進(jìn)行公交車的調(diào)度?？梢詫⒚總€線路的具體情況放在不同的文件中，這樣就可以對不同的線路進(jìn)行調(diào)度和相關(guān)數(shù)據(jù)預(yù)測。由于時間關(guān)系這里我只存儲了xianlul這一個文件。測試結(jié)果如下。c：v"F:、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)大作業(yè).eze請選擇n：4請輸入公交調(diào)度所需數(shù)據(jù)所在的文件名(目前只有“xianlul”這個文件).xianlul根據(jù)文件的

23、數(shù)據(jù)可以膏出公交調(diào)度及相關(guān)數(shù)據(jù)如下：時段1：5:00-6：00,最崔通度為:每間隔12分鐘發(fā)一班車軍瓶礴者藪翦滕;盥U擇待超時乘客比例為自.148063,超載的乘客比例為0.09573412:6:00-9:00度為:每間隔2.酩897分鐘發(fā)一班車0.886415,等待超時乘客比例為目.眄自4幽816,超載的乘客比例為目.曬943H73：9：眄-16：股,最佳調(diào)度為:每間隔H.83333分鐘發(fā)一班車筌勰霹鬻建曹香0.755558,等待超時乘客比例為目.0753063,超載的乘客比例為0.0189075時間段4：16：醴-18：皿,最佳調(diào)度為:每間隔3.07692分鐘發(fā)一班車褊履鬻H翳嚼0.897

24、04,等待超時乘客比例為0加眄9172回3,超載的乘客比例為0.0711743時間段5：18：醴-23：皿,最佳調(diào)度為:每間隔17.6471分鐘發(fā)一班車善履器鰻熟癖0.716921,等待超時乘客比例為目.261883,超載的乘客比例為0.0467687Ld(5)接下來進(jìn)入乘客菜單，先輸入乘客想查詢的起點和終點。F門裁祖結(jié)構(gòu)、救撮結(jié)構(gòu)大作業(yè)tbu曲Dguet)U3.¥ZC輸入起點和終點."季直達(dá)或只轉(zhuǎn)一次車的路練0,求換乘多次的路線口"求時間最短的線路.卜提供幾條村間狡麴號路口"返回主菜單.展擇施八起點：M呢64疑入緣點：鼻341F-乘客選擇菜單，：輸起點

25、和終點*卜=蘋直達(dá)我只轉(zhuǎn)一次車的路線中卜式換乘多次的路線.卜玄時間最短的線路“(6)然后大多數(shù)乘客為了舒適性會選擇查詢直達(dá)或只轉(zhuǎn)一次車的路線，結(jié)果如下，可惜這兩個站點沒有直達(dá)路線，系統(tǒng)會作出提醒?？趞冥gF:數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)大作業(yè)bu£Debugbu3.exeH：返回王菜單.線線線車2的路的次n:車達(dá)車一直次轉(zhuǎn)選需有一有請不小售僅為線。路的乘客選擇菜單U輸入起點和終點。2：求直達(dá)或只轉(zhuǎn)一次車的路線。3：求換乘多次的路線。4：求時間最短的線路。5：提供幾條時間較短線路。H：返回主菜單.請選擇居多次車在所有線路為:(7)然后乘客可以選擇查看需要換乘多次的所有路線，結(jié)果如下。10八FC數(shù)

26、摳結(jié)杓、救據(jù)結(jié)構(gòu)大作業(yè)UrtinDeLug'lm#.eze卜提供幾條時同較期線路。L返回主菜單.dd33333333333333以加那斯死缸泳湖知初知知知知他用月月±21;目,H-R-月月月月月月月月費將費S串2a，«，呼*#*，S2525252524707736363636364712144111iLILIil-l'll'ilL知力對尢尢為"五步為為也為知尢fe叫叫日.一日iT5"T£-Bl印可TrEE-fJttarrrrrrrFrFrbX卜選擇n二信多次半的所有線路為：SSWb-1->L37JD->S38

27、b?->L2B7U->Sd2Vb->LSBV->SlJ41KWWfc4->L37dD->S38b9->L2B7U->S329S->LU89->S1341S006->L373D->S0063->L287U->S3295->L509->S1341S0064->L373D->S0063->L287U->S3295->LB89->S1341E006->L373D->S3618->L287U->S3295->L509->S1341E006

28、4->L373D->S3&18->L287U->S3295->LB89->S1341E0064-JL373D->S3607->L287U->S3295->L509->S1341E0064-JL373D->S36e7->L287U->S3295->L089->S134173D->S3410->L2*7II->S329S->LS->S1341卜4-7LW73D->E141B->L2*7II->K3295-M.HS9->S1341卜130t72

29、D->C2G<49->L2S7U->S229E->L509->S1341E006d->L373D->S2&<ie->L287U->E329E->L09?->G1341麗的4>L373D->G3ie5->Lei&U->Gie31->LS0V->G1341>13?5»>3305->1015(|->51©31-007->81341BB064->L28ZD->S3293->L468U->S3295-?L509->S1341S306->L202D-?S3273->L468U->S1B31->L50?->S134J(8)如果乘客趕時間，想找時間最快的路線:c：vF:、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)大作業(yè)bu3Dcbugbug.eze5：提供幾條時間較短線路。：返回主菜單.請選擇n：4周乘次數(shù)為2次以內(nèi)的最快路線為：S0064->L373D->S3405->L015U->S1831->L509->S1341所用時間為：117.費用為：3乘客選擇菜單U輸入起點和終點。2：求直達(dá)或只轉(zhuǎn)一次車的路線。3：求換乘多次的路線。4：求時間最短