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

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

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

5、ra 算法也可以求解總費用最少模型和換乘次數(shù)最少模型。僅考慮公汽線路，6 對站 S3354 S1828 （2）S1557 S0481（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（分鐘

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

7、的需求主要為總時間短、總費用低、換乘次數(shù)少。這三種需 求對應(yīng)的三個目標函數(shù)的最優(yōu)解的求解與最短路徑問題相似。 現(xiàn)在如果把三個目 標函數(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ù)已知公汽線路的信息 建立

8、有向賦權(quán)圖，使該有向賦權(quán)圖的最短路徑問題可以直接求解（2）同時考慮公汽線路和地鐵線路。首先，根據(jù)已知公交線路的信息建立 有向賦權(quán)圖， 使得該有向賦權(quán)圖包含實際情況中的任意一種情形。 其次，對傳統(tǒng) 的最短路徑算法做改變使它可以求解已經(jīng)建立的有向賦權(quán)圖。1.2. 題中數(shù)據(jù)的兩個問題及修正除 L290 外，其余環(huán)行公交線路所標的首站和末站均相同。而環(huán)行線 L290 的首站為S1477,末站為S1479。根據(jù)L066可知S1477和S1479為相鄰兩站， 故認為此線路的最后少標了一個 S1477,實際仍為環(huán)行線。普通線路L406的起點站和終點站相同，均為S1871oL406的第二站為S1008, 倒數(shù)

9、第二站為S0941，由L034可知，S1008和S0941相鄰，故認為數(shù)據(jù)沒有問 題。但是從實際情況看，這樣的線路會被當作環(huán)線使用，而不會在S1871讓乘客 強制下車。所以我們把L406改成環(huán)線。2. 模型假設(shè)2.1. 總時間 =乘客到達最后一個公汽站的時刻乘客離開第一個 公汽站的時刻；2.2. 假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站 換乘 （無需支付地鐵費 ）；2.3. 換乘交通工具所用時間分為等待時間和步行到站點時間兩部 分 .（題目中給出了換乘中的步行時間 ）；2.4. 環(huán)線地鐵和公汽的線路都是雙向的1623. 符號說明3.1. Lk第 k 條公汽線路（站點相同運行方向不同

10、的公汽線路用不同的 k 表示）32 Tk第k條地鐵線路（k=1,2, 3, 4 ;站點相同運行方向不同的地鐵線路用不同的 k 表示）3.3. mk 第k條公汽線路上公汽站的個數(shù)34 nk第k條地鐵線路上地鐵站的個數(shù)3.5. Si標號為 i 的公汽站3.6. Di標號為 i 的地鐵站3.7. ijSi 和 Sj 確定的邊對應(yīng)的權(quán)3.8. ijDi 和 Dj 確定的邊對應(yīng)的權(quán)3.9. ijDi 和 Sj 確定的邊對應(yīng)的權(quán)3.10. pqr 換乘系數(shù)4. 模型的建立與求解4.1. 僅考慮公汽線路的模型4.1.1. 建立有向賦權(quán)圖I. 總時間為目標函數(shù)對于任意一條公汽線路Lk，有mk個站，以這mk個站

11、為頂點。對于這mk個頂點中的任意兩個頂點 向為邊的方向。Si 和 Sj，以和Sj為端點的線段為邊，公汽的運行方記Xj Lk上S和Sj之間的站點個數(shù)（包括Sj和Sj） 1,則S和Sj確定的邊對應(yīng)的權(quán)ij= Xjj相鄰公汽站平均行駛時間+公汽換乘公汽平均耗時。這樣就建立了僅包含一條公汽線路的有向賦權(quán)圖，對每一條公汽線路Lk都按以上方法建立有向賦權(quán)圖，就得到包含所有公汽線路的有向賦權(quán)圖。 由于在權(quán)值中加入了公汽的 換乘時間，因此所有的邊都具有可加性。此時，只要得到有向圖中兩頂點A、B間的最短路徑，就可以得到乘客從公汽站 A到公汽站B的最短時間。II. 總費用為目標函數(shù)頂點和邊的選取與1）相同，Si和

