基于GIS的路徑規(guī)劃系統(tǒng)的研究

1、基于gis的路徑規(guī)劃系統(tǒng)的研究 摘要本文針對現(xiàn)存的尋路方法難以實(shí)現(xiàn)多目的地的最佳路徑求解和交通規(guī)則難以考慮這一問題,以實(shí)現(xiàn)動態(tài)路徑規(guī)劃為目標(biāo),引入了嵌入式開發(fā)平臺一,對其中的關(guān)鍵技術(shù)做了一定的研究,并對現(xiàn)有的最短路算法進(jìn)行了一定的改進(jìn),設(shè)計(jì)和實(shí)現(xiàn)了基于嵌入式的多目的地路徑規(guī)劃系統(tǒng),實(shí)現(xiàn)了真正意義上的路徑規(guī)劃。本文對普通電子地圖進(jìn)行了改進(jìn),并建立了包括道路等級、道路狀況、路段長度、路段交通量等級和行駛規(guī)則等屬性數(shù)據(jù)的數(shù)據(jù)庫,使其能夠滿足路徑規(guī)劃系統(tǒng)的需要;對嵌入式平臺進(jìn)行了深入的研究,并對其關(guān)鍵技術(shù)進(jìn)行了改造,使得路徑規(guī)劃系統(tǒng)運(yùn)用靈活,對屬性信息的處理簡單方便,不影響應(yīng)用程序的使用:將問題分解為

2、局部路徑規(guī)劃和全局路徑規(guī)劃兩部分分別求解,引入了啟發(fā)式搜索算法算法,定義了適合問題求解的兩個不同的估價函數(shù),使其能夠在資源有限的嵌入式設(shè)備上實(shí)現(xiàn)目的地為多點(diǎn)的路徑求解;并通過對路網(wǎng)的改造對交通規(guī)則和一些特殊的交通狀況進(jìn)行了處理;根據(jù)道路等級給道路分配了不同的權(quán)重,可以向用戶提供其根據(jù)自己喜好選定的最優(yōu)目標(biāo)下的最優(yōu)路線信息:對系統(tǒng)進(jìn)行了整體設(shè)計(jì)、框架分析、數(shù)字地圖設(shè)計(jì)、基礎(chǔ)設(shè)計(jì)以及算法的設(shè)計(jì),并在此基礎(chǔ)之上實(shí)現(xiàn)了路徑規(guī)劃系統(tǒng)的演示。本系統(tǒng)采用動態(tài)的計(jì)算方法,考慮道路的自身特性如單行線、塞車、修路等,根據(jù)這些特性及用戶需求得到不同的解,并把這些解直觀的在電子地圖上顯示出來,具有一定的理論意義。應(yīng)用

3、方面,該系統(tǒng)可以在掌上電腦上實(shí)現(xiàn)路徑規(guī)劃也可應(yīng)用于火車站、旅館等游客集中地。還可應(yīng)用于物流調(diào)度中心,可根據(jù)需求調(diào)度貨車的行程。將來如與結(jié)合起來還可以作為車載導(dǎo)航或手機(jī)導(dǎo)航使用,具有很高的應(yīng)用價值。關(guān)鍵詞:路徑規(guī)劃;地理信息系統(tǒng);最短路;最省時路;最短路算法 缸 , .,:.甜;.髓. 伍 ;, .,仕,啪. . ., .: ;獨(dú)創(chuàng)性說明作者鄭重聲明:本碩士學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得研究成果。盡我所知,除了文中特別加以標(biāo)注和致謝的地方外,論文中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果,也不包含為獲得大連理工大學(xué)或其他單位的學(xué)位或證書所使用過的材料。與我一同工作的同志對本研究所做

4、的貢獻(xiàn)均已在論文中做了明確的說明并表示廣謝意。聲云毒作者簽名:日期:型絲竺基于的路徑規(guī)劃系統(tǒng)研究引言.問題的提出隨著國際化城市的發(fā)展,交通事業(yè)也正以前所未有的速度迅猛發(fā)展著。交通圖上的道路日益增多,單行線、路口禁止轉(zhuǎn)向等交通管理措施也被越來越廣泛地采用。這對于出行者來說,一方面為他們提供了更大的出行路線的選擇余地,保證了路網(wǎng)的暢通,但同時也增大了其出行的復(fù)雜性。因此智能交通已經(jīng)受到了國際社會的普遍重視,而作為其重要組成部分的路徑規(guī)劃系統(tǒng)更是一個國際化城市的必備服務(wù)設(shè)施。概括來說,路徑規(guī)劃系統(tǒng)的作用主要包括以下幾個方面:幫助用戶規(guī)劃行程,得到最合理的出行路線;向用戶提供其根據(jù)自己喜好選定的最優(yōu)目

5、標(biāo)下的最優(yōu)路線信息,從而帶來時間的節(jié)約以及巨大的社會效益和經(jīng)濟(jì)效益;是減少交通擁堵的一個高效而可行的方式。不僅可帶來經(jīng)濟(jì)效益,還可減少交通環(huán)境污染,為建立可持續(xù)發(fā)展的交通模式提供了一種思路;優(yōu)化交通流在整個路網(wǎng)上的分配。目前國內(nèi)存在一些路徑導(dǎo)向系統(tǒng)只能給出兩點(diǎn)之間的路徑,而且一般采用靜態(tài)方式計(jì)算,不能根據(jù)路況的變化時時求解,有的甚至不考慮交通規(guī)則。主要困難在于現(xiàn)在普遍使用的尋路算法均為經(jīng)典的最短路算法,只能給出兩點(diǎn)問的最短路,不能實(shí)現(xiàn)多目的地的最短路求解,也無法對一些特殊情況如,單行線、路口禁止轉(zhuǎn)向等進(jìn)行處理。并且嵌入式設(shè)備資源普遍緊張,而最佳路徑求解算法復(fù)雜。用現(xiàn)有的方法更加難以實(shí)現(xiàn)。這樣系

6、統(tǒng)往往會產(chǎn)生以下問題:當(dāng)用戶的目的地為多點(diǎn)時,這樣的系統(tǒng)是無法滿足用戶需求的。由于采用的算法是靜態(tài)的,當(dāng)路況發(fā)生變化時系統(tǒng)給出的最優(yōu)路徑可能已經(jīng)失去意義了。不考慮交通規(guī)則的系統(tǒng)給出的路線很有可能出現(xiàn)單行線逆向通行的情況,根本無法使用。因此真正意義上的路徑規(guī)劃系統(tǒng)應(yīng)該在計(jì)算過程中充分考慮路況的變化、道路的狀態(tài)和交通規(guī)則的因素,并能給出目的地為多點(diǎn)的路線規(guī)劃,這樣才能為用戶提供準(zhǔn)確、及時的出行參考,從而幫助用戶規(guī)劃行程,得到最合理的出行路線,并在客觀上起到優(yōu)化交通流在整個路網(wǎng)上分配的效果。另一方面,路徑規(guī)劃系統(tǒng)應(yīng)該以直觀的圖文形式為用戶提供信息,并盡可能簡化操作過程使用戶易于基于的路徑規(guī)劃系統(tǒng)研究

7、使用。近年來,技術(shù)的發(fā)展為多目的地動態(tài)路徑規(guī)劃系統(tǒng)的開發(fā)創(chuàng)造了有利的條件。經(jīng)過從模塊到集成式、核心式和組件式以及的發(fā)展歷程,已廣泛的深入到各行各業(yè),其應(yīng)用和發(fā)展成為勢不可擋的國際潮流。尤其是路徑規(guī)劃及汽車導(dǎo)航這一領(lǐng)域,更是應(yīng)當(dāng)充分利用技術(shù)為路徑規(guī)劃提供處理地理信息的支持,并為用戶提供直觀的可視化操作環(huán)境。尤其是,現(xiàn)今地理信息系統(tǒng)領(lǐng)域發(fā)展的最新特點(diǎn)是組件式,而組件式憑借其強(qiáng)大的功能的靈活性,可能會為智能交通系統(tǒng)的發(fā)展帶來一場新的革命。組件式適應(yīng)性強(qiáng)、應(yīng)用面廣、使用簡單能夠簡化路徑規(guī)劃系統(tǒng)的研制,縮短其開發(fā)周期,進(jìn)一步增加系統(tǒng)的功能。本文針對現(xiàn)存的尋路方法難以實(shí)現(xiàn)多目的地的最佳路徑求解和交通規(guī)則難

