車載導(dǎo)航技術(shù)李必軍lee@2023/7/22課程安排一、基本概念二、課程背景三、汽車導(dǎo)航基本原理四、導(dǎo)航地理數(shù)據(jù)模型導(dǎo)航地理數(shù)據(jù)交換格式（國(guó)標(biāo)）五、汽車導(dǎo)航關(guān)鍵技術(shù)六、導(dǎo)航新技術(shù)（網(wǎng)絡(luò)導(dǎo)航）七、未來發(fā)展一、基本概念2023/7/222023/7/22GNSSGlobalNavigationSatelliteSystem,全球?qū)Ш叫l(wèi)星系統(tǒng)當(dāng)前全球有四大衛(wèi)星定位系統(tǒng)，分別是GPS、

GLONASS、Galileo、Compass；印度的IRNSS衛(wèi)星系統(tǒng)也在計(jì)劃中。參見劉基余：GPS衛(wèi)星導(dǎo)航定位原理與方法，科學(xué)出版社2023/7/22GPS?全球衛(wèi)星定位系統(tǒng)（GlobalPositionSystem,GPS）為美國(guó)國(guó)防部開發(fā)，由遍及全球的24顆人造衛(wèi)星所構(gòu)成，其中包括三顆預(yù)備衛(wèi)星。利用對(duì)民間開放的C/A碼標(biāo)準(zhǔn)，能得到十米左右的精度，為無線電定位法的一種。衛(wèi)星定位系統(tǒng)整體運(yùn)作上可分成三部份：太空部分、地面部分以及訊號(hào)部分。2023/7/22GPS太空部分目前太空中有24顆GPS衛(wèi)星可供定位運(yùn)用，它們平均分布於6個(gè)軌道面，每個(gè)軌道面上各有4顆，距離地面高度約10,900海里(大約20,000公里)，呈55°角傾斜繞行地球運(yùn)轉(zhuǎn)，繞行地球一周需12恒星時(shí)，每日可繞行地球2周；任何時(shí)間，任何地點(diǎn)，包含北極,南極，至少有4顆以上的衛(wèi)星出現(xiàn)在我們的上空。

2023/7/22GPS訊號(hào)部分GPS衛(wèi)星產(chǎn)生兩組隨機(jī)電碼，一組稱為C/A碼，一組稱為P碼。C/A碼主要開放給民間使用，因此在精度上刻意降低，P碼則是美國(guó)國(guó)防部保留為其軍事用途的電碼，精度比C/A碼高很多，因此設(shè)有密碼，一般民間使用者無法解讀。GPS衛(wèi)星傳送兩種頻率的載波，L1(Link1)載波的頻率為1575.42MHZ，L2(Link2)載波的頻率為1227.60MHZ。

2023/7/22GPS地面部分監(jiān)控站包括一個(gè)主要控制站（MasterControlStation）、五個(gè)監(jiān)測(cè)站（MonitorStation，夏威夷、亞森欣島、迪亞哥加西亞、瓜加林島、科羅拉多州），三個(gè)地面控制站（GroundControlStation）。監(jiān)測(cè)站主要負(fù)責(zé)追蹤所有衛(wèi)星的運(yùn)行位置、時(shí)間、氣象資料及電離層資料等，根據(jù)每15秒觀測(cè)到的資料計(jì)算出每15分鐘一組的平滑化數(shù)據(jù)（SmoothedData），傳送到主控制站后，由主控制站加以整合，計(jì)算出衛(wèi)星星歷、時(shí)表修正量、電離層改正系數(shù)，再轉(zhuǎn)換成導(dǎo)航訊息，以維護(hù)衛(wèi)星系統(tǒng)的精度與正常運(yùn)作。

使用者接收設(shè)備主要是一個(gè)衛(wèi)星訊號(hào)接收器，基本的功能是接收L1載波，分離出C/A電碼，進(jìn)行最簡(jiǎn)單的虛擬距離定位，是車輛定位所使用的機(jī)型。GPS衛(wèi)星產(chǎn)生兩種不同的載波來承載所有電碼與訊息，其中C/A碼僅調(diào)置在L1載波上，P碼則分別調(diào)置在L1與L2載波上，并區(qū)別為P1與P2電碼，但美國(guó)軍方目前僅開放C/A碼僅民間使用。2023/7/22BD1/22003年建立北斗導(dǎo)航試驗(yàn)系統(tǒng)，為中國(guó)及其周邊地區(qū)定位、授時(shí)、報(bào)文等至今年12月已有6顆導(dǎo)航衛(wèi)星，預(yù)計(jì)2012年覆蓋亞太地區(qū)，2020年建成覆蓋全球，形成由５顆靜止軌道衛(wèi)星和３０顆非靜止軌道衛(wèi)星組成的網(wǎng)絡(luò)應(yīng)用于海陸空交通運(yùn)輸、有線和無線通信、地質(zhì)勘探、資源調(diào)查、森林防火、醫(yī)療急救、海上搜救、精密測(cè)量、目標(biāo)監(jiān)控等領(lǐng)域BD1vsGPS2023/7/221、覆蓋范圍：北斗導(dǎo)航系統(tǒng)是覆蓋我國(guó)本土的區(qū)域?qū)Ш较到y(tǒng)。覆蓋范圍東經(jīng)約70°--140°，北緯5°--55°。GPS是覆蓋全球的全天候?qū)Ш较到y(tǒng)。能夠確保地球上任何地點(diǎn)、任何時(shí)間能同時(shí)觀測(cè)到6-9顆衛(wèi)星(實(shí)際上最多能觀測(cè)到11穎)。2、衛(wèi)星數(shù)量和軌道特性：北斗導(dǎo)航系統(tǒng)是在地球赤道平面上設(shè)置2顆地球同步衛(wèi)星顆衛(wèi)星的赤道角距約60°。GPS是在6個(gè)軌道平面上設(shè)置24顆衛(wèi)星，軌道赤道傾角55°，軌道面赤道角距60°。導(dǎo)航衛(wèi)星為準(zhǔn)同步軌道，繞地球一周11小時(shí)58分。BD1vsGPS2023/7/223、定位原理：北斗導(dǎo)航系統(tǒng)是主動(dòng)式雙向測(cè)距二維導(dǎo)航。地面中心控制系統(tǒng)解算，供用戶三維定位數(shù)據(jù)。GPS是被動(dòng)式偽碼單向測(cè)距三維導(dǎo)航。由用戶設(shè)備獨(dú)立解算自己三維定位數(shù)據(jù)?！氨倍芬惶?hào)”的這種工作原理帶來兩個(gè)方面的問題，一是用戶定位的同時(shí)失去了無線電隱蔽性，這在軍事上相當(dāng)不利，另一方面由于設(shè)備必須包含發(fā)射機(jī)，因此在體積、重量上、價(jià)格和功耗方面處于不利的地位。4、定位精度：北斗導(dǎo)航系統(tǒng)三維定位精度約幾十米，授時(shí)精度約100ns。GPS三維定位精度P碼目前己由16m提高到6m，C/A碼目前己由25-100m提高到15m，授時(shí)精度日前約20ns。BD1vsGPS2023/7/225、用戶容量：主動(dòng)雙向測(cè)距的詢問--應(yīng)答系統(tǒng)，用戶設(shè)備與地球同步衛(wèi)星之間不僅要接收地面中心控制系統(tǒng)的詢問信號(hào)，還要求用戶設(shè)備向同步衛(wèi)星發(fā)射應(yīng)答信號(hào)。系統(tǒng)的用戶容量取決于用戶允許的信道阻塞率、詢問信號(hào)速率和用戶的響應(yīng)頻率。

6、生存能力：和所有導(dǎo)航定位衛(wèi)星系統(tǒng)一樣，“北斗一號(hào)”基于中心控制系統(tǒng)和衛(wèi)星工作；但是“北斗一號(hào)”定位解算不是由用戶設(shè)備完成的。

