乘公交看奧運

1、承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則 我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵 件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問 題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他 公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正 文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反 競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從 A/B/C/D中選擇一項填寫）：B我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾?/p>

2、的全名）：重慶大學(xué)參賽隊員（打印并簽名）：1.熊國剛2. 王杰3. 黎明指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：龔劬日期：2007年9月21日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：乘公交，看奧運【摘要】本文要解決的問題是以即將舉行的 08年北京奧運會為背景而提出的。 人們?yōu)榱四墁F(xiàn)場觀看奧運會，必然會面對出行方式與路線選擇的問題。 因此如何 快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的

3、關(guān)鍵。鑒于公交系統(tǒng)網(wǎng)絡(luò)的復(fù)雜性，我們沒有采用常規(guī)的 Dijkstra算法，而采用了 高效的廣度優(yōu)先算法。其基本思想是從經(jīng)過起（始）點的路線出發(fā)，搜尋出轉(zhuǎn)乘 次數(shù)不超過兩次的可行路線，然后對可行解進(jìn)行進(jìn)一步處理。為滿足不同查詢者 要求，我們對三個問題都分別建立了以時間、 轉(zhuǎn)乘次數(shù)、費用最小為目標(biāo)的優(yōu)化 模型。針對問題一（只考慮公汽系統(tǒng)），我們建立了模型一并通過 VC+編程得到 了任意兩個站點間的多種最優(yōu)路線， 并得出所求站點間最優(yōu)路線的最優(yōu)值， 如下 表所示：出發(fā)站1S33591S15571S09711S00081S01481S00871終點站VS1828S0481VS0485S0073VS04

4、85VS3676最短耗時（min）641061066710646最少轉(zhuǎn)乘次數(shù)（次）121122最少費用（元）333233模型二是根據(jù)問題二（同時考慮公汽和地鐵系統(tǒng)）建立的，同樣用VC+編程得到所求站點間的最優(yōu)路線，如下表所示：出發(fā)站1S33591S15571S09711S00081S01481S00871終點站S1828VS0481S0485S0073S0485VS3676最短耗時（min）64106965587.533最少轉(zhuǎn)乘次數(shù)（次）12P 1120最少費用（元）333233對問題三（將步行考慮在內(nèi)）我們建立了模型三的優(yōu)化模型，然后在模型改 進(jìn)里又建立了圖論模型。本文的主要特點在于，所用算

5、法的效率十分顯著。在對原始數(shù)據(jù)僅做簡單預(yù) 處理的條件下，搜索任意站點間的最優(yōu)路線所需的平均時間不超過 0.5秒。另外, 本文所建立的模型簡單、所用算法比較清晰，易于程序?qū)崿F(xiàn)，對公交線路自主查 詢計算機(jī)系統(tǒng)的實現(xiàn)具有現(xiàn)實指導(dǎo)作用。關(guān)鍵字：轉(zhuǎn)乘次數(shù)廣度優(yōu)先算法查詢效率實時系統(tǒng)問題的重述傳承華夏五千年的文明，夢圓十三億華夏兒女的暢想，2008年8月8日這個不平凡的日子終于離我們越來越近了！在觀看奧運的眾多方式之中，現(xiàn)場觀看無疑是最激動人心的。為了迎接 2008年奧運會，北京公交做了充分的準(zhǔn)備，首 都的公交車大都煥然一新，增強(qiáng)了交通的安全性和舒適性，公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便

6、利。但同時也面臨多條線路的選擇問題。 為滿足公眾查詢公交線路的選擇問題，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選 擇問題的自主查詢計算機(jī)系統(tǒng)。這個系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實際情況出發(fā)考 慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與 算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對起始站到終到站最佳路線。、S3359 S1828 (2) 、S155L S0481 (3)、S0971 S0485、S0008S0073 (5) 、S014IS0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，解

7、決以上問題。3、假設(shè)又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問 題的數(shù)學(xué)模型。二符號說明Li :第i條公汽線路標(biāo)號,i=1,210400，當(dāng) i空520時，表示上行公汽路線,當(dāng)i 520時，匚表示與上行路線Lio相對應(yīng)的下行公汽路線；Si,g :經(jīng)過第i條公汽路線的第g個公汽站點標(biāo)號；：第j條地鐵路線標(biāo)號,j=1,2;Dj,h :經(jīng)過第j條地鐵線路的第h個地鐵站點標(biāo)號；LSn :轉(zhuǎn)乘n次的路線；Tk :選擇第k種路線的總時間；N1 k :選擇第k種路線公汽換乘公汽的換乘次數(shù)；N2k :選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；N3k :選擇第k種路線地鐵換乘公汽的換乘次數(shù)；N4