12、Sj確定的邊對應(yīng)的權(quán)ij為該公交線所需 的車票費用，即：1 Lk為單一票價1 Lk為分段計價，0 Xjj 20ij 2 Lk為分段計價，20 Xjj 403 Lk為分段計價，40 XjjIII. 換乘次數(shù)為目標函數(shù)頂點和邊的選取與1）相同，Sj和Sj確定的邊對應(yīng)的權(quán)ij 1。4.1.2 .模型求解在已經(jīng)建立的有向賦權(quán)圖中，需要求出任意兩頂點間的最短路徑。Dijkstra算法可以解決有向賦權(quán)圖的最短路徑問題， 該算法要求所有邊的權(quán)值非負，4.1.1 建立的有向賦權(quán)圖顯然滿足該算法的要求。以Dijkstra算法為基礎(chǔ)，編程求解4.1.1中有向賦權(quán)圖的最短路徑。I.總時間最少的模型求解程序計算的得到

13、的總時間比實際情況多了一次換乘時間，因此, 最優(yōu)線路的總時間=程序計算的得到的總時間-5分鐘。起始站f終到站最優(yōu)線路的總時間（分鐘）S335X S1828時間：64 花費：3 換乘：2S1557 S0481時間99花費4換乘3S0971S0485時間103花費3換乘2S0008 S0073時間59花費5換乘4S0148 S0485時間102花費4換乘3:S0087 S3676時間46花費3換乘2II.總費用最少的模型求解起始站f終到站最優(yōu)線路的總費用（元）S335X S1828時間145花費：3換乘2S1557 S0481時間115花費：3換乘2S0971S0485時間149花費：3換乘1S0

14、008 S0073時間83花費：2換乘1S0148 S0485時間124花費：3換乘2S0087f S3676時間71花費：2換乘1III.換乘次數(shù)最少的模型求解起始站f終到站最優(yōu)線路的換乘次數(shù)（次）S3359f S1828時間：137花費：3換乘：1S1557f S0481時間：178花費：4換乘：2S0971f S0485時間：260花費：5換乘：1S0008f S0073時間：116花費：3換乘：1S0148f S0485時間：196花費：4換乘：2S0087f S3676時間：71花費：2換乘：142考慮公汽和地鐵線路的時間最短模型421.建立有向賦權(quán)圖對于公汽線路的建圖同4.1。類似

15、的，對于任意一條地鐵線路 Tk，有珈個站，以這珈個站為頂點。對于 這nk個頂點中的任意兩個頂點Di和Dj，定義以Di和Dj為端點的線段是一條邊， 地鐵的運行方向為邊的方向。Di和Dj確定的邊對應(yīng)的權(quán)ij =（上Dj和Dj之間的站點個數(shù)（包括Di和Dj） -1）相鄰地鐵站平均行駛時間。對于任意一個地鐵站Di，都存在1至5個可供換乘的公汽站Sj （例如地鐵站D01存在3個可供換乘的公汽站 S0567, S0042, S0025)。建立以Di和Sj為頂 點的雙向邊，其權(quán)值 ij 4 ，即步行時間 4分鐘。pqr (p,q,r的取值為0或根據(jù)以上三步可以建立包含所有公汽線路和地鐵線路的有向賦權(quán)圖, 但

16、該賦 權(quán)圖還沒有考慮換乘時間。下面考慮每一種換乘情況,共有 8 種換乘情況。 0 代 表地鐵站, 1 代表公汽站, A 表示乘地鐵, B 表示乘公汽, C 表示步行。那么 0 00 , 0 0 1, 0 1 0,0 1 1,1 0 0,1 0 1,1 1 0, 1 1 1 分別表示：地鐵站A地鐵站A地鐵站地鐵間換乘時間：4 分鐘地鐵站A地鐵站C公汽站無換乘時間地鐵站C公汽站C地鐵站無換乘時間地鐵站C公汽站B公汽站等待公汽的時間：3 分鐘公汽站C地鐵站A地鐵站等待地鐵的時間：2 分鐘公汽站C地鐵站C公汽站無換乘時間公汽站B公汽站C地鐵站無換乘時間公汽站B公汽站B公汽站公汽間換乘時間：4 分鐘將這

17、 8 種情況下在換乘所需的時間定義為換成系數(shù)1),則000 4001 0010 0011 3100 2101110 0111 5令所有的公汽站Si構(gòu)成的集合為S,所有的地鐵站Di構(gòu)成的集合為D,V=S D,用Vi表示V中的頂點。令所有的ij構(gòu)成的集合為，所有的ij構(gòu), E=W 所對應(yīng)的各成的集合為 ,所有的 ij 構(gòu)成的集合為 , W= 邊。這樣就得到了有向賦權(quán)圖 G(V,E,W)。4.2.2. 運用修改的 Dijkstra 算法求解模型I. 修改的 Dijkstra 算法在 4.2.1 建立的有向賦權(quán)圖中,每一個頂點有換乘系數(shù),顯然此時不可以直 接運用 Dijkstra 算法求最短路徑。基于