8、以考慮這一問題,以實(shí)現(xiàn)動態(tài)路徑規(guī)劃為目標(biāo),引入了嵌入式開發(fā)平臺一,對其中的關(guān)鍵技術(shù)做了一定的研究,并對算法進(jìn)行了一定的改進(jìn),設(shè)計(jì)和實(shí)現(xiàn)了基于嵌入式的多目的地路徑規(guī)劃系統(tǒng),實(shí)現(xiàn)了真正意義上的路徑規(guī)劃。.國內(nèi)外同類問題研究綜述.地理信息系統(tǒng)璐的研究綜述概述地理信息系統(tǒng)就是一種利用計(jì)算機(jī)對有關(guān)地理、空間位置的數(shù)據(jù)信息進(jìn)行存儲、處理、查詢和顯示的計(jì)算機(jī)支持系統(tǒng)【”。的發(fā)展始于年代,是計(jì)算機(jī)同步發(fā)展的結(jié)果。今天的地理信息系統(tǒng)集成了計(jì)算機(jī)數(shù)據(jù)庫技術(shù)和計(jì)算機(jī)圖形輔助設(shè)計(jì)軟件。在圖象處理上比上述兩類軟件更加全面,郎地理信息系統(tǒng)所處理的事物對象具有空間地理特征,也具有統(tǒng)計(jì)信息特征?？梢哉f,地理信息系統(tǒng)將空間信息

9、數(shù)字化,并使這些信息可視化,通過功能強(qiáng)大的軟件,使空間分析直觀簡明,數(shù)據(jù)管理便捷高效。通過地理信息系統(tǒng)的普及和應(yīng)用,其強(qiáng)大的功能將成為交通信息管理的必備工具,成為科學(xué)管理和決策的依據(jù)。基于公路數(shù)據(jù)庫基礎(chǔ)上的交通地理信息系統(tǒng)?的研究是公路建設(shè)管理現(xiàn)代化的基礎(chǔ)。它不僅能夠適應(yīng)各種層次管理部門隨時了解已有公路現(xiàn)狀的需求,同時還能夠通過強(qiáng)大的空間分析能力和豐富的圖表顯示,實(shí)現(xiàn)公路養(yǎng)護(hù)管理的電子化【。的發(fā)展基于的路徑規(guī)劃系統(tǒng)研究國外的發(fā)展最早是在年。.博士提出“把地圖變成數(shù)字形式的地圖,使之更利于計(jì)算機(jī)處理和分析”。正是這個具有前瞻性的思想,導(dǎo)致了地理信息系統(tǒng)的誕生。年,.在一個會議上提出“地理信息系統(tǒng)

10、”這個術(shù)語。年加拿大建設(shè)了世界上第一個地理信息系統(tǒng)?加拿大地理信息系統(tǒng)口】。進(jìn)入本世紀(jì)年代以后,由于計(jì)算機(jī)硬件和軟件技術(shù)的飛速發(fā)展,促使朝著實(shí)用方向迅速發(fā)展,一些發(fā)達(dá)國家先后建立了許多專業(yè)性的土地信息系統(tǒng)和地理信息系統(tǒng)。例如,從年至年,美國地質(zhì)調(diào)查局就建成多個,加拿大、聯(lián)邦德國、瑞典和日本等國也相繼發(fā)展自己的。與此同時,一些商業(yè)公司開始活躍起來,軟件在市場上受到歡迎,許多大學(xué)和研究機(jī)構(gòu)開始重視軟件設(shè)計(jì)及應(yīng)用的研究。年代,由于計(jì)算機(jī)行業(yè)推出了圖形工作站和機(jī)等性價比大為提高的新一代計(jì)算機(jī),為普及和推廣應(yīng)用提供了硬件基礎(chǔ)。軟件的研制和開發(fā)也取得了很大成績,涌現(xiàn)出一些有代表性的軟件。如/懂、等。的普及

11、和推廣應(yīng)用又使得其理論研究不斷完善,使理論、方法和技術(shù)趨于成熟,開始有效地解決全球性的難題,例如全球沙漠化、全球可居住區(qū)的評價、厄爾尼諾現(xiàn)象及酸雨、核擴(kuò)散及核廢料等問題,以及全球變化與全球監(jiān)測。剛我國的發(fā)展我國的起步較晚,到年代末才提出開展研究的倡議。進(jìn)入年代后迅速發(fā)展,在理論探索、規(guī)范探討、實(shí)驗(yàn)技術(shù)、軟件開發(fā)、系統(tǒng)建立、人才培養(yǎng)和區(qū)域性、專題性試驗(yàn)等方面都取得了突破和進(jìn)展。一些有遠(yuǎn)見的地方政府也開始投資建立本地的,在應(yīng)用日益活躍的今天,諸如沙市這樣名不見經(jīng)傳的中小城市,由于起步早而譽(yù)冠全國。年代末,武漢測繪科技大學(xué)在攝影測量與遙感專業(yè)的基礎(chǔ)上建立信息工程專業(yè),使我國基本人才的培養(yǎng)納入了正軌。

12、年月,我國專門成立了“中國協(xié)會”,此后又成立了“中國技術(shù)應(yīng)用協(xié)會”,加強(qiáng)了國內(nèi)各種學(xué)術(shù)交流,研制推出了、.、等具有自主版權(quán)的軟件,使得我國的技術(shù)已開始躋身于國際先進(jìn)行列糾。的問題在流行的軟件中,因?yàn)樯虡I(yè)或者別的因素,一般都是采用了有限種類的數(shù)據(jù)格式轉(zhuǎn)換接,加上在這些軟件中的前端開發(fā)工具代碼效率與穩(wěn)定性和執(zhí)基于的路徑規(guī)劃系統(tǒng)研究行速度的限制,使得不論從系統(tǒng)設(shè)計(jì)開發(fā)者、還是從使用者的角度看來,都不能得到滿意的結(jié)果。作為空間數(shù)據(jù)分析和處理的工具,缺乏知識處理和進(jìn)行啟發(fā)式推理的能力,不能給設(shè)計(jì)者與使用者提供智能化的功能。因此,與擅長啟發(fā)式推理和擅長分析決策的知識表示理論相融合,實(shí)現(xiàn)綜合分析處理,以數(shù)字

13、化的手段統(tǒng)一實(shí)現(xiàn)對相關(guān)現(xiàn)象的重現(xiàn)和認(rèn)識,則是解決目前所面臨問題的重要途徑【】。的研究方向現(xiàn)今國內(nèi)步的研究主要集中在以下幾方面:與其它學(xué)科的交叉結(jié)合伴隨著的成熟與發(fā)展,人們將與其它任何可以結(jié)合的學(xué)科進(jìn)行集成研究,輸出方式更直觀,以滿足人們生產(chǎn)、生活的各種需求,使人們可以合理利用資源,保護(hù)環(huán)境,實(shí)現(xiàn)人類可持續(xù)性發(fā)展。事實(shí)上,已涉及到社會科學(xué)、自然科學(xué)的許多領(lǐng)域,因此,我們還可以得出這樣的結(jié)論,必將發(fā)展成為集社會科學(xué)、自然科學(xué)于一體的全球性的綜合性的巨型軟科學(xué)?；谝蛱鼐W(wǎng)的是下階段的一個發(fā)展主流如今計(jì)算機(jī)網(wǎng)絡(luò)迅速興起和發(fā)展,可以將數(shù)字化的地理信息和空間數(shù)據(jù)方便、快速和及時地傳送到需要的地方去,以充分

