乘公交看奧運(yùn)

1、公交查詢系統(tǒng)最佳乘車(chē)方案研究與設(shè)計(jì)摘要本文主要利用改進(jìn)的鄰接算法解決多需求下公交線路的選擇問(wèn)題。本題建立模型求解后主要實(shí)現(xiàn)如下功能：用戶發(fā)出請(qǐng)求，系統(tǒng)優(yōu)先為用戶提供直達(dá)的公交線路，若無(wú)直達(dá)線路，分別為用戶提供轉(zhuǎn)乘次數(shù)最少、耗時(shí)最短、費(fèi)用最低三種線路作為備選線路，同時(shí)，在相同換乘次數(shù)內(nèi)，按照乘車(chē)時(shí)間由少到多為用戶提供多條相對(duì)較優(yōu)的乘車(chē)路線，并給出相應(yīng)的乘車(chē)費(fèi)用作為參考，由用戶自主選擇滿足其需求的乘車(chē)路線。問(wèn)題一，依題意在數(shù)據(jù)處理階段將不同公交汽線路抽象化，建立站點(diǎn)間直達(dá)線路信息存儲(chǔ)結(jié)構(gòu)元胞，基于直達(dá)線路數(shù)據(jù)庫(kù)構(gòu)造站點(diǎn)間以直達(dá)線路數(shù)目為元素的鄰接矩陣，在鄰接矩陣構(gòu)成的數(shù)據(jù)結(jié)構(gòu)之上，考慮公汽線路不同

2、票價(jià)、線路等條件，采用改進(jìn)的鄰接算法分別以轉(zhuǎn)乘次數(shù)最少、耗時(shí)最短、費(fèi)用最低為目標(biāo)進(jìn)行全局最佳路線的求解。問(wèn)題二，在問(wèn)題一的基礎(chǔ)上考慮公汽與地鐵混排，將地鐵站點(diǎn)與周?chē)墓军c(diǎn)集抽象為同一新站點(diǎn)，把以上公汽線路站點(diǎn)映射為新站點(diǎn)，建立新的直達(dá)數(shù)據(jù)庫(kù)，結(jié)合地鐵費(fèi)用、地鐵與公汽間的換乘時(shí)間以及兩者站間行駛時(shí)間等條件，將地鐵與公汽結(jié)合的問(wèn)題轉(zhuǎn)化為問(wèn)題一，采用改進(jìn)的鄰接算法得到不同目標(biāo)下的多種優(yōu)化方案。問(wèn)題三，根據(jù)問(wèn)題一與問(wèn)題二基于換乘次數(shù)最少逐步分析目標(biāo)選定最佳路線的模型，在知道所有站點(diǎn)之間的步行時(shí)間的基礎(chǔ)上，建立以步行代替短距離減少換乘次數(shù)和以步行鄰邊化減少出行用時(shí)的優(yōu)化數(shù)學(xué)模型，采用廣度優(yōu)先算法,改

3、進(jìn)公交線路的路線選擇方案。本文中公交出行以達(dá)到用時(shí)短、費(fèi)用低、換乘少等目標(biāo)而涉及的公交線路安排問(wèn)題可以歸結(jié)為不同權(quán)值含義下的最短路問(wèn)題，作為運(yùn)籌學(xué)與圖論中的經(jīng)典優(yōu)化問(wèn)題，本文所建立的數(shù)學(xué)模型與求解方法具有較強(qiáng)的現(xiàn)實(shí)意義。關(guān)鍵字： 直達(dá)數(shù)據(jù)庫(kù) 鄰接算法 步行鄰邊化 廣度優(yōu)先算法一、問(wèn)題重述第29屆奧運(yùn)會(huì)明年8月將在北京舉行，作為城市樞紐的公共交通承擔(dān)著非常重的運(yùn)輸任務(wù)。近年來(lái)，北京市的公交系統(tǒng)有很大的發(fā)展，公交線路的條數(shù)和公交車(chē)數(shù)量在迅速增多，給人民生活帶來(lái)便利的同時(shí)，也面臨多條線路得選擇問(wèn)題，有時(shí)出行往往還需要轉(zhuǎn)乘多輛公交車(chē)才能到達(dá)目的地。如何在短時(shí)間、換乘次數(shù)最少、成本最低的情況到達(dá)目的地，

4、是人們所關(guān)注的問(wèn)題。因此，我們通過(guò)建立線路選擇的模型與算法，設(shè)計(jì)一套自主查詢計(jì)算機(jī)系統(tǒng)，查詢到出行時(shí)所需的最佳公交路線及換乘方法，給人們出行節(jié)約更多的時(shí)間和金錢(qián)。要求：1. 僅考慮公汽線路，建立任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型與算法。并求出以下6對(duì)起始站終到站之間的最佳路線。（1）S3359S1828 （2）S1557S0481 （3）S0971S0485（4）S0008S0073 （5）S0148S0485 （6）S0087S36762. 同時(shí)考慮公汽與地鐵線路，解決1中問(wèn)題。3. 如果所有站點(diǎn)間的步行時(shí)間已知，建立任意兩站點(diǎn)間路線選擇問(wèn)題的數(shù)學(xué)模型。二、問(wèn)題分析2.1 受限條件分析

5、2.1.1 約束條件繁瑣度高1公交線路中的票價(jià)問(wèn)題分為單一票制和分段計(jì)價(jià)兩種不同情況；2耗時(shí)問(wèn)題分為站點(diǎn)耗時(shí)和換乘耗時(shí)兩類；3最短路徑已非傳統(tǒng)意義上距離的最短化，需要綜合考慮所經(jīng)站點(diǎn)數(shù)、步行距離和換乘次數(shù)等多方面因素。上述各種因素所形成的約束使本問(wèn)題并非常見(jiàn)圖論問(wèn)題，難以直接應(yīng)用圖論知識(shí)解決。 數(shù)據(jù)（信息）量大所研究的北京市公交系統(tǒng)，共有公汽線路520條，站點(diǎn)3957站，單條線路對(duì)應(yīng)站點(diǎn)約5060個(gè)；地鐵線路2條，站點(diǎn)39站。線路與站點(diǎn)間的對(duì)應(yīng)關(guān)系復(fù)雜，考慮換乘情況，運(yùn)用現(xiàn)有的Dijkstra、Floyd等圖論算法，處理該數(shù)量級(jí)數(shù)據(jù)量，時(shí)空復(fù)雜度高，時(shí)效性低，不能滿意解決本問(wèn)題。2.2 乘客選

