乘公交看奧運

1、公交查詢系統(tǒng)最佳乘車方案研究與設計摘要本文主要利用改進的鄰接算法解決多需求下公交線路的選擇問題。本題建立模型求解后主要實現如下功能：用戶發(fā)出請求，系統(tǒng)優(yōu)先為用戶提供直達的公交線路，若無直達線路，分別為用戶提供轉乘次數最少、耗時最短、費用最低三種線路作為備選線路，同時，在相同換乘次數內，按照乘車時間由少到多為用戶提供多條相對較優(yōu)的乘車路線，并給出相應的乘車費用作為參考，由用戶自主選擇滿足其需求的乘車路線。問題一，依題意在數據處理階段將不同公交汽線路抽象化，建立站點間直達線路信息存儲結構元胞，基于直達線路數據庫構造站點間以直達線路數目為元素的鄰接矩陣，在鄰接矩陣構成的數據結構之上，考慮公汽線路不同

2、票價、線路等條件，采用改進的鄰接算法分別以轉乘次數最少、耗時最短、費用最低為目標進行全局最佳路線的求解。問題二，在問題一的基礎上考慮公汽與地鐵混排，將地鐵站點與周圍的公汽站點集抽象為同一新站點，把以上公汽線路站點映射為新站點，建立新的直達數據庫，結合地鐵費用、地鐵與公汽間的換乘時間以及兩者站間行駛時間等條件，將地鐵與公汽結合的問題轉化為問題一，采用改進的鄰接算法得到不同目標下的多種優(yōu)化方案。問題三，根據問題一與問題二基于換乘次數最少逐步分析目標選定最佳路線的模型，在知道所有站點之間的步行時間的基礎上，建立以步行代替短距離減少換乘次數和以步行鄰邊化減少出行用時的優(yōu)化數學模型，采用廣度優(yōu)先算法,改

3、進公交線路的路線選擇方案。本文中公交出行以達到用時短、費用低、換乘少等目標而涉及的公交線路安排問題可以歸結為不同權值含義下的最短路問題，作為運籌學與圖論中的經典優(yōu)化問題，本文所建立的數學模型與求解方法具有較強的現實意義。關鍵字： 直達數據庫 鄰接算法 步行鄰邊化 廣度優(yōu)先算法一、問題重述第29屆奧運會明年8月將在北京舉行，作為城市樞紐的公共交通承擔著非常重的運輸任務。近年來，北京市的公交系統(tǒng)有很大的發(fā)展，公交線路的條數和公交車數量在迅速增多，給人民生活帶來便利的同時，也面臨多條線路得選擇問題，有時出行往往還需要轉乘多輛公交車才能到達目的地。如何在短時間、換乘次數最少、成本最低的情況到達目的地，

4、是人們所關注的問題。因此，我們通過建立線路選擇的模型與算法，設計一套自主查詢計算機系統(tǒng)，查詢到出行時所需的最佳公交路線及換乘方法，給人們出行節(jié)約更多的時間和金錢。要求：1. 僅考慮公汽線路，建立任意兩公汽站點之間線路選擇問題的數學模型與算法。并求出以下6對起始站終到站之間的最佳路線。（1）S3359S1828 （2）S1557S0481 （3）S0971S0485（4）S0008S0073 （5）S0148S0485 （6）S0087S36762. 同時考慮公汽與地鐵線路，解決1中問題。3. 如果所有站點間的步行時間已知，建立任意兩站點間路線選擇問題的數學模型。二、問題分析2.1 受限條件分析

5、2.1.1 約束條件繁瑣度高1公交線路中的票價問題分為單一票制和分段計價兩種不同情況；2耗時問題分為站點耗時和換乘耗時兩類；3最短路徑已非傳統(tǒng)意義上距離的最短化，需要綜合考慮所經站點數、步行距離和換乘次數等多方面因素。上述各種因素所形成的約束使本問題并非常見圖論問題，難以直接應用圖論知識解決。 數據（信息）量大所研究的北京市公交系統(tǒng)，共有公汽線路520條，站點3957站，單條線路對應站點約5060個；地鐵線路2條，站點39站。線路與站點間的對應關系復雜，考慮換乘情況，運用現有的Dijkstra、Floyd等圖論算法，處理該數量級數據量，時空復雜度高，時效性低，不能滿意解決本問題。2.2 乘客選