7、實(shí)時(shí)性：“北斗一號(hào)”用戶的定位申請(qǐng)要送回中心控制系統(tǒng)，中心控制系統(tǒng)解算出用戶的三維位置數(shù)據(jù)之后再發(fā)回用戶，其間要經(jīng)過地球靜止衛(wèi)星走一個(gè)來回，再加上衛(wèi)星轉(zhuǎn)發(fā)，中心控制系統(tǒng)的處理，時(shí)間延遲對(duì)于高速運(yùn)動(dòng)體，就加大了定位的誤差。此外，“北斗一號(hào)”衛(wèi)星導(dǎo)航系統(tǒng)具備的短信通訊功能就是GPS所不具備的。BD22023/7/222009年滿足中國(guó)及周邊地區(qū)用戶對(duì)衛(wèi)星導(dǎo)航系統(tǒng)的需求，2010年覆蓋亞洲地區(qū)。北斗二號(hào)，是中國(guó)開發(fā)的獨(dú)立的全球衛(wèi)星地位系統(tǒng)，不是北斗一號(hào)的簡(jiǎn)單延伸，更類似于GPS全球定位系統(tǒng)和伽利略。北斗二號(hào)衛(wèi)星導(dǎo)航系統(tǒng)提供開放服務(wù)和授權(quán)服務(wù)。開放服務(wù)是在服務(wù)區(qū)免費(fèi)提供定位、測(cè)速和授時(shí)服務(wù)，定位精度為10米，授時(shí)精度為50納秒，測(cè)速精度為0.2米/秒。授權(quán)服務(wù)是向授權(quán)用戶提供更安全的定位、測(cè)速、授時(shí)和通信服務(wù)以及系統(tǒng)完好性信息。2023/7/22智能交通系統(tǒng)（ITS）智能交通系統(tǒng)就是以緩和道路堵塞和減少交通事故，提高交通利用者的方便、舒適為目的，利用交通信息系統(tǒng)、通訊網(wǎng)絡(luò)、定位系統(tǒng)和智能化分析與選線的交通系統(tǒng)的總稱。它通過傳播實(shí)時(shí)的交通信息使出行者對(duì)即將面對(duì)的交通環(huán)境有足夠的了解，并據(jù)此作出正確選擇；通過消除道路堵塞等交通隱患，建設(shè)良好的交通管制系統(tǒng)，減輕對(duì)環(huán)境的污染；通過對(duì)智能交叉路口和自動(dòng)駕駛技術(shù)的開發(fā)，提高行車安全，減少行駛時(shí)間。2023/7/22ITS的構(gòu)成ITS智能車輛系統(tǒng)智能信息服務(wù)系統(tǒng)智能交通管理系統(tǒng)智能道路系統(tǒng)……LBS自動(dòng)導(dǎo)航系統(tǒng)自動(dòng)駕駛系統(tǒng)自動(dòng)車距保持系統(tǒng)視覺增強(qiáng)系統(tǒng)周邊車輛危險(xiǎn)報(bào)警系統(tǒng)駕駛員狀態(tài)監(jiān)控系統(tǒng)聲控系統(tǒng)車道跟蹤/變更/交匯系統(tǒng)自動(dòng)剎車系統(tǒng)精確停車系統(tǒng)2023/7/22二、課程背景2023/7/22屬于汽車電子類消費(fèi)類產(chǎn)品，以車載嵌入式計(jì)算機(jī)技術(shù)為基礎(chǔ)，結(jié)合地理信息系統(tǒng)（GIS）、衛(wèi)星定位（GPS）技術(shù)、無線通信技術(shù)而開發(fā)的應(yīng)用產(chǎn)品。引言2.1汽車導(dǎo)航系統(tǒng)2023/7/222.2國(guó)家科技計(jì)劃2000年發(fā)改委發(fā)布了《國(guó)家計(jì)委關(guān)于組織實(shí)施衛(wèi)星導(dǎo)航應(yīng)用產(chǎn)業(yè)化專項(xiàng)的公告》。2004年發(fā)改委發(fā)布了《汽車產(chǎn)業(yè)發(fā)展政策》，支持作為汽車零部件重要組成部分的車載導(dǎo)航信息終端的自主化研究和生產(chǎn)。2004年，發(fā)改委發(fā)布了《國(guó)家發(fā)展改革委關(guān)于組織實(shí)施汽車電子產(chǎn)業(yè)化專項(xiàng)的通知》，明確把車載信息系統(tǒng)（包括車載信息系統(tǒng)、車載網(wǎng)絡(luò)系統(tǒng)等）作為支持重點(diǎn)。863計(jì)劃設(shè)立了對(duì)地觀測(cè)與導(dǎo)航領(lǐng)域，每年支持的科研經(jīng)費(fèi)上億元863計(jì)劃現(xiàn)代交通將車路協(xié)同與區(qū)域交通協(xié)調(diào)控制作為十二五主題項(xiàng)目2023/7/222.3導(dǎo)航技術(shù)前景衛(wèi)星導(dǎo)航是繼通信后又一大IT技術(shù)；2010年中國(guó)移動(dòng)用戶手機(jī)量7億；PND（PortalNavigationDevice）在中國(guó)需求量爆發(fā)增長(zhǎng)（IPHONE、NOKIA）物聯(lián)網(wǎng)技術(shù)發(fā)展將促進(jìn)導(dǎo)航技術(shù)2023/7/22車載導(dǎo)航技術(shù)主要問題與發(fā)展趨勢(shì)？2023/7/22三、汽車導(dǎo)航基本原理2023/7/223.1主要基本概念導(dǎo)航電子地圖自主導(dǎo)航POI（PointsofInterest）DR（DeadReconing）地圖匹配（MapMatching）路徑規(guī)劃（RoutePlaning）GIS-T（GISforTransportation）2023/7/223.2汽車導(dǎo)航系統(tǒng)汽車導(dǎo)航系統(tǒng)通過GPS信號(hào)、車輪傳感器、陀螺等三種傳感器獲取數(shù)據(jù)，確定汽車的速度和位置。車輪傳感器記錄車輪的速度，產(chǎn)生的脈沖信號(hào)用于定時(shí)計(jì)算行駛距離和方向變化。電子地圖存儲(chǔ)容量能夠存儲(chǔ)汽車運(yùn)行區(qū)域的所有數(shù)據(jù)，車載電腦與存儲(chǔ)道路網(wǎng)絡(luò)數(shù)據(jù)不斷比較判斷，更正定位誤差從而確定最佳行駛路徑。多用單片機(jī)結(jié)構(gòu)，嵌入式操作系統(tǒng)，軟件代碼存儲(chǔ)于ROM中，代碼簡(jiǎn)潔，運(yùn)行可靠，啟動(dòng)及關(guān)閉迅速，具有幾乎完整的ＰＣ組件和輸入輸出端口，適應(yīng)汽車惡劣的工作環(huán)境，在高溫或低溫以及劇烈振動(dòng)環(huán)境下工作可靠性高。2023/7/223.3自主導(dǎo)航（一）汽車自動(dòng)導(dǎo)航系統(tǒng)的作用是根據(jù)車輛當(dāng)前位置和用戶輸入的車輛目的地、參照電子地圖計(jì)算的行駛路線，并在行駛中將信息提供給駕車者。其主要特征是每套車載導(dǎo)航設(shè)備都自帶電子地圖，定位和導(dǎo)航功能全部由車載設(shè)備完成。它的工作過程主要有以下步驟：1、輸入數(shù)據(jù)信息出發(fā)前，車主將目的地輸入到導(dǎo)航設(shè)備中，在系統(tǒng)顯示的電子地圖上直接點(diǎn)擊，或者是借助某種輸入方法，將目的地名稱輸入到系統(tǒng)中。根據(jù)輸入設(shè)備的不同，可以有不同的地名輸入方法；目前人們也在開發(fā)語音識(shí)別技術(shù)的產(chǎn)品。2023/7/22自主導(dǎo)航（二）2、顯示電子地圖汽車導(dǎo)航系統(tǒng)中至關(guān)重要的一部分是存儲(chǔ)在光盤或內(nèi)置存儲(chǔ)器(如硬盤)中的電子地圖，電子地圖中存儲(chǔ)了一定范圍內(nèi)的地理、道路和交通管制信息，與地點(diǎn)對(duì)應(yīng)存儲(chǔ)了相關(guān)的經(jīng)緯度信息。汽車導(dǎo)航主機(jī)從經(jīng)過計(jì)算確定的當(dāng)前點(diǎn)經(jīng)緯度，通過與電子地圖數(shù)據(jù)的對(duì)比，就可以隨時(shí)確定車輛當(dāng)前所在的地點(diǎn)；一般汽車導(dǎo)航系統(tǒng)將車輛當(dāng)前位置默認(rèn)為出發(fā)點(diǎn)，在用戶輸入了目的地之后，導(dǎo)航系統(tǒng)根據(jù)電子地圖上存儲(chǔ)的地圖信息，就可以自動(dòng)計(jì)算出一條最合適的推薦路線。在有的系統(tǒng)中，用戶還可以指定途中希望經(jīng)過的途徑點(diǎn)，或者指定一定的路線選擇規(guī)則(如不允許經(jīng)過高速公路、按照行駛路線最短的原則等)。推薦的路線將以醒目的方式顯示在屏幕上的地圖中，同時(shí)屏幕上也時(shí)刻顯示出車輛的當(dāng)前位置，以提供參考；偏離路線后，重新根據(jù)確定的規(guī)則計(jì)算更新推薦路線。2023/7/223.4輸出設(shè)備汽車自動(dòng)導(dǎo)航系統(tǒng)的輸出設(shè)備包括顯示屏幕和語音輸出設(shè)備。顯示屏幕是液晶顯示屏(支持手寫輸入時(shí)，顯示屏表面還有一張透明的觸摸屏）；主要顯示內(nèi)容包括：地圖(包括相應(yīng)的道路名稱、公路編號(hào)、重要地點(diǎn)名稱等)、車輛的當(dāng)前位置、推薦路線等，根據(jù)用戶的設(shè)定還可以顯示附近的維修站、加油站、停車場(chǎng)及其他公共服務(wù)單位的名稱及地理位置等信息，以方便用戶需要；汽車導(dǎo)航系統(tǒng)操作的簡(jiǎn)便性是設(shè)計(jì)者追求的目標(biāo)，實(shí)際上這也涉及到一個(gè)安全的問題，因?yàn)轳{車者不允許一邊開車一邊看電子地圖。因此，設(shè)計(jì)者都考慮針對(duì)汽車導(dǎo)航系統(tǒng)應(yīng)用需求開發(fā)語音及語音識(shí)別技術(shù)。2023/7/223.5電子地圖汽車導(dǎo)航系統(tǒng)的應(yīng)用關(guān)鍵是電子地圖。隨著城鄉(xiāng)建設(shè)及道路變化，電子地圖也會(huì)定期更新。建立公共交通信息電臺(tái)，通過移動(dòng)通訊形式或電臺(tái)發(fā)送最新的交通信息提供給汽車上的導(dǎo)航設(shè)備對(duì)汽車上電子地圖的信息隨時(shí)進(jìn)行修正。我國(guó)對(duì)于地圖的出版有嚴(yán)格的規(guī)定。電子地圖標(biāo)準(zhǔn)性、政策性、保密性、技術(shù)性較強(qiáng)，是國(guó)家版圖、行政區(qū)劃界線的科學(xué)表達(dá)，因此電子地圖一定要經(jīng)審核后才能出版。為了適應(yīng)汽車自動(dòng)導(dǎo)航設(shè)備需要根據(jù)行駛區(qū)域、路線、自動(dòng)或人工改變地圖比例尺的需求，汽車導(dǎo)航系統(tǒng)所使用的地圖必須是以向量方式記錄的。2023/7/223.6車輛導(dǎo)航系統(tǒng)基本框架2023/7/22四、導(dǎo)航地理數(shù)據(jù)模型基礎(chǔ)地理數(shù)據(jù)與導(dǎo)航地理數(shù)據(jù)比較基礎(chǔ)地理數(shù)據(jù)導(dǎo)航地理數(shù)據(jù)數(shù)據(jù)內(nèi)容以同樣重要程度全面描述了地理空間中的地物特征主要刻畫道路網(wǎng)絡(luò)信息，以信息索引數(shù)據(jù)和背景數(shù)據(jù)作為參考信息數(shù)據(jù)組織結(jié)構(gòu)用“比例尺”的概念來描述地圖對(duì)現(xiàn)實(shí)世界不同詳盡程度的表達(dá)，較小比例尺的要素通常需進(jìn)行“綜合”不同比例尺數(shù)據(jù)按照相應(yīng)圖幅組織數(shù)據(jù)集的描述與表達(dá)無比例尺的概念在一個(gè)數(shù)據(jù)集中集成地表達(dá)不同詳細(xì)程度、不同抽象程度的道路拓?fù)潢P(guān)系不表達(dá)道路之間的交通關(guān)系通常定義數(shù)據(jù)中點(diǎn)、線、面的拓?fù)潢P(guān)系表達(dá)道路網(wǎng)絡(luò)的連通關(guān)系路段以道路中心線或交通流方向?yàn)榻Ｄ繕?biāo)基礎(chǔ)地理數(shù)據(jù)中道路的表示道路以中心線表達(dá)立交橋以點(diǎn)或圖示符號(hào)的方式表達(dá)不表示道路間的立交關(guān)系內(nèi)容簡(jiǎn)化內(nèi)容增加模型改變

