最優(yōu)公交線路的模型研究

1、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è)置

2、報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?北京化工大學(xué) 參賽隊員 (打印并簽名) ：1. 鄭宇 2. 姜園博 3. 來斯惟 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 郭秋敏 日期： 2007 年 09 月 24 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：最優(yōu)公交線路的模型研究摘要本文以乘車的路線為研究對象，根據(jù)乘客的不同需求，存在總時間、總費用、

3、換乘次數(shù)三個目標(biāo)函數(shù)。將求解目標(biāo)函數(shù)最優(yōu)值的問題轉(zhuǎn)化為最短路徑問題。在僅考慮公汽線路的時間最短模型中，首先由已知信息建立有向賦權(quán)圖，以公交站點為頂點，所有直通公交線路為邊。對于時間，每條邊的權(quán)值為公交車的運行時間加上轉(zhuǎn)車時間。然后可直接采用Dijkstra算法求出任意兩公汽站點之間最優(yōu)線路。該模型方法比較簡單，準(zhǔn)確性高，可操作性強。且對圖中的權(quán)值做相應(yīng)的改變，可以將其轉(zhuǎn)化為總費用最少模型以及換乘次數(shù)最少模型。同時考慮公汽和地鐵線路，存在公汽與地鐵的換乘問題，基于該問題本文設(shè)計了另一種有向賦權(quán)圖，以所有公汽站點和地鐵站點為頂點，所有直接連通線路為邊。以時間最短作為目標(biāo)，邊的權(quán)值設(shè)為兩點間實際運動

4、的時間。并相應(yīng)地提出一種修改的Dijkstra算法，在拼接兩條鄰邊時，會加上換乘時間。根據(jù)這種算法可得到任意兩公交站點之間的較優(yōu)線路，該算法效率較高。但在求解中發(fā)現(xiàn)，該方法并不能總求得最優(yōu)解，因為到某一站點的最短路不僅僅由其前面的一個站點的最短路決定?；谶@個問題，本文采用雙層Dijkstra算法，在該算法中，考慮一站點對其以后兩站的最短路徑的影響。雙層Dijkstra算法復(fù)雜度較高，但運用該算法可以得到更優(yōu)化的線路。統(tǒng)計結(jié)果表明，修改的Dijkstra算法求得的最優(yōu)解中，有5.7%的解可以被雙層Dijkstra算法的最優(yōu)解更新。類似的，雙層Dijkstra算法也可以求解總費用最少模型和換乘次

5、數(shù)最少模型。僅考慮公汽線路，6對站(1)S3359S1828 (2)S1557S0481 (3)S0971S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676的總時間最短的線路所對應(yīng)時間分別為64、99、103、59、102、46（分鐘）；總費用最少的線路所需費用分別為3、3、3、2、3、2（元）；總換乘次數(shù)最少的線路所需換乘次數(shù)分別為1、2、1、1、2、1（次）。同時考慮公汽和地鐵線路，本文求得6對起始站終到站的總時間最短的線路所需時間分別為62、99、95、53.5、86.5、30（分鐘）；總費用最少的線路所需費用分別為3、3、3、2、3、2（元）

6、；總換乘次數(shù)最少的線路所需換乘次數(shù)分別為1、2、1、1、2、0（次）。最后，本文對模型進(jìn)行了評價和推廣，使其能更好的應(yīng)用于實際生產(chǎn)生活中。關(guān)鍵詞雙層Dijkstra算法，最短路徑1. 問題分析1.1. 問題背景及分析奧運會即將來臨了，屆時有很多觀眾希望方便快捷的到達(dá)各個比賽場地，公交出行成為很多人的首選。北京市的公交線路已達(dá)800條以上，因此乘客面臨多條線路的選擇問題。本文的核心是提出一個解決公交線路選擇問題的方案。根據(jù)對實際情況的考慮并結(jié)合北京公交網(wǎng)和北京地鐵網(wǎng)提供的線路搜索需求，本文認(rèn)為查詢者的需求主要為總時間短、總費用低、換乘次數(shù)少。這三種需求對應(yīng)的三個目標(biāo)函數(shù)的最優(yōu)解的求解與最短路徑問