14、發(fā)揮其應(yīng)用價值。因此需要研制基于網(wǎng),采用技術(shù),采用/體系結(jié)構(gòu)或多層/體系結(jié)構(gòu)的曲和視窗以方便網(wǎng)上用戶使用。組件式的研究組件式軟件開發(fā)的基本思想,是將的各大功能模塊劃分為幾個“部件”,每個“部件”完成不同的功能,各個“部件”之聞可以方便的通過可視化的軟件開發(fā)工具集成起來,形成最終的應(yīng)用?！安考比缤欢迅魇礁鳂拥姆e木,他們分別實(shí)現(xiàn)不同的功能,根據(jù)需要把這些“積木”搭建起來,就構(gòu)成了應(yīng)用系統(tǒng)。因此如何分解出這些“部件”以及怎樣將它們通過標(biāo)準(zhǔn)的系統(tǒng)環(huán)境,與其它非的“部件”嵌接,有效地實(shí)現(xiàn)系統(tǒng)合成,如和自然就成了的研究方向。與多媒體技術(shù)的結(jié)合多媒體技術(shù)正在應(yīng)入中,以改善的數(shù)據(jù)采集、數(shù)據(jù)處理以及成果表達(dá)

15、與輸出的效能,發(fā)揮聲、像等多媒體的應(yīng)用。目前,圖形圖像的立體顯示已成功地融入數(shù)字?jǐn)z影測量系統(tǒng)中,與的集成和多媒體技術(shù)的應(yīng)用將把我們感興趣的東西變成一個虛擬實(shí)體,我們可以通過的輸出系統(tǒng)用視覺、基于的路徑規(guī)劃系統(tǒng)研究聽覺、觸覺、嗅覺等來感知它。發(fā)展趨勢自世紀(jì)年代問世以來,經(jīng)過多年的蓬勃發(fā)展,不論在理論上還是在技術(shù)上都取得了很大的進(jìn)展,一些系統(tǒng)和應(yīng)用軟件日趨成熟和完善。但是地理信息系統(tǒng)技術(shù)的發(fā)展還遠(yuǎn)沒有止境,仍處于急劇變化之中,主要表現(xiàn)在以下方面“”:與專家系統(tǒng)和神經(jīng)網(wǎng)絡(luò)的結(jié)合;與虛擬現(xiàn)實(shí)技術(shù)的、結(jié)合;真三維和時空;移動;與、結(jié)合的“”、技術(shù)等。.智能運(yùn)輸系統(tǒng)的研究綜述智能運(yùn)輸系統(tǒng): 是高效、綜合地

16、運(yùn)用了信息技術(shù)、電子通信、自動控制、傳感器、運(yùn)籌學(xué)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等諸多先進(jìn)的最新科研成果,立起來的一種大范圍、全方位、實(shí)時、準(zhǔn)確、高效的交通運(yùn)輸綜合管理和控制系統(tǒng)【。的發(fā)展現(xiàn)狀,】國外的發(fā)展,從國際上智能運(yùn)輸系統(tǒng)的發(fā)展歷史來看,起步于世紀(jì)一年代的交通管理計(jì)算機(jī)化就是智能運(yùn)輸系統(tǒng)的萌芽。自世紀(jì)年代末以來,國際領(lǐng)域已形成美國、歐洲和日本三強(qiáng)鼎立的局面。年,歐洲啟動智能運(yùn)輸系統(tǒng)研究的第一批項(xiàng)目和;年,美國國會通過了“綜合地面運(yùn)輸效率方案”,旨在利用高新技術(shù)和合理的交通分配提高整個公路路網(wǎng)的效率【。日本目前在項(xiàng)目上已經(jīng)形成了官方、民間、學(xué)術(shù)機(jī)構(gòu)的協(xié)調(diào)體制,特別重視技術(shù)的商品化發(fā)展和不停車收費(fèi)系

17、統(tǒng)的開發(fā)。目前正在進(jìn)行的全面應(yīng)用開發(fā)工作,的主要功能如交通管理、導(dǎo)駛和電子收費(fèi)等都圍繞和全歐無線數(shù)據(jù)通信網(wǎng)來實(shí)現(xiàn)。國內(nèi)的發(fā)展【我國的發(fā)展起步較晚,世紀(jì)年代以來,從國外引進(jìn)消化了一些項(xiàng)目,并進(jìn)行了一些或類似基礎(chǔ)項(xiàng)目的研究和應(yīng)用。世紀(jì)年代中至年代初,主要是進(jìn)行城市交通信號控制試驗(yàn)研究,世紀(jì)年代中至年代初,在一些大城市引進(jìn)和消化城市交通信號控制系統(tǒng),實(shí)現(xiàn)了一些高速公路監(jiān)控系統(tǒng)、高等級公路電子收費(fèi)系統(tǒng)和路邊信息服務(wù)系統(tǒng),如廣佛高速公路監(jiān)控系統(tǒng)、首都機(jī)場高速公路電子收費(fèi)系統(tǒng)。世紀(jì)年代中以來,開始研究部門基于的路徑規(guī)劃系統(tǒng)研究發(fā)展戰(zhàn)略和、在交通中的應(yīng)用,重視交通信息網(wǎng)絡(luò)的建設(shè),如交通部的公路智能運(yùn)輸系統(tǒng)發(fā)

18、展戰(zhàn)略研究、鐵道部、等信息系統(tǒng)開發(fā)。公路和橋梁管理用基礎(chǔ)數(shù)據(jù)庫以及道路交通量和氣象數(shù)據(jù)采集等經(jīng)過多年的努力,也已取得明顯的進(jìn)展。的研究動向目前,大致的研究方向主要在交通控制與管理、車輛安全和控制、旅行信息服務(wù)、交通中人的因素、交通模型開發(fā)、行政和組織問題、通信與廣播技術(shù)、系統(tǒng)等方面【。根據(jù)上述研究方向現(xiàn)今的研究重點(diǎn)【】主要集中以下方面:先進(jìn)的交通通信系統(tǒng)根據(jù)信息采集、信息處理與信息傳送的繼承程度及系統(tǒng)功能分配的不問,可分為自動導(dǎo)航系統(tǒng)、單項(xiàng)通信系統(tǒng)和雙向通信系統(tǒng)。系統(tǒng)的研究與實(shí)施涉及的單位機(jī)構(gòu)、行業(yè)部門眾多,學(xué)科專業(yè)綜合性強(qiáng),專業(yè)聯(lián)合跨度大,因此具有很高的難度。先進(jìn)的交通管理系統(tǒng)就是從應(yīng)用計(jì)算

19、機(jī)和通信技術(shù)發(fā)展到將交通系統(tǒng)和車輛作為一個整體的系統(tǒng)。這個發(fā)展過程包括分析各種來源交通情報的軟件的發(fā)展、快速探測公路交通事故的設(shè)備的發(fā)展及感知并預(yù)測未來交通擁擠并給出交通管理最佳策略的專家系統(tǒng)的發(fā)展。先進(jìn)的車輛系統(tǒng)借助車載設(shè)備及路側(cè)、路表的電子設(shè)備來檢鍘周圍行駛環(huán)境的變化情況,進(jìn)行部分或完全的自動駕駛控制,以達(dá)到行車安全和增加道路通行能力的目的。的研究方向包括危險預(yù)警、碰撞前駕乘人員的安全保護(hù)、防止縱向碰撞和側(cè)向擦撞、交叉口避碰、自動公路系統(tǒng)。先進(jìn)的公共運(yùn)輸系統(tǒng)址呵致力于使公共運(yùn)輸與合乘車輛更有效和可靠,它向出行者傳達(dá)可靠和精確的情報,使更多的人可使用這些備選出行方式。商用車輛運(yùn)營系統(tǒng)指出商用

20、車輛駕駛員是技術(shù)運(yùn)用的中心,他們?yōu)槊绹枰焖俪鲂泻瓦\(yùn)貨的顧客提供服務(wù),而車隊(duì)駕駛員也需要知道他們車輛的位置和日程安排。.導(dǎo)航系統(tǒng)的研究綜述基于的路徑規(guī)劃系統(tǒng)研究車輛導(dǎo)航系統(tǒng)利用計(jì)算機(jī)和通訊技術(shù),向行駛在道路上的車輛提供信息,弓導(dǎo)車輛避開擁擠路段,沿最佳的線路到達(dá)目的地,它是智能化交通系統(tǒng)中效益顯著、見效快的項(xiàng)目,是歐、美、日等國竟相研究與開發(fā)的重點(diǎn)。車輛導(dǎo)航系統(tǒng)同交通管理與控制系統(tǒng)融合,可以在大范圍內(nèi)進(jìn)行交通流誘導(dǎo),從而緩解道路交通擁擠狀況;還可以向火警車輛、救護(hù)車輛與緊急救援車輛提供最短路徑引導(dǎo)服務(wù);此外,導(dǎo)航系統(tǒng)的應(yīng)用將大幅提高道路通行能力,減少交通事故,節(jié)省能源與時間,對解決當(dāng)前各國面

