乘公交看奧運(yùn)

1、承諾書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則 我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵 件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn) 題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的，如果引用別人的成果或其他 公開(kāi)的資料（包括網(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)填寫(xiě)）：B我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整

2、的全名）：重慶大學(xué)參賽隊(duì)員（打印并簽名）：1.熊國(guó)剛2. 王杰3. 黎明指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：龔劬日期：2007年9月21日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：編號(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)【摘要】本文要解決的問(wèn)題是以即將舉行的 08年北京奧運(yùn)會(huì)為背景而提出的。 人們?yōu)榱四墁F(xiàn)場(chǎng)觀看奧運(yùn)會(huì)，必然會(huì)面對(duì)出行方式與路線選擇的問(wèn)題。 因此如何 快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問(wèn)題的

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

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

5、法的效率十分顯著。在對(duì)原始數(shù)據(jù)僅做簡(jiǎn)單預(yù) 處理的條件下，搜索任意站點(diǎn)間的最優(yōu)路線所需的平均時(shí)間不超過(guò) 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)問(wè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í)也面臨多條線路的選擇問(wèn)題。 為滿足公眾查詢公交線路的選擇問(wèn)題，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選 擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。這個(gè)系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實(shí)際情況出發(fā)考 慮，滿足查詢者的各種不同需求。需要解決的問(wèn)題有：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與 算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對(duì)起始站到終到站最佳路線。、S3359 S1828 (2) 、S155L S0481 (3)、S0971 S0485、S0008S0073 (5) 、S014IS0485 (6)、S0087S36762、同時(shí)考慮公汽與地鐵線路，解

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

8、k:選擇第k種路線公汽換乘地鐵的換乘次數(shù)；Wk,m :第k種路線、乘坐第m輛公汽的計(jì)費(fèi)方式，其中:Wkm =1表示實(shí)行單一票價(jià)，Wk,m =2表示實(shí)行分段計(jì)價(jià)；CL k, m :第k種路線，乘坐第m輛公汽的費(fèi)用；Ck :選擇第k種路線的總費(fèi)用；MSk,m :選擇第k種路線，乘坐第m輛公汽需要經(jīng)過(guò)的公汽站個(gè)點(diǎn)數(shù)；MD k,n:選擇第k種路線，乘坐第n路地鐵需要經(jīng)過(guò)的地鐵站個(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表示選擇步行；FD k,n :對(duì)于第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、相鄰公汽站平均行駛時(shí)間2、相鄰地鐵站平均行駛時(shí)間3、公汽換乘公汽平均耗時(shí)：4、地鐵換乘地鐵平均耗時(shí)：5、地鐵換乘公汽平均耗時(shí)： &公汽換乘地鐵平均耗時(shí)：（包括停站時(shí)間）:3分鐘 （包括停站時(shí)間）:2.5分鐘 5分鐘（其中步行時(shí)間 4分鐘（其中步行時(shí)間 7分鐘（其中步行時(shí)間 6分鐘（其中步行時(shí)間2分鐘）2分鐘）4分鐘）4分鐘）7、公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種; 單一票價(jià)：1元其中分段計(jì)價(jià)的票價(jià)為:020站：1元2140站：2元40站以上：3元8、地鐵票價(jià)：3元（無(wú)論地鐵

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

11、線路通過(guò)交匯而形成的（此時(shí)需要轉(zhuǎn)乘公交一次），甚至更多公交線路交匯而成。然后在這些可行路線中搜尋最優(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ù)最少

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

13、 1數(shù)據(jù)的存儲(chǔ)由于所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲(chǔ) 格式。從所給文件中讀出線路上的站點(diǎn)信息，存入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: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為L(zhǎng)009所對(duì)應(yīng)的下行線路。如果下行線是上行線原路返回，那么存儲(chǔ)的兩行數(shù)據(jù)中的站點(diǎn)信息剛好順序 顛倒，以公交線路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、等效為兩條線路：順時(shí)針?lè)较颍篠1SP S3 S1 S2 SI S4; 逆時(shí)針?lè)较颍篠1S4 S3 S2 S1 S4 S3 S2。經(jīng)過(guò)分析，此兩條”單行路線”線路的作用等同于原環(huán)形路線圖5.1環(huán)行線路示意圖以環(huán)形公交線L158為例，此環(huán)形路線存儲(chǔ)數(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)成下行路線。這樣對(duì)于每條公交 線路都可以得到兩行線路存儲(chǔ)信息。5. 2搜尋經(jīng)過(guò)每個(gè)站點(diǎn)的公交路線處理5.1所得信息，找出通過(guò)每個(gè)站點(diǎn)的所有公交路線，并將它們存入數(shù)據(jù) 文件中。例如，通過(guò)搜尋得出經(jīng)過(guò)站點(diǎn) S0

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

