公交路線選擇模型

1、基于換乘次數(shù)優(yōu)先的公交路線選擇模型中國(guó)地質(zhì)大學(xué)（武漢）方俊 趙志江 趙科 指導(dǎo)教師 朱小寧 湖北省二等獎(jiǎng)?wù)?要： 隨著城市建設(shè)的飛速發(fā)展及公交系統(tǒng)的不斷完善，公交車已成為 城市居民出行的主要交通工具。 但由于城市公交線路四通八達(dá)， 且隨著城市擴(kuò)建 而快速發(fā)展。 新的公交線路在不斷延伸和開(kāi)辟， 再加上單行道、 禁左等道路交通 約束， 即使是當(dāng)?shù)鼐用褚膊灰欢苷业降竭_(dá)目的地的最佳線路， 外地游客更是難 以獲取公交出行的路徑信息。 因此， 建立適合于公交線路查詢特點(diǎn)的公交數(shù)據(jù)模 型，開(kāi)發(fā)操作直觀、 便捷、 快速、準(zhǔn)確的城市公交查詢系統(tǒng)， 為出行者提供全面、 準(zhǔn)確的公交信息，是城市公交建設(shè)與發(fā)展的迫切

2、需要。影響乘客公交出行路線的選擇主要有以下四個(gè)因素：換乘次數(shù)、出行距離、 出行時(shí)間和出行費(fèi)用。 通過(guò)查找資料和分析， 得出它們對(duì)乘客的影響大小依次為： 換乘次數(shù)、 出行時(shí)間、 出行距離和出行費(fèi)用。 其中出行時(shí)間和出行距離可以看做 一個(gè)整體用出行時(shí)間來(lái)衡量。本文針對(duì)人們的出行心理并根據(jù)以上三個(gè)因素的重要程度和公交線網(wǎng)的實(shí) 際布線情況， 建立基于最優(yōu)換乘次數(shù)條件下出行時(shí)間最短、 出行費(fèi)用最小的換乘 算法模型。 在模型中， 判斷的原則是優(yōu)先考慮換乘次數(shù)少的路徑， 在換乘次數(shù)相 同的情況下， 再考慮出行時(shí)間最短。 這種基于最優(yōu)換乘次數(shù)算法能夠更好的滿足 實(shí)際應(yīng)用的需求， 很好的解決了居民出行公交路線選

3、擇的問(wèn)題， 使公眾的出行更 加通暢、便利。一、對(duì)于公汽網(wǎng)絡(luò)中最佳路線的選擇問(wèn)題， 我們首先定義了兩個(gè)矩陣 line 、 stat_line ，分別存儲(chǔ)各條線路的站點(diǎn)信息和通過(guò)各站點(diǎn)的線路信息，建立了一 個(gè)完整、詳細(xì)的公交網(wǎng)絡(luò)。然后利用廣度優(yōu)先搜索 （BFS） 及類似于遞歸的方法， 從解空間中依次查找滿足約束條件零次換乘（直達(dá) ），一次換乘，兩次換乘的時(shí)間最優(yōu)路線。多次換乘路線的選取則可以綜合利用啟發(fā)式搜索算法和遞歸原理進(jìn)行 查找。 廣度優(yōu)先搜索得到的結(jié)果更準(zhǔn)確， 但是效率較低。 啟發(fā)式搜索則提高了效 率和方向性。 在換乘次數(shù)相同的情況下， 考慮出行時(shí)間最少的路線， 最后將得到 的各種換乘次數(shù)最

4、少、 出行時(shí)最短路線輸出， 并給出各種路線的出行費(fèi)用， 提供 給用戶參考選擇。二、對(duì)于在公汽地鐵混合的公交網(wǎng)絡(luò)中查尋最優(yōu)路線的問(wèn)題， 我們先把地鐵 線和公汽線輸入到問(wèn)題一建立的兩個(gè)矩陣line 、stat_line 中（重新定義） ，從而構(gòu)成一個(gè)大的公交網(wǎng)絡(luò)，再建立一個(gè)矩陣 stat_stat ，用于存儲(chǔ)站點(diǎn)的 鄰接點(diǎn)， 即不需要乘車，可以直接聯(lián)系起來(lái)的站點(diǎn)。 先編寫(xiě)出直達(dá)的程序，然后 利用類似于遞歸的方法， 查找出最優(yōu)換乘次數(shù)的路線。 由于多次換乘實(shí)際應(yīng)用價(jià) 值較小且數(shù)據(jù)量大我們不予考慮。三、對(duì)于考慮步行后出行路線選擇的問(wèn)題， 它的解決模型是問(wèn)題二的模型的 擴(kuò)展。 雖然知道了所有站點(diǎn)之間的步

5、行時(shí)間， 但是我們根據(jù)實(shí)際情況只考慮步行 一站，站點(diǎn)的鄰接點(diǎn)增多，最優(yōu)路線增多。關(guān)鍵詞 ： 換乘次數(shù)廣度優(yōu)先搜索公交網(wǎng)絡(luò)遞歸算法啟發(fā)式搜索 鄰接點(diǎn)一、 一、 問(wèn)題的提出我國(guó)人民翹首企盼的第 29 屆奧運(yùn)會(huì)明年 8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具(簡(jiǎn)稱公交，包括公汽、地鐵等)出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交 線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求，可準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主 查詢計(jì)算機(jī)系統(tǒng)。設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際

6、情況出發(fā)考慮，滿足查詢者的各種不同需求。需要解決如下問(wèn)題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄1提供的數(shù)據(jù)，利用本文建立的模型與算法，求出以下6對(duì)起始站f終到站之間的最佳路線。、S3359 S1828(2)、S1557 S0481(3)、S0971 S0485(4) 、S0008f S0073(5)、S0148f S0485 (6)、S0087 f S36762、同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意兩站點(diǎn)之間線路選擇問(wèn) 題的數(shù)學(xué)模型。二、問(wèn)題的分析乘車方案選擇的最終目的是盡最大可能地滿足乘客的出行