21、臨的嚴(yán)重的交通問題有著重要的意義。多年以來,許多專家學(xué)者都開展了這方面的研究與應(yīng)用,也取得了很多的成就,有的已經(jīng)進(jìn)入實(shí)用化階段【”。研究方向目前國內(nèi)外關(guān)于車輛導(dǎo)航系統(tǒng)的研究重點(diǎn)主要在以下及各方面:在導(dǎo)航系統(tǒng)中的應(yīng)用研究;導(dǎo)航系統(tǒng)算法的研究;導(dǎo)航系統(tǒng)分類的研究導(dǎo)航系統(tǒng)技術(shù)方面的研究。在導(dǎo)航系統(tǒng)中的應(yīng)用研究地理信息系統(tǒng)在車輛導(dǎo)航系統(tǒng)中發(fā)揮著十分重要的作用吲。在交通運(yùn)輸業(yè)中的應(yīng)用.最早起源于年代,并在世紀(jì)年代初開始獲得長足的發(fā)展。在最近的研究中,認(rèn)為,“毫無疑問,?的時代已到來,且代表了技術(shù)最重要的一個領(lǐng)域”拉”。也撰文認(rèn)為,“對的研究興趣和其挑戰(zhàn)潮流主要是三個視圖:地圖視圖 ,導(dǎo)航視圖 以及行為視

22、圖”這三個階段層次逐漸提高,由一維向平面、空間演進(jìn),從簡單靜態(tài)查找向復(fù)雜動態(tài)分析深入。到目前為止,對的研究主要集中在第一階段,即地圖視圖,其中的道路交通信息是存放在街道中線數(shù)據(jù)庫中的,并在此基礎(chǔ)上進(jìn)行道路交通網(wǎng)最短路徑搜索【?，F(xiàn)今,在車輛導(dǎo)航系統(tǒng)中應(yīng)用組件式開發(fā)已經(jīng)成為研究熱點(diǎn)。組件式是基于標(biāo)準(zhǔn)的組件式平臺,各個組件之間不僅可以進(jìn)行自由、靈活的重組,而且具有可視化的界面和使用方便的標(biāo)準(zhǔn)接口,允許跨語言應(yīng)用的組件提供的。同傳統(tǒng)比較,其具有許多特點(diǎn)如:可擴(kuò)展性:在組件式軟件技術(shù)背后,有一個十分龐大的組件資源庫,用戶可以從組件中挑選需要的組件與組件式一起集成應(yīng)用系統(tǒng),極大地擴(kuò)展了的功能,利用它開發(fā)的

23、系統(tǒng)具有無限的擴(kuò)展性。伸縮性:傳統(tǒng)結(jié)構(gòu)的封閉性,軟件龐大,不同系統(tǒng)之間交互性差,系統(tǒng)的開發(fā)難度大。組件式提供空間數(shù)據(jù)的采集、存儲、管理、分析和模擬等基于的路徑規(guī)劃系統(tǒng)研究功能,至于其他非功能如關(guān)系數(shù)據(jù)庫管理、統(tǒng)計(jì)圖表制作等則可以使用專業(yè)廠商提供的專門組件,有利于降低軟件開發(fā)成本,用戶可以根據(jù)實(shí)際需要選擇所需控件,具有選擇的伸縮性。另外,拓?fù)浠碾娮拥貓D是導(dǎo)航系統(tǒng)的基礎(chǔ),路徑優(yōu)化算法主要依賴于地圖中道路的拓?fù)潢P(guān)系。電子地圖的建立一般有兩種選擇,一種是利用現(xiàn)有的平臺,但是考慮到嵌入式設(shè)備的硬盤空間和運(yùn)行速度等因素,不太可能裝上這樣大型的平臺;另一種是自己編程實(shí)現(xiàn),這種方法的缺點(diǎn)在于自己建立的地圖拓

24、撲關(guān)系不完備和空間分析功能不強(qiáng)。地理信息系統(tǒng)控件則避免了二者的缺點(diǎn),首先控件體積小,可以滿足系統(tǒng)對硬盤和速度的要求,同時還具備了大型地理信息系統(tǒng)的基本功能。因此,利用地理信息系統(tǒng)控件開發(fā)路徑規(guī)劃系統(tǒng)是一個很好的選擇【】。導(dǎo)航系統(tǒng)算法的研究在旅行前或旅行中為駕駛員提供參考行駛路線和駕駛引導(dǎo)的過程,是車輛導(dǎo)航系統(tǒng)的基本功能之一。針對陸地車輛導(dǎo)航的不同要求,在路徑規(guī)劃中可采取多種優(yōu)化標(biāo)準(zhǔn),如最短距離、最少行駛時間或收費(fèi)等。但無論使用哪種標(biāo)準(zhǔn),路徑規(guī)劃最終都可以歸結(jié)為在特定道路網(wǎng)絡(luò)中搜索總代價最小的目標(biāo)路徑問題,其求解的理論基礎(chǔ)就是經(jīng)典的迪杰斯特拉日妨最短路徑算法叨,已經(jīng)有許多針對這一算法的具體實(shí)現(xiàn)口

25、】;另外還有算法算法,啟發(fā)式算法等。算法算法是由.于年提出的一個適用于所有弧的權(quán)均為非負(fù)的最短路算法,也是目前公認(rèn)的求解最短路問題高效的經(jīng)典算法之一。它可給出從某指定結(jié)點(diǎn)到圖中其它所有結(jié)點(diǎn)的最短路。其時間復(fù)雜度為.,為結(jié)點(diǎn)個數(shù)【】。?算法該算法分別由和在世紀(jì)年代提出。其時間復(fù)雜度是,是邊,弧數(shù)。目前這樣的時間復(fù)雜度在所有帶有負(fù)權(quán)弧的最短路算法中是最好的。但其實(shí)際運(yùn)算效果卻往往不及等算法【。匿算法算法是一個求圖中所有結(jié)點(diǎn)對間最短路的算法,由于年提出。其時間復(fù)雜度為,雖然與對每一結(jié)點(diǎn)作一次算法的時間復(fù)雜度相同,但其實(shí)際運(yùn)算效果要好于后者【?；诘穆窂揭?guī)劃系統(tǒng)研究啟發(fā)式算法當(dāng)今啟發(fā)式算法是解決這一問

26、題最流行的算法,多年來許多學(xué)者對這一問題進(jìn)行了深入研究,提出了種各樣的啟發(fā)式方法【】。大體上可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。簡單啟發(fā)式方法包括:年和】首先提出的啟發(fā)式節(jié)省法,路線內(nèi)/間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。兩階段方法包括先分組后定路線 和先定路線后分.組 兩種啟發(fā)式策略。前者是先將所有需求點(diǎn)大略分為幾個組,然后再對各個組分別進(jìn)行路線排序;后者則是先將所有的需求點(diǎn)建構(gòu)成一條路線,再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。年以來,人工智能方法在解決組合優(yōu)化問題上顯示出強(qiáng)大功能,在各個領(lǐng)域得到充分應(yīng)用,很多學(xué)者也將人工智能引入車輛路線

27、問題的求解中,并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。禁忌搜索法基本上是屬于一種人工智能型的局部搜尋方法,首先引入該算法,隨后亦有許多位學(xué)者也發(fā)表了求解的算法;提出了模擬退火算法【】;采用了遺傳算法編碼解決車輛路線問題;提出了采用遺傳算法和禁忌搜索方法的混合策略嘲:和 刀則首先用模擬退火算法將車輛路線的數(shù)量最小化,然后用大鄰域搜索法辯瞰曲將運(yùn)輸費(fèi)用降到最低。導(dǎo)航系統(tǒng)分類的研究目前國內(nèi)外已經(jīng)存在的路徑規(guī)劃系統(tǒng)基本上可以分為兩大類:靜態(tài)路徑規(guī)劃系統(tǒng)以幾何距離、道路質(zhì)量為路阻計(jì)算的最短路徑和靜態(tài)路徑都屬于靜態(tài)型最優(yōu)路徑,目前車輛導(dǎo)航系統(tǒng)動態(tài)交通分配研究中多采用該類路徑,計(jì)算結(jié)果與真實(shí)最短路存在較大差