傳統(tǒng)測(cè)繪產(chǎn)品不能滿足導(dǎo)航地理數(shù)據(jù)庫的基本要求基礎(chǔ)地理數(shù)據(jù)導(dǎo)航地理數(shù)據(jù)2023/7/22導(dǎo)航地理數(shù)據(jù)模型與交換格式(GB/T19711-2005)應(yīng)用范圍：ITS用于ITS（IntelligentTransportationSystems）的地圖數(shù)據(jù)“建?！迸c“交換”車載導(dǎo)航(NAV)實(shí)時(shí)引導(dǎo)基于位置的服務(wù)(LBS)離我最近的“服務(wù)”在什么地方？交通管理(TTM)協(xié)助交通管理中心進(jìn)行交通情況監(jiān)控與疏導(dǎo)先進(jìn)駕駛者輔助系統(tǒng)（ADAS）適應(yīng)性巡航控制，彎道車速報(bào)警與控制，車道偏離報(bào)警與控制,….應(yīng)用范圍：功能分類地圖顯示美觀、易讀（NAV/LBS/TTM）地理編碼能夠?qū)ζ鹗键c(diǎn)與目的地的地址信息進(jìn)行定位（NAV/LBS/TTM/ADAS）定位為GPS應(yīng)用提供坐標(biāo)信息（NAV/LBS/ADAS）路徑規(guī)劃確定出行路徑

(NAV/LBS/TTM/ADAS)行駛引導(dǎo)轉(zhuǎn)向?qū)崟r(shí)引導(dǎo)（NAV/LBS）信息服務(wù)提供POI信息與動(dòng)態(tài)服務(wù)信息（NAV/LBS/TTM）應(yīng)用范圍：功能需求地圖數(shù)據(jù)滿足以下要求對(duì)現(xiàn)實(shí)世界建模要素的一般精度（NAV/LBS/TTM）的或高精度（ADAS）幾何表達(dá)要素網(wǎng)絡(luò)拓?fù)浣煌ㄒ?guī)則完整的地址模型POI信息高程模型（ADAS）應(yīng)用范圍：非ITS領(lǐng)域ITS以外領(lǐng)域的應(yīng)用是獨(dú)立于應(yīng)用的數(shù)據(jù)模型不依賴于數(shù)據(jù)提供商和操作系統(tǒng)是對(duì)“現(xiàn)實(shí)世界”的建?？稍诜敲嫦騃TS的GIS系統(tǒng)中應(yīng)用作用在不同的應(yīng)用之間共享地理信息減少生產(chǎn)商的成本、降低用戶消費(fèi)價(jià)格不同應(yīng)用之間的成本均攤統(tǒng)一生產(chǎn)過程、格式，降低生產(chǎn)成本開放標(biāo)準(zhǔn)刺激競(jìng)爭(zhēng)適應(yīng)不斷發(fā)展的市場(chǎng)需求為應(yīng)用開發(fā)者提供了穩(wěn)定的開發(fā)基礎(chǔ)為產(chǎn)品與服務(wù)提供了技術(shù)框架基本內(nèi)容（1）從四個(gè)層面描述地圖數(shù)據(jù)概念層：數(shù)據(jù)內(nèi)容的最高層抽象描述（總體概念）現(xiàn)實(shí)世界對(duì)象（如一個(gè)線要素）及其特征（屬性）的數(shù)據(jù)庫表達(dá)內(nèi)容層：?jiǎn)蝹€(gè)數(shù)據(jù)元素的定義一個(gè)道路元素是……，街道名稱是……邏輯層：總體概念的邏輯組織一個(gè)線要素由起始結(jié)點(diǎn)、形狀點(diǎn)以及終止結(jié)點(diǎn)表達(dá)起始結(jié)點(diǎn)由X與Y坐標(biāo)表達(dá)形狀點(diǎn)……一個(gè)X坐標(biāo)是一個(gè)10位數(shù)…………物理層：物理表現(xiàn)一個(gè)線要素記錄包含X個(gè)字段，有Y個(gè)屬性基本內(nèi)容（2）獨(dú)立于具體應(yīng)用的數(shù)據(jù)模型數(shù)據(jù)內(nèi)容分類要素（FeatureCatalogue）屬性（AttributeCatalogue）關(guān)系（RelationshipsCatalogue）數(shù)據(jù)表達(dá)規(guī)則元數(shù)據(jù)邏輯與物理數(shù)據(jù)規(guī)范總體概念模型：基本數(shù)據(jù)組織單元獨(dú)立于具體應(yīng)用的數(shù)據(jù)模型要素：現(xiàn)實(shí)世界中地理實(shí)體或在某個(gè)地理位置的活動(dòng)在數(shù)據(jù)庫中的表達(dá)屬性：要素所具有的性質(zhì)關(guān)系：一個(gè)要素所具有的涉及到其它要素的特性要素屬性關(guān)系

幾何（Geometry）

要素（feature）復(fù)雜要素屬性關(guān)系點(diǎn)要素線要素面要素結(jié)點(diǎn)邊面坐標(biāo)

“要素（Feature）”是現(xiàn)實(shí)世界地理對(duì)象(object)在數(shù)據(jù)庫中的表達(dá)，如道路、建筑物等。每個(gè)要素必須屬于且僅屬于一個(gè)要素種類(FeatureClass)和一個(gè)要素主題（FeatureTheme）。要素種類和要素主題由一個(gè)名稱（Name）和一個(gè)代碼(Code)唯一標(biāo)識(shí)。每個(gè)要素可以有零個(gè)、一個(gè)或多個(gè)屬性（Attribute），并可以與一個(gè)或多個(gè)要素相關(guān)聯(lián)。每個(gè)要素只可以表達(dá)為一個(gè)要素表達(dá)類型（Featurecategory）。要素表達(dá)類型定義為點(diǎn)要素、線要素、面要素和復(fù)雜要素。單向箭頭線表達(dá)子類約束。模型中點(diǎn)要素、線要素、面要素均表示了兩次，表明這些要素在圖形數(shù)據(jù)文件中可以用兩種方法來表達(dá)。其區(qū)別在于本標(biāo)準(zhǔn)所支持的不同類型的拓?fù)潢P(guān)系。因而首先應(yīng)注意信息存儲(chǔ)在哪個(gè)層次。總體概念模型：拓?fù)浞秋@式拓?fù)洌簺]有顯式定義對(duì)象之間的拓?fù)潢P(guān)系，即拓?fù)潢P(guān)系僅僅通過坐標(biāo)值來定義。連通拓?fù)洌好鞔_定義了０維與１維對(duì)象之間的拓?fù)潢P(guān)系。但沒有明確定義這些對(duì)象與２維對(duì)象之間的拓?fù)潢P(guān)系完全拓?fù)洌海?、１、２維對(duì)象之間的所有拓?fù)潢P(guān)系都明確定義?？傮w概念模型：要素線要素面要素面邊點(diǎn)要素結(jié)點(diǎn)復(fù)雜要素Level-2Level-1要素的集合Level-1添加類型Level-0基本幾何圖元總體概念模型：屬性11..n屬性復(fù)雜屬性簡(jiǎn)單屬性子屬性1..n限制性子屬性1要素分類與定義：要素主題內(nèi)容規(guī)范：要素主題（FeatureTheme）道路與車渡行政區(qū)域命名區(qū)域土地覆蓋與利用構(gòu)造物鐵路水系道路附屬設(shè)施服務(wù)公共交通鏈參考要素通用要素道路與車渡1-層（簡(jiǎn)單要素）2-層（復(fù)雜要素）道路元素連接點(diǎn)渡口聯(lián)絡(luò)線封閉交通區(qū)域地址區(qū)域邊界元素地址區(qū)域路段交叉口渡口環(huán)島聚合路匯交路口位于…邊界上被…界定包含屬于1-層屬于包含2-層道路元素（ID）連接點(diǎn)（ID）渡口聯(lián)絡(luò)線（ID）界定開始于界定結(jié)束于包含屬于屬于包含開始于界定結(jié)束于界定包含屬于地址區(qū)域邊界元素（ID）包含屬于屬于包含界定開始于界定終止于包含屬于封閉交通區(qū)域（ID）地址區(qū)域（ID）界定被界定包含屬于路段（ID）渡口（ID）交叉口（ID）開始于界定結(jié)束于界定界定開始于界定結(jié)束于聚合路（ID）匯交路口（ID）環(huán)島（ID）包含屬于1-層1-層道路元素的獨(dú)立特性道路元素CD獨(dú)立于其它道路元素。當(dāng)CD被隔斷時(shí)，交通流仍可在其它道路元素通行。道路元素AF與BF的屬性不同（名稱不同），因而是彼此獨(dú)立的。AD、DE和EC的區(qū)別在于交通限制不同。1-層非結(jié)構(gòu)化的交通廣場(chǎng)視為封閉交通區(qū)域地址區(qū)域2-層2-層2-層上的多車道表示有三個(gè)連接點(diǎn)和一個(gè)交叉口的3岔路口2-層2-層2-層公共交通公交路線線段公交連接點(diǎn)公交車站公交點(diǎn)公交換乘區(qū)公交路線公交線路公交路線[ID]公交車站[ID]包含存在于包含存在于路線線段[ID]連接點(diǎn)[ID]開始于界定結(jié)束于界定公交點(diǎn)[ID]包含存在于線路[ID]包含存在于換乘區(qū)[ID]包含存在于公共交通鐵路鐵路中的要素鐵路元素[ID]鐵路元素連接點(diǎn)[ID]開始于界定結(jié)束于界定行政區(qū)劃國(guó)家：由國(guó)家邊境所界定的區(qū)域第1至第7級(jí)行政區(qū)劃：是一個(gè)國(guó)家行政結(jié)構(gòu)中的中間區(qū)劃層第8級(jí)行政區(qū)劃：是一個(gè)國(guó)家在全國(guó)范圍內(nèi)存在的行政區(qū)劃結(jié)構(gòu)中的最低一層第9級(jí)行政區(qū)劃：是第8級(jí)行政區(qū)劃的下一級(jí)。它可以只存在于部分第8級(jí)區(qū)劃中跨國(guó)行政區(qū)劃：由多個(gè)國(guó)家構(gòu)成的區(qū)域行政地點(diǎn)：在行政區(qū)劃層次結(jié)構(gòu)之外定義的管理區(qū)域行政區(qū)劃邊界元素行政區(qū)劃邊界連接點(diǎn)服務(wù)（POI）