7、需求。所以建立合理的乘客出行路線選擇模型很重要的一點(diǎn)是通過(guò)對(duì)居民出行心理進(jìn)行研究，以確定模型的優(yōu)化目標(biāo)和約束條件。居民公交出行需求是居民對(duì)公交服務(wù)的期望，故應(yīng)首先分析乘客出行考慮的因素及其重要性。我們通過(guò)查找資料(參考文獻(xiàn)4)得到石家莊在市內(nèi)主要公交站點(diǎn)進(jìn)行的一 次居民公交需求問(wèn)卷調(diào)查的結(jié)果：34. 47%的居民希望換乘次數(shù)最少；其次是時(shí)問(wèn)最短為25. 31%;路程最短為18 . 59% ;出行費(fèi)用最低為12. 44% ;其他 為6. 19%?？梢?jiàn)影響居民公交出行的主要因素有以下3個(gè)：換乘次數(shù)、出行距圖1 :重要性比例圖換乘次數(shù)是指乘客完成一次出行過(guò)程所需的換乘次數(shù)。調(diào)查結(jié)果表明，換乘次數(shù)對(duì)公

8、交的選擇影響最大，若換乘次數(shù)較多，出行者會(huì)放棄對(duì)公交的選擇。轉(zhuǎn)向其他更便捷的方式。此外，換乘次數(shù)的增多往往也意味著出行費(fèi)用的增加。換乘比例高是我國(guó)城市公交出行的一個(gè)普遍現(xiàn)象，換乘次數(shù)的多少已成為影響居民公交出行的首要因素。出行時(shí)間是影響居民公交出行的另一主要因素。當(dāng)其中任何一種出行方式時(shí)間過(guò)長(zhǎng)時(shí)，居民都有可能改選其他出行方式。出行距離尤其是車外距離對(duì)居民公交出行影響也比較明顯，但是出行距離往往與出行時(shí)間成正比，而出行時(shí)間更能反映心理中出行距離的遠(yuǎn)近， 故綜合起來(lái)只考慮出行時(shí)間，即出行距離和出行時(shí)間看作一個(gè)因素考慮。出行費(fèi)用對(duì)居民出行路線選擇的影響最小， 因?yàn)橐话闱闆r下，換乘次數(shù)是不 會(huì)超過(guò)兩次

9、的，不同路線的出行費(fèi)用相差很小，在乘客的承受范圍之內(nèi)。根據(jù)以上分析，確定選定乘車路線的原則為： 首先選擇換乘次數(shù)最少的路線， 其次是時(shí)間最短。最后將得到的換乘次數(shù)最少、出行時(shí)間最短的路線輸出， 并給出各路線的出行費(fèi)用，供乘客參考選擇。其次我們對(duì)公共交通工具進(jìn)行分析。公共交通工具簡(jiǎn)稱公交， 本題中包括公汽、地鐵兩種。其中公汽又可以分為三種：環(huán)線車、往返車，上下線車。因?yàn)檐?的種類很多，線路各有特點(diǎn)，比如上下線車的上下線路站點(diǎn)不完全一樣，環(huán)行車的起始點(diǎn)和終點(diǎn)一樣等， 為了研究的方便必須進(jìn)行統(tǒng)一的處理，然后建立一個(gè)完整、詳細(xì)的公交網(wǎng)，利用這個(gè)公交網(wǎng)進(jìn)行查詢。我們利用公交網(wǎng)可以查找到換乘次數(shù)最少的路線

10、，但是換乘次數(shù)相同的路線往往不止一條，在換乘次數(shù)相同的情況下， 還需要考慮出行時(shí)間。 公交的出行時(shí) 間由三部分組成，即公共交通乘行時(shí)間、步行時(shí)間、候車時(shí)間，計(jì)算時(shí)間時(shí)按部分分開(kāi)計(jì)算。分析了以上問(wèn)題后，我們對(duì)具體問(wèn)題進(jìn)行具體分析。問(wèn)題一只考慮公汽的換乘，利用已經(jīng)建立的公交網(wǎng)絡(luò)，建立查詢模型相對(duì)容 易。搜索的方法可以采用啟發(fā)式搜索算法、廣度優(yōu)先搜索算法及類似于遞歸的方法進(jìn)行查找。得到換乘次數(shù)最少的路線后，再計(jì)算出行時(shí)間，最后給出供選擇路線的出行費(fèi)用，供乘客參考。問(wèn)題二加入了地鐵線路， 地鐵線和公汽線構(gòu)成了一個(gè)大的公交網(wǎng)絡(luò)。但是在問(wèn)題二中不同站點(diǎn)間可不乘車而通過(guò)地鐵站聯(lián)系起來(lái)，即不同站點(diǎn)近似成一個(gè)站

11、點(diǎn)了。因?yàn)檫@些站點(diǎn)是通過(guò)地鐵站聯(lián)系起來(lái)的，而不是通過(guò)線路連接起來(lái)的，它們間的關(guān)系在公交網(wǎng)中無(wú)法體現(xiàn)出來(lái)，所以我們應(yīng)該建立一個(gè)矩陣來(lái)存儲(chǔ)站點(diǎn)間的關(guān)系，該矩陣要能反映出可以通過(guò)地鐵站聯(lián)系起來(lái)的站點(diǎn)間的關(guān)系。然后根據(jù)該矩陣，利用地鐵線路和公汽線構(gòu)成的公交網(wǎng)絡(luò)進(jìn)行查找，原理同問(wèn)題一的一樣，即可以得到結(jié)果。問(wèn)題三又考慮了步行的情況。它比問(wèn)題二的范圍更廣，也更符合現(xiàn)實(shí)情況。問(wèn)題一中只有當(dāng)不同線路之間具有公共點(diǎn)時(shí)才能進(jìn)行轉(zhuǎn)車，問(wèn)題二可以通過(guò)地鐵站在不同的站點(diǎn)換乘，但是它們計(jì)算出來(lái)的結(jié)果有時(shí)并不符合實(shí)際情況，比如在實(shí)際出行時(shí)只需換乘兩次便可以到達(dá)目的地，但是計(jì)算出來(lái)的結(jié)果卻需要乘三次或四次。出現(xiàn)這種情況的原因