8、k:選擇第k種路線公汽換乘地鐵的換乘次數(shù)；Wk,m :第k種路線、乘坐第m輛公汽的計費方式，其中:Wkm =1表示實行單一票價，Wk,m =2表示實行分段計價；CL k, m :第k種路線，乘坐第m輛公汽的費用；Ck :選擇第k種路線的總費用；MSk,m :選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公汽站個點數(shù)；MD k,n:選擇第k種路線，乘坐第n路地鐵需要經(jīng)過的地鐵站個點數(shù)；FSk,m :表示對于第k種路線的第m路公汽的路線是否選擇步行，F(xiàn)Sk,m為0-1變量，F(xiàn)Sk,m =0表示不選擇步行，F(xiàn)Sk,m =1表示選擇步行；FD k,n :對于第k種路線的第n路地鐵的路線是否選擇步行，F(xiàn)D k

9、,n為0-1變量,FD k,n =0表示不選擇步行，F(xiàn)D k,n =1表示選擇步行；三模型假設(shè)3.1基本假設(shè)1、相鄰公汽站平均行駛時間2、相鄰地鐵站平均行駛時間3、公汽換乘公汽平均耗時：4、地鐵換乘地鐵平均耗時：5、地鐵換乘公汽平均耗時： &公汽換乘地鐵平均耗時：（包括停站時間）:3分鐘 （包括停站時間）:2.5分鐘 5分鐘（其中步行時間 4分鐘（其中步行時間 7分鐘（其中步行時間 6分鐘（其中步行時間2分鐘）2分鐘）4分鐘）4分鐘）7、公汽票價：分為單一票價與分段計價兩種; 單一票價：1元其中分段計價的票價為:020站：1元2140站：2元40站以上：3元8、地鐵票價：3元（無論地鐵

10、線路間是否換乘）9、假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘，且無需支 付地鐵費3.2其它假設(shè)10、查詢者轉(zhuǎn)乘公交的次數(shù)不超過兩次；11、所有環(huán)行公交線路都是雙向的；12、地鐵線T2也是雙向環(huán)行的；13、各公交車都運行正常，不會發(fā)生堵車現(xiàn)象;14、公交、列車均到站停車四問題的分析在北京舉行奧運會期間，公眾如何在眾多的交通路線中選擇最優(yōu)乘車路線或 轉(zhuǎn)乘路線去看奧運，這是我們要解決的核心問題。針對此問題，我們考慮從公交 線路的角度來尋求最優(yōu)線路。首先找出過任意兩站點（公眾所在地與奧運場地） 的所有路線，將其存儲起來，形成數(shù)據(jù)文件。這些路線可能包含有直達(dá)公交線路， 也有可能是兩條公交

11、線路通過交匯而形成的（此時需要轉(zhuǎn)乘公交一次），甚至更多公交線路交匯而成。然后在這些可行路線中搜尋最優(yōu)路線。對于路線的評價，我們可以分別以總行程時間，總轉(zhuǎn)乘次數(shù)，總費用為指標(biāo)， 也可以將三種指標(biāo)標(biāo)準(zhǔn)化后賦以不同權(quán)值形成一個綜合指標(biāo)。而最優(yōu)路線則應(yīng)是總行程時間最短，總費用最少或總轉(zhuǎn)乘次數(shù)最少，或者三者皆有之。之所以這樣 考慮目標(biāo)，是因為對于不同年齡階段的查詢者， 他們追求的目標(biāo)會有所不同，比 如青年人比較熱衷于比賽，因而他們會選擇最短時間內(nèi)到達(dá)奧運賽場觀看比賽。 而中年人則可能較傾向于綜合指標(biāo)最小，即較快、較省，轉(zhuǎn)乘次數(shù)又不多。老年 人總愿意以最省的方式看到奧運比賽。而對于殘疾人士則總轉(zhuǎn)乘次數(shù)最少

12、為好。 不同的路線查詢需求用圖4.1表示如下：圖4.1公交線路查詢目標(biāo)圖經(jīng)分析，本問題的解決歸結(jié)為一個求最短路徑的問題，但是傳統(tǒng)的Dijkstra最短路徑算法并不適用于本問題，因為 Dijkstra算法采用的存儲結(jié)構(gòu)和計算方法 難以應(yīng)付公交線路網(wǎng)絡(luò)拓?fù)涞膹?fù)雜性，而且由于執(zhí)行效率的問題，其很難滿足實 時系統(tǒng)對時間的嚴(yán)格要求。為此我們在實際求解的過程中，采用了效率高效得廣度優(yōu)先算法，其基本思 路是每次搜索指定點，并將其所有未訪問過的近鄰點加入搜索隊列， 循環(huán)搜索過 程直到隊列為空。此方法在后文中有詳細(xì)說明。五建模前的準(zhǔn)備為了后面建模與程序設(shè)計的方便，在建立此模型前，我們有必要做一些準(zhǔn)備 工作。5.