6、擇線路分析乘客需求的多樣化乘客在進行公交路線選擇時，考慮的因素多種多樣，有的乘客會側重考慮出行費用；有的乘客會側重考慮出行耗時；有的乘客（如老年人、殘疾人等）會側重考慮換乘次數；較為特殊的情況時，乘客還會根據個人喜好考慮途經站點、公交服務質量等多種因素?；谝陨隙鄻踊男枨笄闆r，針對公交線路選擇，本文確定以下三個目標：出行耗時最短、出行費用最少、換乘次數最少。 換乘次數無上界1統(tǒng)計計算附錄中數據，發(fā)現站點間換乘次數與到達率之間具有如下關系：圖1 站點間換乘次數與到達率關系圖表1 站點間換乘次數與到達率換乘次數012345到達率0.02530.40080.93930.99870.9999931分

7、析圖1/表1：直達線路覆蓋較少，僅為2.53%，但當換乘次數達到3次時，站點間到達率為99.87%，接近100%；換乘次數為5次時到達率為100%，故換乘三次已基本滿足乘客出行需求。2.對于本問題，容易想到通過不斷增加換乘次數以減少乘車時間或乘車距離，但是，查詢資料后得到北京公共交通集團關于乘客對換乘次數的接受率的統(tǒng)計圖表：圖2 乘客對換乘次數的接受率表2 乘客對換乘次數的接受率換乘次數012345接受率176.04%25.32%0.04%(7.02e-4)%0分析圖2/表2：幾乎沒有乘客接受4次換乘或更多次換乘的出行方案。從人性化角度考慮，不能無限次的增加換乘次數。因此本題僅考慮換乘次數最多

8、為3次的線路方案。2.3 問題分支分析2.3.1 問題一分析對于問題一，題目給出的公汽線路主要分為上下行線、原路折回線及環(huán)行線，線路不同，選擇不同，故對每種線路需要進行抽象化處理。站點較多，可以利用圖論知識描述該公交網絡：即將每個站點轉化為圖論中圖的每個節(jié)點，線路轉化為鄰接邊，在邊的信息中包含線路名、票價、行駛方向等。依據轉化思想將尋求不同目標下的問題轉化為圖論中不同有向賦權圖中內尋求最短路的問題。設計合適的算法在圖論中尋求三種目標下的最佳路線。2.3.2 問題二的分析對于問題二，對于兩條地鐵線路，依據問題一中的抽象化方法進行抽象化處理；對于地鐵站點，由地鐵與鄰近公汽站點可換乘的信息可知地鐵站

9、點及其周圍的公汽站點距離較近，考慮將其抽象化歸一為新的站點，減小站點差異性，重新構造站點間的鄰接矩陣?；趩栴}一更新數據，尋找合適的算法組合不同路線及站點分別給出三種目標下的最優(yōu)方案。 問題三的分析考慮公汽站點與地鐵站點的實際分布情況，在某些轉乘點存在步行小段距離再轉車可以節(jié)省時間或減少轉車次數的情況，在求解時需確定線路中該類選擇多樣化的站點，然后主要優(yōu)化該類站點后繼線路的選擇方案，達到以上三個目標。三、模型假設1、車站站點無重名； 2、相鄰站點間平均行駛時間一定； 3、公交運行順暢：無交通阻塞、無車輛故障、無道路交通事故等意外情況；4、公交準點到達，不考慮紅綠燈等待時間；5、各路線公交車發(fā)車

10、頻度相同；6、限制最多換乘車次為3次。四、符號說明符號符號說明相鄰公汽站平均行駛時間(包括停站時間)，為3分鐘相鄰地鐵站平均行駛時間(包括停站時間)，為2.5分鐘公汽換乘公汽平均耗時，為5分鐘(其中步行時間2分鐘) 地鐵換乘地鐵平均耗時，為4分鐘(其中步行時間2分鐘) 地鐵換乘公汽平均耗時，為7分鐘(其中步行時間4分鐘) 公汽換乘地鐵平均耗時，為6分鐘(其中步行時間4分鐘)從站點乘車到達站點站點到達站點所用的最少時間值（分鐘）站點到達站點的步行次數公汽單一票價1元公汽分段計價（020站：1元；2140站2元；40站以上：3元；=1,2,3）地鐵票價3元乘客總路程所花的時間乘客總路程所花的費用乘

