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

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

2、報(bào)名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?北京化工大學(xué) 參賽隊(duì)員 (打印并簽名) ：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ū)評閱時(shí)使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：最優(yōu)公交線路的模型研究摘要本文以乘車的路線為研究對象，根據(jù)乘客的不同需求，存在總時(shí)間、總費(fèi)用、

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

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

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

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

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

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

9、1871讓乘客強(qiáng)制下車。所以我們把L406改成環(huán)線。2. 模型假設(shè)2.1. 總時(shí)間=乘客到達(dá)最后一個(gè)公汽站的時(shí)刻乘客離開第一個(gè)公汽站的時(shí)刻；2.2. 假設(shè)同一地鐵站對應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘(無需支付地鐵費(fèi))；2.3. 換乘交通工具所用時(shí)間分為等待時(shí)間和步行到站點(diǎn)時(shí)間兩部分.(題目中給出了換乘中的步行時(shí)間)；2.4. 環(huán)線地鐵和公汽的線路都是雙向的3. 符號說明第k條公汽線路（站點(diǎn)相同運(yùn)行方向不同的公汽線路用不同的k表示）第k條地鐵線路（k=1, 2, 3, 4；站點(diǎn)相同運(yùn)行方向不同的地鐵線路用不同的k表示）第k條公汽線路上公汽站的個(gè)數(shù)第k條地鐵線路上地鐵站的個(gè)數(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) 總時(shí)間為目標(biāo)函數(shù)對于任意一條公汽線路，有個(gè)站，以這個(gè)站為頂點(diǎn)。對于這個(gè)頂點(diǎn)中的任意兩個(gè)頂點(diǎn)和，以和為端點(diǎn)的線段為邊，公汽的運(yùn)行方向?yàn)檫叺姆较颉Ｓ洠瑒t和確定的邊對應(yīng)的權(quán)= 相鄰公汽站平均行駛時(shí)間+公汽換乘公汽平均耗時(shí)。這樣就建立了僅包含一條公汽線路的有向賦權(quán)圖，對每一條公汽線路都按以上方法建立有向賦權(quán)圖，就得到包含所有公汽線路的有向賦權(quán)圖。由于在權(quán)值中加入了公汽的換乘時(shí)間，因此所有的邊都具有可加性。此時(shí)，只要得到有向圖中兩頂點(diǎn)A

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

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

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

14、2.1. 建立有向賦權(quán)圖對于公汽線路的建圖同4.1。類似的，對于任意一條地鐵線路，有個(gè)站，以這個(gè)站為頂點(diǎn)。對于這個(gè)頂點(diǎn)中的任意兩個(gè)頂點(diǎn)和，定義以和為端點(diǎn)的線段是一條邊，地鐵的運(yùn)行方向?yàn)檫叺姆较?。和確定的邊對應(yīng)的權(quán)=(上和之間的站點(diǎn)個(gè)數(shù)(包括和) -1)相鄰地鐵站平均行駛時(shí)間。對于任意一個(gè)地鐵站，都存在1至5個(gè)可供換乘的公汽站（例如地鐵站D01存在3個(gè)可供換乘的公汽站S0567，S0042，S0025）。建立以和為頂點(diǎn)的雙向邊，其權(quán)值，即步行時(shí)間4分鐘。根據(jù)以上三步可以建立包含所有公汽線路和地鐵線路的有向賦權(quán)圖，但該賦權(quán)圖還沒有考慮換乘時(shí)間。下面考慮每一種換乘情況，共有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分別表示： 地鐵站地鐵站地鐵站地鐵間換乘時(shí)間：4分鐘地鐵站地鐵站公汽站無換乘時(shí)間地鐵站公汽站地鐵站無換乘時(shí)間地鐵站公汽站公汽站等待公汽的時(shí)間：3分鐘公汽站地鐵站地鐵站等待地鐵的時(shí)間：2分鐘公汽站地鐵站公汽站無換乘時(shí)間公汽站公汽站地鐵站無換乘時(shí)間公汽站公汽站公汽站公汽間換乘時(shí)間：4分鐘將這8種情況下在換乘所需的時(shí)間定義為換成系數(shù)（p,q,r的取值為0或1），則, , , , , , , 令所有的公汽站構(gòu)成的集合為S, 所有的地鐵站構(gòu)成的集合為

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

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

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

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

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

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

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

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

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

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

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

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

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

