城市公交網(wǎng)絡(luò)出行路線選擇的計算機(jī)算法探討

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

上一篇：基于物聯(lián)網(wǎng)技術(shù)的智能家庭應(yīng)用分析

下一篇：智慧校園建設(shè)在教育信息化及校園..