11、客總路程經過的公交站數（不含起始站）乘客公汽換乘公汽的次數乘客總路程經過的地鐵站數（不含起始站）乘客公汽換乘地鐵的次數乘客地鐵換乘公汽的次數乘客乘坐的單一票價公交路線數乘客乘坐的分段公交路線數（分三個級別，=1,2,3）公汽的票價函數（元）整型函數 ，其值為1或0換車的兩站之間所隔的站臺數五、模型的建立與求解5.1 問題一 模型建立與求解本問題主要研究任意兩公汽站點間線路選擇的數學模型與算法。5.1.1 模型準備1、確定目標分別在不同行程需求下推薦最佳路線，根據實際情況得到以下三個目標：（1） 換乘次數最少；（2） 行程耗時最少；（3） 行程費用最少。2、對三種公汽線路進行抽象化處理（1）上、

12、下行線原路返回線路這種線路有兩個端點站，在兩個端點之間雙向行車，并且兩個方向上的行車路線相同，經過同樣的站點序列。由于線路的方向不同，故上行線和下行線抽象為兩條線路處理。（2）線路為環(huán)行線實際情況中環(huán)形路線一般是雙環(huán)，但在對這兩條線路進行抽象時，為保證任意兩站點距離最近，把每條線路抽象為兩條，即環(huán)形抽象為順時針2個半環(huán)、逆時針2個半環(huán)共計四條線路。（3）下行線與上行線經過站點不同由于下行線與上行線經過站點不同，該種線路顯然抽象為兩條不同線路。圖3 不同公汽線路的抽象化 3、換乘次數直觀化表示換乘次數可分為：(1) 換乘0次：直達；(2) 換乘1次；(3) 換乘2次；(4) 換乘3次；如下圖：圖

13、4 換乘次數的抽象化4、建立公汽直達信息庫：元胞結合公眾出行心理，優(yōu)先考慮兩站點之間是否有直達公汽線路，故在查詢系統(tǒng)內部需設有任兩站點的直達線路表，以方便查詢，當存在直達線路時直接輸出所有直達線路；若無直達線路，再搜索換乘路線，出于以上考慮，在系統(tǒng)內部需建立公汽直達信息庫。本問題共涉及3957 個公汽站點,站點信息量大，所以中的數據存儲結構的選擇非常重要：若采用數據矩陣存儲，操作復雜，存儲量大，轉而使用MATLAB 內建元胞結構建立，并利用陣列存儲站點間所有直達線路的信息。陣列數據存儲類型若使用雙精度實型，當部分陣列不存在直達信息時，該類型仍然占用存儲，總存儲量必將超過MATLAB內存限制，可

14、使用無符整型表示信息數據，當兩站點間信息陣列不存在直達信息時，不占用存儲，故縮小存儲減少系統(tǒng)讀取數據時間。具體元胞結構設計如下：Cell1,1Cell1,2車號耗時相隔站點數Cell1,3Cell2,1Cell2,2Cell2,3圖5 元胞示意圖上圖中Cell1,21行2列直達陣列描述了從站點S0001到站點S0002的所有直達線路信息，其中陣列中一頁內每行代表一條直達線路信息。 模型的建立需求過程如下描述：當輸入起點和終點后，根據處理數據后輸出直達線路，否則自動搜尋換乘次數最少的路線。若換乘次數相同情況下有多種轉乘方案，提供耗時最短轉乘路線（包括轉乘次數、行程總時間、轉乘站點及路線、行程總費

15、用）供查詢者自主選擇，同時系統(tǒng)可以向查詢者推薦“時間最短”“費用最省”“換乘次數最少”的不同目標下的最佳路線。建立兩站點間換乘線路數矩陣，方便用戶輸入起點與終點后，系統(tǒng)立即查詢出到達終點最少轉乘次數。統(tǒng)計中各陣列長度，得到任意兩站點的直達線路數目，構造以兩兩站點間直達路線數目為元素的直達線路數矩陣 ，通過矩陣運算得到任兩站點間換乘次數矩陣，從而可快速查詢任意兩站間所需的最少換乘次數。1、直達線路路數矩陣的建立根據，建立直達線路數矩陣，其矩陣元素表示站點到站點的直達線路數n，其中，當時為無效路徑，設定值為0，即： （1）以表示所有公汽所經過的站點總數，則直達線路數矩陣可表示為： （2）2、換乘線

16、路數矩陣直達矩陣為階方陣，矩陣中元素表示任意兩站點間通過1次換乘的路線數，即：=· （3）下面以中1行2列元素為例對中元素來源進行舉例說明：例： 假設上式中等號右邊僅，其余為0，說明1站點可直達到3站點，3站點可直達2站點，當=·后，即1站點通過一次換乘到達2站點，換乘點為站點3，則中元素表示站點到站點通過1次換乘的路線數由圖論與矩陣知識，可知如下推廣： ，為站點的直達路線數： （4）其中的元素表示通過n-1次換乘站點的線路數。3、最少換乘次數矩陣的建立引入矩陣，其矩陣元素為使得的（）的最小值，即： （5）則表示從站點必要的最少換乘次數，以矩陣表示最少換乘次數矩陣，則： （

