2007-乘公交看奧運

2007高教社杯全國大學(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è)置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?重 慶 大 學(xué) 參賽隊員 (打印并簽名) ：1. 熊國剛 2. 王杰 3. 黎明 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 龔劬 日期： 2007年 9 月 21 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：乘公交，看奧運【摘要】本文要解決的問題是以即將舉行的08年北京奧運會為背景而提出的。人們?yōu)榱四墁F(xiàn)場觀看奧運會，必然會面對出行方式與路線選擇的問題。因此如何快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關(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ā)站終點站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗時（min）641061066710646最少轉(zhuǎn)乘次數(shù)（次）121122最少費用（元）333233模型二是根據(jù)問題二（同時考慮公汽和地鐵系統(tǒng)）建立的，同樣用VC+編程得到所求站點間的最優(yōu)路線，如下表所示：出發(fā)站終點站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗時（min）64106965587.533最少轉(zhuǎn)乘次數(shù)（次）121120最少費用（元）333233對問題三（將步行考慮在內(nèi)）我們建立了模型三的優(yōu)化模型，然后在模型改進(jìn)里又建立了圖論模型。本文的主要特點在于，所用算法的效率十分顯著。在對原始數(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條以上，使得公眾的出行更加通暢、便利。但同時也面臨多條線路的選擇問題。為滿足公眾查詢公交線路的選擇問題，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。這個系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對起始站到終到站最佳路線。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。二 符號說明：第i條公汽線路標(biāo)號,i=1,2 10400,當(dāng)時, 表示上行公汽路線, 當(dāng)時, 表示與上行路線相對應(yīng)的下行公汽路線；：經(jīng)過第i條公汽路線的第g個公汽站點標(biāo)號；：第j條地鐵路線標(biāo)號, j=1,2；：經(jīng)過第j條地鐵線路的第h個地鐵站點標(biāo)號；：轉(zhuǎn)乘n次的路線；：選擇第k種路線的總時間；：選擇第k種路線公汽換乘公汽的換乘次數(shù)；：選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；：選擇第k種路線地鐵換乘公汽的換乘次數(shù)；：選擇第k種路線公汽換乘地鐵的換乘次數(shù)；：第k種路線、乘坐第m輛公汽的計費方式，其中：表示實行單一票價，表示實行分段計價；：第k種路線，乘坐第m輛公汽的費用； ：選擇第k種路線的總費用；：選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公汽站個點數(shù)；：選擇第k種路線，乘坐第n路地鐵需要經(jīng)過的地鐵站個點數(shù)； ：表示對于第k種路線的第m路公汽的路線是否選擇步行，為0-1變量，表示不選擇步行，表示選擇步行；：對于第k種路線的第n路地鐵的路線是否選擇步行，為0-1變量，表示不選擇步行，表示選擇步行；三 模型假設(shè)3.1基本假設(shè)1、相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘2、相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘3、公汽換乘公汽平均耗時：5分鐘(其中步行時間2分鐘)4、地鐵換乘地鐵平均耗時：4分鐘(其中步行時間2分鐘)5、地鐵換乘公汽平均耗時：7分鐘(其中步行時間4分鐘)6、公汽換乘地鐵平均耗時：6分鐘(其中步行時間4分鐘)7、公汽票價：分為單一票價與分段計價兩種；單一票價：1元其中分段計價的票價為：0 20站：1元2140站：2元40站以上：3元8、地鐵票價：3元（無論地鐵線路間是否換乘）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á)公交線路，也有可能是兩條公交線路通過交匯而形成的（此時需要轉(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ù)最少為好。不同的路線查詢需求用圖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)備工作。51數(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 1921 1920 3439 3440 2482 2211 2377 2159 1478 0359 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所示），則可以等效為兩條線路:順時針方向：S1S2S3S4S1S2S3S4；逆時針方向：S1S4S3S2S1S4S3S2。經(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 1215 1217 251 2604 2606 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606L673: 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649在這里，L153被看作成上行路線，L673被當(dāng)成下行路線。這樣對于每條公交線路都可以得到兩行線路存儲信息。52搜尋經(jīng)過每個站點的公交路線處理5.1所得信息，找出通過每個站點的所有公交路線，并將它們存入數(shù)據(jù)文件中。例如，通過搜尋得出經(jīng)過站點S0001的線路和經(jīng)過站點S0002的線路如下：經(jīng)過S0001的線路有：L421經(jīng)過S0002的線路有：L027 L152 L365 L395 L48553統(tǒng)計任意兩條公交線路的相交（相近）站點依次統(tǒng)計出任意兩條公交線路之間相交(相近)的站點，將其存入10401040的矩陣A中，但是這個矩陣的元素是維數(shù)不確定的向量，具體實現(xiàn)的時候可以將用隊列表示。例如：公交線路L001與公交線路L025相交的站點為A125=S0619，S1914，S0388，S0348。六 模型的建立與求解61模型一的建立 該模型針對問題一，僅考慮公汽線路，先找出經(jīng)過任意兩個公汽站點與最多轉(zhuǎn)乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。611 公汽路線的數(shù)學(xué)表示任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分別對應(yīng)圖6.1的四種情況。該圖中的A、B為出發(fā)站和終點站，C、D、E、F為轉(zhuǎn)乘站點。圖6.1 公汽路線圖對于任意兩個公汽站點與，經(jīng)過的公汽線路表示為，有；經(jīng)過的公汽線路表示為，有；1）直達(dá)的路線（如圖6.1（a）所示）表示為：2）轉(zhuǎn)乘一次的路線（如圖6.1（b）所示）表示為：其中：SC為，的一個交點；3）轉(zhuǎn)乘兩次的路線（如圖6.1（c）所示）表示為： 通過以上轉(zhuǎn)乘路線的建模過程，可以看出不同轉(zhuǎn)乘次數(shù)間可作成迭代關(guān)系，進(jìn)而對更多轉(zhuǎn)乘次數(shù)的路線進(jìn)行求尋。不過考慮到實際情況，轉(zhuǎn)乘次數(shù)以不超過2次為佳，所以本文未對轉(zhuǎn)乘三次及三次以上的情形做討論。612最優(yōu)路線模型的建立 找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進(jìn)行選擇，找出最優(yōu)路線了:1）以時間最短作為最優(yōu)路線的模型：行程時間等于乘車時間與轉(zhuǎn)車時間之和。 （6.1式）其中，第k路線是以上轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少作為最優(yōu)路線的模型： （6.2式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次的優(yōu)先次序來考慮。3）以費用最少作為最優(yōu)路線的模型： （6.3式）其中， （6.4式）613模型的算法描述針對該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個站點間的可行路線，然后搜索出最優(yōu)路線?，F(xiàn)將此算法運用到該問題中，結(jié)合圖6.2敘述如下：（該圖中的、表示公汽站點，、表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點到點直達(dá)、轉(zhuǎn)乘一次、轉(zhuǎn)乘兩次的情況）圖6.2 公交直達(dá)、轉(zhuǎn)乘圖（1）首先輸入需要查詢的兩個站點與（假設(shè)為起始站，為終點站）；（2）搜索出經(jīng)過的公汽線路（i=1,2,m）和經(jīng)過的公汽線路(=1,2, ，n)，存入數(shù)據(jù)文件；判斷是與是否存在相同路線，若有則站點與之間有直達(dá)路線(如圖6.2中的)，則該路線是換乘次數(shù)最少(換乘次數(shù)等于0)的路線，若有多條直達(dá)路線，則可以在此基礎(chǔ)上找出時間最省的路線；這樣可以找出所有直達(dá)路線，存入數(shù)據(jù)文件；（3）找出經(jīng)過的公汽線路(如圖6.2中的)中的另一站點和經(jīng)過的公汽線路中的另一站點。判斷與中是否存在相同的點，若存在(如圖6.2中的)則站點與間有一次換乘的路線(如圖6.2中的與)，該相同點即為換乘站點；這樣又找出了一次換乘路線，存入數(shù)據(jù)文件；（4）再搜索出經(jīng)過(如圖6.2中的)線路上除了站點的另一站點(如圖6.2中的)的公汽線路(如圖6.2中的)，找出公汽線路上的其他站點；判斷，如果與經(jīng)過的公汽線路中的其他站點存在相同的點(如圖6.2中的)，則與間有二次換乘的路線(如圖6.2中的、)，該相同點和點是換乘站點；將此二次換乘的路線存入數(shù)據(jù)文件中；（5）對上述存儲的經(jīng)過兩個站點與的不同路線，根據(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到終到站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)站公汽線路中轉(zhuǎn)站公汽線路終到站轉(zhuǎn)乘次數(shù)所需費用S3359L0535S2903L1005S1784L0687S182823S3359L0535S2903L1005S1784L0737S182823S3359L0123S2903L1005S1784L0687S182823S3359L0123S2903L1005S1784L0737S182823S3359L0652S2903L1005S1784L0687S182823S3359L0652S2903L1005S1784L0737S182823S3359L0844S2027L1005S1784L0687S182823S3359L0844S2027L1005S1784L0737S182823S3359L0844S1746L1005S1784L0687S182823S3359L0844S1746L1005S1784L0737S182823S1557L0604S1919L0709S3186L0980S048123S1557L0883S1919L0709S3186L0980S048123S0971L0533S2517L0810S2480L0937S048523S0971L0533S2517L0296S2480L0937S048523S0008L0198S3766L0296S2184L0345S007323S0008L0198S3766L0296S2184L0345S007323S0148L0308S0036L0156S2210L0937S048523S0148L0308S0036L0156S3332L0937S048523S0148L0308S0036L0156S3351L0937S048523S0087L0541S0088L0231S0427L0097S367623S0087L0541S0088L0231S0427L0982S367623S0087L0541S0088L0901S0427L0097S367623S0087L0541S0088L0901S0427L0982S367623S0087L0206S0088L0231S0427L0097S367623S0087L0206S0088L0231S0427L0982S367623S0087L0206S0088L0901S0427L0097S367623S0087L0206S0088L0901S0427L0982S367623S0087L0974S0088L0231S0427L0097S367623S0087L0974S0088L0231S0427L0982S367623S0087L0974S0088L0901S0427L0097S367623S0087L0974S0088L0901S0427L0982S3676232） 以轉(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)路線有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)路線路線如表6.2所示。表6.2 轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線表起始站公汽線路中轉(zhuǎn)站公汽線路終到站耗時所需費用S3359L0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679S0491L0578S0073832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S0073832S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0073832S0008L0983S2083L0057S00738323）以費用最少為目標(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到終到站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中。 621模型二的建立 該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然后尋找最優(yōu)路線。對于地鐵線路，也可以將其作為公交線路，本質(zhì)上沒有什么區(qū)別，只不過乘車費用、時間，換乘時間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公交的轉(zhuǎn)乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中的基本相同。現(xiàn)建立模型二下的最優(yōu)路線模型。1）以時間最短的路線作為最優(yōu)路線的模型：可行路線的總時間為乘公交（公汽和地鐵）時間與公汽與地鐵換乘、公汽間、地鐵間換乘時間之和。 （6.5式）其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型： （6.6式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次（包括公交與地鐵間的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：可行路線的費用為乘公交和地鐵費用的總和。 （6.7式）其中，仍滿足（6.4式）。622模型二的求解 不難發(fā)現(xiàn)，問題一是問題二解的一部分。在問題二中，新產(chǎn)生的最優(yōu)解主要源于在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示： 從點A到B，圖(a)表示的是通過兩公交線路上相鄰公汽站S1,S2進(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所示）相吻合。圖6.4 北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個站點間的可行線路，再將目標(biāo)函數(shù)分別用模型二建立的模型表達(dá)式表達(dá)，用VC+進(jìn)行編程（程序見附錄）求得出考慮地鐵情況的最優(yōu)路線。1）以轉(zhuǎn)乘次數(shù)最少為目標(biāo)的最優(yōu)路線起始站S0008到終到站S0073的最少轉(zhuǎn)乘次數(shù)為1次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有1條；起始站S0087到終到站S3676的最少轉(zhuǎn)乘次數(shù)為0次，即有直達(dá)路線，直達(dá)下的最優(yōu)路線有1條；起始站S0148到終到站S0485的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有10條；起始站S0971到終到站S0485的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有20條（注表6.4中羅列其中10條）；起始站S1557到終到站S0481的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有17條（注表6.4中羅列其中10條）；起始站S3359到終到站S1828的最少轉(zhuǎn)乘次數(shù)為2次，轉(zhuǎn)乘次數(shù)最少的最優(yōu)路線有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耗時最少為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元，最少費用的最優(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。631模型三的建立 該模型針對問題三，將步行方式考慮在了出行方式當(dāng)中，更符合實際。因為當(dāng)出發(fā)點與換乘點、終點站或轉(zhuǎn)乘站與轉(zhuǎn)乘站之間只相隔幾個站時，當(dāng)然該段選擇步行方式更優(yōu)。因此作出如下假設(shè)：一、如果存在某段路線，其兩端點站之間相隔站點數(shù)小等于（即至多經(jīng)過4個站點），則該段線路選擇步行方式到達(dá)目的地。其他的情況用模型二來處理。其中路線的兩端點站之間相隔站點數(shù)是根據(jù)公交直達(dá)換乘路線來確定的。二、相鄰公交站點（包括地鐵站）間平均步行時間為5分鐘。三、如果在公汽線路上選擇步行，則公汽間換乘次數(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ù)小等于，則也采取步行的方式；圖中（c）選擇步行方式的依據(jù)類似。圖6.5 步行示意圖是否選擇步行方式的函數(shù)： （6.8式）其中表示第m路公交路線是否步行，表示第n路地鐵線路是否步行； 對于直達(dá)路線，如果出發(fā)點與終點站之間相隔站點數(shù)小等于則步行，否則乘車。對于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時間最短的路線作為最優(yōu)路線的模型：路線總時間等于乘車時間加上步行時間，再加上轉(zhuǎn)乘時間。 （6.9式）其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：每步行一次就少換乘一次車。 （6.20式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次、三次（包括公交與地鐵間的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型： （6.21式）其中，仍滿足（6.4式）。七 模型的優(yōu)缺點及改進(jìn)7.1模型的評價7.1.1 模型優(yōu)點1、模型是由簡單到復(fù)雜一步步建立的，使得更貼近實際。2、本文的模型簡單，其算法直觀，容易編程實現(xiàn)。3、本文模型比較注重數(shù)據(jù)的處理和存儲方式，大大提高了查詢效率。4、本文模型注重效率的提高，通過大量的特征信息的提取，并結(jié)合有效的算法，使其完全可以滿足實時系統(tǒng)的要求。7.1.2 模型缺點在建模與編程過程中，使用的數(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中表示公汽線路標(biāo)號，該線路是公汽線路的上行線或下行線，、是公汽線路上的站點標(biāo)號；表示地鐵線路標(biāo)號，該地鐵線路是雙向行駛的，、是地鐵線路上的站點標(biāo)號；公汽與地鐵可以在公汽站和地鐵站間換乘。如果圖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)某段線路的兩段點間間隔站點數(shù)小等于3時，選擇步行，該線路的權(quán)值等于步行時間。不同公汽和地鐵間進(jìn)行換乘時需要賦給不同的權(quán)值，以表示換乘時間。例如（如圖7.1）：當(dāng)j4時，到 的邊權(quán)值；， 從到 不需要的轉(zhuǎn)車，但根據(jù)假設(shè)應(yīng)選擇步行，其邊權(quán)值；，從到 要么乘公交，然后轉(zhuǎn)車，要么步行，根據(jù)步行的假設(shè)條件，到 的站點間隔數(shù)小于2，因此選擇步行，其邊權(quán)值；，當(dāng)g4時，與之間的邊權(quán)值；，到的邊權(quán)值；到的邊權(quán)值；當(dāng)j4、g4時，到的路徑長度為：；當(dāng)、g4時，則從到選擇步行，再乘地鐵到，其路徑長度為；找出任意兩點間可行路線的路徑長度后，再搜索出其中的最短路徑的的可行路線作為時間的最優(yōu)路線。2）當(dāng)以費用最省為目標(biāo)時，則給每條邊賦上費用的權(quán)值。公汽站點間的邊權(quán)按（6.4式）賦值。當(dāng)公汽線路按單一票價計費，對于上任意兩個公汽站點和間，若，則選擇步行；若，則；當(dāng)公汽線路按分段計價，若，則；若，則；若，則；若，則；地鐵線路上任意兩個站點和間，若，則選擇步行；若，則；換乘站點與間的邊權(quán)值均為0，即；則從通過站點換乘到的一條可行路線的路徑長度為：若，則從到選擇步行，；若，則；同樣可以找出任意兩點間可行路線的路徑長度，然后再搜索出最短路徑作為費用的最優(yōu)路線。 以上從公交站點出發(fā)，將公交站點作為網(wǎng)絡(luò)圖中頂點，得出公交的拓?fù)浣Y(jié)構(gòu)，進(jìn)而尋求不同目標(biāo)下的最短路徑，為我們提供了另外一種思路。但是從以上圖形的結(jié)構(gòu)，我們已經(jīng)看得出其復(fù)雜程度是不可預(yù)知的，尤其隨著數(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)Sl-0313 張帥 彭玉青 趙鎮(zhèn) 李志強(qiáng)，螞蟻算法在公交查詢最短路徑求法中的應(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ù)S0087454S0541S0540462S36764421轉(zhuǎn)乘2次的情況起始站點：S0008 目標(biāo)站點：S0073起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0008L150S3874D30T2D25S0525L103S00735552S0008L159S3874D30T2D25S0525L103S00735552S0008L259S3874D30T2D25S0525L103S00735552S0008L200S2534D15T1D12S0609L57S007365.552S0008L159S0400S2633L474S0527S0525L103S00736732起始站點：S0087 目標(biāo)站點：S3676 起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0087L21S0087D27T2D36S3676L97S36763330S0087L28S0608D12T2D36S3676L97S367633.552S0087L28S0608D12T2D36S3676L209S367633.552S0087L28S0608D12T2D36S3676L209S367633.552S0087L28S0608D12T2D36S3676L462S367633.552S0087L28S0608D12T2D36S3676L462S367633.552S0087L28S0608D12T2D36S3676L506S367633.552起始站點：S0148 目標(biāo)站點：S0485 起始站點線路站點站點線路站點站點線路站點耗時/min車費/元轉(zhuǎn)乘次數(shù)S0148L24S1487D2T1D21S0466L51S048587.552S0148L24S1487D2T1D21S0464L104S048587.552S0148L24S1487D2T1D21S0464L395S048587.552S0148L24S1487D2T1D21S0466L450S048587.552S0148L24S1487D2T1D21S0464L469S048587.552S0148L24S1487D2T1D21S0466L51S048587.552S0148L24S1487D2T1D21S0464L104S048587.552S0148L24S1487D2T1D21