6、擇線路分析乘客需求的多樣化乘客在進(jìn)行公交路線選擇時(shí)，考慮的因素多種多樣，有的乘客會(huì)側(cè)重考慮出行費(fèi)用；有的乘客會(huì)側(cè)重考慮出行耗時(shí)；有的乘客（如老年人、殘疾人等）會(huì)側(cè)重考慮換乘次數(shù)；較為特殊的情況時(shí)，乘客還會(huì)根據(jù)個(gè)人喜好考慮途經(jīng)站點(diǎn)、公交服務(wù)質(zhì)量等多種因素。基于以上多樣化的需求情況，針對(duì)公交線路選擇，本文確定以下三個(gè)目標(biāo)：出行耗時(shí)最短、出行費(fèi)用最少、換乘次數(shù)最少。 換乘次數(shù)無(wú)上界1統(tǒng)計(jì)計(jì)算附錄中數(shù)據(jù)，發(fā)現(xiàn)站點(diǎn)間換乘次數(shù)與到達(dá)率之間具有如下關(guān)系：圖1 站點(diǎn)間換乘次數(shù)與到達(dá)率關(guān)系圖表1 站點(diǎn)間換乘次數(shù)與到達(dá)率換乘次數(shù)012345到達(dá)率0.02530.40080.93930.99870.9999931分

7、析圖1/表1：直達(dá)線路覆蓋較少，僅為2.53%，但當(dāng)換乘次數(shù)達(dá)到3次時(shí)，站點(diǎn)間到達(dá)率為99.87%，接近100%；換乘次數(shù)為5次時(shí)到達(dá)率為100%，故換乘三次已基本滿足乘客出行需求。2.對(duì)于本問(wèn)題，容易想到通過(guò)不斷增加換乘次數(shù)以減少乘車(chē)時(shí)間或乘車(chē)距離，但是，查詢資料后得到北京公共交通集團(tuán)關(guān)于乘客對(duì)換乘次數(shù)的接受率的統(tǒng)計(jì)圖表：圖2 乘客對(duì)換乘次數(shù)的接受率表2 乘客對(duì)換乘次數(shù)的接受率換乘次數(shù)012345接受率176.04%25.32%0.04%(7.02e-4)%0分析圖2/表2：幾乎沒(méi)有乘客接受4次換乘或更多次換乘的出行方案。從人性化角度考慮，不能無(wú)限次的增加換乘次數(shù)。因此本題僅考慮換乘次數(shù)最多

8、為3次的線路方案。2.3 問(wèn)題分支分析2.3.1 問(wèn)題一分析對(duì)于問(wèn)題一，題目給出的公汽線路主要分為上下行線、原路折回線及環(huán)行線，線路不同，選擇不同，故對(duì)每種線路需要進(jìn)行抽象化處理。站點(diǎn)較多，可以利用圖論知識(shí)描述該公交網(wǎng)絡(luò)：即將每個(gè)站點(diǎn)轉(zhuǎn)化為圖論中圖的每個(gè)節(jié)點(diǎn)，線路轉(zhuǎn)化為鄰接邊，在邊的信息中包含線路名、票價(jià)、行駛方向等。依據(jù)轉(zhuǎn)化思想將尋求不同目標(biāo)下的問(wèn)題轉(zhuǎn)化為圖論中不同有向賦權(quán)圖中內(nèi)尋求最短路的問(wèn)題。設(shè)計(jì)合適的算法在圖論中尋求三種目標(biāo)下的最佳路線。2.3.2 問(wèn)題二的分析對(duì)于問(wèn)題二，對(duì)于兩條地鐵線路，依據(jù)問(wèn)題一中的抽象化方法進(jìn)行抽象化處理；對(duì)于地鐵站點(diǎn)，由地鐵與鄰近公汽站點(diǎn)可換乘的信息可知地鐵站

9、點(diǎn)及其周?chē)墓军c(diǎn)距離較近，考慮將其抽象化歸一為新的站點(diǎn)，減小站點(diǎn)差異性，重新構(gòu)造站點(diǎn)間的鄰接矩陣。基于問(wèn)題一更新數(shù)據(jù)，尋找合適的算法組合不同路線及站點(diǎn)分別給出三種目標(biāo)下的最優(yōu)方案。 問(wèn)題三的分析考慮公汽站點(diǎn)與地鐵站點(diǎn)的實(shí)際分布情況，在某些轉(zhuǎn)乘點(diǎn)存在步行小段距離再轉(zhuǎn)車(chē)可以節(jié)省時(shí)間或減少轉(zhuǎn)車(chē)次數(shù)的情況，在求解時(shí)需確定線路中該類選擇多樣化的站點(diǎn)，然后主要優(yōu)化該類站點(diǎn)后繼線路的選擇方案，達(dá)到以上三個(gè)目標(biāo)。三、模型假設(shè)1、車(chē)站站點(diǎn)無(wú)重名； 2、相鄰站點(diǎn)間平均行駛時(shí)間一定； 3、公交運(yùn)行順暢：無(wú)交通阻塞、無(wú)車(chē)輛故障、無(wú)道路交通事故等意外情況；4、公交準(zhǔn)點(diǎn)到達(dá)，不考慮紅綠燈等待時(shí)間；5、各路線公交車(chē)發(fā)車(chē)

10、頻度相同；6、限制最多換乘車(chē)次為3次。四、符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)，為3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)，為2.5分鐘公汽換乘公汽平均耗時(shí)，為5分鐘(其中步行時(shí)間2分鐘) 地鐵換乘地鐵平均耗時(shí)，為4分鐘(其中步行時(shí)間2分鐘) 地鐵換乘公汽平均耗時(shí)，為7分鐘(其中步行時(shí)間4分鐘) 公汽換乘地鐵平均耗時(shí)，為6分鐘(其中步行時(shí)間4分鐘)從站點(diǎn)乘車(chē)到達(dá)站點(diǎn)站點(diǎn)到達(dá)站點(diǎn)所用的最少時(shí)間值（分鐘）站點(diǎn)到達(dá)站點(diǎn)的步行次數(shù)公汽單一票價(jià)1元公汽分段計(jì)價(jià)（020站：1元；2140站2元；40站以上：3元；=1,2,3）地鐵票價(jià)3元乘客總路程所花的時(shí)間乘客總路程所花的費(fèi)用乘