17、6）其中，元素表示從站點必要的最少換乘次數基于最少換乘次數矩陣,每對起始站、終點站的最少換乘次數列出如下：表3 最少換乘次數表 線路編號 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 終到站 S1828 S0481 S0485 S0073 S0485 S3676 最少換乘 1 2 1 1 2 1 5.1.3 模型求解1、 算法步驟描述：step1:起點為，終點為，換乘次數為，直達即=0，非直達時利用鄰接矩陣 由條件改進查找路徑，經過站點為，記錄換乘次線路最小用時 ，中間線路信息從元胞中抽取，保存線路信息；若=3,轉至 step3，否則，

18、轉入step2。step2:，以min()（其中）為次換乘時間上界，轉至 step1；step3:結束，打印線路信息。2、約束條件描述：目標一：換乘次數最少： （7）目標二：線路用時最短僅考慮公汽路線的情況下，得到任意兩站站之間的最少乘車用時（包括初始站點的等待時間3min），即：最少用時=乘車時間+換乘時間 （8）所求的最短時間要受到如下的7個條件約束： （9）以上目標函數表示從站點到站點公汽線路中行使時間和換乘時間的總和，其中：（1）表示從站點到站點條線路所經過的站點數；（2）表示總的轉車次數；（3）表示出發(fā)站應滿足的條件，即乘客從某線路前往某站。（4）表示目的站應滿足的條件，即乘客從某線

19、路到達該站。（5）表示線路與某站點的關系，若線路不經過某站點，式子左右兩邊都為0，若線路經過某站點，則式子左右兩邊都為1。（6）分為以下幾種情況：1）假如線路沒有經過某站點，此時的值為0，同時的值也為0，中間的式子為0；2)假如線路經過某站點且沒有轉車（換乘），此時的值為1，同時的值也為1，中間的式子為0；3）假如線路經過某站點且有轉車（換乘）的情況，對于轉車前的線路，此時的值為1，同時的值也為0中間式子為1；對于轉車后的線路有的值為0，同時的值也為1，中間式子為-1。這三種情況的結果符合模型的換乘函數。目標三：最小費用本系統(tǒng)在選擇公汽線路時考慮花費，使到達目的地的花費最?。?（10）其中表示

20、線路從站點至站點中間所經過的站點數分析公汽線路票價，有票價函數： （11）基于以上各式，得以下目標函數： （12）以上算法實現見附錄。3、求解結果1）報表說明：目標：1,2,3,4,5,6分別表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676；換乘：換乘次數；時間：線路總計用時（分鐘）；站1：第1次換乘站點；站2：第2次換乘站點；站3：第3次換乘站點；線1：第1次乘坐的公汽線路；線2：第2次乘坐的公汽線路；線3：第3次乘坐的公汽線路；線4：第4次乘坐的公汽線路；費用：從始發(fā)站到目的站所需要的總費用（元）；程序：

21、MATLAB程序運行時間（秒）。2）換乘次數最少路線：表4 換乘次數最少路線方案目標換乘時間站1站2站3線1線2線3線4費用程序111041784-436167-34.62210919193186-84189460-361.8311312184-13417-3232.64186291-15958-2209.9186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-21862559-15958-31862633-159474-21862683-15958-21863053-159474-21863315

22、-15958-31863614-15958-21863917-355345-252109362210-308156417-363.92109363332-308156417-32109363351-308156417-361683496-454209-267.23）最短用時路線：表5 用時最短的路線方案目標換乘時間站1站2站3線1線2線3線4費用程序126717461784-324485167-34.626720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-3231021

23、91931869028418991254461.8310219193186903841899123943210625172159-13290469-3232.643666304835251592313281034209.9366630604525159231328103436663060952515923132810343668544835251592313281034366854604525159231328103436685460952515923132810343661383132752543232810343661691132752519823281034366172813275251

24、98140328103436622631327525355140328103436627554835253551732810343662755604525355173281034366275560952535517328103436637661327525198232810345310536042361221030881156417463.9310536042361333230881156417431053604236133513088115641746249884272123197367.24）費用最少路線：表 6 費用最少的路線方案目標換乘時間站1站2站3線1線2線3線4費用程序11104

