【摘要】：大規(guī)模時(shí)變公交網(wǎng)絡(luò)中最短路徑精確查詢的算法是公交網(wǎng)絡(luò)尋徑問題的研究難點(diǎn)之一,近似搜索算法的求解滿意度不高,而精確搜索算法的效率又較低。針對(duì)公交網(wǎng)絡(luò)的時(shí)變特性與不確定性,建立了時(shí)變公交網(wǎng)絡(luò)模型。將公交最優(yōu)路徑選擇問題分解為換乘次數(shù)與換乘線路的查詢問題,給出了基于線路影射網(wǎng)絡(luò)的換乘次數(shù)的查詢算法和基于站點(diǎn)影射網(wǎng)絡(luò)的換乘站點(diǎn)和乘車距離、乘車時(shí)間的計(jì)算方法,兩種算法都是多項(xiàng)式算法,最后給出算例驗(yàn)證了該方法的有效性。
[Abstract]:The algorithm of accurate query of shortest path in large-scale time-varying public transport network is one of the difficulties in the research of routing problem of public transport network. The approximate search algorithm is not satisfied with the solution and the efficiency of the exact search algorithm is low. In view of the time-varying characteristics and uncertainty of public transport network, a time-varying bus network model is established. The optimal route selection problem of public transportation is decomposed into the query problem of transfer times and transfer lines, and the query algorithm of transfer times based on line mapping network and the transfer station and distance based on site-mapping network are given. The two algorithms are polynomial algorithms. Finally, an example is given to verify the effectiveness of this method.
【作者單位】： 河北工業(yè)大學(xué)理學(xué)院;北京大學(xué)軟件與微電子學(xué)院無錫基地;南開大學(xué)商學(xué)院;北京大學(xué)軟件與微電子學(xué)院;新加坡管理大學(xué)信息系統(tǒng)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金(71071079) 河北省自然科學(xué)基金(A2013202198)
【分類號(hào)】：U491.17

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 錢臻,陸化普;一種公交網(wǎng)絡(luò)客流分配方法及其實(shí)用性研究[J];清華大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年09期

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李洪濤;;基于數(shù)據(jù)庫(kù)的公交換乘算法的實(shí)現(xiàn)與優(yōu)化[J];軟件導(dǎo)刊;2008年02期

2 呂亮;劉枝燕;楊盼盼;程茂林;張晉銘;;一種新的基于WebGIS的公交換乘模型[J];太原師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年04期

3 江南;史峰;盧紅巖;鄧連波;;鐵路旅客乘車方案優(yōu)化決策模型研究[J];鐵道學(xué)報(bào);2007年03期

4 羅朝暉;韋增欣;陳巧萍;;多類型多準(zhǔn)則相互影響的彈性需求隨機(jī)用戶平衡模型[J];統(tǒng)計(jì)與決策;2010年23期

5 吳世江,史其信,陸化普;基于交通效率的城市公共交通路網(wǎng)布局模型[J];土木工程學(xué)報(bào);2005年01期

6 陳培軍;王欣潔;;基于矩陣的公交查詢高效算法[J];太原科技大學(xué)學(xué)報(bào);2011年01期

7 羅建;;公路大件運(yùn)輸線路選擇方案及模型研究[J];西華大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

8 孫楊;孫小年;孔慶峰;宋瑞;何世偉;;軌道交通新線投入運(yùn)營(yíng)下常規(guī)公交網(wǎng)絡(luò)優(yōu)化調(diào)整方法研究[J];鐵道學(xué)報(bào);2014年03期

9 梁萌;;基于計(jì)算機(jī)算法的城市公交網(wǎng)絡(luò)出行路徑問題研究[J];陜西教育(高教版);2014年04期

10 魏超;龍建成;;城市軌道交通接駁公交線路優(yōu)化設(shè)計(jì)[J];山東科學(xué);2015年03期

相關(guān)會(huì)議論文 前4條

1 扈震;張發(fā)勇;劉書良;;城市公交換乘數(shù)據(jù)模型研究及算法實(shí)現(xiàn)[A];中國(guó)測(cè)繪學(xué)會(huì)九屆四次理事會(huì)暨2008年學(xué)術(shù)年會(huì)論文集[C];2008年

2 楊峰;紀(jì)凱;陳濤燾;韓棟;;一種公交最佳路徑選擇方法[A];中國(guó)地理信息系統(tǒng)協(xié)會(huì)第四次會(huì)員代表大會(huì)暨第十一屆年會(huì)論文集[C];2007年

3 鄧連波;史峰;秦進(jìn);;基于鐵路列車開行方案的客流分配方法[A];可持續(xù)發(fā)展的中國(guó)交通——2005全國(guó)博士生學(xué)術(shù)論壇（交通運(yùn)輸工程學(xué)科）論文集（上冊(cè)）[C];2005年