12、就是忽視了現(xiàn)實(shí)生活中人們步行小段距離再轉(zhuǎn)車的 現(xiàn)象。具體地說(shuō)，人們?cè)谵D(zhuǎn)車時(shí)， 并不是下車后直接在下車的站點(diǎn)處轉(zhuǎn)車，往往 需要步行一小段距離到附近的站點(diǎn)去轉(zhuǎn)車。問(wèn)題三即考慮了這種情況，它和問(wèn)題二都是同一類的問(wèn)題， 即不同站點(diǎn)間可以轉(zhuǎn)車， 只是它的聯(lián)系方式有兩種： 地鐵 站和步行。我們只需將問(wèn)題二建立的矩陣擴(kuò)大一下，加入步行后站點(diǎn)間的關(guān)系， 就可以利用問(wèn)題二的模型計(jì)算出結(jié)果。三、模型假設(shè)考慮實(shí)際問(wèn)題情況和解決問(wèn)題的方便，我們對(duì)問(wèn)題進(jìn)行了簡(jiǎn)化，做出如下的假設(shè)：(1) 乘客出行路線的選擇依據(jù)的先后順序都為：換乘次數(shù)、出行時(shí)間、出行 費(fèi)用。(2) 不考慮道路交通運(yùn)行條件的影響；(3) 公汽、地鐵等相鄰站

13、點(diǎn)間運(yùn)行時(shí)間相同，不考慮各站間距離、交通狀況 對(duì)行駛時(shí)間的影響，即：相鄰公汽站平均行駛時(shí)間 (包括停站時(shí)間 )： 3 分鐘 相鄰地鐵站平均行駛時(shí)間 (包括停站時(shí)間 )： 2.5 分鐘(4) 各種公交在不同地點(diǎn)的換乘所需時(shí)間都統(tǒng)一處理，即不考慮各種公交的 發(fā)車頻率、行駛速度以及其他一些因素的影響。即：公汽換乘公汽平均耗時(shí)：5分鐘 (其中步行時(shí)間 2分鐘)地鐵換乘地鐵平均耗時(shí)：4分鐘 (其中步行時(shí)間 2分鐘)地鐵換乘公汽平均耗時(shí)：7 分鐘(其中步行時(shí)間 4 分鐘)公汽換乘地鐵平均耗時(shí)：6 分鐘(其中步行時(shí)間 4 分鐘)(5) 乘坐各種公交時(shí)所需的等待時(shí)間一定。即：乘坐公汽需要的等待時(shí)間為 3 分鐘

14、、乘坐地鐵所需要的等待時(shí)間為 2 分鐘。(6) 地鐵站點(diǎn)相對(duì)應(yīng)的公汽站點(diǎn)間的換乘時(shí)間是由從一對(duì)應(yīng)公汽站走到地鐵 站的 4分鐘、再由地鐵站走到另一對(duì)應(yīng)的公汽站的 4 分鐘以及乘坐公汽所需的等 待時(shí)間 3分鐘組成。即通過(guò)地鐵站點(diǎn)相對(duì)應(yīng)的公汽站點(diǎn)間的換乘時(shí)間為 11 分鐘四、參數(shù)定義 S： 起始點(diǎn)； F： 終到點(diǎn)； C： 中轉(zhuǎn)站；line ：存儲(chǔ)各條線路的站點(diǎn)信息的矩陣；stat_line ：存儲(chǔ)通過(guò)各站點(diǎn)的線路信息的矩陣；stat_stat ：存儲(chǔ)鄰接點(diǎn)的矩陣；type ：保存存儲(chǔ)的路線的收費(fèi)情況: 分段計(jì)費(fèi)或單一制 1 元計(jì)費(fèi)； L: 公汽線路；S: 公汽站點(diǎn)；T: 地鐵線路； D: 地鐵站點(diǎn)。

15、五、 五、 模型的建立及求解1. 1. 問(wèn)題一模型的建立及求解本問(wèn)題的建模思路為： 首先對(duì)題目所給的數(shù)據(jù)進(jìn)行處理、輸入， 建立公交網(wǎng) 絡(luò)；然后根據(jù)公交網(wǎng)絡(luò)進(jìn)行搜索， 找到換乘次數(shù)最少的路線； 再算出各路線的出 行時(shí)間， 找出出行時(shí)間最短的路線； 最后算出路線的出行費(fèi)用， 將換乘次數(shù)最少、 出行時(shí)間最短的路線輸出，并輸出其出行費(fèi)用。公交網(wǎng)絡(luò)路線查詢算法：1) 1) 讀入數(shù)據(jù)，建立公交網(wǎng)絡(luò)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。 將原始數(shù)據(jù)進(jìn)行特殊處理，便于存儲(chǔ)。每一條線包括 4-5 行，如下： 第一行：線路的編號(hào) , 在存儲(chǔ)的時(shí)候?qū)⒎殖蓛蓷l線來(lái)存儲(chǔ) ; 第二行：線路的類型 , 0 : 分段計(jì)價(jià)， 1 : 單一制 1 元

16、計(jì)價(jià) ; 第三行：線路的條數(shù)， 1: 往返線， 2: 上下行線， 3: 環(huán)形線 ;第四行：線路經(jīng)過(guò)的節(jié)點(diǎn)（若有上下行線則還有第五行）;公交路線的存儲(chǔ)：建立lin e矩陣，如表一所示：a 上下行線：對(duì)于上行和下行分別當(dāng)成兩條路線來(lái)處理，且編號(hào)相差520例如上行線為L(zhǎng)1，則下行線編號(hào)L521;b .往返線：把往返線也當(dāng)作兩條線來(lái)處理，編號(hào)相差520;c. 環(huán)形線：只當(dāng)成一條線，但在存儲(chǔ)時(shí)仍然占用兩條線的存儲(chǔ)空間。路線編號(hào)0123nL1節(jié)點(diǎn)個(gè)數(shù)S619 1S1914S0388S710L2節(jié)點(diǎn)個(gè)數(shù)S3748S2160.S0004L3節(jié)點(diǎn)個(gè)數(shù)S0417 ：S0272S2488L4節(jié)點(diǎn)個(gè)數(shù)S3010S05