在某一位置的活動(dòng)。代表的是一個(gè)活動(dòng)而非活動(dòng)發(fā)生所在地的建筑物。

機(jī)場(chǎng)[ID]露天大型運(yùn)動(dòng)場(chǎng)[ID]高速公路休息區(qū)[ID]上山纜索站[ID]收費(fèi)站[ID]飯店[ID]旅游點(diǎn)[ID]旅館[ID]銀行[ID]服務(wù)中的要素服務(wù)入口點(diǎn)[ID]道路附屬設(shè)施道路附屬設(shè)施主題中的要素路標(biāo)[ID]環(huán)境設(shè)備[ID]測(cè)量設(shè)備[ID]交通標(biāo)志[ID]人行橫道[ID]照明燈[ID]交通信號(hào)燈[ID]安全設(shè)備[ID]路面標(biāo)記[ID]構(gòu)造物交通網(wǎng)絡(luò)中的重要建筑物，如橋梁、高架橋、隧道、渡槽、路塹（Cuttings）、廊道、防護(hù)墻（Retainingwall）、涵洞等構(gòu)造物構(gòu)造物主題中的要素水系對(duì)水體的表達(dá)

水體[ID]水體邊界元素[ID]水體邊界連接點(diǎn)[ID]被界定界定開始于界定結(jié)束于界定內(nèi)陸水體水道運(yùn)河河流湖泊海水沿海礁湖河口海、洋水庫要素屬性分段屬性通用要素屬性及用戶自定義屬性

道路附屬設(shè)施屬性屬于有目的地位置[屬于有交通標(biāo)志上的路線編號(hào)屬于有交通標(biāo)志類型屬于帶有交通標(biāo)志上的符號(hào)屬于有交通標(biāo)志上的數(shù)值屬于帶有其它文字內(nèi)容屬于在…有效方向交通標(biāo)志信息有屬于交通標(biāo)志交通標(biāo)志上的目的地信息屬于有道路附屬設(shè)施中的要素設(shè)備標(biāo)識(shí)屬于有出口編號(hào)有屬于要素關(guān)系：關(guān)系數(shù)據(jù)模型要素關(guān)系關(guān)系類型屬性具有屬于圖層包含包含于作為１＃成員參與涉及1＃成員作為N＃成員參與涉及Ｎ＃成員具有屬于

交通關(guān)系要素空間關(guān)系鏈接關(guān)系交通關(guān)系在ISOGDF5.0中，由交通標(biāo)志特別指明的交通限制用關(guān)系（稱為策略）來表達(dá)，而一般具有較普遍意義的交通規(guī)則只需用道路元素的屬性來表達(dá)。策略分為：優(yōu)先策略禁止策略限制策略優(yōu)先策略優(yōu)先策略（只能用于描述靜態(tài)的行駛權(quán)，不描述由交通信號(hào)燈控制的優(yōu)先權(quán)

）隱式：主路先行、直行先行、……顯式：由交通標(biāo)志指示關(guān)系代碼道路元素連接點(diǎn)道路元素道路元素道路元素2104 L711 J1 L712 L522 L5212104 L511 J2 L721 禁止策略關(guān)系代碼道路元素連接點(diǎn)道路元素道路元素道路元素

2103 L711 J1 L712 L522 L521 2103 L723 J4 L521

限制策略要素空間關(guān)系表達(dá)要素在空間位置上的包含與鄰接關(guān)系可以通過空間要素的形狀及位置坐標(biāo)推算，在模型中顯式定義是為了提高導(dǎo)航應(yīng)用中實(shí)時(shí)查詢與計(jì)算的速度行政區(qū)劃建成區(qū)域管區(qū)有名稱區(qū)域服務(wù)道路元素相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)連接點(diǎn)相關(guān)相關(guān)相關(guān)相關(guān)建筑物相關(guān)相關(guān)相關(guān)相關(guān)服務(wù)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)建成區(qū)域相關(guān)相關(guān)管區(qū)相關(guān)相關(guān)相關(guān)相關(guān)封閉交通區(qū)域相關(guān)相關(guān)相關(guān)相關(guān)渡口聯(lián)絡(luò)線相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)相關(guān)要素鏈接關(guān)系路標(biāo)與道路元素匯交路口與出口……交通元素[ID]立交跨越[ID]構(gòu)造物[ID]有上層要素作為上層要素參與有下層要素作為下層要素參與構(gòu)成由……組成要素鏈接關(guān)系路標(biāo)信息直達(dá)路線……R1R2R3

珠海中山14

橫瀝坦尾2529L574L604L575S1關(guān)系代碼路標(biāo)道路元素道路元素屬性值2128S1L574L604珠海中山

142128S1L574L575橫瀝坦尾

2529交換格式交換格式包含字母或數(shù)字字符的記錄記錄長(zhǎng)80個(gè)字節(jié)數(shù)據(jù)組織記錄（records）包含于——分區(qū)（sections）包含于——層（layers）包含于——數(shù)據(jù)集（datasets）包含于——一個(gè)或多個(gè)卷（volumes）交換格式的記錄層次交換格式交換格式元數(shù)據(jù)與數(shù)據(jù)記錄點(diǎn)要素記錄線要素記錄結(jié)點(diǎn)記錄邊記錄屬性記錄2023/7/22五、汽車導(dǎo)航關(guān)鍵技術(shù)5.1時(shí)空一體化模型多元數(shù)據(jù)采集與融合技術(shù)邏輯模型與物理存儲(chǔ)格式5.2組合定位技術(shù)5.3路徑規(guī)劃技術(shù)2023/7/225.1時(shí)空一體化模型2023/7/225.1.1多元數(shù)據(jù)采集與融合建模道路數(shù)據(jù)的采集道路網(wǎng)（基礎(chǔ)數(shù)據(jù)）設(shè)施信息屬性信息實(shí)時(shí)交通信息的采集與管理（重點(diǎn)）2023/7/22實(shí)時(shí)交通信息編碼與表達(dá)交通信息采集 交通流：通過傳感檢測(cè)設(shè)施； 出行信息：通過警察、交通等公共部門。交通信息編碼 交通信息編碼方案； 交通信息與導(dǎo)航電子地圖的融合方案。交通信息管理 使用面向?qū)ο髷?shù)據(jù)庫來管理交通信息。交通信息發(fā)布 發(fā)布交通信息的手段包括有：調(diào)頻副載波、GSM、GPRS、CDMA、3G等。2023/7/22實(shí)時(shí)交通信息發(fā)布西方發(fā)達(dá)國(guó)家的ITS建設(shè)已經(jīng)發(fā)展到了一定程度，普遍開展了較高層次的交通信息服務(wù)，最典型的莫過于日本的VICS以及歐洲的RDS-TMC。我國(guó)由于交通、通信等基礎(chǔ)設(shè)施不完備，到現(xiàn)在為止還沒有建立起一套統(tǒng)一的、完整的實(shí)時(shí)交通信息采集、處理、發(fā)布的有效途徑。實(shí)時(shí)交通信息系統(tǒng)2023/7/22實(shí)時(shí)交通系統(tǒng)的概述實(shí)時(shí)智能交通運(yùn)輸系統(tǒng)（ITS）是人們徹底解決交通擁擠、交通事故以及環(huán)境污染等交通問題的殺手锏，它將先進(jìn)的信息、數(shù)據(jù)通迅?jìng)鬏?、電子控制、傳感器以及?jì)算機(jī)處理等各種技術(shù)有效地綜合運(yùn)用于整個(gè)運(yùn)輸體系，從而建立起一種大范圍、全方位地發(fā)揮作用的實(shí)時(shí)、準(zhǔn)確、高效的運(yùn)輸綜合管理系統(tǒng)，使人、車、路都得以密切配合、和諧統(tǒng)一，極大地提高交通運(yùn)輸效率，保障交通安全，改善環(huán)境質(zhì)量，提高能源利用率。先進(jìn)的交通信息系統(tǒng)（ATIS）是ITS的重要組成部分，也是發(fā)展ITS的基礎(chǔ)和關(guān)鍵技術(shù)，ATIS是建立在完善的信息網(wǎng)絡(luò)基礎(chǔ)上的，交通參與者通過裝備在道路上、車上、換乘站上、停車場(chǎng)上以及氣象中心的傳感器和傳輸設(shè)備，可以向交通信息中心提供各處的交通信息。

2023/7/22類分件事息信通交時(shí)實(shí)按照ISO14819-2-2006的規(guī)定，實(shí)時(shí)交通信息可分為以下31類：編號(hào)事件類別編號(hào)事件類別1levelofservice17windandairquality2expectedlevelofservice18activities3accidents19securityalerts4incidents20

delays5closuresandlanerestrictions21cancellations6carriagewayrestrictions22traveltimeinformation7exitrestrictions23dangerousvehicles8entryrestrictions24exceptionalloads/vehicles9trafficrestrictions25trafficequipmentstatus10carpoolinformation26sizeandweightlimits11roadworks27parkingrestrictions12obstructionhazards28parking13dangeroussituations29referencetoaudiobroadcasts14roadconditions30servicemessages15temperatures31specialmessages16precipitationandvisibility2023/7/22