18、 Dijkstra 算法的基本思想,本文提出一種修改的Dijkstra算法，用于求該有向賦權(quán)圖中頂點 v到頂點Vn的最短路徑。Dijkstra 算法的基本思想是：將點集 V 分成兩部分，一部分是頂點具有 p 標 號（永久性標號）的集合 P, 另一部分是頂點具有 t 標號（臨時性標號）的集合 T， 并首先至Vl具有p標號，而其余頂點具有t標號，然后逐步將具有t標號的頂點置為p標號。當Vn具有p標號時，就找到了頂點Vl到頂點Vn的最短路徑。所 謂頂點Vi的p標號是指從vi到Vi的最短路徑的長度，頂點Vj的p標號是指從vi到vj的最短路徑的長度。頂點v 的標號用 L（v） 表示。Dijkstra 算

19、法描述如下：W(vi,vj) (v1,vj) EL(vj)標號是：（1）初始化。設(shè) Vl具有 p標號，L（Vi）=o，p=W, t=V-P,且Vj（Vj T）的 telse（2）求下一個頂點的p標號。設(shè)頂點Vi的t標號是T中所有頂點t標號的 最小值。將Vi的t標號改為p標號，修改永久性標號集P和臨時性標號集T,使 P P vi， T T vi 。，。3）修改 T 中各頂點的 t 標號值。對任意的vjL(vj) min L(vj),L(vi) W(vi,vj )（4）重復(fù)步驟（2）和（3），直到Vn獲p標號。 為了適應(yīng)中間的換乘時間，將原 Dijkstra 算法的第（ 3）步改為： 對任意的 v

20、j T， L（vj） min L（vj）,L（vi） W（vi,vj）f（vi）,vi,vj其中，換乘系數(shù) f（vi）,vi,vj 的取值為 4.2.1 中 8 種換乘情況之一。f（Vi）為vi到Vi的最短路徑（實際上只是原Dijkstra算法中的最短路徑，修改后并非最短）上， vi 的上一級頂點。II. 模型求解以 1）中修改的 Dijkstra 算法為基礎(chǔ)編程，求 4.2.1 中建立的有向賦權(quán)圖中任 意兩頂點的最短路徑。計算結(jié)果如下(具體路線間附錄)：起始站終到站最優(yōu)線路的總時間(分鐘)S3359 S1828時間62 花費:7換乘:4S1557 S0481時間99 花費:4換乘:3S097

21、1S0485時間95 花費:6換乘:3S0008 S0073時間53.5花費:5換乘:3S0148 S0485時間86.5花費:6換乘:3:S0087 S3676時間30 花費:3換乘:0運用雙層Dijkstra算法求解模型1、2、4號頂點為地鐵站，3號頂點為公汽站，1 2上文422中的修改的Dijkstra算法雖然 具有和原始Dijkstra算法相同的時空復(fù)雜度，計算效率很高，但并不 是總能算得最短路徑。如圖1所示的公交線路圖(此圖僅作示例， 并非從實際數(shù)據(jù)中獲得) 線上另有2個地鐵站，故1 2線所需時間為7.5分鐘，2為地鐵換乘點，24 線的時間為2.5分鐘。3號公交站同時連接1號和2號地