7、題相似?，F(xiàn)在如果把三個目標(biāo)函數(shù)的最優(yōu)解的求解轉(zhuǎn)化為最短路徑問題，就會遇到以下兩個問題：（1）同時考慮公汽線路和地鐵線路時，線路比較復(fù)雜，如何用已知的線路信息建立有向賦權(quán)圖（2）建立有向賦權(quán)圖之后，圖論中傳統(tǒng)的最短路徑算法是否適用。如果不適用，是否可以對傳統(tǒng)的最短路徑算法做相應(yīng)的改變，使其改變后可以求解已經(jīng)建立的有向賦權(quán)圖，或者是否可以提出新的算法用來求解已經(jīng)建立的有向賦權(quán)圖?；谶@兩個問題，考慮兩種解決辦法：（1）考慮簡單的公交線路，即只考慮公汽線路。根據(jù)已知公汽線路的信息建立有向賦權(quán)圖，使該有向賦權(quán)圖的最短路徑問題可以直接求解（2）同時考慮公汽線路和地鐵線路。首先，根據(jù)已知公交線路的信息建立

8、有向賦權(quán)圖，使得該有向賦權(quán)圖包含實際情況中的任意一種情形。其次，對傳統(tǒng)的最短路徑算法做改變使它可以求解已經(jīng)建立的有向賦權(quán)圖。1.2. 題中數(shù)據(jù)的兩個問題及修正除L290外，其余環(huán)行公交線路所標(biāo)的首站和末站均相同。而環(huán)行線L290的首站為S1477，末站為S1479。根據(jù)L066可知S1477和S1479為相鄰兩站，故認(rèn)為此線路的最后少標(biāo)了一個S1477，實際仍為環(huán)行線。普通線路L406的起點站和終點站相同，均為S1871。L406的第二站為S1008，倒數(shù)第二站為S0941，由L034可知，S1008和S0941相鄰，故認(rèn)為數(shù)據(jù)沒有問題。但是從實際情況看，這樣的線路會被當(dāng)作環(huán)線使用，而不會在S

9、1871讓乘客強制下車。所以我們把L406改成環(huán)線。2. 模型假設(shè)2.1. 總時間=乘客到達(dá)最后一個公汽站的時刻乘客離開第一個公汽站的時刻；2.2. 假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘(無需支付地鐵費)；2.3. 換乘交通工具所用時間分為等待時間和步行到站點時間兩部分.(題目中給出了換乘中的步行時間)；2.4. 環(huán)線地鐵和公汽的線路都是雙向的3. 符號說明第k條公汽線路（站點相同運行方向不同的公汽線路用不同的k表示）第k條地鐵線路（k=1, 2, 3, 4；站點相同運行方向不同的地鐵線路用不同的k表示）第k條公汽線路上公汽站的個數(shù)第k條地鐵線路上地鐵站的個數(shù)標(biāo)號為i的公汽

10、站標(biāo)號為i的地鐵站 和確定的邊對應(yīng)的權(quán)和確定的邊對應(yīng)的權(quán)和確定的邊對應(yīng)的權(quán)換乘系數(shù)4. 模型的建立與求解4.1. 僅考慮公汽線路的模型4.1.1. 建立有向賦權(quán)圖1) 總時間為目標(biāo)函數(shù)對于任意一條公汽線路，有個站，以這個站為頂點。對于這個頂點中的任意兩個頂點和，以和為端點的線段為邊，公汽的運行方向為邊的方向。記，則和確定的邊對應(yīng)的權(quán)= 相鄰公汽站平均行駛時間+公汽換乘公汽平均耗時。這樣就建立了僅包含一條公汽線路的有向賦權(quán)圖，對每一條公汽線路都按以上方法建立有向賦權(quán)圖，就得到包含所有公汽線路的有向賦權(quán)圖。由于在權(quán)值中加入了公汽的換乘時間，因此所有的邊都具有可加性。此時，只要得到有向圖中兩頂點A

