乘公交看奧運數(shù)學(xué)建模

1、乘公交看奧運高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細(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è)置報名號

2、的話）：所屬學(xué)校（請?zhí)顚懲暾娜褐貞c大學(xué)參賽隊員（打印并簽名）：1.2.3.指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：日期：年月日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：乘公交看奧運高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：乘公交看奧運乘公交，看奧運【摘要】本文要解決的問題是以即將舉行的08年北京奧運會為背景而提出的。人們?yōu)榱四墁F(xiàn)場觀看奧運會，必然會面對出行方式與路線選擇的問題。因此如何快速、高效地從眾多可

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

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

5、十分顯著。在對原始數(shù)據(jù)僅做簡單預(yù)處理的條件下，搜索任意站點間的最優(yōu)路線所需的平均時間不超過0.5秒。另外,本文所建立的模型簡單、所用算法比較清晰，易于程序?qū)崿F(xiàn)，對公交線路自主查詢計算機系統(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)備，首都的公交車大都煥然一新，增強了交通的安全性和舒適性，公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利。但

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

7、所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。二符號說明Li:第i條公汽線路標(biāo)號,i=1,210400，當(dāng)iM520時，L表示上行公汽路線，當(dāng)i520時，L表示與上行路線L-20相對應(yīng)的下行公汽路線；Si,g：經(jīng)過第i條公汽路線的第g個公汽站點標(biāo)號；Tj:第j條地鐵路線標(biāo)號，j=1,2;Dj,h：經(jīng)過第j條地鐵線路的第h個地鐵站點標(biāo)號；LSn:轉(zhuǎn)乘n次的路線；Tk:選擇第k種路線的總時間；N1k：選擇第k種路線公汽換乘公汽的換乘次數(shù)；N2k：選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；N3選擇第k種路線地鐵換乘公汽的換乘次數(shù)；N4k：選擇第k種路線公汽換乘地鐵的換乘次數(shù)；Wk

8、,m：第k種路線、乘坐第m輛公汽的計費方式，其中:乘公交看奧運Wk,m=1表示實行單一票價，Wk,m=2表示實行分段計價；CLk,m：第k種路線，乘坐第m輛公汽的費用；Ck:選擇第k種路線的總費用；MSk,m：選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公汽站個點數(shù)；MDk,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表示選擇步行；FDk,n:對于第k種路線的第n路地鐵的路線是否選擇步行，F(xiàn)Dk,n為0-1變量,FDk,n=0表示不選擇步行，F(xiàn)Dk,n=1

9、表示選擇步行；三模型假設(shè)3.1 基本假設(shè)1、相鄰公汽站平均行駛時間（包括停站時間）:3分鐘2、相鄰地鐵站平均行駛時間（包括停站時間）:2.5分鐘3、公汽換乘公汽平均耗時4、地鐵換乘地鐵平均耗時5、地鐵換乘公汽平均耗時6、公汽換乘地鐵平均耗時7、公汽票價：分為單一票價與分段計價兩種單一票價：1元5分鐘（其中步行時間2分鐘）4分鐘（其中步行時間2分鐘）7分鐘（其中步行時間4分鐘）6分鐘（其中步行時間4分鐘）其中分段計價的票價為：020站：1元2140站：2元40站以上：3元8、地鐵票價：3元（無論地鐵線路間是否換乘）9、假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵費3.

10、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á)公交線路，也有可能是兩條公交線路通過交匯而形成的（此時需要轉(zhuǎn)乘公交一次），甚至更多公交線路交匯而成。然后在這些可行路線中搜

11、尋最優(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ù)最少為好。不同的路線查詢需求用圖4.1表示如下：圖4.1公交線路查詢目標(biāo)圖經(jīng)分析，本問題的解決歸結(jié)為一個求最短