4 ;Models for Multi-Service Line Planning Problem in Public Transportation[A];第24屆中國(guó)控制與決策會(huì)議論文集[C];2012年

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 錢臻,陸化普;一種公交網(wǎng)絡(luò)客流分配方法及其實(shí)用性研究[J];清華大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年09期

2 馬良河,劉信斌,廖大慶;城市公交線路網(wǎng)絡(luò)圖的最短路與乘車路線問題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2004年06期

3 商麗媛;張全信;;一種改進(jìn)的公交網(wǎng)絡(luò)最優(yōu)路徑算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2009年01期

4 李彬,楊超,楊佩昆;公交最短路徑算法與網(wǎng)絡(luò)通達(dá)性指標(biāo)的計(jì)算[J];同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版);1997年06期

5 吳世江,史其信,陸化普;基于交通效率的城市公共交通路網(wǎng)布局模型[J];土木工程學(xué)報(bào);2005年01期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 閆小勇,牛學(xué)勤;公交網(wǎng)絡(luò)多路徑選擇啟發(fā)式算法研究[J];城市交通;2005年03期

2 蘇愛華,施法中;公交網(wǎng)絡(luò)換乘問題的一種實(shí)現(xiàn)[J];工程圖學(xué)學(xué)報(bào);2005年04期

3 倪立;;對(duì)上海公交網(wǎng)絡(luò)的分析與改善設(shè)想[J];交通與運(yùn)輸;2006年02期

4 張晨;張寧;;上海市公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)研究[J];上海理工大學(xué)學(xué)報(bào);2006年05期

5 蔣忠海;鄒志云;;城市公交網(wǎng)絡(luò)阻抗函數(shù)模型[J];華中科技大學(xué)學(xué)報(bào)(城市科學(xué)版);2006年S2期

6 任華玲;高自友;;動(dòng)態(tài)公交網(wǎng)絡(luò)設(shè)計(jì)的雙層規(guī)劃模型及算法研究[J];系統(tǒng)工程理論與實(shí)踐;2007年05期

7 戴帥;陳艷艷;魏中華;;復(fù)雜公交網(wǎng)絡(luò)的系統(tǒng)可靠性分析[J];武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版);2007年03期

8 李岸巍;;太原市公交網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)特性分析[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

9 張晉偉;鄒云;;公交網(wǎng)絡(luò)最優(yōu)線路查詢模型及軟件開發(fā)[J];交通運(yùn)輸工程與信息學(xué)報(bào);2008年04期

10 劉銳;嚴(yán)寶杰;黃志鵬;劉蕓欣;;可靠性理論在公交網(wǎng)絡(luò)分析中的應(yīng)用[J];公路交通科技;2008年04期

相關(guān)會(huì)議論文 前10條

1 蔣忠海;鄒志云;;城市公交網(wǎng)絡(luò)阻抗函數(shù)模型[A];第二屆湖北省力學(xué)學(xué)會(huì)青年學(xué)術(shù)研討會(huì)論文集[C];2006年

2 白子建;朱兆芳;龔鳳剛;;禁忌算法在公交網(wǎng)絡(luò)優(yōu)化中的應(yīng)用[A];第一屆中國(guó)智能交通年會(huì)論文集[C];2005年

3 王寶輝;;城市(鎮(zhèn))群骨干公交網(wǎng)絡(luò)框架研究[A];轉(zhuǎn)型與重構(gòu)——2011中國(guó)城市規(guī)劃年會(huì)論文集[C];2011年

4 周康;馬曉旦;夏曉梅;;基于最小換乘模型的公交網(wǎng)絡(luò)優(yōu)化[A];構(gòu)建生態(tài)人文交通 促進(jìn)經(jīng)濟(jì)跨越發(fā)展——第十九屆海峽兩岸都市交通學(xué)術(shù)研討會(huì)論文選編[C];2011年

5 徐一飛;張國(guó)華;;一種求實(shí)的公交網(wǎng)絡(luò)優(yōu)化方法[A];科學(xué)決策與系統(tǒng)工程——中國(guó)系統(tǒng)工程學(xué)會(huì)第六次年會(huì)論文集[C];1990年

6 陳學(xué)武;胡剛;;公交分層系統(tǒng)的規(guī)劃方法研究[A];北京快速公交系統(tǒng)發(fā)展戰(zhàn)略研討會(huì)文集[C];2003年

7 王昊;吳嬌蓉;;多模式公交網(wǎng)絡(luò)的換乘懲罰附加值研究[A];轉(zhuǎn)型與重構(gòu)——2011中國(guó)城市規(guī)劃年會(huì)論文集[C];2011年

8 孫豹;楊旭華;;一種具有可控直徑的公交網(wǎng)絡(luò)演化模型研究[A];第五屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文（摘要）匯集[C];2009年

9 秦瓊;張放;劉海英;許鵬遠(yuǎn);王志平;;復(fù)雜網(wǎng)絡(luò)理論在大連公交網(wǎng)絡(luò)中的應(yīng)用[A];2006全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

10 楊峰;紀(jì)凱;陳濤燾;韓棟;;一種公交最佳路徑選擇方法[A];中國(guó)地理信息系統(tǒng)協(xié)會(huì)第四次會(huì)員代表大會(huì)暨第十一屆年會(huì)論文集[C];2007年

相關(guān)重要報(bào)紙文章 前10條

1 壽寧記者站 朱雅秀;壽寧投入160多萬元完善公交網(wǎng)絡(luò)[N];閩東日?qǐng)?bào);2010年

