題-1_100_100.jpg)
基本信息
- 項目名稱：
- 基于GPS的最佳動態(tài)路徑分析與仿真研究
- 小類：
- 機(jī)械與控制
- 簡介：
- 利用車輛導(dǎo)航技術(shù)的反饋信息，通過A*算法對靜態(tài)路網(wǎng)的最優(yōu)路徑做出動態(tài)選擇?，F(xiàn)今流行的Dijkstra算法、A*算法等，都是基于完全靜態(tài)、確定的信息數(shù)據(jù)庫下，求解得出的最短路徑。本文通過A*算法充分利用靜態(tài)路網(wǎng)信息，借助車輛導(dǎo)航系統(tǒng)加以動態(tài)路網(wǎng)中的適應(yīng)條件，以及實時更新的交通數(shù)據(jù)，得出計算結(jié)果精確，時間復(fù)雜度較低，且符合實際情況的最佳路徑。
- 詳細(xì)介紹：
- 目前，隨著社會經(jīng)濟(jì)的發(fā)展、城市化進(jìn)程的加快和機(jī)動車保有量的快速增長，尤其私家小汽車的快速發(fā)展，城市交通越發(fā)擁擠。 由于土地資源不足，建造各種公路等物理設(shè)施的能力是有限的, 所以單純地依靠修建更多的道路、擴(kuò)大路網(wǎng)規(guī)模等這樣的措施僅僅能解一時之需, 并不能從根本上解決日益增長的交通需求?；谶@種需要，提出了以車載GPS（Global Positioning System）為核心的路徑分析系統(tǒng)。該技術(shù)是以GPS技術(shù)為核心, 綜合利用廣播技術(shù)、光電傳感器、計算機(jī)網(wǎng)絡(luò)、自動控制和人工智能等技術(shù)的一種新型車輛導(dǎo)航技術(shù)[1]。 現(xiàn)階段，車載GPS進(jìn)入規(guī)模化發(fā)展階段。“車載GPS 最佳路徑分析” 在車輛導(dǎo)航系統(tǒng)及城市應(yīng)急系統(tǒng)中有著廣泛的應(yīng)用前景。針對城市道路網(wǎng)的特點，對基于城市道路網(wǎng)的最佳路徑分析的關(guān)鍵技術(shù)進(jìn)行了研究和驗證。提出了一種實用、高效的最佳路徑分析解決方案，并在此基礎(chǔ)上實現(xiàn)了一個最佳路徑分析法的高效實現(xiàn)算法。 一條路徑的確定取決于許多因素，如距離、行程時間、路網(wǎng)彎數(shù)、路況復(fù)雜度、轉(zhuǎn)向燈個數(shù)、交通信號燈的數(shù)目和動態(tài)交通信息等。選擇最短路徑、最佳路徑、最低耗費(fèi)等問題，都離不開最短路徑搜索并以其作為選擇依據(jù)。路徑選擇標(biāo)準(zhǔn)可由程序設(shè)計決定或通過用戶界面修改[2]。 最短路徑問題的解決方法很多，包括啟發(fā)式搜索A*算法、動態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)、Dijkstra 算法等，其中以迪杰斯特拉(Dijkstra)算法在實際應(yīng)用中較為廣泛。 由于Dijkstra算法的搜索過程屬于遍歷計算，所以出現(xiàn)大量的搜索節(jié)點。其中，Dijkstra算法與A*算法搜索范圍特點如下圖1所示。由于所引入的動態(tài)算法，是要求處理大量的靜態(tài)數(shù)據(jù)的同時，還需要實時監(jiān)測接受的動態(tài)數(shù)據(jù)，并計算當(dāng)前對于最佳路徑的影響的一些數(shù)據(jù)[3]。因此，處理量就變得相當(dāng)大，一般來說，硬件不能支持。 A*算法是比較流行的啟發(fā)式搜索算法之一，被廣泛應(yīng)用于路徑的最優(yōu)解。A*算法對比其他算法，不同之處在于A*算法引入了啟發(fā)式函數(shù)。啟發(fā)式估價函數(shù)估價每一生成節(jié)點以確定此節(jié)點的優(yōu)劣性。通過這種方式，啟發(fā)式函數(shù)決定在諸多路徑中首先遍歷那條路徑以便搜索過程更為有效，因為算法首先搜索最優(yōu)希望的節(jié)點[4]。 A*算法的算法步驟： 1)創(chuàng)建開放列表OPENLIST，初始化列表，使其只包含起始點； 2)創(chuàng)建關(guān)閉列表CLOSEDLIST，初始化清空列表； 3)從OPENLIST中選擇f′(n)值最小的一個節(jié)點n； 4)如果n是目標(biāo)節(jié)點，停止搜索，轉(zhuǎn)到步驟（7）； 5)對于n的相鄰節(jié)點中的一個節(jié)點m； （1）如果m在CLOSEDLIST中并且g（m）更小，更新節(jié)點m的g值，將其父節(jié)點指向n。 （2）如果m在OPENLIST中且目前的g（m）更小，更新節(jié)點m的g值，將其父節(jié)點指向n。 （3）如果m不在OPENLIST和CLOSEDLIST中，將m加入OPENLIST中，計算其g值，將其父指針指向n。 6)返回執(zhí)行步驟（3），繼續(xù)搜索； 7)從目標(biāo)節(jié)點向上回溯到原節(jié)點，記錄經(jīng)過的節(jié)點。遍歷一系列后向指針后，得到最佳路徑； 現(xiàn)實生活當(dāng)中，交通信息屬于動態(tài)信息，即每一段路都有其自己的屬性。如果單純地從距離和時間出發(fā)，所得出的最短路徑與實際駕駛者所希望的并不能完全符合。譬如，得出的最短路徑上，有其中路段屬于交通擁堵嚴(yán)重的，即其路段的效率就相對低下。相對駕駛者來說，意味著比其他路徑所使用的路徑花費(fèi)更多時間。又或者即使路徑上沒有交通意外，堵塞等情況，但是路徑上出現(xiàn)較多的收費(fèi)設(shè)置，同樣對于駕駛者來說是不利的[5]。因為這意味著花費(fèi)更多的費(fèi)用。 因此，必須從動態(tài)路網(wǎng)中分析主要影響車輛行駛最佳路徑的因素。根據(jù)路徑選擇的限制要求，得出以下幾點： 1）道路系數(shù) 道路的級別對于車輛通過性有重要意義，高速公路的效率肯定要比城市里面的支路的效率高。同樣級別的道路，雙車道和四車道同樣擁有不同的通過效率[6]。根據(jù)我國現(xiàn)行的《公路工程技術(shù)標(biāo)準(zhǔn)》（JTJ001-1997），公路按使用任務(wù)、功能和適應(yīng)的交通量分為高速公路、一級公路、二級公路、三級公路、四級公路五個等級： （1）、高速公路為專供汽車分向分車道行駛并應(yīng)全部控制出入的多車道公路。 四車道高速公路能適應(yīng)將各種汽車折合成小客車的年平均日交通量25000～55000輛。 六車道高速公路能適應(yīng)將各種汽車折合成小客車的年平均日交通量45000～80000輛。 八車道高速公路能適應(yīng)將各種汽車折合成小客車的年平均日交通量60000～100000輛。 （2）、一級公路為供汽車分向分車道行駛并可根據(jù)需要控制出入的多車道公路。 四車道一級公路能適應(yīng)將各種汽車折合成小客車的年平均日交通量15000～30000輛。 六車道一級公路能適應(yīng)將各種汽車折合成小客車的年平均日交通量25000～55000輛。 （3）、二級公路為供汽車行駛的雙車道公路。 一般能適應(yīng)每晝夜3000～7500輛中型載重汽車交通量。 （4）、三級公路為主要供汽車行駛的雙車道公路。 一般能適應(yīng)每晝夜1000～4000輛中型載重汽車交通量。 （5）、四級公路為主要供汽車行駛的雙車道或單車道公路。 雙車道四級公路能適應(yīng)每晝夜中型載重汽車交通量1500輛以下。 單車道四級公路能適應(yīng)每晝夜中型載重汽車交通量200輛以下。 2）GPS/DR（航位推算,Dead-Reckoning)組合定位的反饋信息 DR的基本原理是利用方向傳感器和速度傳感器來推算車輛的瞬時位置，可以實現(xiàn)連續(xù)自主式定位。但由于其推算過程是一個累加過程，方向傳感器的誤差隨時間的延長而積累，另外，推算只能確定相對位置和航向。因此，將航位推算與GPS 組合起來，兩者取長補(bǔ)短，可以彌補(bǔ)各自的缺點, 確保系統(tǒng)能在任何時候都能為運(yùn)動車輛提供較為準(zhǔn)確的導(dǎo)航信息。一方面可以利用GPS精確的定位結(jié)果輔助DR 的初始化并且可以定期地用它對DR 的定位誤差進(jìn)行在線校正。另一方面，在GPS無法定位時系統(tǒng)又可以自動地切換到DR 導(dǎo)航方式，直至GPS 恢復(fù)正常接收后, 系統(tǒng)再回到GPS 與DR 的組合導(dǎo)航方式[7]。從而，即使在GPS失效、單獨(dú)使用DR推算定位時也能長時間保持較高的定位精度。 通過GPS反饋的定位信號進(jìn)行運(yùn)動車輛的檢測和分割，預(yù)測其在相關(guān)路徑的運(yùn)動軌跡，從而根據(jù)交通流量綜合其他情況進(jìn)行調(diào)度，可以把發(fā)生沖突的交通流從時間和空間上進(jìn)行分離，穩(wěn)定平衡交通流的密度。 3）廣播和交通部門信息的雙向調(diào)控 在通信網(wǎng)絡(luò)的支持下，參考廣播電臺的實時路面路況信息，即時接受交通部門發(fā)布的突發(fā)事故，并通過GSM通信網(wǎng)與移動中的車輛進(jìn)行通話、短信息傳輸和數(shù)據(jù)傳輸，完成車輛定位、調(diào)度、監(jiān)控、報警等功能，且在電子地圖上顯示車輛的位置，做出應(yīng)急路徑選擇，間接地約束最優(yōu)動態(tài)路徑，避免大面積的交通癱瘓，保證動態(tài)路網(wǎng)運(yùn)動車輛行駛路徑的準(zhǔn)確性[8]。 其中，接受短信息可用GSM用戶終端（如車載臺、手機(jī)）或用可接收短信息功能的固定用戶設(shè)備，也可用ISDN方式直接連接到移動通信局的短消息服務(wù)中心，并聯(lián)通車輛導(dǎo)航管理系統(tǒng)，這樣接收短信息更迅捷，容量更大[9]。 4）可自動更新的數(shù)據(jù)庫管理系統(tǒng) 車輛定位導(dǎo)航系統(tǒng)由自導(dǎo)航系統(tǒng)，管理系統(tǒng)，組合系統(tǒng)三部分組成。同時，系統(tǒng)應(yīng)配置有圖形結(jié)構(gòu)簡單、冗余度小、拓?fù)潢P(guān)系簡單、空間信息查詢與分析速度快、擁有開放數(shù)據(jù)接口的電子地圖數(shù)據(jù)庫。 出發(fā)地和目的地之間的最佳線路需要參照最新的時間、距離、收費(fèi)等標(biāo)準(zhǔn)，并且所要求的數(shù)據(jù)存儲冗余小，空間數(shù)據(jù)處理與分析操作時間短。因此，要求電子地圖的數(shù)據(jù)庫能夠智能通過GRPS聯(lián)網(wǎng)更新，進(jìn)行電子地圖數(shù)據(jù)的自適應(yīng)，并要求裝載硬盤的剩余空間足夠大而擁有不斷下載更新包的能力。 由上述約束條件，得到基于A*算法的最佳路徑的算法流程圖。 歐氏距離在路網(wǎng)中的代碼如下： function distance=euclideandis(x，y)％x and y：two vectors to be tested． if(max(size(x))-----max(size(y)))％label lerror(’Array sizes do not match．’)； end if((rain(size(x))--=1)l(min(size(y))-一-1)) error(’Both x and Y are vectors’)； end％label2 distance=sqrt(sum((x?y)．^2))／max(size(x))； GPS \DR快速定位功能彌補(bǔ)了遙感不足，GPS 能將遙感獲取數(shù)據(jù)實時快速進(jìn)入地理信息系統(tǒng)，并保證遙感數(shù)據(jù)與地面同步監(jiān)測數(shù)據(jù)獲取動態(tài)配準(zhǔn)，動態(tài)進(jìn)入GIS（地理信息系統(tǒng)，Geographic Information System）、RS (遙感，Remote Sensing) 數(shù)據(jù)庫。同時，利用遙感數(shù)據(jù)可實現(xiàn)GPS 定位遙感信息查詢。GIS系統(tǒng)，GPS 定位信息電子地圖上將以實時反映和漫游查詢。將GPS 和電子圖相配合，可組成各種電子導(dǎo)航和監(jiān)控系統(tǒng)。并且，GPS\DR 可為GIS 及時采集，更新和修正數(shù)據(jù)，輸入電子圖或數(shù)據(jù)庫后，可對原有專題圖進(jìn)行修正，核實或形成新專題圖件，從而得到動態(tài)實時的顯示車輛的運(yùn)行狀況，車輛所處的位置，周圍道路兩側(cè)的空間信息等[10]。 通過最小距離點連點的方法獲取原始路徑，再由行車電腦內(nèi)置的大容量導(dǎo)航電子地圖處理相關(guān)位置信息，同時，對比優(yōu)化電子地圖的數(shù)據(jù)庫進(jìn)行自適應(yīng)管理，添補(bǔ)更多的路面信息，包括路途上的交通信息，入限速標(biāo)志、交叉路口轉(zhuǎn)彎限制、信號燈等。 根據(jù)當(dāng)前位置和將要到達(dá)的目標(biāo)位置(工作時輸入)，導(dǎo)航系統(tǒng)自動，實時地計算和顯示最短路徑或最佳路徑，引導(dǎo)駕駛員最快地到達(dá)目的地。最短路徑或最佳路徑的分析計算量比較大，因此采用上述的算法，減少系統(tǒng)的搜索時間和運(yùn)算速度至關(guān)重要。最佳路徑的選擇不僅要考慮，距離最短，而且也要考慮時間最省，道路狀況，交通管制等因素[11]。根據(jù)用戶的要求，系統(tǒng)建立空間索引，通過查詢和分析數(shù)據(jù)庫的歷史數(shù)據(jù)和道路空間數(shù)據(jù)的信息，選擇滿足用戶要求的一條路線。 本文討論分析了基于車輛監(jiān)控導(dǎo)航系統(tǒng)的A*算法最佳路徑,并通過相關(guān)的約束條件進(jìn)行優(yōu)化。針對城鄉(xiāng)路網(wǎng)的特點，對最短路徑分析的各項關(guān)鍵技術(shù)進(jìn)行了研究，編寫了相關(guān)路徑選擇程序進(jìn)行了模擬，提出了一種實用的最佳路徑分析解決方案，在此基礎(chǔ)上實施了最佳路徑分析方法及技術(shù)；城市交通設(shè)施和規(guī)則日益復(fù)雜，需要進(jìn)一步改進(jìn)數(shù)據(jù)模型，較完整地表達(dá)和建立了路網(wǎng)的拓?fù)潢P(guān)系。本文的算法能較準(zhǔn)確、快速地檢測和提取出運(yùn)動目標(biāo),為交通調(diào)度提供了保障,有一定的實用價值。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 撰寫的目的：為緩解城市交通擁擠，改善交通狀況，保障公共安全，提高汽車出行效率，通過以GPS為核心的動態(tài)路徑分析，配合交通部門調(diào)度，使得交通網(wǎng)絡(luò)運(yùn)行暢通。 撰寫的基本思路： 以基于靜態(tài)路網(wǎng)的A*算法為核心，通過對原算法添加道路權(quán)值的約束（約束包括：道路等級系數(shù)、道路堵塞系數(shù)、道路通過系數(shù)等），判斷路徑的動態(tài)情況，并作出車輛與路網(wǎng)的實時匹配，從而獲得對交通行駛最有利的高效路徑。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 引入了啟發(fā)式函數(shù)，估價每一生成節(jié)點以確定此節(jié)點的優(yōu)劣性。因為算法首先搜索最有希望的節(jié)點，啟發(fā)式函數(shù)決定在諸多路徑中首先遍歷那條路徑以便搜索過程更有效。通過添加道路權(quán)值改進(jìn)A*算法，更精確地尋找出適合交通行駛的動態(tài)路徑。算法通過添加約束條件的推薦系數(shù)，結(jié)合實時交通情況對車輛進(jìn)行有效地調(diào)度，提高道路的利用效率。GPS/DR相關(guān)模塊的引入，減少系統(tǒng)的搜索時間和運(yùn)算速度，便于最佳路徑的快速獲得。
應(yīng)用價值和現(xiàn)實意義
- 針對城市路網(wǎng)的特點，對最短路徑分析的關(guān)鍵技術(shù)進(jìn)行了優(yōu)化，提出實用的最佳路徑分析解決方案，在此基礎(chǔ)上實施了最佳路徑分析方法及技術(shù)。隨著城市交通設(shè)施和規(guī)則日益復(fù)雜，需要電子地圖數(shù)據(jù)庫能夠完整地建立和表達(dá)路網(wǎng)的拓?fù)潢P(guān)系。本文的算法能準(zhǔn)確、快速地檢測和提取出運(yùn)動目標(biāo)并有很強(qiáng)的實踐性,仿真程序能夠按照算法約束條件的動態(tài)反饋信息對突發(fā)事件作出及時的處理，從而為城鄉(xiāng)交通路網(wǎng)提供有效的、智能化的調(diào)度。
學(xué)術(shù)論文摘要
- 利用車輛導(dǎo)航技術(shù)的反饋信息，通過A*算法對靜態(tài)路網(wǎng)的最優(yōu)路徑做出動態(tài)選擇?；陟o態(tài)路網(wǎng)信息的最優(yōu)路徑求解是現(xiàn)時車輛GPS導(dǎo)航領(lǐng)域所面臨的關(guān)鍵問題?，F(xiàn)今流行的Dijkstra算法、A*算法等，都是基于完全靜態(tài)、確定的信息數(shù)據(jù)庫下，求解得出的最短路徑。本文通過A*算法充分利用靜態(tài)路網(wǎng)信息，借助車輛導(dǎo)航系統(tǒng)加以動態(tài)路網(wǎng)中的適應(yīng)條件，以及實時更新的交通數(shù)據(jù)，得出計算結(jié)果精確，時間復(fù)雜度較低，且符合實際情況的最佳路徑。
獲獎情況
- 無
鑒定結(jié)果
- 本自然論文是由曾志雄等同學(xué)在老師的指導(dǎo)下通過一系列的理論分析和討論研究獨(dú)立編撰完成的，情況屬實。并且，論文符合挑戰(zhàn)杯課外學(xué)術(shù)科技作品競賽的要求。
參考文獻(xiàn)
- [1]楊利強(qiáng),張寧,陶志祥. 3G移動通信技術(shù)在城市交通信息系統(tǒng)中的應(yīng)用研究[J]. 公路交通科技, 2007,(12) [2]楊兆升. 關(guān)于智能運(yùn)輸系統(tǒng)的關(guān)鍵理論——綜合路段行程時間預(yù)測的研究[J]. 交通運(yùn)輸工程學(xué)報, 2001,(01) [3]于德新，楊兆升，高鵬. 動態(tài)限制搜索區(qū)域的帶約束K則最優(yōu)路徑算法[J]. 吉林大學(xué)學(xué)報（工學(xué)版），2009（39）2:172-176 [4]Van der Auweraer H,Mas P,Dom S,et al. Transfer analysis in the critical path of vehicle refinement:the role of fast,hybrid and operational path analysis .SAE Paper 2007 -01-2352 [5]楊瑞臣,周永付,云慶夏. 尋找車輛最優(yōu)路徑的混合算法[J]. 交通運(yùn)輸工程學(xué)報, 2005,(01) [6]張?zhí)m,雷秀娟. 幾種改進(jìn)PSO算法在帶時間窗車輛路徑問題中的比較與分析[J]. 計算機(jī)工程與科學(xué), 2008,(12) [7]Juha Plunt. Finding and fixing vehicle nvh problems transfer path analysis[J] .Sound and Vibration, 2005, 39 (11) :12-16 [8]Hendricx William,De Vis Dirk. An overview of the European research project DIANA .SAE Paper 971897 [9]賀竹磬,孫林巖. 動態(tài)交通下車輛路徑選擇模型及算法[J]. 交通運(yùn)輸工程學(xué)報, 2007,(01) [10]李瑞敏,陸化普. 基于WebGIS的智能交通管理指揮調(diào)度系統(tǒng)[J]. 計算機(jī)工程, 2007,(21)
同類課題研究水平概述
- 1、美國、西歐和日本等發(fā)達(dá)國家為了解決共同所面臨的交通問題，競相投入大量資金和人力，開始大規(guī)模地進(jìn)行道路交通運(yùn)輸智能化的研究試驗。 2、在美國，智能交通應(yīng)用發(fā)展較快的幾個方面分別是，車輛安全系統(tǒng)（占 51%），電子收費(fèi)（占37%），公路及車輛管理系統(tǒng)（占28%），實時自動定位系統(tǒng)（占20%），商業(yè)車輛管理系統(tǒng)（占14%）。因為美國交通路網(wǎng)的前期規(guī)劃十分合理，因此其關(guān)注的重點是安全。 3、北美、歐洲和日本的很多城市現(xiàn)在都在開始使用“自適應(yīng)面控系統(tǒng)”，即面控的信號燈系統(tǒng)模式，而我國還主要停留在點控的信號燈系統(tǒng)模式上，可見差距巨大。國外一些城市現(xiàn)在已經(jīng)嘗試對每輛車安裝GPS，以此確定每輛車的位置，最終通過物流網(wǎng)技術(shù)來調(diào)節(jié)交通擁堵。而國內(nèi)還在對智能交通系統(tǒng)的基礎(chǔ)——中國國情下的“車流量”如何計算投入研究，規(guī)劃實現(xiàn)一條線上四五個路口之間信號燈配合的線控系統(tǒng)模式。 4、國外的研究表明，智能交通系統(tǒng)可極大地提高公路的通行能力和服務(wù)水平，使每條車道每小時的車流量增加2至3倍，縮短行車時間35％ ～50％。此外，智能交通系統(tǒng)還可以大大提高公路交通的安全性，降低并排除人為錯誤、駕駛員心理對交通安全的消極影響，使預(yù)防和避免交通事故成為可能。從理論上講，智能交通系統(tǒng)可以減少事故31％ ～85％。 5、利用地理信息系統(tǒng)（GIS），GPS，專用短程通信技術(shù)（DSRC）開發(fā)ATIS，ETC，CVO的車輛安全系統(tǒng)作為智能交通的主要應(yīng)用在全球范圍內(nèi)已呈一種趨勢。 6、智能交通的前景是美好的，但也是交通運(yùn)輸領(lǐng)域中技術(shù)難度最高的系統(tǒng)，其中，基于磁性標(biāo)記誘導(dǎo)的車輛車道自動保持技術(shù)是當(dāng)今世界車輛工程及自動控制領(lǐng)域的研究前沿，無論在理論上，還是在工程實踐上都是對各國科研攻關(guān)實力和水平的考驗。
