公交系統(tǒng)快速查詢的優(yōu)化模型與算法

1、 公交系統(tǒng)快速查詢的優(yōu)化模型與算法 摘要對(duì)北京將要舉辦的第29屆奧運(yùn)會(huì)，交通問題十分重要。研制一種快速查詢系統(tǒng)，幫助用戶特別是那些不熟悉北京交通的用戶，快速查詢從出發(fā)點(diǎn)到目標(biāo)站如何到達(dá)及最優(yōu)路線十分重要。本文針對(duì)該實(shí)際問題，提出該問題的一般數(shù)學(xué)表達(dá)模型及有效的算法。對(duì)問題一，我們采用一個(gè)三維0-1矩陣完整的表達(dá)了任意兩站點(diǎn)間的線路信息。建立了表達(dá)任意兩站點(diǎn)到達(dá)情況的0-1決策變量，并以換乘次數(shù)最少，時(shí)間最少，費(fèi)用最少為目標(biāo)的多目標(biāo)非線性規(guī)劃模型。為求解該模型，我們提出了以換乘次數(shù)為步長(zhǎng)的快速搜索算法。并用鄰接矩陣的方法計(jì)算出該城市公交網(wǎng)絡(luò)系統(tǒng)通過2次換乘，可以完成99.98%站點(diǎn)對(duì)的互達(dá)，最多

2、通過3次換乘，可以全部實(shí)現(xiàn)任意站點(diǎn)對(duì)的互達(dá)。對(duì)該搜索算法，我們還進(jìn)行了算法復(fù)雜性分析，分析表明，該算法對(duì)換乘次數(shù)不大情況下是快速有效的。利用該算法，我們得到了問題一的結(jié)果：對(duì)(1)S3359S1828,我們得到2條換乘1次，時(shí)間為101分鐘，費(fèi)用3元的線路。同時(shí)得到4條換乘2次，時(shí)間為76分鐘，費(fèi)用3元的線路.對(duì)(2)、S1557S0481,我們得到1條換乘2次，時(shí)間為106分鐘，費(fèi)用3元的線路。對(duì)(3)、S0971S0485, 我們得到1條換乘1次，時(shí)間為128分鐘，費(fèi)用3元的線路, 同時(shí)得到1條換乘2次，時(shí)間為106分鐘，費(fèi)用3元的線路.更詳細(xì)結(jié)果見附錄一.對(duì)問題二，我們提出標(biāo)準(zhǔn)線路的概念

3、，將地鐵線路，地鐵站和公交站，和地鐵相連的公交站，都當(dāng)作新增的線路來考慮。文中重新考慮該線路的費(fèi)用與時(shí)間，得到與模型一統(tǒng)一的模型。在算法上，利用地鐵站的特點(diǎn)，首先計(jì)算出地鐵任意站間的時(shí)間矩陣和費(fèi)用矩陣。對(duì)兩公交站(起始點(diǎn)和目標(biāo)點(diǎn))通過地鐵到達(dá)情況，分為四種情況計(jì)算，分別采用合理算法進(jìn)行搜索。得到結(jié)果如下：對(duì)(1)（2）兩對(duì)點(diǎn)，乘坐地鐵對(duì)最優(yōu)解沒有改善,對(duì)(3)得到7條時(shí)間為96 分鐘，費(fèi)用為5元的線路. 對(duì)(4)得到1條時(shí)間為65.5分鐘，費(fèi)用為5元的線路, 對(duì)(5)得到1條時(shí)間為87.5分鐘，費(fèi)用為5元的線路, 對(duì)(6)得到1條時(shí)間為35分鐘，費(fèi)用為3元的線路.這些為問題一中費(fèi)用最小的最優(yōu)線

4、路，提供了一種時(shí)間更少的線路。更詳細(xì)結(jié)果見附錄二.對(duì)問題三，我們?nèi)匀话巡叫挟?dāng)作一種新的線路加入到問題一和二模型中。這里考慮線路費(fèi)用為0，時(shí)間為步行時(shí)間.在實(shí)際中，則考慮對(duì)公交線路的補(bǔ)充，當(dāng)只需要乘坐12站時(shí)，考慮步行。且只考慮對(duì)不多于一次且步行時(shí)間少于30分鐘的情況關(guān)鍵詞：非線性規(guī)劃, 鄰接矩陣, 最優(yōu)解, 算法復(fù)雜性1問題重述第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具出行。近年來，城市的公交系統(tǒng)的快速發(fā)展，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢

5、計(jì)算機(jī)系統(tǒng)。設(shè)計(jì)這樣一個(gè)系統(tǒng)的核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請(qǐng)你們依據(jù)題中提供的附錄1（基本參數(shù)設(shè)定）和附錄2（數(shù)據(jù)文件：公交線路及相關(guān)信息），解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站終到站之間的最佳路線（要有清晰的評(píng)價(jià)說明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題

6、。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。2基本假設(shè)1） 不考慮各路段公交流量限制，無道路擁擠、堵車等耽擱、延誤事件發(fā)生。2） 假設(shè)各線路公交按理想情況到站、發(fā)車，無拋錨等意外事件發(fā)生，公汽、地鐵均運(yùn)行正常。3） 不考慮公交容量問題，即不出現(xiàn)因等車人數(shù)過多，乘客無法在預(yù)定時(shí)間內(nèi)搭乘預(yù)定公汽的現(xiàn)象。4） 環(huán)行公汽到達(dá)終點(diǎn)站后，乘客必須離開，若繼續(xù)乘坐本環(huán)行路線的下一班次公汽，屬于換乘情況。5） 原題附錄所提供的信息均真實(shí)可信。3符號(hào)說明符號(hào)含義路線站點(diǎn)關(guān)系矩陣第條公交線路上由起點(diǎn)站起的第個(gè)站點(diǎn)包含站點(diǎn)A的線路的集合包含站點(diǎn)B的線路的集合的交集由站點(diǎn)的出

7、行費(fèi)用換乘次數(shù)為次到達(dá)目標(biāo)站點(diǎn)時(shí)所需的出行費(fèi)用由站點(diǎn)的出行耗時(shí)換乘次數(shù)為次到達(dá)目標(biāo)站點(diǎn)時(shí)所需的出行耗時(shí)集合中的車輛可以到達(dá)的站點(diǎn)集合4問題分析近年來，公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）已逐漸成為人們?nèi)粘３鲂械闹饕煌üぞ撸覈?guó)各城市的公交系統(tǒng)也迅速發(fā)展，公眾出行較為通暢、便利。但與此同時(shí)，搭乘公交時(shí)，乘客也面臨著多條線路的選擇問題。在這種情況下，研制開發(fā)出一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)，已成為一個(gè)非常值得研究與探討的問題。公交線路選擇問題的研究，涉及乘客心理、路段流量、公交容量、換乘耗時(shí)、及站點(diǎn)分配等諸多因素。這些因素彼此約束，內(nèi)在聯(lián)系較為細(xì)微，各種因素難以精確分析并予以