18、最多轉(zhuǎn)乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。6. 1. 1公汽路線的數(shù)學(xué)表示任意兩個(gè)站點(diǎn)間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分 別對(duì)應(yīng)圖6.1的四種情況。該圖中的 A B為出發(fā)站和終點(diǎn)站，C、D E、F為轉(zhuǎn) 乘站點(diǎn)。圖6.1公汽路線圖對(duì)于任意兩個(gè)公汽站點(diǎn)Si,g與S o,g，經(jīng)過(guò)Si,g的公汽線路表示為L(zhǎng)i，有-Lo ；Si,gLi;經(jīng)過(guò)So,g的公汽線路表示為L(zhǎng)o，有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為L(zhǎng)i1，Li2的一個(gè)交點(diǎn);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通過(guò)以上轉(zhuǎn)乘路線的建模過(guò)程，可以看出不同轉(zhuǎn)乘次數(shù)間可作成迭代關(guān)系， 進(jìn)而對(duì)更多轉(zhuǎn)乘次數(shù)的路線進(jìn)行求尋。 不過(guò)考慮到實(shí)際情況，轉(zhuǎn)乘次數(shù)以不超過(guò) 2次為佳，所以本文未對(duì)轉(zhuǎn)乘三次及三次以上的情形做討論。6. 1. 2最優(yōu)

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

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

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

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

25、到站S0485耗時(shí)最少為106 min,耗時(shí)最少的最優(yōu)路線有2條; 起始站S0008到終到站S0073耗時(shí)最少為67 min,耗時(shí)最少的最優(yōu)路線有2 條;起始站S0148到終到站S0485耗時(shí)最少為106 min,耗時(shí)最少的最優(yōu)路線有3條; 起始站S0087到終到站S3676耗時(shí)最少為46 min,耗時(shí)最少的最優(yōu)路線有12條; 其耗時(shí)最少的最優(yōu)路線如表6.1所示。表6.1耗時(shí)最少的最優(yōu)路線表起始 站公汽線 路就站公汽線 路就站公汽線 路終到 站轉(zhuǎn)乘 次數(shù)所需 費(fèi)用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) 路線（所需時(shí)間較短

30、，費(fèi)用較省的路線）有 2條；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有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)路線相同；其余轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線路線如表

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

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

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

34、該模型針對(duì)問(wèn)題二，將公汽與地鐵同時(shí)考慮，找出可行路線，然后尋找最優(yōu) 路線。對(duì)于地鐵線路，也可以將其作為公交線路，本質(zhì)上沒(méi)有什么區(qū)別，只不過(guò) 乘車費(fèi)用、時(shí)間，換乘時(shí)間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公 交的轉(zhuǎn)乘站即可作為兩者的交匯點(diǎn)。因此該模型的公交換乘路線模型與模型一中 的基本相同。現(xiàn)建立模型二下的最優(yōu)路線模型。1）以時(shí)間最短的路線作為最優(yōu)路線的模型：可行路線的總時(shí)間為乘公交（公汽 和地鐵）時(shí)間與公汽與地鐵換乘、公汽間、地鐵間換乘時(shí)間之和。Min T3=（MSk,mT）2 5江 （MD 1）5 XN1mn（6.5 式）4 N27N36 N4k其中，第k路線為同時(shí)考慮公汽與地鐵的轉(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)先次序來(lái)考慮。3）以費(fèi)用最少的路線作為最優(yōu)路線的模型：可行路線的費(fèi)用為乘公交和地鐵費(fèi) 用的總和。Min Ck» eg3N k4（ 6.7 式）m其中，CLk,m仍滿足（6.4式）。6. 2. 2模型二的求解不難發(fā)現(xiàn)，問(wèn)題一是問(wèn)題二解的一部分。在問(wèn)題二中，新產(chǎn)生的最優(yōu)解主 要源于在通過(guò)換乘地鐵、換乘附近相近站點(diǎn)的路線上，如下圖所示：從點(diǎn)A到B,圖（a）表示的是通過(guò)兩公交線路上相鄰公汽站S1,S

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

37、椿%用MZKIJU兒 *#琳W WW圖6.4北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個(gè)站點(diǎn)間的可行線路，再將目標(biāo)函數(shù)分別用模型二建立的模型表達(dá)式表達(dá)，用VC+進(jìn)行編程（程序見(jià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）以耗時(shí)最少為目標(biāo)的最優(yōu)路線起始站S3359到終到站S1828耗時(shí)最少為64 min,耗時(shí)最少的最優(yōu)路線（轉(zhuǎn) 乘次數(shù)較少，費(fèi)用較省的路線）有 28條（注：表6.1選擇了其中的10條表示）；起始站S1557到終到站S0481耗時(shí)最少為109 min,耗時(shí)最少的最優(yōu)路線有 17條與轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線相同；起始站S0971到終到站S0485耗

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