13、 1數(shù)據(jù)的存儲由于所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲 格式。從所給文件中讀出線路上的站點信息，存入txt文檔中，其存儲格式為：兩行數(shù)據(jù)，第一行表示上行線上的站點信息，第二行表示下行線的站點信息，其 中下行路線標(biāo)號需要在原標(biāo)號的基礎(chǔ)上加上520,用以區(qū)分上行線和下行線。如果上行線與下行線的站點名不完全相同，那么存儲的兩行數(shù)據(jù)相應(yīng)的不完 全相同，以公交線L009為例：L009:3739 0359 1477 2159 2377 2211 2482 2480 3439 1920 1921 0180 2020 3027 2981L529:2981 3027 2020 0180

14、 1921 1920 3439 3440 2482 2211 2377 2159 14780359 3739L529為L009所對應(yīng)的下行線路。如果下行線是上行線原路返回，那么存儲的兩行數(shù)據(jù)中的站點信息剛好順序 顛倒，以公交線路L001為例：L001:0619 1914 0388 0348 0392 0429 0436 3885 3612 0819 3524 0820 3914 0128 0710L521:0710 0128 3914 0820 3524 0819 3612 3885 0436 0429 0392 0348 0388 1914 0619如果是環(huán)線的情況（如圖5.1所示），則可以

15、等效為兩條線路：順時針方向：S1SP S3 S1 S2 SI S4; 逆時針方向：S1S4 S3 S2 S1 S4 S3 S2。經(jīng)過分析，此兩條”單行路線”線路的作用等同于原環(huán)形路線圖5.1環(huán)行線路示意圖以環(huán)形公交線L158為例，此環(huán)形路線存儲數(shù)據(jù)如下：L153: 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 12151217 251 2604 2606 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 260

16、6L673: 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 1701215 3513 264 814171 812 1212 2355 649 534 2606 2604 251 1217 1585 172 2600 811 170 171 812 1212 2355 649在這里，L153被看作成上行路線，L673被當(dāng)成下行路線。這樣對于每條公交 線路都可以得到兩行線路存儲信息。5. 2搜尋經(jīng)過每個站點的公交路線處理5.1所得信息，找出通過每個站點的所有公交路線，并將它們存入數(shù)據(jù) 文件中。例如，通過搜尋得出經(jīng)過站點 S0

17、001的線路和經(jīng)過站點S0002的線路如下: 經(jīng)過S0001的線路有：L421經(jīng)過 S0002 的線路有：L027 L152 L365 L395 L4855. 3統(tǒng)計任意兩條公交線路的相交（相近）站點依次統(tǒng)計出任意兩條公交線路之間相交（相近）的站點，將其存入1040X 1040的矩陣A中，但是這個矩陣的元素是維數(shù)不確定的向量，具體實現(xiàn)的時候 可以將用隊列表示。例如：公交線路L001與公交線路L025相交的站點為A125= S0619, S1914, S0388, S0348。六模型的建立與求解6. 1模型一的建立該模型針對問題一，僅考慮公汽線路，先找出經(jīng)過任意兩個公汽站點Si,g與S o ,g