17、82S0579.S2488.L1040節(jié)點(diǎn)個(gè)數(shù)S1848S2645S1344.S0600表一：公汽路線的存儲(chǔ)結(jié)構(gòu)圖公汽站與路線的對(duì)應(yīng)關(guān)系：建立stat_line矩陣，如表二所示：每一個(gè)公汽站有多路公汽路線通過(guò)，每一條路線通過(guò)多個(gè)公汽站， stat_lineij=1表示第i個(gè)公汽站有第j路公汽車通過(guò)，相反若為0則表示沒(méi)有 該路車通過(guò)。公汽站名0L1L2L3L4L1040S1-00010S2r 100 :0001001S395700100表二：公汽站和公汽路線對(duì)應(yīng)關(guān)系存儲(chǔ)結(jié)構(gòu)圖2） 2）零次換乘算法設(shè)計(jì)：對(duì)于給定的起點(diǎn)站S和終點(diǎn)站F，在公汽網(wǎng)絡(luò)中S若能通過(guò)一路公汽車直達(dá)F，則必存在同時(shí)經(jīng)過(guò)兩站點(diǎn)的

18、公汽路線。因此，在查旬S到F能否直達(dá)時(shí)只要在stat_line中從第1列到最1040列搜索，若stat_lineSi 和 stat_lineFi同時(shí)為1則說(shuō)明S和F有可能直達(dá)，對(duì)于該算法還需考慮幾點(diǎn)：a.b.c.d.a. 有可能同時(shí)存在不同的公汽線路通過(guò)S和F ；b. 在單向行駛路線中起點(diǎn)站 S必須在終點(diǎn)站F的前面，而環(huán)線可以，因此對(duì) 于環(huán)線應(yīng)該特殊處理；c. 搜索交通線路時(shí)，同時(shí)求出該條公汽路線從S到F經(jīng)過(guò)的站點(diǎn)個(gè)數(shù)，據(jù)此可以求出S到F花費(fèi)的時(shí)間=乘車等待時(shí)間 +行駛時(shí)間；d. 對(duì)于環(huán)線我們的算法是同時(shí)在公汽路線的節(jié)點(diǎn)順序和逆序搜索兩次，經(jīng)過(guò)的公汽站個(gè)數(shù)取兩次搜索的較小值，具體說(shuō)明如圖二：e

19、.f.e.f.a.a.b.c.b.c.在公汽路線中存在如上圖所示的路線圖(例如L17)，即在給定的公汽站點(diǎn)中存在環(huán)的情況(站點(diǎn)B在路線中出現(xiàn)兩次),把B當(dāng)做S, A當(dāng)做F,在統(tǒng)計(jì)經(jīng)過(guò) 的路線時(shí)，我們可能得到：B-C-D-B-A，經(jīng)過(guò)的站點(diǎn)個(gè)數(shù) num=4；而實(shí)際上路線B-A才是我們希望得到的，經(jīng)過(guò)的站點(diǎn)個(gè)數(shù)num=1。e. 算法實(shí)現(xiàn)函數(shù)：int num_O(int s, int f, int L, int *mi, int *sch) ； mi 指向的空 間存儲(chǔ)經(jīng)過(guò)站點(diǎn)的個(gè)數(shù)，sch指向的空間存儲(chǔ)在最小值條件下路線方案的個(gè)數(shù)。f. 時(shí)間復(fù)雜度：O(L*N)，其中L為公汽線的條數(shù)，N為公汽線中最

20、大的節(jié)點(diǎn) 個(gè)數(shù)。3) 3) 一次換乘算法設(shè)計(jì)：一次換乘即在S和F之間沒(méi)有公汽車直接往返，用戶需要在途徑的某個(gè)站點(diǎn)下車，然后轉(zhuǎn)乘另一線路公汽車才能達(dá)到目的站點(diǎn)。算法的關(guān)鍵在于找 到一個(gè)中轉(zhuǎn)站點(diǎn) C,從而可以轉(zhuǎn)化成兩次S-C，C-F查詢零次換乘的公汽路線。a. 中轉(zhuǎn)站C的查找：與S在同一公汽路線的站點(diǎn)都可能作為中轉(zhuǎn)站，但必須經(jīng)過(guò)兩次檢驗(yàn)：第一必須保證從 S可乘L1路車到達(dá)C ；第二必須保證 C能夠乘 L2路車到達(dá)F ；b. 路線花費(fèi)總時(shí)間=乘車等待時(shí)間 + L1的行駛時(shí)間+換乘時(shí)間+ L2的行 駛時(shí)間；c. 路線方案有多種：存在n條L1和m條L2(n, m=1,2,3)情況，貝山總的路線總數(shù)為n*

21、m條，如圖三所示，即存在4條路線；d.e.f.d.e.f.d. 中轉(zhuǎn)站不能重復(fù)，即在搜索路線L1中的所有節(jié)點(diǎn)后，當(dāng)搜索路線L2中的節(jié)點(diǎn)時(shí)，若存在一站點(diǎn)C在L1中出現(xiàn)，則不應(yīng)把 C再當(dāng)做中轉(zhuǎn)站。e. 算法實(shí)現(xiàn)函數(shù)：int num_1(ints,intf, int L1,intL2,int*mi,intc,int*sch)；f. 時(shí)間復(fù)雜度：O(L*N) 2);當(dāng)找到中轉(zhuǎn)站C后，可以遞歸的調(diào)用零次換乘算法的函數(shù)：num_0(S, C,L1,&min1, &sch1)和num_0(C, F,&min2, &sch2)。若兩函數(shù)都返回 1,則說(shuō)明通過(guò)中 轉(zhuǎn)站C可以從S換

22、乘一次車到達(dá) F。min1和min2分別保存了從 S-C, C-F路線 的經(jīng)過(guò)站點(diǎn)的最小值。sch1和sch2分別保存了從 S-C, C-F在最小值條件下路 線的條數(shù)。4) 4)兩次換乘算法設(shè)計(jì)：兩次換乘即從S到F中間經(jīng)過(guò)了兩個(gè)中轉(zhuǎn)站，對(duì)于該算法完全可以按照一 次換乘的實(shí)現(xiàn)過(guò)程。首先查找中轉(zhuǎn)站C ,再分別調(diào)用一次零次換乘的函數(shù)和一次 一次換乘的函數(shù)。具體過(guò)程不再贅敘。算法實(shí)現(xiàn)函數(shù)：int num_2(int s, int f, int L1, int L2, int L3, int *mi, int c1, int c2, int *sch)；時(shí)間復(fù)雜度：O(L*N) 3)，由此可知當(dāng)查找兩次