11、、B間的最短路徑，就可以得到乘客從公汽站A到公汽站B的最短時間。2) 總費用為目標(biāo)函數(shù)頂點和邊的選取與1）相同，和確定的邊對應(yīng)的權(quán)為該公交線所需的車票費用，即：3) 換乘次數(shù)為目標(biāo)函數(shù)頂點和邊的選取與1）相同，和確定的邊對應(yīng)的權(quán)。4.1.2. 模型求解在已經(jīng)建立的有向賦權(quán)圖中，需要求出任意兩頂點間的最短路徑。Dijkstra算法可以解決有向賦權(quán)圖的最短路徑問題，該算法要求所有邊的權(quán)值非負(fù)，4.1.1建立的有向賦權(quán)圖顯然滿足該算法的要求。以Dijkstra算法為基礎(chǔ)，編程求解4.1.1中有向賦權(quán)圖的最短路徑。1) 總時間最少的模型求解程序計算的得到的總時間比實際情況多了一次換乘時間，因此，最優(yōu)線

12、路的總時間=程序計算的得到的總時間-5分鐘。 起始站終到站最優(yōu)線路的總時間（分鐘）S3359S1828 時間： 64 花費：3 換乘：2S1557S0481 時間： 99 花費：4 換乘：3S0971S0485時間：103 花費：3 換乘：2S0008S0073時間： 59 花費：5 換乘：4S0148S0485時間：102 花費：4 換乘：3S0087S3676時間： 46 花費：3 換乘：22) 總費用最少的模型求解起始站終到站最優(yōu)線路的總費用（元）S3359S1828 時間：145 花費：3 換乘：2S1557S0481 時間：115 花費：3 換乘：2S0971S0485時間：149

13、花費：3 換乘：1S0008S0073時間： 83 花費：2 換乘：1S0148S0485時間：124 花費：3 換乘：2S0087S3676時間： 71 花費：2 換乘：13) 換乘次數(shù)最少的模型求解起始站終到站最優(yōu)線路的換乘次數(shù)（次）S3359S1828 時間：137 花費：3 換乘：1S1557S0481 時間：178 花費：4 換乘：2S0971S0485時間：260 花費：5 換乘：1S0008S0073時間：116 花費：3 換乘：1S0148S0485時間：196 花費：4 換乘：2S0087S3676時間： 71 花費：2 換乘：14.2. 考慮公汽和地鐵線路的時間最短模型4.

14、2.1. 建立有向賦權(quán)圖對于公汽線路的建圖同4.1。類似的，對于任意一條地鐵線路，有個站，以這個站為頂點。對于這個頂點中的任意兩個頂點和，定義以和為端點的線段是一條邊，地鐵的運行方向為邊的方向。和確定的邊對應(yīng)的權(quán)=(上和之間的站點個數(shù)(包括和) -1)相鄰地鐵站平均行駛時間。對于任意一個地鐵站，都存在1至5個可供換乘的公汽站（例如地鐵站D01存在3個可供換乘的公汽站S0567，S0042，S0025）。建立以和為頂點的雙向邊，其權(quán)值，即步行時間4分鐘。根據(jù)以上三步可以建立包含所有公汽線路和地鐵線路的有向賦權(quán)圖，但該賦權(quán)圖還沒有考慮換乘時間。下面考慮每一種換乘情況，共有8種換乘情況。0代表地鐵站

