2007數(shù)模競賽B題,城市公交線路選擇優(yōu)化模型你要的

1、2007B題：乘公交，看奧運（數(shù)據(jù)有變化）我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型

2、與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站t終到站之間的最佳路線（要有活晰的評價說明）。（1）、S3769tS2857（2）、S1557tS0481（3）、S1879tS2322、S0008tS0073（5）、S0148tS0485（6）、S0087tS36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)乂知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型?！靖戒?】基本參數(shù)設(shè)定相鄰公汽站平均行駛時間（包括停站時間）：3分鐘相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘6分鐘（其中步行時間5分鐘（其中步行時間8分鐘（其中步行時間6分鐘（其中

3、步行時間相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘6分鐘（其中步行時間5分鐘（其中步行時間8分鐘（其中步行時間6分鐘（其中步行時間6分鐘（其中步行時間5分鐘（其中步行時間8分鐘（其中步行時間6分鐘（其中步行時間6分鐘（其中步行時間5分鐘（其中步行時間8分鐘（其中步行時間6分鐘（其中步行時間2分鐘）2分鐘）4分鐘）4分鐘）公汽換乘公汽平均耗時：地鐵換乘地鐵平均耗時：地鐵換乘公汽平均耗時：公汽換乘地鐵平均耗時：公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡

4、化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合?！靖戒?】公交線路及相關(guān)信息（見公汽線路信息，對原數(shù)據(jù)文件B2007data.rar有少量更改）城市公交線路選擇優(yōu)化模型摘要本文針對城市公交線路選擇問題建立了兩個模型，一個是基于集合尋線算法模型，另一個是圖論模型?；诩蠈ぞ€算法模型中，首先固定換乘次數(shù)n,通過集合論的相關(guān)知識把確定換乘點的具體位置，轉(zhuǎn)化成確定一些集合間的交集，從而建立集合尋線算法，再根據(jù)集合相關(guān)公式，得到所有可行線路；進(jìn)一步考慮時間和費用等因素，對可行線路進(jìn)行處理比較，得出最佳線路。圖論模型中，通過圖論的知識將整個北京市交通線路構(gòu)建出一個有向圖，每個站點與有向圖的頂點對應(yīng)，同一線路上

5、的相鄰站點對應(yīng)為有向邊，通過不同目標(biāo)（時間、費用）給有向圖進(jìn)行不同的賦權(quán)，分別將不同目標(biāo)轉(zhuǎn)化為賦權(quán)有向圖尋找最短有向路，根據(jù)最短路徑算法，得到最佳線路。最后綜合評價了兩個模型的優(yōu)缺點。關(guān)鍵詞：集合尋線算法；最短路算法；換乘點；賦權(quán)有向圖1問題提出北京將于2008年舉行奧運會，屆時會有從四面八方而來觀看奧運比賽觀眾,其中大部分人將會乘坐公共交通工具(簡稱公交，包括公汽、地鐵等)出行。隨著現(xiàn)代化的步伐加快，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。在現(xiàn)實生活中，公交線路以及其相應(yīng)經(jīng)過的站點非常多且密，乘客往往難以知道

6、如何選擇公交線路，所以針對市場需求以及公交線路選擇上的問題，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。該系統(tǒng)的核心在于線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)，滿足查詢者的各種不同需求。根據(jù)附錄1、附錄2,解決如下問題：1. 僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用建立的模型與算法，求出以下6對起始站t終到站之間的最佳線路。(1)S3359tS1828(2)S1557tS0481(3)S0971tS0485S0008tS0073(5)S0148tS0485(6)S0087tS36762. 同時考慮公汽與地鐵線路，解決以上