23、換乘路線時(shí)，時(shí)間效率不高， 但是經(jīng)過(guò)一定的優(yōu)化可以在理想的實(shí)踐內(nèi)查找到，合適的方案來(lái)，比如第二組和第五組數(shù)據(jù)都要用兩次換乘算法查找到最優(yōu)的路線。雖然兩次換乘的算法在時(shí)間效率方面不高，但是大部分查詢通過(guò)兩次換乘就可以得到最優(yōu)路線5) 5)多次換乘算法設(shè)計(jì)：由兩次換乘可以看出 n次換乘的實(shí)踐復(fù)雜度成指數(shù)增長(zhǎng)，為O(L*N) n-1)；當(dāng)n超過(guò)3時(shí)，可以想象查詢效率會(huì)慢的讓人無(wú)法忍受，因此應(yīng)該尋找更加優(yōu)越的算法，啟發(fā)式搜索就是一種很好的解決方法。啟發(fā)式搜索就是在狀態(tài)空間中的搜索前對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。三次換乘算法中，我們可以統(tǒng)計(jì)出各個(gè)站點(diǎn)通過(guò)的線路

24、數(shù)，在進(jìn)行路線搜索時(shí)，可以直接找通過(guò)起始點(diǎn)的所有線路上通過(guò)的線路數(shù)最多的站點(diǎn)，然后調(diào)用二次換乘的程序進(jìn)行搜索，這樣省略了大量無(wú)畏的搜索路徑，增加了目的性，提到了效率。更多次換乘的搜索原理和三次換乘原理相同。6) 6)算法實(shí)現(xiàn)流程圖：根據(jù)以上算法思想，我們可以做出如圖四所示的流程圖：輸入數(shù)據(jù)，建立公交網(wǎng)絡(luò)7) 7)問(wèn)題一的最優(yōu)選擇路線： 線路說(shuō)明如下：路線：S3359->L436->S1784->L167->S1828 表示從 S3359 站經(jīng)過(guò) L436 路車在S1784站下后，換乘 L167路車在站點(diǎn)S1828下車；時(shí)間:104 表示從起始站到終到站耗費(fèi)的時(shí)間為104

25、min，包括等待時(shí)間+換乘時(shí)間+行駛時(shí)間；路線L436->L167=3表示從起始站到終到站的總票價(jià)為3元。本模型給出的6對(duì)起始站到終到站的最優(yōu)換乘方案如下：1. 1.S:F=S3359S1828有2種換乘方案：換乘一次車 1: 線路 S3359->L436->S1784->L167->S1828, 時(shí)間 104 換乘一次車 2: 線路 S3359->L436->S1784->L217->S1828, 時(shí)間 104 方案 1: 路線 L436->L167=3 方案 2: 路線 L436->L217=32. 2. S:F=S1557

26、 S481 有 2 種換乘方案 : 換乘兩次車 1: 線路 S1557->L84->S1919->L189->S3186->L460->S481, 時(shí)間：109 換乘兩次車 2: 線路 S1557->L363->S1919->L189->S3186->L460->S481, 時(shí)間：109 方案 1: 路線 L84->L189=3 方案 2: 路線 L363->L189=33. 3. S:F=S971 S485 有 1 種換乘方案 : 換乘一次車 1: 線路 S971->L13->S2184->

27、L417->S485, 時(shí)間 131 方案 1: 路線 L13->L417=3換乘一次車換乘一次車4. 4. S:F=S8 S73 有 14 種換乘方案 :1:線路S8->L159->S3315->L58->S73,時(shí)間862:線路S8->L159->S2559->L464->S73,時(shí)間863:線路S8->L159->S2559->L58->S73,時(shí)間864:線路S8->L159->S491->L58->S73,時(shí)間 865:線路S8->L159->S3614->L

28、58->S73,時(shí)間866:線路S8->L159->S291->L58->S73,時(shí)間 867:線路S8->L159->S2683->L58->S73,時(shí)間868:線路S8->L159->S3053->L474->S73,時(shí)間869:線路S8->L159->S2633->L474->S73,時(shí)間8610: 線路S8->L159->S400->L474->S73,時(shí)間86換乘一次車 換乘一次車 換乘一次車 換乘一次車 換乘一次車 換乘一次車 換乘一次車 換乘一次車 換乘一

29、次車 換乘一次車11: 線路 S8->L355->S2303->L345->S73,12: 線路 S8->L355->S3917->L345->S73,時(shí)間 86時(shí)間 86、.> > r方案1:路線、.> > r方案2:路線、.> > r方案3:路線、.> > r方案4:路線、.> > r方案5:路線、.> > r方案6:路線、.> > r方案7:路線、.> > r方案8:路線、.> > r方案9:路線、.> > r方案10:

30、路線、.> > r方案11: 路線、.> > r方案12: 路線時(shí)間 86時(shí)間 86換乘一次車換乘一次車13: 線路 S8->L463->S2083->L57->S73, 14: 線路 S8->L355->S2263->L345->S73,L159->L58=3L159->L464=3L159->L58=3L159->L58=2L159->L58=2L159->L58=2L159->L58=2L159->L474=2L159->L474=2L159->L474=2

31、L355->L345=2L355->L345=2 方案 13:路線 L463->L57=2 方案 14:路線 L355->L345=25. 5.S:F=S148S485有3種換乘方案：換乘兩次車1:線路S148->L308->S36->L156->S2210->L417->S485,時(shí)間109換乘兩次車2:線路S148->L308->S36->L156->S3332->L417->S485,時(shí)間109換乘兩次車3:線路S148->L308->S36->L156->S3351-

32、>L417->S485,時(shí)間109方案 1:路線 L308->L156=3方案 2:路線 L308->L156=3方案 3:路線 L308->L156=36. 6.S:F=S87S3676有1種換乘方案：換乘一次車 1:線路 S87->L454->S3496->L209->S3676,時(shí)間 68方案 1:路線 L454->L209=27 .程序?qū)嶋H運(yùn)算截屏示意圖:8) 8) 評(píng)價(jià)分析：6對(duì)起始站-終到站之間輸出的最佳路線，其中有4對(duì)需要換乘一次車、，還有2對(duì)需要換乘2次車，說(shuō)明它們之間沒(méi)有直達(dá)車，而且除了第3、6對(duì)只有一種方案外，其他