12、路徑的問題，但是傳統(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.1數(shù)據(jù)的存儲由于所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲格式。從所給文件中讀出線路上的站點信息，存入

13、txt文檔中，其存儲格式為：兩行數(shù)據(jù)，第一行表示上行線上的站點信息，第二行表示下行線的站點信息，其中下行路線標(biāo)號需要在原標(biāo)號的基礎(chǔ)上加上520,用以區(qū)分上行線和下行線。如果上行線與下行線的站點名不完全相同，那么存儲的兩行數(shù)據(jù)相應(yīng)的不完全相同，以公交線L009為例：L009:373903591477215923772211248224803439192019210180202030272981L529:2981302720200180192119203439344024822211237721591478乘公交看奧運03593739L529為L009所對應(yīng)的下行線路。如果下行線是上行線原路返回，

14、那么存儲的兩行數(shù)據(jù)中的站點信息剛好順序顛倒，以公交線路L001為例：L001:061919140388034803920429043638853612081935240820391401280710L521:071001283914082035240819361238850436042903920348038819140619如果是環(huán)線的情況（如圖5,1所示），則可以等效為兩條線路：順時針方向：S1S2S3-SAS1-S2一SAS4;逆時針方向：SWS4S3-S2-SWS4-S3-S2o經(jīng)過分析，此兩條“單行路線”線路的作用等同于原環(huán)形路線圖5,1環(huán)行線路示意圖以環(huán)形公交線L158為例，此環(huán)形

15、路線存儲數(shù)據(jù)如下：L153:534649235512128121711708112600172158581426435131215121725126042606534649235512128121711708112600172158581426435131215121725126042606L673:534260626042511217121535132648141585172260081117017181212122355649534260626042511217121535132648141585172260081117017181212122355649在這里，L153被看作成上行路線，

16、L673被當(dāng)成下行路線。這樣對于每條公交線路都可以得到兩行線路存儲信息。5.2搜尋經(jīng)過每個站點的公交路線處理5,1所得信息，找出通過每個站點的所有公交路線，并將它們存入數(shù)據(jù)文件中。例如，通過搜尋得出經(jīng)過站點S0001的線路和經(jīng)過站點S0002的線路如下：經(jīng)過S0001的線路有：L421經(jīng)過S0002的線路有：L027L152L365L395L4855.3統(tǒng)計任意兩條公交線路的相交（相近）站點依次統(tǒng)計出任意兩條公交線路之間相交（相近）的站點，將其存入1040X1040的矩陣A中，但是這個矩陣的元素是維數(shù)不確定的向量，具體實現(xiàn)的時候可以將用隊列表示。例如：公交線路L001與公交線路L025相交的站

17、點為A125=S0619,S1914,S0388,S0348。乘公交看奧運六模型的建立與求解6.1模型一的建立該模型針對問題一，僅考慮公汽線路，先找出經(jīng)過任意兩個公汽站點Si,g與So&最多轉(zhuǎn)乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。i,g6.1.1公汽路線的數(shù)學(xué)表示任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分別對應(yīng)圖6.1的四種情況。該圖中的A、B為出發(fā)站和終點站，C、DE、F為轉(zhuǎn)乘站點。圖6.1公汽路線圖對于任意兩個公汽站點Sig與Soo,經(jīng)過Sig的公汽線路表示為Li,有1,g1g,gSi,gwLi;經(jīng)過Soo的公汽線路表示為Lo,有SoowLo;

18、7g丫，gi1)直達(dá)的路線LSo(如圖6.1(a)所示)表示為：L=Li1Si,g0月工2)轉(zhuǎn)乘一次的路線LS(如圖6.1(b)所示)表示為：LS=(Li1,Li2)S,gWLi1,SqjLi2；Li1,Li2更LSo；SLLi1且SCWLi?其中：SC為Li1,Li2的一個交點；3)轉(zhuǎn)乘兩次的路線LS2(如圖6.1(c)所小)表小為：LS2=(Li1,Li2,Li3)Si,g匚Ln,Si&匚Li2；(Li1,Li3),(Li3,Li2)(乏LS1；Li1,Li2尸LG),g通過以上轉(zhuǎn)乘路線的建模過程，可以看出不同轉(zhuǎn)乘次數(shù)間可作成迭代關(guān)系，進而對更多轉(zhuǎn)乘次數(shù)的路線進行求尋。不過考慮到實際情況，