40、最優(yōu)路線有17條；起始站S0971到終到站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到終到站S3676的最少費(fèi)用為2元，最少費(fèi)用的最優(yōu)路線有1 條；在此種情況下，我們就只考慮可以通過(guò)地鐵站換乘的情況， 不通過(guò)地鐵站的 情況即為模型1的求解結(jié)果。模型2的求解結(jié)果見(jiàn)附件1。6. 3. 1模型三的建立該模型針對(duì)問(wèn)題三，將步行方式考慮在了出行方式當(dāng)中，更符合實(shí)際。因 為當(dāng)出發(fā)點(diǎn)與換乘點(diǎn)、終點(diǎn)站或轉(zhuǎn)乘站與轉(zhuǎn)乘站之

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

42、發(fā)點(diǎn)A與終點(diǎn)站B間通過(guò)一次換乘能到達(dá)，其中路段 AC的站點(diǎn)數(shù)等于2 所以選擇步行，同樣如果CB路段的站點(diǎn)數(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路地鐵線路是否步行;對(duì)于直達(dá)路線，如果出發(fā)點(diǎn)與終點(diǎn)站之間相隔站點(diǎn)數(shù)小等于2則步行，否 則乘車。對(duì)于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時(shí)間最短的路線作為最優(yōu)路線的模型：路線總時(shí)間等于乘車時(shí)間加上步行 時(shí)間，再

43、加上轉(zhuǎn)乘時(shí)間。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路線為同時(shí)考慮公汽與地鐵的轉(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)先次序來(lái)考慮。3）以費(fèi)用最少的路線作為最優(yōu)路線的模型：M i n C八（-1 kFS ）C kg 3 N4（6.21 式）m其中，CLk,m仍滿足（6.4式）。七模型的優(yōu)缺點(diǎn)及改進(jìn)7.1模型的評(píng)價(jià)模型優(yōu)點(diǎn)1、模型是由簡(jiǎn)單到復(fù)雜一步步建立的，使得更貼近實(shí)際。2、本文的模型簡(jiǎn)單，其算法直觀，容易編程實(shí)現(xiàn)。3、本文模型比較注重?cái)?shù)據(jù)的處理和存儲(chǔ)方式，大大提高了查詢效率。4、本文

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

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

47、間隔站點(diǎn)數(shù)小等于3時(shí)，選擇步行，該線路的權(quán)值等于步行時(shí)間。不同公汽和地鐵間進(jìn)行換乘時(shí)需要賦給不同的權(quán)值，以表示換乘時(shí)間。例如（如圖7.1）：當(dāng)j>4時(shí)，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的站點(diǎn)間隔數(shù)小于2,因此選擇步行，其邊權(quán)值 SjDg =5 ；，當(dāng) g>4 時(shí)，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時(shí)，Si到Di的路徑長(zhǎng)度為：(S，Di),Si，Sj+Sj,Dg+Dg,Di> =(3 + 6+(g-1)x25;當(dāng)j乞4、g>4時(shí)，則從Si到Dg選擇步行，再乘地鐵到Di，其路徑長(zhǎng)度為；(Si,Di) = Si,DgDg,Di =(j -i) 5 (g-i) 2.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)公汽線路Li按單一票價(jià)計(jì)費(fèi)，對(duì)于Li上任意兩個(gè)公汽站點(diǎn)Sj和S°間，OO若 j -

49、j 4，則選擇步行 S,S °=0 ;若 j -j i 4，則 SjS ° =i ；oo當(dāng)公汽線路Li按分段計(jì)價(jià)，若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上任意兩個(gè)站點(diǎn)Dg和D±間，若j - j 14，則選擇步行ODg,D± 二 D±,Dg =0;若 j d 1 4，則 Dg,D±= D±,Dg =3;換乘站點(diǎn) S

50、j與Dg間的邊權(quán)值均為0, 即卩Dg,Sj二Sj,Dg =0 ;則從Si通過(guò)站點(diǎn)Sj換乘Dg到Di的一條可行路線的路徑長(zhǎng)度為：若 j4，g 4，則從 Si 到 Sj 選擇步行，(Si,Di)= Dg,D3 二;若 j >4，g>4，貝U (Si,Di)=(S,Sj)D gi,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ù)雜程度是不可預(yù)知的，尤

51、其隨著數(shù)據(jù)的增多，圖的復(fù)雜度隨之上升。如果不尋求一個(gè)好的算法，而用常規(guī)的Dijkstra算法，將有可 能在可以忍受的時(shí)間范圍內(nèi)得不出有效結(jié)果。經(jīng)過(guò)參考相關(guān)資料，我們發(fā)現(xiàn)用螞蟻算法可能比較有效。該算法利用了螞蟻尋食出行路徑選擇的行為特點(diǎn)，通過(guò)線路激素強(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)SI-0313 張帥 彭玉青 趙鎮(zhèn) 李志強(qiáng)，螞蟻算法在公交查 詢最短路徑求法中的應(yīng)用，華中科技大學(xué)學(xué)報(bào)(自然科學(xué)報(bào))，第 31卷，2003九附件轉(zhuǎn)乘0次的情況起始站占八、線路站點(diǎn)站點(diǎn)線路站點(diǎn)站點(diǎn)線