2 本報(bào)記者 李保良 通訊員 李朝旗 郭文輝;邯鄲力推縣市公交網(wǎng)絡(luò)方便百姓[N];中國(guó)交通報(bào);2010年

3 任相國(guó)　王硯才;陵縣構(gòu)建城鄉(xiāng)村一體化公交網(wǎng)絡(luò)[N];德州日?qǐng)?bào);2009年

4 本報(bào)記者 李競(jìng)立;昆明初步形成較為完善公交網(wǎng)絡(luò)[N];云南日?qǐng)?bào);2002年

5 阮春生;完善三級(jí)公交網(wǎng)絡(luò) 解決百姓出行難題[N];麗水日?qǐng)?bào);2007年

6 孫曉雷　張偉超 記者 雷蕾;萊蕪市構(gòu)建大公交網(wǎng)絡(luò)實(shí)現(xiàn)“公交村村通”[N];人民政協(xié)報(bào);2011年

7 記者 劉鯤;五年內(nèi)形成城市公交網(wǎng)絡(luò)體系[N];攀枝花日?qǐng)?bào);2014年

8 特約記者 李劍雄 記者 楊眉;株洲構(gòu)建綠色公交網(wǎng)絡(luò)[N];中國(guó)交通報(bào);2013年

9 成露;政府首先要考慮為無車市民做些什么[N];工人日?qǐng)?bào);2007年

10 張魁勇邋陳文勇;大城市應(yīng)優(yōu)先發(fā)展軌道公交[N];成都日?qǐng)?bào);2008年

相關(guān)博士學(xué)位論文 前6條

1 朱永剛;城市公交網(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化方法研究[D];吉林大學(xué);2010年

2 司徒炳強(qiáng);公交網(wǎng)絡(luò)時(shí)刻表編制的理論建模及可靠性控制方法研究[D];華南理工大學(xué);2011年

3 張建剛;復(fù)雜網(wǎng)絡(luò)同步理論在城市公交網(wǎng)絡(luò)中的應(yīng)用研究[D];蘭州交通大學(xué);2011年

4 陳光;空間復(fù)雜網(wǎng)絡(luò)分析、優(yōu)化及其在城市公交網(wǎng)絡(luò)中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2014年

5 田慶飛;基于復(fù)雜網(wǎng)絡(luò)理論的城市公交網(wǎng)絡(luò)生成與優(yōu)化研究[D];吉林大學(xué);2013年

6 孫磊磊;基于�？繒r(shí)間的城市公共交通網(wǎng)絡(luò)均衡客流分配模型研究[D];長(zhǎng)安大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 劉霞霞;太原市公交網(wǎng)絡(luò)優(yōu)化研究[D];山西大學(xué);2008年

2 陳鳳;城市群一體化城際公交網(wǎng)絡(luò)設(shè)計(jì)研究[D];長(zhǎng)沙理工大學(xué);2009年

3 張君超;基于復(fù)雜網(wǎng)絡(luò)的城市公交網(wǎng)絡(luò)特性分析與演化研究[D];西南交通大學(xué);2010年

4 汪濤;城市公交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和演化模型研究[D];南京航空航天大學(xué);2009年

5 張欣;公交網(wǎng)絡(luò)的復(fù)雜性研究[D];大連理工大學(xué);2006年

6 衡玉明;城市公交網(wǎng)絡(luò)可靠性研究[D];北京交通大學(xué);2007年

7 高巖;城市公交網(wǎng)絡(luò)設(shè)計(jì)模型與算法研究[D];長(zhǎng)沙理工大學(xué);2007年

8 趙炳璜;烏魯木齊市公交網(wǎng)絡(luò)結(jié)構(gòu)特性分析研究[D];新疆農(nóng)業(yè)大學(xué);2011年

9 張勝虎;基于復(fù)雜網(wǎng)絡(luò)的南昌市公交網(wǎng)絡(luò)優(yōu)化研究[D];南昌大學(xué);2010年

10 孫豹;理想n-深度派系網(wǎng)絡(luò)模型及其在公交網(wǎng)絡(luò)中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2011年

，

本文編號(hào)：2142638