11、客總路程經(jīng)過(guò)的公交站數(shù)（不含起始站）乘客公汽換乘公汽的次數(shù)乘客總路程經(jīng)過(guò)的地鐵站數(shù)（不含起始站）乘客公汽換乘地鐵的次數(shù)乘客地鐵換乘公汽的次數(shù)乘客乘坐的單一票價(jià)公交路線數(shù)乘客乘坐的分段公交路線數(shù)（分三個(gè)級(jí)別，=1,2,3）公汽的票價(jià)函數(shù)（元）整型函數(shù) ，其值為1或0換車(chē)的兩站之間所隔的站臺(tái)數(shù)五、模型的建立與求解5.1 問(wèn)題一 模型建立與求解本問(wèn)題主要研究任意兩公汽站點(diǎn)間線路選擇的數(shù)學(xué)模型與算法。5.1.1 模型準(zhǔn)備1、確定目標(biāo)分別在不同行程需求下推薦最佳路線，根據(jù)實(shí)際情況得到以下三個(gè)目標(biāo)：（1） 換乘次數(shù)最少；（2） 行程耗時(shí)最少；（3） 行程費(fèi)用最少。2、對(duì)三種公汽線路進(jìn)行抽象化處理（1）上、

12、下行線原路返回線路這種線路有兩個(gè)端點(diǎn)站，在兩個(gè)端點(diǎn)之間雙向行車(chē)，并且兩個(gè)方向上的行車(chē)路線相同，經(jīng)過(guò)同樣的站點(diǎn)序列。由于線路的方向不同，故上行線和下行線抽象為兩條線路處理。（2）線路為環(huán)行線實(shí)際情況中環(huán)形路線一般是雙環(huán)，但在對(duì)這兩條線路進(jìn)行抽象時(shí)，為保證任意兩站點(diǎn)距離最近，把每條線路抽象為兩條，即環(huán)形抽象為順時(shí)針2個(gè)半環(huán)、逆時(shí)針2個(gè)半環(huán)共計(jì)四條線路。（3）下行線與上行線經(jīng)過(guò)站點(diǎn)不同由于下行線與上行線經(jīng)過(guò)站點(diǎn)不同，該種線路顯然抽象為兩條不同線路。圖3 不同公汽線路的抽象化 3、換乘次數(shù)直觀化表示換乘次數(shù)可分為：(1) 換乘0次：直達(dá)；(2) 換乘1次；(3) 換乘2次；(4) 換乘3次；如下圖：圖

13、4 換乘次數(shù)的抽象化4、建立公汽直達(dá)信息庫(kù)：元胞結(jié)合公眾出行心理，優(yōu)先考慮兩站點(diǎn)之間是否有直達(dá)公汽線路，故在查詢系統(tǒng)內(nèi)部需設(shè)有任兩站點(diǎn)的直達(dá)線路表，以方便查詢，當(dāng)存在直達(dá)線路時(shí)直接輸出所有直達(dá)線路；若無(wú)直達(dá)線路，再搜索換乘路線，出于以上考慮，在系統(tǒng)內(nèi)部需建立公汽直達(dá)信息庫(kù)。本問(wèn)題共涉及3957 個(gè)公汽站點(diǎn),站點(diǎn)信息量大，所以中的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的選擇非常重要：若采用數(shù)據(jù)矩陣存儲(chǔ)，操作復(fù)雜，存儲(chǔ)量大，轉(zhuǎn)而使用MATLAB 內(nèi)建元胞結(jié)構(gòu)建立，并利用陣列存儲(chǔ)站點(diǎn)間所有直達(dá)線路的信息。陣列數(shù)據(jù)存儲(chǔ)類型若使用雙精度實(shí)型，當(dāng)部分陣列不存在直達(dá)信息時(shí)，該類型仍然占用存儲(chǔ)，總存儲(chǔ)量必將超過(guò)MATLAB內(nèi)存限制，可

14、使用無(wú)符整型表示信息數(shù)據(jù)，當(dāng)兩站點(diǎn)間信息陣列不存在直達(dá)信息時(shí)，不占用存儲(chǔ)，故縮小存儲(chǔ)減少系統(tǒng)讀取數(shù)據(jù)時(shí)間。具體元胞結(jié)構(gòu)設(shè)計(jì)如下：Cell1,1Cell1,2車(chē)號(hào)耗時(shí)相隔站點(diǎn)數(shù)Cell1,3Cell2,1Cell2,2Cell2,3圖5 元胞示意圖上圖中Cell1,21行2列直達(dá)陣列描述了從站點(diǎn)S0001到站點(diǎn)S0002的所有直達(dá)線路信息，其中陣列中一頁(yè)內(nèi)每行代表一條直達(dá)線路信息。 模型的建立需求過(guò)程如下描述：當(dāng)輸入起點(diǎn)和終點(diǎn)后，根據(jù)處理數(shù)據(jù)后輸出直達(dá)線路，否則自動(dòng)搜尋換乘次數(shù)最少的路線。若換乘次數(shù)相同情況下有多種轉(zhuǎn)乘方案，提供耗時(shí)最短轉(zhuǎn)乘路線（包括轉(zhuǎn)乘次數(shù)、行程總時(shí)間、轉(zhuǎn)乘站點(diǎn)及路線、行程總費(fèi)

15、用）供查詢者自主選擇，同時(shí)系統(tǒng)可以向查詢者推薦“時(shí)間最短”“費(fèi)用最省”“換乘次數(shù)最少”的不同目標(biāo)下的最佳路線。建立兩站點(diǎn)間換乘線路數(shù)矩陣，方便用戶輸入起點(diǎn)與終點(diǎn)后，系統(tǒng)立即查詢出到達(dá)終點(diǎn)最少轉(zhuǎn)乘次數(shù)。統(tǒng)計(jì)中各陣列長(zhǎng)度，得到任意兩站點(diǎn)的直達(dá)線路數(shù)目，構(gòu)造以兩兩站點(diǎn)間直達(dá)路線數(shù)目為元素的直達(dá)線路數(shù)矩陣 ，通過(guò)矩陣運(yùn)算得到任兩站點(diǎn)間換乘次數(shù)矩陣，從而可快速查詢?nèi)我鈨烧鹃g所需的最少換乘次數(shù)。1、直達(dá)線路路數(shù)矩陣的建立根據(jù)，建立直達(dá)線路數(shù)矩陣，其矩陣元素表示站點(diǎn)到站點(diǎn)的直達(dá)線路數(shù)n，其中，當(dāng)時(shí)為無(wú)效路徑，設(shè)定值為0，即： （1）以表示所有公汽所經(jīng)過(guò)的站點(diǎn)總數(shù)，則直達(dá)線路數(shù)矩陣可表示為： （2）2、換乘線