18、最多轉(zhuǎn)乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。6. 1. 1公汽路線的數(shù)學(xué)表示任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分 別對應(yīng)圖6.1的四種情況。該圖中的 A B為出發(fā)站和終點站，C、D E、F為轉(zhuǎn) 乘站點。圖6.1公汽路線圖對于任意兩個公汽站點Si,g與S o,g，經(jīng)過Si,g的公汽線路表示為Li，有-Lo ；Si,gLi;經(jīng)過So,g的公汽線路表示為Lo，有Sq,g1）直達(dá)的路線LSo （如圖6.1 （a）所示）表示為:LSo二：Li1Si , g Li1, S(o g Li12）轉(zhuǎn)乘一次的路線LS1 （如圖6.1（b）所示）表示為:LS =&

19、#39;(Li1, Li2i)S,gULi1,Sq,g,Li2；Lii2 - LSo；SC Li1 且SC J2?其中：SC為Li1，Li2的一個交點;3）轉(zhuǎn)乘兩次的路線LS2 （如圖6.1（c）所示）表示為:LS2 ='(Li1, Li2，Li3 ) S ,g 匸 Li1, S i ,g 匸 Li2；(Li1,Li3),(Li3,Li2)( LS1； Li1, Li2 LS通過以上轉(zhuǎn)乘路線的建模過程，可以看出不同轉(zhuǎn)乘次數(shù)間可作成迭代關(guān)系， 進(jìn)而對更多轉(zhuǎn)乘次數(shù)的路線進(jìn)行求尋。 不過考慮到實際情況，轉(zhuǎn)乘次數(shù)以不超過 2次為佳，所以本文未對轉(zhuǎn)乘三次及三次以上的情形做討論。6. 1. 2最優(yōu)

20、路線模型的建立找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進(jìn)行選擇，找出最優(yōu)路線了 ：1）以時間最短作為最優(yōu)路線的模型：行程時間Tk等于乘車時間與轉(zhuǎn)車時間之和N 1 + 1（6.1 式）Min Tk =3 匯送（MSk, m1）+5xN1 k m 二o m1= ,2,gggN1k+1; k=1,2,ggg, k其中，第k路線是以上轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少作為最優(yōu)路線的模型：M in Nk1（ 6.2 式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次的優(yōu)先次序來考慮3）以費用最少作為最優(yōu)路線的模型：M inC=wmCkL m（6.3 式）1Wk,m=1或 W

21、k,m =2,0M Sk,mE20其中，CLk,m=2Wjm",21M Sk,mW40（6.4 式）3Wk,m",40M Sk,m6. 1. 3模型的算法描述針對該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個站點間的可行 路線，然后搜索出最優(yōu)路線。現(xiàn)將此算法運用到該問題中，結(jié)合圖6.2敘述如下:（該圖中的 Si,g、Sq,g、Sl,l、S2,1、S2,2 表示公汽站點，Li、L2、L3、L4、L5、L6表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點Si,g到點S i g直 達(dá)、轉(zhuǎn)乘一次、轉(zhuǎn)乘兩次的情況）圖6.2 公交直達(dá)、轉(zhuǎn)乘圖（1）首先輸入需要查詢的兩個站點

22、Si,g與Sq g （假設(shè)Si,g為起始站，S9 g 為終點站）；（2） 搜索出經(jīng)過Si,g的公汽線路Li （i=1,2,m）和經(jīng)過Sq,g的公汽線路 tq （9 =1,2,，n），存入數(shù)據(jù)文件；判斷是Li與LOi是否存在相同路線，若 有則站點Si,g與Sq,g之間有直達(dá)路線（如圖6.2中的Li），則該路線是換乘次數(shù) 最少（換乘次數(shù)等于0）的路線，若有多條直達(dá)路線，則可以在此基礎(chǔ)上找出時間 最省的路線；這樣可以找出所有直達(dá)路線，存入數(shù)據(jù)文件；（3）找出經(jīng)過Si,g的公汽線路Li（如圖6.2中的L2）中的另一站點Sigi和經(jīng) 過Sq,g的公汽線路0_o中的另一站點Sqlgl。判斷Sig與Sqlg

23、i中是否存在相 同的點，若存在（如圖6.2中的Si,i）則站點Si,g與So,g間有一次換乘的路線（如 圖6.2中的L2與La），該相同點即為換乘站點；這樣又找出了一次換乘路線，存 入數(shù)據(jù)文件；（4）再搜索出經(jīng)過Li （如圖6.2中的L4）線路上除了站點Si,g的另一站點 Si2,gi（如圖6.2中的S2,i）的公汽線路Li6（如圖6.2中的L6），找出公汽線路Li6上 的其他站點Si2,g2 ；判斷，如果Si2,g2與經(jīng)過S q曲的公汽線路0_彳中的其他站點 Sq2g2存在相同的點（如圖6.2中的S2,2），則Si,g與Sq,g間有二次換乘的路線 （如圖6.2中的L4、L6、L5），該相同點

24、和點Si2,gi是換乘站點；將此二次換乘的路線存入數(shù)據(jù)文件中；（5）對上述存儲的經(jīng)過兩個站點Si,g與Sq g的不同路線，根據(jù)不同模型進(jìn)行最優(yōu)路線進(jìn)行搜索，得出查詢者滿意的最優(yōu)路線。6. 1.4 模型一的求解根據(jù)以上算法和前面建立的模型一，用VC+進(jìn)行編程（程序見附錄）就可以得出不同目標(biāo)下的最優(yōu)路線。1）以耗時最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828耗時最少為64 min，耗時最少的最優(yōu)路線（轉(zhuǎn)乘 次數(shù)較少，費用較省的路線）有 28條（注：表6.1選擇了其中的10條表示）； 起始站S1557到終到站S0481耗時最少為106 min,耗時最少的最優(yōu)路線有2條;起始站S0971到終

25、到站S0485耗時最少為106 min,耗時最少的最優(yōu)路線有2條; 起始站S0008到終到站S0073耗時最少為67 min,耗時最少的最優(yōu)路線有2 條;起始站S0148到終到站S0485耗時最少為106 min,耗時最少的最優(yōu)路線有3條; 起始站S0087到終到站S3676耗時最少為46 min,耗時最少的最優(yōu)路線有12條; 其耗時最少的最優(yōu)路線如表6.1所示。表6.1耗時最少的最優(yōu)路線表起始 站公汽線 路就站公汽線 路就站公汽線 路終到 站轉(zhuǎn)乘 次數(shù)所需 費用S3359L0535S2903L1005S1784L0687S182823S3359L0535S2903L1005S1784L073

26、7S182823S3359L0123S2903L1005S1784L0687S182823S3359 L0123:S2903L1005S1784:L0737 :S18282P 3S3359L0652S2903L1005S1784L0687S182823S3359L0652S2903L1005S1784L0737S182823S3359 L0844:S2027L1005S1784:L0687 :S18282:3S3359 1L0844:S2027L1005S1784L0737 nS182823S3359L0844S1746L1005S1784L0687S182823S3359L0844S1746

27、L1005S1784L0737S18282r 3S1557 1L0604:S1919L0709S3186L0980S048123S1557L0883S1919L0709S3186L0980S048123S0971L0533S2517L0810S2480L0937S048523S0971 L0533S2517L0296S2480L0937 S04852P 3S0008L0198S3766L0296S2184L0345S007321 3S0008L0198S3766L0296S2184L0345S007323S01481L0308S0036L0156S2210L0937 :S04852r 3S01

28、48L0308S0036L0156S3332L0937S048523S0148L0308S0036L0156S3351L0937S048523S0087 |L0541:S0088L0231S0427:L0097 :S36762:3S0087L0541S0088L0231S0427L0982S367623S0087L0541S0088L0901S0427L0097S367623S0087L0541:S0088L0901S0427L0982 :S36762r 3S0087L0206S0088L0231S0427L0097S367623S0087L0206S0088L0231S0427L0982S3

29、67623S0087L0206S0088L0901S0427L0097S367623S0087 1L0206S0088L0901S0427L0982 S367623S0087L0974S0088L0231S0427L0097S367623S0087L0974S0088L0231S0427L0982S367623S0087 1L0974:S0088L0901S0427L0097 S36762P 3S0087L0974S0088L0901S0427L0982S3676232）以轉(zhuǎn)乘次數(shù)最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828的最少轉(zhuǎn)乘次數(shù)為1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu) 路線（所需時間較短

