城市公交網絡出行路線選擇的計算機算法探討

【文章摘要】
優秀的城市公交網絡出行路線圖的制定首先應該站在公交乘客的角度上進行研究，在對城市公交網絡路線最短路徑算法的基礎上，同時充分的利用地理信息系統，對公共交通網絡中進行兩個結點間的最佳路線的選擇，通過此路線能夠達到最大程度的減少換車的次數。本文充分探討了基于地理信息系統的城市公交網絡出行路線的最佳選擇。
【關鍵詞】
城市；公交網絡；出行路線；地理信息系統
對于任何一個城市來說，公共交通信息系統是至關重要的交通工具，它能夠進行各種交通信息的查詢，這樣便為統計提供了更加方便直觀的手段。同時公共交通信息系統也為市民的日常出行帶來了方便。公共交通信息系統具有一個最為重要的功能，就是它能夠在乘客給出起始點后，為乘客選擇出最優的出行方案。在公交網或者是道路網上找出顧客出行的路徑的分布規律是城市交通網絡出行路線選擇算法的根本所在。為了能夠對公交客流更為合理的分配，就需要研究并建立更為接近現實的城市公交網絡出行線路。
1 城市公交乘客出行的心理期望
一般情況話，城市公交的換乘次數， 出行的距離、費用以及耗時是乘客在出行的時候選擇城市公交路線所受影響的幾大因素。通過具體的調查研究表明，大部分的乘客在選擇城市公交時，換乘的公交車的次數是其考慮的重要因素，再就是進行出行時間長短的考慮。綜上所述，城市公交網絡出行路線選擇的計算機算法以換乘次數最少為其優化目標。
2 城市公交網絡所具備的特點
城市中公共交通汽車時沿著道路進行的，這就使其具有自身的一些特點，并且因其區別于其他不同的道路交通網絡。
2.1 連通性
就單向的城市公共交通來說它是不具備連通性的，只有經過換乘從而使弧度有效的連接起來，才能夠構成較為完整并具連通性的公交網絡。
2.1.1 有向線性
實際情況中，城市公交路線都是具有方向性的，不僅不同路線的公交具有不同的行駛方向及路線，即便是同路線的公交，上下行車的路線也不盡相同。城市公交網絡中這些公交路線的方向性只有通過有向線性才能夠進行表現，因此來說有向線路集應該被引入到城市公交網絡中。
2.1.2 時間性
一般來說城市公共交通都是具有相應的運行時間表，但是在實際運行過程中也會受到交通狀況等因素的影響。
2.1.3 換乘性
相同站點的換乘以及不同站點的換乘共同構成了公共交通的換乘。通常情況下， 同站點的換乘，乘客只需要對站點的內部細節有較為熟悉的掌握便可，異站點的換乘則需要建立在各個站點能夠相互連接的接觸上，同時站點的換乘也是需要付出相應的成本的，比如說時間或者金錢等。
3 城市公交網絡中路徑選擇的計算機方法研究
3.1 以時間鏈為基準的公交網絡數據模型算法
現階段人們的生活速度不斷加快，此公交網絡模型的算法便是將時間作為乘客出行的重要因素進行考慮計算。以時間鏈的角度來計算，就可以把行車中的不同類型的其他因素進行以時間的換算。
人們持續出行的時間被稱為相對時間，相對時間是一個較為完整的時間鏈。相對時間的計算公式為：相對時間= 步行時間+ 等成時間+ 實際乘車時間+ 換乘所消耗的時間。因此來說可以通過控制四種不同因素的時間來選擇路徑最優的出行路線。通常情況下，乘客是不會輕易的選擇換乘車次的，因為換乘車次需要具有較高的時間代價。乘客的步行時間主要是由出發點到達站牌的距離所決定的，因此距離成為影響步行時間的重要因素。乘客等車時間的影響因素則較為復雜，主要包括發車的頻率、交通的順暢以及停車的耗時。乘客的換乘時間則主要是受上下車時間、換乘距離以及換乘數所決定的。
以時間鏈為基準的公交網絡數據算法是一種較為簡潔的公交路線選擇法，通常只適用于中小型城市的公交運行，而大城市的公交運行時間鏈較為復雜，此種方法便不適用。
3.2 傳統意義上的Dijkstra 最優化路徑選擇算法
穩定性以及能夠適應網絡拓撲的變化是Dijkstra 最優化路徑算法的特點， 使得其在地理信息系統以及計算機網絡拓撲路徑選擇中廣泛應用，但是傳統的Dijkstra 并不適應公交路線的選擇。公交線路網絡具有非常復雜的數據結構，采用Dijkstra 算法，不僅算法時間長且在碰到大計算量的問題時，系統的整體運算效率也會有較為明顯的下降。除此之外，利用Dijkstra 算法只能進行兩個結點之間存在的計算，這也就導致所計算出的路線可能是最短的路線，但是卻無法保證公交的換乘次數是最少的，也就無法得到換乘次數最優化的目的。而從之前的出行乘客心理期望的研究來看，換乘次數少才是乘客在公交出行時首先考慮的因素。
3.3 改進后的Dijkstra 最優化路徑選擇算法
改進之后的Dijkstra 算法可以充分的利用最小換乘次數矩陣，來計算出換乘次數最少的最短路徑。但是此種算法只能使用于一些較為簡單的公交網絡拓撲，而面對一些復雜的公交網絡拓撲時還需要進行相應的簡化，這無疑又提高了整個算法的復雜度。
3.4 廣度優先搜素算法
廣度優先搜索算法在進行方案選擇時會搜索出大量的不合理的路徑，這就容易造成維數爆炸，從而為整個算法增加不必要的麻煩，由此來說此種算法很難適用于大型的實際公交網。
3.5 螞蟻算法
螞蟻算法是一種仿生類算法，最早是由意大利學者提出的。此種算法具有較強的靈活性、組織性以及分散性，是一種將并行以及隨機搜索的優化算法。螞蟻算法的提出正是因為城市道路復雜，影響公交網絡規劃因素較多等因素與螞蟻覓食的現象極為相似。在此算法中公共密集的場所被比喻為螞蟻的巢穴，螞蟻所向前行的每一步便作為對應公交網絡中一個節點到另一個節點。路徑上螞蟻所留下的信息素，則在交通網絡中被認為是一個狀態到另一個狀態的變化，也就是指路權值所發生的變化。
3.6 城市公交網絡中的二分圖法計算方法
二分圖不僅在理論研究中具有豐富的意義，在實際應用中同樣具有。在二分圖的計算方法里，所有的公交結點都被分為M 集合與N 集合。并且兩個集合中的點都是無法直接相連的。
城市公交網絡中的二分圖模型是包含線路及站點集合的網絡。在二分圖中線路與站點之間則用無向線段進行相連并用數字將站牌號表示出來，從而選擇出兩點之間最優路徑的算法及路徑選擇。
4 結語
在實際的生活中，城市公交網絡是異常復雜的，如果僅僅是局限在出行距離最短、換乘次數最少或者是出行時間最短等單一因素上是具有非常大的局限性的。地理信息系統對空間信息的管理以及圖形的表現都具有很強的能力，充分的結合城市自身的特點以及長時間以來人們累積的實際路徑尋求知識，進行具有現代交通發展需要的地理信息系統是有非常重要的實際意義的。
【參考文獻】
[1] 劉波濤. 城市公交網絡出行路徑選擇的計算機算法研究[J]. 電腦知識與技術,2010,30:8420- 8421+8426.
[2] 張本群. 城市公交網絡出行路徑選擇的計算機算法研究[J]. 信息與電腦( 理論版),2011,12:184+186.
[3] 梁萌. 基于計算機算法的城市公交網絡出行路徑問題研究[J]. 陜西教育( 高教版),2014,04:64+67.