EUROSCOUTEUROSCOUT是以紅外線信標(biāo)為媒體的動(dòng)態(tài)路線引導(dǎo)系統(tǒng)。車輛和信標(biāo)間的紅外線通信是雙向進(jìn)行的，汽車就變?yōu)橐粋€(gè)探頭，將旅行時(shí)間、排隊(duì)等候時(shí)間及OD信息等交通信息數(shù)據(jù)傳輸給中央引導(dǎo)計(jì)算機(jī)。歐洲的代表性系統(tǒng)2023/7/22RDS-TMC基于ALERT-C協(xié)議的交通數(shù)據(jù)專用電臺(tái)RDS-TMC用于為歐洲大陸提供交通與出行信息服務(wù)（TrafficandTravelInformationServices）。ALERT-C協(xié)議主要由兩個(gè)表組成：位置編碼表以及事件列表。隨著無線通信技術(shù)的發(fā)展，除了RDS能作為TTI的傳輸媒介外，DAB（DigitalAudioBroadcasting）、DVB（DigitalVideoBroadcasting）、GSM/GPRS/CDMA以及MobileInternet都可以用來傳輸TTI，這些傳輸媒介比RDS的數(shù)據(jù)傳輸能力強(qiáng)。2023/7/22RDS-TMC特點(diǎn)不斷更新的、實(shí)時(shí)發(fā)送的交通信息，包括交通堵塞、交通事故以及道路維修等；可進(jìn)行過濾，只取與動(dòng)態(tài)導(dǎo)航相關(guān)的路段信息；語言獨(dú)立性；高質(zhì)量的無線數(shù)據(jù)傳輸，整個(gè)RDS-TMC流程的數(shù)據(jù)傳輸最多只需30秒；RDS-TMC接收機(jī)在歐洲范圍內(nèi)的兼容性；遍布?xì)W洲范圍的免費(fèi)或低收費(fèi)的交通信息服務(wù)。2023/7/22

歐洲的RDS-TMC服務(wù)流程2023/7/22美國(guó)的代表性系統(tǒng)TRAVTEKTRAVTEK以實(shí)時(shí)路線引導(dǎo)和服務(wù)信息系統(tǒng)實(shí)用化為目的，由交通管理中心、信息與服務(wù)中心、裝有導(dǎo)航裝置的車輛組成。交通管理中心進(jìn)行道路交通信息的收集、管理及提供，同時(shí)還進(jìn)行系統(tǒng)運(yùn)行所必需的信息管理和提供；信息服務(wù)中心收集觀光設(shè)施、旅館、飯店等為對(duì)象的各種服務(wù)信息；車載導(dǎo)航裝置由車輛位置測(cè)定、路線選擇及接口3種功能構(gòu)成，可顯示交通堵塞地段、事故及施工等信息的奧蘭多地區(qū)的地圖、按駕駛員需要進(jìn)行的路線引導(dǎo)及提供服務(wù)的文字信息等。2023/7/22ADVANCEADVANCE通過電波的雙向通信直接將車載導(dǎo)航裝置和交通管制中心連通，導(dǎo)航裝置由接觸式屏幕、顯示器及導(dǎo)航計(jì)算機(jī)構(gòu)成。一輸入最終目的地便可利用最新交通信息計(jì)算最佳路線。路線引導(dǎo)是采用聲音合成及用顯示器上的符號(hào)指示的形式。美國(guó)的代表性系統(tǒng)2023/7/22FASTTRACFASTTRAC是把先進(jìn)交通管理系統(tǒng)（ATMS）和先進(jìn)交通信息系統(tǒng)（ATIS）技術(shù)組合在一起的ITS項(xiàng)目，它計(jì)劃進(jìn)行使實(shí)驗(yàn)車輛與信息控制方式統(tǒng)一的試驗(yàn)，亦即根據(jù)車輛測(cè)量的等候時(shí)間等使信號(hào)控制和綠色信號(hào)實(shí)現(xiàn)最佳化。美國(guó)的代表性系統(tǒng)2023/7/22日本的代表性系統(tǒng)VICSVICS中心通過日本道路交通通信中心匯總交通管理者和道路管理者雙方的交通信息。由VICS提供的信息有：交通堵塞信息、所需時(shí)間信息、交通障礙信息、交通管制信息和停車場(chǎng)信息5種。2023/7/22ATISATIS是先進(jìn)的交通信息服務(wù)系統(tǒng)，它的通信媒體是電話線路（無線、有線）。交通信息利用者通過車上裝載的導(dǎo)航裝置或自己家及辦公室的微機(jī)，可按需要接收多媒體的地圖信息和文字信息。日本的代表性系統(tǒng)2023/7/22VICS 道路車輛信息通信系統(tǒng)（VehicleInformationandCommunicationSystem，VICS）是日本東京一家具有半官方辦民營(yíng)性質(zhì)的交通信息處理、發(fā)布中心，它將警察部門和高速公路管理部門提供的交通堵塞、駕駛所需時(shí)間、交通施工、車速及路線限制，以及停車場(chǎng)空位等信息在VICS中心編輯處理后及時(shí)傳輸給交通參與者。2023/7/22實(shí)時(shí)交通信息的原理（VICS）信息收集信息處理信息傳輸2023/7/22VICS由四部分功能組成：實(shí)時(shí)交通信息的采集、交通信息的編輯與處理、交通信息的無線傳輸、車載單元對(duì)交通信息的接收和使用。VICS釆用三種無線通信方式：紅外信標(biāo)（安裝于道路的主要路段）、短波信標(biāo)（安裝于鄉(xiāng)村區(qū)域的道路和高速公路）和調(diào)頻副載波廣播。VICS播發(fā)的實(shí)時(shí)交通信息包括：主要地點(diǎn)間的旅行時(shí)間、交通擁擠狀況、交通法規(guī)、事故、交通管制、廣域的最優(yōu)路徑選擇信息和道路施工信息、天氣狀況及停車場(chǎng)信息等。VICS于1993年11月開始試運(yùn)行，于1996年4月正是開始信息服務(wù)，覆蓋區(qū)包括東京等大城市及主要高速公路，在2002年已經(jīng)基本覆蓋全日本。VICS特點(diǎn)2023/7/22提供信息內(nèi)容通過電波信標(biāo)，主要提供行駛方向的有關(guān)信息：高速公路各出入口之間的駕駛時(shí)間以及包括附近一般道路在內(nèi)的交通堵塞信息和道路分流指南。交通事故信息和車速、車道限制以及輪胎防滑鏈加裝規(guī)定等信息；高速公路休息服務(wù)區(qū)域和停車區(qū)域的車位空置狀況信息。通過光信標(biāo)，主要提供行駛方向的有關(guān)信息：交通堵塞信息以及駕駛所需時(shí)間；交通事故以及有關(guān)事故車輛的信息和因施工而實(shí)行的道路限制等信息；停車場(chǎng)的車位空置狀況信息。通過調(diào)頻多重廣播，主要提供以下有關(guān)信息：廣泛區(qū)域的交通堵塞信息和駕駛所需的時(shí)間；廣泛區(qū)域內(nèi)的交通事故、道路施工以及車速、車道限制的信息；停車場(chǎng)的位置和車位空置狀況信息。2023/7/22交通信息顯示三種類型1、文字顯示型即在車載機(jī)的顯示器上以文字的形式顯示VICS信息。它用文字提供時(shí)刻變化著的道路交通狀況信息，幫助駕駛員選擇行車路線。一般道路光信標(biāo)&電波信標(biāo)高速道路一般道路多重調(diào)頻廣播高速道路2023/7/222、簡(jiǎn)易圖形顯示型

即在車載機(jī)的顯示器上以簡(jiǎn)單的圖形顯

VICS信息。其特點(diǎn)是，以道路交通信息模型化的簡(jiǎn)易圖形和文字來顯示交通堵塞地點(diǎn)和地段行駛時(shí)間。交通信息顯示三種類型一般道路光信標(biāo)&電波信標(biāo)城市快速路一般道路多重調(diào)頻廣播城市快速路紅色：

嚴(yán)重堵塞黃色：

輕微堵塞2023/7/223、地圖顯示型

即在車載機(jī)顯示器的地圖畫面上集中顯示交通堵塞等各種信息。由于行駛地點(diǎn)和堵塞地段一目了然，所以，駕駛員可以根據(jù)隨時(shí)變化的道路交通狀況來選擇行駛時(shí)間最短的線路或是避開堵塞地段的線路。交通信息顯示三種類型2023/7/22浮動(dòng)車交通信息采集系統(tǒng)浮動(dòng)車交通信息采集系統(tǒng)介紹以裝有自動(dòng)定位裝置的車輛作為浮動(dòng)車，通過無線通信網(wǎng)絡(luò)實(shí)現(xiàn)浮動(dòng)車與數(shù)據(jù)處理中心的數(shù)據(jù)交換，產(chǎn)生實(shí)時(shí)路況信息，通過發(fā)布系統(tǒng)以Internet、無線局域網(wǎng)或公眾移動(dòng)網(wǎng)等多種方式向管理決策部門和社會(huì)公眾提供服務(wù)，是一種新型的交通信息采集系統(tǒng)。

2023/7/22浮動(dòng)車交通信息采集系統(tǒng)主要功能面向政府管理部門實(shí)時(shí)掌握道路運(yùn)行狀況和發(fā)展態(tài)勢(shì)評(píng)價(jià)擁堵治理效果，制訂疏堵方案掌握出租車運(yùn)營(yíng)特征和行業(yè)發(fā)展，制定行業(yè)政策為綜合交通規(guī)劃提供數(shù)據(jù)支持面向社會(huì)公眾提供實(shí)時(shí)路況信息，路徑誘導(dǎo)避開擁堵路段，提供出行效率實(shí)時(shí)浮動(dòng)車數(shù)據(jù)處理系統(tǒng)實(shí)時(shí)地圖匹配，匹配準(zhǔn)確率達(dá)95%以上實(shí)時(shí)準(zhǔn)確的旅行速度估計(jì)5分鐘間隔動(dòng)態(tài)更新路網(wǎng)狀態(tài)信息2023/7/22浮動(dòng)車信息采集系統(tǒng)提供數(shù)據(jù)結(jié)構(gòu)