8、量化，處理起來較為復(fù)雜。而且，由于大中型城市的公交線路數(shù)、站點(diǎn)數(shù)都已達(dá)到百、千數(shù)量級(jí)，數(shù)據(jù)處理的繁瑣性進(jìn)一步增大了問題本身的難度?？紤]到題中提供的信息容量，以及問題處理的實(shí)際可行性與復(fù)雜度，我們?cè)谘芯烤€路選擇問題并建立模型時(shí)，無法對(duì)所有相關(guān)因素都進(jìn)行研究、處理。為了簡(jiǎn)化模型，我們僅從出行耗時(shí)、出行費(fèi)用、換乘次數(shù)等幾個(gè)著手點(diǎn)，結(jié)合乘客心理進(jìn)行問題的研究與分析。首先，我們來分析公交線路選擇的幾大特點(diǎn)：特點(diǎn)一：乘客需求的多樣化。乘客在進(jìn)行公交路線選擇時(shí)，考慮的因素多種多樣，有的乘客會(huì)側(cè)重考慮出行費(fèi)用；有的乘客會(huì)側(cè)重考慮出行耗時(shí)；有的乘客（如老年人、殘疾人等）會(huì)側(cè)重考慮換乘次數(shù)；較為特殊的情況時(shí)，乘客

9、還會(huì)根據(jù)個(gè)人喜好考慮途經(jīng)站點(diǎn)、公交服務(wù)質(zhì)量等多種因素。在這種情況下，我們依據(jù)實(shí)際情況，歸納出公交線路選擇時(shí)的三大主要優(yōu)化目標(biāo)：出行耗時(shí)最短、出行費(fèi)用最少、換乘次數(shù)最少。針對(duì)這三大目標(biāo)，我們?cè)诳紤]換乘次數(shù)較少的前提下，將分別給出對(duì)應(yīng)所給起始站點(diǎn)的綜合最佳路線、耗時(shí)最佳路線、費(fèi)用最佳路線，并進(jìn)行詳細(xì)清晰的評(píng)價(jià)說明。此外，我們還將針對(duì)少數(shù)乘客的特殊需求，給出推薦線路表列，以便滿足不同需求。特點(diǎn)二：約束的復(fù)雜繁瑣化。公交線路中的票價(jià)問題分為單一票制和分段計(jì)價(jià)兩種不同情況；耗時(shí)問題分為站點(diǎn)耗時(shí)和換乘耗時(shí)兩類；最短路徑則已非傳統(tǒng)意義上距離的最短化，而是要綜合考慮所經(jīng)站點(diǎn)數(shù)、步行距離和換乘次數(shù)等多方面綜合因

10、素。上述各因素所形成的約束，極為復(fù)雜繁瑣，并且難以直接應(yīng)用于圖論知識(shí)中。特點(diǎn)三：數(shù)據(jù)（信息）的海量化。我們要研究的北京市公交系統(tǒng)，共有公交線路520條，站點(diǎn)3957個(gè)，單條線路對(duì)應(yīng)站點(diǎn)約5060個(gè)。而且，線路與站點(diǎn)間的對(duì)應(yīng)關(guān)系復(fù)雜，再考慮到換乘情況，運(yùn)用現(xiàn)有的迪杰斯特拉（Dijkstra）、弗羅伊德（Floyd）等圖論算法，其時(shí)間復(fù)雜度分別和。在目前的計(jì)算機(jī)運(yùn)行速度下，這種處理方法是難以快速實(shí)現(xiàn)的，已無法保障 “自動(dòng)問路機(jī)”所要求的實(shí)時(shí)快速性。5問題一1. 模型的分析 設(shè)城市公交系統(tǒng)共有個(gè)站點(diǎn)，(本問題中)，條公交線路，設(shè)站點(diǎn)和線路通過一個(gè)3維的0-1矩陣來表達(dá)。設(shè) 這樣該城市的公交網(wǎng)絡(luò)通過該

11、0-1矩陣能完全表達(dá)。 設(shè)決策變量為，意義為：則當(dāng)站點(diǎn)i和j之間無第k條線路時(shí)，i和j之間則不能通過第k條線路到達(dá)，因此有： (1)設(shè)起始點(diǎn)為a,目標(biāo)點(diǎn)為b，我們目的是在在a和b之間插入r個(gè)站點(diǎn)，使得a,b構(gòu)成一個(gè)可到達(dá)的線路。即： (2)目標(biāo)函數(shù)我們考慮費(fèi)用最小，時(shí)間最小和換乘次數(shù)最小三個(gè)目標(biāo)。設(shè)，表示線路是否需要通過換乘。當(dāng)則線路不換乘；當(dāng)則線路換乘。則換乘次數(shù)最少的目標(biāo)為要求時(shí)間最小，則有：其中為經(jīng)過站點(diǎn)數(shù)，為坐車時(shí)間；表示換乘時(shí)間.二者之和為總時(shí)間. 設(shè)線路a,b計(jì)算得到費(fèi)用為Cost,計(jì)算方法根據(jù)一元制和分段計(jì)價(jià)制度的規(guī)則進(jìn)行計(jì)算。 總費(fèi)用最小的目標(biāo)函數(shù)為：最后得到的總模型為：換乘次

12、數(shù)最少 時(shí)間最少費(fèi)用最小 (3)對(duì)該模型的求解，我們可以根據(jù)換乘次數(shù)最少得到最優(yōu)結(jié)果，也可以根據(jù)時(shí)間最少得到最優(yōu)結(jié)果，還也可以根據(jù)費(fèi)用最少得到最優(yōu)結(jié)果.把三種情況下的最好結(jié)果都可以提供給顧客考慮，由顧客根據(jù)自己的需要選擇。當(dāng)然有的結(jié)果會(huì)是兩種或三種目標(biāo)最小情況下的解，這樣就更好。但直接利用該模型比較難求解，因此我們考慮搜索的方法快速得到結(jié)果，以滿足公交線路查詢的實(shí)時(shí)性要求。 2換乘次數(shù)分析對(duì)城市公交系統(tǒng)，乘客通常選擇直達(dá)，不能直接到達(dá)則考慮換乘，而換乘則盡量少換乘。因此對(duì)乘客來說，盡量少換乘是一個(gè)很重要的參考指標(biāo)。因此我們首先對(duì)該城市的公交網(wǎng)絡(luò)系統(tǒng)進(jìn)行換乘次數(shù)的分析。 設(shè)城市公交系統(tǒng)共有個(gè)站點(diǎn)

