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