7、問題。3. 假設(shè)知道所有站點之間步行時間，給出任意兩站點之間線路選擇的數(shù)學(xué)模型。2問題分析為了研制開發(fā)一個解決公交線路最佳選擇(即乘客在多條公交線路中根據(jù)自己的需求獲得最適合自己的線路)問題的自主查詢計算機(jī)系統(tǒng)，只要乘客給出起點站A和終點站B兩個站點，系統(tǒng)就給出最佳交通線路，使得公眾出行更加通暢、便利。而問題核心是如何在多條線路選擇中獲得最佳線路。乘客往往不能只乘一輛公交便直達(dá)終點，而是要通過換乘一輛或多輛公交才能到達(dá)終點站，但若多次換乘公交，可能導(dǎo)致乘客所花時間及其費用的增加，更會給乘客造成不便。在奧運將在北京舉行的背景下，我們知道乘客前往觀看奧運比賽時，主要注重的是能否及時到達(dá)，所以在為乘

8、客選擇線路時，力求乘坐花費的時間盡可能少以及路程盡可能短的線路，同時考慮換乘車輛以及乘車費用盡量少的最佳線路,而現(xiàn)實是很難同時滿足上面三個目標(biāo)的。為了使問題簡單化,我們分別以乘車時間、乘車費用以及換乘次數(shù)為目標(biāo)函數(shù)，得到各自的較優(yōu)線路，再通過對比，有效地處理這些線路，最終得出查詢系統(tǒng)給出的結(jié)果。3模型準(zhǔn)備3.1模型假設(shè)1. 假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘（無需支付地鐵費）；2. 假設(shè)所有交通線路都不出現(xiàn)停運或者線路變動；3. 假設(shè)公汽的環(huán)行行駛線路是單向的。3.2符號約定c：相鄰公汽站平均行駛時間（包括停站時間），c3min;d:相鄰地鐵站平均行駛時間（包括停站時間）

9、，d2.5min;e：公汽換乘公汽平均耗時，e5min（其中步行時間2min）；f:地鐵換乘地鐵平均耗時，f4min（其中步行時間2min）;g:地鐵換乘公汽平均耗時，g7min（其中步行時間4min）；h：公汽換乘地鐵平均耗時，h6min（其中步行時間4min）；tj:交通工具與交通工具換乘所需時間；k：地鐵票價，k3元；n:換乘次數(shù)；Nij:乘客在可選擇的從起始站到終點站線路中第i條線路的換乘點（包括始點和終點），j0,1,2,n1,Nz為起點，Ni,n1為終點；Mj:乘客從第j1換乘點上車到第j換乘點的下車所付的票價，j1,2,n1;Wj:公交車從第j1換乘點到第j換乘點經(jīng)過的站點數(shù)（含

10、第j換乘點）j1,2,n1;Cj：公交車在第i線路上從第j換乘點到第j1換乘點線路；kj：公交車在第i線路上從第j1換乘點到第j換乘點經(jīng)過每站所需時間;Tni:只換乘n次乘客從起始站到終點站選擇第i條線路所需要的總時間；%：只換乘n次乘客從起始站到終點站選擇第i條線路所需要的總費用。4基于集合尋線算法的模型4.1集合尋線算法的建立現(xiàn)實乘客換乘的次數(shù)n很小，公司在設(shè)計一個城市公交線路時，為了使線路更合理，一般不會使乘客要通過多次換乘(超過3次)才到達(dá)終點站。則不妨假設(shè)換乘次數(shù)n0,2,nZ。我們可以看到問題中關(guān)鍵要解決的是找出換乘點Nj的具體位置，顯然換乘點是公交線路的交義點，或者說站點至少要有

