城市公交網絡出行路徑選擇的計算機算法研究論文
摘 要：隨著經濟的發展以及城市居民的生活質量的提高，外出購物、訪友、娛樂等活動成了人們不可缺少的與日�；顒�，因此，與人們出行息息相關的公共交通工具也受到前所未有的挑戰，為了提高公共交通的使用效率為人們帶來便利以及緩解交通擁堵的現狀，公共交通工具的充分、合理、規范化的出行路線的制定是解決問題的關鍵。本文比較了BP神經計算機模型、時間鏈公交計算機模型、二分圖模型以及Branch-Cut 計算法、螞蟻計算法的優缺點，為制定正確的公交路線提供依據。
關鍵詞：公交網絡；路徑選擇；計算方法
1. 前 言
伴隨人們消費水平的迅猛增長出現的各能源價格飛速上漲以及城市的空氣質量日趨下降的問題，大力倡導節能、環保的理念已成為時代的主題，以在各大城市中廣大市民出行首選的公共交通工具為例，公共交通不僅可以節省時間、減少開支，還可以節約能源、緩解交通擁堵的難題。因此，在一些大、中型城市中公共交通的覆蓋范圍和運行數量在不斷的擴大，交通工具也由相對比較單一的公共汽車發展到高速、節省空間的輕軌、地鐵等多種出行選擇。人們出行次數的增加以及出行理念的改善在給公共交通工具帶來發展機遇的.同時，也對公共交通的正常、快捷、高效的運行帶來巨大挑戰，這就要求公交網絡的設計更人性、更合理、更完善。
建立最簡便有效的最有公交路線的設計規劃成了熱點話題，不同學者對于"最優"的理解含義不同，可以從不同角度出發選擇不同的最有公交網絡出行路線的計算方法，最優路線的理論研究主要包括公交網絡的數學模型描述和設計最優路線的算法。在數學描述方面，Qiu-jin Wu等利用圖論中的K最短路徑算法求解出公交網絡中多路徑優化問題的答案；Choi等討論了如何利用GIS技術，從街道的地理位置設定公交線路和站點的問題；而Anez等對于用偶圖描述公交路線的可能覆蓋范圍，為人們找出更多的可能性。在設計最優路線方面，Konez等提出了以換乘次數少為主要目標，以出行距離短為次要目標的一種公交網絡路徑選擇算法；除此外還有Floyd算法、Dijkstra算法、Moore-pape算法、二分圖發、BP模型法、螞蟻計算法等。
本文首先對公交網絡進行了系統描述，繼而分析了公交乘客出行時所面臨的各種重要因素，從換乘次數、途徑站點、出行耗時和出行費用等進行考慮，比較了不同最優公交路線選擇的計算方法的不同特點。
2. 公交網絡的特點
公交網絡跟計算機網絡一樣，具有拓撲性質。公交網絡盡管依附于路網，但又與網絡有區別擁有自身的特點。
2.1 時間特性--公共交通一般具有固定的時間表，但也受實時交通狀況等因素的影響。
2.2 換乘特性--公共交通共具的換乘包括同站間的換乘和異站間的換乘，同站換乘需要考慮到諸多站點內部的細節；而異站換乘則需要建立各個站點之間的相互連接，而且換乘需要付出時間、金錢等代價。
2.3 有向性--完整的公交路線大體上分為上行和下行兩個空間疊加的行駛方向，一般不同方向具各自的運行時間表和行駛站點分布，甚至不同的行駛線路線。
2.4連通性--單獨的公交線路并不具備連通特性，只有當與換乘連接弧段一起的時候才能組成完整的連通公交網絡。
3.公交網絡出行路線選擇的方法研究
3.1時間鏈公交網絡數據模型計算
伴隨人們日常節奏加快的現象，本方法將時間作為人們選擇出行最主要的考慮因素。從人們出行時間鏈的視角出發，可以把影響出行意愿和偏好等不同類型的因素（如目的距離、換乘次數、等車時間、距離車站的遠近等）折換成時間，并且用時間作為唯一的主要影響因素進行計算。由于公交網絡中時間鏈的復雜程度較高，從時間鏈的視角出發建立公交網絡模型較少。
相對時間是指人們出行的持續時間，它是一個相對完整的出行時間鏈，有4種因素決定：T=Twalk + Twait + Tv + Ti
其中Twalk 代表步行時間，是人們距離公交站點所花費的時間。Twait 代表等車時間，Tv 是實際乘車時間，Ti 是換乘所消耗的時間，包括上下車、各站點步行所需時間。
上述公式即為公交出行時間鏈，乘客每次出行即完成一個出行時間鏈。由此可以用以上4種時間的總和考慮不同出行方式的花費，進而求出最優路徑。因為換乘需要較高的時間代價換取（上下車、步行和等車等花費的時間），除非換乘直接到達的車次，縮短路線，節省更多的時間，否則人們輕易不會換乘車次。乘客的步行時間主要由出發地、目的地到車站的距離決定，人們的步行速度相差不大是一個定值，因此距離的長短成了主要的因素；而乘客等車時間則與發車頻率、停車耗時、交通的通暢度等因素有關，一般用發車間隔的一半來表示；車輛的行駛時間與路段上公交路線和車速大小有關，常用公交線路運行距離與平均車速的比值表示；換乘時間主要由上下車時間、換乘距離、換乘數等決定，一般用換乘距離與步行平均速度的比值表示。
本方法是一個相對簡潔的網絡公交路線選擇的方法，適用于人口密度較小的中小型城市的公交規劃。
3.2 二分圖法計算模型
二分圖是一種不論在理論研究或是實際應用中都具有豐富意義的特殊模型。在二分圖中，所有站點都被分割為兩個集合M和N，其中M或N中任意兩個在同一集合中的點都不直接相連。本方法運用標有站牌號的二分圖對公交網絡進行建模，并結合此模型和站點網絡圖給出最佳出行路徑的計算方法。
公交網絡二分圖模型是包含線路和站點集合的網絡，若某條線路經過某些站點，則將站點間用一條無向線段相連。公交系統二分圖模型是將標有站牌號的站點與線路之間用一條賦予數字(數字表示該線路經過該站點時的站牌號)的無向線段相連。并與站點網絡圖選擇兩站點間最優出行路徑的算法和選擇方案。從乘車的方案看，二分圖算法還可以展示出整條換乘線路。
3.3 分支一切割法計算模型
分支一切割法即Branch-Cut algorithms 法它是一個求解混合整數規劃的成功模型。它首先由Grotchel、Junger和Reinelt等人應用線性排序解決大規�；旌险麛狄巹濍y題，以提高分支運行效率的方法。
3.4 BP計算模型
BP計算模型即誤差反向傳播神經網絡模型，它是人工神經網絡ANN模型中使用性能最優越的一款計算方法，它是以MATLAB環境下開發的ANN工具為運行背景，具有預測分析各交通分區現狀及不同因素變化下的公交出行比例的功能，該方法不需要詳細分析各變量之間的相互影響，尤其是數學關系，減少很多不必要的瑣碎復雜的因素，該方法還具有簡易的學習過程，并不需要很多的訓練樣本數據，而取得較好的預測結果。
3.5 螞蟻算法
螞蟻算法最早是由意大利學者M．Dorigo等人提出的模擬生物世界中螞蟻覓食行為的仿生類算法。它是一種新的本質上并行和隨機搜索的優化算法，具有很好的靈活性、分散性和自發組織性�？紤]到城市道路結構復雜，公交線網規劃考慮的因素眾多，特別是直達客流量的影響，這一系列特征正好與螞蟻覓食的現象相似，公共密集場所如市中心、商業區等正如螞蟻的巢穴，螞蟻每向前行走一步，對應公交網絡中從一個節點到另一個節點。螞蟻在路徑上留下的信息素，對應于網絡從一個狀態變化到另一個狀態，路段的權值發生的變化。
4. 結 語
城市網絡交通的便利暢通與否，與人們的日常生活息息相關，為使人們的生活工作出行的便捷、準確、安穩，網絡交通的人性化、合理化的計算規劃十分重要，伴隨時代進步的腳步，公交網絡出行路線的計算機選擇也正日新月異，提出不同的計算方法，沒有最好或者最優的計算方法，只有根據當地的影響因素設定最適合的路線才是人們所需求的。
參考文獻：
[1] 公交出行完整路線計算方法研.劉岳峰,張 鑫,孫華波,劉 婷
[2] 公交最優路徑選擇的數學模型及算法.雷一鳴.廣東工業大學
[3] 公交網絡最優路徑選擇算法研究.陳小輝.榆林學院計算機與網絡工程系
[4] 大城市公共交通網絡最優路徑算法研究.鄢勇飛.武漢理工大學
【城市公交網絡出行路徑選擇的計算機算法研究論文】相關文章：
7.城市公交調研報告