30、，費用較省的路線）有 2條；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有2條與耗時最少的最優(yōu)路線相同（表示在表 6.1中，下同）；起始站S0971到終到站S0485的最少轉(zhuǎn)乘次數(shù)為1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu) 路線有1條；起始站S0008到終到站S0073的最少轉(zhuǎn)乘次數(shù)為1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu) 路線有9條；起始站S0148到終到站S0485的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu) 路線有3條與耗時最少的最優(yōu)路線相同；起始站S0087到終到站S3676的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu) 路線有6條與耗時最少的最優(yōu)路線相同；其余轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線路線如表

31、6.2所示表6.2轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線表起始站公汽線路中轉(zhuǎn)站公汽線路終到站耗時所需費用S3359L0956S1784L0687:S1828 11013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L05781S0073 1832S0008L0679S0491L0578S0073:832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073 :832S0008L0679S3614L0578S0073 :832S0008L0875S2263L03

32、45S0073832S0008L0875S2303L0345S0073 :832S0008L0875S3917L0345 丁S0073 :832S0008L0983S2083L0057S00738323）以費用最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828的最少費用為3元，最少費用的最優(yōu)路線（所 需時間較短，轉(zhuǎn)乘次數(shù)較少的路線）有30條，其中28條路線所需時間為64 min, 轉(zhuǎn)乘次數(shù)為2次，另外兩條路線所需時間為101 min，轉(zhuǎn)乘次數(shù)為1次；起始站S1557到終到站S0481的最少費用為3元，最少費用的最優(yōu)路線有2 條，所需時間為106 min，轉(zhuǎn)乘次數(shù)為2次；起始站S0971到終

33、到站S0485的最少費用為3元，最少費用的最優(yōu)路線有3 條，其中兩條所需時間為106 min,轉(zhuǎn)乘次數(shù)為2次，另外一條所需時間為128 min， 轉(zhuǎn)乘次數(shù)為1次；起始站S0008到終到站S0073的最少費用為2元，最少費用的最優(yōu)路線有9 條，所需時間為83 min，轉(zhuǎn)乘次數(shù)為1次；起始站S0148到終到站S0485的最少費用為3元，最少費用的最優(yōu)路線有3 條, 所需時間為106min，轉(zhuǎn)乘次數(shù)為2次；起始站S0087到終到站S3676的最少費用為3元，最少費用的最優(yōu)路線有 12條，所需時間為46 min，轉(zhuǎn)乘次數(shù)為2次；最少費用的最優(yōu)路線表示在表 6.1和表6.2中。6. 2. 1模型二的建立

34、該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然后尋找最優(yōu) 路線。對于地鐵線路，也可以將其作為公交線路，本質(zhì)上沒有什么區(qū)別，只不過 乘車費用、時間，換乘時間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公 交的轉(zhuǎn)乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中 的基本相同?，F(xiàn)建立模型二下的最優(yōu)路線模型。1）以時間最短的路線作為最優(yōu)路線的模型：可行路線的總時間為乘公交（公汽 和地鐵）時間與公汽與地鐵換乘、公汽間、地鐵間換乘時間之和。Min T3=（MSk,mT）2 5江 （MD 1）5 XN1mn（6.5 式）4 N27N36 N4k其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘

35、路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：Min N 1 N 2 N 3 kN 4（6.6 式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次（包括公交與地鐵間的轉(zhuǎn)乘） 的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：可行路線的費用為乘公交和地鐵費 用的總和。Min Ck» eg3N k4（ 6.7 式）m其中，CLk,m仍滿足（6.4式）。6. 2. 2模型二的求解不難發(fā)現(xiàn)，問題一是問題二解的一部分。在問題二中，新產(chǎn)生的最優(yōu)解主 要源于在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示：從點A到B,圖（a）表示的是通過兩公交線路上相鄰公汽站S1,S

36、2進(jìn)行一次轉(zhuǎn)乘；圖（b）表示利用地鐵站進(jìn)行二次轉(zhuǎn)乘；圖（c）表示利用另一條公汽路線為中 介進(jìn)行二次轉(zhuǎn)乘。鐵路線路引入給題目的求解增加了難度，為了形象了解為數(shù)不多的兩條鐵路 間的交叉關(guān)系，我們通過 matlab編程（程序見附錄）作出了兩條鐵路的位置關(guān) 系圖，如圖6.3所示。圖6.3 T1與T2鐵路位置關(guān)系圖注：圖四中的直線表示 T1鐵路線，圓表示T2鐵路線，數(shù)值表示站點，例如 1 表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網(wǎng)上 查詢到的北京地鐵示意圖（如圖 6.4所示）相吻合。囲K東站99B站*:Kn站木-«鬼唱 *-14強(qiáng)«營主螢帀 Hr*荃糕

37、椿%用MZKIJU兒 *#琳W WW圖6.4北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個站點間的可行線路，再將目標(biāo)函數(shù)分別用模型二建立的模型表達(dá)式表達(dá)，用VC+進(jìn)行編程（程序見附錄）求得出考慮地鐵情況的最優(yōu)路線。1）以轉(zhuǎn)乘次數(shù)最少為目標(biāo)的最優(yōu)路線1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)0次，即有直達(dá)路線，直達(dá)2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)起始站S0008到終到站S0073的最少轉(zhuǎn)乘次數(shù)為 路線有1條；起始站S0087到終到站S3676的最少轉(zhuǎn)乘次數(shù)為 下的最優(yōu)路線有1條；起始站S0148到終到站S0485的最少轉(zhuǎn)乘次數(shù)為 路線有10條

38、；起始站S0971到終到站S0485的最少轉(zhuǎn)乘次數(shù)為 路線有20條（注表6.4中羅列其中10條）；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為 路線有17條（注表6.4中羅列其中10條）；起始站S3359到終到站S1828的最少轉(zhuǎn)乘次數(shù)為 路線有2條2）以耗時最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828耗時最少為64 min,耗時最少的最優(yōu)路線（轉(zhuǎn) 乘次數(shù)較少，費用較省的路線）有 28條（注：表6.1選擇了其中的10條表示）；起始站S1557到終到站S0481耗時最少為109 min,耗時最少的最優(yōu)路線有 17條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0971到終到站S0485耗

39、時最少為96 min，耗時最少的最優(yōu)路線有 20條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0008到終到站S0073耗時最少為55 min,耗時最少的最優(yōu)路線有3 條;起始站S0148到終到站S0485耗時最少為87.5 min，耗時最少的最優(yōu)路線 有10條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0087到終到站S3676耗時最少為33 min,耗時最少的最優(yōu)路線有1 條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；3）最少費用的最優(yōu)路線起始站S3359到終到站S1828的最少費用為3元，最少費用的最優(yōu)路線（所 需時間較短，轉(zhuǎn)乘次數(shù)較少的路線）有2條；起始站S1557到終到站S0481的最少費用為3元，最少費用的

40、最優(yōu)路線有17條；起始站S0971到終到站S0485的最少費用為5元，最少費用的最優(yōu)路線有 20條；起始站S0008到終到站S0073的最少費用為2元，最少費用的最優(yōu)路線有1 條；起始站S0148到終到站S0485的最少費用為5元，最少費用的最優(yōu)路線有 10條；起始站S0087到終到站S3676的最少費用為2元，最少費用的最優(yōu)路線有1 條；在此種情況下，我們就只考慮可以通過地鐵站換乘的情況， 不通過地鐵站的 情況即為模型1的求解結(jié)果。模型2的求解結(jié)果見附件1。6. 3. 1模型三的建立該模型針對問題三，將步行方式考慮在了出行方式當(dāng)中，更符合實際。因 為當(dāng)出發(fā)點與換乘點、終點站或轉(zhuǎn)乘站與轉(zhuǎn)乘站之