11、兩條公交線路經(jīng)過。由于公交線路不是一條直線段或者有一定幾何規(guī)律的曲線，所以我們通過代數(shù)的相關(guān)知識，把具有同一屆性的站點放入同一集合中,這樣就把問題轉(zhuǎn)化成代數(shù)問題?；诖怂枷耄覀兘⒁韵录蠈ぞ€算法：步驟1:找出經(jīng)過終點B站的所有公交線路Bj存放到集合Y(Bj|BBj,以及這些線路Bj經(jīng)過的所有站點存放到集合Q。步驟2:找出經(jīng)過起始站A的所有公交線路Ai，存放到集合X(Ai|AAi,以及這些公交線路A經(jīng)過的站點存放到集合P。步驟3:判斷X和Y的關(guān)系：1 .若XY，即存在i,jZ,使得ABj,表示起始站A到終點站B之間有一條或幾條直達(dá)線路，乘客不必?fù)Q乘公交車，算出這些直達(dá)線路各自所需要的時間和票

12、價；通過比較大小，得到該情況下的乘車最少時間孩in和最少費用Smin,以及其相應(yīng)的線路。2 .若XY，則說明起始站A與終點站B之間不存在公交車直達(dá)的情況，只能通過換乘才能到達(dá)終點站B,則要尋找換乘點。步驟4:查找公交線路Ai與公交線路Bj的所有共同站點a,存放到集合I(a|aABj)。集合I中的元素是換乘點。步驟5:判斷集合I:1 .如果集合I,即乘客可以通過一次換乘就能到達(dá)終點站。記錄換乘點及其相應(yīng)線路。2 .如果集合I,即乘客不能通過一次換乘到達(dá)終點站，則要選取新的起始點。步驟6:選取新的起始點：從集合P中任取一站點A(AA),即遍歷集合P中所有的元素，以站點A代替原來的起始站A。轉(zhuǎn)到步驟

13、2,這樣就能找出所有經(jīng)過兩次換乘的線路。步驟7:通過重復(fù)上面的6個步驟可得經(jīng)過n次換乘的所有可能線路。4.2模型的建立4.2.1時間及費用計算我們固定換乘次數(shù)n,通過集合尋線算法，得到通過n次換乘的所有可達(dá)線路，再對這些線路進(jìn)行下面的運算：從起點站A到終點站B,A:經(jīng)過起點站A的第i條公交線路；Bj:經(jīng)過終點站B的第j條公交線路；只通過n次換乘到達(dá)可選擇的線路共有U條，設(shè)第i條乘坐線路的換乘點為Nj,j0,1,n1,膈為起點，N*ni為終點，第i條線路上從第j換乘點到第j1換乘點線路為Cj,其途徑的站點數(shù)Wj,j0,1,ni,所付的票價Mj，相鄰站點平均行駛時間kj,第j個換乘點需要的換乘時間

14、為tj。1) 只考慮公汽線路：a.第i線路所需要的總時間：nnnTkWniijijtijcWen(1j1j1j1其中，c表示公汽相鄰兩站的平均行使時間,e汽車換乘需要的平均耗時b.第i線路所需要的總費用:(2)Sni1,Ch段乘坐單一票價公汽10Wij202，20Wj40Cj3Wij400Wij0段乘坐按段收費公汽nMjj1其中，Mj2）同時考慮公汽與地鐵線路：a.第i線路所需要的總時間:TninkjWjj1其中,kjntijj1Cj段乘坐汽車Cj段乘坐地鐵(3)tje,f,g,h,公汽換乘公汽地鐵換乘地鐵地鐵換乘公汽公汽換乘地鐵b.第i線路所需要的總費用:1,3,nMijj1Cj段乘坐汽車單

15、一票價線路Ch段乘坐地鐵Sni(4)Mj1,2,3,0Wij20Wij404020Cij段乘坐按段收費汽車0,WjWj3）同時考慮公汽、a.第i線路所血女地鐵和步行時間:也麗的總時間：TnikijWjntij(5)c,q段乘坐的是汽車其中，kijd,Cij段乘坐的是地鐵v,d段為步行e,公汽換乘公汽tf,地鐵換乘地鐵ijg,地鐵換乘公汽h,公汽換乘地鐵b.第i線路所需要的總費用：nSniMij（6）Cn段乘坐汽車單一票價線路3,Gj段乘坐地鐵0四20Mijij20Wij40Gj段乘坐按段收費汽車Wj400,Wjj0注意：由于步行不需費用，所以要給個步行線路約束：步行時間不超過To4.2.2目標(biāo)

16、函數(shù)的確定固定了換乘次數(shù)n,確立以下目標(biāo)：1）時間目標(biāo)：min（Tni），即找出只通過n次換乘乘車時間最少的最佳線路及其時間；2）費用目標(biāo)：min（Sni），即找出只通過n次換乘乘車費用最少的最佳線路及其費用。4.2.3最佳線路的處理由于公交線路很多，在同一目標(biāo)下，乘客可能還有較多條最佳線路的選擇，那么我們不可能把所有最佳線路給乘客選擇，乘客也不能接受，所以我們可根據(jù)下面幾點進(jìn)行處理：1）盡量滿足時間最短的情況下，選擇費用最少的線路；2）盡量不要把換乘站點安排在熱門站點（即較多線路交義點，不妨設(shè)最佳線路大于5條時，通過查找經(jīng)過換乘站點的所有交通線路，遍歷所有換乘站點，記錄每一個站點對應(yīng)的r,r

17、較大就是熱門站點）；3）可以隨機(jī)抽取幾條給乘客，避免某條線路上過于繁忙；4）盡量不要把繁忙線路（累加每一條線路上所有站點對應(yīng)的r得到較大的的線路為繁忙線路）安排為最佳線路，避免交通阻塞；4.2.4算法的時間復(fù)雜度由丁所選的換乘次數(shù)最多兩次，所以此算法的時間復(fù)雜度為O(n2)。5基于圖論的模型及其算法實現(xiàn)5.1圖論模型的建立以每個站點為頂點，若站點A到站點B有公交線路并且A與B為相鄰站點，則連一條A到B有向邊，根據(jù)所給的站點與線路我們建立一個得到一個有重邊的有向圖D(V,E)。一條公交線路就是D(V,E)的一條有向路。5.1.1以時間為目標(biāo)的線路模型1)僅考慮公汽線路對丁有向圖D(V,E),給每