13、，(本問題中)，條公交線路，考察任意兩個(gè)站點(diǎn)和之間換乘車次數(shù)。定義鄰接矩陣如下： 當(dāng)后，說明該兩站點(diǎn)不需要換乘就可以到達(dá)。利用原來的條公交線路，計(jì)算每條線路上的站點(diǎn)，容易得到鄰接矩陣，該矩陣是對(duì)稱的，統(tǒng)計(jì)上三角中1的個(gè)數(shù)，則得到不需要換乘就可以到達(dá)的站點(diǎn)對(duì)。計(jì)算,其中*運(yùn)算與矩陣乘法相同，但其中數(shù)字的加法與乘法按布爾法則進(jìn)行:即： 則仍然是0-1矩陣，其元素表示站點(diǎn)和通過一次換乘可以到達(dá)；表示站點(diǎn)和通過一次換乘不能到達(dá)。 依此類推，仍然是0-1矩陣，其元素表示站點(diǎn)和通過次換乘可以到達(dá)；表示站點(diǎn)和通過次換乘不能到達(dá)。 在該計(jì)算過程中，我們還可以得到任意兩個(gè)站點(diǎn)最少需要經(jīng)過換乘的次數(shù)。方法如下：

14、若，而，則站點(diǎn)和需要經(jīng)過次換乘才能到達(dá)。對(duì)問題在1中給出的6對(duì)站點(diǎn)，我們很容易得到最少換乘次數(shù),結(jié)果為： 表1 6條站點(diǎn)換乘次數(shù)線路換乘次數(shù)S3359S18281S1557S04812S0971S04851S0008S00731S0148S04852S0087S36761為對(duì)所有的站點(diǎn)對(duì)需要換乘次數(shù)我們進(jìn)行完整分析，我們利用C語(yǔ)言編程，由于太大，利用動(dòng)態(tài)分配內(nèi)存的方式，實(shí)現(xiàn)了該矩陣的賦值與乘法。我們可以計(jì)算出經(jīng)過1次，2次換乘等到達(dá)目的地的站點(diǎn)對(duì)。而總站點(diǎn)對(duì)，由此我們可以計(jì)算出經(jīng)過1次，2次等換乘到達(dá)目的地的站點(diǎn)對(duì)的百分比，結(jié)果如下：表2 換乘次次數(shù)的統(tǒng)計(jì)換乘情況直接到達(dá)1次換乘到達(dá)2次換乘到

15、達(dá)3次換乘到達(dá)站點(diǎn)對(duì)221751345982178250337826946占總站點(diǎn)對(duì)的百分比2.83%44.2%99.98%100%該結(jié)果說明換乘1次到達(dá)目的地的占44.2%，換乘2次到達(dá)目的地的占99.98%，而通過3次換乘則一定到達(dá)目的地。由此，我們提出按換乘次數(shù)進(jìn)行搜索的快速算法。 3按換乘次數(shù)搜索的快速算法 3.1 算法思想：設(shè)城市公交網(wǎng)絡(luò)系統(tǒng)共有個(gè)站點(diǎn)，公交線路有條。通過分析數(shù)據(jù)，得到本問題站點(diǎn)數(shù)。對(duì)線路，本問題中共有520條公交線路，當(dāng)把上下行看作不同的線路，而22條環(huán)線當(dāng)作單環(huán)，只當(dāng)一條線路處理，則這里有條線路。我們按換乘次數(shù)進(jìn)行搜索，設(shè)任意出發(fā)站和目的站點(diǎn)，當(dāng)?shù)娇梢灾苯拥竭_(dá)時(shí)則

16、直接到達(dá)，不能直接到達(dá)則搜索經(jīng)過1次換乘能到達(dá)的線路，統(tǒng)計(jì)每條線路上的所花時(shí)間，費(fèi)用值，輸出時(shí)間最少的線路和費(fèi)用值最小的線路。當(dāng)換乘1次不能到達(dá)，則考慮換乘2次，同樣輸出所有線路中時(shí)間最少的線路和費(fèi)用值最小的線路。以次類推，以換乘次數(shù)為步長(zhǎng)進(jìn)行搜索，一直進(jìn)行下去，一定可以得到換乘次數(shù)最少情況下時(shí)間最小的線路和費(fèi)用最小的線路。而對(duì)于本問題，前面已經(jīng)計(jì)算出，任意兩個(gè)站點(diǎn)間最多經(jīng)過3次換乘就可以到達(dá)。3.2 算法實(shí)現(xiàn) 1).數(shù)據(jù)預(yù)處理 從含有公交信息的數(shù)據(jù)文件中讀入數(shù)據(jù)，將每條線路包含的公交站點(diǎn)提取出來，保存在整型數(shù)組ALM中。由于每條線路站點(diǎn)數(shù)最多為86, 而線路總數(shù)作1018處理，因此可取L=1

17、018,M=86.A中每行保存的是一條線路的站點(diǎn)號(hào)。同時(shí)記錄每條線路的站點(diǎn)總數(shù)，保存在PL中。每條線路的票價(jià)信息保存在BL中，其中Bi=0表示第i條線路采用分段計(jì)價(jià)，Bi=1表示第i條線路采用單一票制1元.其它如上下行信息，每條線路對(duì)應(yīng)的原始車次號(hào)，也需要采用數(shù)組保存，便于后面計(jì)算。 該步是一個(gè)重要的預(yù)處理工作，將所有的車次和站點(diǎn)由字符串按原來數(shù)字次序編號(hào)，并完全采用數(shù)組保存，才便于后面的計(jì)算。2).搜索直接到達(dá)的線路固定起始點(diǎn)i和j，其中i為出發(fā)站點(diǎn)，j為目標(biāo)站點(diǎn)。若i和j都在A的第k個(gè)行向量中.且i在j前，則i可通過第k條線路到達(dá)j.，并統(tǒng)計(jì)該線路上產(chǎn)生的時(shí)間z2和費(fèi)用z1.若前面兩個(gè)條件

18、之一不滿足，則i不能通過第k 條線路到達(dá)j.循環(huán)執(zhí)行下一條線路。最后輸出費(fèi)用最小的線路和費(fèi)用最小的線路, 對(duì)應(yīng)完整線路(包括站點(diǎn)和車次).3)搜索換乘1次到達(dá)的線路 固定起始點(diǎn)i和目標(biāo)點(diǎn)j,循環(huán)執(zhí)行每個(gè)站點(diǎn).按前面方法判斷站點(diǎn)i能否直接到達(dá)站點(diǎn)k，同時(shí)判斷站點(diǎn)k能否直接到達(dá)站點(diǎn)j.統(tǒng)計(jì)每條i能直接到達(dá)k，k能直接到達(dá)j的線路.并計(jì)算該條以k為中轉(zhuǎn)站的線路的時(shí)間z2和費(fèi)用z1.共循環(huán)n次，就可以完成所有搜索.輸出費(fèi)用最小的線路和費(fèi)用最小的線路, 及對(duì)應(yīng)完整線路(包括站點(diǎn)和車次)。4) 搜索換乘2次到達(dá)的線路 固定起始點(diǎn)i和目標(biāo)點(diǎn)j,循環(huán)計(jì)算通過i的所有線路和通過j的所有線路。對(duì)通過i的某條線路r