16、路數(shù)矩陣直達(dá)矩陣為階方陣，矩陣中元素表示任意兩站點(diǎn)間通過(guò)1次換乘的路線數(shù)，即：=· （3）下面以中1行2列元素為例對(duì)中元素來(lái)源進(jìn)行舉例說(shuō)明：例： 假設(shè)上式中等號(hào)右邊僅，其余為0，說(shuō)明1站點(diǎn)可直達(dá)到3站點(diǎn)，3站點(diǎn)可直達(dá)2站點(diǎn)，當(dāng)=·后，即1站點(diǎn)通過(guò)一次換乘到達(dá)2站點(diǎn)，換乘點(diǎn)為站點(diǎn)3，則中元素表示站點(diǎn)到站點(diǎn)通過(guò)1次換乘的路線數(shù)由圖論與矩陣知識(shí)，可知如下推廣： ，為站點(diǎn)的直達(dá)路線數(shù)： （4）其中的元素表示通過(guò)n-1次換乘站點(diǎn)的線路數(shù)。3、最少換乘次數(shù)矩陣的建立引入矩陣，其矩陣元素為使得的（）的最小值，即： （5）則表示從站點(diǎn)必要的最少換乘次數(shù)，以矩陣表示最少換乘次數(shù)矩陣，則： （

17、6）其中，元素表示從站點(diǎn)必要的最少換乘次數(shù)基于最少換乘次數(shù)矩陣,每對(duì)起始站、終點(diǎn)站的最少換乘次數(shù)列出如下：表3 最少換乘次數(shù)表 線路編號(hào) 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 終到站 S1828 S0481 S0485 S0073 S0485 S3676 最少換乘 1 2 1 1 2 1 5.1.3 模型求解1、 算法步驟描述：step1:起點(diǎn)為，終點(diǎn)為，換乘次數(shù)為，直達(dá)即=0，非直達(dá)時(shí)利用鄰接矩陣 由條件改進(jìn)查找路徑，經(jīng)過(guò)站點(diǎn)為，記錄換乘次線路最小用時(shí) ，中間線路信息從元胞中抽取，保存線路信息；若=3,轉(zhuǎn)至 step3，否則，

18、轉(zhuǎn)入step2。step2:，以min()（其中）為次換乘時(shí)間上界，轉(zhuǎn)至 step1；step3:結(jié)束，打印線路信息。2、約束條件描述：目標(biāo)一：換乘次數(shù)最少： （7）目標(biāo)二：線路用時(shí)最短僅考慮公汽路線的情況下，得到任意兩站站之間的最少乘車(chē)用時(shí)（包括初始站點(diǎn)的等待時(shí)間3min），即：最少用時(shí)=乘車(chē)時(shí)間+換乘時(shí)間 （8）所求的最短時(shí)間要受到如下的7個(gè)條件約束： （9）以上目標(biāo)函數(shù)表示從站點(diǎn)到站點(diǎn)公汽線路中行使時(shí)間和換乘時(shí)間的總和，其中：（1）表示從站點(diǎn)到站點(diǎn)條線路所經(jīng)過(guò)的站點(diǎn)數(shù)；（2）表示總的轉(zhuǎn)車(chē)次數(shù)；（3）表示出發(fā)站應(yīng)滿足的條件，即乘客從某線路前往某站。（4）表示目的站應(yīng)滿足的條件，即乘客從某線

19、路到達(dá)該站。（5）表示線路與某站點(diǎn)的關(guān)系，若線路不經(jīng)過(guò)某站點(diǎn)，式子左右兩邊都為0，若線路經(jīng)過(guò)某站點(diǎn)，則式子左右兩邊都為1。（6）分為以下幾種情況：1）假如線路沒(méi)有經(jīng)過(guò)某站點(diǎn)，此時(shí)的值為0，同時(shí)的值也為0，中間的式子為0；2)假如線路經(jīng)過(guò)某站點(diǎn)且沒(méi)有轉(zhuǎn)車(chē)（換乘），此時(shí)的值為1，同時(shí)的值也為1，中間的式子為0；3）假如線路經(jīng)過(guò)某站點(diǎn)且有轉(zhuǎn)車(chē)（換乘）的情況，對(duì)于轉(zhuǎn)車(chē)前的線路，此時(shí)的值為1，同時(shí)的值也為0中間式子為1；對(duì)于轉(zhuǎn)車(chē)后的線路有的值為0，同時(shí)的值也為1，中間式子為-1。這三種情況的結(jié)果符合模型的換乘函數(shù)。目標(biāo)三：最小費(fèi)用本系統(tǒng)在選擇公汽線路時(shí)考慮花費(fèi)，使到達(dá)目的地的花費(fèi)最?。?（10）其中表示

20、線路從站點(diǎn)至站點(diǎn)中間所經(jīng)過(guò)的站點(diǎn)數(shù)分析公汽線路票價(jià)，有票價(jià)函數(shù)： （11）基于以上各式，得以下目標(biāo)函數(shù)： （12）以上算法實(shí)現(xiàn)見(jiàn)附錄。3、求解結(jié)果1）報(bào)表說(shuō)明：目標(biāo)：1,2,3,4,5,6分別表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676；換乘：換乘次數(shù)；時(shí)間：線路總計(jì)用時(shí)（分鐘）；站1：第1次換乘站點(diǎn)；站2：第2次換乘站點(diǎn)；站3：第3次換乘站點(diǎn)；線1：第1次乘坐的公汽線路；線2：第2次乘坐的公汽線路；線3：第3次乘坐的公汽線路；線4：第4次乘坐的公汽線路；費(fèi)用：從始發(fā)站到目的站所需要的總費(fèi)用（元）；程序：

21、MATLAB程序運(yùn)行時(shí)間（秒）。2）換乘次數(shù)最少路線：表4 換乘次數(shù)最少路線方案目標(biāo)換乘時(shí)間站1站2站3線1線2線3線4費(fèi)用程序111041784-436167-34.62210919193186-84189460-361.8311312184-13417-3232.64186291-15958-2209.9186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-21862559-15958-31862633-159474-21862683-15958-21863053-159474-21863315

22、-15958-31863614-15958-21863917-355345-252109362210-308156417-363.92109363332-308156417-32109363351-308156417-361683496-454209-267.23）最短用時(shí)路線：表5 用時(shí)最短的路線方案目標(biāo)換乘時(shí)間站1站2站3線1線2線3線4費(fèi)用程序126717461784-324485167-34.626720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-3231021