18、條有向邊都賦權(quán)c(相鄰公汽站點行駛時間)，若站點A有n條公汽線路，則把A變成n個點&,A2,An(相當(dāng)丁增加了n1假想點，換乘公汽線路需要從A變?yōu)闅?，&,A2,An的每兩頂點都連對稱有向邊，即這是一個n階雙向完全有向圖(見圖1)，每條邊都賦權(quán)e(公汽換乘公汽耗時)，丁是得到一個賦權(quán)有向圖D(V,E,W)。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求D(V,E,W)的對應(yīng)兩頂點的最短有向路問題。圖1圖2同時考慮公汽和地鐵對丁有向圖D(V,E),給每條公汽線路的有向邊都賦權(quán)c,每條地鐵線路的有向邊都賦權(quán)d，若站點B有mn條公交線路(其中m條公汽線，n條地鐵線)則把B變成mn

19、個頂點。1,。2，川Q;Pi,P2,川,0(相當(dāng)丁增加了mn1個假想點)，邊為mn個頂點都連對稱有向邊，它一個mn階完全雙向有向圖(見圖2)。Oi,O2,|U,Om問的邊賦權(quán)e(公汽換乘公汽耗時),PR,川,Pn問的邊賦權(quán)f(地鐵換乘地鐵耗時)，。1,。2，川,Om的每點到日尸2,川,0的每點的邊賦權(quán)h(公汽換乘地鐵耗時)，P,%川,Pn的每點到Ol,。2,川,Om的每點的邊賦權(quán)g(地鐵換乘公汽耗時)。得到一個賦權(quán)有向圖H(V,E,W)。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求H(V,E,W)的對應(yīng)兩頂點的最短有向路問題。2) 同時考慮公交與步行時間在賦權(quán)有向圖H(V,E,W)中任兩