19、轉(zhuǎn)乘次數(shù)以不超過2次為佳，所以本文未對轉(zhuǎn)乘三次及三次以上的情形做討論。6.1.2最優(yōu)路線模型的建立找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進行8乘公交看奧運選擇，找出最優(yōu)路線了1）以時間最短作為最優(yōu)路線的模型：行程時間Tk等于乘車時間與轉(zhuǎn)車時間之和n口+iMinTk=3父（MSk,mi）+5xN1km1m1=,2,gggN1k+1;k=1,2,gggk其中，第k路線是以上轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少作為最優(yōu)路線的模型：（6.1式）MinN1（6.2式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次的優(yōu)先次序來考慮3）以費用最少作為最優(yōu)路線的模型:MinCkL

20、m（6.3式）1其中，CLk,m=23Wk,m=1或Wk,m=2,0MSk,m20Wk,m=2Wk,m=221MSk,m4040MSk,m（6.4式）6.1.3模型的算法描述針對該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個站點間的可行路線，然后搜索出最優(yōu)路線?，F(xiàn)將此算法運用到該問題中，結(jié)合圖6.2敘述如下:（該圖中的Si,g、Sqg、S1/、S2,1S2,2表小公汽站點，L1、L2、L3、L4、L5、L6表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點Sig到點Si&直,gi,g達(dá)、轉(zhuǎn)乘一次、轉(zhuǎn)乘兩次的情況）圖6.2公交直達(dá)、轉(zhuǎn)乘圖（1）首先輸入需要查詢的兩個站點Si,g與Sqo

21、（假設(shè)Si,g為起始站，Sqo7g7g為終點站）；（2）搜索出經(jīng)過Sig的公汽線路Li（i=1,2，,m）和經(jīng)過Sqq的公汽線路,gq,gQq（q=1,2，n）,存入數(shù)據(jù)文件；判斷是Li與L,是否存在相同路線，若乘公交看奧運有則站點Si,g與Sqo之間有直達(dá)路線（如圖6.2中的LJ,則該路線是換乘次數(shù)1,g最少（換乘次數(shù)等于0）的路線，若有多條直達(dá)路線，則可以在此基礎(chǔ)上找出時間最省的路線；這樣可以找出所有直達(dá)路線，存入數(shù)據(jù)文件；（3）找出經(jīng)過Si,g的公汽線路Li（如圖6.2中的L2）中的另一站點Sii,gi和經(jīng)過Sqq的公汽線路q.o中的另一站點SqdqO判斷Sii,gi與Sqi對中是否存在

22、相q,gq1,gq1,g1同的點，若存在（如圖6.2中的Si,i）則站點Si,g與Sqg間有一次換乘的路線（如圖6.2中的L2與L3）,該相同點即為換乘站點；這樣又找出了一次換乘路線，存入數(shù)據(jù)文件；（4）再搜索出經(jīng)過Lj（如圖6.2中的LJ線路上除了站點Sjg的另一站點,Si2,g1（如圖6.2中的S2,i）的公汽線路Li6（如圖6.2中的L6）,找出公汽線路Li6上的其他站點Si2,g2；判斷，如果Si2,g2與經(jīng)過Sqq的公汽線路電q中的其他站點,gSq2q2存在相同的點（如圖6.2中的S2,2）,則Si,g與Sqq間有二次換乘的路線,g,g（如圖6.2中的L4、L6、L5）,該相同點和點

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

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

25、310乘公交看奧運S3359L0123S2903L1005S1784L0687S182823S3359L0123S2903L1005S1784L0737S182823S3359L0652S2903L1005S1784L0687S182823S3359L0652S2903L1005S1784L0737S182823S3359L0844S2027L1005S1784L0687S182823S3359L0844S2027L1005S1784L0737S182823S3359L0844S1746L1005S1784L0687S182823S3359L0844S1746L1005S1784L0737S1

26、82823S1557L0604S1919L0709S3186L0980S048123S1557L0883S1919L0709S3186L0980S048123S0971L0533S2517L0810S2480L0937S048523S0971L0533S2517L0296S2480L0937S04852t3S0008L0198S3766L0296S2184L0345S007323S0008L0198S3766L0296S2184L0345S007323S0148L0308S0036L0156S2210L0937S048523S0148L0308S0036L0156S3332L0937S0485