41、間只相隔幾個站時，當(dāng)然該段選擇步行方式更優(yōu)。因此作出如下假設(shè)：一、如果存在某段路線，其兩端點站之間相隔站點數(shù)小等于2（即至多經(jīng)過4個站點），貝U該段線路選擇步行方式到達(dá)目的地。其他的情況用模型二來處理。 其中路線的兩端點站之間相隔站點數(shù)是根據(jù)公交直達(dá)換乘路線來確定的。二、相鄰公交站點（包括地鐵站）間平均步行時間為5分鐘。三、如果在公汽線路上選擇步行，則公汽間換乘次數(shù)減少1;如果在地鐵線路上選擇步行，則地鐵間換乘次數(shù)減少 1,直達(dá)線路除外。直達(dá)和轉(zhuǎn)乘一次、兩次的路線需要步行的路段示意圖如圖 6.5所示。圖中（a） 表示出發(fā)點A與終點站B間能直達(dá)，相隔的站點數(shù)等于2所以選擇步行；圖中（b） 表示出

42、發(fā)點A與終點站B間通過一次換乘能到達(dá)，其中路段 AC的站點數(shù)等于2 所以選擇步行，同樣如果CB路段的站點數(shù)小等于2,則也采取步行的方式；圖中 （c）選擇步行方式的依據(jù)類似。Lt 步行I0）T1圖6.5步行示意圖是否選擇步行方式的函數(shù)：1 MSk ,m 豈4Sk,m二0 其他FD k, n1 M D匸0 其他（6.8 式）其中FSk,m表示第m路公交路線是否步行，F(xiàn)D k,n表示第n路地鐵線路是否步行;對于直達(dá)路線，如果出發(fā)點與終點站之間相隔站點數(shù)小等于2則步行，否 則乘車。對于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時間最短的路線作為最優(yōu)路線的模型：路線總時間等于乘車時間加上步行 時間，再

43、加上轉(zhuǎn)乘時間。Min Tk=3<L(1FSk,Z(MS k-1)+25 吃(1_FD )k(MD_1)mn5 ' FSk,m (MSk,m -1) 5 ' FDk,n (MDk,n -1)(6.9 式)mn+5x(N1k -送 FSk,m )+4x(N2k -送 FDk,n )+7xN3k+6xN4kmn，(3 2F£,m) (MSk,m 一 1) ' (2.5 2.5FDk,n ) (MDk,n -1)mn5 (N1k-、FS5) 4 (N2' FDk,n) 7 N3k 6 N4mn其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2

44、）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：每步行一次就少換乘一次車。Min N1送 FSN,m 2 FD 譏 N3 + N4（6.20 式）mn此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次、三次（包括公交與地鐵間 的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：M i n C八（-1 kFS ）C kg 3 N4（6.21 式）m其中，CLk,m仍滿足（6.4式）。七模型的優(yōu)缺點及改進(jìn)7.1模型的評價模型優(yōu)點1、模型是由簡單到復(fù)雜一步步建立的，使得更貼近實際。2、本文的模型簡單，其算法直觀，容易編程實現(xiàn)。3、本文模型比較注重數(shù)據(jù)的處理和存儲方式，大大提高了查詢效率。4、本文

45、模型注重效率的提高，通過大量的特征信息的提取，并結(jié)合有效的算法， 使其完全可以滿足實時系統(tǒng)的要求。模型缺點在建模與編程過程中，使用的數(shù)據(jù)只是現(xiàn)實數(shù)據(jù)的一種近似，因而得出的結(jié) 果可能與現(xiàn)實情況有一定的差距。7.2模型的改進(jìn)以上模型主要是從公交線路出發(fā)，尋找公交線路的交叉站作為換乘站點， 進(jìn) 而找出經(jīng)過任意兩個站點的可能乘車路線。我們也可以從公交站點的角度出發(fā)， 用圖論的方法建立有向賦權(quán)圖（如圖 7.1所示），此向賦權(quán)圖是針對問題三建立的圖論模型，問題一、問題二只是此模型的簡化。圖7.1中Li表示公汽線路標(biāo)號，該線路是公汽線路Li的上行線或下行線，S、ggg、Sj、Sj、Sj d ggg、Sn 是

46、公汽線路Li上的站點標(biāo)號；Tk表示地鐵線路標(biāo)號，該地鐵線路是雙向行駛的，D1、ggg Dg、Dg 1、ggg、Dm是地鐵線路Tj上的站點標(biāo)號；公汽L與地鐵Tk可 以在公汽站Sj和地鐵站Dg間換乘。如果圖7.1中的地鐵線路替換成公汽線路， 為了表示公汽間換乘所需的時間或者費用， 應(yīng)將同一個換乘站點用兩個站點來表 示。圖7.1公交線路的有向賦權(quán)圖根據(jù)不同的目標(biāo)，給不同的站點間的邊賦上不同的權(quán)值。然后利用圖論的相 關(guān)算法,找出相應(yīng)的最短路徑。1）當(dāng)以時間最短為目標(biāo)時，給每條邊賦上時間的權(quán)值。給同一線路上任意 兩個站點間的邊賦值時，其權(quán)值等于站點間的公交線路段數(shù)與平均時間的乘積。 當(dāng)某段線路的兩段點間