23、91931869028418991254461.8310219193186903841899123943210625172159-13290469-3232.643666304835251592313281034209.9366630604525159231328103436663060952515923132810343668544835251592313281034366854604525159231328103436685460952515923132810343661383132752543232810343661691132752519823281034366172813275251

24、98140328103436622631327525355140328103436627554835253551732810343662755604525355173281034366275560952535517328103436637661327525198232810345310536042361221030881156417463.9310536042361333230881156417431053604236133513088115641746249884272123197367.24）費(fèi)用最少路線：表 6 費(fèi)用最少的路線方案目標(biāo)換乘時(shí)間站1站2站3線1線2線3線4費(fèi)用程序11104

25、1784-436167-34.626717461784-324485167-326720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-32210919193186-84189460-30.8311312184-13417-32.2210625172159-13290469-34186291-15958-20.0077186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-2186

26、2633-159474-21862683-15958-21863053-159474-21863614-15958-21863917-355345-252109362210-308156417-30.62109363332-308156417-32109363351-308156417-361683496-454209-20.0019以上表中已按換乘次數(shù)最少、出行用時(shí)最短、費(fèi)用最少三個(gè)目標(biāo)列出最優(yōu)出行路線方案，用戶只需要根據(jù)實(shí)際需要選取即可。結(jié)果分析分析以上報(bào)表：1、幾乎所有換乘3次的線路都可以以較短時(shí)間、較低的費(fèi)用到達(dá)目的站點(diǎn)，說(shuō)明選擇三次作為換乘次數(shù)的上限是可行的。2、考慮查詢系統(tǒng)的時(shí)效性

27、，給出MATLAB程序運(yùn)行時(shí)間。由運(yùn)行時(shí)間：查詢換乘次數(shù)小于1次含1次的線路，程序運(yùn)行時(shí)間遠(yuǎn)小于1秒；查詢換乘2次程序耗時(shí)不超過(guò)5秒；查詢換乘3次程序所需時(shí)間200秒左右。在實(shí)際情況中，乘客在乘車(chē)點(diǎn)等車(chē)時(shí)進(jìn)行路線查詢，以上查詢時(shí)間是可以被乘客接受的。以上所述程序運(yùn)行時(shí)間說(shuō)明在本文描述的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)下，改進(jìn)的鄰接算法的可行性與較低的時(shí)間復(fù)雜度。綜述，模型I求解的線路方案集使用于不同需求下的所有用戶，具有較強(qiáng)的實(shí)用價(jià)值，很大程度上滿足了乘客乘車(chē)線路多樣化的需求。5.2 問(wèn)題二的模型建立與求解5.2.1 模型準(zhǔn)備1、兩種地鐵線路抽象處理基于對(duì)三種公汽線路路線的抽象方法，以相同的方法對(duì)兩地鐵線路T1、

28、T2進(jìn)行抽象化處理：T1：雙向線路，根據(jù)不同的方向?qū)⑵涑橄鬄閮蓷l單向行駛線路；T2：環(huán)行線路，根據(jù)公汽線路抽象方法化為4條行駛線路處理。2、歸一站點(diǎn)由題目給出的地鐵換乘公汽的數(shù)據(jù)可知：地鐵站點(diǎn)附近存在多個(gè)公汽站點(diǎn)。處于同一個(gè)地鐵站點(diǎn)附近的公汽站點(diǎn)地理位置應(yīng)非常接近或容易換乘，定義這些站點(diǎn)為緊鄰站點(diǎn)，將緊鄰站點(diǎn)與對(duì)應(yīng)的地鐵站點(diǎn)抽象為一個(gè)新的站點(diǎn)，減小這類站點(diǎn)的差異性。例如地鐵換乘公汽的數(shù)據(jù)首行“D01:S0567,S0042,S0025”,可認(rèn)為這四個(gè)站點(diǎn)實(shí)際距離較近，為緊鄰站點(diǎn)，將五個(gè)站點(diǎn)做歸一處理，構(gòu)造新站點(diǎn),以上過(guò)程示意圖如下：圖6 可互換站點(diǎn)抽象為一個(gè)站點(diǎn)示意圖基于這種思想，在整個(gè)交通網(wǎng)

29、絡(luò)中將所有地鐵站點(diǎn)及其緊鄰站點(diǎn)分別做歸一站點(diǎn)處理。認(rèn)為在新站點(diǎn)所代表的站點(diǎn)集中的任意站點(diǎn)可通過(guò)步行到達(dá)，且時(shí)間忽略。3、建立公汽、地鐵直達(dá)信息庫(kù)綜合考慮公汽與地鐵時(shí)建立的實(shí)質(zhì)是新站點(diǎn)與新站點(diǎn)間的直達(dá)線路信息集。用戶輸入起點(diǎn)和終點(diǎn)后，系統(tǒng)內(nèi)部先自動(dòng)查找兩點(diǎn)所屬的新站點(diǎn)，然后查找新站點(diǎn)間可直達(dá)的線路，并給出起點(diǎn)及其附近站點(diǎn)直達(dá)終點(diǎn)及其附近站點(diǎn)的最佳乘車(chē)線路。采用與5.1相同的思路及方法，將已知的可直達(dá)公汽線路映射到，建立新的直達(dá)線路信息庫(kù)，結(jié)合地鐵費(fèi)用與地鐵換乘公汽等待時(shí)間填充元胞內(nèi)陣列描述的直達(dá)線路信息。具體元胞結(jié)構(gòu)設(shè)計(jì)圖如下：Cell1,1Cell1,2車(chē)號(hào)耗時(shí)相隔站點(diǎn)數(shù)Cell1,3Cell

30、2,1Cell2,2Cell2,3圖7 直達(dá)線路信息庫(kù)（3996*3996）元胞結(jié)構(gòu)示意圖上圖中Cell1,21行2列直達(dá)陣列描述了從站點(diǎn)S0001到站點(diǎn)S0002的所有直達(dá)線路信息，其中陣列中一頁(yè)內(nèi)每行代表一條直達(dá)線路信息。5.2.2 模型建立需求過(guò)程如下描述：對(duì)于新站點(diǎn)，可等同看作問(wèn)題一中的公汽站點(diǎn)，當(dāng)用戶輸入起點(diǎn)和終點(diǎn)后，優(yōu)先顯示直達(dá)線路，否則自動(dòng)搜尋轉(zhuǎn)乘線路，同時(shí)，系統(tǒng)向查詢者推薦不同目標(biāo)下的最佳路線及轉(zhuǎn)乘方案?？紤]乘客可以乘坐地鐵，依據(jù)問(wèn)題一中的模型，調(diào)整如下：1、乘客選擇的公交為公汽或地鐵，相應(yīng)有變量： （13）表示公交經(jīng)過(guò)t線路有i站點(diǎn)到達(dá)j站點(diǎn)。2、乘客由公汽轉(zhuǎn)乘地鐵，相應(yīng)有變

