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