19、，通過j的某條線路s，若線路r中存在站點(diǎn)x1, 線路s存在站點(diǎn)x2，使x1可由某條線路直接到達(dá)x2，則獲得一條iàx1àx2àj的換乘兩次的線路。其中x1和x2為中轉(zhuǎn)站。對(duì)通過i的所有線路，通過j的所有線路進(jìn)行循環(huán)執(zhí)行，且判斷兩條線路上的站點(diǎn)能否直接到達(dá)，就可以得到所有有兩個(gè)中轉(zhuǎn)站的線路，計(jì)算每條這樣線路的時(shí)間z2和費(fèi)用z3，最后輸出時(shí)間最少的線路和費(fèi)用最小的線路及對(duì)應(yīng)完整線路(包括站點(diǎn)和車次).5)搜索換乘d次()到達(dá)的線路 固定起始點(diǎn)i和目標(biāo)點(diǎn)j，任意取d個(gè)站點(diǎn)，判斷i能否直接到達(dá),能否直接到達(dá)，能否直接到達(dá)，能否直接到達(dá)j.若以上每條線路都可以直接到達(dá)，則獲

20、得一條iàà-.àj的線路。循環(huán)取，則可獲得所有經(jīng)過d次換乘的線路，最后輸出時(shí)間最少的線路和費(fèi)用最小的線路及對(duì)應(yīng)完整線路(包括站點(diǎn)和車次)。3.3 算法分析 1）直接到達(dá)搜索步數(shù) 該搜索方法只需要對(duì)固定的i和j點(diǎn)，搜索所有線路即可。因此搜索的線路數(shù)為L(zhǎng).2) 換乘1次搜索步數(shù) 該算法采用對(duì)通過i的所有線路和通過j的所有線路進(jìn)行求交，若兩條線路有交點(diǎn)，則可通過換乘一次完成。設(shè)通過i的線路總數(shù)為，通過j的線路總數(shù)為，則只需要進(jìn)行次線路求交即可.計(jì)算量很小。3) 換乘2次搜索步數(shù)該算法采用對(duì)通過i的所有線路和通過j的所有線路進(jìn)行處理.設(shè)通過i的線路總數(shù)為，通過j的線路總

21、數(shù)為，通過的條線路包含的站點(diǎn)數(shù)分別為，通過j的條線路包含的站點(diǎn)數(shù)分別為，過i的每條線路上的每個(gè)站點(diǎn)和過j的每條線路上的每個(gè)站點(diǎn)判斷能否直接到達(dá)，則搜索的線路數(shù)為：:設(shè)每條線路包含的站點(diǎn)數(shù)最大為M,過每個(gè)站點(diǎn)的最大線路數(shù)為，則，則 考慮到實(shí)際問題，通常過每條線路的站點(diǎn)數(shù)不多，如本問題中最大為86，過每個(gè)站點(diǎn)的線路數(shù)也不大，如本問題中最多線路為64，最少為1,平均為7.7條。若直接任意采用選取兩個(gè)中轉(zhuǎn)點(diǎn)進(jìn)行枚舉，則搜索所有線路數(shù)為顯然，因此有：因此該算法比直接選用任意兩個(gè)中轉(zhuǎn)點(diǎn)進(jìn)行搜索速度快得多。4) 搜索換乘d次()到達(dá)的線路 由于要求換乘的次數(shù)較多，采用直接枚舉k個(gè)點(diǎn)作為換乘點(diǎn)進(jìn)行搜索。思想簡(jiǎn)

22、單，實(shí)現(xiàn)容易，但算法復(fù)雜性增大。其搜索線路數(shù)為：固定換乘次數(shù)d,搜索線路數(shù)為n和L的多項(xiàng)式，因此在算法上還是可行的。當(dāng)總站數(shù)和總線路數(shù)L比較大時(shí)，計(jì)算比較費(fèi)時(shí)。對(duì)本問題，由于最多經(jīng)過3次換乘，而且有99.98%的站點(diǎn)對(duì)可以通過最多兩次換乘就可以完成，因此本算法在實(shí)際中是可行的。特別是對(duì)直接到達(dá)，一次換乘，兩次換乘分別根據(jù)具體情況進(jìn)行特殊算法處理，實(shí)現(xiàn)速度完全可以滿足實(shí)時(shí)性要求。如對(duì)本問題在普通計(jì)算機(jī)上計(jì)算，一次換乘瞬間就可以完成，兩次換乘也不超過40秒就可以找到最優(yōu)線路。3.4 模型的求解與結(jié)果分析：我們采用操作靈活、功能強(qiáng)大的C語(yǔ)言工具進(jìn)行求解。上下行性質(zhì)1表示原線路是上行，上下行性質(zhì)2表示

23、原線路是下行S1 S3359S18281.起點(diǎn)3359,終點(diǎn)1828,站數(shù) 33,換乘次數(shù)1,時(shí)間101.0,費(fèi)用 3,線路號(hào) 3開始車次號(hào)436,上下行性質(zhì) 2,結(jié)束車次號(hào)217,上下行性質(zhì) 2,公共站點(diǎn)17843359 2026 1132 2266 2263 3917 2303 2301 3233 618 616 2112 2110 2153 2814 2813 3501 3515 3500 756 492 903 1768 955 480 2703 2800 2192 2191 1829 2.起點(diǎn)3359,終點(diǎn)1828,站數(shù) 23,換乘次數(shù)2,時(shí)間76.0,費(fèi)用 3,線路號(hào) 1開始車次號(hào)

24、15,上下行性質(zhì) 1,連接車次號(hào)201,上行行性質(zhì) 1,結(jié)束車次號(hào)41,上下行性質(zhì) 1,公共站點(diǎn)1327,17903359 2266 3917 2303 1327 1842 609 483 604 2650 3470 2619 2340 2182 992 2322 1770 1790 458 1792 1783 1671 1828 方案一換乘一次但時(shí)間為101分鐘，方案二換乘兩次，但時(shí)間減少為76分鐘，可供用戶選擇。S2 路線S1557S04811.起點(diǎn)1557,終點(diǎn)481,站數(shù) 33,換乘次數(shù)2,時(shí)間106.0,費(fèi)用 3,線路號(hào)257開始車次號(hào)363,上下行性質(zhì) 2,連接車次號(hào)189,上行行

25、性質(zhì) 2,結(jié)束車次號(hào)460,上下行性質(zhì) 2,公共站點(diǎn)1919,31861557 3158 2628 3408 2044 1985 2563 2682 2735 29 55 51 1919 2840 1402 3186 3544 2116 2119 1788 1789 1770 2322 992 2184 2954 3117 2424 1174 902 903 2101 481.S3: S0971S0485 1.起點(diǎn)971,終點(diǎn)485,站數(shù) 42,換乘次數(shù)1,時(shí)間128.0,費(fèi)用 3,線路號(hào) 4開始車次號(hào)13,上下行性質(zhì) 2,結(jié)束車次號(hào)417,上下行性質(zhì) 2,公共站點(diǎn)2184971 3832 3