28、異【。靜態(tài)路徑規(guī)劃系統(tǒng)用于路徑規(guī)劃的路況信息數(shù)據(jù)庫固定不變。主要產(chǎn)品有:北京靈圖科技的“天行者之縱橫四?！?它具有地圖顯示縮放,漫游、信息采集與濾波、車輛定位及路段匹配、地名查詢名稱查詢,分類查詢,坐標(biāo)查詢、最優(yōu)路線設(shè)計(jì)、路徑引導(dǎo)文字引導(dǎo)及語音引導(dǎo)、航跡記錄與管理等功能,還可以利用提供的無線通訊功能,向服務(wù)中心申請興趣點(diǎn)查詢、路況信息服務(wù)、最佳路徑導(dǎo)引等服務(wù)【柏】;蘇州宇達(dá)電通的“易上路”等。動態(tài)路徑規(guī)劃系統(tǒng)基于的路徑規(guī)劃系統(tǒng)研究實(shí)時動態(tài)最優(yōu)路徑是真實(shí)的最短路徑,并且,若想提高導(dǎo)航信息的準(zhǔn)確度,擁擠程度最低、綜合最優(yōu)路徑的計(jì)算都應(yīng)以動態(tài)行程時間為依據(jù),可見,車輛導(dǎo)航系統(tǒng)應(yīng)以動態(tài)行程時間作為計(jì)算

29、最優(yōu)路徑的基礎(chǔ),并提供實(shí)時動態(tài)最優(yōu)路徑作為必備服務(wù)】。動態(tài)路徑規(guī)劃系統(tǒng)用于導(dǎo)航的路況信息數(shù)據(jù)庫按照交通流實(shí)時刷新,這需要交通信息中心將交通信息,如堵車情況,交通擁擠情況通過無線通訊鏈路傳到系統(tǒng),系統(tǒng)收到該信息后,對原始信息數(shù)據(jù)庫進(jìn)行刷新,從而可以選取最優(yōu)路徑,并能動態(tài)調(diào)整選取新的路徑。此類產(chǎn)品一般均處于研究階段,市場上還沒有正事發(fā)售的。導(dǎo)航系統(tǒng)技術(shù)方面的研究車輛定位導(dǎo)航技術(shù)始于世紀(jì)年代晚期。當(dāng)時美國聯(lián)邦公路局啟動了一個被稱為電子路徑誘導(dǎo)系統(tǒng),簡稱的項(xiàng)目。是具有無線路徑誘導(dǎo)能力的導(dǎo)航系統(tǒng),可用于控制和分配交通流【。世紀(jì)年代以后,特別是年代后期,車輛導(dǎo)航系統(tǒng)進(jìn)入了一個迅猛發(fā)展時期。這主要是由于有關(guān)

30、的相關(guān)技術(shù)日趨成熟,而有關(guān)的組織如歐洲的、日本的和美國的 等也竟相成立,的會議和刊物大量涌現(xiàn),從而形成了一個所謂的“”運(yùn)動。年日本進(jìn)行項(xiàng)目,該項(xiàng)目類似于項(xiàng)目的概念。世紀(jì)年代后期,歐洲啟動了工程項(xiàng)目,進(jìn)入了年代后又先后啟動了和兩個項(xiàng)目,隨后是項(xiàng)目,年代后期和等,美國實(shí)施了有、和。近年來,隨著、技術(shù)的成熟與發(fā)展,還有車載設(shè)備的不斷更新與升級,汽車導(dǎo)航系統(tǒng)技術(shù)已趨于成熟。導(dǎo)航系統(tǒng)產(chǎn)品的發(fā)展現(xiàn)狀國外的發(fā)展國外生產(chǎn)汽車導(dǎo)航系統(tǒng)具有代表性的廠家有阿爾派、飛利浦、索尼、松下、先鋒、建伍、通用、富士通、蘭德、意法、博世及德爾福等世界著名公司。在激烈的競爭中,日本公司的表現(xiàn)非常引人注目,可以說領(lǐng)導(dǎo)著這一領(lǐng)域的潮

31、流。例如日本阿爾派的系列汽車導(dǎo)航儀、超小型尺寸汽車導(dǎo)航儀、及汽車多媒體系統(tǒng)。飛利浦交互式汽車導(dǎo)航系統(tǒng),索尼.、汽車導(dǎo)航系統(tǒng)及手提式導(dǎo)航儀,松下、汽車導(dǎo)航儀,先鋒汽車導(dǎo)航儀,建伍系基于的路徑規(guī)劃系統(tǒng)研究列、系列汽車導(dǎo)航儀,三菱和富士通系列汽車導(dǎo)航儀,德法蘭寶和意法公司的汽車導(dǎo)航系統(tǒng)等。國內(nèi)的發(fā)展導(dǎo)航系統(tǒng)研制和應(yīng)用在我國起步較晚。但是發(fā)展非常迅速。現(xiàn)今國內(nèi)已經(jīng)有幾十家廠家和研究所從事這方面的研究和產(chǎn)品制造。例如,北京城際在線網(wǎng)絡(luò)科技有限公司在京推出的“城際通”多功能便攜式衛(wèi)星導(dǎo)航汽車電腦,被業(yè)界認(rèn)為是我國第一代自導(dǎo)航產(chǎn)品,它集成了衛(wèi)星定位技術(shù)、地理信息管理和互聯(lián)網(wǎng)技術(shù),以電子地圖為基礎(chǔ),通過接收衛(wèi)

32、星信號,能夠完成智能路徑規(guī)劃、全程語音提示、電子地圖測覽、衛(wèi)星定位導(dǎo)航等功能聞;北京華隆世紀(jì)的導(dǎo)航之星,能夠?qū)崿F(xiàn)地圖顯示、智能導(dǎo)航、地圖信息查詢等功能【】;。到年估計(jì)北京會有%甚至更多的車輛安裝該裝置。到時候,價格也會越于合理,就連普通的出租車司機(jī)都能接受。存在的問題從技術(shù)水平和產(chǎn)品的質(zhì)量和成熟程度來說,我們還處在往上發(fā)展時期,僅僅為一般水平。主要存在闖題有:相當(dāng)長一段時缺少大公司大企業(yè)介入電子地圖精確度差、更新周期過長電子地圖繪制得越精確,定位也就越準(zhǔn)確,用戶使用起來就越方便。而在中國,電子城市地圖資源一直還沒有一個完全開放的標(biāo)準(zhǔn)平臺。國內(nèi)的汽車導(dǎo)航市場發(fā)展得不快,與我國的電子地圖市場沒有放

33、開是密不可分的。規(guī)范化和規(guī)?；瘑栴}長期不能解決,缺乏統(tǒng)一的標(biāo)準(zhǔn)由于這是一個新興行業(yè),目前行業(yè)還缺乏統(tǒng)一的標(biāo)準(zhǔn)。在國外越來越普及的綜合管理系統(tǒng),在我國還處于各自為營的散亂狀態(tài),沒有統(tǒng)一的平臺支持,行業(yè)缺乏統(tǒng)一的標(biāo)準(zhǔn)。不同公司的產(chǎn)品及運(yùn)營系統(tǒng)不能通用、兼容,產(chǎn)品的可靠性、一致性及質(zhì)量標(biāo)準(zhǔn)方面存在著問題。這些問題都在無形中妨礙了該產(chǎn)品的推廣應(yīng)用。價格因素在很大程度上制約著產(chǎn)業(yè)發(fā)展一種產(chǎn)品能否被市場所接受,關(guān)鍵還是在于是否適應(yīng)了市場需求,再有就是產(chǎn)品價格、質(zhì)量、服務(wù)等方面也是消費(fèi)者所考慮的因素。消費(fèi)者究竟需要什么樣的車載導(dǎo)航系統(tǒng),恐怕是眾多廠家所要率先解決的問題。車輛導(dǎo)航系統(tǒng)的市場潛力在國外,車輛導(dǎo)航