31、量及約束條件： （14） （15）3、乘客由地鐵轉(zhuǎn)乘公汽，相應(yīng)有變量及約束條件： （16） （17）4、乘客可由地鐵轉(zhuǎn)乘地鐵，相應(yīng)有變量及約束條件： （18）5、乘客在公汽站可不換公汽、可轉(zhuǎn)乘公汽、可轉(zhuǎn)乘地鐵，三種選擇不同時(shí)進(jìn)行，相應(yīng)有變量及約束條件： （19）6、乘客在D12及D18地鐵站可不換地鐵線、可換乘公汽、可換乘地鐵線，三種選擇不同時(shí)進(jìn)行，相應(yīng)有變量及約束條件： （20）5.2.3 模型求解1、算法步驟描述：step1:起點(diǎn)為，終點(diǎn)為，換乘次數(shù)為，直達(dá)即=0，非直達(dá)時(shí)利用鄰接矩陣 由條件改進(jìn)查找路徑，經(jīng)過(guò)站點(diǎn)為，記錄換乘次線路最小用時(shí) ，中間線路信息從元胞中抽取，保存線路信息；若=3

32、,轉(zhuǎn)至 step3，否則，轉(zhuǎn)入step2。step2:，以min()（其中）為次換乘時(shí)間上界，轉(zhuǎn)至 step1；step3:結(jié)束，打印線路信息。2、求解結(jié)果1）報(bào)表說(shuō)明：目標(biāo)：1,2,3,4,5,6分別表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676；換乘：換乘次數(shù)；時(shí)間：線路總計(jì)用時(shí)（分鐘）；站1：第1次換乘站點(diǎn)；站2：第2次換乘站點(diǎn)；站3：第3次換乘站點(diǎn)；線1：第1次乘坐公交路線；線2：第2次乘坐公交路線；線3：第3次乘坐公交路線；線4：第4次乘坐公交路線；費(fèi)用：從始發(fā)站到目的地所需要的費(fèi)用（元）；程序：

33、程序運(yùn)行時(shí)間（秒）。2）換乘次數(shù)最少路線方案：表7 換乘次數(shù)最少路線方案目標(biāo)換乘時(shí)間站1站2線1線2線3費(fèi)用程序11140S0304L469L21737110S1241L436L167104S1784L436L16722115D20：S2079，S2933，S1919，S1921，S1920S0902L084L417L25432.2112D20：S2079，S2933，S1919，S1921，S1920S2424L084L417L254109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46031152S0872L119L41735.5134S0

34、992L013L417131S2184L013L41741110S0275L043L17035.686S0491L159L058283D13：S2633，S0399，S0401，S0400L159L47452109S0036S2210L308L156L41731.6106S3604D20：S2079，S2933，S1919，S1921，S1920L308L454L41791D02：S1487D20：S2079，S2933，S1919，S1921，S1920L02T001L417590.5D02：S1487D21：S0465，S0467，S0466，S0464L024T001L05156023T

35、00232.528T00228T0023）出行用時(shí)最短路線方案：表8 出行用時(shí)最短路線方案目標(biāo)換乘時(shí)間站1站2線1線2線3費(fèi)用程序1267S1746S1784L324L4851673722109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46032.23299D01：S0567，S0042，S0025D21：S0465，S0467，S0466，S0464L094T001L05155.54258D30：S3874，S1426，S1427D25：S0526，S0528，S0527，S0525L150T002L10355.652106S3604D20

36、：S2079，S2933，S1919，S1921，S1920L308L454L41731.66023T00232.54） 費(fèi)用最少路線方案：表9 費(fèi)用最少路線方案目標(biāo)換乘時(shí)間站1站2線1線2線3費(fèi)用程序1267S1746S1784L324L4851673722109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46032.231131S2184L013L41735.54183D13：S2633，S0399，S0401，S0400L159L4748325.652106S3604D20：S2079，S2933，S1919，S1921，S1920L30

37、8L454L41731.66023T00232.5結(jié)果分析加入地鐵后，乘客有了更多的公交路線選擇，可以在換乘兩次之內(nèi)到達(dá)任意目的站點(diǎn)，減少了換乘次數(shù)，優(yōu)化了交通網(wǎng)絡(luò)。5.3模型的建立與求解5.3.1 問(wèn)題分析1、問(wèn)題一與問(wèn)題二啟發(fā)分析 將步行方式考慮在了出行方式當(dāng)中更符合實(shí)際。因?yàn)楫?dāng)站點(diǎn)間只相隔較少的幾個(gè)站點(diǎn)時(shí)，選擇步行方式不但節(jié)省花費(fèi)同時(shí)減少換乘次數(shù)，增加步行方式可能增加新的公交路線。在解決問(wèn)題一、問(wèn)題二的過(guò)程中，基于換乘次數(shù)逐步分析給出了起始點(diǎn)與終點(diǎn)之間的最佳路線。對(duì)比問(wèn)題一、問(wèn)題二分析，可得如下啟發(fā)： 1）在兩個(gè)問(wèn)題的最佳路線中均出現(xiàn)上車(chē)后只乘坐一站就下車(chē)的情況，這樣情況乘客可以考慮步行

38、經(jīng)過(guò)中間換乘站到達(dá)下個(gè)換乘站； 2）增加一種交通工具可使原來(lái)不能直達(dá)的站點(diǎn)直達(dá)，優(yōu)化了交通網(wǎng)絡(luò)。例如前兩個(gè)問(wèn)題中的5、6 ，增加地鐵后，5找到時(shí)間更短的路線，而6找到直達(dá)路線。步行可替代交通工具實(shí)現(xiàn)以上功能：如果在某站點(diǎn)下車(chē)后沒(méi)有直接換乘的車(chē)次，但較近的兩行車(chē)路線上有相鄰站點(diǎn), 行人可選擇步行到鄰近路線站點(diǎn)進(jìn)行換乘。所得到的啟發(fā)1和2圖形直觀化描述如下：圖8 采用步行方式優(yōu)化路線3）公交路線都是有向的，即在站點(diǎn)間只能由起始方向至終點(diǎn)方向前進(jìn)，如<,Start,>，<,end,>,只能在<>,<>中選擇，不能在<>,<>中選