26、341 2237 3565 3333 1180 3494 1523 1520 1988 1743 1742 1181 1879 3405 2517 3117 2954 531 2184 992 2322 1770 1789 2119 2116 3544 3186 3409 2717 1402 2840 643 2079 1920 2480 2482 2210 3332 3351 485 2. 起點(diǎn)971,終點(diǎn)485,站數(shù) 33,換乘次數(shù)2,時(shí)間106.0,費(fèi)用 3,線路號(hào)278開始車次號(hào)13,上下行性質(zhì) 1,連接車次號(hào)140,上行行性質(zhì) 2,結(jié)束車次號(hào)469,上下行性質(zhì) 1,公共站點(diǎn)1609,

27、2654971 3571 1609 3242 1481 3426 2553 3903 1553 3531 1967 12 2636 2113 2112 2833 618 1327 2303 2263 3037 2654 1729 3766 1691 1383 1381 1321 2019 2017 2159 772 485 方案一換乘一次但時(shí)間為128分鐘，方案二換乘兩次，但時(shí)間減少為106分鐘，可供用戶選擇.S4 S0008S00731. 起點(diǎn) 8,終點(diǎn)73,站數(shù) 27,換乘次數(shù)1,時(shí)間83.0,費(fèi)用 2,線路號(hào)21開始車次號(hào)159,上下行性質(zhì) 2,結(jié)束車次號(hào)58,上下行性質(zhì) 2,公共站點(diǎn)2

28、683 8 3412 2743 3586 2544 913 2953 3874 630 854 400 2633 3053 408 145 3138 2684 2683 291 3614 491 2559 990 3315 3898 1855 73 2 .起點(diǎn) 8,終點(diǎn)73,站數(shù) 21,換乘次數(shù)2,時(shí)間70.0,費(fèi)用 3,線路號(hào)13570開始車次號(hào)159,上下行性質(zhì) 2,連接車次號(hào)231,上行行性質(zhì) 3,結(jié)束車次號(hào)57,上下行性質(zhì) 1,公共站點(diǎn)630,609 8 3412 2743 3586 2544 913 2953 3874 630 854 88 609 483 604 2650 3470

29、 2619 2340 3162 2181 73 方案一換乘一次但時(shí)間為83分鐘，方案二換乘兩次，但時(shí)間減少為70分鐘，可供用戶選擇.S5、S0148S0485.起點(diǎn)148,終點(diǎn)485,站數(shù) 33,換乘次數(shù)2,時(shí)間106.0,費(fèi)用 3,線路號(hào)339開始車次號(hào)308,上下行性質(zhì) 1,連接車次號(hào)156,上行行性質(zhì) 1,結(jié)束車次號(hào)417,上下行性質(zhì) 2,公共站點(diǎn) 36,2210148 462 361 1797 2221 302 2222 2737 1716 128 2268 1308 1391 2272 36 3233 618 617 721 2057 2361 608 399 2535 2534 2

30、39 497 2090 2082 2210 3332 3351 485 S6、S0087S3676起點(diǎn)87,終點(diǎn)3676,站數(shù) 21,換乘次數(shù)1,時(shí)間65.0,費(fèi)用 2,線路號(hào) 1開始車次號(hào)454,上下行性質(zhì) 1,結(jié)束車次號(hào)209,上下行性質(zhì) 2,公共站點(diǎn)3496 87 857 630 1427 1426 541 978 3389 1919 641 2840 3496 1883 1159 2699 2922 3010 583 1987 82 3676 以第（1）隊(duì)：S3359S1828為例進(jìn)行分析，我們把得出的十一組換乘一次的數(shù)據(jù)在下表中列出，進(jìn)行比對(duì)分析。表 3. S3359S1828線路比

31、對(duì)表編號(hào)乘車耗時(shí)乘車費(fèi)用換乘次數(shù)1101.00312107.00313101.00314107.00315113.00316125.00317140.00318137.00319137.003110137.003111137.0031從表 1. S3359S1828線路比對(duì)表中，我們很容易看出，這十一組數(shù)據(jù)的換乘次數(shù)和乘車費(fèi)用均相同，而它們的乘車耗時(shí)則區(qū)別較大，從101.00分鐘到140.00分鐘不等，相差39分鐘，這說明不同線路間存在較大差距，通過比對(duì)得到的線路會(huì)在很大程度上為乘客節(jié)約時(shí)間或金錢。節(jié)約百分比可達(dá)到 由于數(shù)據(jù)比對(duì)效果明顯，我們很容易找出所需的換乘一次的三種最佳線路：1經(jīng)過簡(jiǎn)單計(jì)

32、算，我們很容易得出綜合最佳線路為：編號(hào)為1的線路和編號(hào)為3的線路。2顯然，耗時(shí)最少的線路是編號(hào)為1的線路和編號(hào)為3的線路，均耗時(shí)101.00分鐘。因此，耗時(shí)最佳線路為：編號(hào)為1的線路和編號(hào)為3的線路。3這十組數(shù)據(jù)的乘車費(fèi)用均相同，為3元。故這十組線路均為乘車費(fèi)用最佳線路。更多求解所得線路信息見附錄一。3.5）模型的優(yōu)缺點(diǎn)及改進(jìn)：模型的優(yōu)點(diǎn)：1. 在模型的建立中，引入了路線站點(diǎn)關(guān)系矩陣，清晰的給出了各線路與站點(diǎn)間的復(fù)雜關(guān)系；并且使公交路線單向化，便于算法的進(jìn)行；2. 模型建立合理，完整性、嚴(yán)密性均較高，思路清晰，原理簡(jiǎn)單易懂，易于推廣到其它場(chǎng)合；3. 本模型的算法與傳統(tǒng)圖論算法相比，便于數(shù)據(jù)的隨

33、時(shí)截取，因此，計(jì)算量極小。模型在運(yùn)用C語(yǔ)言編程進(jìn)行求解時(shí)，運(yùn)行時(shí)間在幾到幾十秒以內(nèi)，完全符合自主查詢計(jì)算機(jī)系統(tǒng)對(duì)實(shí)時(shí)性的要求。模型的缺點(diǎn)： 1. 建立模型時(shí)，我們做了大量的假設(shè)，沒有考慮堵車現(xiàn)象、排隊(duì)滯留現(xiàn)象、公交容量限制等因素，所建模型太過于理想化，參考數(shù)據(jù)較少，現(xiàn)實(shí)適用性受到一定程度的限制。2. 模型的完整嚴(yán)密性和算法的快速實(shí)現(xiàn)性是彼此矛盾的，建立本模型時(shí)，我們側(cè)重考慮了自主查詢計(jì)算機(jī)系統(tǒng)的實(shí)時(shí)應(yīng)用性，在一定程度上犧牲了嚴(yán)密性。以換乘次數(shù)為標(biāo)準(zhǔn)的數(shù)據(jù)截取規(guī)則，很容易導(dǎo)致為了追求換乘次數(shù)最少，而以犧牲全局費(fèi)用最佳或全局耗時(shí)最佳線路為代價(jià)的情況發(fā)生。3. 乘客選擇公交線路時(shí)的出發(fā)點(diǎn)具有多樣性，