25、1784-436167-34.626717461784-324485167-326720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-32210919193186-84189460-30.8311312184-13417-32.2210625172159-13290469-34186291-15958-20.0077186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-2186

26、2633-159474-21862683-15958-21863053-159474-21863614-15958-21863917-355345-252109362210-308156417-30.62109363332-308156417-32109363351-308156417-361683496-454209-20.0019以上表中已按換乘次數最少、出行用時最短、費用最少三個目標列出最優(yōu)出行路線方案，用戶只需要根據實際需要選取即可。結果分析分析以上報表：1、幾乎所有換乘3次的線路都可以以較短時間、較低的費用到達目的站點，說明選擇三次作為換乘次數的上限是可行的。2、考慮查詢系統(tǒng)的時效性

27、，給出MATLAB程序運行時間。由運行時間：查詢換乘次數小于1次含1次的線路，程序運行時間遠小于1秒；查詢換乘2次程序耗時不超過5秒；查詢換乘3次程序所需時間200秒左右。在實際情況中，乘客在乘車點等車時進行路線查詢，以上查詢時間是可以被乘客接受的。以上所述程序運行時間說明在本文描述的數據存儲結構下，改進的鄰接算法的可行性與較低的時間復雜度。綜述，模型I求解的線路方案集使用于不同需求下的所有用戶，具有較強的實用價值，很大程度上滿足了乘客乘車線路多樣化的需求。5.2 問題二的模型建立與求解5.2.1 模型準備1、兩種地鐵線路抽象處理基于對三種公汽線路路線的抽象方法，以相同的方法對兩地鐵線路T1、

28、T2進行抽象化處理：T1：雙向線路，根據不同的方向將其抽象為兩條單向行駛線路；T2：環(huán)行線路，根據公汽線路抽象方法化為4條行駛線路處理。2、歸一站點由題目給出的地鐵換乘公汽的數據可知：地鐵站點附近存在多個公汽站點。處于同一個地鐵站點附近的公汽站點地理位置應非常接近或容易換乘，定義這些站點為緊鄰站點，將緊鄰站點與對應的地鐵站點抽象為一個新的站點，減小這類站點的差異性。例如地鐵換乘公汽的數據首行“D01:S0567,S0042,S0025”,可認為這四個站點實際距離較近，為緊鄰站點，將五個站點做歸一處理，構造新站點,以上過程示意圖如下：圖6 可互換站點抽象為一個站點示意圖基于這種思想，在整個交通網

29、絡中將所有地鐵站點及其緊鄰站點分別做歸一站點處理。認為在新站點所代表的站點集中的任意站點可通過步行到達，且時間忽略。3、建立公汽、地鐵直達信息庫綜合考慮公汽與地鐵時建立的實質是新站點與新站點間的直達線路信息集。用戶輸入起點和終點后，系統(tǒng)內部先自動查找兩點所屬的新站點，然后查找新站點間可直達的線路，并給出起點及其附近站點直達終點及其附近站點的最佳乘車線路。采用與5.1相同的思路及方法，將已知的可直達公汽線路映射到，建立新的直達線路信息庫，結合地鐵費用與地鐵換乘公汽等待時間填充元胞內陣列描述的直達線路信息。具體元胞結構設計圖如下：Cell1,1Cell1,2車號耗時相隔站點數Cell1,3Cell

30、2,1Cell2,2Cell2,3圖7 直達線路信息庫（3996*3996）元胞結構示意圖上圖中Cell1,21行2列直達陣列描述了從站點S0001到站點S0002的所有直達線路信息，其中陣列中一頁內每行代表一條直達線路信息。5.2.2 模型建立需求過程如下描述：對于新站點，可等同看作問題一中的公汽站點，當用戶輸入起點和終點后，優(yōu)先顯示直達線路，否則自動搜尋轉乘線路，同時，系統(tǒng)向查詢者推薦不同目標下的最佳路線及轉乘方案?？紤]乘客可以乘坐地鐵，依據問題一中的模型，調整如下：1、乘客選擇的公交為公汽或地鐵，相應有變量： （13）表示公交經過t線路有i站點到達j站點。2、乘客由公汽轉乘地鐵，相應有變