39、擇，但步行不需要考慮此約束，可以在<>,<>中選擇站點(diǎn)，通過(guò)沿已經(jīng)過(guò)路線逆行步行方式尋求最佳路線。4）問(wèn)題一問(wèn)題二沒(méi)有考慮站點(diǎn)間步行時(shí)間問(wèn)題，實(shí)際情況中：在相對(duì)小于車(chē)輛行駛時(shí)間情況下，人們步行一段距離再轉(zhuǎn)車(chē)，可減少出行總時(shí)間。2、模型建立分析含步行線路選擇問(wèn)題與四種因素相關(guān)：換乘次數(shù)、總時(shí)間、花費(fèi)、步行次數(shù)n。 下面分析步行次數(shù)對(duì)前三種因素的影響，在此列舉與之前相比可能優(yōu)化的情形。圖9 換乘抽象化圖形有1個(gè)或很少的中間站點(diǎn)，在站點(diǎn)A乘坐公交到站點(diǎn)，換乘一次到達(dá)后，再換乘一次最終到達(dá)B，換乘次數(shù)為2，步行次數(shù)為0?？紤]步行時(shí)，選擇從走到，減少換乘次數(shù)同時(shí)減少花費(fèi)，比如，從

40、 S3359 到 S1828的方案中，出現(xiàn)的從中轉(zhuǎn)站S1784到S1828只有一站的情況。當(dāng)路線是分段計(jì)價(jià)的時(shí)，如果步行到達(dá)最后一站，會(huì)節(jié)省花費(fèi)。例如起始站點(diǎn)A到達(dá)站點(diǎn)B剛好是21/31/41站。通過(guò)上述的分析，考慮步行的模型應(yīng)存在以下優(yōu)點(diǎn)：1）增加新的可能的路徑，因?yàn)椴叫胁豢紤]公交線路的方向性； 2）節(jié)省費(fèi)用，合理的步行安排可以降低費(fèi)用或減少換乘次數(shù)，但可能以增加總時(shí)間和步行次數(shù)為代價(jià)。5.3.2模型準(zhǔn)備1、模型假設(shè)1） 所有站點(diǎn)之間的步行時(shí)間是固定不變的，不受其他外界隨機(jī)因素的干擾；2）只有規(guī)定步行時(shí)間 (取定的整數(shù))之內(nèi)的站點(diǎn)之間才可以互稱為鄰近站點(diǎn)，步行后選擇鄰近站點(diǎn)或同一站點(diǎn)進(jìn)行車(chē)次

41、的換乘；3）只考慮公汽站點(diǎn)間可以步行，地鐵站點(diǎn)中不能步行；2、新增符號(hào)說(shuō)明 ：任意兩個(gè)相鄰的公交站點(diǎn)間步行平均時(shí)間為t；T：判定是否為鄰近站點(diǎn)的時(shí)間上確界 ；：站點(diǎn)與其鄰近站點(diǎn)之間的步行時(shí)間。 模型I建立綜合上述分析，考慮啟發(fā)一，在知道所有站點(diǎn)間步行時(shí)間后，以最少換乘次數(shù)為目標(biāo)，搜索最小換乘次數(shù)路線中所有只坐一站的換乘的情況，將其用步行來(lái)代替，以犧牲出行時(shí)間為代價(jià)減少換乘次數(shù)，求解任意兩個(gè)站點(diǎn)間的最小換乘路線。將最小換乘次數(shù)按公交直達(dá)，一次換乘，二次換乘和三次換乘分別討論步行優(yōu)化換乘模型的策略。設(shè)起始站點(diǎn)和目的站點(diǎn)分別為站點(diǎn)s和e，相鄰兩站之間的距離基本相等為L(zhǎng)，且L小于乘客愿意采取步行的最大

42、距離。圖10 轉(zhuǎn)乘圖Step1：從s可以直達(dá)e：如圖七中（a）所示，則建議直接從s點(diǎn)步行到e點(diǎn)，不需乘坐公交。 Step 2：從站點(diǎn)s經(jīng)站點(diǎn)c轉(zhuǎn)乘一次到達(dá)e：如圖中（b）所示，若sc<ce（sc>ce），則路線可以根據(jù)實(shí)際狀況將換乘一次優(yōu)化為sc 段步行,ce段直達(dá)（或ce段直達(dá)，sc段步行）。 Step3：從站點(diǎn)s經(jīng)站點(diǎn)c，d 轉(zhuǎn)乘兩次到達(dá)e：如圖中（c）所示，若sc<L或cd<L或de<L,則路線可以根據(jù)實(shí)際交通繁忙狀況或乘客自己的意愿將換乘兩次優(yōu)化為換乘一次的情況； 模型II準(zhǔn)備基于前面問(wèn)題的分析，本模型主要以出行總時(shí)間最少為目標(biāo)，同時(shí)考慮轉(zhuǎn)乘次數(shù)盡量少，行

43、程費(fèi)用盡量低原則。模型I分析了換乘時(shí)步行一站的情況，在現(xiàn)實(shí)生活中，人們常常步行一站以上，而且乘客沿公汽線路步行也是不合理的。假設(shè)人們步行路線不受公汽線路限制，但有最大承受時(shí)間，受到問(wèn)題二的啟發(fā)，若已知所有站點(diǎn)之間的步行時(shí)間，可以認(rèn)為在人們最大步行范圍內(nèi)，所有公汽站點(diǎn)都可看作相互鄰接。在所有站點(diǎn)之間的步行時(shí)間確定的情況下，對(duì)于相距不遠(yuǎn)的兩站，考慮以其中站點(diǎn)為圓心，以人們能接受的步行距離為半徑做圓，將在該圓形區(qū)域內(nèi)所有的站點(diǎn)抽象為一個(gè)站點(diǎn)。圖11 依步行距離歸一站點(diǎn)模型II的建立1、步行鄰邊化模型 假設(shè)乘客所能忍受的最長(zhǎng)步行時(shí)間為T(mén)，定義站點(diǎn)與站點(diǎn)間的平均步行時(shí)間。定義以乘客所在的起始點(diǎn)為圓心，以

