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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、原線路是下行S1 S3359S18281.起點3359,終點1828,站數(shù) 33,換乘次數(shù)1,時間101.0,費用 3,線路號 3開始車次號436,上下行性質(zhì) 2,結(jié)束車次號217,上下行性質(zhì) 2,公共站點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.起點3359,終點1828,站數(shù) 23,換乘次數(shù)2,時間76.0,費用 3,線路號 1開始車次號

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

25、性質(zhì) 2,結(jié)束車次號460,上下行性質(zhì) 2,公共站點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.起點971,終點485,站數(shù) 42,換乘次數(shù)1,時間128.0,費用 3,線路號 4開始車次號13,上下行性質(zhì) 2,結(jié)束車次號417,上下行性質(zhì) 2,公共站點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. 起點971,終點485,站數(shù) 33,換乘次數(shù)2,時間106.0,費用 3,線路號278開始車次號13,上下行性質(zhì) 1,連接車次號140,上行行性質(zhì) 2,結(jié)束車次號469,上下行性質(zhì) 1,公共站點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 方案一換乘一次但時間為128分鐘，方案二換乘兩次，但時間減少為106分鐘，可供用戶選擇.S4 S0008S00731. 起點 8,終點73,站數(shù) 27,換乘次數(shù)1,時間83.0,費用 2,線路號21開始車次號159,上下行性質(zhì) 2,結(jié)束車次號58,上下行性質(zhì) 2,公共站點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 .起點 8,終點73,站數(shù) 21,換乘次數(shù)2,時間70.0,費用 3,線路號13570開始車次號159,上下行性質(zhì) 2,連接車次號231,上行行性質(zhì) 3,結(jié)束車次號57,上下行性質(zhì) 1,公共站點630,609 8 3412 2743 3586 2544 913 2953 3874 630 854 88 609 483 604 2650 3470

29、 2619 2340 3162 2181 73 方案一換乘一次但時間為83分鐘，方案二換乘兩次，但時間減少為70分鐘，可供用戶選擇.S5、S0148S0485.起點148,終點485,站數(shù) 33,換乘次數(shù)2,時間106.0,費用 3,線路號339開始車次號308,上下行性質(zhì) 1,連接車次號156,上行行性質(zhì) 1,結(jié)束車次號417,上下行性質(zhì) 2,公共站點 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起點87,終點3676,站數(shù) 21,換乘次數(shù)1,時間65.0,費用 2,線路號 1開始車次號454,上下行性質(zhì) 1,結(jié)束車次號209,上下行性質(zhì) 2,公共站點3496 87 857 630 1427 1426 541 978 3389 1919 641 2840 3496 1883 1159 2699 2922 3010 583 1987 82 3676 以第（1）隊：S3359S1828為例進行分析，我們把得出的十一組換乘一次的數(shù)據(jù)在下表中列出，進行比對分析。表 3. S3359S1828線路比

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

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

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

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

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

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

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

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

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

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

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

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

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

44、6,上下行性質(zhì) 2,結(jié)束車次號217,上下行性質(zhì) 2,公共站點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.起點3359-中轉(zhuǎn)站3068-地鐵站 8-地鐵站34-中轉(zhuǎn)站578-目的站1828, 公交總站數(shù) 20,總時間101.0,總費用 5,地鐵時間34.0,地鐵站數(shù) 12,編號 9開始車次號15,上下行性質(zhì) 1,結(jié)束車次號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乘坐地鐵后，時間沒有減少，但費用增加兩元，因此選擇方案1S2 路線S1557S0481 (公交地鐵各換1次54條可到達線路)起點1557-中轉(zhuǎn)站978-地鐵站32-地鐵站24-中轉(zhuǎn)站537-目的站481, 公交總站數(shù) 29,總時間116.5,總費用 5,地鐵時間22.5,地鐵站數(shù) 9,編號50開始車次號84,上下行性質(zhì) 2,結(jié)束車次號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.起點971,終點485,站數(shù) 42,換乘次數(shù)1,時間128.0,費用 3,線路號 4開始車次號13,上下行性質(zhì) 2,結(jié)束車次號417,上下行性質(zhì) 2,公共站點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. 起點971,終點485,站數(shù) 33,換乘次數(shù)2,時間106.0,費用 3,線路號278開始車次號13,上下行性質(zhì) 1,連接車次號140,上行行性質(zhì) 2,結(jié)束車次號469,上下行性質(zhì) 1,公共站點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.起點971-中轉(zhuǎn)站567-地鐵站 1-地鐵站21-中轉(zhuǎn)站466-目的站485, 公交總站數(shù) 13,總時間96.0,總費用 5,地鐵時間50.0,地鐵站數(shù) 20,編號 9開始車次號94,上下行性質(zhì) 1,結(jié)束車次號51,上下行性質(zhì) 1971 3571 1609 345 1419 2389 567 466 3189 2810 2385 71 485 方案1換乘一次但時間為128分鐘，方案2換乘兩次，但時間減少為106分鐘，方案3采用坐地鐵，時間為

49、96分鐘，但費用由3元增加為5元，可供用戶選擇. S4: S0008S00731. 起點 8,終點73,站數(shù) 27,換乘次數(shù)1,時間83.0,費用 2,線路號21開始車次號159,上下行性質(zhì) 2,結(jié)束車次號58,上下行性質(zhì) 2,公共站點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 .起點 8,終點73,站數(shù) 21,換乘次數(shù)2,時間70.0,費用 3,線路號13570開始車次號159,上下

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

51、04 2650 3470 2619 2340 3162 2181 73 方案1換乘一次但時間為83分鐘，方案2換乘兩次，但時間減少為70分鐘，方案3采用坐地鐵，時間為65.5分鐘，但費用增加為5元，可供用戶選擇.S5: S0148S04851.起點148,終點485,站數(shù) 33,換乘次數(shù)2,時間106.0,費用 3,線路號339開始車次號308,上下行性質(zhì) 1,連接車次號156,上行行性質(zhì) 1,結(jié)束車次號417,上下行性質(zhì) 2,公共站點 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.起點148-中轉(zhuǎn)站1487-地鐵站 2-地鐵站21-中轉(zhuǎn)站466-目的站485, 公交總站數(shù) 11,總時間87.5,總費用 5,地鐵時間47.5,地鐵站數(shù) 19,編號 4開始車次號24,上下行性質(zhì) 2,結(jié)束車次號51,上下行性質(zhì) 1148 927 2830 2070 1487 466 3189 2810 2385 71 485 坐地鐵后，時間減少18.5分鐘，但費用增加2元，可供用戶選擇。S6: S0087S36761. 起點87,終點3

53、676,站數(shù) 21,換乘次數(shù)1,時間65.0,費用 2,線路號 1開始車次號454,上下行性質(zhì) 1,結(jié)束車次號209,上下行性質(zhì) 2,公共站點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. 時間為：2.5*10+10=35分鐘 費用為：3元坐地鐵后，時間減少30分鐘，但費用增加1元，可供用戶選擇。更多詳細(xì)結(jié)果見附錄二7問題三1）模型的分析 相對于問題一和問題二，這里引入了步行的方式。設(shè)任意兩個站點間的步行時間為.則相對于問題一和問題二中模型，我們再引入一種新的線路。該線路共條，設(shè)站點i和j構(gòu)成一條步行線路，該線路