31、量及約束條件： （14） （15）3、乘客由地鐵轉乘公汽，相應有變量及約束條件： （16） （17）4、乘客可由地鐵轉乘地鐵，相應有變量及約束條件： （18）5、乘客在公汽站可不換公汽、可轉乘公汽、可轉乘地鐵，三種選擇不同時進行，相應有變量及約束條件： （19）6、乘客在D12及D18地鐵站可不換地鐵線、可換乘公汽、可換乘地鐵線，三種選擇不同時進行，相應有變量及約束條件： （20）5.2.3 模型求解1、算法步驟描述：step1:起點為，終點為，換乘次數為，直達即=0，非直達時利用鄰接矩陣 由條件改進查找路徑，經過站點為，記錄換乘次線路最小用時 ，中間線路信息從元胞中抽取，保存線路信息；若=3

32、,轉至 step3，否則，轉入step2。step2:，以min()（其中）為次換乘時間上界，轉至 step1；step3:結束，打印線路信息。2、求解結果1）報表說明：目標：1,2,3,4,5,6分別表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676；換乘：換乘次數；時間：線路總計用時（分鐘）；站1：第1次換乘站點；站2：第2次換乘站點；站3：第3次換乘站點；線1：第1次乘坐公交路線；線2：第2次乘坐公交路線；線3：第3次乘坐公交路線；線4：第4次乘坐公交路線；費用：從始發(fā)站到目的地所需要的費用（元）；程序：

33、程序運行時間（秒）。2）換乘次數最少路線方案：表7 換乘次數最少路線方案目標換乘時間站1站2線1線2線3費用程序11140S0304L469L21737110S1241L436L167104S1784L436L16722115D20：S2079，S2933，S1919，S1921，S1920S0902L084L417L25432.2112D20：S2079，S2933，S1919，S1921，S1920S2424L084L417L254109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46031152S0872L119L41735.5134S0

34、992L013L417131S2184L013L41741110S0275L043L17035.686S0491L159L058283D13：S2633，S0399，S0401，S0400L159L47452109S0036S2210L308L156L41731.6106S3604D20：S2079，S2933，S1919，S1921，S1920L308L454L41791D02：S1487D20：S2079，S2933，S1919，S1921，S1920L02T001L417590.5D02：S1487D21：S0465，S0467，S0466，S0464L024T001L05156023T

35、00232.528T00228T0023）出行用時最短路線方案：表8 出行用時最短路線方案目標換乘時間站1站2線1線2線3費用程序1267S1746S1784L324L4851673722109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46032.23299D01：S0567，S0042，S0025D21：S0465，S0467，S0466，S0464L094T001L05155.54258D30：S3874，S1426，S1427D25：S0526，S0528，S0527，S0525L150T002L10355.652106S3604D20

36、：S2079，S2933，S1919，S1921，S1920L308L454L41731.66023T00232.54） 費用最少路線方案：表9 費用最少路線方案目標換乘時間站1站2線1線2線3費用程序1267S1746S1784L324L4851673722109D20：S2079，S2933，S1919，S1921，S1920S3186L084L189L46032.231131S2184L013L41735.54183D13：S2633，S0399，S0401，S0400L159L4748325.652106S3604D20：S2079，S2933，S1919，S1921，S1920L30

37、8L454L41731.66023T00232.5結果分析加入地鐵后，乘客有了更多的公交路線選擇，可以在換乘兩次之內到達任意目的站點，減少了換乘次數，優(yōu)化了交通網絡。5.3模型的建立與求解5.3.1 問題分析1、問題一與問題二啟發(fā)分析 將步行方式考慮在了出行方式當中更符合實際。因為當站點間只相隔較少的幾個站點時，選擇步行方式不但節(jié)省花費同時減少換乘次數，增加步行方式可能增加新的公交路線。在解決問題一、問題二的過程中，基于換乘次數逐步分析給出了起始點與終點之間的最佳路線。對比問題一、問題二分析，可得如下啟發(fā)： 1）在兩個問題的最佳路線中均出現上車后只乘坐一站就下車的情況，這樣情況乘客可以考慮步行

38、經過中間換乘站到達下個換乘站； 2）增加一種交通工具可使原來不能直達的站點直達，優(yōu)化了交通網絡。例如前兩個問題中的5、6 ，增加地鐵后，5找到時間更短的路線，而6找到直達路線。步行可替代交通工具實現以上功能：如果在某站點下車后沒有直接換乘的車次，但較近的兩行車路線上有相鄰站點, 行人可選擇步行到鄰近路線站點進行換乘。所得到的啟發(fā)1和2圖形直觀化描述如下：圖8 采用步行方式優(yōu)化路線3）公交路線都是有向的，即在站點間只能由起始方向至終點方向前進，如<,Start,>，<,end,>,只能在<>,<>中選擇，不能在<>,<>中選