22、鐵站(如數(shù)據(jù)中S0540 同時連接了 D17和D31)，兩條邊的權(quán)值均為4分鐘。下面我們用修改的Dijkstra 算法來計算這個冋題。第一步：L(1)=0第二步：由1號頂點出發(fā)更新其它頂點，L(3)=4，L(2)=7.5第三步：由3號頂點出發(fā)更新其它頂點，L(2)=min7.5, L(3)+4+ 010=7.5第四步：由2號頂點出發(fā)更新其它頂點,L=L(2)+2.5+ 000=14。因為 2 號頂點由1號頂點擴展而來，所以是000實際上，如果走1 3 2 4的路線距離反而更短。L=4+ 010+4+ 100 +2.5=12.5這種修改的Dijkstra算法不能總能算得最短路徑的原因在于我們加了

23、pqr這一項，其中的p為q的前一個頂點。這就說明頂點p可以影響之后的兩層頂點， 而Dijkstra算法每次只掃描并修改了一層頂點。從這一原因出發(fā)，我們考慮把算 法設(shè)計為“雙層Dijkstra算法”。在雙層Dijkstra算法中，每次掃描頂點均嘗試更新直接相鄰的頂點和與直接 相鄰的頂點相鄰的頂點。即將原 Dijkstra算法的第(3)步改為：對任意的Vj,Vk T，i, j, k互不相等，L(Vj) min L(v)L(vJ W(Vj,vJ心),“Vi , Vj ,vkL(vQ min L(Vk),L(vJ W(w,Vj)帥),計 W(Vj,vQ423.用雙層Dijkstra算法計算得到六條線路

24、的最少時間與422中修改的Dijkstra算法相同，但在之后的模型評價中可以看出雙層Dijkstra算法還是很有優(yōu)勢的?？紤]公汽和地鐵線路的費用最少模型以及換乘次數(shù)最少模型建立有向賦權(quán)圖該模型的有向賦權(quán)圖類似4.2.1的有向賦權(quán)圖，頂點和邊的設(shè)置與4.2.1完全相同，權(quán)值的設(shè)置、換乘系數(shù) pqr的設(shè)置與4.2.1不同對于公汽線路的有向賦權(quán)圖,Si和Sj確定的邊對應(yīng)的權(quán)ij為該公交線所需的車票費用，即:1 Lk為單一票價1 Lk為分段計價，0 Xjj 202 Lk為分段計價，20 Xjj 403 Lk為分段計價，40 Xjj對于任意一條地鐵線路Tk，Di和Dj確定的邊對應(yīng)的權(quán)3ij 3，地鐵票價

25、。對于任意一個地鐵站Di，都存在1至5個可供換乘的公汽站Sj，建立以DiS和Sj為頂點的雙向邊，其權(quán)值 ij=0。因為沒有乘坐交通工具。換乘系數(shù)pqr的設(shè)置：000300100100011 0 100 0地鐵站（A表示乘1010,1100,1110。因為地鐵站 A 地鐵站 地鐵）多收了一次地鐵票價。運用雙層Dijkstra算法求解模型用雙層Dijkstra算法計算得到六條線路的最少費用，結(jié)果如下（具體路線間附錄）:起始站f終到站最優(yōu)線路的總費用（元）S335X S1828時間137花費:3換乘1S1557 S0481時間160花費:3換乘2S0971S0485時間149花費:3換乘1S0008

26、 S0073時間83花費：2換乘1S0148 S0485時間121花費:3換乘2 :S0087f S3676時間71花費：2換乘1考慮公汽和地鐵線路的換乘次數(shù)最少模型 建立有向賦權(quán)圖公汽線路的有向賦權(quán)圖同4.1.1的3）。對于任意一條地鐵線路Tk，有九個站，以這九個站為頂點。對于這 入個頂 點中的任意兩個頂點Di和Dj，定義以Di和Dj為端點的線段是一條邊，地鐵的 運行方向為邊的方向。Di和Dj確定的邊對應(yīng)的權(quán)ij =1。對于任意一個地鐵站Di，都存在1至5個可供換乘的公汽站Sj，建立以Di S和Sj為頂點的雙向邊，其權(quán)值 ij=o。因為沒有乘坐交通工具。運用Dijkstra算法求解模型用Di

27、jkstra算法計算得到六條線路的最少換乘次數(shù)，結(jié)果如下（具體路線見附錄）：起始站f終到站最優(yōu)線路的總費用（元）S335X S1828時間132花費:3換乘1S1557 S0481時間166花費:3換乘2S0971S0485時間260花費:5換乘1S0008f S0073時間116花費:3換乘1S0148f S0485時間196花費:4換乘2S0087f S3676時間30花費:3換乘0已知行走時間的最佳路線考慮了步行時間，換乘次數(shù)、票價這兩個目標將失去意義，因為查詢者會選 擇走完全程，以獲得換乘次數(shù)為 0,且沒有票價的“最優(yōu)路線”。因此我們只需 要分析時間這一目標。在4.2的基礎(chǔ)上，我們可以

28、得到任兩點間乘坐公交的最短路線。建立圖G1,頂點為所有公交站點，邊權(quán)值為各頂點間通過公交線到達的最短時間。我們已知了任兩點間的步行時間，故可用最短路徑算法直接求得任意兩點間 的最少步行時間。建立圖 G2,頂點為所有公交站點，邊權(quán)值為各頂點間通過步 行到達的最短時間。因為G1和G2的所有邊已是各自的最短路徑，所以G1或是G2中任意兩條 屬于同一個圖的邊的拼接只會讓路徑更長。我們只需考慮輪換拼接 G1和G2中 的邊。G1邊接G2邊：公交車之后步行，兩條邊可以直接拼接。G2邊接G1邊：步行之后乘坐公交車，可能需要在此處加入公汽或地鐵的 等待時間。具體要看這條公交邊中最開頭的兩站。我們發(fā)現(xiàn)這里和之前4

29、.2.3中建立雙層Dijkstra算法時遇到的情形是一樣的， 在拼接兩條邊時需要加上換乘系數(shù)，每個頂點會對之后兩層頂點產(chǎn)生影響。與 4.2.3不同的是，要拼接的邊不在同一張圖中。我們假設(shè)第一條邊來自G1,對于奇數(shù)號頂點，采用以下兩個公式代替 4.2.3 中的公式L（Vj） min L（Vj）, L（vJ W（V，Vj）vi,vj ,vkL(vk) min L(vk ), L(vi ) W1(vi,vj)f (vi ),vi,vj W2(vj,vk)對于偶數(shù)號頂點，把上述公式的 W1和W2互換即可。然后再假設(shè)第一條邊來自 G2,用完全對應(yīng)的方法計算，最后取兩者的最小 值即可。5. 模型評價及改進

30、5.1. 模型評價1）本文根據(jù)乘客的不同需求，提出三個目標函數(shù)（總時間最短、總費用最 少、換乘次數(shù)最少），并求出三個目標函數(shù)在僅考慮公汽線路時的最優(yōu)解，以及 目標函數(shù)在同時考慮公汽線路和地鐵線路時的最優(yōu)解。 因此本文所建的模型可以 滿足乘客的不同需求。 但是，本文并沒有提出一個綜合考慮乘客 3 種需求的模型。2）在模型 4.1 中，采用 Dijkstra 算法求出任意兩公汽站點之間最優(yōu)線路。該 模型方法比較簡單， 準確性高， 可操作性強。 但該算法只能解決公交線路比較簡 單的情況，具有它的局限性。3）雙層 Dijkstra 算法與修改的 Dijkstra 算法的比較為了說明雙層 Dijkstr

31、a 算法較修改的 Dijkstra 算法的優(yōu)點，枚舉了 3996 個站C2點（其中 3957個公汽站點和 39 個地鐵站點）的兩兩組合，一共 C3996 = 7982010 種查詢。對于每一個查詢， 分別用兩種算法計算， 并加以比較， 發(fā)現(xiàn)雙層 Dijkstra 算法在其中的 458681 條查詢更優(yōu)，其余的計算結(jié)果相同。兩種算法最多會相差 3.5分鐘。如S1914-S3060,用修改的Dijkstra算法算得最少時間為42分鐘，用 雙層 Dijkstra 算得最少時間為 38.5分鐘。具體路線見附錄。 把所有相差的時間平 均分散到所有查詢中，每條線路多用 4.5秒。修改的 Dijkstra

32、算法效率較高， 但不是總能獲得時間最少的解。 從分析中看， 該算法在 94.3%情況下適用。在其不適用的 5.7%中，最大誤差也僅為 3.5分鐘， 這已是一種十分實用的近似算法。雙層 Dijkstra 算法能獲得最短路徑， 但效率相對降低， 大約比修改的 Dijkstra 算法慢 40倍。從實際應(yīng)用來看，該公司可以將所有路徑計算好，待查詢者查詢 時，直接查表即可。4）雙層 Dijkstra 算法可以得到非常好的結(jié)果，但是本文無法給出嚴格的證 明。5.2. 模型改進1）單一目標函數(shù)能找到使其目標函數(shù)達到很好，但并不一定實用的路線。 可考慮多個目標函數(shù)加權(quán)作為權(quán)值以獲得更實用的路線。參考文獻1（美

33、）科曼（Corme n, T.H.）等著；潘金貴等譯，算法導(dǎo)論，北京：機械工業(yè) 出版社， 2006。6. 附錄6.1.附1:只考慮公汽的最佳路線詳細換乘表（公交線路后的括 號內(nèi)的兩個數(shù)據(jù)分別為車票花費和時間）最少時間S3354 S1828S1557 S0481時間：64 花費：3換乘：2時間：99花費：4換乘：3S3354S2903 乘 L474(1,8),S1557 S1919 乘 L363(1,41),L436(1,8), L366(1,8),L084(1,41)L352(1,8), L132(1,8),S1919 S3186 乘 L189(1, 14)L123(1,8), L015(1,

34、8)S3186S0902 乘 L317(1,35),S290IS1784 乘 L485(1,53),L091(1,35)L485(1,53)S0902 S0481 乘 L516(1, 14),S178S S1828 乘 L217(1,8),L460(1, 14), L447(1, 14),L167(1,8)L312(1, 14), L254(1, 14)S0971 S0485S0008 S0073時間：103花費：3 換乘：2時間：59花費：5 換乘：4S0971 S2517 乘 L013(1,53)S0008 S1691 乘 L198(1, 11)S2517 S2159 乘 L290(1,4

35、4),S1691S2085 乘 L476(1,20)L290(1,44)S208N S0609 乘 L406(1,8),S2154 S0485 乘 L469(1, 11)L406(1,8), L017(1,8),L017(1,8)S0609S0525 乘 L328(1, 14)S052NS0073 乘 L103(1, 11)S01410485S00873676時間：102花費：4 換乘：3時間：46花費：3 換乘：2S014IS3604 乘 L308(1,50)S0087 S0088 乘 L454(1,8),S360SS2361 乘 L354(1, 11),L206(1,8), L021(1,

36、8)L123(1, 11), L081(1, 11)S0088 S0427 乘 L381(1,35),S2361 S2210 乘 L156(1,32)L231(1,35), L231(1, 35)S2210 S0485 乘 L417(1, 14)S0427 S3676 乘 L462(1,8),L097(1,8)最少換乘次數(shù)最小花費S 3359S1828時間：137花費：3換乘：1S335XS0304 乘 L469(2, 92)S0304 S1828 乘 L217(1,50)時間：145花費：3換乘：2 S3354S0772 乘 L469(1,47) S077PS0096 乘 L204(1,65

37、) S0096S1828 乘 L167(1,38)S時間：178花費：4換乘:2時間：115花費：3換乘：21557S1557 S0051 乘 L363(1,38),S1557 S1919 乘 L363(1,L084(1,38)41),S0481S0051S0273 乘 L384(1,65)L084(1,41)S0273 S0481 乘 L460(2, 80)S1914 S0902 乘 L417(1,65)S0902 S0481 乘 L516(1,14),L460(1,14),L447(1,14),L312(1, 14), L254(1, 14)S時間：260花費：5換乘：1時間：149花費：

38、3換乘：10971S0971S0354 乘 L119(2, 80)S0971 S0872 乘 L119(1,56)S0354 S0485 乘 L377(3,S0485185)S0872 S0485 乘 L417(2, 98)S時間：116花費：3換乘：1時間：83花費：2換乘：10008S0008 S0181 乘 L259(1,44)S000IS0291 乘 L159(1,59)S0073S0181S0073 乘 L058(2, 77)S0291 S0073 乘 L058(1,29)S時間：196花費：4換乘：2時間：124花費：3換乘：2S0148 S0302 乘 L308(1,20)014

39、8S014IS3604 乘 L308(1,50)S0302 S0029 乘 L348(2,4 4 QS3604 S0248 乘 L021(1,20)S0485119)S0029 S0485 乘 L051(1,62)S024IS0485 乘 L469(1,59)S時間：71花費：2換乘：1時間：71花費：2換乘：1008/S0087 S1893 乘 L454(1,41)S0087 S1893 乘 L454(1,41)S3676S1893 S3676 乘 L209(1,35)S189IS3676 乘 L209(1,35)62附2 :考慮公汽和地鐵的最佳路線詳細換乘表（公交線路后 的括號內(nèi)的兩個數(shù)據(jù)

40、分別為車票花費和時間）最少時間S3354 S1828S1557 S0481時間：62花費：7換乘：4 S3354 S2903 乘 L474(1,3), L436(1,3), L366(1,3),L352(1,3), L132(1,3),L123(1,3), L015(1,3)公汽換乘公汽(0, 5)S290IS0609 乘 L201(1, 12)S0604 D12步行(0, 4)等待地鐵(0, 2)D12 D37 乘 T2(3, 15)D37 S1961 步行(0, 4)等待公汽(0, 3)S1961 S1671 乘 L428(1,6) 公汽換乘公汽(0, 5)S1671 S1828 乘 L0

41、41(1,3)時間：99花費：4換乘：3 S1557 S1919 乘 L363(1,36), L084(1,36)公汽換乘公汽(0, 5)S1919 S3186 乘 L189(1,9) 公汽換乘公汽(0, 5)S3186 S0902 乘 L317(1,30), L091(1,30)公汽換乘公汽(0, 5)S0902 S0481 乘 L516(1,9),L460(1,9), L447(1,9),L312(1,9), L254(1,9)S0971 S0485S0008 S0073時間：95花費：6換乘：3 S0971 S0567 乘 L119(1, 18), L094(1, 18)S0567 D0

42、1 步行(0, 4)等待地鐵(0, 2)D01 D15 乘 T1(3, 35)D15 S2534 步行(0, 4)等待公汽(0, 3)S253S S2210 乘 L156(1, 15) 公汽換乘公汽(0, 5)S221X S0485 乘 L417(1,9)時間：53.5花費：5換乘：3 S0008 S2534 乘 L200(1, 18) S2534 D15 步行(0, 4)等待地鐵(0, 2)D15 D12 乘 T1(3, 7.5) 地鐵換乘地鐵(0, 4)D12 D25 乘 T2(0, 5)D25 S0525 步行(0, 4)等待公汽(0, 3)S052NS0073 乘 L103(1,6)S

43、014IS0485S0087 S3676時間：86.5花費：6換乘：3 S014IS1487 乘 L024(1, 12) S1487 D02步行(0, 4)等待地鐵(0, 2)D02 D15 乘 T1(3, 32.5)D15 S2534 步行(0, 4)等待公汽(0, 3)S253S S2210 乘 L156(1, 15) 公汽換乘公汽(0, 5)S221X S0485 乘 L417(1,9)時間：30花費：3換乘：0S0087 D27 步行(0, 4)等待地鐵(0, 2)D27 D36 乘 T2(3, 20)D36 S3676 步行(0, 4)最少換乘最少花費S時間：132花費：3換乘：1時間：137花費：3換乘：13359S335XS0304 乘 L469(2