34、限于題中所提供條件，我們只主要考慮了出行費(fèi)用、出行耗時(shí)和換乘次數(shù)幾個(gè)方面，并沒有照顧到特殊人群的特殊需求，模型的建立人文色彩不夠濃。鑒于以上缺點(diǎn)，我們認(rèn)為可以從以下幾方面進(jìn)行模型的改進(jìn)：1. 應(yīng)當(dāng)搜集更為廣泛的數(shù)據(jù)，仔細(xì)考慮堵車、公路流量、公交容量等問題，引入堵車因子、流量額度、容量額度等控制量，建立更為貼近生活、更為實(shí)用的模型。2. 尋求嚴(yán)密度和算法的快速可實(shí)現(xiàn)性結(jié)合度更高的模型，對(duì)公交線路選擇問題進(jìn)行更高質(zhì)量的求解。3. 考慮特殊人群的特殊需求，根據(jù)殘疾人、孕婦、體弱者、病人等的不同需求，建立適合不同人群的公交線路選擇模型。6問題二1一般模型分析：對(duì)本問題，主要是在公交線路的系統(tǒng)中再添加了

35、地鐵系統(tǒng).我們考慮增加線路的方法將兩種系統(tǒng)合并在一起。 這里我們考慮一種標(biāo)準(zhǔn)線路。對(duì)標(biāo)準(zhǔn)線路，主要滿足三個(gè)性質(zhì)：性質(zhì)1: 每條線路上從任意一點(diǎn)i出發(fā)到另一點(diǎn)j，可計(jì)算時(shí)間，費(fèi)用.性質(zhì)2 任意兩條線路之間有換乘時(shí)間特性具有這兩個(gè)性質(zhì)的線路就可以稱為一個(gè)標(biāo)準(zhǔn)線路。對(duì)公交系統(tǒng)，不管是采用單一的一元制還是分段計(jì)價(jià)，都可以計(jì)算出任意兩點(diǎn)間的時(shí)間和費(fèi)用.任意兩個(gè)公交線路的換乘時(shí)間為5分種.對(duì)地鐵系統(tǒng)，對(duì)每條線路T1或T2上都可以計(jì)算出從任意一點(diǎn)i出發(fā)到另一點(diǎn)j的費(fèi)用(這里固定為3元)，時(shí)間，兩條地鐵線之間換乘時(shí)間為4分鐘。對(duì)地鐵線T1(分上下行)，環(huán)行線T2，都是標(biāo)準(zhǔn)線路，因此對(duì)地鐵可增加3條線路.在考慮

36、地鐵連接的公交站點(diǎn)。設(shè)某地鐵D與k個(gè)公交站點(diǎn)相連。則地鐵和公交站點(diǎn)之間可以連接，公交和之間也可以連接。根據(jù)前面標(biāo)準(zhǔn)線路的特性，我們?cè)黾觾煞N線路，一種是地鐵和公交站之間的線路，另一種是公交和之間連接線路。對(duì)線路D和，作為一種新的線路，該線路上時(shí)間為地鐵換乘公汽時(shí)間，費(fèi)用為0，與其它線路間換乘次數(shù)為0；對(duì)線路和D，該線路上時(shí)間為公汽換乘地鐵時(shí)間，費(fèi)用為0。對(duì)和線路，時(shí)間為公汽換公汽時(shí)間，費(fèi)用為0.與其它線路間換乘次數(shù)為0。這樣，從前面模型考慮，增加地鐵系統(tǒng)后，實(shí)際上相當(dāng)于增加了三種線路：地鐵到地鐵線路，地鐵和公汽站之間線路，公汽站和公汽站之間的線路。每條線路上有了特有的時(shí)間和費(fèi)用信息。因此，從模型

37、上，只是增加了許多線路。在問題一中，只要添加反映交通網(wǎng)絡(luò)系統(tǒng)的0-1矩陣A，同時(shí)將時(shí)間和費(fèi)用按新增線路考慮就可以了。我們?cè)敿?xì)來考慮如何把地鐵線路轉(zhuǎn)化為公汽線路的問題。地鐵除了自身具有能駛經(jīng)沿途各站點(diǎn)（D01、D02等）的特性外，它還具有連接不同公汽站點(diǎn)的特性。以地鐵線路T1為例，它的前幾個(gè)地鐵站點(diǎn)可連接的公汽站點(diǎn)為：D01：S0567，S0042，S0025D02：S1487D03：S0303，S0302D04：S0566D05：S0436，S0438，S0437，S0435我們可以把地鐵線路T1看作是一條下圖所示的公交線路，即把地鐵站點(diǎn)連接的公汽站點(diǎn)穿插到地鐵線路中；在穿插后的地鐵線路中，同

38、一地鐵站點(diǎn)對(duì)應(yīng)的不同公汽站點(diǎn)間的行程出行耗時(shí)和出行費(fèi)用記為零，就是說，計(jì)算地鐵站點(diǎn)間的耗時(shí)和費(fèi)用時(shí)，僅以經(jīng)過的DXX字樣為準(zhǔn)。這樣的處理后，我們就可以把地鐵線路看成是一條的公交線路來研究了。用同樣的方法，我們可以把地鐵線路T2看作另一條公交線路。需要注意的是：1. 找出可行路線后，計(jì)算直達(dá)站點(diǎn)間出行費(fèi)用時(shí)，要在原有公式式（1）和式（2）的基礎(chǔ)上增加以下公式乘坐地鐵線路時(shí)費(fèi)用 乘坐地鐵線路時(shí)時(shí)間 2. 計(jì)算總的出行費(fèi)用時(shí)，綜合進(jìn)行求解：但是，在計(jì)算總的出行耗時(shí)時(shí)， 其中，一.、分別表示在相應(yīng)情形下公汽換公汽、地鐵換地鐵、地鐵換公汽、公汽換地鐵的次數(shù)。二上述式中，1、2、3、的取值規(guī)定仍為：如果0

39、1，則1230；如果11，則0230；如果21，則0130。=1表示由A到達(dá)B的最少換乘次數(shù)為i. 3. 對(duì)于同一地鐵站點(diǎn)對(duì)應(yīng)的不同公汽站點(diǎn)間的換乘，如D01：S0567，S0042，S0025中，S0567和S0042間進(jìn)行換乘時(shí)，應(yīng)按照公汽換乘公汽耗時(shí)進(jìn)行計(jì)算。在修改了上述計(jì)算公式的基礎(chǔ)上，我們?nèi)源_立三個(gè)最佳目標(biāo)模型： 綜合最佳線路模型： 采用指數(shù)加權(quán)法，建立綜合最佳線路模型如下 、分別表示通過線路由起始站點(diǎn)A到達(dá)目標(biāo)站點(diǎn)B時(shí)，所需的出行耗時(shí)和出行費(fèi)用。注：權(quán)重值、由層次分析法求得分別為0.5，0.5。 耗時(shí)最佳線路模型： 表示選取可選擇線路中耗時(shí)最少的線路。 費(fèi)用最佳線路模型： 表示選取