以序列號(hào)、時(shí)間、類別、內(nèi)容等多個(gè)字段組成一條記錄，并由多條記錄形成一份.xml文件發(fā)布。記錄數(shù)據(jù)結(jié)構(gòu)示例：

<Event>

<Serial>4559318</Serial>

<Time>2007-09-3023:52:42</Time>

<Type>3</Type>

<Content/>

<State>1</State>

<Valid>1</Valid>

<Spot>事故處理咨詢</Spot>

<PhoneX>116.417613</PhoneX>

<PhoneY>39.8021</PhoneY>

<EventX>0</EventX>

<EventY>0</EventY></Event>2023/7/22北京市實(shí)時(shí)交通信息路網(wǎng)數(shù)據(jù)顯示：用戶根據(jù)路名查詢道路實(shí)時(shí)交通信息情況：2023/7/22地感線圈的原理地感線圈實(shí)質(zhì)是一震蕩電路，其原則是振蕩穩(wěn)定可靠。當(dāng)有大的金屬物如汽車經(jīng)過時(shí)，由于空間介質(zhì)發(fā)生變化引起了振蕩頻率的變化（有金屬物體時(shí)振蕩頻率升高），這個(gè)變化就作為汽車經(jīng)過“地感線圈”的證實(shí)信號(hào)。同時(shí)利用這個(gè)信號(hào)的開始和結(jié)束之間的時(shí)間間隔來測(cè)量汽車的移動(dòng)速度。技術(shù)關(guān)鍵是設(shè)計(jì)出的振蕩器穩(wěn)定可靠并且有汽車經(jīng)過時(shí)頻率變化明顯。地感線圈采集動(dòng)態(tài)交通信息2023/7/22地感線圈采集數(shù)據(jù)格式地感線圈采集到的數(shù)據(jù)主要就是車輛行駛速度。交管部門事先將埋有地感線圈的各環(huán)路上的路段進(jìn)行base64編碼處理，如“HI9064c薊門橋->學(xué)知橋”，結(jié)合此路段接收到的車速組成一條記錄。最終所有的記錄形成一個(gè).xml文件，以每2分鐘一次的頻率發(fā)送出來。2023/7/22地感線圈采集動(dòng)態(tài)交通信息導(dǎo)航儀上顯示的二、三、四環(huán)上的交通信息狀況：2023/7/22放大后的二、三、四環(huán)上的交通信息狀況：用戶查詢環(huán)路上的各路段的交通狀況：2023/7/22浮動(dòng)車與地感線圈采集系統(tǒng)的比較投入和效益地感線圈需要政府交通部門一次性的投入，花費(fèi)人力物力去埋設(shè)，并且后期不會(huì)直接產(chǎn)生效益；浮動(dòng)車由出租車公司向交管部門訂購整套管理系統(tǒng)，并繳納一定的費(fèi)用，而交管部門則在系統(tǒng)中設(shè)置反饋車輛交通信息的裝置。采集數(shù)據(jù)范圍地感線圈是靜態(tài)的，目前只在北京市的二環(huán)、三環(huán)、四環(huán)上埋設(shè)，提供僅限于環(huán)路上的交通狀況；浮動(dòng)車是則動(dòng)態(tài)的，在北京市六環(huán)以內(nèi)次干道以上的道路信息都可以被接收到。數(shù)據(jù)量及質(zhì)量由范圍決定，故地感線圈提供的數(shù)據(jù)量較小，而浮動(dòng)車則能提供大量的交通信息數(shù)據(jù)；并且，由于浮動(dòng)車是動(dòng)態(tài)的，其提供的信息更具有現(xiàn)實(shí)性，質(zhì)量也更高一些。2023/7/225.1.2邏輯模型與物理存儲(chǔ)格式2023/7/22NCHRP模型NCHRP（NationalCooperativeHighwayResearchProgram）的概念模型2023/7/22NCHRP的主要功能i)Locate（定位）.Establishthelocationofanunknownpointinthefieldbyreferencetootherobjectsinthe"realworld.“ii)Position.Translationofareal-worldlocationintoadatabaselocation.iii)Place（位置轉(zhuǎn)換）.Translationofadatabaselocationintoareal-worldlocation(i.e.,theinverseof"position").iv)Transform（不同參照系間的轉(zhuǎn)換）.ConversionbetweenvariousLRMsrepresentedbydatabaselocations,betweenvariouscartographicrepresentationsandbetweenLRMsandcartographicrepresentations.2023/7/22NCHRP的優(yōu)缺點(diǎn)基準(zhǔn)層由錨固點(diǎn)和錨固段組成,可連接各種網(wǎng)絡(luò)和多種地圖表達(dá),實(shí)現(xiàn)不同數(shù)據(jù)間的共享。每一個(gè)網(wǎng)絡(luò)模型都有很多的LRM,而商業(yè)數(shù)據(jù)庫都是基于不同的LRM建立的,因此提供了一個(gè)數(shù)據(jù)集成的方法。NCHRP模型因其穩(wěn)固的理論而得到好評(píng),尤其是模型對(duì)于適應(yīng)多網(wǎng)絡(luò)和多種地圖表達(dá)的貢獻(xiàn)。然而,NCHRP模型應(yīng)用困難、不靈活,尤其是對(duì)于線性基準(zhǔn)層的維護(hù)2023/7/22以結(jié)點(diǎn)弧段為基礎(chǔ)的道路網(wǎng)模型平面強(qiáng)化的道路網(wǎng)數(shù)據(jù)模型基于車道的交通網(wǎng)絡(luò)模型（Fohl，1996）建模單位定義為車道基于特征的城市交通網(wǎng)模型（陸鋒，2000）將互通的車道集成，作為一個(gè)綜合車道改進(jìn)的基于車道的道路數(shù)據(jù)模型（左小清，2004）基于特征和超圖理論的交通網(wǎng)絡(luò)數(shù)據(jù)模型（于至文，2005）2023/7/22國(guó)際流行的導(dǎo)航數(shù)據(jù)格式1ISOGDF2日本的Kiwi3美國(guó)NevTechSADL2023/7/22GDF（GeographicalDataFile）是歐洲交通網(wǎng)絡(luò)表達(dá)的空間數(shù)據(jù)標(biāo)準(zhǔn)，用于描述和傳遞與路網(wǎng)和道路相關(guān)的數(shù)據(jù)。它規(guī)定了獲取數(shù)據(jù)的方法和如何定義各類特征要素、屬性數(shù)據(jù)和相互關(guān)系。主要用于汽車導(dǎo)航系統(tǒng)，但也可以用在其他交通數(shù)據(jù)資料庫中。GDF格式已為CEN（CentralEuropeanNormalization）所認(rèn)可，并已提交ISOTC204/WG3，最新版本的GDF5.0。GDF2023/7/22KIWI格式是由KIWI-WConsortium制定的標(biāo)準(zhǔn)，它是專門針對(duì)汽車導(dǎo)航的電子數(shù)據(jù)格式。該格式是公開的，任何人都可使用。KIWI-WConsortium成立于2001年7月，致力于制定汽車導(dǎo)航用電子地圖物理存儲(chǔ)格式（PSF）的行業(yè)標(biāo)準(zhǔn)，PSF的主要載體是CD、DVD和HDD。KIWI的將用于顯示的數(shù)據(jù)和用于導(dǎo)航的數(shù)據(jù)分離，提高顯示速度以及路徑規(guī)劃效率。KIWI按照數(shù)據(jù)邏輯結(jié)構(gòu)來存儲(chǔ)存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)物理結(jié)構(gòu)實(shí)際上就是數(shù)據(jù)邏輯結(jié)構(gòu)在物理存儲(chǔ)介質(zhì)上的映像。KIWI2023/7/22NavTech公司致力于生產(chǎn)大比例尺的道路網(wǎng)商用數(shù)據(jù)，包括詳細(xì)的道路、道路附屬物、交通信息等，這些數(shù)據(jù)主要用于車輛導(dǎo)航。NavTech公司自有的商用地理數(shù)據(jù)庫的數(shù)據(jù)格式是SDAL（SharedDataAccessLibrary），通過SDAL編譯器，可以把一般的電子地圖數(shù)據(jù)轉(zhuǎn)換為SDAL格式，進(jìn)而可以由SDAL程序接口調(diào)用SDAL格式數(shù)據(jù)用于各種車輛導(dǎo)航應(yīng)用。SDAL格式本身提供了對(duì)地圖快速查詢和顯示的優(yōu)化，可提高路徑分析和計(jì)算速度，并可存儲(chǔ)高質(zhì)量的語音數(shù)據(jù)為用戶提供語音提示。SDAL格式的標(biāo)準(zhǔn)也是公開的。NavTech還為導(dǎo)航應(yīng)用提供了一套NAVTOOLS工具，可以較方便地進(jìn)行基于SDAL格式數(shù)據(jù)的導(dǎo)航應(yīng)用開發(fā)。NAVTOOLS提供了地圖顯示、車輛定位、路徑計(jì)算等多種功能。當(dāng)然，也可直接由SDAL開發(fā)導(dǎo)航應(yīng)用。NavTech2023/7/22KIWI與GDF關(guān)鍵的不同就在于PSF。GDF僅定義了數(shù)據(jù)的組織和表達(dá)，而其物理存儲(chǔ)只是簡(jiǎn)單地采用ASCII碼的單文件形式，并沒有對(duì)物理存儲(chǔ)模式進(jìn)行規(guī)范。相反，KIWI的核心就在于PSF。KIWI是一種直接與硬件和車載導(dǎo)航應(yīng)用相關(guān)的電子地圖格式，它的各種特性都是完全針對(duì)特定的導(dǎo)航應(yīng)用需求而設(shè)計(jì)的，不具有一般意義上的通用性。GDF則扮演了作為基礎(chǔ)數(shù)據(jù)交換格式的角色。GDF在導(dǎo)航應(yīng)用體系中起到的作用更加基礎(chǔ)一些，而KIWI的層次更高一些，它直接與硬件和系統(tǒng)要實(shí)現(xiàn)的功能相關(guān)。KIWIvs.GDF2023/7/22保證地理位置數(shù)據(jù)的精確性和實(shí)際地物信息的準(zhǔn)確性具備完備的地物屬性信息在保證精度和信息量的前提下盡量精簡(jiǎn)滿足嵌入式設(shè)備GUI的特殊需求導(dǎo)航用電子地圖技術(shù)要求2023/7/22各種格式比較1已有的GIS－T數(shù)據(jù)模型中大多以線形參照系統(tǒng)與動(dòng)態(tài)分段技術(shù)為理論基礎(chǔ)，比較適合與交通管理，但很難直接應(yīng)用于車輛導(dǎo)航系統(tǒng)。2以結(jié)點(diǎn)弧段為基礎(chǔ)的數(shù)據(jù)模型大多集中注重道路的拓?fù)浔磉_(dá)，比較適合于車輛導(dǎo)航系統(tǒng)中的某一部分的功能如路徑規(guī)劃，對(duì)車輛導(dǎo)航中的其它功能，如地圖匹配，路徑導(dǎo)引，地圖顯示等支持不夠。3國(guó)際上流行的數(shù)據(jù)格式GDF為導(dǎo)航數(shù)據(jù)交換格式，而kiwi和SDAL為物理存儲(chǔ)格式，且數(shù)據(jù)格式本身并不能代替數(shù)據(jù)模型，直接應(yīng)用于導(dǎo)航系統(tǒng)的開發(fā)，盡管其中體現(xiàn)了數(shù)據(jù)模型。2023/7/222基于功能的導(dǎo)航數(shù)據(jù)模型導(dǎo)航數(shù)據(jù)模型的主要特點(diǎn)和要求（與傳統(tǒng)的GIS相比）其信息內(nèi)容要求不同包括組成要素、空間和交通關(guān)系拓?fù)潢P(guān)系的描述不同注重道路拓?fù)洌鲆暺渌亻g的拓?fù)洳煌壤邤?shù)據(jù)的集成要求要求能將不同比例尺數(shù)據(jù)在一個(gè)數(shù)據(jù)庫中集成系統(tǒng)性能要求高，實(shí)時(shí)性強(qiáng)硬件性能差，數(shù)據(jù)量大2023/7/22導(dǎo)航數(shù)據(jù)的總體組織模型垂直方向上的數(shù)據(jù)組織2023/7/22水平方向的數(shù)據(jù)組織

