《Dijkstra算法在GPS導航中的應(yīng)用研究》14000字【論文】

ii第1章緒論1.1研究背景與意義隨著世界經(jīng)濟的發(fā)展，車輛價格不斷降低，汽車保有量節(jié)節(jié)高升，我國的汽車占有率近幾年也呈大幅增長的趨勢.我們的日常生活中乘坐汽車等交通工具，已是我們必不可少的一部分，與此同時交通、環(huán)境問題也隨之而來，為此，國家增加基建成本，不斷地拓寬道路，修建高架橋等一系列有利于人民出行便利的方式，來解決交通問題.但是盡管在如此高成本的投入下，仍沒有明顯緩解目前擁堵的情況.因此人們逐漸認識到，單單依靠建設(shè)基礎(chǔ)設(shè)施不可能在道路擴增速度遠遠跟不上車輛增長速度的情況下從根本上解決交通擁堵的問題，且各地的交通阻塞都有明顯的地域性，即具體某一路段在某一時間經(jīng)常擁堵.而大部分車主都不熟悉道路狀況，且新增的相鄰道路提供給車主的多樣的路徑選擇由于缺少有效的導航和路線引導并沒有發(fā)揮他們本身的最大價值，實際出行中往往是那些無效的出行路線提高了造成交通擁堵和交通事故的可能性.那么充分利用現(xiàn)有的道路基礎(chǔ)設(shè)施，在計算機技術(shù)和人工智能等高科技的輔助下高效利用現(xiàn)有的公路網(wǎng)絡(luò)就顯得尤為重要，所以要提高交通路網(wǎng)的運行能力，利用現(xiàn)代化的技術(shù)手段合理調(diào)度公共資源，優(yōu)化駕駛員的行車路線，合理地疏通汽車的流量，有利于解決道路的擁堵問題，從而智能交通系統(tǒng)就產(chǎn)生了，其中很重要的一部分就是車載導航系統(tǒng).可以這么說，車載導航系統(tǒng)的產(chǎn)生，能為駕駛員規(guī)劃從初始位置到目的地終點的合理路徑，從而解決因不熟悉交通狀況和道路選擇而浪費出行時間或迷路的問題.車載導航系統(tǒng)的發(fā)展離不開GPS衛(wèi)星導航系統(tǒng)，日常生活中人們出行求得最快最短路徑的最常用的方式就是利用GPS導航系統(tǒng)，而且它也不只是在出行方面有作用，還在交通、旅游、規(guī)劃、設(shè)計等方面有廣泛的應(yīng)用，同時基于智能手機的移動4G網(wǎng)絡(luò)與傳統(tǒng)GPS導航系統(tǒng)的結(jié)合也成為了一個熱門研究領(lǐng)域.而最短路徑問題和規(guī)劃方法是GPS導航中最重要和最核心的關(guān)鍵性問題，該問題是實現(xiàn)路徑規(guī)劃功能的前提條件.那次是就要求按照地圖上的拓撲信息，篩選出已經(jīng)確定目的地和出發(fā)地的駕駛?cè)?，按照一定的方法或策略進行進一步準確地把握出最佳路徑，可以提供給駕駛?cè)耍@種情況在日常生活中很常見并且最終的路徑結(jié)果顯示在智能設(shè)備屏幕的電子地圖上和支持智能語音輸出.另外，最短路徑規(guī)劃算法是圖論中最為廣泛的算法，它為系統(tǒng)優(yōu)化，路徑規(guī)劃和資源分配等問題都提供了理論基礎(chǔ).無論是用于車載還是移動智能手機的GPS導航系統(tǒng)市場需求都十分巨大，所以用于GPS導航的最短路徑規(guī)劃方法具有十分重要的現(xiàn)實意義.1.2車載導航系統(tǒng)國內(nèi)外技術(shù)發(fā)展現(xiàn)狀1.2.1國外的技術(shù)發(fā)展現(xiàn)狀我們都知道，美國、日本和歐洲是目前世界上導航發(fā)展最發(fā)達的地區(qū)，他們的技術(shù)表現(xiàn)了當今世界最主流且發(fā)達的導航技術(shù).例如美國的人口密度較低，人們習慣于駕車出行，所以他們的導航網(wǎng)絡(luò)比較發(fā)達，同時他們的發(fā)達城市比較多，所以道路建設(shè)的是非常復雜的，這些因素都促進了他們的導航系統(tǒng)快速發(fā)展，一直處于世界領(lǐng)先水平，上世紀八零年代美國的市場上就出現(xiàn)了彩色的顯示設(shè)備，利用光盤來儲存導航保留留下來的數(shù)據(jù)，而且他們的導航系統(tǒng)還加入了畫面、聲音等新的技術(shù)，不算的豐富了他們研發(fā)的導航產(chǎn)品，從而加快了他們的發(fā)展.如今美國的許多汽車上都有車載導航設(shè)備，這已經(jīng)成為了他們國家產(chǎn)車的標配，絕大多數(shù)的生產(chǎn)汽車的工廠都會給汽車提前安裝GPS衛(wèi)星導航設(shè)備，每年他們的銷量只增不減，可達上百萬套，隨著這些的不斷進展，也產(chǎn)生了一系列的名牌導航設(shè)備，例如我們已經(jīng)熟知的TomTom,Garmin,Navman,新科，任我游等等.美國正在使用一種新的方式來提高車載導航技術(shù)的定位精確度，那就是D-GPS，他們通過使用該方法，對導航頻道進行誤差的校正，大大提高車輛定位的精準度，其精確度可以達到8nm，這可以說是非常精準了.美國接著利用一些專業(yè)的導航地圖，在使用的過程中會更加地提高精確度，這樣就可以廣泛的應(yīng)用于國防軍事交通等領(lǐng)域，意大利、英國等歐洲國家也追隨著美國的節(jié)奏，相繼開發(fā)出自己專屬的導航設(shè)備系統(tǒng)并廣泛地在各汽車上得到使用，例如寶馬，奔馳，西門子等大企業(yè).在導航領(lǐng)域，提供最佳駕駛路線和各種法規(guī)細節(jié)的能力已成為汽車市場建設(shè)的熱點.各種路線規(guī)劃使駕駛員可以選擇不同的路線到達目的地，例如最短和最短的路線，選擇高速，高速道路等，以便駕駛員可以選擇適合他們的路線.即使您在錯誤的地方駕駛，導航設(shè)備也可以快速響應(yīng)并重新安排路線，無論它在哪里.大自然，無論是普通的還是罕見的，都可以安全，迅速地到達終點.現(xiàn)在，成熟的漫游系統(tǒng)使用單片機設(shè)備，WINCE操作系統(tǒng)，并且部分軟件通常存儲在ROM中.和輸出字段以及LCD屏幕和建筑設(shè)備都適用于惡劣的駕駛環(huán)境，并且可以在高溫，低溫和快速振動下安全運行.1.2.2國內(nèi)技術(shù)發(fā)展現(xiàn)狀在1990年代初期，我國開始了對衛(wèi)星導航系統(tǒng)的基礎(chǔ)研究，包括交通分析，交通信息收集，駕駛測試系統(tǒng)，車輛識別和識別等.在1990年代后期，我國開始設(shè)計和建設(shè)道路交通管制和指揮系統(tǒng)，中間進行了道路標志系統(tǒng)和城市交通管制監(jiān)管技術(shù)的研究.但是，沒有設(shè)計成熟有效的汽車成熟產(chǎn)品.近年來，我國已經(jīng)有一些公司引進了高科技旅游技術(shù)，并將其用作發(fā)展的基礎(chǔ)，從而推出了多種成熟的產(chǎn)品，從而促進了我國市場的發(fā)展.目前，由于產(chǎn)品未婚且其結(jié)構(gòu)的準確性很差.問題，因此仍然有許多問題需要改進和解決.在北京奧運會期間確定的十項重大科技項目中，一項是北京汽車的智能管理和實施.實際上，2004年初，上海市質(zhì)量監(jiān)督局就提出了為上海世博會建設(shè)智能交通系統(tǒng)的建議，使上海能夠與長三角的其他城市快速連接，從而提供更高效，更快捷的交通系統(tǒng)，從而展示這座城市的美麗.今天，二十一世紀的中國將成為世界上最大的電信技術(shù)市場，而我國的移動和互聯(lián)網(wǎng)使用量將成為世界上最大的市場.隨著Internet寬帶和Internet的發(fā)展和擴展，以及對GPS和GIS的不斷研究，以及無線通信技術(shù)的迅速擴展和增強，自動駕駛汽車設(shè)備有很多發(fā)展機會，并且可以繼續(xù)開拓新市場，我國的智能汽車系統(tǒng)發(fā)展緩慢，具有強大的市場力量.隨著許多技術(shù)生產(chǎn)商的投資和政府的資助，這些類型的漫游設(shè)備將滲透到人們的生活中.每天為許多人的旅途帶來真正的幫助.盡管我國的研究和發(fā)展才剛剛開始，但它將不可避免地在未來產(chǎn)生深遠而深遠的影響.在過去的幾年中，汽車GPS導航系統(tǒng)的開發(fā)通常分為兩類，一類主要是歐洲和美國.自主導航得益于歐美強大的經(jīng)濟實力以及全球GPS定位系統(tǒng)的發(fā)展，使得這些移動通信設(shè)備的運行速度更快，并且經(jīng)常在私人和軍事市場上處于領(lǐng)先地位.另一個由中國，日本和韓國代表的跟蹤和監(jiān)視部門通常在導航，資產(chǎn)管理和安全保護領(lǐng)域中運作.不斷推出一系列北斗衛(wèi)星.這種情況將被扭轉(zhuǎn).近年來，這兩種類型的系統(tǒng)逐漸集成在一起，以更好地識別衛(wèi)星終端服務(wù)的功能并提供額外的服務(wù)空間.取決于導航工具的網(wǎng)絡(luò)，許多較舊的機器專用于專用網(wǎng)絡(luò)，并且機器的運營成本非常高，有時甚至不穩(wěn)定.在設(shè)備安裝可見性較差的某些地區(qū)，專業(yè)技術(shù)解決方案應(yīng)使主要的移動網(wǎng)絡(luò)運營商加強網(wǎng)絡(luò)通信基礎(chǔ)設(shè)施，使用GPRS和短消息服務(wù)來檢測漫游設(shè)備與監(jiān)視中心之間的通信，并促進并快速選擇.當前，許多家庭監(jiān)視平臺使用較短的消息傳遞，這可以快速降低通信成本并降低衛(wèi)星導航網(wǎng)絡(luò)的建設(shè)成本，從而加速了汽車技術(shù)的快速發(fā)展.1.3研究內(nèi)容本論文主要涉及以下幾個方向的工作：（1）介紹了國內(nèi)外車載導航系統(tǒng)的技術(shù)發(fā)展狀況.（2）分析了GPS在車輛定位導航系統(tǒng)中的應(yīng)用.（3）對比了三種最短路徑算法，并詳細介紹了Dijkstra算法及其在GPS導航中的應(yīng)用實現(xiàn).1.4本章小結(jié)本章首先說明并分析了當今世界下車載導航市場的發(fā)展情況，并且根據(jù)本課題的研究內(nèi)容提出了本課題的意義，最后給出了接下來的研究方向與細節(jié).第2章車載導航的相關(guān)技術(shù)2.1中國北斗衛(wèi)星導航系統(tǒng)中國自主研發(fā)了一種名為北斗的衛(wèi)星導航系統(tǒng)，這是北斗七星的意思.其目的就是為了加強地質(zhì)監(jiān)測、運輸和漁業(yè)生產(chǎn)等.根據(jù)更先進的導航系統(tǒng)，與GPS、GLONASS進行比較，該系統(tǒng)只能向用戶提供全天路線，包括天氣路線、短信通知、高精度定位和亞洲其他服務(wù)，定位精度小于15m，同步精度小于80ns.2012年北斗系統(tǒng)正式被公開，同時為亞洲地區(qū)提供導航服務(wù).在空間衛(wèi)星端有五顆衛(wèi)星在工作，地面監(jiān)控管理中心主要由地面主控中心、衛(wèi)星信號注入站和衛(wèi)星監(jiān)測站組成，地面應(yīng)用終端則以北斗衛(wèi)星接收芯片為核心的終端定位設(shè)備，并且此設(shè)備一般與GPS衛(wèi)星接收器兼容.北斗在定位精度上是不輸于GPS和格洛納斯.并且還在某些方面優(yōu)秀于GPS和格洛納斯.我們可以通過下圖2-1直觀感受到北斗衛(wèi)星的工作方式.圖2-1北斗導航的系統(tǒng)流程圖2.2全球定位系統(tǒng)(GPS)全球定位系統(tǒng)(GlobalPositioningSystem)簡稱GPS，是20世紀70年代由美國陸?？杖娐?lián)合研制的新一代空間衛(wèi)星導航定位系統(tǒng).GPS系統(tǒng)主要有三部分組成，三部分的名稱和功能如表2-1，三者的關(guān)系如圖2-1所示.表2-1衛(wèi)星導航圖名稱描述空間衛(wèi)星載體發(fā)射到空中的衛(wèi)星載體，主要負責不間斷的發(fā)生衛(wèi)星信號陸地監(jiān)控中心負責對空間衛(wèi)星進行控制和交互的地面管控中心終端信號接收機用戶終端用來接收衛(wèi)星信號并進行計算定位的設(shè)備圖2-1GPS系統(tǒng)組成關(guān)系圖該系統(tǒng)優(yōu)點有很多，例如使用戶可以全天使用，并且定位范圍廣泛，可以覆蓋全球各個角落，并且定位精確度較高，有良好的使用體驗，有了這些鋪墊后該系統(tǒng)后來就慢慢發(fā)展到其他領(lǐng)域.2000年以來，人們生活水平逐漸提升，工作疲憊的時候可以選擇的解壓放松方式也越來越多樣化，例如自駕出游，徒步旅游等等戶外方式，那么此時小巧的便攜式GPS導航設(shè)備就非常的實用了，為了旅途提供了便利，給行程安排的安全給予了保障，.GPS的銷售市場非常良好，據(jù)相關(guān)專家研究表明，就中國銷售的車載導航產(chǎn)品的產(chǎn)值就高達50億元.隨著科技的不斷發(fā)展，GPS的技術(shù)也越來越成熟，它的應(yīng)用也隨之越來越廣泛，例如海陸空等領(lǐng)域，也慢慢向公路運輸領(lǐng)域發(fā)展，同時在社會生活中的交通運輸?shù)犬a(chǎn)業(yè)中可以得到很好的應(yīng)用，可以有效地改善交通擁擠，從而便利了生活，并能在一定程度上保障車輛及人身安全.在系統(tǒng)開發(fā)上，各大公司也不斷進行開發(fā)完善，為用戶提供更好的使用體驗.2.2.1GPS車載導航相關(guān)研究GPS導航最優(yōu)算法誕生于二十世紀中后期，由西方發(fā)達國家的專家學者最早進行研究的.經(jīng)過長期的研究，西方學者提出了半確定性的路徑匹配算法.后來國外學者提出了點到點、點到曲線及曲線到曲線的GPS導航最優(yōu)算法，這幾類算法均屬于幾何層面的GPS導航最優(yōu)算法，此外還對這些算法進行了改進.自此，國內(nèi)外的學者們開始了大量的、深入的有關(guān)GPS導航最優(yōu)算法的學術(shù)研究.國外學者早期對GPS導航最優(yōu)算法進行了大量的研究，其中比較具有代表性的是WhiteC.E.等學者對GPS導航最優(yōu)算法中如何搜索匹配路徑、怎樣結(jié)合統(tǒng)計學推斷車輛最可能的行駛路徑等相關(guān)問題進行了大量的研究工作，并在研究曲線到曲線的GPS導航最優(yōu)算法的基礎(chǔ)上，考慮將車輛行駛的方向及道路網(wǎng)的拓撲結(jié)構(gòu)信息與這類幾何匹配算法結(jié)合起來，提出了一個有效的GPS導航最優(yōu)算法，并通過實驗來驗證該GPS導航最優(yōu)算法的有效性及性能[1].SinnKim提出了一種能確切找到匹配路段的GPS導航最優(yōu)算法，此算法是以神經(jīng)網(wǎng)絡(luò)作為理論基礎(chǔ)的.該算法的基本思想是將車輛的行駛方向和車輛與候選匹配道路的最短距離作為參考因素來選取最佳匹配道路，雖然這類算法能有效地提高匹配精度，但是它需要人為地選擇這兩個參考因素參數(shù)，導致算法具有一定的局限性[2].Greenfeld提出了一種基于權(quán)重的GPS導航最優(yōu)算法，該算法以電子地圖中道路網(wǎng)的拓撲信息為基礎(chǔ)，為多個匹配因子分配權(quán)重系數(shù)，并進行權(quán)重擬合計算，選取權(quán)重最大的候選匹配路段作為車輛的行駛路段[3].這類算法計算簡單，但在道路網(wǎng)比較復雜的情況下，可能會出現(xiàn)匹配錯誤的問題.由于傳統(tǒng)的車輛信息采集技術(shù)有一定的局限性，導致采集的車輛行駛相關(guān)信息存在一定的不確定性和隨機性，GPS導航最優(yōu)算法的研究處于瓶頸.隨后日本學者提出一種基于模式識別的GPS導航最優(yōu)算法，該算法不同于以往的匹配算法.由于國內(nèi)對車輛導航系統(tǒng)的研究晚于國外，但國內(nèi)學者對車輛導航系統(tǒng)中的GPS導航最優(yōu)算法的研究并沒有因為起步晚而落后于國外的學者們，研究成果也可謂是碩果累累.國內(nèi)學者對基于D-S證據(jù)理論的GPS導航最優(yōu)算法進行了大量的研究.比較具有代表性的是胡林、谷正氣、楊易等基于對現(xiàn)有基于證據(jù)理論算法的研究提出的基于權(quán)值D-S證據(jù)理論的車輛導航GPS導航最優(yōu)[4]，該算法是以矩陣為基礎(chǔ)，計算各個證據(jù)的可信度作為匹配的權(quán)值，利用融合算法處理證據(jù)中的沖突信息，再結(jié)合電子地圖中的道路網(wǎng)拓撲信息，并將車輛經(jīng)韓度、航向等信息作為依據(jù)進行車輛導航系統(tǒng)的GPS導航最優(yōu).隨后他們又提出了基于改進D-S證據(jù)理論的車輛導航GPS導航最優(yōu)算法，此算法中推出了組合推理思想和概率決策理論，便于路網(wǎng)比較復雜的道路進行有效快速的匹配[5].國內(nèi)對基于權(quán)重的GPS導航最優(yōu)算法的研究成果也不勝枚舉，北京交通大學電氣工程學院的李洋、張曉東、鮑遠律等提出了多權(quán)值概率實時GPS導航最優(yōu)算法[6],該算法是對Greenfeld提出的基于權(quán)重的匹配算法的改進，在不同的道路匹配階段采用不同的權(quán)值匹配模型，并以概率理論和內(nèi)積理論作為基礎(chǔ)，構(gòu)建不同的權(quán)重函數(shù)，并根據(jù)當前行駛道路來選取權(quán)值系數(shù)，最后計算總權(quán)重，選取權(quán)重最大的作為最優(yōu)匹配路段.國內(nèi)對基于拓撲結(jié)構(gòu)的GPS導航最優(yōu)算法也做了大量的研究，并提出了各種改進的基于拓撲結(jié)構(gòu)的匹配算法，比較具有代表性的是南京航空航天大學的楊新勇，黃勝國等提出的基于拓撲結(jié)構(gòu)/自適應(yīng)模糊決策的GPS導航最優(yōu)算法[7]，東南大學的張小國，王慶，萬德鈞等提出的基于路網(wǎng)拓撲特性及先驗知識的GPS導航最優(yōu)算法[8]，北京理工大學的丁露，陳家斌，張麗華等提出的拓撲結(jié)構(gòu)/模糊邏輯的車載導航系統(tǒng)GPS導航最優(yōu)算法等[9].這些算法都是將基于拓撲結(jié)構(gòu)的GPS導航最優(yōu)算法與其它GPS導航最優(yōu)算法進行有效的融合，以提高算法的匹配精度.2.3GPS在車輛定位導航系統(tǒng)中的應(yīng)用2.3.1GPS車輛定位導航系統(tǒng)的設(shè)計原理（1）車輛定位技術(shù)車輛定位技術(shù)是車輛定位導航系統(tǒng)的基礎(chǔ)，系統(tǒng)中所有的功能都要以精準的車輛定位作為前提條件.一個智能交通系統(tǒng)具備多大的實用價值，很大一方面是取決于車輛定位的實時性和準確性的.鑒于車輛定位技術(shù)的特殊性和重要性，它在車輛定位系統(tǒng)中是很重要的研究對象.隨著越來越多人使用GPS導航，GPS全球定位系統(tǒng)逐漸從專為美國軍方服務(wù)的航天工程轉(zhuǎn)變成了一個全球性的工具.因為GPS的實時性非常好，精度也足夠高，所以在車輛定位技術(shù)中，GPS是很適合的一個選擇，它可以滿足ITS中車輛導航必須的精度要求.基于GPS的定位技術(shù)研究正受到國內(nèi)外很多企業(yè)和部門的高度重視，這方面的技術(shù)成熟度也越來越高.（2）GPS車輛定位系統(tǒng)的硬件設(shè)計車載GPS的設(shè)計要求很高，需要同時滿足小體積、高精度、高可靠性、高抗擾度的要求，通常采用嵌入式硬件系統(tǒng)的架構(gòu)來進行設(shè)計.系統(tǒng)的硬件核心是嵌入式計算機，也可以說是嵌入式微機處理器.PC的體系結(jié)構(gòu)非常的成熟和普遍，與其兼容的硬件、軟件和外設(shè)都很豐富且成本低廉.所以應(yīng)用PC架構(gòu)來進行開發(fā)，可以降低開發(fā)難度和成本，縮短開發(fā)周期，也可以減少系統(tǒng)維護和技術(shù)支持的工作.（3）電子導航地圖電子導航地圖幫助用戶直觀而簡便地使用導航系統(tǒng).而且電子導航地圖是作為外設(shè)一般的存在，屬于導航系統(tǒng)的擴展，由相應(yīng)的軟件組成，不需要硬件方面的支持.電子導航地圖可以方便地實現(xiàn)很多功能，最大程度發(fā)揮出了車輛導航系統(tǒng)的實用性，具有方便、快捷、準確的優(yōu)點.（4）地圖匹配技術(shù)地圖匹配技術(shù)是GPS定位技術(shù)和電子導航地圖相結(jié)合的一種技術(shù).任何定位技術(shù)都具有一定的局限性，地圖匹配技術(shù)就是為了解決積累誤差而發(fā)展起來的.地圖匹配技術(shù)的核心是糾錯技術(shù)，它的目的是確定車輛在電子導航地圖上的位置.地圖匹配技術(shù)通過GPS測量到車輛的位置信息，再從電子導航地圖的數(shù)據(jù)庫中獲取相關(guān)信息進行匹配計算，得到偏差信息后進行實時修正，保證車輛在電子導航地圖上的位置是準確的.地圖匹配算法的效果將直接決定了車輛定位和導航的精度，也是決定導航產(chǎn)品性能的重要技術(shù).GPS定位、電子導航地圖和地圖匹配技術(shù)有機結(jié)合后的導航技術(shù)，是目前最為理想的導航方式.2.3.2GPS車輛定位導航系統(tǒng)的應(yīng)用實例（1）私家車的應(yīng)用GPS車輛定位導航系統(tǒng)在私家車上的應(yīng)用是最為普遍而且顯而易見的，車主可以通過導航系統(tǒng)，在一個完全陌生的環(huán)境下找到正確的行駛路線.而且現(xiàn)在軟件功能豐富，在電子地圖上，車主還能找到停車場、加油站、旅館等信息，在外出旅游度假時，系統(tǒng)所具備的娛樂功能還能給用戶提供所需的其他服務(wù).（2）運輸車輛的調(diào)度及管理工程運輸項目中，合理的調(diào)度安排是提升車隊效率的關(guān)鍵.配置了GPS車輛定位導航系統(tǒng)的車隊可以動態(tài)地調(diào)整車輛的行駛路線，按照最佳的路線完成運輸任務(wù)，從而節(jié)省了時間和能源.另一方面，交通中心也可以實時的跟蹤到車輛的當前位置，根據(jù)具體的運輸任務(wù)進行針對性安排，減少車輛的空運率，大大的提高了車輛運營效率.車載導航系統(tǒng)還可以將運輸路線進行存儲，便于后期管理部分利用數(shù)據(jù)進行線路優(yōu)化開發(fā).（3）救護車的應(yīng)用車載導航系統(tǒng)在醫(yī)療領(lǐng)域發(fā)揮的作用是具有重大意義的，眾所周知，搶救病人的關(guān)鍵因素就是要在最短的時間內(nèi)到達現(xiàn)場.以120救護車為例，病人家屬撥打救護專線需要花費時間，車輛趕赴現(xiàn)場也需要一定時間，醫(yī)生尋找現(xiàn)場也需要時間.如果救護車在出發(fā)前就精確知道病人位置，再利用車載導航系統(tǒng)規(guī)劃最快的路徑，就可以大大縮短路程時間，對病人和醫(yī)院來講都是十分必要的.（4）車輛及車主安全防護車載導航系統(tǒng)對車輛和車主也具有一定的安全防護作用，近些年車輛相關(guān)的犯罪活動日益增長，不管是車輛被盜或是出租車司機遇害等事件都在頻繁發(fā)生.裝備了車載導航系統(tǒng)的車輛，可以從某些方面對車輛和車主進行保護，比如在車輛被非法啟動時自動觸發(fā)聲光報警并將位置信息通過車載程序發(fā)給用戶和交通指揮中心，幫助車主快速找回被盜車輛.再比如出租車刑事案件當中，公安系統(tǒng)獲取車輛的行駛信息，可以提高破案效率，嚴厲打擊犯罪分子.2.4本章小結(jié)GPS定位技術(shù)和車載導航的結(jié)合，讓車輛系統(tǒng)變得更加的安全可靠.隨著硬件技術(shù)和軟件技術(shù)的不斷發(fā)展，車載導航系統(tǒng)還會不停的升級，向更高精度、更高實時性邁進.第3章最短路徑規(guī)劃算法最短路徑算法在圖論中應(yīng)用很廣泛，也是一個很經(jīng)典的問題.19世紀50年代數(shù)學家們就開始了對它的研究，至今大概有2000多篇相關(guān)文獻記載，最優(yōu)路徑算法移植都是很前沿的研究，最優(yōu)路徑不僅僅是“顧名思義”上的距離最短，還可以是時間最短等等，針對不同的對象可以滿足不同的需求，但無論是哪一種，其關(guān)鍵步驟就是選擇最優(yōu)路徑算法的計算方法，例如人們在選擇最佳路徑是會首先根據(jù)時效性，因此系統(tǒng)也會首先考慮從高速公路，高效快捷，從費用上考慮，會避開收費的路段，從而最終結(jié)果會讓收費的路段比例降低，達到時間最短的情況下，費用也是最少的，這就是最短時間路徑算法的一種粗略的理解.現(xiàn)在最佳路線規(guī)劃問題有很多種解決方法，其中Dijkstra被GPS導航系統(tǒng)普遍采用，他的關(guān)鍵方法就是從近到遠，給搜索方式加入權(quán)值，一步步地尋找最佳路徑，直到抵達目的地，這其實也就是我們所熟知的“性價比”，也是很容易理解的，在一些問題中，我們可以根據(jù)已知的條件和要求，探究一些可能利用的解決方案，然后再這些方案中來回探討，那最佳路徑算法也是如此，需要反復不停的對各個方法進行試驗，在不斷的搜索中嘗試找到有效且最佳的路徑，同時對已經(jīng)實驗過的路徑留下標記，方便以后用戶再次尋找該路徑，然而以上給出的方法都只是得到已知到達目的地的路線，不太具備智能高效等現(xiàn)代特點，在實際的應(yīng)用過程中不太能根據(jù)實際情況進行比較與分析，從而得出一個最佳路徑的方案.3.1三種最短路徑算法的比較與選擇最短路徑算法的選擇是導航功能中比較重要且關(guān)鍵的，下面我對三種算法進行歸納和總結(jié)，分析了它們?nèi)齻€的對比，如下表3所示：表3-1三種最短路徑算法對比表Floyd算法Bellman-Ford算法Dijkstra算法能否處理有向圖能能能完全或單源最短路完全最短路單源最短路單源最短路能否處理負權(quán)邊否能否圖的存儲方式鄰接矩陣鄰接表鄰接表接表時間復雜度O(V3)O(V*E)O(E+V*log|V|)空間復雜度O(V3)O(V+E)O(V+E)顯然由上表可以看出第三個算法無論是從時間上還是從空間復雜度上都比前兩個算法要好，但是第三個算法對于含負權(quán)邊的圖是沒有辦法的，在實際情況下，我們知道道路長度一定為正數(shù).時間也一定是大于0的，因此第三個算法，即Dijkstra算法對于無法處理含負權(quán)邊的圖這一不足可以忽略不計，綜上所述，第三種算法是最優(yōu)的.3.2Dijkstra算法Dijkstra算法（Dijkstra'salgorithm）是由艾茲赫爾·戴克斯特拉（EdsgerWybeDijkstra）一位荷蘭計算機科學家發(fā)明的[10].該算法主要是用來解決有向圖中指定的一個源點到其他頂點的最短路徑問題.3.2.1Dijkstra算法的原理Dijkstra核心算法的原理是把整個搜索路徑看成是一棵樹，這棵樹是以某個指定起點作為其根，每個節(jié)點到這個根的搜索路徑稱為到這個節(jié)點的最短路徑，在運用Dijkstra算法求最短路徑樹的時候，因為在運用算法的網(wǎng)絡(luò)中不存在負權(quán)的問題，所以在路徑樹產(chǎn)生的過程中對各節(jié)點到指定起點的距離和點與點之間的關(guān)系會一步一步加入到樹中.在一個帶權(quán)的有向圖中求取最短路徑其實就是計算從一個指定的起點到一個固定的權(quán)值最小的路徑，假如用弧的長度表示權(quán)值的話，那最小路徑就是從起點到終點的最小弧長度之和.為了進一步說明迪科斯徹算法的原理，我們可以從單源點的角度進行分析.在一個給定了起點P的帶權(quán)有向圖G=(V,E)中計算起點P到V中包含的其他節(jié)點的最短距離.對于這樣的問題，Dijkstra算法提出了一種按路徑長度增長順序來計算最短路徑的方法.用舉例說明，以D為開頭，求D到各個點的最短距離.圖3-1有權(quán)圖第1步：初始化距離，其實指與D直接連接的點的距離.dis[C]代表D到C點的最短距離，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余為無窮大.設(shè)置集合S用來表示已經(jīng)找到的最短路徑.此時，S={D}.現(xiàn)在得到D到各點距離{D(0)，C(3)，E（4），F(xiàn)（?），G（?），B（?），A(?)}，其中*代表未知數(shù)也可以說是無窮大，括號里面的數(shù)值代表D點到該點的最短距離.第2步：不考慮集合S中的值，因為dis[C]=3，是當中距離最短的，所以此時更新S，S={D,C}.接著我們看與C連接的點，分別有B，E，F(xiàn)，已經(jīng)在集合S中的不看，dis[C?B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C?F]=9，dis[E]=dis[C]+dis[C?E]=3+5=8>4(初始化時的dis[E]=4)不更新.此時{D(0)，C(3)，E（4），F(xiàn)（9），G（*），B（13），A(*)}.第3步：在第2步中，E點的值4最小，更新S={D，C，E}，此時看與E點直接連接的點，分別有F，G.dis[F]=dis[E]+dis[E?F]=4+2=6（比原來的值小，得到更新），dis[G]=dis[E]+dis[E?G]=4+8=12（更新）.此時{D(0)，C(3)，E（4），F(xiàn)（6），G（12），B（13），A(?)}.第4步：在第3步中，F(xiàn)點的值6最小，更新S={D，C，E，F(xiàn)}，此時看與F點直接連接的點，分別有B,A,G.dis[B]=dis[F]+dis[F?B]=6+7=13，dis[A]=dis[F]+dis[F?A]=6+16=22，dis[G]=dis[F]+dis[F?G]=6+9=15>12（不更新）.此時{D(0)，C(3)，E（4），F(xiàn)（6），G（12），B（13），A(22)}.第5步：在第4步中，G點的值12最小，更新S={D，C，E，F(xiàn)，G}，此時看與G點直接連接的點，只有A.dis[A]=dis[G]+dis[G?A]=12+14=26>22(不更新).{D(0)，C(3)，E（4），F(xiàn)（6），G（12），B（13），A(22)}.第6步：在第5步中，B點的值13最小，更新S={D，C，E，F(xiàn)，G，B}，此時看與B點直接連接的點，只有A.dis[A]=dis[B]+dis[B?A]=13+12=25>22(不更新).{D(0)，C(3)，E（4），F(xiàn)（6），G（12），B（13），A(22)}.第6步：最后只剩下A值，直接進入集合S={D，C，E，F(xiàn)，G，B，A}，此時所有的點都已經(jīng)遍歷結(jié)束，得到最終結(jié)果{D(0)，C(3)，E（4），F(xiàn)（6），G（12），B（13），A(22)}.3.2.2Dijkstra算法的實現(xiàn)前面經(jīng)過對算法思想和原理的分析，我們可以采用鄰接節(jié)點法來實現(xiàn)，其基本思想為先找出道路網(wǎng)中每個節(jié)點與其直接相連的節(jié)點的個數(shù)也稱為最大鄰接點，使用maximum來表示最大鄰接點并將其作為矩陣的列數(shù).一個道路網(wǎng)絡(luò)矩陣的行數(shù)由其節(jié)點總數(shù)N來表示，道路網(wǎng)絡(luò)中節(jié)點與節(jié)點之間的鄰接關(guān)系用鄰節(jié)點矩陣J來表示，J的行號是由節(jié)點的號順序排列的，凡是與節(jié)點vi相鄰的節(jié)點都填充到矩陣的第i行.假如其相鄰的節(jié)點數(shù)小于最大鄰接數(shù)maximum則使用0來填充第i行，一直到填滿.使用Dj來表示初始判斷矩陣，其構(gòu)造的方法與J相同，凡是與J中的每一個節(jié)點有鄰接關(guān)系的對應(yīng)邊，其對應(yīng)的權(quán)值填在同一位置上（其中∞表示0元素)，這樣的話J(vi,vj為了有效的能求解指定兩個節(jié)點之間的最短路徑,為了能夠獲取初始化的矩陣J以及Dj1，首先加載道路地圖數(shù)據(jù)，得到地圖數(shù)據(jù)中所有節(jié)點的序列號.需要注意的是電子地圖數(shù)據(jù)中的點與線的序號可能與實際的編號有差異，為了提高算法的靈活性這里統(tǒng)一使用地圖網(wǎng)絡(luò)數(shù)據(jù)中的序號作為參數(shù)進行運算.2，獲取地圖網(wǎng)絡(luò)數(shù)據(jù)的最大鄰接節(jié)點數(shù)值（maximum).3，構(gòu)造并初始化鄰接節(jié)點矩陣J，每一行的節(jié)點序列號可以任意放置，參照矩陣J的元素來構(gòu)造判斷矩陣Dj.完成矩陣J和D步驟1，用向量Flag(vi)來作為初始標記.Flag(步驟2，以起點v0為基礎(chǔ)初始化判斷矩陣Dj，第v0行的元素值，其中Flag(步驟3，以終點vn為判斷依據(jù)，判斷是否已經(jīng)標注Dj的第步驟4，在判斷矩陣Dj中那些已經(jīng)被標記過的行中，把每一元素的最小值求出并用Lmin表示.假如Lmin=∞則說明根本不存在最短距離，則程序直接退出.否則就是存在最短距離mindist=Lmin,把最小值所在的vi行和vj列記錄下來并在矩陣J中取出(vi,vj)的元素值，并用變量W記錄.假如第W行沒有被標記則去標記判斷矩陣Dj對應(yīng)的W行，同時把vi賦值給Flag(W)，同時在矩陣J中去查找對應(yīng)W行的值為vi的元素，并用ri和r步驟5，知道起點S和終點D，從終點開始沿著被標記的Flag的分量向前查詢，得到的mindist即為最短路徑.3.3Dijkstra算法在GPS導航中的實現(xiàn)3.3.1Dijkstra算法實現(xiàn)步驟Dijkstra算法是目前求最短路徑的方法中相對來講比較好的，且在交通網(wǎng)絡(luò)最短路徑中也展現(xiàn)了它的優(yōu)勢.因此，下面我們不僅要對該算法進行改進，還要在此基礎(chǔ)之上利用Matlab進行編程，根據(jù)源代碼一次求出局部最優(yōu)解，從而得到整體最優(yōu)路徑，并以上海吳涇鎮(zhèn)到延安西路900號的駕駛路線為例，結(jié)合不同需求對交通線路進行優(yōu)化設(shè)計.首先把路線圖畫為有權(quán)重的有向圖G，以及G中的一個來源頂點v0.我們用V表示G中所有的頂點的集合.圖中的邊都是兩個頂點形成的有序元素對.(vi，vj)表示從頂點vi到vj有路徑相連，E表示G中所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)定義.因此，就是從頂點到頂點的非負權(quán)重.邊的權(quán)重可以想象成兩個頂點之間的距離.任兩點間路徑的權(quán)重，就是該路徑上所有邊的權(quán)重總和.已知集合中有源點及改進Dijkstra算法可以找到的最低權(quán)重路徑.每兩條主干路的交匯路口組成的集合為V，進一步找到最短路徑的頂點放到新的集合中V’，3.3.2問題分析（一）問題提出從上海郊區(qū)吳涇鎮(zhèn)到達延安西路900號參加考試，本身半小時不到的路程在早高峰時間如若選擇不好交通道路，可能駕駛路程時間會在2小時以上，有很多駕駛員會在距離短擁堵多和距離長擁堵少兩種情況中糾結(jié)選擇.現(xiàn)在假定不出現(xiàn)車輛故障和交通事故，考慮以下兩個問題.從早上7點45分出發(fā)，吳涇鎮(zhèn)開往延安西路900號路線最短、時間最短的路線設(shè)計.（二）符號說明1：起點吳涇鎮(zhèn)2：龍吳路與龍耀路交叉路口3：龍吳路/龍華西路路口4：紅梅高架路出口5：中環(huán)路/虹許路路口6：滬閔高架路/內(nèi)環(huán)高架路7：滬閔高架路/漕溪北路路口8：龍華西路/中山南二路路口9：龍耀路與云錦路交叉路口10：康平路/華山路路口11：延安高架路入口12：延安西路900號（三）數(shù)據(jù)來源根據(jù)早高峰時間選擇路線，通過網(wǎng)絡(luò)查詢得到各個線路之間的距離、路途消耗時間[12].實驗環(huán)境軟件版本：matlabr2016a3.3.3實驗過程與結(jié)果由圖1可以抽象出圖2圖1圖2圖2可以抽象出來兩個矩陣，用矩陣來表示圖，圖的表示方式為：矩陣中的元素A（i，j）表示i點與j點所相接的邊的權(quán)重，如果i與j沒有直接相接的邊的話，權(quán)重為無窮大，在這里表示成2147483647，自身到自身的權(quán)重是0.Eg：A（4,6）=6.5km，A（2,9）=3.2A（4,8）=A（3,3）=0最終會將圖2抽象成兩個矩陣，一個用來存儲時間的權(quán)重，另一個用來儲存距離的權(quán)重，分別為圖3和圖4.。。。。。。。。。。。。。。。。。。。。圖3距離的權(quán)重圖圖4時間的權(quán)重圖Dijkstra算法表示的是單源最短路徑，我這里把1作為起點得到的結(jié)果如下:圖5距離圖的結(jié)果第一行表示的是起點到每個點的最短距離，得到1到2的最小距離為13km,1到3的最小距離是15，這里可以得到1到12的最小距離是22.8.第二行表示的儲存的路徑的最終點到起始點1的上一個點是哪一個點，比如1到12之間最短路徑是12-10-7-8-3-1.具體看的方法如下：從12開始，看第二行的數(shù)據(jù)，12的第二行是10就表示上一個點是10，找到10之后再看10的第二行，可以找到第上一個點是7，以此類推，直到第二行的數(shù)據(jù)是1為止，就可以得到一條最短路徑.圖6時間圖的結(jié)果和距離圖的使用方式一樣，只是從最短距離換成了最短時間.得出最短路程路線：1-3-8-7-10-12，該線路行程共22.8km.最省時間路線：1-4-7-10-12，該線路途中用時85mins.3.3.4實驗分析結(jié)合實際的交通狀態(tài)進行分析，起點和目的地之間的道路處于通暢狀態(tài)，因此最短路徑就處于虹梅高架路以及中環(huán)路的主干道上.但同時我們都知道早高峰和晚高峰實踐主干道都是非常擁擠的，因此我們?yōu)榱藢嶒灧治龅囊话阈?，要選擇路況較為通暢的或者避開擁擠時間段即可，同一條道路選擇下，車輛在平時段和高峰時段時長要平均相差70分鐘，在Dijkstra算法下不同路徑選擇可以節(jié)約20分鐘的時間，這說明此算法的應(yīng)用具有可行性，路徑選擇結(jié)果符合實際交通狀況，可以幫助更好優(yōu)化路線，滿足實際出行的需要.Dijkstra函數(shù)代碼如下：%n為方陣維度%x為起始點%input為輸入的圖，output為輸出結(jié)果的路徑function[output]=dijkstra(input,n,x)%各個變量的初始化output=zeros(2,n);%輸出的初始化.輸出的第一層是距離，第二層是路徑tag=zeros(1,n);%用于標記被使用過的頂點count=n-1;%用于記錄仍然未被使用的頂點，除了起始點以外，初值為n-1dist=zeros(1,n);path=zeros(1,n);distcap=2147483647;%定義int32最大值為無窮距離%對路徑以及最短距離的初始化fori=1:ndist(1,i)=distcap;%取int32最大值表示無窮距離path(1,i)=-1;%-1表示未找到路徑end%找到與初始點鄰接的頂點，更新最短距離與路徑的值fori=1:nifinput(x,i)<dist(1,i)dist(1,i)=input(x,i);path(1,i)=x;tag(1,x)=1;endend%dijkstra算法的實現(xiàn)while1distmin=distcap;%用于儲存dist中找到的最短距離的值,初值為無限大fori=1:nifdist(1,i)<distmin&&tag(1,i)==0distmin=dist(1,i);x=i;%找到最短距離且未被標記的點后，將該點作為新的起始點endendcount=count-1;%表示又一個元素被選取tag(1,x)=1;%將該元素標記為被選取的元素fori=1:nifdist(1,x)+input(x,i)<dist(1,i)dist(1,i)=dist(1,x)+input(x,i);path(1,i)=x;endendifcount==0%如果所有元素都被使用為空則終止循環(huán)break;endend%結(jié)果輸出fori=1:noutput(1,i)=dist(1,i);output(2,i)=path(1,i);endEnd3.3.5結(jié)語將Dijkstra算法應(yīng)用到早高峰交通路線設(shè)計中，采用matlab編程找出最優(yōu)路徑，方法具有普適性.早高峰線路設(shè)計一定程度上會影響該區(qū)域的經(jīng)濟發(fā)展狀況，在未來的應(yīng)用中，matlab相關(guān)代碼可拓展考慮到路程行程時間權(quán)值的動態(tài)變化，更具有實際應(yīng)用意義.第4章結(jié)論與展望隨著社會的不斷發(fā)展，人們對生活水平逐漸提高，GPS導航系統(tǒng)早已成為人們生活中很重要的一部分，與此同時他還對于推進社會發(fā)展起著不可推卸的作用.5G生活逐漸走入當今社會，網(wǎng)絡(luò)連接等技術(shù)不斷完善與改進，人們出行必須帶著移動智能設(shè)備，而GPS導航和定位系統(tǒng)早已成為出行的必備品，所以對于GPS的相關(guān)研究是具有相當大的現(xiàn)實意義的，也有很多的理論支撐.因此本文介紹GPS導航系統(tǒng)相關(guān)的技術(shù)及其最短路徑算法的研究，主要貢獻如下：首先說明了當今世界各國的車載導航系統(tǒng)的發(fā)展情況如何，并對其未來的進展進行預測.還給出了兩種世界上比較流行的兩種系統(tǒng)，分別是GPS和北斗衛(wèi)星，深度闡述了他們的系統(tǒng)工作流程和目前的發(fā)展狀況.其次分析了目前GPS車載導航的發(fā)展情況，列舉了GPS在車輛定位導航系統(tǒng)中的應(yīng)用，包括其設(shè)計原理和應(yīng)用實例.然后對最佳路徑算法和Dijkstra算法進行研究，對他們分別分析了各自的工作機制，并進行分別對比，實現(xiàn)Dijkstra算法在GPS導航中的應(yīng)用，說明dijkstra算法在實際應(yīng)用中的可行性.社會不斷發(fā)展，城市不斷進步，道路網(wǎng)絡(luò)也隨之變得越來越復雜，并且車流量的激增，使得道路出行越來越不便，路況的變化也是非常多的，所以導航系統(tǒng)應(yīng)該具