20、點之間(除去假想點)連接對稱有向邊，其邊賦權(quán)為v,從而得到一個新的賦權(quán)有向圖J(V,E,W)。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求J(V,E,W)的對應(yīng)兩頂點的最短有向路問題。5.1.2以費用為目標(biāo)的線路模型1) 僅考慮公汽的線路對丁公交線路有向圖D(V,E),給所經(jīng)過的同一公汽線路上的最大站點數(shù)n的有向路進(jìn)行賦權(quán)：若單一票價，則賦權(quán)fo；若分段計價，則賦權(quán)1,0n20f(n)2,21n40，丁是得到一個動態(tài)賦權(quán)有向圖G(V,E,W)。3,n41則任意兩公汽站點之間線路最少費用選擇問題就轉(zhuǎn)化為求動態(tài)賦權(quán)有向圖G(V,E,W)的對應(yīng)兩頂點的最短有向路問題。2) 同時考慮公汽和地鐵對

21、丁城市公交線路自然圖D(V,E),給所經(jīng)過的同一公汽線路上的最大站點有向路進(jìn)行賦權(quán)：若單一票價，則賦權(quán)fo；若分段計價，則賦權(quán)1,0n20f1(n)2,21n40(n為最大站點數(shù))，給所經(jīng)過的同一地鐵線路賦權(quán)f?,丁是3,n41得到一個動態(tài)賦權(quán)有向圖H(V,E,W)0丁是任意兩公交站點之間線路最少費用選擇問題就轉(zhuǎn)化為求H(V,E,W)的對應(yīng)兩頂點的最短有向路問題。3) 同時考慮公交和步行由丁步行是不需要費用的，則在賦權(quán)圖是H(V,E,W)上任意兩點問連上對稱的有向邊，但其權(quán)為0,顯然費用最少為0,即步行到終點站。顯然是不合理的。故這里不能用賦權(quán)圖對應(yīng)線路。5.2最短路徑算法上面模型可以通過如算

22、法實現(xiàn)5:f(i)minWjf(j),in1,2,1步驟1:通過計算式子j(其中n是終點，1f(n)0是起點，終點的f(n)0,從終點出發(fā)逐步向起點推算，j是與i相鄰，f(j)為已知j點到終點的最小線路)，得到最短路。此算法時間復(fù)雜度為：O(n2)步驟2:通過對上面最短路經(jīng)過的站點的搜索和判斷，找出換乘點和換乘次數(shù)。步驟3:把步驟1最短路的權(quán)值與步驟2換乘目標(biāo)值相加，得到最終的最短路。6模型的求解因為乘坐的費用比較少，乘客還是偏重與對時間的選擇，本文下面的求解都是以時間為目標(biāo)得到的最佳線路。6.1基丁集合尋線算法模型的求解6.1.1僅考慮公汽根據(jù)模型求解出問題中通過模型得到了6對查詢點都不能通

23、過一條線路直接到達(dá)，也得到1,2次換乘的最佳線路。見下表：S3359tS1828的不同線路乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L436下行S1784L16732101312L436下行S1784L21732101313L015下行S2903L027上行S1784L167下行2173324L015下行S2903L027上行S1784L217下行2173325L015下行S2903L201上行S1790L041上行2173326L015下行S2903L201上行S0458L041上行2173327L015下行S2903L201上行S1792L041上行217332

24、8L015下行S2903L201上行S1783L041上行2173329L015下行S2903L201上行S1671L041上行21733210L123S2903L027S1784L167217332S1557tS0481的不同最優(yōu)解路線上行上行下行11L123上行S2903L027上行S1784L217下行21733212L123上行S2903L201上行S1790L041上行217332乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L084下行S1919L189下行S3186L46032106222L363下行S1919L189下行S3186L4603210622S

25、0971tS0485的最佳路線S0008tS0073最佳路線乘車方案線路一換乘點1線路二換乘點2線路總站數(shù)總時間總費用換乘次數(shù)1L013下行S2184L417下行41128312L013上行S1690L140下行S2654L46932106323L013下行S2517L296上行S2480L41732106324L024下行S1690L140下行S2654L46932106325L094上行S1690L140下行S2654L46932106326L119下行S1690L140下行S2654L46932106327L263下行S1690L140下行S2654L4693210632乘車方案線路一換