2023/7/22道路數(shù)據(jù)模型顯示相關(guān)的道路數(shù)據(jù)2023/7/22顯示相關(guān)的道路數(shù)據(jù)多路段表路段/結(jié)點(diǎn)表結(jié)點(diǎn)附加屬性表2023/7/22顯示相關(guān)的道路數(shù)據(jù)道路數(shù)據(jù)對(duì)地圖匹配的支持2023/7/22規(guī)劃相關(guān)的道路數(shù)據(jù)結(jié)點(diǎn)表拓?fù)渎?lián)結(jié)表路段表2023/7/22拓?fù)溥B接表的組成規(guī)劃相關(guān)的道路數(shù)據(jù)與顯示相關(guān)的道路數(shù)據(jù)之間的連接通過路段ID實(shí)現(xiàn)結(jié)點(diǎn)關(guān)聯(lián)路段索引表路段通行表路段間花費(fèi)表2023/7/225.2組合定位技術(shù)GNSS+DR+MapMatching2023/7/22DR：航位推算(Dead-Reckoning)是一種常用的車輛導(dǎo)航定位技術(shù)，它是利用方向傳感器(角速度陀螺儀)和速度傳感器(里程表)來推算車輛的瞬時(shí)位置，即從一己知的坐標(biāo)位置開始，根據(jù)航行體(船只、飛機(jī)、陸地車輛等)在該點(diǎn)的航向、航速和航行時(shí)間，推算下一時(shí)刻坐標(biāo)位置的導(dǎo)航過程。1基本概念2023/7/22DR系統(tǒng)以地球表面的參考坐標(biāo)系的原點(diǎn)作為其推算車輛位置的起點(diǎn)，利用車載里程儀和航向傳感器的信息，實(shí)時(shí)確定車輛的位置，其基本推算方程為：這里，(x0,y0)是車輛t0時(shí)刻的初始位置，Si，分別是車輛從ti時(shí)刻的位置(xi,yi)到ti+1時(shí)刻的位置(xi+1,yi+1)的位移矢量的長(zhǎng)度和絕對(duì)航向。2航位推算原理

2023/7/22完全自主，既不發(fā)射信號(hào)，也不接收信號(hào)，不存在電磁波傳播問題，只需利用自身的測(cè)量元件的觀測(cè)量，推求位置、速度等導(dǎo)航政策性人為因素的影響;機(jī)動(dòng)靈活，無論是涵洞還是水下，只要載體(車、船、飛機(jī)、潛艇)能夠到達(dá)的地方就能導(dǎo)航定位。DR的優(yōu)點(diǎn)32023/7/22方向的累積誤差：

在DR計(jì)算公式中方向計(jì)算公式中，傳感器一般給出的是角速度信號(hào)ωi，在實(shí)際應(yīng)用中，由于陀螺儀等角速度傳感器的敏感度、精度、信號(hào)處理電路、A/D等引入的誤差及受到溫度等環(huán)境條件的影響，方向誤差將隨時(shí)間而積累，并無法自動(dòng)消除，最終使得方向完全錯(cuò)誤。距離的累積誤差：在DR計(jì)算中，距離一般通過車輪編碼器來測(cè)量，由于車輪有效直徑受到氣壓、載荷、氣溫、磨損而發(fā)生變化，距離誤差將隨距離延長(zhǎng)而積累，也無法自動(dòng)消除，最終使得定位不準(zhǔn)。DR的弱點(diǎn)42023/7/22

GPS(全球衛(wèi)星定位系統(tǒng))的定位和測(cè)速精度高,具有全天候、全球性且基本不受地域、時(shí)間限制,但當(dāng)車輛行駛在城市高樓區(qū)、林蔭、隧道、立交橋下等區(qū)域時(shí),常出現(xiàn)GPS衛(wèi)星信號(hào)被遮擋或多徑效應(yīng)問題。當(dāng)衛(wèi)星少于4顆,GPS接收機(jī)就無法正常定位,或者受多徑效應(yīng)的影響,導(dǎo)致定位精度很差。這是由GPS被動(dòng)定位的方式?jīng)Q定的。航位推算(DR)是一種常用自主式車輛導(dǎo)航技術(shù),其基本原理是利用方向和速度傳感器來推算車輛的位置。DR方法不能單獨(dú)、長(zhǎng)時(shí)間地使用,而常作為一種輔助導(dǎo)航技術(shù)得到應(yīng)用。GPS/DR組合的提出52023/7/22

將GPS定位系統(tǒng)與自主式DR系統(tǒng)組合形成的組合定位系統(tǒng)，能有效的綜合2種定位系統(tǒng)的優(yōu)點(diǎn)，獲得更高的定位精度及可靠性。

在GPS信號(hào)失鎖或受阻擋而沒有位置輸出時(shí)，系統(tǒng)則采用DR航位推算方式繼續(xù)定位；

而GPS能正常定位，車速大于一定數(shù)值時(shí)，則可以利用GPS推導(dǎo)得到的速度和航向信息校正里程計(jì)和陀螺，從而能夠保證車輛定位的連續(xù)性和高精度性。GPS/DR的優(yōu)點(diǎn)62023/7/22

切換式組合導(dǎo)航系統(tǒng)有兩種工作狀態(tài)，一種是以GPS數(shù)據(jù)作為系統(tǒng)的定位輸出，另一種以DR推算定位數(shù)據(jù)作為系統(tǒng)的定位輸出。系統(tǒng)具體工作于何種方式取決于GPS數(shù)據(jù)的有效性：當(dāng)GPS觀測(cè)衛(wèi)星數(shù)較多、衛(wèi)星幾何分布結(jié)構(gòu)較好(GDOP值較小)時(shí)工作于GPS方式，同時(shí)用GPS數(shù)據(jù)刷新DR系統(tǒng)的初始推算位置；一旦GPS數(shù)據(jù)失效或定位精度降低(GDOP值增大到預(yù)定門限)，則切換到DR定位方式。切換式組合的優(yōu)點(diǎn)是簡(jiǎn)單易行，系統(tǒng)承擔(dān)的計(jì)算量很小，可以解決在衛(wèi)星信號(hào)受遮擋后的短時(shí)間定位問題。但是用這種簡(jiǎn)單的切換方法并不能真正把GPS和DR系統(tǒng)的兩種定位數(shù)據(jù)融合在一起，也沒有充分利用其中的有效信息，因而不能完全發(fā)揮二者的優(yōu)點(diǎn)。GPS/DR算法-切換式72023/7/22

采用增強(qiáng)型卡爾曼濾波器（EKF）算法或其他類似功能算法對(duì)GPS定位數(shù)據(jù)和傳感器輸入進(jìn)行自動(dòng)加權(quán)平均,以精確計(jì)算下一點(diǎn)的位置。GPS與DR算法的加權(quán)權(quán)重由GPS信號(hào)質(zhì)量和DR信息的置信等級(jí)決定。GPS/DR-Kalman算法82023/7/225.3路徑規(guī)劃技術(shù)（最短路徑算法）最短路徑問題是圖論中研究的一個(gè)重要課題,它廣泛應(yīng)用于交通、網(wǎng)絡(luò)尋優(yōu)等領(lǐng)域。經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。它們?cè)诳臻g復(fù)雜度、時(shí)間復(fù)雜度、易實(shí)現(xiàn)性及應(yīng)用范圍等方面各具特色。2023/7/22算法分類按照起點(diǎn)、終點(diǎn)及路徑的數(shù)目和特征，最短路徑問題可分為：?jiǎn)卧醋疃搪窂?、所有?jié)點(diǎn)間最短路徑、K條最短路徑、指定必經(jīng)節(jié)點(diǎn)的最短路徑等；按照技術(shù)實(shí)現(xiàn)方式分為：組合技術(shù)和代數(shù)方法。組合技術(shù)主要指標(biāo)號(hào)算法可分為標(biāo)號(hào)設(shè)定(LabelSetting,簡(jiǎn)稱LS)和標(biāo)號(hào)改正(LabelCorrecting,簡(jiǎn)稱LC)兩大體系。代數(shù)方法通過運(yùn)籌學(xué)中的線性規(guī)劃形式化、所定義代數(shù)系統(tǒng)中的聯(lián)立線性方程集形式化和矩陣乘法等方法來解求最短路徑問題；按照搜索策略分為：廣度優(yōu)先搜索、深度優(yōu)先搜索和啟發(fā)式搜索。網(wǎng)絡(luò)遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷網(wǎng)絡(luò)遍歷路徑規(guī)劃算法-初始節(jié)點(diǎn)概念起點(diǎn)、終點(diǎn)中途點(diǎn)：中間途徑的點(diǎn)回避點(diǎn)：由于某種原因，如道路擁堵等不經(jīng)過的點(diǎn)路徑規(guī)劃算法-初始節(jié)點(diǎn)的處理路徑規(guī)劃算法-節(jié)點(diǎn)擴(kuò)展路徑規(guī)劃-單向搜索求解從V1到V8的最短路徑下求到的最短路：1）從出發(fā)，向走。首先，從到的距離為0，給