15、，1代表公汽站，A表示乘地鐵，B表示乘公汽，C表示步行。那么0 0 0 ，0 0 1，0 1 0，0 1 1，1 0 0，1 0 1，1 1 0，1 1 1分別表示： 地鐵站地鐵站地鐵站地鐵間換乘時間：4分鐘地鐵站地鐵站公汽站無換乘時間地鐵站公汽站地鐵站無換乘時間地鐵站公汽站公汽站等待公汽的時間：3分鐘公汽站地鐵站地鐵站等待地鐵的時間：2分鐘公汽站地鐵站公汽站無換乘時間公汽站公汽站地鐵站無換乘時間公汽站公汽站公汽站公汽間換乘時間：4分鐘將這8種情況下在換乘所需的時間定義為換成系數(shù)（p,q,r的取值為0或1），則, , , , , , , 令所有的公汽站構(gòu)成的集合為S, 所有的地鐵站構(gòu)成的集合為

16、D, V=SD,用表示V中的頂點。令所有的構(gòu)成的集合為，所有的構(gòu)成的集合為，所有的構(gòu)成的集合為，W=，E=W所對應(yīng)的各邊。這樣就得到了有向賦權(quán)圖G(V,E,W)。4.2.2. 運用修改的Dijkstra算法求解模型1) 修改的Dijkstra算法在4.2.1建立的有向賦權(quán)圖中，每一個頂點有換乘系數(shù)，顯然此時不可以直接運用Dijkstra算法求最短路徑?；贒ijkstra算法的基本思想，本文提出一種修改的Dijkstra算法，用于求該有向賦權(quán)圖中頂點到頂點的最短路徑。Dijkstra算法的基本思想是：將點集V分成兩部分，一部分是頂點具有p標(biāo)號（永久性標(biāo)號）的集合P, 另一部分是頂點具有t標(biāo)號（

17、臨時性標(biāo)號）的集合T，并首先至 具有p標(biāo)號，而其余頂點具有t標(biāo)號，然后逐步將具有t標(biāo)號的頂點置為p標(biāo)號。當(dāng) 具有p標(biāo)號時，就找到了頂點到頂點 的最短路徑。所謂頂點的p標(biāo)號是指從到的最短路徑的長度，頂點的p標(biāo)號是指從到的最短路徑的長度。頂點的標(biāo)號用表示。Dijkstra算法描述如下：（1）初始化。設(shè)具有p標(biāo)號，=0，P=, T=V-P, 且的t標(biāo)號是：（2）求下一個頂點的p標(biāo)號。設(shè)頂點的t標(biāo)號是T中所有頂點t標(biāo)號的最小值。將的t標(biāo)號改為p標(biāo)號，修改永久性標(biāo)號集P和臨時性標(biāo)號集T，使，。（3）修改T中各頂點的t標(biāo)號值。對任意的（4）重復(fù)步驟（2）和（3），直到獲p標(biāo)號。為了適應(yīng)中間的換乘時間，將原

18、Dijkstra算法的第（3）步改為：對任意的，其中，換乘系數(shù)的取值為4.2.1中8種換乘情況之一。為到的最短路徑（實際上只是原Dijkstra算法中的最短路徑，修改后并非最短）上，的上一級頂點。2) 模型求解以1)中修改的Dijkstra算法為基礎(chǔ)編程，求4.2.1中建立的有向賦權(quán)圖中任意兩頂點的最短路徑。計算結(jié)果如下（具體路線間附錄）：起始站終到站最優(yōu)線路的總時間（分鐘）S3359S1828 時間:62 花費:7 換乘:4S1557S0481 時間:99 花費:4 換乘:3S0971S0485時間:95 花費:6 換乘:3S0008S0073時間:53.5 花費:5 換乘:3S0148S0

19、485時間:86.5 花費:6 換乘:3S0087S3676時間:30 花費:3 換乘:04.2.3. 運用雙層Dijkstra算法求解模型圖12.51247.5443上文4.2.2中的修改的Dijkstra算法雖然具有和原始Dijkstra算法相同的時空復(fù)雜度，計算效率很高，但并不是總能算得最短路徑。如圖1所示的公交線路圖（此圖僅作示例，并非從實際數(shù)據(jù)中獲得），1、2、4號頂點為地鐵站，3號頂點為公汽站，12線上另有2個地鐵站，故12線所需時間為7.5分鐘，2為地鐵換乘點，24線的時間為2.5分鐘。3號公交站同時連接1號和2號地鐵站（如數(shù)據(jù)中S0540同時連接了D17和D31），兩條邊的權(quán)值