34、系統(tǒng)正在從長途卡車公司業(yè)已確立的地位向運(yùn)輸市場的基于的路徑規(guī)劃系統(tǒng)研究新部門過渡。這些部門如商業(yè)車輛、旅游車、公交車、私人豪華轎車等。以美國為例,據(jù)估計(jì)其裝置數(shù)目將從年的萬套增加到年的萬套,年收入可達(dá)億美元。目前,該系統(tǒng)在長途運(yùn)輸業(yè)中的深入程度已超過%。進(jìn)入世紀(jì)后,由于流動性成為職業(yè)生涯中正在增長的共同特點(diǎn),人們對”虛擬辦公室”的興趣日益遞增。在這一變化的工作環(huán)境下,產(chǎn)業(yè)預(yù)計(jì)將對車載用戶產(chǎn)品提出更為迫切的要求。國際觀察機(jī)構(gòu)普遍認(rèn)為,世紀(jì)的中國將成為全球最大的信息技術(shù)市場,中國的手機(jī)用戶和互聯(lián)網(wǎng)用戶將成為世界上最大的用戶群。隨著寬帶網(wǎng)和移動網(wǎng)的普及應(yīng)用,/的綜合應(yīng)用必將迅速推廣,屬于核心技術(shù)之一

35、的車輛導(dǎo)航系統(tǒng)將有更多機(jī)會開辟新的更為廣闊的國內(nèi)市場【】。.同類問題的研究總結(jié)地理信息系統(tǒng)自從問世到現(xiàn)在已經(jīng)經(jīng)歷了多年的蓬勃發(fā)展,如何合理地組織軟件的結(jié)構(gòu),一直是軟件技術(shù)專家們研究的問題。隨著當(dāng)今軟件業(yè)的組件式思想的興起和思想的不斷進(jìn)步,適應(yīng)性強(qiáng),應(yīng)用面廣,使用簡單的逐漸成為人們的目標(biāo),組件式適應(yīng)這種要求,成為當(dāng)今的一個主要發(fā)展方向。另外,由于要分析和處理海量的地理空間數(shù)據(jù),一般而言,它是一個復(fù)雜的巨系統(tǒng)。在特別是應(yīng)用軟件的開發(fā)過程中,為避免大量重復(fù)勞動,提高軟件生產(chǎn)率和質(zhì)量,采用基于構(gòu)件的軟件開發(fā)技術(shù)就很有必要。因此,和其他軟件一樣,軟件也逐漸過渡到了組件式軟件技術(shù),由過去廠家提供全部系統(tǒng)或

36、者具有二次開發(fā)功能的軟件,發(fā)展到了提供組件,由用戶自己開發(fā)應(yīng)用系統(tǒng)。它基于標(biāo)準(zhǔn)的組件式平臺,各組件之間不僅可能自由、靈活地重組,而且具有可視化的界面的和方便的標(biāo)準(zhǔn)接口。無疑,組件式技術(shù)將給整個技術(shù)體系和應(yīng)用模式帶來巨大影響。目前。國外已有一些成型的嵌入式路徑規(guī)劃系統(tǒng),不過均只能給出兩點(diǎn)間的最短路【】;國內(nèi)目前公交問路系統(tǒng)比較多見,它能以可視化界面為乘客提供公交站點(diǎn)、線路的設(shè)置和運(yùn)營信息。輸入起訖點(diǎn),系統(tǒng)將自動為乘客提供最佳出行方案【】。而現(xiàn)有的車輛導(dǎo)向系統(tǒng),例如靈圖,是采用靜態(tài)算法求解兩點(diǎn)間的最短路,不能根據(jù)路況的變化時時求解,也不能實(shí)現(xiàn)目的地為多點(diǎn)的路徑求解【劃。并且目前這些產(chǎn)品大多存在導(dǎo)航

37、功能單一、體積大、可靠性差、價格高等問題。主要困難在于現(xiàn)在普遍使用的尋路算法均為經(jīng)典的最短路算法,只能給出兩點(diǎn)間的最短路,不能實(shí)現(xiàn)多目的地的最短路求解,無法滿足用戶的需要?；诘穆窂揭?guī)劃系統(tǒng)研究.本文的研究思路本文針對路徑規(guī)劃系統(tǒng)的實(shí)際應(yīng)用情況,以開發(fā)能夠?qū)崿F(xiàn)考慮交通規(guī)則和路況信息的目的地點(diǎn)為多點(diǎn)的動態(tài)路徑規(guī)劃系統(tǒng)為且標(biāo),引入了嵌入式開發(fā)平臺,對其中的關(guān)鍵技術(shù)做了一定的研究,并對算法進(jìn)行了一定的改開發(fā)進(jìn),在此基礎(chǔ)之上以 為操作平臺,運(yùn)用了基于嵌入式的多目的地路徑規(guī)劃系統(tǒng)。根據(jù)以上研究內(nèi)容,本文按照系統(tǒng)分析,系統(tǒng)設(shè)計(jì)和系統(tǒng)實(shí)現(xiàn)將研究思路做了如下安排:第二章,首先確定系統(tǒng)屬性為動態(tài)路徑規(guī)劃系統(tǒng),需

38、要考慮路況變化。然后根據(jù)系統(tǒng)的應(yīng)用情況對系統(tǒng)做出功能分析,確定需要實(shí)現(xiàn)那些功能。最后在此基礎(chǔ)之上對數(shù)字地圖和最優(yōu)路徑進(jìn)行了分析,使其適應(yīng)系統(tǒng)的功能需求。第三章,在第二章功能分析的基礎(chǔ)之上,首先對系統(tǒng)進(jìn)行了總體設(shè)計(jì),根據(jù)實(shí)現(xiàn)的功能把系統(tǒng)分成地圖瀏覽模塊,路徑規(guī)劃模塊和人機(jī)接口模塊。然后設(shè)計(jì)包括數(shù)字地圖、嵌入式地理信息系統(tǒng)開發(fā)平臺和屬性數(shù)據(jù)庫的基礎(chǔ),最后根據(jù)需求設(shè)計(jì)了使用的算法。第四章,在系統(tǒng)設(shè)計(jì)的基礎(chǔ)上,采用軟件工程的設(shè)計(jì)思想,運(yùn)用.作為開發(fā)環(huán)境,以作為系統(tǒng)基礎(chǔ)平臺,用為操作系統(tǒng),實(shí)現(xiàn)了基于的路徑規(guī)劃系統(tǒng)?；诘穆窂届n劃系統(tǒng)研究基于的路徑規(guī)劃系統(tǒng)分析目前路徑規(guī)劃系統(tǒng)的研究中多采用靜態(tài)類計(jì)算,計(jì)算

39、結(jié)果與真實(shí)最短路存在較大差異。實(shí)時動態(tài)最優(yōu)路徑是真實(shí)的最短路徑,并且,若想提高信息的準(zhǔn)確度,擁擠程度最低、綜合最優(yōu)路徑的計(jì)算都應(yīng)以動態(tài)行程時間為依據(jù),可見,路徑規(guī)劃系統(tǒng)應(yīng)以動態(tài)行程時間作為計(jì)算最優(yōu)路徑的基礎(chǔ),并提供實(shí)時動態(tài)最優(yōu)路徑作為必備服務(wù)。因此本系統(tǒng)以動態(tài)的路況數(shù)據(jù)庫為基礎(chǔ),屬于動態(tài)路徑規(guī)劃系統(tǒng)。另外,針對現(xiàn)今交通規(guī)則日益復(fù)雜的狀況,本系統(tǒng)特別強(qiáng)調(diào)了對交叉口轉(zhuǎn)向限制和單行線等情況的處理,只有充分考慮交通規(guī)則的路徑規(guī)劃才是有意義的。.系統(tǒng)功能分析路徑規(guī)劃系統(tǒng)提供充足的地理信息和快速的地圖瀏覽,并享有高精度地圖的支持,因此系統(tǒng)對于外出旅行的私用車輛的益處是顯而易見的,通過這套系統(tǒng),用戶可以在完