標(biāo)號(hào)（0）。畫第一個(gè)弧。（表明已標(biāo)號(hào)，或已走出）從出發(fā)，只有兩條路可走，其距離為2）①可能最短路為①給劃成粗線。③劃第二個(gè)弧。②

給標(biāo)號(hào)（4）。①②表明走出后走向的最短路目前看是，最優(yōu)距離是4?，F(xiàn)已考察完畢第二個(gè)圈內(nèi)的路，或者說，已完成的標(biāo)號(hào)。①②3）接著往下考察，有三條路可走：可選擇的最短路為①給劃成粗線。③劃第3個(gè)弧。②

給標(biāo)號(hào)（6）。③①②4）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第4個(gè)弧。②

給標(biāo)號(hào)（8）。①②③④5）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第5個(gè)弧。②

給標(biāo)號(hào)（9）。①②③④⑤6）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第6個(gè)弧。②

給標(biāo)號(hào)（13）。①②③④⑤⑥7）接著往下考察，有四條路可走：可選擇的最短路為①同時(shí)給劃成粗線。②分別給標(biāo)號(hào)（14）。最后，從逆尋粗線到，得最短路：長(zhǎng)度為15。單向搜索流程圖路徑規(guī)劃雙向搜索2023/7/22經(jīng)典算法經(jīng)典的最短路徑算法主要有兩種：Floyd算法和Dijkstra算法，分別由R.W.Floyd和E.W.Dijkstra提出。目前應(yīng)用的許多最短路徑算法都是根據(jù)實(shí)例特征對(duì)這兩種算法的優(yōu)化。Floyd算法適用于計(jì)算所有節(jié)點(diǎn)之間的最短路徑。Dijkstra算法則適用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。2023/7/22Floyd算法要求的解是一個(gè)矩陣Ｓ[N][N]，其中S[i][j]表示結(jié)點(diǎn)i到j(luò)的最短路徑，算法很像動(dòng)態(tài)規(guī)劃算法，甚至更簡(jiǎn)單些，不同的是這里規(guī)劃的是一個(gè)矩陣，而不是簡(jiǎn)單的數(shù)組。Floyd算法過程描述如下：１、首先Ｓ以邊集Ｍ初始化，得到所有的直接連通代價(jià)；２、依次考慮第k個(gè)結(jié)點(diǎn)，對(duì)于Ｓ中的每一個(gè)Ｓ[i][j]，判斷是否滿足：S[i][j]>S[i][k]+S[k][j]，如果滿足則用S[i][k]+S[k][j]代替Ｓ[i][j]，此為第k步；３、k循環(huán)取遍所有結(jié)點(diǎn)，算法結(jié)束時(shí)，Ｓ為最終解。2023/7/22Dijkstra算法把圖中所有節(jié)點(diǎn)分成OPEN和CLOSED兩組,CLOSED包括已確定最短路徑的節(jié)點(diǎn),OPEN包括尚未確定最短路徑的節(jié)點(diǎn),按最短路徑長(zhǎng)度遞增的順序逐個(gè)把OPEN的節(jié)點(diǎn)加入CLOSED中,直到從S點(diǎn)出發(fā)可以到達(dá)的所有節(jié)點(diǎn)都已包括在CLOSED中,且從S點(diǎn)到CLOSED各節(jié)點(diǎn)的最短路徑都不大于從S點(diǎn)到OPEN的任何節(jié)點(diǎn)的最短路徑長(zhǎng)度。另外,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)1個(gè)距離值(權(quán)值),CLOSED的節(jié)點(diǎn)對(duì)應(yīng)的距離值是從S點(diǎn)到此節(jié)點(diǎn)的最短路徑長(zhǎng)度,OPEN的節(jié)點(diǎn)對(duì)應(yīng)的距離值是從S點(diǎn)到此節(jié)點(diǎn)的只包括CLOSED的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑長(zhǎng)度。2023/7/22Dijkstra算法是應(yīng)用最為廣泛的最短路徑求解算法，但是它存在著一定的缺陷：（1）搜索的時(shí)候毫無方向性，導(dǎo)致搜索范圍很大；（2）臨時(shí)標(biāo)示節(jié)點(diǎn)都是無序排列的，這就使每次進(jìn)行搜索時(shí)都有可能要遍歷所有的臨時(shí)標(biāo)示節(jié)點(diǎn)，增加了搜索的代價(jià)。算法的時(shí)間復(fù)雜度為O(n2)。在實(shí)際網(wǎng)絡(luò)模型的節(jié)點(diǎn)數(shù)n較大情況下，算法的計(jì)算時(shí)間成倍甚至冪次增長(zhǎng)。由此可看出，在城市道路網(wǎng)節(jié)點(diǎn)數(shù)較多的情況下，該算法花費(fèi)時(shí)間長(zhǎng)，求解效率低，很難滿足實(shí)際的要求。在實(shí)際城市路網(wǎng)中，給出起點(diǎn)終點(diǎn)要求求出規(guī)劃路徑的時(shí)候，不僅需要考慮計(jì)算的精度，還需要考慮算法的效率。2023/7/22A*算法定義A*（A-Star)算法是一種啟發(fā)式搜索算法，是靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為：

f(n)=g(n)+h(n),

其中f(n)是節(jié)點(diǎn)n從初始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)，它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。2023/7/22啟發(fā)式搜索算法定義及優(yōu)缺點(diǎn)定義：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。優(yōu)點(diǎn)：與盲目搜索相比，可大量節(jié)省時(shí)間。根據(jù)不同的最短路徑需求，可以設(shè)置不同的啟發(fā)信息（如長(zhǎng)度最短、時(shí)間最短、花費(fèi)最少等）。缺點(diǎn)：最大缺點(diǎn)是不能保證成功；其次其執(zhí)行效率只能借助試驗(yàn)來評(píng)估。2023/7/22算法詳解主要搜索過程：創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。

取OPEN表中f最小的節(jié)點(diǎn)n，將其放入CLOSE中，取n節(jié)點(diǎn)的子節(jié)點(diǎn)X,計(jì)算X的估價(jià)值。2023/7/22搜索過程While(OPEN!=NULL)

{

從OPEN表中取估價(jià)值f最小的節(jié)點(diǎn)n;

if(n節(jié)點(diǎn)==目標(biāo)節(jié)點(diǎn))break;//搜索成功，退出循環(huán)

else

{

if(XinOPEN)比較兩個(gè)X的估價(jià)值f;//注意是同一個(gè)節(jié)點(diǎn)的兩個(gè)不同路徑的估價(jià)值

if(X的估價(jià)值小于OPEN表的估價(jià)值)

更新OPEN表中的估價(jià)值;//取最小路徑的估價(jià)值;

if(XinCLOSE)比較兩個(gè)X的估價(jià)值//注意是同一個(gè)節(jié)點(diǎn)的兩個(gè)不同路徑的估價(jià)值

if(X的估價(jià)值小于CLOSE表的估價(jià)值)

更新CLOSE表中的估價(jià)值;把X節(jié)點(diǎn)放入OPEN;//取最小路徑的估價(jià)值

if(Xnotinboth)

求X的估價(jià)值;

并將X插入OPEN表中;//還沒有排序

}

將n節(jié)點(diǎn)插入CLOSE表中;

按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;//實(shí)際上是比較OPEN表內(nèi)節(jié)點(diǎn)的f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。

}2023/7/22搜索過程解析由上述搜索過程可以看出，A*算法的特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。汗纼r(jià)值h(n)<=n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解；如果估價(jià)值h(n)>n到目標(biāo)節(jié)點(diǎn)的距離>實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。

估價(jià)值與實(shí)際值越接近，估價(jià)函數(shù)取得就越好。

2023/7/22實(shí)例例如對(duì)于幾何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價(jià)值（啟發(fā)信息），即h(n)=sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；f(n)=g(n)+h(n)；這樣估價(jià)函數(shù)f在g值一定的情況下，會(huì)或多或少的受估價(jià)值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對(duì)就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。明顯優(yōu)于Dijkstra算法的毫無方向的向四周搜索。2023/7/22如下圖所示搜索起點(diǎn)為S，終點(diǎn)為E。C和B分別為起點(diǎn)連接的兩個(gè)節(jié)點(diǎn)，計(jì)算C和B的估價(jià)值f時(shí)，它們的估計(jì)代價(jià)分別等于LBE和LCE，C到E的距離明顯大于B到E的距離，從起點(diǎn)到C和B的實(shí)際代價(jià)大約相等，因此f(C)大于f(B)，下次選擇最小f值的節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)B被選擇的可能性要大于C，依次類推，由于估計(jì)代價(jià)h的存在，搜索會(huì)趨向于終點(diǎn)方向進(jìn)行，從而加速了效率，節(jié)省了大量時(shí)間。2023/7/22用A*算法的情況，計(jì)算的點(diǎn)數(shù)從起始點(diǎn)逐漸向目標(biāo)點(diǎn)方向擴(kuò)展，計(jì)算的節(jié)點(diǎn)數(shù)量明顯比Dijkstra少得多，效率很高，且能得到最優(yōu)解。（如下圖：1794為起點(diǎn)，2689為終點(diǎn)，紅