20、均為4分鐘。下面我們用修改的Dijkstra算法來計算這個問題。第一步：L(1)=0第二步：由1號頂點出發(fā)更新其它頂點，L(3)=4，L(2)=7.5第三步：由3號頂點出發(fā)更新其它頂點，L(2)=min7.5, L(3)+4+=7.5第四步：由2號頂點出發(fā)更新其它頂點，L(4)=L(2)+2.5+=14。因為2號頂點由1號頂點擴展而來，所以是。實際上，如果走1324的路線距離反而更短。L=4+4+2.5=12.5這種修改的Dijkstra算法不能總能算得最短路徑的原因在于我們加了這一項，其中的p為q的前一個頂點。這就說明頂點p可以影響之后的兩層頂點，而Dijkstra算法每次只掃描并修改了一層

21、頂點。從這一原因出發(fā)，我們考慮把算法設(shè)計為“雙層Dijkstra算法”。在雙層Dijkstra算法中，每次掃描頂點均嘗試更新直接相鄰的頂點和與直接相鄰的頂點相鄰的頂點。即將原Dijkstra算法的第（3）步改為：對任意的，i, j, k互不相等，用雙層Dijkstra算法計算得到六條線路的最少時間與4.2.2中修改的Dijkstra算法相同，但在之后的模型評價中可以看出雙層Dijkstra算法還是很有優(yōu)勢的。4.3. 考慮公汽和地鐵線路的費用最少模型以及換乘次數(shù)最少模型1) 建立有向賦權(quán)圖該模型的有向賦權(quán)圖類似4.2.1的有向賦權(quán)圖，頂點和邊的設(shè)置與4.2.1完全相同，權(quán)值的設(shè)置、換乘系數(shù)的設(shè)

22、置與4.2.1不同。對于公汽線路的有向賦權(quán)圖，和確定的邊對應(yīng)的權(quán)為該公交線所需的車票費用，即：對于任意一條地鐵線路，和確定的邊對應(yīng)的權(quán)，地鐵票價。對于任意一個地鐵站，都存在1至5個可供換乘的公汽站，建立以和為頂點的雙向邊，其權(quán)值=0。因為沒有乘坐交通工具。換乘系數(shù)的設(shè)置：, , , , , , , 。因為 地鐵站地鐵站地鐵站（A表示乘地鐵）多收了一次地鐵票價。2) 運用雙層Dijkstra算法求解模型用雙層Dijkstra算法計算得到六條線路的最少費用，結(jié)果如下（具體路線間附錄）：起始站終到站最優(yōu)線路的總費用（元）S3359S1828 時間:137 花費:3 換乘:1S1557S0481 時間

23、:160 花費:3 換乘:2S0971S0485時間:149 花費:3 換乘:1S0008S0073時間:83 花費:2 換乘:1S0148S0485時間:121 花費:3 換乘:2S0087S3676時間:71 花費:2 換乘:14.4. 考慮公汽和地鐵線路的換乘次數(shù)最少模型1) 建立有向賦權(quán)圖公汽線路的有向賦權(quán)圖同4.1.1的3)。對于任意一條地鐵線路，有個站，以這個站為頂點。對于這個頂點中的任意兩個頂點和，定義以和為端點的線段是一條邊，地鐵的運行方向為邊的方向。和確定的邊對應(yīng)的權(quán)=1。對于任意一個地鐵站，都存在1至5個可供換乘的公汽站，建立以和為頂點的雙向邊，其權(quán)值=0。因為沒有乘坐交通