29、tra算法慢40倍。從實(shí)際應(yīng)用來看，該公司可以將所有路徑計(jì)算好，待查詢者查詢時(shí)，直接查表即可。4）雙層Dijkstra算法可以得到非常好的結(jié)果，但是本文無法給出嚴(yán)格的證明。5.2. 模型改進(jìn)1）單一目標(biāo)函數(shù)能找到使其目標(biāo)函數(shù)達(dá)到很好，但并不一定實(shí)用的路線?？煽紤]多個(gè)目標(biāo)函數(shù)加權(quán)作為權(quán)值以獲得更實(shí)用的路線。參考文獻(xiàn)1(美)科曼(Cormen, T.H.)等著；潘金貴等譯，算法導(dǎo)論，北京：機(jī)械工業(yè)出版社，2006。附錄附1：只考慮公汽的最佳路線詳細(xì)換乘表（公交線路后的括號內(nèi)的兩個(gè)數(shù)據(jù)分別為車票花費(fèi)和時(shí)間）最少時(shí)間S3359S1828S1557S0481時(shí)間：64 花費(fèi)：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)時(shí)間：99 花費(fèi)：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時(shí)間：103 花費(fèi)：3 換乘：2S0971S2517 乘 L013(1, 53)S2517S2159 乘 L290(1, 44), L290(1, 44)S2159S0485 乘 L469(1, 11)時(shí)間：59 花費(fèi)：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時(shí)間：102 花費(fèi)：4 換乘：3S0148S3604 乘 L308(1, 50)S3604S2361 乘 L354(1, 11), L123(1, 11), L081(1, 11)S2361S2210 乘 L156(1, 32)S2210S0485 乘 L417(1, 14)時(shí)間：46 花費(fèi)：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ù)最小花費(fèi)S3359 S1828時(shí)間：137 花費(fèi)：3 換乘：1S3359S0304 乘 L469(2, 92)S0304S1828 乘 L217(1, 50)時(shí)間：145 花費(fèi)：3 換乘：2S3359S0772 乘 L469(1, 47)S0772S0096 乘 L204(1, 65)S0096S1828 乘 L167(1, 38)S1557 S0481時(shí)間：178 花費(fèi)：4 換乘：2S1557S0051 乘 L363(1, 38), L084(1, 38)S0051S0273 乘 L384(1,

34、65)S0273S0481 乘 L460(2, 80)時(shí)間：115 花費(fèi)：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時(shí)間：260 花費(fèi)：5 換乘：1S0971S0354 乘 L119(2, 80)S0354S0485 乘 L377(3, 185)時(shí)間：149 花費(fèi)：3 換乘：1S0971S0872 乘 L119(1, 56)S0872

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

36、04S0248 乘 L021(1, 20)S0248S0485 乘 L469(1, 59)S0087 S3676時(shí)間：71 花費(fèi)：2 換乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)時(shí)間：71 花費(fèi)：2 換乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)附2：考慮公汽和地鐵的最佳路線詳細(xì)換乘表（公交線路后的括號內(nèi)的兩個(gè)數(shù)據(jù)分別為車票花費(fèi)和時(shí)間）最少時(shí)間S3359S1828S1557S0481時(shí)間：62 花費(fèi)：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)時(shí)間：99 花費(fèi)：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時(shí)間：95 花費(fèi)：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)時(shí)間：53.5 花費(fèi)：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時(shí)間：86.5 花費(fèi)：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)時(shí)間：30 花費(fèi)：3 換乘：0S0087D27 步行(0, 4)等待地鐵(0, 2)D27D36 乘 T2(3, 20)D36S3676 步行(0, 4)最少換乘最少花費(fèi)S3359 S1828時(shí)間：132 花費(fèi)：3 換乘：1S3359S0304 乘 L469(2, 87)公汽換乘公汽(0, 5)S0304S1828 乘 L217(1, 45)時(shí)間：137 花費(fèi)：3 換乘：1S3359S0304 乘 L469(2, 87)公汽換乘公汽(0, 5)S0304S1828 乘 L217(1, 45)S