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

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

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

4、次數是指乘客在完成一次出行過程中所換車的次數。實際上 這幾個出行因素是相互影響的，如換乘次數和出行費用就是相關聯的，特別是在一些實行一 票制的城市中，這兩個因素可以說是一致的。根據早期的測試的結果發現的確如此，所用的 費用基本都是以換乘次數為界劃分的。2、2、傳統的Dijkstra算法無疑是解決一般最短路徑問題的最優算法，但接下來我們會看到傳統 的Dijkstra算法在公交查詢系統是不適合的。依據對公交乘客出行心理調查的統計結果, 指出換乘次數最少是乘客出行時考慮的首要因素，所以這里提出一種基于換乘次數最少的公 交最短路徑算法，并根據公交系統的特點，以圖的鄰接表作為數據結構。3、3、根據經驗表

5、明,在北京這樣的大都市的公交網絡上,換3次車即乘坐4條線路的公交車,方 可到達目的地的情況都是很少發生的。所以本文認為兩次以內的轉車是比較合理的。換乘次數為2次及以下的情況中，會產生出行時間最小和費用最低等相應情形。有些乘 客可能有急事所以較為傾向時間最小，有些乘客因為經濟上的考慮會選擇費用最低，有些乘 客就會做出折中的選擇。為滿足各種乘客的需求，我提出了基于廣度優先搜索，求解所有的 換乘次數為2次及以下的路線。并根據乘客的需求判斷出最優選擇。針對考慮公交的換乘情 況，主要算法描述如下。(1)輸入乘車的起始站點A及目的站點B ;(2)求經過站點A的所有線路集S ( I)和經過站點B的所有線路集

6、T( J );(3)判斷有S ( I) = T( J )嗎？如果有，則找到了從站點A到站點B的直達線路S ( I)即1( J),輸出結果,進行下一步。(4)求線路S ( I)上的站點E( I ,U)以及線路1( J)上的站點F( J ,V);(5)判斷是否存在相同站點，即E( I ,U) = F( J ,V)。如果滿足E( I ,U) = F( J ,V),則 線路S ( I) , T( J)即為一次轉車的線路，E( I ,U)即為轉車站點;輸出結果。再執行下 面。(6)求經過E( I ,U)的線路集R ( K),經過F( J ,V)的線路集丫( O);(7)判斷有R ( K) = Y( O)

7、嗎？如果有，則線路S ( I) , R (K) , T( J)為兩次換車的線路，換車站點為E( I ,U)和F(J,V), 輸出結果。繼續執行下面。(8)求線路R ( K)上的站點6( K ,W)和線路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)即為三次轉車的線路，E( I ,U) , G(K ,W) , F( J,V) 即為轉車站點。公交調度：通過對分析我覺得公車的調度問題是一個雙方利益兼顧的問題，乘客的利益是

8、超時等待 的比例盡量少和超載的情況盡量少發生，公交公司的利益則是滿載率盡量高，以提高效益。 接下來我將這三個目標量化，化為目標函數，以得到最優調度。根據數據大家可以看出在一定的時段里乘客的人數有一定的相似性，這也比較容易理解， 因為大家上班的時間大都集中在8： 00-9： 00，下班時間也集中在16： 00-18： 00左右。所 以我以乘客的人數多少將公車的運行時間分為幾個時段。一是早上平峰時段，二是早上高峰 時段，三是中午平峰時段，四是傍晚的高峰時段，五是晚上的平峰時段。這樣我可以分別對 每一時段單獨進行分析求解，使得問題簡化。我只采用了上行的測試數據，下行同樣可求。 下面是線路上行時段劃分

9、。上行：15： 00-6： 0026： 00-9： 0039： 00-16： 00416： 00-18： 00518： 00-23： 00因為在我劃分的一個時段里，情形都是相近的。每個乘客到達車站又是相互獨立事件, 所以我可以認為在我劃分的每個時間段里到達車站的乘客人數是均勻的。由于乘客到達的均 勻性，則一個時間段里發車也可以看成是均勻的。而總人數Pi除以時間段Ti的運力，就可以得到滿載率的目標函數。下面我們先來求解上行路線。時間段i的平均發車時間間隔為：bi=Ti/Bi；第k輛車到達站點j時，站點j上的等待上車的人數PW(i，k，j)=Pl(i,k-1,j)+bi*Kij而設 Pl(i，0，

10、j)=0，當 k=1 時 PW(i，1，j)=二*Kij；第k輛車到達站點j時，下車人數D(i,k,j)=bi*-而D(i，k，0)=0，即起點站沒人下車。第k輛車到達站點j時，車上乘客下車后車上的最大容量為：On(i,k,j)=Max 120-(PLB(i，k，j-1)-D(i，k，j)，0)；第k輛車離開站點j后車上的人數PLB(i,k,j)=PLB(i,k,j-1)-D(i,k,j)+max O(i,k,j)，PW(I,j,k) 第k輛車離開站點j后車上的超載人數C(i,k,j)=max PLB(i,k,j) 100，0)第k輛車離開站點j后，站點上還剩下的等待人數PL(i,k,j)=m