24、工具。2) 運用Dijkstra算法求解模型用Dijkstra算法計算得到六條線路的最少換乘次數(shù)，結(jié)果如下（具體路線見附錄）：起始站終到站最優(yōu)線路的總費用（元）S3359S1828 時間:132 花費:3 換乘:1S1557S0481 時間:166 花費:3 換乘:2S0971S0485時間:260 花費:5 換乘:1S0008S0073時間:116 花費:3 換乘:1S0148S0485時間:196 花費:4 換乘:2S0087S3676時間:30 花費:3 換乘:04.5. 已知行走時間的最佳路線考慮了步行時間，換乘次數(shù)、票價這兩個目標(biāo)將失去意義，因為查詢者會選擇走完全程，以獲得換乘次數(shù)為

25、0，且沒有票價的“最優(yōu)路線”。因此我們只需要分析時間這一目標(biāo)。在4.2的基礎(chǔ)上，我們可以得到任兩點間乘坐公交的最短路線。建立圖G1，頂點為所有公交站點，邊權(quán)值為各頂點間通過公交線到達(dá)的最短時間。我們已知了任兩點間的步行時間，故可用最短路徑算法直接求得任意兩點間的最少步行時間。建立圖G2，頂點為所有公交站點，邊權(quán)值為各頂點間通過步行到達(dá)的最短時間。因為G1和G2的所有邊已是各自的最短路徑，所以G1或是G2中任意兩條屬于同一個圖的邊的拼接只會讓路徑更長。我們只需考慮輪換拼接G1和G2中的邊。G1邊接G2邊：公交車之后步行，兩條邊可以直接拼接。G2邊接G1邊：步行之后乘坐公交車，可能需要在此處加入公

26、汽或地鐵的等待時間。具體要看這條公交邊中最開頭的兩站。我們發(fā)現(xiàn)這里和之前4.2.3中建立雙層Dijkstra算法時遇到的情形是一樣的，在拼接兩條邊時需要加上換乘系數(shù)，每個頂點會對之后兩層頂點產(chǎn)生影響。與4.2.3不同的是，要拼接的邊不在同一張圖中。我們假設(shè)第一條邊來自G1，對于奇數(shù)號頂點，采用以下兩個公式代替4.2.3中的公式對于偶數(shù)號頂點，把上述公式的W1和W2互換即可。然后再假設(shè)第一條邊來自G2，用完全對應(yīng)的方法計算，最后取兩者的最小值即可。5. 模型評價及改進(jìn)5.1. 模型評價1）本文根據(jù)乘客的不同需求，提出三個目標(biāo)函數(shù)（總時間最短、總費用最少、換乘次數(shù)最少），并求出三個目標(biāo)函數(shù)在僅考慮

27、公汽線路時的最優(yōu)解，以及目標(biāo)函數(shù)在同時考慮公汽線路和地鐵線路時的最優(yōu)解。因此本文所建的模型可以滿足乘客的不同需求。但是，本文并沒有提出一個綜合考慮乘客3種需求的模型。2）在模型4.1中，采用Dijkstra算法求出任意兩公汽站點之間最優(yōu)線路。該模型方法比較簡單，準(zhǔn)確性高，可操作性強。但該算法只能解決公交線路比較簡單的情況，具有它的局限性。 3）雙層Dijkstra算法與修改的Dijkstra算法的比較為了說明雙層Dijkstra算法較修改的Dijkstra算法的優(yōu)點，枚舉了3996個站點（其中3957個公汽站點和39個地鐵站點）的兩兩組合，一共= 7982010種查詢。對于每一個查詢，分別用兩

28、種算法計算，并加以比較，發(fā)現(xiàn)雙層Dijkstra算法在其中的458681條查詢更優(yōu)，其余的計算結(jié)果相同。兩種算法最多會相差3.5分鐘。如S1914S3060，用修改的Dijkstra算法算得最少時間為42分鐘，用雙層Dijkstra算得最少時間為38.5分鐘。具體路線見附錄。把所有相差的時間平均分散到所有查詢中，每條線路多用4.5秒。修改的Dijkstra算法效率較高，但不是總能獲得時間最少的解。從分析中看，該算法在94.3%情況下適用。在其不適用的5.7%中，最大誤差也僅為3.5分鐘，這已是一種十分實用的近似算法。雙層Dijkstra算法能獲得最短路徑，但效率相對降低，大約比修改的Dijks