27、23S0148L0308S0036L0156S3351L0937S048523S0087L0541S0088L0231S0427L0097S367623S0087L0541S0088L0231S0427L0982S367623S0087L0541S0088L0901S0427L0097S367623S0087L0541S0088L0901S0427L0982S36762r3S0087L0206S0088L0231S0427L0097S367623S0087L0206S0088L0231S0427L0982S367623S0087L0206S0088L0901S0427L0097S367623S

28、0087L0206S0088L0901S0427L0982S367623S0087L0974S0088L0231S0427L0097S367623S0087L0974S0088L0231S0427L0982S367623S0087L0974S0088L0901S0427L0097S36762I3S0087L0974S0088L0901S0427L0982S3676232）以轉(zhuǎn)乘次數(shù)最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828的最少轉(zhuǎn)乘次數(shù)為1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線（所需時間較短，費用較省的路線）有2條；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線

29、有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)路線相同；11乘公交看奧運其余轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線路線如表6,2所示表6.2轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線表起始站公汽線路中轉(zhuǎn)站公汽線路終到站耗時所需費用S3359L

30、0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S00738312S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0

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

32、n,轉(zhuǎn)乘次數(shù)為1起始站S0008到終到站S0073的最少費用為2元，最少費用的最優(yōu)路線有9條，所需時間為83min,轉(zhuǎn)乘次數(shù)為1次；起始站S0148到終到站S0485的最少費用為3元，最少費用的最優(yōu)路線有3條，所需時間為106min,轉(zhuǎn)乘次數(shù)為2起始站S0087至IJ終至IJ站S3676的最少費用為3元，最少費用的最優(yōu)路線有12條，所需時間為46min,轉(zhuǎn)乘次數(shù)為2次；最少費用的最優(yōu)路線表示在表6,1和表6.2中。6. 2.1模型二的建立該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然后尋找最優(yōu)路線。對于地鐵線路，也可以將其作為公交線路，本質(zhì)上沒有什么區(qū)別，只不過乘車費用、時間，換乘時

33、間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公交的轉(zhuǎn)乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中的基本相同?，F(xiàn)建立模型二下的最優(yōu)路線模型。1）以時間最短的路線作為最優(yōu)路線的模型：可行路線的總時間為乘公交（公汽和地鐵）時間與公汽與地鐵換乘、公汽問、地鐵間換乘時間之和。MinT3=父（MSk,訴1）2.5父（MD仁1）5kxN1mn（6.5式）4N27N36N4k其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：12乘公交看奧運MinN1N2Nk3Nk4（6.6式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次（包括公交與

34、地鐵間的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：可行路線的費用為乘公交和地鐵費用的總和。MinCk=CLmx3N4（6.7式）m其中，CLk,m仍滿足（6.4式）。6.2.2模型二的求解不難發(fā)現(xiàn)，問題一是問題二解的一部分。在問題二中，新產(chǎn)生的最優(yōu)解主要源于在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示：從點A到B,圖（a）表示的是通過兩公交線路上相鄰公汽站S1,S2進行一次轉(zhuǎn)乘；圖（b）表小利用地鐵站進行二次轉(zhuǎn)乘；圖（c）表小利用另一條公汽路線為中介進行二次轉(zhuǎn)乘。鐵路線路引入給題目的求解增加了難度，為了形象了解為數(shù)不多的兩條鐵路間的交叉關(guān)系，我們通過matlab編

35、程（程序見附錄）作出了兩條鐵路的位置關(guān)系圖，如圖6.3所示。圖6.3T1與T2鐵路位置關(guān)系圖注：圖四中的直線表示T1鐵路線，圓表示T2鐵路線，數(shù)值表示站點，例如1表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網(wǎng)上查詢到的北京地鐵示意圖（如圖6.4所示）相吻合。13乘公交看奧運機越安南1*京地線示意凰sin圖6.4北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個站點間的可行線路，再將目標(biāo)函數(shù)分別用模型二建立的模型表達(dá)式表達(dá)，用VC+赳行編程（程序見附錄）求得出考慮地鐵情況的最優(yōu)路線。1）以轉(zhuǎn)乘次數(shù)最少為目標(biāo)的最優(yōu)路線1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)0次，即有直達(dá)路線，直達(dá)

