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