26、乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L159下行S2683L058下行2683212L159下行S0291L058下行2683213L159下行S3614L058下行2683214L159下行S0491L058下行268321S0148tS0485的不同最優(yōu)解路線5L159下行S2559L058下行2683316L159下行S3315L058下行2683317L159下行S2559L464上行2683318L159下行S0400L474上行2683219L159下行S2633L474上行26832110L159下行S3053L474上行26832111L355下行S2263L

27、345上行26832112L355下行S3917L345上行26832113L355下行S2303L345上行26832114L463下行S2083L057上行26832115L198上行S3766L296上行S2184L345196732乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L308上行S36L156上行S3351L417下行3210622S0087tS3676的最佳路線乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總

28、費用換乘次數(shù)1L454上行S3496L209下行2065212L021下行S0088L231環(huán)行S0427L462下行124632通過模型得到了6對查詢點都不能通過一條線路直接到達(dá)，換乘一次，兩次的較優(yōu)線路，根據(jù)乘客的不同的需求，確定目標(biāo)，選擇適合自己的最佳線路。例如上面從站點S3359到站點S1828,如果乘客不想多次換乘，那么他就可以選擇換乘一次的兩條線路的一條，如果乘客想盡快到達(dá)終點站，那么他可以選擇換乘兩次的10條線路中的一條。6.1.2同時考慮公汽和地鐵我們先算出問題中6對查詢點一定上要一次地鐵的最佳線路見表3:表3乘坐一次地鐵的最佳線路始點r終點公汽線路一換乘點地鐵線路地鐵起點地鐵

29、終點公汽線路二換乘點時間費用S3359S1828線路超過二次換乘，無法提供具體線路S1557S0481L084下行S0978T2D32D24L516上行S0537116.55S0971S0485L094上行S0567T1D1D20L417下行S207999.55S0008S0073L159下行S2633T1D13S12L057上行S060975.55S0148S0485L024下行S1487T1D2D20L417下行S2079915S0087rS3676T2D27D36363再與只考慮公汽的最佳線路進(jìn)行比較，選擇時間最短的，得到S3359TS1828,S1557S0481,S0008S0073

30、只乘坐公汽，S0971S0485,S0148tS0485,S0087tS3676要乘坐地鐵才能獲得最短時間。6.2圖論模型的求解因為根據(jù)此模型得到的結(jié)果，根上面模型基本一致，在此本文就不再贅述，有興趣的讀者可以通過算法得到。7模型評價7.1基于集合尋點算法的模型的評價基于集合尋點算法的模型所給的查詢系統(tǒng)是固定換乘次數(shù)n基礎(chǔ)上，算出能通過n次換乘的所有線路。再通過對不同換乘數(shù)所得到的這些最佳線路，對這些線路的時間，費用的分別比較，通過層層的對比篩選排除，通過一些條件對最佳線路的進(jìn)行處理，最后乘客可以根據(jù)自己的不同需求進(jìn)行選擇。其優(yōu)點：模型中緊緊抓住選擇最佳線路問題的突破點一一換乘次數(shù)，通過集合的

31、相關(guān)知識把難點一一換乘點的具體位置的確定，轉(zhuǎn)化成確定一些集合間的交集，從而把站點，線路與集合中的元素一一對應(yīng)起來，建立起集合尋線算法，再根據(jù)集合相關(guān)公式，通過線路計算式子，有效地計算出最佳線路，并且考慮一些因素，如時間等對最佳線路進(jìn)行處理。算法中有效的摒棄一些無效站點，從而大大減少了計算量和時間，明顯比運用圖論求得最短路要有效的多。能為查詢者提供不同換乘次數(shù)下時間與路程最少的最佳線路，以及對于多條最佳線路，查詢系統(tǒng)盡量采用不太熱門的公交線路，隨機(jī)地為查詢者提供指定數(shù)目的線路，避免同一最佳線路過熱的情況發(fā)生。其缺點：就是此模型只能為查詢者提供換乘次數(shù)較少下的最佳線路，當(dāng)換乘次數(shù)大于三時，模型實現(xiàn)