36、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條；起始站S0971至IJ終至IJ站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至I終

37、至I站S1828耗時最少為64min,耗時最少的最優(yōu)路線（轉(zhuǎn)乘次數(shù)較少，費用較省的路線）有28條（注：表6.1選擇了其中的10條表示）；起始站S1557到終到站S0481耗時最少為109min,耗時最少的最優(yōu)路線有17條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0971到終到站S0485耗時最少為96min,耗時最少的最優(yōu)路線有20條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0008到終到站S0073耗時最少為55min,耗時最少的最優(yōu)路線有3起始站S0148至I終至I站S0485耗時最少為87.5min,耗時最少的最優(yōu)路線有10條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0087到終到站S3676耗時最

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

39、費用為2元，最少費用的最優(yōu)路線有1在此種情況下，我們就只考慮可以通過地鐵站換乘的情況，不通過地鐵站的情況即為模型1的求解結(jié)果。模型2的求解結(jié)果見附件1。6.3.1模型三的建立該模型針對問題三，將步行方式考慮在了出行方式當(dāng)中，更符合實際。因為當(dāng)出發(fā)點與換乘點、終點站或轉(zhuǎn)乘站與轉(zhuǎn)乘站之間只相隔幾個站時，當(dāng)然該段選擇步行方式更優(yōu)。因此作出如下假設(shè)：一、如果存在某段路線，其兩端點站之間相隔站點數(shù)小等于2（即至多經(jīng)過4個站點），則該段線路選擇步行方式到達(dá)目的地。其他的情況用模型二來處理。其中路線的兩端點站之間相隔站點數(shù)是根據(jù)公交直達(dá)換乘路線來確定的。二、相鄰公交站點（包括地鐵站）問平均步行時間為5分鐘。

40、三、如果在公汽線路上選擇步行，則公汽間換乘次數(shù)減少1;如果在地鐵線路上選擇步行，則地鐵間換乘次數(shù)減少1,直達(dá)線路除外。直達(dá)和轉(zhuǎn)乘一次、兩次的路線需要步行的路段示意圖如圖6,5所示。圖中（a）表示出發(fā)點A與終點站B間能直達(dá)，相隔的站點數(shù)等于2所以選擇步行；圖中（b）表示出發(fā)點A與終點站B間通過一次換乘能到達(dá)，其中路段AC的站點數(shù)等于2所以選才步行，同樣如果CB路段的站點數(shù)小等于2,則也采取步行的方式；圖中（c）選擇步行方式的依據(jù)類似。圖6,5步行示意圖是否選擇步行方式的函數(shù):FSk,m1MSk,m三40其他MD市4其他（6.8式）其中FSk,m表示第m路公交路線是否步行，F(xiàn)D5表示第n路地鐵線路

41、是否步行;15乘公交看奧運對于直達(dá)路線，如果出發(fā)點與終點站之間相隔站點數(shù)小等于2則步行，否則乘車。對于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時間最短的路線作為最優(yōu)路線的模型：路線總時間等于乘車時間加上步行時間，再加上轉(zhuǎn)乘時間。Min丁卜=3匯(1_FS”*(MS1)+25M(1-FD)以朋-1)kmn(6.9式)5%FSk,m(MSk,m-1)5%FDk,n(MDk,n-1)mn5(N1kFSk,m)4(N2k-xFDk,n)7N3k6N4kmn=(32F0,m)(MSk,m-1)八(2.52.5FDk,n)(MDk,n-1)mn5(N1k，F(xiàn)Sk,m)4(N2k，F(xiàn)Dk,n)7N3k6