44、最長(zhǎng)步行時(shí)間對(duì)應(yīng)的距離為半徑的圓，該圓形區(qū)域稱為起始點(diǎn)的鄰接圓域（如圖所示）。由假設(shè)知，鄰接圓域內(nèi)任意公汽站點(diǎn)都與相鄰接，且與的鄰接耗時(shí)為。2、模型說(shuō)明： 1）考慮步行后的總耗時(shí)等于未考慮步行的耗時(shí)加鄰接耗時(shí)的和； 2）鄰接耗時(shí)之和不超過(guò)乘客所能忍受的最長(zhǎng)步行時(shí)間； 3、目標(biāo)分析 1）目標(biāo)一：行程總時(shí)間最短 總時(shí)間的目標(biāo)函數(shù)為： （21）2）目標(biāo)二：行程總費(fèi)用最少 滿足時(shí)間最短目標(biāo)后，尋找所有可行方案中費(fèi)用最小的路線，在本層目標(biāo)分析時(shí)，將圖中的權(quán)值賦為途中所需的費(fèi)用。p表示站點(diǎn)到的行程費(fèi)用，則行程總費(fèi)用最小可表示為： （22）有以下目標(biāo)函數(shù)； （23）5.3.5 模型II求解算法1、算法思想：

45、最少換乘的廣度優(yōu)先算法 2、算法描述如下： Step 1：輸入起點(diǎn)目的點(diǎn)，根據(jù)輸入的站點(diǎn)進(jìn)行優(yōu)化，映射入緊鄰站點(diǎn)集。Step2:查找并記錄經(jīng)過(guò)及其緊鄰站點(diǎn)所有路線，記錄上 的所有站點(diǎn)；查找并記錄經(jīng)過(guò)目的站點(diǎn)及其緊鄰站點(diǎn)的所有線路，若，則表明存在從到的一條直達(dá)線路，輸出結(jié)果；否則轉(zhuǎn)Step； Step3: 搜索并記錄公交線路的站點(diǎn)，搜索并記錄公交線路的站點(diǎn)，判斷是否有，若有一個(gè)點(diǎn)滿足要求，該站點(diǎn)即為一次換乘的站點(diǎn)。 若有幾個(gè)站點(diǎn)滿足要求，則先分別求出每一個(gè)站點(diǎn)的距離最短的換乘方案，然后選擇所有方案中距離最短的換乘方案為最優(yōu)線路，輸出結(jié)果；若沒(méi)有，繼續(xù)。Step：搜索并記錄站點(diǎn)所在的線路，記錄上的

46、所有站點(diǎn)，判斷是否有，若有某個(gè)站點(diǎn)滿足要求。則站點(diǎn)為第二個(gè)換乘站點(diǎn)。從起始站點(diǎn)經(jīng)過(guò)一次換乘(假設(shè)換乘點(diǎn)為站點(diǎn)D)，可以到達(dá)站點(diǎn)，從站點(diǎn)可以換乘公交車(chē)直達(dá)目的站點(diǎn)。Step：按照步驟Step和Step的方法求出從起始站點(diǎn)到站點(diǎn)的一次換乘的最優(yōu)線路，再按照step的方法求出從站點(diǎn)到目的站點(diǎn)的最優(yōu)線路。兩個(gè)換乘站點(diǎn)和兩段最優(yōu)線路即組成了從起始站點(diǎn)到目的站點(diǎn)的最優(yōu)線路。若有多個(gè)站點(diǎn)滿足，則分別求出各站點(diǎn)的最優(yōu)換乘方案，比較各方案的線路距離，選擇一種距離最短的換乘線路方案作為最后的結(jié)果，輸出。六、模型檢驗(yàn)與評(píng)價(jià)6.1 模型檢驗(yàn)與靈敏度分析路線用時(shí)有時(shí)會(huì)有微小變動(dòng)，并且公汽和地鐵的票價(jià)也會(huì)隨著政策的不同而

47、改變，所以對(duì)這兩方面可能產(chǎn)生的波動(dòng)進(jìn)行討論就顯得十分必要。6.1.1 時(shí)間的波動(dòng)與公汽和地鐵行駛相關(guān)的時(shí)間有兩個(gè)，分別是相鄰兩站間的平均行駛時(shí)間和換乘車(chē)輛所需時(shí)間，由于最優(yōu)路線的選擇與這兩個(gè)時(shí)間的比值相關(guān)，不妨固定相鄰兩站間公交車(chē)和地鐵的平均行駛時(shí)間，變動(dòng)換乘時(shí)間，研究它對(duì)最優(yōu)路線的影響。1、以S0138到S0485為例，首先固定公交車(chē)和地鐵的兩站間的平均行駛時(shí)間，研究公汽換公汽的時(shí)間對(duì)最優(yōu)路線的影響。 圖12 最優(yōu)路線花費(fèi)時(shí)間與公汽換公汽時(shí)間關(guān)系圖從圖12 中可以看出，公汽換公汽的時(shí)間對(duì)最優(yōu)路線的影響非常大，當(dāng)公汽換公汽的時(shí)間多于6分鐘時(shí)，最優(yōu)策略就會(huì)發(fā)生改變。因此，此時(shí)應(yīng)盡量選擇少換車(chē)的方

48、案，以減小換車(chē)時(shí)的等待造成的時(shí)間開(kāi)銷(xiāo)。2、仍以S0138到S0485為例，固定公汽換公汽的時(shí)間，研究公汽和地鐵的兩站間的平均行駛時(shí)間對(duì)最優(yōu)路線的影響圖13 最優(yōu)路線花費(fèi)的總時(shí)間與公汽行駛時(shí)間與地鐵行駛時(shí)間比的關(guān)系圖 從圖13中可以看到，比值在0.8附近就對(duì)最優(yōu)乘車(chē)路線產(chǎn)生了影響，為了避免這樣的影響，建議出行時(shí)盡量選擇兩站間行駛時(shí)間比較穩(wěn)定的地鐵以減少行駛時(shí)間的變動(dòng)造成的影響。6.1.2 價(jià)格的變動(dòng)分析可知價(jià)格的變動(dòng)對(duì)偏重時(shí)間的最優(yōu)路線沒(méi)有影響，以下討論它對(duì)偏重價(jià)格的最優(yōu)路線的影響。不妨固定公汽的價(jià)格，討論地鐵價(jià)格的變化對(duì)偏重價(jià)格路線的影響，以地鐵價(jià)格下降為2元/次為例。地鐵價(jià)格變動(dòng)之前，地鐵與公汽價(jià)格比為3，相當(dāng)于坐一次地鐵的錢(qián)可以坐3次公汽，這對(duì)于偏重出行費(fèi)用的乘客來(lái)說(shuō)，他們一般不會(huì)坐地鐵。通過(guò)統(tǒng)計(jì)可知，與地鐵站相鄰的共117個(gè)站點(diǎn)間共13689條線路均可通過(guò)不超過(guò)2次換乘到達(dá)，具體乘車(chē)次數(shù)見(jiàn)下圖：圖14 地鐵