40、可選擇線路中費(fèi)用最少的線路。2. 算法描述與分析前面的一般模型不適于求解，從快速系統(tǒng)的實(shí)時(shí)性要求出發(fā)，我們考慮根據(jù)這個(gè)特殊問題采用快速搜索的算法來完成。我們的思想是根據(jù)問題一的算法計(jì)算出只采用公汽系統(tǒng)在三個(gè)目標(biāo)：換乘次數(shù)最少，時(shí)間最少，費(fèi)用最小的線路。再計(jì)算一定采用地鐵的最優(yōu)線路。因此我們這里的算法只考慮一定采用地鐵的方式。在這里，我們考慮的線路分四種：第一種：地鐵到地鐵直接到達(dá)目標(biāo)點(diǎn)第二種：地鐵到地鐵，地鐵到公交到達(dá)目標(biāo)點(diǎn)第三種：公汽到地鐵，地鐵到地鐵到達(dá)目標(biāo)點(diǎn)第四種：公汽到地鐵，地鐵到地鐵，地鐵到公交。步驟0：四種方式下都需要計(jì)算地鐵任意兩點(diǎn)間花費(fèi)的時(shí)間和費(fèi)用。由于地鐵線路很少，任意兩點(diǎn)間

41、的路線，花費(fèi)時(shí)間和費(fèi)用都很容易算出，因此我們首先在程序中計(jì)算出反應(yīng)地鐵任意兩點(diǎn)間信息的時(shí)間矩陣Time3939和費(fèi)用矩陣Cost3939. 步驟1：判斷起始點(diǎn)i和目標(biāo)點(diǎn)j是否都連接地鐵，若是，則調(diào)用步驟0中坐地鐵兩點(diǎn)間花費(fèi)的時(shí)間和費(fèi)用，總時(shí)間加上起始點(diǎn)i步行到地鐵站的時(shí)間及等待時(shí)間6分鐘，同時(shí)加上出地鐵到目標(biāo)站j的時(shí)間4分鐘，費(fèi)用則為地鐵費(fèi)用3元。步驟2：若起始點(diǎn)i和地鐵D點(diǎn)相連，目標(biāo)點(diǎn)不和地鐵相連，則搜索和地鐵D點(diǎn)相連的所有地鐵站對(duì)應(yīng)的公汽站，判斷能否一次到達(dá)，兩次到達(dá)。統(tǒng)計(jì)換乘次數(shù)z1，計(jì)算所有線路的時(shí)間z2和費(fèi)用z3.輸出,輸出最優(yōu)值和對(duì)應(yīng)線路。步驟3：若起始點(diǎn)i和地鐵不相連，目標(biāo)點(diǎn)和地

42、鐵相連，則搜索起始點(diǎn)經(jīng)過一次或兩次換到達(dá)地鐵站的線路，然后調(diào)用坐地鐵的時(shí)間矩陣Time3939和費(fèi)用矩陣Cost3939獲得坐地鐵的時(shí)間和費(fèi)用。統(tǒng)計(jì)換乘次數(shù)z1，計(jì)算所有線路的時(shí)間z2和費(fèi)用z3.輸出,輸出最優(yōu)值和對(duì)應(yīng)線路。步驟4：若起始點(diǎn)i和地鐵站不相連，目標(biāo)點(diǎn)j和地鐵也不相連.則對(duì)地鐵所有站點(diǎn)包含的公汽站點(diǎn)進(jìn)行搜索，判斷起始點(diǎn)能否一次到達(dá)地鐵相連的公汽站點(diǎn)，若一次不行則兩次；對(duì)地鐵和目的站j也采用同樣方法搜索，每連通一次則獲得一條從公汽到地鐵，地鐵到地鐵，地鐵到公交的線路。統(tǒng)計(jì)換乘次數(shù)z1，計(jì)算所有線路的時(shí)間z2和費(fèi)用z3.輸出,輸出最優(yōu)值和對(duì)應(yīng)線路。按照以上五個(gè)步驟，總可以算出換乘次數(shù)，

43、時(shí)間和費(fèi)用最優(yōu)的線路。 該方法對(duì)編制程序較為繁瑣，我們采用C語(yǔ)言編程，實(shí)現(xiàn)了該算法，在普通電腦上不到10秒就算出了所給6 對(duì)站點(diǎn)在三個(gè)目標(biāo)下的最優(yōu)值。 對(duì)本問題，由于地鐵站數(shù)少，只有39站，與所有地鐵相連的公汽站也少，只用 117站，因此對(duì)地鐵相連的所有公汽站是否能一次到達(dá)起始點(diǎn)或目標(biāo)點(diǎn)，搜索量都不大，因此總的計(jì)算時(shí)間很少，每搜索一對(duì)點(diǎn)12秒即可，可以滿足實(shí)時(shí)性要求。3. 計(jì)算結(jié)果與分析 運(yùn)用C語(yǔ)言編程進(jìn)行求解。S1. 路線3359,1828 (公交地鐵各換1次40條可到達(dá)線路)1.起點(diǎn)3359,終點(diǎn)1828,站數(shù) 33,換乘次數(shù)1,時(shí)間101.0,費(fèi)用 3,線路號(hào) 3開始車次號(hào)43

44、6,上下行性質(zhì) 2,結(jié)束車次號(hào)217,上下行性質(zhì) 2,公共站點(diǎn)17843359 2026 1132 2266 2263 3917 2303 2301 3233 618 616 2112 2110 2153 2814 2813 3501 3515 3500 756 492 903 1768 955 480 2703 2800 2192 2191 18292.起點(diǎn)3359-中轉(zhuǎn)站3068-地鐵站 8-地鐵站34-中轉(zhuǎn)站578-目的站1828, 公交總站數(shù) 20,總時(shí)間101.0,總費(fèi)用 5,地鐵時(shí)間34.0,地鐵站數(shù) 12,編號(hào) 9開始車次號(hào)15,上下行性質(zhì) 1,結(jié)束車次號(hào)167,上下行性質(zhì) 23

45、359 2266 3917 2303 1327 3068 578 3095 96 95 1193 105 1194 1189 2801 590 1240 1241 1784 1828 方案2乘坐地鐵后，時(shí)間沒有減少，但費(fèi)用增加兩元，因此選擇方案1S2 路線S1557S0481 (公交地鐵各換1次54條可到達(dá)線路)起點(diǎn)1557-中轉(zhuǎn)站978-地鐵站32-地鐵站24-中轉(zhuǎn)站537-目的站481, 公交總站數(shù) 29,總時(shí)間116.5,總費(fèi)用 5,地鐵時(shí)間22.5,地鐵站數(shù) 9,編號(hào)50開始車次號(hào)84,上下行性質(zhì) 2,結(jié)束車次號(hào)516,上下行性質(zhì) 11557 3158 2628 3408 2044 1

