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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、過一條線路直接到達(dá)，也得到1,2次換乘的最佳線路。見下表：S3359tS1828的不同線路乘車方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(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乘車方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L084下行S1919L189下行S3186L46032106222L363下行S1919L189下行S3186L4603210622S

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

26、乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(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乘車方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L308上行S36L156上行S3351L417下行3210622S0087tS3676的最佳路線乘車方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總

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

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

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

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

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

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