39、擇，但步行不需要考慮此約束，可以在<>,<>中選擇站點，通過沿已經過路線逆行步行方式尋求最佳路線。4）問題一問題二沒有考慮站點間步行時間問題，實際情況中：在相對小于車輛行駛時間情況下，人們步行一段距離再轉車，可減少出行總時間。2、模型建立分析含步行線路選擇問題與四種因素相關：換乘次數、總時間、花費、步行次數n。 下面分析步行次數對前三種因素的影響，在此列舉與之前相比可能優(yōu)化的情形。圖9 換乘抽象化圖形有1個或很少的中間站點，在站點A乘坐公交到站點，換乘一次到達后，再換乘一次最終到達B，換乘次數為2，步行次數為0。考慮步行時，選擇從走到，減少換乘次數同時減少花費，比如，從

40、 S3359 到 S1828的方案中，出現的從中轉站S1784到S1828只有一站的情況。當路線是分段計價的時，如果步行到達最后一站，會節(jié)省花費。例如起始站點A到達站點B剛好是21/31/41站。通過上述的分析，考慮步行的模型應存在以下優(yōu)點：1）增加新的可能的路徑，因為步行不考慮公交線路的方向性； 2）節(jié)省費用，合理的步行安排可以降低費用或減少換乘次數，但可能以增加總時間和步行次數為代價。5.3.2模型準備1、模型假設1） 所有站點之間的步行時間是固定不變的，不受其他外界隨機因素的干擾；2）只有規(guī)定步行時間 (取定的整數)之內的站點之間才可以互稱為鄰近站點，步行后選擇鄰近站點或同一站點進行車次

41、的換乘；3）只考慮公汽站點間可以步行，地鐵站點中不能步行；2、新增符號說明 ：任意兩個相鄰的公交站點間步行平均時間為t；T：判定是否為鄰近站點的時間上確界 ；：站點與其鄰近站點之間的步行時間。 模型I建立綜合上述分析，考慮啟發(fā)一，在知道所有站點間步行時間后，以最少換乘次數為目標，搜索最小換乘次數路線中所有只坐一站的換乘的情況，將其用步行來代替，以犧牲出行時間為代價減少換乘次數，求解任意兩個站點間的最小換乘路線。將最小換乘次數按公交直達，一次換乘，二次換乘和三次換乘分別討論步行優(yōu)化換乘模型的策略。設起始站點和目的站點分別為站點s和e，相鄰兩站之間的距離基本相等為L，且L小于乘客愿意采取步行的最大

42、距離。圖10 轉乘圖Step1：從s可以直達e：如圖七中（a）所示，則建議直接從s點步行到e點，不需乘坐公交。 Step 2：從站點s經站點c轉乘一次到達e：如圖中（b）所示，若sc<ce（sc>ce），則路線可以根據實際狀況將換乘一次優(yōu)化為sc 段步行,ce段直達（或ce段直達，sc段步行）。 Step3：從站點s經站點c，d 轉乘兩次到達e：如圖中（c）所示，若sc<L或cd<L或de<L,則路線可以根據實際交通繁忙狀況或乘客自己的意愿將換乘兩次優(yōu)化為換乘一次的情況； 模型II準備基于前面問題的分析，本模型主要以出行總時間最少為目標，同時考慮轉乘次數盡量少，行

43、程費用盡量低原則。模型I分析了換乘時步行一站的情況，在現實生活中，人們常常步行一站以上，而且乘客沿公汽線路步行也是不合理的。假設人們步行路線不受公汽線路限制，但有最大承受時間，受到問題二的啟發(fā)，若已知所有站點之間的步行時間，可以認為在人們最大步行范圍內，所有公汽站點都可看作相互鄰接。在所有站點之間的步行時間確定的情況下，對于相距不遠的兩站，考慮以其中站點為圓心，以人們能接受的步行距離為半徑做圓，將在該圓形區(qū)域內所有的站點抽象為一個站點。圖11 依步行距離歸一站點模型II的建立1、步行鄰邊化模型 假設乘客所能忍受的最長步行時間為T，定義站點與站點間的平均步行時間。定義以乘客所在的起始點為圓心，以