46、985 2563 2682 28 29 55 51 1919 3389 978 537 2651 3013 1808 1173 910 3517 453 2424 1174 902 903 2101 481 S3: S0971S04851.起點(diǎn)971,終點(diǎn)485,站數(shù) 42,換乘次數(shù)1,時(shí)間128.0,費(fèi)用 3,線路號(hào) 4開始車次號(hào)13,上下行性質(zhì) 2,結(jié)束車次號(hào)417,上下行性質(zhì) 2,公共站點(diǎn)2184971 3832 3341 2237 3565 3333 1180 3494 1523 1520 1988 1743 1742 1181 1879 3405 2517 3117 2954 531

47、 2184 992 2322 1770 1789 2119 2116 3544 3186 3409 2717 1402 2840 643 2079 1920 2480 2482 2210 3332 3351 485 2. 起點(diǎn)971,終點(diǎn)485,站數(shù) 33,換乘次數(shù)2,時(shí)間106.0,費(fèi)用 3,線路號(hào)278開始車次號(hào)13,上下行性質(zhì) 1,連接車次號(hào)140,上行行性質(zhì) 2,結(jié)束車次號(hào)469,上下行性質(zhì) 1,公共站點(diǎn)1609,2654971 3571 1609 3242 1481 3426 2553 3903 1553 3531 1967 12 2636 2113 2112 2833 618 13

48、27 2303 2263 3037 2654 1729 3766 1691 1383 1381 1321 2019 2017 2159 772 485 3.起點(diǎn)971-中轉(zhuǎn)站567-地鐵站 1-地鐵站21-中轉(zhuǎn)站466-目的站485, 公交總站數(shù) 13,總時(shí)間96.0,總費(fèi)用 5,地鐵時(shí)間50.0,地鐵站數(shù) 20,編號(hào) 9開始車次號(hào)94,上下行性質(zhì) 1,結(jié)束車次號(hào)51,上下行性質(zhì) 1971 3571 1609 345 1419 2389 567 466 3189 2810 2385 71 485 方案1換乘一次但時(shí)間為128分鐘，方案2換乘兩次，但時(shí)間減少為106分鐘，方案3采用坐地鐵，時(shí)間為

49、96分鐘，但費(fèi)用由3元增加為5元，可供用戶選擇. S4: S0008S00731. 起點(diǎn) 8,終點(diǎn)73,站數(shù) 27,換乘次數(shù)1,時(shí)間83.0,費(fèi)用 2,線路號(hào)21開始車次號(hào)159,上下行性質(zhì) 2,結(jié)束車次號(hào)58,上下行性質(zhì) 2,公共站點(diǎn)2683 8 3412 2743 3586 2544 913 2953 3874 630 854 400 2633 3053 408 145 3138 2684 2683 291 3614 491 2559 990 3315 3898 1855 73 2 .起點(diǎn) 8,終點(diǎn)73,站數(shù) 21,換乘次數(shù)2,時(shí)間70.0,費(fèi)用 3,線路號(hào)13570開始車次號(hào)159,上下

50、行性質(zhì) 2,連接車次號(hào)231,上行行性質(zhì) 3,結(jié)束車次號(hào)57,上下行性質(zhì) 1,公共站點(diǎn)630,609 8 3412 2743 3586 2544 913 2953 3874 630 854 88 609 483 604 2650 3470 2619 2340 3162 2181 73 3.起點(diǎn) 8-中轉(zhuǎn)站2534-地鐵站15-地鐵站12-中轉(zhuǎn)站609-目的站73, 公交總站數(shù) 17,總時(shí)間65.5,總費(fèi)用 5,地鐵時(shí)間 7.5,地鐵站數(shù) 3,編號(hào)98開始車次號(hào)200,上下行性質(zhì) 1,結(jié)束車次號(hào)57,上下行性質(zhì) 1 8 3412 2743 2544 2953 778 2534 609 483 6

51、04 2650 3470 2619 2340 3162 2181 73 方案1換乘一次但時(shí)間為83分鐘，方案2換乘兩次，但時(shí)間減少為70分鐘，方案3采用坐地鐵，時(shí)間為65.5分鐘，但費(fèi)用增加為5元，可供用戶選擇.S5: S0148S04851.起點(diǎn)148,終點(diǎn)485,站數(shù) 33,換乘次數(shù)2,時(shí)間106.0,費(fèi)用 3,線路號(hào)339開始車次號(hào)308,上下行性質(zhì) 1,連接車次號(hào)156,上行行性質(zhì) 1,結(jié)束車次號(hào)417,上下行性質(zhì) 2,公共站點(diǎn) 36,2210148 462 361 1797 2221 302 2222 2737 1716 128 2268 1308 1391 2272 36 3233

52、 618 617 721 2057 2361 608 399 2535 2534 239 497 2090 2082 2210 3332 3351 4852.起點(diǎn)148-中轉(zhuǎn)站1487-地鐵站 2-地鐵站21-中轉(zhuǎn)站466-目的站485, 公交總站數(shù) 11,總時(shí)間87.5,總費(fèi)用 5,地鐵時(shí)間47.5,地鐵站數(shù) 19,編號(hào) 4開始車次號(hào)24,上下行性質(zhì) 2,結(jié)束車次號(hào)51,上下行性質(zhì) 1148 927 2830 2070 1487 466 3189 2810 2385 71 485 坐地鐵后，時(shí)間減少18.5分鐘，但費(fèi)用增加2元，可供用戶選擇。S6: S0087S36761. 起點(diǎn)87,終點(diǎn)3

53、676,站數(shù) 21,換乘次數(shù)1,時(shí)間65.0,費(fèi)用 2,線路號(hào) 1開始車次號(hào)454,上下行性質(zhì) 1,結(jié)束車次號(hào)209,上下行性質(zhì) 2,公共站點(diǎn)3496 87 857 630 1427 1426 541 978 3389 1919 641 2840 3496 1883 1159 2699 2922 3010 583 1987 82 36762 S0087-D27-D36-S3676. 時(shí)間為：2.5*10+10=35分鐘 費(fèi)用為：3元坐地鐵后，時(shí)間減少30分鐘，但費(fèi)用增加1元，可供用戶選擇。更多詳細(xì)結(jié)果見附錄二7問題三1）模型的分析 相對(duì)于問題一和問題二，這里引入了步行的方式。設(shè)任意兩個(gè)站點(diǎn)間的步行時(shí)間為.則相對(duì)于問題一和問題二中模型，我們?cè)僖胍环N新的線路。該線路共條，設(shè)站點(diǎn)i和j構(gòu)成一條步行線路，該線路