40、全陌生的環(huán)境下通過規(guī)劃系統(tǒng),找到正確的行駛線路,同時,通過該系統(tǒng)自帶的電子地圖,用戶也可以查詢到自已需要的信息。但是其作用遠(yuǎn)不止于此。如果所有的車輛都能根據(jù)實(shí)時的交通路況動態(tài)調(diào)整自己的行車路線,隨時搜索最佳路線,那么整個交通系統(tǒng)的通行能力將會大大改善,道路的利用率也會大大提高,可以減少車輛的堵塞,節(jié)約能源。毫無疑問,路徑規(guī)劃系統(tǒng)可以為整個交通系統(tǒng)做出巨大的貢獻(xiàn)?；诘穆窂揭?guī)劃系統(tǒng)研究圈.路徑規(guī)劃系統(tǒng)功能示意圖.地圖瀏覽功能該模塊通過調(diào)用控件的圖層縮放功能函數(shù)來實(shí)現(xiàn)的,其中通過縮放按鍵或選擇縮放熱區(qū)對地圖進(jìn)行縮放、小地圖的快速導(dǎo)引的功能。.路徑規(guī)劃功能這一模塊是本系統(tǒng)的核心部分,其基本功能是:用

41、戶先選擇最佳路徑類型,比如最短路、最省時路等;然后在地圖上點(diǎn)選起始點(diǎn)和幾個目標(biāo)點(diǎn);最后采用實(shí)時計(jì)算的方式在較短的響應(yīng)時間內(nèi)求出最佳路徑。路徑的質(zhì)量取決于許多因素,如距離、行駛時間、行駛速度轉(zhuǎn)彎和交通信號燈數(shù)量以及是否提供動態(tài)交通信息等。本文將所有這些因素綜合考慮,統(tǒng)一用行駛費(fèi)用參數(shù)來說明。由于有的用戶喜歡最短距離,而有人偏愛最短時間,還有的希望得到最經(jīng)濟(jì)路徑,因此本系統(tǒng)這三種路徑都能計(jì)算出來,用戶可以根據(jù)自己的需求進(jìn)行選擇。.屬性查詢功能對于路徑規(guī)劃系統(tǒng)而言屬性查詢功能并不是主要功能,但是考慮到它對于用戶出行是十分必要的,因此本系統(tǒng)加入了屬性查詢功能。由于嵌入式設(shè)備一般不支持鍵盤輸入,本系統(tǒng)采

42、用點(diǎn)選的方式來確定查詢對象。當(dāng)用戶選擇了某點(diǎn)或某條道路時,系統(tǒng)會給出該對象的相關(guān)屬性數(shù)據(jù),如道路名稱,長度等。.人機(jī)接口人機(jī)接口是負(fù)責(zé)向用戶想用戶提供與計(jì)算機(jī)交互手段的模塊。關(guān)于這個?；诘穆窂揭?guī)劃系統(tǒng)研究塊的研究常見于人機(jī)工程學(xué)或有關(guān)人的因素工程的相關(guān)文獻(xiàn)中。人機(jī)工程學(xué)的研究者們主要研究有關(guān)人的行為、能力、極限和其他特性并將之應(yīng)用于工具、機(jī)器、系統(tǒng)、任務(wù)、工作和環(huán)境設(shè)計(jì)中,目標(biāo)是提高生產(chǎn)力和安全性,保證人類使用的舒適性和有效性。為了建立一個成功的人機(jī)界面,這必須按照一個特定的過程來考慮問題。這包括明確需求,確定需支持的功能,界面類型規(guī)范,控制和顯示形式的選擇和最后設(shè)計(jì)和實(shí)施這個界面。就本系統(tǒng)

43、來說,一方面,我佛要通過人機(jī)接口獲取路徑的起始點(diǎn)、目的地點(diǎn)、中間點(diǎn)等數(shù)據(jù),并獲得用戶的需求,如用戶想得到最短路徑還是最省時路;另一方面,要依據(jù)計(jì)算得來的結(jié)果數(shù)據(jù)建立最優(yōu)路徑對象,顯示在地圖中。.系統(tǒng)用例圖用例 用來描述一個系統(tǒng)外在可見的需求情況,用于系統(tǒng)的需求分析階段【。描述的內(nèi)容是用戶所理解的系統(tǒng)功能,表示系統(tǒng)用戶與系統(tǒng)交互時的所有操作,即對系統(tǒng)的外部特性進(jìn)行建模,展示系統(tǒng)與系統(tǒng)用戶的交互。用例圖的主要元素是用例和角色。用例是用戶與計(jì)算機(jī)之間的一次典型交互作用,表示從用戶角度對系統(tǒng)的要求,它可以捕獲某些用戶的可見需求。角色是指用戶在系統(tǒng)中所扮演的角色,是系統(tǒng)的主體。在中,用橢圓來表示用例。用

44、一個小人表示角色。下面用圖.來描述路徑規(guī)劃系統(tǒng)的總體功能。犬用戶屬性查詢圖.路徑規(guī)劃系統(tǒng)用例圖.基于的路徑規(guī)劃系統(tǒng)研究.數(shù)字地圖分析.數(shù)字地圖的數(shù)據(jù)分析路徑規(guī)劃系統(tǒng)中需要的數(shù)據(jù)主要是電子地圖的空間數(shù)據(jù),和一些與路徑規(guī)劃需求相關(guān)的屬性數(shù)據(jù)組成,包括道路網(wǎng)幾何形狀、道路等級、道路特征、轉(zhuǎn)彎和交通規(guī)則限制等。這些數(shù)據(jù)主要分為兩大類:道路網(wǎng)數(shù)據(jù)和非道路網(wǎng)數(shù)據(jù)。道路網(wǎng)數(shù)據(jù)包括基本的道路網(wǎng)的地理數(shù)據(jù)如道路的地理位置信息以及道路上與車輛行駛相關(guān)的數(shù)據(jù)如道路的流量等級信息和交通規(guī)則信息。道路網(wǎng)數(shù)據(jù)的主要特征是需要有較強(qiáng)的拓?fù)潢P(guān)系。非道路網(wǎng)數(shù)據(jù)主要包括能反映某地區(qū)地形地貌的基本的地物信息如河流、湖泊、邊界、鐵路

45、等以及反映出行信息的地理數(shù)據(jù)如居民區(qū)、學(xué)校、政府機(jī)關(guān)、醫(yī)院等。其中道路網(wǎng)數(shù)據(jù)采用圖的數(shù)據(jù)結(jié)構(gòu)進(jìn)行表示;非道路網(wǎng)數(shù)據(jù)用關(guān)系表來表示并建立相應(yīng)的索引方便查詢。.系統(tǒng)對數(shù)字地圖需求分析對路徑規(guī)劃系統(tǒng)的使用者來說,最關(guān)心的地圖數(shù)據(jù)是道路名和地名,這是數(shù)字道路圖的基本數(shù)據(jù)。許多使用者還關(guān)心其他一些地理信息,如停車場、酒店、醫(yī)院和加油站等,在數(shù)字道路圖數(shù)據(jù)庫中加入這些數(shù)據(jù),系統(tǒng)的性能就被加強(qiáng)了。對路徑規(guī)劃來說,所需要的數(shù)據(jù)是道路網(wǎng)的拓?fù)浣Y(jié)構(gòu),同時還要考慮交通限制信息,如單行線、轉(zhuǎn)彎限制等。將道路按路面寬度,通行能力等因素進(jìn)行等級劃分也可使路徑規(guī)劃功能更有效。另外對地圖顯示來說,僅有以上信息顯示還不夠美觀,