32、的時間較長。7.2圖論模型的評價由圖論模型所得的查詢系統(tǒng)，是以圖論知識中的最短路有向圖為基礎(chǔ)，對不同線路經(jīng)過同一站點時，假設(shè)多個假想點，并將各不同站點之間所需時間作為權(quán)，對各線路站點賦權(quán)，分別確定以時間、費用、換乘為目標(biāo)轉(zhuǎn)化為尋找有向的完全圖，并根據(jù)實際情況，建立出動態(tài)賦權(quán)有向圖，得出最佳線路。其優(yōu)點：模型充分利用公交線路其實就是一個有向圖，而且在比較成熟的最短路算法基礎(chǔ)上，通過插入換乘時間，得到最佳線路。算法還是比較容易實現(xiàn)。其缺點：模型在引入步行，求費用最少，卻不能實現(xiàn)。而且運用最短路算法，得到不一定是真正意義上的最佳線路，只能是近似最佳線路。8模型的推廣建立此模型的思想，不但能應(yīng)用到現(xiàn)在

33、這種公交線路中，并能推廣到海、陸、空多種交通線路之間尋找最優(yōu)線路。通過實際情況對模型的進(jìn)行調(diào)整，模型就能適應(yīng)更多情況。例如圖論模型中對有向圖的權(quán)進(jìn)行調(diào)整就能實現(xiàn)不同時間差站點的最佳線路的選擇。參考文獻(xiàn)1姜啟源，謝金星.數(shù)學(xué)模型M（第三版）.北京:高等教育出版社,2003.2孫惠泉.圖論及其應(yīng)用M.北京:,2004.3邊肇祺，張學(xué)工等.模式識別M（第二版）.北京游華大學(xué)出版社,1999.4蔡自興，徐光祐.人工智能及其應(yīng)用M（第二版）.北京：活華大學(xué)出版社,1996.5袁新生，邵大宏,郁時煉.LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用M.北京：科學(xué)出版社,2007.程序附錄部分程序%數(shù)據(jù)的初始處理c

34、lcfid=fopen('QCLS.txt','r');Data=fread(fid);len=length(Data);gcl=0;qq=0;fori=1:len-1ifchar(Data(i)='L'&qq=0gcl=gcl+1;GCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3);i=i+4;elseifchar(Data(i)='L'&qq=1forj1=1:length(GCLSgcl3)GCLSgcl4j1=GCLSgcl3length(GCLSgc

35、l3)+1-j1;endgcl=gcl+1;qq=0;GCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3);i=i+4;o'&char(Data(i+4)='S'分單上下環(huán)'o'&char(Data(i+4)='S'分單上下環(huán)'o'&char(Data(i+4)='S'分單上下環(huán)'elseifchar(Data(i)*256+Data(i+1)='x=3;i=i+3;qq=1;s=0;elseifchar(Data

36、(i)*256+Data(i+1)='GCLSgcl2=1;i=i+8;elseifchar(Data(i)*256+Data(i+1)='GCLSgcl2=2;i=i+11;elseifchar(Data(i)*256+Data(i+1)='x=3;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1)='x=4;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1)='x=5;i=i+4;qq=0;s=0;elseifchar(Data(i)='S's=s

37、+1;GCLSgclxs=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3),Data(i+4);clci=i+4;endendfori1=1:520iflength(GCLSi1)=5n=length(GCLSi13);GCLSFi11=GCLSi11;GCLSFi12=GCLSi12;fori2=1:nGCLSFi13i2=GCLSi13n-i2+1;endn=length(GCLSi14);GCLSFi11=GCLSi11;GCLSFi12=GCLSi12;fori2=1:nGCLSFi14i2=GCLSi14n-i2+1;endelseiflength(GCLSi1)=5n=len