42、N4kmn其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：每步行一次就少換乘一次車。MinN1k-ZFSk,+N2ZFD+kN3+N4k（6.20式）mn此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次、三次（包括公交與地鐵問的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：MinQ1kFmS4時，&到Sj的邊權(quán)值0,Sj）=（j仍3;,從旬到Sj不需要的轉(zhuǎn)車，但根據(jù)假設(shè)應(yīng)選擇步行，其邊權(quán)值（Sj,Sj）=5；,從Sj到Dj要么乘公交，然后轉(zhuǎn)車，要么步行，根據(jù)步行的假設(shè)條件，Sj至ljDj的站點間隔數(shù)小于2,因此選擇步行，其

43、邊權(quán)值SjDg）=5;,17乘公交看奧運當(dāng)g4時，Di與Dg之間的邊權(quán)值(D1,Dg=4、g4時，6到Di的路徑長度為：(,Di)=Si，SjSj,DgDg,Di=(j-1)36(g-1)2.5;當(dāng)jM4、g4時，則從Si到Dg選擇步行，再乘地鐵到Di,其路徑長度為；(Si,Di)=Si,Dg)+=(j-1)x5+(g-1)x2.5;找出任意兩點間可行路線的路徑長度后，再搜索出其中的最短路徑的的可行路線作為時間的最優(yōu)路線。2)當(dāng)以費用最省為目標(biāo)時，則給每條邊賦上費用的權(quán)值。公汽站點間的邊權(quán)按(6.4式)賦值。當(dāng)公汽線路L按單一票價計費，對于Li上任意兩個公汽站點Sj和Sj問，若j-j+1=0;

44、若j-j+14,WHSjSj)=1;當(dāng)公汽線路Li按分段計價，若j-j+1=0;若3j-j20,貝卜Sj,Sj)=1;若20j-j40,貝卜,SjSj)=3;地鐵線路Tk上任意兩個站點Dg和Dg間，若j-j+1宅4,則選擇步行Dg,D古=4,則4,則從Si到Sj選擇步行，(S,Di)=4,g4,則(Si,Di)=(S,Sj”g%D=3+3=6;同樣可以找出任意兩點間可行路線的路徑長度，然后再搜索出最短路徑作為費用的最優(yōu)路線。以上從公交站點出發(fā)，將公交站點作為網(wǎng)絡(luò)圖中頂點，得出公交的拓?fù)浣Y(jié)構(gòu)，進而尋求不同目標(biāo)下的最短路徑，為我們提供了另外一種思路。但是從以上圖形的結(jié)構(gòu)，我們已經(jīng)看得出其復(fù)雜程度是

45、不可預(yù)知的，尤其隨著數(shù)據(jù)的增多，圖的復(fù)雜度隨之上升。如果不尋求一個好的算法，而用常規(guī)的Dijkstra算法，將有可18乘公交看奧運能在可以忍受的時間范圍內(nèi)得不出有效結(jié)果。經(jīng)過參考相關(guān)資料，我們發(fā)現(xiàn)用螞蟻算法可能比較有效。該算法利用了螞蟻尋食出行路徑選擇的行為特點，通過線路激素強度的更新機制，實現(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)Sl-0313張帥彭玉青趙鎮(zhèn)李志強，螞蟻算法在公交查詢最短

46、路徑求法中的應(yīng)用，華中科技大學(xué)學(xué)報(自然科學(xué)報)，第31卷，2003九附件轉(zhuǎn)乘0次的情況起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0087L21S0087D27T2D36S3676L97S36763330轉(zhuǎn)乘1次的情況起始站點：S0008轉(zhuǎn)乘站點:S0073起始站點路線站點站點路線目標(biāo)站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0008129S0400S2633474S00738021S0008129S0854S0856474S00738321起始站點：S0087轉(zhuǎn)乘站點:S3676起始站點路線站點站點路線目標(biāo)站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0087454S0541S054

47、0462S36764421轉(zhuǎn)乘2次的情況起始站點：S0008目標(biāo)站點：S0073起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0008L150S3874D30T2D25S0525L103S00735552S0008L159S3874D30T2D25S0525L103S00735552S0008L259S3874D30T2D25S0525L103S00735552S0008L200S2534D15T1D12S0609L57S007365.552S0008L159S0400S2633L474S0527S0525L103S00736732起始站點：S0087目標(biāo)站點：S3676起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S008