33、都有多種方案可供選擇。a) a) 本問(wèn)題建立的模型是按換乘次數(shù)由少到多進(jìn)行循環(huán)的，輸出的為換乘次數(shù)最少的路線，這樣花在轉(zhuǎn)車上的時(shí)間將會(huì)減少，步行時(shí)間和距離也會(huì)減少；b) b) 找到換乘次數(shù)最少的路線后，再計(jì)算出各路線的出行時(shí)間，選出時(shí)間最短的路線，時(shí)間越短則浪費(fèi)的時(shí)間越少，對(duì)當(dāng)代人來(lái)說(shuō)無(wú)疑是很重要的；c) c) 模型輸出最佳路線有 4對(duì)不止一條，這樣給乘客提供了更多的選擇空 間，使乘客可以根據(jù)實(shí)際公交運(yùn)行情況和自身情況進(jìn)行選擇。2、問(wèn)題二模型的建立及求解本問(wèn)題的實(shí)現(xiàn)過(guò)程整體上與問(wèn)題一的求解過(guò)程相同，讀入數(shù)據(jù)建立公交網(wǎng)絡(luò) (包括公汽網(wǎng)絡(luò)和地鐵網(wǎng)絡(luò))，并存儲(chǔ)地鐵站與公汽站的對(duì)應(yīng)關(guān)系。模型建立的 關(guān)

34、建在于通過(guò)地鐵站可在地鐵站與公交站之間，或公交站與公交站之間進(jìn)行聯(lián)系(通過(guò)步行)，即從一個(gè)站點(diǎn)到達(dá)另一個(gè)站點(diǎn)可以通過(guò)步行，并假定通過(guò)步行達(dá)到另一站點(diǎn)時(shí)，并不累計(jì)到換乘次數(shù)中。1) 1) 從S到F的零次換乘路線包括如下四種情況:圖五：?jiǎn)栴}二零次換乘路線四種不同情況對(duì)于情況一和問(wèn)題一中的模型一樣，直接通過(guò)公交線路聯(lián)系。 在情況二中首先從S步行到C,從C乘車到F。這樣就相當(dāng)于在 S這個(gè)站點(diǎn)增加了多條交通線 路。在搜索最優(yōu)解的過(guò)程中， 滿足相同約束條件的交通線路增多，因此對(duì)于某些起始點(diǎn)和終到點(diǎn)之間就可以通過(guò)較少的換乘次數(shù)或花費(fèi)較少的時(shí)間的交通路線 相連通(從S到達(dá)F),也就是說(shuō)可以得到更優(yōu)的解，通過(guò)程

35、序的運(yùn)行結(jié)果可以很 好的看到這一點(diǎn)。2) 2)問(wèn)題二的最優(yōu)選擇線路：本模型給出的六對(duì)起始站到終到站的最優(yōu)換乘方案如下：1. 1.S:F=S3359S1828有2種換乘方案：換乘一次方案 1: ->S3359->L436->S1784->L167->S1828,時(shí)間：104.00換乘一次方案 2: ->S3359->L436->S1784->L217->S1828,時(shí)間：104.002. 2.S:F=S1557S481有2種換乘方案：換乘兩 次方案 1: ->S1557->L84->S1919->L189->

36、;S3186->L460->S481, 時(shí)間:109.00換乘兩 次方案 2: ->S1557->L363->S1919->L189->S3186->L460->S481, 時(shí)間:109.003. 3.S:F=S971S485有1種換乘方案：換乘一次方案 1: ->S971->L13->S2184->L417->S485, 時(shí)間：131.004. 4. S:F=S8 S73有14種換乘方案：換乘一次方案1:->S8->L159->S3315->L58->S73,時(shí)間：86.00換乘

37、一次方案 2: ->S8->L159->S2559->L464->S73, 時(shí)間：86.00 換乘一次方案3:->S8->L159->S2559->L58->S73,時(shí)間：86.00換乘一次方案 4: ->S8->L159->S491->L58->S73, 時(shí)間：86.00 換乘一次方案5:->S8->L159->S3614->L58->S73,時(shí)間：86.00換乘一次方案 6: ->S8->L159->S291->L58->S73, 時(shí)間：86

38、.00 換乘一次方案7:->S8->L159->S2683->L58->S73,時(shí)間：86.00時(shí)間：86.00時(shí)間：86.00時(shí)間：86.00換乘一次方案 8: ->S8->L159->S3053->L474->S73,換乘一次方案 9: ->S8->L159->S2633->L474->S73,換乘一次方案 10： ->S8->L159->S400->L474->S73,換乘一次方案 11: ->S8->L355->S2303->L345->

39、S73, 時(shí)間：86.00換乘一次方案 12: ->S8->L355->S3917->L345->S73, 時(shí)間：86.00 換乘一次方案 13: ->S8->L463->S2083->L57->S73,時(shí)間：86.00 換乘一次方案 14: ->S8->L355->S2263->L345->S73,時(shí)間：86.005. 5.S:F=S148S485有1種換乘方案：換乘兩 次方案 1: ->S148->L24->S1487->D2->T1->D22->S3457-

40、>L51->S485, 時(shí)間：93.006. 6.S:F=S87S3676有1種直達(dá)方案：直達(dá)方案 1: ->S87->D27->T2->D36->S3676, 時(shí)間：33.00i £301中闔用空格暢彌1YB3典例如中叵用空椎隔開(kāi).晴瑜人起點(diǎn)站和終點(diǎn)站:4站肖緞艷乘左峯：戻乘兩次方梟L： ->51-48->1<24->£14«7->02->11->022->53457-1->£485,時(shí)間；93.EH7. 程序?qū)嶋H運(yùn)算截屏示意圖：帶間* 爲(wèi)的 冬鐵出3) 3

41、) 結(jié)果分析：考慮地鐵后，乘客出行可供選擇的線路更多了，最佳路線的情況也可能發(fā)生改變。本模型輸出的6對(duì)起始站-終到站之間最佳路線，雖然前4對(duì)沒(méi)有任何改變，但是第5、6對(duì)的最佳路線則有了很大的優(yōu)化。第5對(duì)現(xiàn)在只需要換乘一次車就可以到達(dá)終到站，而且時(shí)間少要了 13分鐘，第6對(duì)的體現(xiàn)更加明顯，不僅可以直達(dá)，而且時(shí)間減少了一半多，很好的體現(xiàn)出 了地鐵的聯(lián)系作用。比如： S:F=S148 S485;在問(wèn)題一中的求解結(jié)果為：有3種換乘方案：換乘兩次車1:線路S148->L308->S36->L156->S2210->L417->S485,時(shí)間109換乘兩次車2:線路S1