11、ax PA(i,j,k)- On(i,k,j)，0)時間段i車上的總人數Pi二”巳 PLB (i, k, j)第k輛車到達站點j時超額等待的乘客人數為平峰期：If (T(i，k，j)-10T(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) -5T (i,k-1,j) W (i, k, j) =maxKij* (T (i, k, j) -5-T (i,k-1,j), 數據及類型描述下面是公交查詢里用到的數據和函數ElemType vtail,vhead;要查詢的起點和終點，作

12、為全局變量bool ev600100,fv600100;eij為線路 i 會進入站點 j, fij為線路 i 會從 站點j出來struct ARcType弧結點：弧頭在頂點數組中的序號，權值，指向下一條弧結點的指針struct VErtexType頂點結點：結點名字，指向第一條弧結點的指針class Graph公交線路圖類VErtexType graph4100;存儲公交線路圖的鄰接表VErtexType graph14100;公交線路圖的逆鄰接表int vertexnum,arcnum;頂點數和弧定點數int L550;記錄線路i能經過幾次換乘到達終點ElemType e600100,f60

13、0100;eij為線路 i 會進入站點 j, fij為線路 i會從站點j出來int en600,fn600;ei有多少個站點bool ticket550;/0為單一票制，1為分段計價bool round550;/是環形路為真，否則為假void initiate。；/初始化 en, fnvoid initiate2();ElemType r6000,y6000;/從 E( I ,U)站點發出的線路集 R ( K)，進入站點 F( J,V) 的線路集Y( O);int getdata();/從文件中讀入數據int LocateVertex(ElemType str);/查找名為str的頂點在數組g

14、raph中的序號，返 回。沒有返回-1int findpathout(ElemType s100,ElemType a);/求出經過站點 a 的所有線路名字， 復制到si中int findpathout(ElemType s100,ElemType a,ElemType hi);int findpathin(ElemType s100,ElemType );/求出經過站點 a 的所有線路名字，復 制到si中int CreateDN();/創建有向有權圖的鄰接表void Insertarc(int i,int j,ElemType linename,ElemType strh,ElemType

15、strt);/在圖 中加入一條弧，由序號i的點指向序號j的點void Insertarc(int i,int j,ElemType &linename,ElemType strh,ElemType strt,char ch);void ShowUDN();顯示圖的領接表的結構int directpath(ElemType h100,ElemType t100,int counth,int countt);/ 否有直接路線int ispath(ElemType vhead,ElemType vtail,ElemType 反)；/判斷 vhead 和 vtail 是 不是線路hi上的先后兩點int

16、 oncepath(ElemType h100,ElemType t100,int counth,int countt);/看是否 有轉一次車路線,即看線路i和j有沒有公共的站點void oncepathtime(ElemType h100,ElemType t100,int counth,int countt);/ 看是否有轉一次車路線,輸出最小時間void oncepathsometime(ElemTypeh100,ElemTypet100,int counth,intcountt);/看是否有轉一次車路線,輸出最小時間int twiceandthreepath(ElemType h100

17、,ElemType t100,int counth0,int countt0,int counth1,int countt1);/看是否有轉2次車路線，即看線路i和j有沒有公共 的站點void twiceandthreepathtime(ElemType h100,ElemType t100,int counth0,int countt0,int counth1,int countt1);/看轉兩次車的最快時間void twiceandthreepathsometime(ElemType h100,ElemType t100,int counth0,int countt0,int counth

18、1,int countt1);/看轉兩次車的最快幾次時間int num1(int fasttime5,int time,int count) /看 time 在 fasttime 數組中是第幾 快的，返回數組中的序號，如果不能入前3快，返回-1，如果count沒有3個，則前count 快。void names(ElemType s,int n)/給公交站點命名int checkarcname(ElemType str)/檢查輸入的弧名是否正確:L+三位數字”，正確就返回1， 否則0int changel(ElemType str)/將站點名轉為相應的數字int change(ElemType

19、str)/將弧名轉為相應的數字void namel(ElemType linename,int busline)/根據線路的號碼給線路命名void Showall()/顯示所有線路的情況GRaph net;/全局變量，存儲站點信息下面是公交調度的相關數據和函數描述：int B6;/Bi,時間段Ti內發出的車輛數float b6;/時間段i的平均發車時間間隔為float PL69020;/PL（i，k，j）時間段i內第k輛車離開第j個站點時，站點j上的 人數float PW69020;/PW (i, k, j)時間段Ti內第k輛車到達站點j時，站點j的等待 上車人數float C69020;/時

20、間段i第k輛車離開站點j時的超載人數float K620;/時間段i內單位時間平均到站j的人數float L620;/時間段i內單位時間平均在站j下車的人數float T6;/時間段i的長度int start6;/5個時段的開始時刻float t14;/起點到各個站點的時間float D69020;/D(i,k,j)，時間段Ti內第k輛車到達站點j時，下車的人數float On69020;/On(i,k,j)，時間段Ti內第k輛車到達站點j時，乘客下車后，車 能容納上車的最大人數float PLB69020;/PLB(i，k，j)時間段i內第k輛車離開第j個站點時，車上的人 數float W6

21、9020;/時間段Ti內第k輛車到達站點j時，等待時間過長的乘客float w6,c6,z6;/記錄各個目標函數的數值。int b1;/全局變量，要調度的線路的站點數void initiate1()/劃分各個時段int change(int n)/看開始時間n是第幾時段int larger(int a,int b)/比較，返回大數int less(int a,int b)/比較，返回小數void getdata()/從要調度的線路讀出文件,并初始化相關數據void findbestBi(int i,int b1)/求時段 i 最佳發車數數量Biint cusmenu()/乘客菜單函數int g

22、uanli()/管理員菜單測試方法描述(1)輸入密碼進入管理員菜單，進行相關操作，先是初始化公交查詢系統。乘客菜單X結束程序,直看某玷點為出入站情投。1:看看所有淺珞 日于線路過冬一開始會出現閔庠的 根據采集的嵯躇的數據燈該線瞬沖行會車的調度1返回主菜單.（3）查看所有線路的情況。由于數據太多，近500多條線路，所以一開始會出現類似閃屏的情況。運行過程如下。（2）然后測試函數：查看某站點的出入站的線路的情況co F: 數據結構,數據結構大作業buwDcbugbus. exer5 -F乘客菜單X結束程序,直看某玷點為出入站情投。1:看看所有淺珞 日于線路過冬一開始會出現閔庠的 根據采集的嵯躇的數

23、據燈該線瞬沖行會車的調度1返回主菜單.（3）查看所有線路的情況。由于數據太多，近500多條線路，所以一開始會出現類似閃屏的情況。運行過程如下。（2）然后測試函數：查看某站點的出入站的線路的情況co F: 數據結構,數據結構大作業buwDcbugbus. exer5 -F二 數摳結構、歙據結構大作業lmnDcbugtniM. eien ： 1公交查狗系統成功。b:查看某站點的出入站情況。3;查看所有線路（由于線路過多一開始會出現閃屏兒卜：根據采集的線路的數據對該線路進行公車的調度快返回主菜單。二富蟹菜單E1459-L271D82062if入站點名：S1459E1459-L271US1461E14

24、59-L244DS2062K1459-L244U 81143悵入站點后145癡線路情況為:K1461-L271D81459E2062-L271U 81459E1143-L244DS1459E2062-L244U81459輸人管理員密碼Hl）： 111管理反菜單1初始化公.爻查詢下院E-丁 I s - 一行0-行3苴一一叫T157E-丁 I s - 一行0-行3苴一一叫T157497 甘LT 45 141210 8 3 fl- 7 3 7 2 2 .283 ZMr s s Jt 7 1: s IIM或IT仃u段行行 3分-寶IL5介二”、L513lui ”這個文件）o超載的乘客比例為0.0957

25、341團716921,等待超時乘客比例為.261883,超載的乘客比例為0刃467687時間段5： 18：豳-23： M最佳調度為：每間隔17.6471分鐘發一班車0.89704,等待超時乘客比例為.000917203,超載的乘客比例為0lui ”這個文件）o超載的乘客比例為0.0957341團716921,等待超時乘客比例為.261883,超載的乘客比例為0刃467687時間段5： 18：豳-23： M最佳調度為：每間隔17.6471分鐘發一班車0.89704,等待超時乘客比例為.000917203,超載的乘客比例為0.0711743時間段4： 16：股-18：網最佳調度為：每間隔3.769

26、2分鐘發一班車即同段,：，：孫16：嗎隼佳調度為:每間隔5.83333分鐘發一班車霜窯露饕飄墻 厚待超時乘客比例為.0753063,超載的乘客比例為四.0189075時回段? ： 6 ： 00-9 ： 00,霜褊鸚明蕊乩,等待超時乘客比例為,000408816,超載的乘客比例為0.0594357鵲度為:每間隔2. M897分鐘發一班車（5）接下來進入乘客菜單，先輸入乘客想查詢的起點和終點。CA7：敦據結構數據結構大作業11式。611/113.6屋日回in an:公工件1:聞酒 擇入111文段時的 選輸an!輛 請請1X1根翳車亡 1#若陽 -Fn 才可有 只 前 目4次口后調為麻交度.輔出賽5

27、5管取測78以0,預98可:0關0.據-6%數眄的率的5:暮露需鸚霜熟嚼槳1鸚露露器-,，總直達或只轉一次中的路編“京換乘:多次為路線b提供凡品時可較超號路。向返回主菜單.b，總直達或只轉一次中的路編“京換乘:多次為路線:豆的線路,，總直達或只轉一次中的路編“京換乘:多次為路線b提供凡品時可較超號路。向返回主菜單.b，總直達或只轉一次中的路編“京換乘:多次為路線:豆的線路腳人起點:SB864輸入終點:1341拿客選擇菜聿卜輸入起點和終點.(6)然后大多數乘客為了舒適性會選擇查詢直達或只轉一次車的路線，結果如下，可惜這 兩個站點沒有直達路線，系統會作出提醒。 為為線路。路的線線線車 為為線路。路

28、的線線線車2的踣的次n:車達車一囊直次轉選需有一有請不認食僅卜乘客選擇菜單輸入起點和終點。卜求直達或只轉一次車的路線。,求換乘多次的路線。卜求時間最短的線路。卜提供幾條時間較短線路。k返回主菜單.轉多次車的所有線路為: (7)然后乘客可以選擇查看需要換乘多次的所有路線，結果如下。105 F： Sfc無結構速據結構大作業以Debugbus. exeh提供凡圣時間較短線路.忸返回主榮單.慢選擇n二特多次豐的所.有線路大：SUtlb4-L373D-S3ijV-L27U-S32?5-L50?-SlJ41 SKItlb4-?LJ73D-SJB5y-LliB7U-S32V5-?LUBy-SlJ41 S30

29、64-L373D-S0063-L287U-S329E-L509-S1341 S0064-L373D-S0063-L287U-S3295-L089-S1341 S3064-L373D-S3618-L287U-S329E-L509-S1341 S0064-L373D-S3618-L287U-S3295-L089-S1341 S3064-L373D-S3607-L287U-S3295-L509-S1341 S0064-L373D-S3607-L287U-S329E-L089-S1341 RHflA4-T73D-R41R-L2fl7ll-R39R-LSR9-R141 RW(J|f；4-L371D-R4

30、10-L2n7ll-S339-LnS9-S1 41 G0064-L373D-E264S-L287U-G329E-L509-S1341 E00G4-L273D-E2t4e-L287U-S329E-L0e9-Gia41 S30G4-L3?3D-E3465 L015U G1S31 L50?-S1J41 S0BG4-L373D-S3465 LB15U 31031 L08?-S1J41 S0e64-L282D-S3293-L468U-S3295-L507-S1341 S0e64-L282D-S3293-L468U-S1831-L50?-S1341聽聽工b.可可可.一日音=日司司.司司司可可可司 特多次豐

31、的所.有線路大：SUtlb4-L373D-S3ijV-L27U-S32?5-L50?-SlJ41 SKItlb4-?LJ73D-SJB5y-LliB7U-S32V5-?LUBy-SlJ41 S3064-L373D-S0063-L287U-S329E-L509-S1341 S0064-L373D-S0063-L287U-S3295-L089-S1341 S3064-L373D-S3618-L287U-S329E-L509-S1341 S0064-L373D-S3618-L287U-S3295-L089-S1341 S3064-L373D-S3607-L287U-S3295-L509-S1341

32、S0064-L373D-S3607-L287U-S329E-L089-S1341 RHflA4-T73D-R41R-L2fl7ll-R39R-LSR9-R141 RW(J|f；4-L371D-R410-L2n7ll-S339-LnS9-S1 41 G0064-L373D-E264S-L287U-G329E-L509-S1341 E00G4-L273D-E2t4e-L287U-S329E-L0e9-Gia41 S30G4-L3?3D-E3465 L015U G1S31 L50?-S1J41 S0BG4-L373D-S3465 LB15U 31031 L08?-S1J41 S0e64-L282D-S3293-L468U-S3295-L50