29、tra算法慢40倍。從實際應(yīng)用來看，該公司可以將所有路徑計算好，待查詢者查詢時，直接查表即可。4）雙層Dijkstra算法可以得到非常好的結(jié)果，但是本文無法給出嚴(yán)格的證明。5.2. 模型改進(jìn)1）單一目標(biāo)函數(shù)能找到使其目標(biāo)函數(shù)達(dá)到很好，但并不一定實用的路線?？煽紤]多個目標(biāo)函數(shù)加權(quán)作為權(quán)值以獲得更實用的路線。參考文獻(xiàn)1(美)科曼(Cormen, T.H.)等著；潘金貴等譯，算法導(dǎo)論，北京：機械工業(yè)出版社，2006。附錄附1：只考慮公汽的最佳路線詳細(xì)換乘表（公交線路后的括號內(nèi)的兩個數(shù)據(jù)分別為車票花費和時間）最少時間S3359S1828S1557S0481時間：64 花費：3 換乘：2S3359S29

30、03 乘 L474(1, 8), L436(1, 8), L366(1, 8), L352(1, 8), L132(1, 8), L123(1, 8), L015(1, 8)S2903S1784 乘 L485(1, 53), L485(1, 53)S1784S1828 乘 L217(1, 8), L167(1, 8)時間：99 花費：4 換乘：3S1557S1919 乘 L363(1, 41), L084(1, 41)S1919S3186 乘 L189(1, 14)S3186S0902 乘 L317(1, 35), L091(1, 35)S0902S0481 乘 L516(1, 14), L4

31、60(1, 14), L447(1, 14), L312(1, 14), L254(1, 14)S0971S0485S0008S0073時間：103 花費：3 換乘：2S0971S2517 乘 L013(1, 53)S2517S2159 乘 L290(1, 44), L290(1, 44)S2159S0485 乘 L469(1, 11)時間：59 花費：5 換乘：4S0008S1691 乘 L198(1, 11)S1691S2085 乘 L476(1, 20)S2085S0609 乘 L406(1, 8), L406(1, 8), L017(1, 8), L017(1, 8)S0609S052

32、5 乘 L328(1, 14)S0525S0073 乘 L103(1, 11)S01480485S00873676時間：102 花費：4 換乘：3S0148S3604 乘 L308(1, 50)S3604S2361 乘 L354(1, 11), L123(1, 11), L081(1, 11)S2361S2210 乘 L156(1, 32)S2210S0485 乘 L417(1, 14)時間：46 花費：3 換乘：2S0087S0088 乘 L454(1, 8), L206(1, 8), L021(1, 8)S0088S0427 乘 L381(1, 35), L231(1, 35), L231

33、(1, 35)S0427S3676 乘 L462(1, 8), L097(1, 8)最少換乘次數(shù)最小花費S3359 S1828時間：137 花費：3 換乘：1S3359S0304 乘 L469(2, 92)S0304S1828 乘 L217(1, 50)時間：145 花費：3 換乘：2S3359S0772 乘 L469(1, 47)S0772S0096 乘 L204(1, 65)S0096S1828 乘 L167(1, 38)S1557 S0481時間：178 花費：4 換乘：2S1557S0051 乘 L363(1, 38), L084(1, 38)S0051S0273 乘 L384(1,

34、65)S0273S0481 乘 L460(2, 80)時間：115 花費：3 換乘：2S1557S1919 乘 L363(1, 41), L084(1, 41)S1919S0902 乘 L417(1, 65)S0902S0481 乘 L516(1, 14), L460(1, 14), L447(1, 14),L312(1, 14), L254(1, 14)S0971 S0485時間：260 花費：5 換乘：1S0971S0354 乘 L119(2, 80)S0354S0485 乘 L377(3, 185)時間：149 花費：3 換乘：1S0971S0872 乘 L119(1, 56)S0872