42、48->L308->S36->L156->S3332->L417->S485,時(shí)間109換乘兩次車3:線路S148->L308->S36->L156->S3351->L417->S485,時(shí)間109方案 1:路線 L308->L156=3 方案 2:路線 L308->L156=3 方案 3:路線 L308->L156=3而在問(wèn)題二中的求解結(jié)果為：有1種換乘方案：換乘兩 次方案 1： ->S148->L24->S1487->D2->T1->D22->S3457-&g

43、t;L51->S485, 時(shí) 間：93.00又比如： S:F=S87 S3676 在問(wèn)題一中的求解結(jié)果為： 有 1 種換乘方案 :換乘一次車 1: 線路 S87->L454->S3496->L209->S3676, 時(shí)間 68方案 1: 路線 L454->L209=2 而在問(wèn)題二中的求解結(jié)果為： 有 1 種直達(dá)方案 : 直達(dá)方案 1: ->S87->D27->T2->D36->S3676, 時(shí)間： 33.003 3 問(wèn)題三的模型建立 本問(wèn)題的建模思路為：首先將題目所給的公汽線、地鐵線的數(shù)據(jù)進(jìn)行處理，輸入， 建立公交網(wǎng)絡(luò)。 公交網(wǎng)

44、絡(luò)中地鐵線與公交線通過(guò)建立一個(gè)鄰接站矩陣聯(lián)系 起來(lái)， 為了便于問(wèn)題的分析， 不失一般性， 我們假設(shè)在某一站點(diǎn)可以向其相鄰的 站點(diǎn)聯(lián)通起來(lái)，即可以沿著某一公交線路 (地鐵線除外 ) 向前或向后一站點(diǎn)步行， 到達(dá)下一站點(diǎn)后， 仍然可以選擇步行還是乘車。 根據(jù)公交網(wǎng)絡(luò)和鄰接站矩陣在問(wèn) 題二模型的基礎(chǔ)上進(jìn)行搜索， 找到換乘次數(shù)最少的路線， 再根據(jù)給定的站點(diǎn)到站 點(diǎn)的步行時(shí)間，計(jì)算出給路線的耗費(fèi)時(shí)間，從而給出最優(yōu)路線方案。1) 1) 類似于問(wèn)題二中增加與地鐵站相關(guān)聯(lián)的公交站，在查找最優(yōu)路線時(shí)， 不 考慮步行對(duì)換乘次數(shù)的影響 ( 例如從 A 步行到 B ，換乘次數(shù)不增加 )，在最優(yōu) 換乘次數(shù)的決策中，某些

45、路線的換乘次數(shù)會(huì)降低。表面上與問(wèn)題二相比找到 了更優(yōu)解，但是由于站與站之間的步行時(shí)間不定，可能導(dǎo)致搜索出的最優(yōu)解 耗費(fèi)的時(shí)間反而比換乘次數(shù)多的路線大很多。這并不滿足實(shí)際情況，此時(shí)我 們可以修改約束因素的優(yōu)先級(jí)，并同時(shí)提供多種方案給用戶選擇。2) 2) 假設(shè)任意相鄰站點(diǎn)之間的步行時(shí)間相同， 且為 3 分鐘， 我們初步得出給 定的 6 對(duì)起始點(diǎn)到終到點(diǎn)在該模型下， 仍以換乘次數(shù)優(yōu)先級(jí)最高的最優(yōu)路線， 如下：1. 1. S:F=S3359 S1828有 2 種直達(dá)方案 :直達(dá)方案 1: ->S3359->S2903->L201->S1671->S1828直達(dá)方案 2:

46、->S3359->S2903->L27->S1784->S18282. 2. S:F =S1557 S481有 2 種換乘方案 :換乘一次方案 1: ->S1557->L84->S1919->S2840->L417->S3919->S481 換乘一次方案 2: ->S1557->L363->S1919->S2840->L417->S3919->S4813. 3. S:F =S971 S485有 2 種換乘方案 :換乘一次方案 1: ->S971->L13->S25

47、17->S2184->L417->S485換乘一次方案 2: ->S971->L13->S3405->S2515->L417->S4854. 4. S:F =S8 S73有 1 種直達(dá)方案 :直達(dá)方案 1: ->S8->L159->S3729->S735. 5. S:F =S148 S485有 1 種換乘方案 :換乘一次方案 1: ->S148->L308->S36->S617->L156->S3351->S4856. 6. S:F =S87 S3676有 1 種直達(dá)方案 :

48、直達(dá)方案 1: ->S87->D27->T2->D36->S3676很明顯， 第 1、2、4 對(duì)起始點(diǎn)到終到點(diǎn)尋找出的最優(yōu)路線換乘次數(shù)相對(duì)于在問(wèn)題 二中的求解減少一，但耗費(fèi)的時(shí)間不一定會(huì)減少（這依賴于站點(diǎn)間的步行時(shí)間 ） 。當(dāng)步行的站點(diǎn)數(shù)越多時(shí)， 耗費(fèi)的時(shí)間越長(zhǎng)， 這樣毫無(wú)意義的步行下去來(lái)保證換乘 次數(shù)的較小，并不是用戶所想要的，因此可知當(dāng)相互關(guān)聯(lián)的站點(diǎn)數(shù)比較多時(shí)， 可 適當(dāng)放寬對(duì)最優(yōu)換乘次數(shù)約束條件。六、模型的優(yōu)缺點(diǎn)及體會(huì) 本文研究居民出行公交路線選擇的問(wèn)題， 綜合考慮了影響居民出行的多種因 素，針對(duì)不同情況建立了三個(gè)基于站點(diǎn)優(yōu)先級(jí)的情況下出行時(shí)間最短、 出行費(fèi)