44、最長步行時間對應的距離為半徑的圓，該圓形區(qū)域稱為起始點的鄰接圓域（如圖所示）。由假設知，鄰接圓域內任意公汽站點都與相鄰接，且與的鄰接耗時為。2、模型說明： 1）考慮步行后的總耗時等于未考慮步行的耗時加鄰接耗時的和； 2）鄰接耗時之和不超過乘客所能忍受的最長步行時間； 3、目標分析 1）目標一：行程總時間最短 總時間的目標函數為： （21）2）目標二：行程總費用最少 滿足時間最短目標后，尋找所有可行方案中費用最小的路線，在本層目標分析時，將圖中的權值賦為途中所需的費用。p表示站點到的行程費用，則行程總費用最小可表示為： （22）有以下目標函數； （23）5.3.5 模型II求解算法1、算法思想：

45、最少換乘的廣度優(yōu)先算法 2、算法描述如下： Step 1：輸入起點目的點，根據輸入的站點進行優(yōu)化，映射入緊鄰站點集。Step2:查找并記錄經過及其緊鄰站點所有路線，記錄上 的所有站點；查找并記錄經過目的站點及其緊鄰站點的所有線路，若，則表明存在從到的一條直達線路，輸出結果；否則轉Step； Step3: 搜索并記錄公交線路的站點，搜索并記錄公交線路的站點，判斷是否有，若有一個點滿足要求，該站點即為一次換乘的站點。 若有幾個站點滿足要求，則先分別求出每一個站點的距離最短的換乘方案，然后選擇所有方案中距離最短的換乘方案為最優(yōu)線路，輸出結果；若沒有，繼續(xù)。Step：搜索并記錄站點所在的線路，記錄上的

46、所有站點，判斷是否有，若有某個站點滿足要求。則站點為第二個換乘站點。從起始站點經過一次換乘(假設換乘點為站點D)，可以到達站點，從站點可以換乘公交車直達目的站點。Step：按照步驟Step和Step的方法求出從起始站點到站點的一次換乘的最優(yōu)線路，再按照step的方法求出從站點到目的站點的最優(yōu)線路。兩個換乘站點和兩段最優(yōu)線路即組成了從起始站點到目的站點的最優(yōu)線路。若有多個站點滿足，則分別求出各站點的最優(yōu)換乘方案，比較各方案的線路距離，選擇一種距離最短的換乘線路方案作為最后的結果，輸出。六、模型檢驗與評價6.1 模型檢驗與靈敏度分析路線用時有時會有微小變動，并且公汽和地鐵的票價也會隨著政策的不同而

47、改變，所以對這兩方面可能產生的波動進行討論就顯得十分必要。6.1.1 時間的波動與公汽和地鐵行駛相關的時間有兩個，分別是相鄰兩站間的平均行駛時間和換乘車輛所需時間，由于最優(yōu)路線的選擇與這兩個時間的比值相關，不妨固定相鄰兩站間公交車和地鐵的平均行駛時間，變動換乘時間，研究它對最優(yōu)路線的影響。1、以S0138到S0485為例，首先固定公交車和地鐵的兩站間的平均行駛時間，研究公汽換公汽的時間對最優(yōu)路線的影響。 圖12 最優(yōu)路線花費時間與公汽換公汽時間關系圖從圖12 中可以看出，公汽換公汽的時間對最優(yōu)路線的影響非常大，當公汽換公汽的時間多于6分鐘時，最優(yōu)策略就會發(fā)生改變。因此，此時應盡量選擇少換車的方

48、案，以減小換車時的等待造成的時間開銷。2、仍以S0138到S0485為例，固定公汽換公汽的時間，研究公汽和地鐵的兩站間的平均行駛時間對最優(yōu)路線的影響圖13 最優(yōu)路線花費的總時間與公汽行駛時間與地鐵行駛時間比的關系圖 從圖13中可以看到，比值在0.8附近就對最優(yōu)乘車路線產生了影響，為了避免這樣的影響，建議出行時盡量選擇兩站間行駛時間比較穩(wěn)定的地鐵以減少行駛時間的變動造成的影響。6.1.2 價格的變動分析可知價格的變動對偏重時間的最優(yōu)路線沒有影響，以下討論它對偏重價格的最優(yōu)路線的影響。不妨固定公汽的價格，討論地鐵價格的變化對偏重價格路線的影響，以地鐵價格下降為2元/次為例。地鐵價格變動之前，地鐵與公汽價格比為3，相當于坐一次地鐵的錢可以坐3次公汽，這對于偏重出行費用的乘客來說，他們一般不會坐地鐵。通過統(tǒng)計可知，與地鐵站相鄰的共117個站點間共13689條線路均可通過不超過2次換乘到達，具體乘車次數見下圖：圖14 地鐵