35、S0485 乘 L417(2, 98)S0008 S0073時間：116 花費：3 換乘：1S0008S0181 乘 L259(1, 44)S0181S0073 乘 L058(2, 77)時間：83 花費：2 換乘：1S0008S0291 乘 L159(1, 59)S0291S0073 乘 L058(1, 29)S0148 S0485時間：196 花費：4 換乘：2S0148S0302 乘 L308(1, 20)S0302S0029 乘 L348(2, 119)S0029S0485 乘 L051(1, 62)時間：124 花費：3 換乘：2S0148S3604 乘 L308(1, 50)S36

36、04S0248 乘 L021(1, 20)S0248S0485 乘 L469(1, 59)S0087 S3676時間：71 花費：2 換乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)時間：71 花費：2 換乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)附2：考慮公汽和地鐵的最佳路線詳細(xì)換乘表（公交線路后的括號內(nèi)的兩個數(shù)據(jù)分別為車票花費和時間）最少時間S3359S1828S1557S0481時間：62 花費：7 換乘：4S3359S2903 乘 L474(1, 3), L436(1,

37、3), L366(1, 3), L352(1, 3), L132(1, 3), L123(1, 3), L015(1, 3)公汽換乘公汽(0, 5)S2903S0609 乘 L201(1, 12)S0609D12 步行(0, 4)等待地鐵(0, 2)D12D37 乘 T2(3, 15)D37S1961 步行(0, 4)等待公汽(0, 3)S1961S1671 乘 L428(1, 6)公汽換乘公汽(0, 5)S1671S1828 乘 L041(1, 3)時間：99 花費：4 換乘：3S1557S1919 乘 L363(1, 36), L084(1, 36)公汽換乘公汽(0, 5)S1919S31

38、86 乘 L189(1, 9)公汽換乘公汽(0, 5)S3186S0902 乘 L317(1, 30), L091(1, 30)公汽換乘公汽(0, 5)S0902S0481 乘 L516(1, 9), L460(1, 9), L447(1, 9), L312(1, 9), L254(1, 9)S0971S0485S0008S0073時間：95 花費：6 換乘：3S0971S0567 乘 L119(1, 18), L094(1, 18)S0567D01 步行(0, 4)等待地鐵(0, 2)D01D15 乘 T1(3, 35)D15S2534 步行(0, 4)等待公汽(0, 3)S2534S221

39、0 乘 L156(1, 15)公汽換乘公汽(0, 5)S2210S0485 乘 L417(1, 9)時間：53.5 花費：5 換乘：3S0008S2534 乘 L200(1, 18)S2534D15 步行(0, 4)等待地鐵(0, 2)D15D12 乘 T1(3, 7.5)地鐵換乘地鐵(0, 4)D12D25 乘 T2(0, 5)D25S0525 步行(0, 4)等待公汽(0, 3)S0525S0073 乘 L103(1, 6)S0148S0485S0087S3676時間：86.5 花費：6 換乘：3S0148S1487 乘 L024(1, 12)S1487D02 步行(0, 4)等待地鐵(0

40、, 2)D02D15 乘 T1(3, 32.5)D15S2534 步行(0, 4)等待公汽(0, 3)S2534S2210 乘 L156(1, 15)公汽換乘公汽(0, 5)S2210S0485 乘 L417(1, 9)時間：30 花費：3 換乘：0S0087D27 步行(0, 4)等待地鐵(0, 2)D27D36 乘 T2(3, 20)D36S3676 步行(0, 4)最少換乘最少花費S3359 S1828時間：132 花費：3 換乘：1S3359S0304 乘 L469(2, 87)公汽換乘公汽(0, 5)S0304S1828 乘 L217(1, 45)時間：137 花費：3 換乘：1S3359S0304 乘 L469(2, 87)公汽換乘公汽(0, 5)S0304S1828 乘 L217(1, 45)S