49、用 最小的換乘算法的模型。該模型很好的解決了居民出行公交路線選擇的問(wèn)題， 使 公眾的出行更加通暢、便利。模型的建立充分考慮了居民的出行心理，思路清晰，搜索方便，容易理解， 并能滿足乘客的普遍要求。 而且輸出的結(jié)果是滿足要求的換乘次數(shù)最少、 出行時(shí) 間最短的多種最佳路線， 給乘客提供了更多的選擇空間， 使乘客可以根據(jù)實(shí)際公 交運(yùn)行情況和自身情況進(jìn)行選擇。模型的適應(yīng)性很強(qiáng)， 增加線路或者站點(diǎn)時(shí)，模型不需要做大的改變， 只需要 將增加的線路或者站點(diǎn)的情況輸入到模型中定義的矩陣內(nèi)即可。 考慮步行等現(xiàn)實(shí) 因素同樣容易實(shí)現(xiàn)。下面是我們?cè)谧鲞@個(gè)問(wèn)題時(shí)的一些感受、體會(huì)以及算法的缺點(diǎn)：1）在本題關(guān)于乘車最優(yōu)路線

50、的選擇問(wèn)題中，由于影響路線選擇的因素有很 多，比如：出行時(shí)間，換乘次數(shù)，出行距離，出行費(fèi)用等，要解決路線的選擇問(wèn) 題，首先就要確定在人們心目中什么樣的路線是最優(yōu)的路線。 因此最關(guān)鍵的問(wèn)題 就是確定最優(yōu)路線的選擇原則。 但是這樣就把乘客出行路線選擇時(shí)考慮的因素及 其重要性統(tǒng)一化了， 模型是在該原則的基礎(chǔ)上建立起來(lái)的。 雖然它能滿足居民的 普遍需求， 但是還是存在一些情況， 不能滿足不同查詢者的不同需求， 比如查詢 者想選擇出行費(fèi)用最低的路線， 本模型就必須進(jìn)行調(diào)整后才能給出滿足查詢者需 求的最佳路線。2）本題中我們最開(kāi)始對(duì)環(huán)行線的處理方式為：假設(shè)公汽的環(huán)線到終點(diǎn)站必 須下車， 從而把公汽環(huán)線增加

51、的一條線路設(shè)計(jì)為空， 而且搜索最佳路線時(shí)沒(méi)有特 殊考慮。 因?yàn)楣协h(huán)線只有二十輛， 故這樣處理對(duì)路線的選擇影響不大。 但是 在問(wèn)題二中地鐵二號(hào)線也是環(huán)線， 由于地鐵線路只有兩條且通過(guò)地鐵可以將很多 站點(diǎn)聯(lián)系起來(lái)， 這樣處理就不合適， 對(duì)結(jié)果影響較大。 因此我們?cè)谒阉髯罴崖肪€ 時(shí)，先判斷線路是否為環(huán)形，如果是就特殊考慮，如果不是就按常規(guī)方法搜索。3）本題建立的模型采用了廣度優(yōu)先搜索算法，通過(guò)程序運(yùn)行我們發(fā)現(xiàn)問(wèn)題 一中計(jì)算機(jī)的運(yùn)行速度隨著換乘次數(shù)的增加而變慢，在問(wèn)題二中體現(xiàn)的更明顯。 這是因?yàn)閺V度優(yōu)先搜索有一個(gè)很大的缺陷就是它是在一個(gè)給定的狀態(tài)空間中窮 舉。這在狀態(tài)空間不大的情況下是很合適的算法

52、， 可是當(dāng)狀態(tài)空間十分大， 且不 預(yù)測(cè)的情況下就不可取了。 它的效率實(shí)在太低， 甚至不可完成。 在這種情況下可 以采用啟發(fā)式搜索。 啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn) 行評(píng)估， 得到最好的位置， 再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。 這樣可以省略大量 無(wú)畏的搜索路徑，提到了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的， 我們提供了站點(diǎn)評(píng)估的方法，但是沒(méi)有編出程序?qū)崿F(xiàn)。4）當(dāng)解決實(shí)際問(wèn)題時(shí)候，我們會(huì)遇到很多人為無(wú)法確定的因素，也就是說(shuō) 在解決問(wèn)題的時(shí)候會(huì)有很多實(shí)際存在的問(wèn)題無(wú)法在建模中利用模型來(lái)解決， 所以 還需要對(duì)題目做進(jìn)一步的簡(jiǎn)化和假設(shè)。 由于在實(shí)際模型中不可能考慮到各個(gè)車次

53、運(yùn)行的速度， 車次的多少， 發(fā)車的頻率， 轉(zhuǎn)車的時(shí)間等一系列影響時(shí)間計(jì)算的因 素以及各個(gè)站點(diǎn)間距離的不同而帶來(lái)的距離的不同， 所以對(duì)一些因素要有正確的 處理方式。對(duì)那些影響時(shí)間計(jì)算以及距離計(jì)算的因素按照平均或一般的情況進(jìn)行 統(tǒng)一的假設(shè)， 對(duì)于無(wú)關(guān)因素可以在建模中不予考慮。 就像本模型中把各個(gè)公交站 點(diǎn)間的行駛時(shí)間、 轉(zhuǎn)車時(shí)間、 候車時(shí)間都平均統(tǒng)一下來(lái)， 而對(duì)一些不確定的情況 做了一些合理的假設(shè)，對(duì)那些不重要的因素不予考慮。5）考慮地鐵和步行因素后，得到的最佳路線有一些發(fā)生了變化，但是也存 在最佳路線和只考慮公汽的換乘次數(shù)一樣、 出行時(shí)間也一樣的情況。 我們把所有 的最佳路線都輸出，但是實(shí)際情況

54、下，居民一般都會(huì)選擇步行時(shí)間最短的路線， 我們可以將各個(gè)路線需要的步行時(shí)間進(jìn)行比較，得出步行時(shí)間最少的最佳路線。6）在根據(jù)題意求解的過(guò)程中，必須要盡可能了考慮到各種情況對(duì)結(jié)果的影 響。建模的時(shí)候要顧及到各種條件，力求求出的結(jié)果是真正的最優(yōu)解。附錄1 北京市公交系統(tǒng)線路站點(diǎn)一覽表（ 2007 年全國(guó)大學(xué)生數(shù)學(xué)建模大賽提供） 文件： 1.1.txt（ 公汽線路信息 ）L001 分段計(jì)價(jià)。 S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S08 20-S3914-S0128-S0710L002 分段計(jì)價(jià)。 上行： S3748-S216