46、因此需要增加一定數(shù)量的其他信息,如森林、植被、海洋、河流、鐵路等。.數(shù)字地圖的內(nèi)容分析總的來說用于路徑規(guī)劃的電子地圖應(yīng)具有一定精度和足夠信息并且數(shù)據(jù)完整無縫包括幾何完整性和拓?fù)湟恢滦?。它?yīng)該包含以下信息:靜態(tài)信息:節(jié)點(diǎn)的幾何位置;每一個節(jié)點(diǎn)都應(yīng)有其相鄰節(jié)點(diǎn)的信息;每一個節(jié)點(diǎn)都有和相鄰節(jié)點(diǎn)之間的路段信息,包括道路級別、道路寬度、交通流量等參數(shù);行駛限制信息,如路段的行駛方向限制,節(jié)點(diǎn)的拐彎限制等;其他信息,如道路和河流或鐵路的交點(diǎn)信息。動態(tài)信息:道路實(shí)況,包括道路當(dāng)前流量、擁擠情況;交通阻塞或交通事故路段或節(jié)點(diǎn)信息;天氣情況主要用于智能導(dǎo)航等其他重要信息。.最優(yōu)路徑分析影響駕駛員選擇路徑的因素很

47、多,可以從路徑特性與駕駛員特性兩個方面進(jìn)行分析,前者包括行程時間、行駛距離、擁擠程度、路線所經(jīng)過交叉口的數(shù)量基于的路徑規(guī)劃系統(tǒng)研究及控制方式等,后者包括駕駛員的駕駛經(jīng)驗(yàn)、個人偏好、出行目的等。研究表明,駕駛員選擇路線的準(zhǔn)則呈現(xiàn)多樣性,每個駕駛員都有自己的偏好,但是考慮到算法的復(fù)雜程度和數(shù)據(jù)可獲得性,系統(tǒng)能提供的可選準(zhǔn)則是有限的。對用戶信息需求多樣性與系統(tǒng)提供信息能力有限性作折衷處理,可以提供以行程時間、行駛距離和綜合費(fèi)用為準(zhǔn)則的最優(yōu)路徑,供具有不同偏好的出行者選擇或參考。其中行程時間和行程距離是多數(shù)駕駛員選擇或關(guān)注的準(zhǔn)則,對此作重點(diǎn)剖析。由于路段上交通狀態(tài)是動態(tài)變化的,路段的交通流量信息應(yīng)該是

48、實(shí)時變化的。但是受交通參數(shù)檢測技術(shù)和預(yù)測分析技術(shù)的限制,難以得到準(zhǔn)確的、可用的流量信息隨時間變化的關(guān)系式,為此,可以對時間作離散化處理,將系統(tǒng)工作時間劃分為若干時段,認(rèn)為單個時段內(nèi)交通狀態(tài)穩(wěn)定、路段流量等級固定,但不同時段的流量等級可能不相同。用這種方法來處理動態(tài)的交通狀況可以獲得較好的動態(tài)最優(yōu)路徑。.操作系統(tǒng)分析近年來,嵌入式計(jì)算機(jī)在關(guān)于路徑規(guī)劃的各種系統(tǒng)中得到了普遍的應(yīng)用。在這些應(yīng)用如監(jiān)控系統(tǒng)、車輛導(dǎo)航系統(tǒng)等中的移動終端手機(jī)、等基本上就是一個嵌入式計(jì)算機(jī)。在這種作為移動終端的嵌入式計(jì)算機(jī)平臺上開發(fā)軟件,主要用兩種方式:一種是自己開發(fā)專用操作系統(tǒng),并在其基礎(chǔ)上上開發(fā)軟件;另一種是使用通用的操

49、作系統(tǒng)。前一種開發(fā)方式是針對某系統(tǒng)需求,開發(fā)專屬于這個軟件的操作系統(tǒng),具有專用性,因此數(shù)據(jù)的保密性較好,但通用性不好,僅可用于有限的嵌入式設(shè)備上,而且成本很高。由于目前市場上已經(jīng)有比較穩(wěn)定可靠的、通用的嵌入式操作系統(tǒng),因而我采用第二種開發(fā)方式開發(fā)路徑規(guī)劃系統(tǒng),這樣開發(fā)的軟件可以適用的硬件設(shè)備較多,便于推廣應(yīng)用,同時也縮短了軟件的、嵌入式叫開發(fā)周期。目前通用的嵌入式操作系統(tǒng)有很多,如等。其中, 是一個多任務(wù)實(shí)時操作系統(tǒng),具有出色的用戶界面和良好的通信功能,是微軟專門為信息設(shè)備、移動應(yīng)用、消費(fèi)類電子產(chǎn)品等嵌入式領(lǐng)域而全新設(shè)計(jì)的操作系統(tǒng)。本文針對嵌入式計(jì)算機(jī)的硬件平臺,在操作系統(tǒng)下設(shè)計(jì)實(shí)現(xiàn)了這套路徑

50、規(guī)劃系統(tǒng)?；?的嵌入式軟件是在 操作系統(tǒng)平臺上面向特殊應(yīng)用服務(wù)的軟件系統(tǒng)。它具有一般軟件的共性,同時具有不同于桌面機(jī)軟件的一些特點(diǎn):小型化,軟件占用的空間小;基于的路徑規(guī)劃系統(tǒng)研究專業(yè)化,嵌入式軟件往往服務(wù)于具體的應(yīng)用領(lǐng)域,不求大全:實(shí)時性強(qiáng);配置要求低,可運(yùn)行于低配置的環(huán)境中?；诘穆窂揭?guī)劃系統(tǒng)設(shè)計(jì).系統(tǒng)總體設(shè)計(jì).系統(tǒng)總體設(shè)計(jì)目標(biāo)針對用戶工作環(huán)境的需求,系統(tǒng)應(yīng)具有良好的人機(jī)交互性、系統(tǒng)的可擴(kuò)縮性、地域的可變更性等特點(diǎn)。系統(tǒng)的設(shè)計(jì)方案以信息存儲空間小、實(shí)時性好、通用性強(qiáng)為主要目標(biāo),以組件、開放式數(shù)據(jù)庫訪問等技術(shù)手段,在臺式機(jī)上開發(fā),實(shí)現(xiàn)系統(tǒng)的功能后,移植到掌上型個人數(shù)字助手上,以推廣系統(tǒng)的實(shí)

51、用領(lǐng)域。具體目標(biāo)如下滿足目的地為多點(diǎn)的求解要求,并具有一定的時效性;能夠根據(jù)用戶需求提供距離最短路,最經(jīng)濟(jì)路和最省時路;充分考慮路況變化及交通規(guī)則;將結(jié)果直觀的現(xiàn)實(shí)給用戶;.系統(tǒng)總體構(gòu)成路人機(jī)交互界面刪徑人一規(guī)不機(jī)數(shù)字地圖數(shù)據(jù)庫劃模結(jié)果嗲界腳模塊面塊自建路況數(shù)據(jù)庫圈吟圈.路徑規(guī)劃系統(tǒng)構(gòu)成筒圖. 枉 咖口根據(jù)上述設(shè)計(jì)目標(biāo),本系統(tǒng)主要由以下幾部分構(gòu)成:人機(jī)交互界面:獲得用戶需求并顯示結(jié)果;數(shù)字地圖數(shù)據(jù)庫:獲得地圖道路數(shù)據(jù);路況數(shù)據(jù)庫:獲得交通信息。從技術(shù)方面,路徑規(guī)劃系統(tǒng)集成嵌入式地理信息系統(tǒng)、數(shù)據(jù)庫技術(shù)為一體,、為開發(fā)平臺,根據(jù)用戶需求實(shí)以電子地圖為基礎(chǔ)數(shù)據(jù)庫,以時規(guī)劃出一條最佳路徑。在可視化開發(fā)環(huán)境中,需要在設(shè)計(jì)階段將基于的路徑規(guī)劃系統(tǒng)研究控件插入到窗體中,并對其進(jìn)行編程?設(shè)置屬性、調(diào)用方法或響應(yīng)事件實(shí)現(xiàn)數(shù)據(jù)地圖化、地圖數(shù)據(jù)可視化及地理分析、最優(yōu)路徑分析等豐富的地理信息系統(tǒng)功能。地理信息系統(tǒng)是收集、管理、操作、分析和顯示空間數(shù)據(jù)的計(jì)算機(jī)軟硬件系統(tǒng),集成了計(jì)算機(jī)數(shù)據(jù)庫技術(shù)和計(jì)算機(jī)圖形輔助設(shè)計(jì)軟件。目前用于應(yīng)用軟件開發(fā)的模式有很多,其中組件式軟件開發(fā)是目前較為流行、高效