47、間隔站點數(shù)小等于3時，選擇步行，該線路的權(quán)值等于步行時間。不同公汽和地鐵間進(jìn)行換乘時需要賦給不同的權(quán)值，以表示換乘時間。例如（如圖7.1）：當(dāng)j>4時，S到Sj的邊權(quán)值S,Sj =（j-1） 3 ；，從Sj4到Sj不需要的轉(zhuǎn)車，但根據(jù)假設(shè)應(yīng)選擇步行，其邊權(quán)值Sj_,Sj =5 ；，從Sj4到Dj要么乘公交，然后轉(zhuǎn)車，要么步行，根據(jù)步行的假設(shè)條件，S#至U Dj的站點間隔數(shù)小于2,因此選擇步行，其邊權(quán)值 SjDg =5 ；，當(dāng) g>4 時，Di 與Dg 之間的邊權(quán)值 Di,Dg 二 Dg,Di =(g-1) 2.5 ;,Sj到Dg的邊權(quán)值S,D g =6 ;Dg到Sj的邊權(quán)值DgS

48、j =7 ;當(dāng)j>4、g>4時，Si到Di的路徑長度為：(S，Di),Si，Sj+Sj,Dg+Dg,Di> =(3 + 6+(g-1)x25;當(dāng)j乞4、g>4時，則從Si到Dg選擇步行，再乘地鐵到Di，其路徑長度為；(Si,Di) = Si,DgDg,Di =(j -i) 5 (g-i) 2.5 ；找出任意兩點間可行路線的路徑長度后，再搜索出其中的最短路徑的的可行 路線作為時間的最優(yōu)路線。2)當(dāng)以費用最省為目標(biāo)時，則給每條邊賦上費用的權(quán)值。 公汽站點間的邊權(quán)按(6.4式)賦值。當(dāng)公汽線路Li按單一票價計費，對于Li上任意兩個公汽站點Sj和S°間，OO若 j -

49、j 4，則選擇步行 S,S °=0 ;若 j -j i 4，則 SjS ° =i ；oo當(dāng)公汽線路Li按分段計價，若j - j 4，則Sj, S ° =0 ;若3< j -j <20，oo則 SjS j =i ;若 20 ： j j乞 4 0,貝 U SjS ± =2 ;若 j -j 4 0 ,貝U S”S . =3 ;o地鐵線路Tk上任意兩個站點Dg和D±間，若j - j 14，則選擇步行ODg,D± 二 D±,Dg =0;若 j d 1 4，則 Dg,D±= D±,Dg =3;換乘站點 S

50、j與Dg間的邊權(quán)值均為0, 即卩Dg,Sj二Sj,Dg =0 ;則從Si通過站點Sj換乘Dg到Di的一條可行路線的路徑長度為：若 j4，g 4，則從 Si 到 Sj 選擇步行，(Si,Di)= Dg,D3 二;若 j >4，g>4，貝U (Si,Di)=(S,Sj)D gi,D >=3 + 3 = 6 ;同樣可以找出任意兩點間可行路線的路徑長度，然后再搜索出最短路徑作為 費用的最優(yōu)路線。以上從公交站點出發(fā)，將公交站點作為網(wǎng)絡(luò)圖中頂點，得出公交的拓?fù)浣Y(jié)構(gòu)， 進(jìn)而尋求不同目標(biāo)下的最短路徑， 為我們提供了另外一種思路。但是從以上圖形 的結(jié)構(gòu)，我們已經(jīng)看得出其復(fù)雜程度是不可預(yù)知的，尤

51、其隨著數(shù)據(jù)的增多，圖的復(fù)雜度隨之上升。如果不尋求一個好的算法，而用常規(guī)的Dijkstra算法，將有可 能在可以忍受的時間范圍內(nèi)得不出有效結(jié)果。經(jīng)過參考相關(guān)資料，我們發(fā)現(xiàn)用螞蟻算法可能比較有效。該算法利用了螞蟻尋食出行路徑選擇的行為特點，通過線路激素強(qiáng)度的更新機(jī)制，實現(xiàn)了以換乘次 數(shù)最少和公交出行站點最少的公交出行路徑選擇優(yōu)化目標(biāo)。八參考文獻(xiàn)1 344000溫小文 臧德彥，城市公交信息查詢系統(tǒng)設(shè)計初探，江西測繪，第65期,20062 龔劬 圖論與網(wǎng)絡(luò)最優(yōu)化算法 重慶大學(xué)出版社，20003 1671-4512(2003)SI-0313 張帥 彭玉青 趙鎮(zhèn) 李志強(qiáng)，螞蟻算法在公交查 詢最短路徑求法中的應(yīng)用，華中科技大學(xué)學(xué)報(自然科學(xué)報)，第 31卷，2003九附件轉(zhuǎn)乘0次的情況起始站占八、線路站點站點線路站點站點線