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

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

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

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

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

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

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

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

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

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

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

11、尋最優(yōu)路線。對(duì)于路線的評(píng)價(jià)，我們可以分別以總行程時(shí)間，總轉(zhuǎn)乘次數(shù)，總費(fèi)用為指標(biāo)，也可以將三種指標(biāo)標(biāo)準(zhǔn)化后賦以不同權(quán)值形成一個(gè)綜合指標(biāo)。而最優(yōu)路線則應(yīng)是總行程時(shí)間最短，總費(fèi)用最少或總轉(zhuǎn)乘次數(shù)最少，或者三者皆有之。之所以這樣考慮目標(biāo)，是因?yàn)閷?duì)于不同年齡階段的查詢者，他們追求的目標(biāo)會(huì)有所不同，比如青年人比較熱衷于比賽，因而他們會(huì)選擇最短時(shí)間內(nèi)到達(dá)奧運(yùn)賽場(chǎng)觀看比賽。而中年人則可能較傾向于綜合指標(biāo)最小，即較快、較省，轉(zhuǎn)乘次數(shù)又不多。老年人總愿意以最省的方式看到奧運(yùn)比賽。而對(duì)于殘疾人士則總轉(zhuǎn)乘次數(shù)最少為好。不同的路線查詢需求用圖4.1表示如下：圖4.1公交線路查詢目標(biāo)圖經(jīng)分析，本問題的解決歸結(jié)為一個(gè)求最短

12、路徑的問題，但是傳統(tǒng)的Dijkstra最短路徑算法并不適用于本問題，因?yàn)镈ijkstra算法采用的存儲(chǔ)結(jié)構(gòu)和計(jì)算方法難以應(yīng)付公交線路網(wǎng)絡(luò)拓?fù)涞膹?fù)雜性，而且由于執(zhí)行效率的問題，具很難滿足實(shí)時(shí)系統(tǒng)對(duì)時(shí)間的嚴(yán)格要求。為此我們?cè)趯?shí)際求解的過程中，采用了效率高效得廣度優(yōu)先算法，其基本思路是每次搜索指定點(diǎn)，并將其所有未訪問過的近鄰點(diǎn)加入搜索隊(duì)列，循環(huán)搜索過程直到隊(duì)列為空。此方法在后文中有詳細(xì)說明。五建模前的準(zhǔn)備為了后面建模與程序設(shè)計(jì)的方便，在建立此模型前，我們有必要做一些準(zhǔn)備工作。5.1數(shù)據(jù)的存儲(chǔ)由于所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲(chǔ)格式。從所給文件中讀出線路上的站點(diǎn)信息，存入

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

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

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

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

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

19、轉(zhuǎn)乘次數(shù)以不超過2次為佳，所以本文未對(duì)轉(zhuǎn)乘三次及三次以上的情形做討論。6.1.2最優(yōu)路線模型的建立找出了任意兩個(gè)公汽站點(diǎn)間的可行路線，就可以對(duì)這些路線按不同需求進(jìn)行8乘公交看奧運(yùn)選擇，找出最優(yōu)路線了1）以時(shí)間最短作為最優(yōu)路線的模型：行程時(shí)間Tk等于乘車時(shí)間與轉(zhuǎn)車時(shí)間之和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)先次序來(lái)考慮3）以費(fèi)用最少作為最優(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模型的算法描述針對(duì)該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個(gè)站點(diǎn)間的可行路線，然后搜索出最優(yōu)路線?，F(xiàn)將此算法運(yùn)用到該問題中，結(jié)合圖6.2敘述如下:（該圖中的Si,g、Sqg、S1/、S2,1S2,2表小公汽站點(diǎn)，L1、L2、L3、L4、L5、L6表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點(diǎn)Sig到點(diǎn)Si&直,gi,g達(dá)、轉(zhuǎn)乘一次、轉(zhuǎn)乘兩次的情況）圖6.2公交直達(dá)、轉(zhuǎn)乘圖（1）首先輸入需要查詢的兩個(gè)站點(diǎn)Si,g與Sqo

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

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

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

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

25、310乘公交看奧運(yùn)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)路線（所需時(shí)間較短，費(fèi)用較省的路線）有2條；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線

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

30、0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S00738312S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0

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

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

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

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

35、程（程序見附錄）作出了兩條鐵路的位置關(guān)系圖，如圖6.3所示。圖6.3T1與T2鐵路位置關(guān)系圖注：圖四中的直線表示T1鐵路線，圓表示T2鐵路線，數(shù)值表示站點(diǎn)，例如1表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網(wǎng)上查詢到的北京地鐵示意圖（如圖6.4所示）相吻合。13乘公交看奧運(yùn)機(jī)越安南1*京地線示意凰sin圖6.4北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個(gè)站點(diǎn)間的可行線路，再將目標(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）以耗時(shí)最少為目標(biāo)的最優(yōu)路線起始站S3359至I終

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

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

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

40、三、如果在公汽線路上選擇步行，則公汽間換乘次數(shù)減少1;如果在地鐵線路上選擇步行，則地鐵間換乘次數(shù)減少1,直達(dá)線路除外。直達(dá)和轉(zhuǎn)乘一次、兩次的路線需要步行的路段示意圖如圖6,5所示。圖中（a）表示出發(fā)點(diǎn)A與終點(diǎn)站B間能直達(dá)，相隔的站點(diǎn)數(shù)等于2所以選擇步行；圖中（b）表示出發(fā)點(diǎn)A與終點(diǎn)站B間通過一次換乘能到達(dá)，其中路段AC的站點(diǎn)數(shù)等于2所以選才步行，同樣如果CB路段的站點(diǎn)數(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乘公交看奧運(yùn)對(duì)于直達(dá)路線，如果出發(fā)點(diǎn)與終點(diǎn)站之間相隔站點(diǎn)數(shù)小等于2則步行，否則乘車。對(duì)于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時(shí)間最短的路線作為最優(yōu)路線的模型：路線總時(shí)間等于乘車時(shí)間加上步行時(shí)間，再加上轉(zhuǎn)乘時(shí)間。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路線為同時(shí)考慮公汽與地鐵的轉(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)先次序來(lái)考慮。3）以費(fèi)用最少的路線作為最優(yōu)路線的模型：MinQ1kFmS4時(shí)，&到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的站點(diǎn)間隔數(shù)小于2,因此選擇步行，其

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

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

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

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

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