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

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

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

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