智能運(yùn)輸系統(tǒng)講義(先進(jìn)的旅游者信息系統(tǒng))

1、智能(zh nn)運(yùn)輸系統(tǒng)（ITS）共九十六頁(yè)先進(jìn)的旅行者信息系統(tǒng)（ATIS）1 了解ATIS的主要內(nèi)容 2 了解車載路徑誘導(dǎo)(yudo)系統(tǒng)和車載導(dǎo)航器的基本結(jié)構(gòu) 3 了解車載路徑誘導(dǎo)系統(tǒng)的工作過程 4 了解路徑規(guī)劃中的主要研究問題 5 了解停車場(chǎng)誘導(dǎo)系統(tǒng)的基本結(jié)構(gòu) 1 先進(jìn)的旅行者信息系統(tǒng)與以往的交通信息系統(tǒng)相比，有哪些技術(shù)進(jìn)步 2 車載導(dǎo)航器的一般結(jié)構(gòu) 3 車輛定位技術(shù)如何在車載導(dǎo)航中綜合應(yīng)用 對(duì)于交通規(guī)劃與管理專業(yè)的學(xué)生，ATIS中的定位技術(shù)、顯示技術(shù)、人工智能中的搜索技術(shù)是難點(diǎn)，請(qǐng)參考第二大部分有關(guān)章節(jié)。 共九十六頁(yè)4.2 先進(jìn)的旅行者信息系統(tǒng)（ATIS） 4.2.1 先進(jìn)的旅行者信

2、息系統(tǒng)概述（視頻：ATIS 參考美國(guó)“TransGuide”和韓國(guó)“ITS在韓國(guó)”） 先進(jìn)的旅行者信息系統(tǒng)ATIS（Advanced Traveler Information Systems）是運(yùn)用(ynyng)各種先進(jìn)的通信、信息技術(shù)向利用私家車、公交車或同時(shí)利用這兩種車輛的旅行者提供為到達(dá)所希望的目的地所需要的各種信息的系統(tǒng)。其中很多信息是在車中獲得，也有許多為旅行前做旅行計(jì)劃所需要的信息是在家中、辦公室、公用電話亭等地獲得，甚至還可隨時(shí)隨地利用便攜式計(jì)算機(jī)、手掌機(jī)得到。多模式的旅行信息更受歡迎，因?yàn)槁眯姓呖筛鶕?jù)最新的信息選擇他們的旅行方式和時(shí)間。ATMS也提供信息，如可變信息標(biāo)志VMS、

3、公路咨詢廣播等，但ATIS的信息更加復(fù)雜，要使公眾能很方便地獲得它需要克服更多的困難。ATIS可以利用ATMS提供的信息，但它自身也要發(fā)展同時(shí)提供旅行前和旅行途中信息的方法。 共九十六頁(yè)手掌機(jī)共九十六頁(yè)VMS提供(tgng)信息共九十六頁(yè) 公共信息亭共九十六頁(yè)ATIS除提供傳統(tǒng)意義的交通運(yùn)輸信息的功能外，它的主要功能子系統(tǒng)還有： 車載路徑誘導(dǎo)系統(tǒng) 停車場(chǎng)可利用性誘導(dǎo)系統(tǒng) 數(shù)字地圖數(shù)據(jù)庫(kù) 車載路徑誘導(dǎo)是ATIS的最重要的功能之一，它能幫助駕駛員避開擁擠和事故、避免因不熟悉城市交通環(huán)境而“迷路”、也有利于增加安全。不僅是靜態(tài)路徑誘導(dǎo)從路側(cè)發(fā)展到了車上，而且動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)也已經(jīng)有了很大的進(jìn)展。局域

4、決策的動(dòng)態(tài)車載路徑誘導(dǎo)系統(tǒng)已經(jīng)被市場(chǎng)廣泛接受。一些國(guó)家也正在研究中心決策的動(dòng)態(tài)車載路徑誘導(dǎo)系統(tǒng)。日本關(guān)于車載路徑誘導(dǎo)系統(tǒng)的市場(chǎng)增長(zhǎng)速度在世界上是最快的。如1996年，日本車載路徑誘導(dǎo)系統(tǒng)的市場(chǎng)滲透是180萬套，美國(guó)是1萬套，而整個(gè)(zhngg)歐洲是2萬套。共九十六頁(yè)停車場(chǎng)可利用性誘導(dǎo)是ATIS的另一個(gè)重要功能。在沒有停車場(chǎng)可利用性誘導(dǎo)系統(tǒng)的一些大城市的中心區(qū)，為了尋找一個(gè)停車空位，駕駛員往往要花費(fèi)半個(gè)小時(shí)，他們?yōu)閷ふ彝＼噲?chǎng)的行車?yán)锍痰扔谠诔鞘械目傂熊嚴(yán)锍痰乃姆种弧Ｒ蚨＼噲?chǎng)可利用性誘導(dǎo)系統(tǒng)可大大減少這種無謂的交通量和隨之產(chǎn)生的環(huán)境污染。世界第一個(gè)停車場(chǎng)可利用性誘導(dǎo)系統(tǒng)是在德國(guó)的Aachen

5、引入的。至1990年世界上就有50個(gè)這種系統(tǒng)投入運(yùn)營(yíng)。 數(shù)字地圖數(shù)據(jù)庫(kù)是許多ATIS的關(guān)鍵分量。但支持路徑誘導(dǎo)的電子數(shù)據(jù)地圖太昂貴，所以尚不能在所有的城市應(yīng)用。但是到1997年底，發(fā)達(dá)國(guó)家的主要城市使用的路徑誘導(dǎo)系統(tǒng)就都能利用電子數(shù)據(jù)地圖了。數(shù)字地圖數(shù)據(jù)庫(kù)工作開展得最好的是日本。日本數(shù)字道路地圖協(xié)會(huì)（JDRMA）于1988年成立。它建立了數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)并開發(fā)了數(shù)字道路地圖（DRM）數(shù)據(jù)庫(kù)。JDRMA最初(zuch)使用1：50,000的地圖，后來改用1：25,000的地圖，這樣可提供更詳細(xì)、更精確的地理信息。到1995年3月，基于1：25,000的DRM數(shù)據(jù)庫(kù)覆蓋了整個(gè)日本。共九十六頁(yè)4.2.2旅

6、行者信息系統(tǒng)的技術(shù)進(jìn)步 （1）信息發(fā)布手段的視覺化 先進(jìn)的旅行者信息系統(tǒng)除了利用無線電廣播、電話咨詢等技術(shù)發(fā)布語(yǔ)音交通信息外，還普遍運(yùn)用Internet網(wǎng)頁(yè)、交互電視、車載單元顯示屏和各種可變信息標(biāo)志來發(fā)布信息。 例如，美國(guó)得克薩斯州休斯敦市的Houston Transtar項(xiàng)目，1996年已有30,000輛汽車與公交車裝上了帶信用卡 那樣大的異頻雷達(dá)收發(fā)器的車輛自動(dòng)識(shí)別（AVI）裝置。當(dāng)這種車輛經(jīng)過AVI檢測(cè)器時(shí)，它的信息就送至交通控制中心（TMC），中心的計(jì)算機(jī)計(jì)算出車輛的旅行時(shí)間和速度，并在彩色地圖上以不同的顏色(yns)表示不同的道路交通條件，然后Transtar將此信息以多種方式傳輸

7、給用戶，這些方式包括可變信息板、Internet網(wǎng)頁(yè)及筆記本電腦。 共九十六頁(yè)共九十六頁(yè)（2）無線電廣播技術(shù)的革新 將交通信息傳輸給駕駛員的最一般(ybn)的方法是使用無線電廣播。但是，隨著可供利用的信息量的大幅度增加和對(duì)信息的實(shí)時(shí)性要求的提高，以前的無線電廣播技術(shù)已不能滿足需要。因而先進(jìn)的旅行者信息系統(tǒng)中的無線電廣播技術(shù)有了很大的發(fā)展。如歐洲現(xiàn)在廣泛使用的一種交通信息傳輸方式是RDS-TMC（無線電數(shù)據(jù)系統(tǒng)交通消息頻道），日本使用的是先進(jìn)的路側(cè)廣播技術(shù)。共九十六頁(yè)（3）雙向通信技術(shù)的廣泛應(yīng)用 傳統(tǒng)的旅行者信息系統(tǒng)和ATMS中的通信方式主要是由交通管理/信息中心對(duì)旅行者的單向通信，如交通管理/

8、信息中心利用廣播、電視、可變信息標(biāo)志等向用戶發(fā)布信息，沒有信息反饋，所提供的信息沒有個(gè)性。而在先進(jìn)的旅行者信息系統(tǒng)中，越來越多地采用雙向通信方式， 不僅是交通管理/信息中心向旅行者發(fā)布信息，而且交通管理/信息中心也能從旅行者那里獲得(hud)他的旅行計(jì)劃信息和運(yùn)行實(shí)況信息，旅行者不僅能獲得(hud)面向大眾的旅行信息，而且能獲得(hud)他個(gè)人需要的特殊信息并提出特殊的服務(wù)請(qǐng)求。全球移動(dòng)通信系統(tǒng)GSM、無線尋呼系統(tǒng)、紅外線信標(biāo)、路邊電話就是ATIS中廣泛應(yīng)用的新通信技術(shù)的代表。共九十六頁(yè)（4）信息的實(shí)時(shí)性不斷提高 隨著信息收集、處理、傳輸、發(fā)布技術(shù)的進(jìn)步，ATIS提供的信息的實(shí)時(shí)程度越來越高。

9、例如： 美國(guó)休斯敦市的道路交通報(bào)告網(wǎng)頁(yè)每1分鐘更新一次。 日本東京都高速公路交通控制系統(tǒng)（MEPC）提供的高速公路交通信息每1分鐘更新一次。 1992年英國(guó)南安普敦的ROMANSE項(xiàng)目使用VMS為該市13個(gè)主要停車場(chǎng)顯示(xinsh)空閑的車位，每一個(gè)停車場(chǎng)的8個(gè)停車信息牌豎立在進(jìn)入該市中心的各路口處，每2分鐘更新一次信息。 1993年?yáng)|京都新宿區(qū)建立的日本的第一個(gè)停車引導(dǎo)和信息系統(tǒng)PGIS為29個(gè)停車場(chǎng)提供可利用性引導(dǎo)。通過電話獲得的或顯示在電子告示牌上的引導(dǎo)信息每2分鐘更新一次。 日本的動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)每5分鐘更新一次路徑誘導(dǎo)信息。 共九十六頁(yè)（5）信息的復(fù)雜程度日益增強(qiáng) 由于地理信息系統(tǒng)

10、GIS、全球定位系統(tǒng)GPS和移動(dòng)通信技術(shù)等的應(yīng)用，ATIS所能提供的信息越來越復(fù)雜，其對(duì)于整個(gè)交通系統(tǒng)所產(chǎn)生的影響也就越來越大。如數(shù)字地圖數(shù)據(jù)庫(kù)使ATIS提供的信息是前所未有的豐富、清晰和準(zhǔn)確，具有(jyu)了廣泛的可利用性；停車場(chǎng)不僅是停車的場(chǎng)所，也成為搭乘者上車的場(chǎng)所，有效地輔助實(shí)施了交通需求管理；路徑誘導(dǎo)系統(tǒng)的路徑選擇不再是僅僅依據(jù)于路網(wǎng)結(jié)構(gòu)的靜態(tài)數(shù)據(jù)和交通流的歷史數(shù)據(jù)，而是越來越多地依據(jù)路網(wǎng)最新的和預(yù)測(cè)的動(dòng)態(tài)數(shù)據(jù)，使路網(wǎng)交通流的整體優(yōu)化成為可能。 共九十六頁(yè)2.路徑誘導(dǎo)系統(tǒng)的功能 系統(tǒng)的導(dǎo)航功能是根據(jù)道路交通法規(guī)、汽車結(jié)構(gòu)、用戶要求建立(jinl)，由導(dǎo)航軟件和電子地圖數(shù)據(jù)庫(kù)來實(shí)現(xiàn)。（

11、1） 對(duì)目的地進(jìn)行最佳路線的檢索 該系統(tǒng)可以直接輸入地名、經(jīng)緯度、電話號(hào)碼進(jìn)行路線檢索，能快捷提供13條到目的地的最佳路線以供選擇，還能獲取自身位置、目的地坐標(biāo)、行駛距離、速度、時(shí)間和前進(jìn)方向等。（2） 具有瞬時(shí)再檢索功能 有道路施工、堵塞、走錯(cuò)路等情況，推薦的路線行不通時(shí)，具有再檢索功能。舍去堵塞、錯(cuò)路、施工路段，提供新的路線時(shí)，要求至少有3條路線可供選擇，并用不同顏色在顯示器上標(biāo)出。所以要求CPU運(yùn)算速度和精度特別高，CPU應(yīng)選高速32bit的。共九十六頁(yè)（3） 提供豐富的菜單和記錄功能 為與日本導(dǎo)航軟件的S規(guī)則相對(duì)應(yīng)，系統(tǒng)應(yīng)能記錄1000萬個(gè)住所地址，1100萬個(gè)電話號(hào)碼，25cm比例尺

12、相當(dāng)于1/3000的街道圖并用11+1層顯示，還有十字路口交叉點(diǎn)全畫面擴(kuò)大顯示圖，并與VICS實(shí)時(shí)對(duì)應(yīng)。（4） 在適當(dāng)時(shí)間提供實(shí)時(shí)語(yǔ)音提示 凡行駛在交叉路口前，一般道路在300700m之前，高速公路在2000m、1000m、500m之前要分別向駕駛員說明十字路口、交叉點(diǎn)的名稱和更改的方向，以及高速公路的分支點(diǎn)、進(jìn)出口、單行線等引導(dǎo)指示，同時(shí)具備中英文兩種語(yǔ)言，以供切換。（5） 擴(kuò)大的十字路口標(biāo)志顯示功能 行駛在交叉路口、十字路口之前300 m處，高速公路進(jìn)出口之前300m都要自動(dòng)開窗顯示擴(kuò)大了的十字路口附近全面圖，并指出十字路口的名稱，拐彎后的道路名稱和方向。（6） 擴(kuò)展功能 系統(tǒng)應(yīng)具備有多種

13、接口，以便與交通管理部門(bmn)、郵電部門(bmn)、建筑部門(bmn)的VICS、ATIS、IIS聯(lián)網(wǎng)。共九十六頁(yè)共九十六頁(yè)4.2.3 車載路徑誘導(dǎo)系統(tǒng) 從20世紀(jì)60年代美國(guó)的ERGS開始直到今天，車載路徑誘導(dǎo)系統(tǒng)一直是智能運(yùn)輸系統(tǒng)最具代表性的一個(gè)功能子系統(tǒng)?？梢哉f，車載路徑誘導(dǎo)系統(tǒng)從低級(jí)向高級(jí)的發(fā)展過程也集中地反映了ITS的智能化程度逐步提高的過程。 1. 路徑誘導(dǎo)系統(tǒng)的分類 路徑誘導(dǎo)系統(tǒng)（Route Guidance Systems）也可以稱為車輛導(dǎo)航系統(tǒng)（Vehicle Navigation Systems），其主要功能是輔助駕駛員為到達(dá)目的地而選擇路徑和沿既定路徑行駛，必要時(shí)（如

14、遇道路條件發(fā)生變化時(shí)）幫助駕駛員重新選擇路徑。這個(gè)過程也稱為“路徑計(jì)劃導(dǎo)航(dohng)路徑再計(jì)劃”或“路徑選擇路徑引導(dǎo)路徑再選擇”。根據(jù)路徑計(jì)劃和導(dǎo)航功能實(shí)現(xiàn)方法的不同，路徑誘導(dǎo)系統(tǒng)有不同的分類方法。共九十六頁(yè)按導(dǎo)航方式的不同，路徑誘導(dǎo)系統(tǒng)可劃分為： 路側(cè)路徑誘導(dǎo)系統(tǒng) 導(dǎo)航設(shè)施為設(shè)置于路側(cè)的各種道路標(biāo)志，導(dǎo)航的功能由駕駛員正確識(shí)別和理解這些標(biāo)志，按交通規(guī)則行駛實(shí)現(xiàn)。 車載路徑誘導(dǎo)系統(tǒng) 導(dǎo)航設(shè)施為設(shè)置在車內(nèi)的車載導(dǎo)航器，導(dǎo)航的功能由導(dǎo)航器的定位計(jì)算和給出聲音提示或屏幕顯示，一步步引導(dǎo)駕駛員實(shí)現(xiàn)。在ITS出現(xiàn)之前，沒有車載路徑誘導(dǎo)系統(tǒng)。 路徑誘導(dǎo)系統(tǒng)又可按路徑計(jì)劃所依據(jù)(yj)的信息的性質(zhì)劃分為

15、： 靜態(tài)路徑誘導(dǎo)系統(tǒng) 路徑計(jì)劃所依據(jù)的信息為靜態(tài)的路網(wǎng)信息，如預(yù)先儲(chǔ)存在車載導(dǎo)航器的CD-ROM中的路網(wǎng)結(jié)構(gòu)、路段旅行時(shí)間甚至最短路徑樹。共九十六頁(yè)動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng) 路徑計(jì)劃所依據(jù)的信息有實(shí)時(shí)的動(dòng)態(tài)路網(wǎng)信息和環(huán)境信息，如當(dāng)前和短期預(yù)測(cè)的路段旅行時(shí)間、交通管制信息、道路氣象信息等。 另外，按照路徑計(jì)劃產(chǎn)生的地點(diǎn)，車載路徑誘導(dǎo)系統(tǒng)還可劃分為： 自治型路徑誘導(dǎo)系統(tǒng)（或局部決策的路徑誘導(dǎo)系統(tǒng)） 路徑計(jì)劃由車載計(jì)算機(jī)系統(tǒng)根據(jù)車內(nèi)裝載數(shù)據(jù)庫(kù)的數(shù)據(jù)和車載軟件計(jì)算產(chǎn)生。車載數(shù)據(jù)庫(kù)的路段行駛時(shí)間等信息可以通過與道路系統(tǒng)的雙向通信得以更新。 中心型路徑誘導(dǎo)系統(tǒng)（或中心決策的路徑誘導(dǎo)系統(tǒng)） 路徑計(jì)劃由交通控制中心的

16、計(jì)算機(jī)系統(tǒng)計(jì)算產(chǎn)生。中心的計(jì)算機(jī)系統(tǒng)根據(jù)實(shí)際路況和交通條件為每一特定的車輛選擇最優(yōu)路徑，并將選擇結(jié)果(ji gu)通過路側(cè)通信裝置傳送給車輛。共九十六頁(yè)完全利用車載導(dǎo)航器中固有的信息決定路徑的自治型路徑誘導(dǎo)系統(tǒng)是靜態(tài)路徑誘導(dǎo)系統(tǒng)，同時(shí)還利用接收到的道路實(shí)時(shí)信息決定路徑的自治型路徑誘導(dǎo)系統(tǒng)是動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)。 中心決策的路徑誘導(dǎo)系統(tǒng)是最理想的路徑誘導(dǎo)系統(tǒng)，從理論上說，只有它才能優(yōu)化交通流在整個(gè)路網(wǎng)上的分配。但是，這樣(zhyng)的中心決策的路徑誘導(dǎo)系統(tǒng)需要很大的投入，技術(shù)難度也很大。然而，歐洲的一些中心決策的路徑誘導(dǎo)系統(tǒng)不僅車載設(shè)備簡(jiǎn)單、廉價(jià)，而且路側(cè)通信基礎(chǔ)設(shè)施也成本很低，其誘導(dǎo)效果并不比自

17、治型的路徑誘導(dǎo)系統(tǒng)來得好。所以，為了改進(jìn)誘導(dǎo)效果，歐洲引進(jìn)了雙制式路徑誘導(dǎo)系統(tǒng)；為了降低系統(tǒng)成本，日本引進(jìn)了混合式路徑誘導(dǎo)系統(tǒng)。 關(guān)于各類路徑誘導(dǎo)系統(tǒng)，我們可以給出下面幾個(gè)例子： 美國(guó)的“先進(jìn)的駕駛員咨詢與車輛導(dǎo)航概念”ADVANCE（Advance Driver and Vehicle Advisory Navigation Concept）和“旅行技術(shù)”TRAVTEK（Travel Technology）是兩個(gè)典型的自治型路徑誘導(dǎo)系統(tǒng)項(xiàng)目。共九十六頁(yè) 德國(guó)的Ali-Scout系統(tǒng)是一種典型的較簡(jiǎn)單的中心(zhngxn)型路徑誘導(dǎo)系統(tǒng)。 德國(guó)“斯圖加特區(qū)域性交通運(yùn)營(yíng)管理”STORM項(xiàng)目以實(shí)時(shí)

18、交通數(shù)據(jù)來發(fā)送雙制式路徑誘導(dǎo)DMRG（Dual Mode Route Guidance）。 日本的車載路徑誘導(dǎo)系統(tǒng)處于世界領(lǐng)先地位。日本的DRGS采用局部決策的路徑誘導(dǎo)和中心決策的路徑誘導(dǎo)相結(jié)合的混合式路徑誘導(dǎo)策略。 車載導(dǎo)航系統(tǒng)是由GPS導(dǎo)航、自律導(dǎo)航、智能導(dǎo)航地圖匹配器、微處理器（MPU）或數(shù)字信息處理器（DSP）、車速傳感器、陀螺傳感器、CD-ROM驅(qū)動(dòng)器或DVD-ROM驅(qū)動(dòng)器、TFTLCD顯示器以及電子地圖數(shù)據(jù)庫(kù)相應(yīng)的軟件等組成。 共九十六頁(yè)共九十六頁(yè)共九十六頁(yè)車載導(dǎo)航系統(tǒng)一般結(jié)構(gòu) 由GPS導(dǎo)航和自律導(dǎo)航（包括車速傳感器和陀螺傳感器）所測(cè)到的汽車坐標(biāo)位置數(shù)據(jù)、前進(jìn)的方向與實(shí)際行駛的路線

19、軌跡在電子地圖上都存在一定誤差，為了修 正誤差，須采用地圖(dt)匹配技術(shù)。右圖表示地圖(dt)匹配器如何修正路線。(動(dòng)畫：地圖匹配）共九十六頁(yè)共九十六頁(yè)2.路徑誘導(dǎo)系統(tǒng)的功能 系統(tǒng)的導(dǎo)航功能是根據(jù)道路交通法規(guī)、汽車結(jié)構(gòu)、用戶要求建立，由導(dǎo)航軟件和電子地圖數(shù)據(jù)庫(kù)來實(shí)現(xiàn)。（1） 對(duì)目的地進(jìn)行最佳路線的檢索 該系統(tǒng)可以直接輸入地名、經(jīng)緯度、電話號(hào)碼進(jìn)行路線檢索，能快捷提供13條到目的地的最佳路線以供選擇，還能獲取自身位置、目的地坐標(biāo)、行駛距離、速度、時(shí)間和前進(jìn)方向等。（2） 具有瞬時(shí)再檢索功能 有道路施工、堵塞、走錯(cuò)路等情況，推薦的路線行不通時(shí)，具有再檢索功能。舍去堵塞、錯(cuò)路、施工路段，提供新的路

20、線時(shí)，要求至少有3條路線可供選擇，并用(bn yn)不同顏色在顯示器上標(biāo)出。所以要求CPU運(yùn)算速度和精度特別高，CPU應(yīng)選高速32bit的。共九十六頁(yè)（3） 提供豐富的菜單和記錄功能 為與日本導(dǎo)航軟件的S規(guī)則相對(duì)應(yīng)，系統(tǒng)應(yīng)能記錄1000萬個(gè)住所地址，1100萬個(gè)電話號(hào)碼，25cm比例尺相當(dāng)于1/3000的街道圖并用11+1層顯示，還有十字路口交叉點(diǎn)全畫面擴(kuò)大顯示圖，并與VICS實(shí)時(shí)對(duì)應(yīng)。（4） 在適當(dāng)時(shí)間提供實(shí)時(shí)語(yǔ)音提示(tsh) 凡行駛在交叉路口前，一般道路在300700m之前，高速公路在2000m、1000m、500m之前要分別向駕駛員說明十字路口、交叉點(diǎn)的名稱和更改的方向，以及高速公路的

21、分支點(diǎn)、進(jìn)出口、單行線等引導(dǎo)指示，同時(shí)具備中英文兩種語(yǔ)言，以供切換。（5） 擴(kuò)大的十字路口標(biāo)志顯示功能 行駛在交叉路口、十字路口之前300 m處，高速公路進(jìn)出口之前300m都要自動(dòng)開窗顯示擴(kuò)大了的十字路口附近全面圖，并指出十字路口的名稱，拐彎后的道路名稱和方向。（6） 擴(kuò)展功能 系統(tǒng)應(yīng)具備有多種接口，以便與交通管理部門、郵電部門、建筑部門的VICS、ATIS、IIS聯(lián)網(wǎng)。共九十六頁(yè)共九十六頁(yè)3. 路徑誘導(dǎo)系統(tǒng)的工作過程（1）路徑計(jì)劃過程 完成路徑計(jì)劃有六個(gè)處理子過程： 計(jì)算車輛行駛路徑 提供車輛路徑計(jì)算數(shù)據(jù) 提供其它地區(qū)的路段數(shù)據(jù) 更新車輛路徑選擇地圖數(shù)據(jù) 提供與信息提供裝置操作員的接口(ji

22、 ku) 計(jì)算用于誘導(dǎo)的車輛探測(cè)數(shù)據(jù)共九十六頁(yè)車載路徑誘導(dǎo)系統(tǒng)的路徑計(jì)劃參數(shù)由駕駛員在子過程輸入和由信息提供裝置操作員在子過程設(shè)置，道路和高速公路幾何數(shù)據(jù)由地圖升級(jí)供應(yīng)商通過子過程提供，交通數(shù)據(jù)在子過程和子過程提供。當(dāng)駕駛員需要路徑誘導(dǎo)時(shí)，他首先會(huì)輸入他所要到達(dá)的目的地，并依據(jù)個(gè)人偏好給出路徑的優(yōu)化目標(biāo)和約束因素。同時(shí)，信息提供裝置操作員也會(huì)根據(jù)當(dāng)前道路條件設(shè)置一些路徑選擇參數(shù)。例如，過程會(huì)依據(jù)駕駛員的要求計(jì)算出一條城市街道而忽略一條城市快速道；使用約束條件可使選擇的路徑包括一條特定的小街道等。這樣，將偏好參數(shù)置于路徑需求(xqi)數(shù)據(jù)的頂層，就可以按駕駛員需求(xqi)計(jì)算出一條使用優(yōu)先給定

23、的某種類型道路或方式的路徑。共九十六頁(yè)（2）路徑提供過程 為駕駛員提供實(shí)時(shí)(sh sh)路徑誘導(dǎo)信息的過程分為如下幾個(gè)子過程： 提供車輛誘導(dǎo) 處理車輛定位數(shù)據(jù) 提供駕駛員誘導(dǎo)工作接口 更新車輛導(dǎo)航地圖數(shù)據(jù)庫(kù) 駕駛員的誘導(dǎo)需求被子過程接收并發(fā)送到子過程去完成。依靠所選擇的（或可行的）誘導(dǎo)方式，這些需求將與一個(gè)中心設(shè)備（動(dòng)態(tài)誘導(dǎo)）相聯(lián)系，或使用子過程所支持的導(dǎo)航圖存儲(chǔ)信息去提供所需的誘導(dǎo)。當(dāng)駕駛員提供確切的信息時(shí)，即子過程已有一條路經(jīng)，并準(zhǔn)備開始引導(dǎo)時(shí)，這才將所有應(yīng)發(fā)送給駕駛員的誘導(dǎo)信息都發(fā)送到子過程，并以一種不會(huì)削弱駕駛員控制車輛能力的形式提供給駕駛員。 共九十六頁(yè) 當(dāng)通過(tnggu)子過程收

24、到駕駛員的需求時(shí)，導(dǎo)航圖中存取的信息將由子過程更新。更新的完成依賴于支付活動(dòng)的成功，該支付活動(dòng)由子過程發(fā)送到高級(jí)支付收集設(shè)備。子過程提供車輛定位數(shù)據(jù)，以備子過程和其他設(shè)備以及智能運(yùn)輸系統(tǒng)功能使用。 可行的車輛旅行計(jì)劃，要比執(zhí)行時(shí)間早一些，例如，提前5分鐘，以免誘導(dǎo)信息不能及時(shí)地被子過程提供，或者不能被簡(jiǎn)單的路徑數(shù)據(jù)所替換。 共九十六頁(yè)4. 動(dòng)態(tài)交通分配理論概述 動(dòng)態(tài)路徑(ljng)誘導(dǎo)的理論研究是智能運(yùn)輸系統(tǒng)理論研究的最重要領(lǐng)域之一。其核心內(nèi)容是實(shí)時(shí)動(dòng)態(tài)交通分配理論。動(dòng)態(tài)交通分配（Dynamic Traffic Assignment）是指以時(shí)時(shí)刻刻變動(dòng)的交通需求為對(duì)象的交通量分配。實(shí)時(shí)動(dòng)態(tài)交通

25、分配則是基于路網(wǎng)中的一個(gè)活動(dòng)著的交通流，預(yù)測(cè)其短期（如5分鐘）內(nèi)的交通需求，進(jìn)行交通量分配。顯然，實(shí)時(shí)動(dòng)態(tài)交通分配理論是動(dòng)態(tài)路徑誘導(dǎo)的理論基礎(chǔ)。 動(dòng)態(tài)交通分配理論已有20多年的發(fā)展歷史。其研究的方法主要有：l 計(jì)算機(jī)模擬方法l 數(shù)學(xué)規(guī)劃建模方法 l 最優(yōu)控制理論建模方法 l 變分不等式建模方法 等4種，所研究的問題主要有：共九十六頁(yè)出行時(shí)間選擇，即每個(gè)時(shí)段出行率的研究 l 出行路徑選擇，即對(duì)于如何將預(yù)先給定的隨時(shí)間變化的OD交通量分配到路網(wǎng)上的研究 l 同時(shí)決定出行時(shí)間和出行路徑的選擇 等3類。在綜合考慮出行時(shí)間和出行路徑的選擇時(shí)，若交通量分配對(duì)象是實(shí)際出行行為(xngwi)發(fā)生的路網(wǎng)，時(shí)間段

26、分割得足夠細(xì)密，路徑選擇依據(jù)的參數(shù)來自當(dāng)前路網(wǎng)和當(dāng)前的出行需求，則這一交通量分配就是實(shí)時(shí)動(dòng)態(tài)交通分配。 動(dòng)態(tài)交通分配模型，從出行者路徑選擇行為的假定看，可分為：l 動(dòng)態(tài)用戶最優(yōu)模型 l 動(dòng)態(tài)系統(tǒng)最優(yōu)模型 共九十六頁(yè)動(dòng)態(tài)用戶最優(yōu)是要使用戶個(gè)人“費(fèi)用”最小，而根據(jù)個(gè)人“費(fèi)用”定義的不同，又有兩類用戶最優(yōu)模型： 預(yù)測(cè)型用戶最優(yōu) 反應(yīng)型用戶最優(yōu) 實(shí)際上，當(dāng)交通網(wǎng)絡(luò)中的交通條件是每日變化不大、可以預(yù)測(cè)的，而出行者又了解這些條件時(shí)，用戶可以根據(jù)未來的交通條件來估計(jì)出行費(fèi)用，選擇出行路徑；當(dāng)交通網(wǎng)絡(luò)中的交通條件是不可預(yù)測(cè)的，而出行者又擁有完善的實(shí)時(shí)交通信息服務(wù)時(shí)，用戶只能依據(jù)當(dāng)前的交通條件來選擇出行路徑。這

27、分別導(dǎo)致了預(yù)測(cè)型和反應(yīng)型的路徑選擇行為。在智能運(yùn)輸系統(tǒng)的路徑誘導(dǎo)中，兩種模型都有應(yīng)用。 另外(ln wi)，動(dòng)態(tài)交通分配模型的形式，按狀態(tài)變量與時(shí)間關(guān)系的描述方式分，有連續(xù)時(shí)間模型和離散時(shí)間模型兩大類。對(duì)應(yīng)于靜態(tài)隨機(jī)交通分配模型，也有動(dòng)態(tài)隨機(jī)交通分配模型。在實(shí)際應(yīng)用中，離散型的動(dòng)態(tài)隨機(jī)交通分配模型用得更多。共九十六頁(yè)無論用哪種模型求解最優(yōu)路徑，都還有很多具體的理論和方法問題。如： 路網(wǎng)的描述(mio sh)方法 路段權(quán)重的標(biāo)定 交叉口延誤和通行時(shí)間的確定 最短路算法等。對(duì)于特定的模型，還會(huì)有特定的問題。如使用預(yù)測(cè)型用戶最優(yōu)模型時(shí)，交通流的實(shí)時(shí)預(yù)測(cè)就是非常重要、也是難度較大的問題。 共九十六頁(yè)4

28、.2.4 最短路徑算法 1. 概述 路徑規(guī)劃是幫助司機(jī)在旅行(lxng)前或旅行(lxng)中規(guī)劃行駛路線的過程，被廣泛認(rèn)為是車輛導(dǎo)航領(lǐng)域中的一個(gè)基本問題。而路徑規(guī)劃的最基本問題是求解最短路徑問題。 在路徑規(guī)劃中，可采用各種路徑優(yōu)化標(biāo)準(zhǔn)。一條路徑的好壞取決于許多因素，例如距離、旅行時(shí)間、旅行速度、拐彎和交通燈的數(shù)目和動(dòng)態(tài)交通信息。我們把所有這些因素稱為旅行費(fèi)用。有些司機(jī)愿意選擇最短路徑，而其他司機(jī)愿意選擇最短旅行時(shí)間等等。因此，選擇的估價(jià)函數(shù)取決于系統(tǒng)的設(shè)計(jì)和用戶的選擇。路徑選擇標(biāo)準(zhǔn)可由設(shè)計(jì)決定或通過用戶界面修改。為了求最小旅行距離（路段長(zhǎng)度），距離可存儲(chǔ)在數(shù)字地圖數(shù)據(jù)庫(kù)以便路徑規(guī)劃算法進(jìn)行最

29、小化時(shí)使用。如果最小化的是旅行時(shí)間，可以把路段長(zhǎng)度和速度限制存儲(chǔ)在數(shù)字地圖數(shù)據(jù)庫(kù)中以便計(jì)算每條路段的旅行時(shí)間時(shí)使用。線段長(zhǎng)度和速度限制通常在數(shù)字地圖數(shù)據(jù)庫(kù)中被定義為路段的屬性。總之，求最佳路徑通常要用到數(shù)字地圖數(shù)據(jù)庫(kù)來選擇使諸如時(shí)間和距離最小的一條路徑.共九十六頁(yè) 選擇路徑規(guī)劃算法的依據(jù)是希望算法的時(shí)間復(fù)雜性和空間復(fù)雜性較小，尤其是前者。從運(yùn)籌學(xué)的學(xué)習(xí)中大家熟悉的Dijkstra算法是個(gè)常用的算法，它計(jì)算從一個(gè)節(jié)點(diǎn)到路網(wǎng)其它各節(jié)點(diǎn)的最短路徑的時(shí)間復(fù)雜度是O（n3），表明算法運(yùn)行時(shí)間與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n的立方成正比。 事實(shí)上，對(duì)于一輛車的誘導(dǎo)，我們只要求求出從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑，因此可以改進(jìn)

30、Dijkstra算法，在遞推計(jì)算進(jìn)行到目標(biāo)節(jié)點(diǎn)時(shí)就停止遞推，而得到改進(jìn)的最短路徑算法。 最短路徑算法通常用于實(shí)時(shí)地尋找一個(gè)已知圖的解，或在脫機(jī)情況下，預(yù)先計(jì)算路徑存儲(chǔ)起來。當(dāng)一個(gè)誘導(dǎo)系統(tǒng)運(yùn)行時(shí)，用戶希望立即找出最優(yōu)路徑。盡管從車輛導(dǎo)航的觀點(diǎn)看，可以把一個(gè)大的、詳細(xì)的道路網(wǎng)看作一個(gè)圖，但為了路徑規(guī)劃把整個(gè)道路網(wǎng)裝人主存是不現(xiàn)實(shí)的（就當(dāng)前(dngqin)技術(shù)而言）。通常按要求把規(guī)劃過程中可能用到的部分道路網(wǎng)裝入主存，我們不需要處理整個(gè)圖，尤其在實(shí)時(shí)計(jì)算中?？梢栽O(shè)想我們正在搜索這樣一棵樹，其起始節(jié)點(diǎn)作為根節(jié)點(diǎn)，其余的生成節(jié)點(diǎn)作為葉子或后裔節(jié)點(diǎn)。因此，需要不同的度量函數(shù)來估計(jì)算法的運(yùn)行時(shí)間。 設(shè)b表示

31、分枝系數(shù)，它是搜索中每一節(jié)點(diǎn)引出的線段數(shù)的平均值。設(shè)d表示從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑解的搜索深度。搜索深度是搜索算法為了尋找解而必須遍歷的樹的層數(shù)。例如，如果把根節(jié)點(diǎn)看作第0層，根節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)為第l層。在這一概念下，改進(jìn)的最短路徑算法的運(yùn)行時(shí)間為O（bd）。在完成規(guī)劃過程中，主存中樹節(jié)點(diǎn)總數(shù)大約為bd。共九十六頁(yè)2. A*算法 啟發(fā)式搜索(su su)是基于知識(shí)的搜索(su su)策略，即從初始狀態(tài)和當(dāng)前狀態(tài)到目標(biāo)狀態(tài)搜索(su su)時(shí)具有與步驟數(shù)或費(fèi)用相關(guān)的信息。在路徑規(guī)劃采用的最流行的啟發(fā)式搜索(su su)是A*算法，它是一種最佳優(yōu)先搜索方法。 必須進(jìn)行搜索的原因是不知道確切

32、該走哪條路，如果事先知道該走哪條路情況會(huì)好得多。因此，引入啟發(fā)式信息會(huì)提高效率。啟發(fā)式信息有助于確定哪個(gè)節(jié)點(diǎn)“最有希望”生成哪些后繼節(jié)點(diǎn)和修剪哪些相關(guān)分枝。采用啟發(fā)式的目的是提供一個(gè)節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)有多遠(yuǎn)的估計(jì)，以便系統(tǒng)能夠確定特定節(jié)點(diǎn)處于最佳路徑解上的可能性。若啟發(fā)式方法對(duì)于正確方向進(jìn)行引導(dǎo)，它是令人滿意的；但是對(duì)于特定旅行，它可能暫時(shí)或偶爾對(duì)一個(gè)不適當(dāng)?shù)墓?jié)點(diǎn)進(jìn)行搜索，例如，街道的終點(diǎn)。盡管這是暫時(shí)問題，但如果存在通往目標(biāo)節(jié)點(diǎn)的路徑，搜索過程仍然能到達(dá)目標(biāo)節(jié)點(diǎn)。利用好的啟發(fā)式方法可以利用較少的時(shí)間和空間獲得令人滿意解路徑。共九十六頁(yè)A*算法對(duì)實(shí)現(xiàn)道路網(wǎng)的最佳優(yōu)先搜索極其有用。如果所選擇(xu

33、nz)的估價(jià)函數(shù)滿足某一特性（見下面解釋），且存在最優(yōu)路徑，A*算法保證能找到該最佳路徑，而其搜索空間比Dijkstra算法或修改過的最短路徑算法要少。為了理解節(jié)省的空間，用一個(gè)圓大致表示改進(jìn)的最短路徑算法（或Dijkstra算法）擴(kuò)展的抽象空間，朋一個(gè)雞蛋形區(qū)域大致代表A*算法擴(kuò)展的抽象空間，這樣，兩個(gè)算法搜索的空間如下圖所示。 共九十六頁(yè)利用啟發(fā)式信息的有效方法是計(jì)算啟發(fā)式函數(shù)，該函數(shù)估價(jià)每一生成節(jié)點(diǎn)以確定它的優(yōu)或劣。用這種方式，啟發(fā)式函數(shù)決定在諸多路徑中首先遍歷哪條路徑以便搜索過程更為有效。在A*算法中，啟發(fā)式估價(jià)函數(shù)便算法首先搜索最有希望的節(jié)點(diǎn)。節(jié)點(diǎn)n的估價(jià)函數(shù)f（n）定義為： 其中，

34、g（n）是從原節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際費(fèi)用，h（n）是從當(dāng)前節(jié)點(diǎn)”到目標(biāo)節(jié)點(diǎn)最小費(fèi)用路徑的估計(jì)。注意該公式中帶(zhn di)撇號(hào)的項(xiàng)表示包含估計(jì)費(fèi)用函數(shù)。共九十六頁(yè)正如前面所述，確定估價(jià)函數(shù)所使用的費(fèi)用取決于系統(tǒng)設(shè)計(jì)者和用戶。例如，如果選擇最短旅行時(shí)間，一種選擇是采用下面的啟發(fā)式估價(jià)函數(shù)： 其中，t（n）為旅行時(shí)間，d（n）是路段i的旅行距離，Vi（n）是該路段i的最大旅行速度（速度限制）。實(shí)際度量函數(shù)g（n）是從原節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)所經(jīng)過的所有路段的旅行時(shí)間總和。每一路段的旅行時(shí)間可以由路段的實(shí)際距離di（n）除以最大旅行速度Vi（n）得到。估計(jì)項(xiàng)h（n）是當(dāng)前點(diǎn)n和給定的目標(biāo)點(diǎn)之間的歐氏距離除

35、以估計(jì)的最大旅行速度V。注意我們用歐氏距離作為距離的估計(jì)。該距離是當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短距離，它通常小于或等于實(shí)際距離。如果估計(jì)的最大旅行速度大于或等于實(shí)際旅行速度，就往下估計(jì)時(shí)間?？傊?，算法(sun f)的目標(biāo)是使f（n）最小化。在這個(gè)例子中，使旅行時(shí)間最小化，即min（t（n）。 共九十六頁(yè)算法按步驟運(yùn)行，每一步擴(kuò)展一個(gè)節(jié)點(diǎn)（從給定的原節(jié)點(diǎn)開始），直到產(chǎn)生目標(biāo)節(jié)點(diǎn)。每一步僅擴(kuò)展生成節(jié)點(diǎn)中最有希望的節(jié)（最高優(yōu)先權(quán)，即”最好”）并把該最有希望的節(jié)點(diǎn)送入CLOSED表中。最好節(jié)點(diǎn)的后繼節(jié)點(diǎn)送入OPEN表中?！弊詈谩惫?jié)點(diǎn)是具有最小代價(jià)的節(jié)點(diǎn)，即其f（n）為最小。在此過程中，帶有約束的節(jié)點(diǎn)在搜索中

36、或在最終的路徑中不予以考慮，如排除方向錯(cuò)誤或帶有終止節(jié)點(diǎn)的路段，以致于導(dǎo)致不合法的拐彎或死胡同街道的節(jié)點(diǎn)。啟發(fā)式函數(shù)在檢查(jinch)任一個(gè)已擴(kuò)展的節(jié)點(diǎn)是否以前產(chǎn)生過之后，對(duì)每個(gè)擴(kuò)展節(jié)點(diǎn)估計(jì)它的希望大小。該檢查(jinch)保證節(jié)點(diǎn)在兩個(gè)鏈表之一中只出現(xiàn)一次。重復(fù)上述過程直到達(dá)到目標(biāo)節(jié)點(diǎn)，從目標(biāo)結(jié)點(diǎn)到原節(jié)點(diǎn)鏈起的節(jié)點(diǎn)是可逆的，因而作為解路徑。最后的節(jié)點(diǎn)和相關(guān)路段表或它們的擴(kuò)展表通常被稱為行駛指令表，因?yàn)檐囕v以后需要按照此表來操作以通過道路網(wǎng)達(dá)到希望的目標(biāo)。共九十六頁(yè)如果啟發(fā)式函數(shù)h（n）沒有過高估計(jì)達(dá)到目標(biāo)節(jié)點(diǎn)的實(shí)際費(fèi)用，A*算法將發(fā)現(xiàn)達(dá)到目標(biāo)的最優(yōu)解。這被稱為可納性。從估價(jià)函數(shù)的樣本來看，

37、因?yàn)楹瘮?shù)h（n）對(duì)任一節(jié)點(diǎn)n過低估計(jì)了它的費(fèi)用，所以h（n）的過高估計(jì)能夠容易地避免(bmin)。因此，如果啟發(fā)式函數(shù)選擇得好，則很容易滿足可納性。A*算法一般來說是最優(yōu)的，因?yàn)樗谇蠼膺^程中只生成最少節(jié)點(diǎn)。由于最短路徑費(fèi)用標(biāo)準(zhǔn)和可納性決定了所有路徑費(fèi)用和費(fèi)用估計(jì)是正的，故若存在最優(yōu)解的話，那么通過此算法一定能為車輛找到最優(yōu)路徑。共九十六頁(yè)A*算法步驟 第1步 設(shè)初始的OPEN表僅包含原節(jié)點(diǎn)，其費(fèi)用值為0，即g值為0。令CLOSED為空表，設(shè)其他節(jié)點(diǎn)的費(fèi)用為0。 第2步 若OPEN表為空，則宣告失?。环駝t，選取OPEN表中具有最小f值的節(jié)點(diǎn)，并叫做(jiozu)最佳節(jié)點(diǎn)BEST，把BEST從O

38、PEN表移至CLOSED表，判斷此BEST是否是一目標(biāo)節(jié)點(diǎn)。若BEST為目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)步驟3，若BEST不是目標(biāo)節(jié)點(diǎn)，則根據(jù)地圖數(shù)據(jù)庫(kù)包含的聯(lián)接路段屬性擴(kuò)展并生成BEST的后繼節(jié)點(diǎn)。對(duì)于每一個(gè)后繼節(jié)點(diǎn)n，進(jìn)行下列過程：2a 計(jì)算節(jié)點(diǎn)n的費(fèi)用：g（n）=BEST費(fèi)用+從BEST到n的費(fèi)用2b 如果n與OPEN表上的任一節(jié)點(diǎn)相同，判斷n是否具有最低的g值，若是最低的g值，用n的費(fèi)用代替OPEN表中相同的節(jié)點(diǎn)費(fèi)用，且建立匹配節(jié)點(diǎn)的后向指針指向BEST。 共九十六頁(yè)2c 如果n在CLOSED表中與一節(jié)點(diǎn)相匹配，檢查節(jié)點(diǎn)n是否具有最小的g值，如果節(jié)點(diǎn)n具有最小的g值，則用節(jié)點(diǎn)n的費(fèi)用代替匹配節(jié)點(diǎn)的費(fèi)用，并

39、把匹配節(jié)點(diǎn)的后向指針指向BEST，并把該匹配節(jié)點(diǎn)移到OPEN表。 2d 如果n不在OPEN表上，也不在CLOSED表上，則把n的后向指針指向BEST，并把n放入OPEN表中。計(jì)算節(jié)點(diǎn)n的估價(jià)函數(shù)：f(n)=g(n)+h(n) 重復(fù)第2步。 第3步 從BEST節(jié)點(diǎn)回朔，即從BEST的后向指針一直到原節(jié)點(diǎn)遍歷節(jié)點(diǎn)；最后報(bào)告(bogo)解路徑。出于完整性，我們已經(jīng)描述了整個(gè)算法。仔細(xì)研究A*算法后，我們看到A*算法與改進(jìn)的最短路徑算法的唯一差別是估價(jià)函數(shù)引人了一個(gè)啟發(fā)式函數(shù)。共九十六頁(yè)為了更好地理解A*算法，讓我們看看(kn kn)它對(duì)于下圖所示的道路網(wǎng)是如何建立一個(gè)樹的，其中每個(gè)交叉路口由一個(gè)英文

40、字母表示。 一個(gè)簡(jiǎn)單的道路網(wǎng)共九十六頁(yè)對(duì)于該旅行，假設(shè)原節(jié)點(diǎn)在m，目標(biāo)節(jié)點(diǎn)為g。完成路徑規(guī)劃過程后，最后的搜索樹如下圖所示。同前面一樣，用圓圈表示每一節(jié)點(diǎn)，忽略節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和指針箭頭；用直線段表示節(jié)點(diǎn)的向上指針（后向指針）和向下指針（下一項(xiàng)指針）；向上指針指向該節(jié)點(diǎn)的前趨節(jié)點(diǎn)，向下指針指向節(jié)點(diǎn)的后繼節(jié)點(diǎn)；圓圈中的字母表示該節(jié)點(diǎn)在OPEN表中還是在CLOSED表中。盡管樹上的每一 節(jié)點(diǎn)作為后繼節(jié)點(diǎn)不只一次，但在OPEN表和CLOSED表之一只能出現(xiàn)一次，因?yàn)锳*算法步驟2b和2c消除了冗余節(jié)點(diǎn)。樹中節(jié)點(diǎn)多次出現(xiàn)并不難理解，因?yàn)榈侥繕?biāo)節(jié)點(diǎn)可以有不同的路徑經(jīng)過相同的交叉路口。注意這種情況沒有發(fā)生在

41、所舉的簡(jiǎn)單的例子中。在例子中，算法沒有檢查(jinch)最后的后繼節(jié)點(diǎn)i且沒有把它放大樹中，因?yàn)樗惴ㄒ呀?jīng)搜索到目標(biāo)節(jié)點(diǎn)g。遍歷一系列后向指針，得到最佳路 徑為m-n-j-g。右圖是A*算法的最終搜索樹 共九十六頁(yè)共九十六頁(yè)例中最后(zuhu)的OPEN表和CLSED表如右圖所示。黑點(diǎn)指示表頭，接地符號(hào)表示表結(jié)束。在實(shí)現(xiàn)中，表結(jié)束用空指針表示。OPEN表是這樣安排的，即最小費(fèi)用節(jié)點(diǎn)總是處在表的頂部。共九十六頁(yè)共九十六頁(yè) A*算法的運(yùn)行時(shí)間為O（bd）。初看起來用大寫O標(biāo)記表達(dá)的運(yùn)行時(shí)間與改進(jìn)的最短路徑算法相同。實(shí)際上A*算法使用的啟發(fā)式信息通常會(huì)減少時(shí)間復(fù)雜性，因?yàn)锳*算法的b值應(yīng)該小于改進(jìn)的最

42、短路徑算法的b值?？傊@是我們使用啟發(fā)式方法的主要原因。正如改進(jìn)的Dijkstra算法，A*算法的運(yùn)行時(shí)間通過使用較好的數(shù)據(jù)結(jié)構(gòu)可得到進(jìn)一步減少。 上述(shngsh)A*算法是從起始節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)搜索。還可以 改進(jìn)為同時(shí)從起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)開始搜索（雙向搜索），得到更好的啟發(fā)式算法。右圖是雙向搜索和單向搜索算法搜索空間的比較示意圖。共九十六頁(yè)共九十六頁(yè)4.2.5 路徑引導(dǎo) 1.概述(i sh) 路徑引導(dǎo)是引導(dǎo)司機(jī)沿著由路徑規(guī)劃模塊計(jì)算出的路線行駛的過程。該引導(dǎo)過程可以在旅行前或在途中以實(shí)時(shí)方式進(jìn)行。行駛前的引導(dǎo)信息可以用打印機(jī)打印出來，提供給司機(jī)。這些指令可以 包括轉(zhuǎn)向、街道名稱、行駛距離

43、和路標(biāo)。另一方面，行進(jìn)中的路徑引導(dǎo)需要向司機(jī)提供實(shí)時(shí)的依次轉(zhuǎn)向行駛指令。右圖是導(dǎo)航器顯示器。共九十六頁(yè)在車載導(dǎo)航器軟件中，路徑引導(dǎo)模塊利用路徑規(guī)劃模塊和定位子系統(tǒng)引導(dǎo)車輛行駛。除地圖數(shù)據(jù)庫(kù)模塊外，定位子系統(tǒng)可以僅包括定位模塊，或者包括定位模塊和地圖匹配模塊。一旦由路徑規(guī)劃模塊計(jì)算出特定(tdng)的路徑且定位子系統(tǒng)已經(jīng)確定了車輛的位置，路徑引導(dǎo)模塊與這些子系統(tǒng)協(xié)同工作以向司機(jī)提供適當(dāng)?shù)囊龑?dǎo)。引導(dǎo)信息的表達(dá)借助于人機(jī)接口模塊。引導(dǎo)模塊與其他模塊相互作用的簡(jiǎn)化功能框圖如下圖所示。注意在某些系統(tǒng)中行駛指令的產(chǎn)生是路徑規(guī)劃模塊的主要任務(wù)。 共九十六頁(yè)路徑引導(dǎo)(yndo)模塊和其他模塊相互作用的簡(jiǎn)化框圖

44、共九十六頁(yè)隨著車輛(chling)行駛，實(shí)時(shí)路徑導(dǎo)航要求車輛(chling)的位置作為時(shí)間的函數(shù)不斷地與路徑規(guī)劃模塊產(chǎn)生的最佳路徑相比較。根據(jù)車輛(chling)當(dāng)前的位置、走向及行駛的道路信息，實(shí)時(shí)路徑引導(dǎo)系統(tǒng)不斷地更新這些信息。當(dāng)轉(zhuǎn)彎或者行駛指令到達(dá)時(shí)，路徑引導(dǎo)系統(tǒng)的可視信號(hào)、聲頻信號(hào)或者行駛指令向駕駛員發(fā)出報(bào)警信號(hào)。 2.途中引導(dǎo) 正如上圖所示，路徑引導(dǎo)包括兩個(gè)任務(wù)：一是行駛指令的產(chǎn)生；二是規(guī)劃路徑的跟蹤。注意對(duì)于路徑引導(dǎo)模塊有許多不同的設(shè)計(jì)和實(shí)現(xiàn)方案而不只是圖中所示的一種方案。例如，行駛指令生成任務(wù)可以是路徑規(guī)劃模塊的主要部分。行駛指令生成任務(wù)和規(guī)劃路徑跟蹤任務(wù)可直接處理由規(guī)劃模塊產(chǎn)生

45、的數(shù)據(jù)。然而為了表達(dá)基本思想，我們利用圖中所示的功能框圖描述路徑引導(dǎo)模塊的原理和實(shí)際問題。共九十六頁(yè)3.行駛指令的產(chǎn)生 如上所述，行駛指令的產(chǎn)生是路徑規(guī)劃模塊的子功能或者是路徑引導(dǎo)模塊的獨(dú)立任務(wù)。該任務(wù)的主要功能是產(chǎn)生一個(gè)由規(guī)劃路徑跟蹤所遵循的行駛指令列表。由非層次路徑規(guī)劃模塊生成的典型輸出路徑是簡(jiǎn)單的路段列表，該列表并不提供足夠的引導(dǎo)信息。行駛指令的產(chǎn)生以適當(dāng)?shù)男旭傊噶詈娃D(zhuǎn)彎信息向列表中的路段添加信息，這些信 息通過人機(jī)接口以特殊的視、聽指令加以解釋(jish)。右圖給出了行駛指令和轉(zhuǎn)彎類型的某些實(shí)例。行駛指令與轉(zhuǎn)彎類型的不同組合對(duì)應(yīng)于不同的視聽表達(dá)。共九十六頁(yè)共九十六頁(yè)如果采用層次路徑規(guī)劃

46、模型，如上面所討論的，增添輸出路段信息前，把輸出路段分成最底層的路段，這取決于如何構(gòu)造高層路段。為節(jié)省內(nèi)存，高層路段僅包含(bohn)與路徑規(guī)劃有關(guān)的信息。對(duì)于定位與引導(dǎo)，最好使用最底層的路段，因?yàn)榈讓拥拿恳宦范伟?bohn)較詳細(xì)的引導(dǎo)信息。幾乎所有的車輛在任何旅行中既使用高層路段又使用底層路段，這意味著利用存儲(chǔ)相關(guān)數(shù)據(jù)的最低層路段引導(dǎo)車輛更加有效。事實(shí)上，在規(guī)劃和引導(dǎo)中所采用的數(shù)據(jù)存取方法對(duì)于獲得最大性能是至關(guān)重要的，尤其是基于分層地圖數(shù)據(jù)庫(kù)系統(tǒng)。 共九十六頁(yè)為了確保路徑引導(dǎo)模塊的有效實(shí)現(xiàn)，對(duì)于內(nèi)存空間和數(shù)據(jù)存取機(jī)制應(yīng)該給予認(rèn)真考慮。為了使路徑規(guī)劃模塊使用最小的內(nèi)存，較高層的數(shù)據(jù)可以采用

47、僅適用規(guī)劃的形式存儲(chǔ)。利用地圖數(shù)據(jù)的分層表達(dá)，會(huì)給路徑規(guī)劃帶來很大好處。采用分層表示的不利一面是在路徑引導(dǎo)模塊中處理最后所得到的路段需要額外的時(shí)間。當(dāng)然總會(huì)有折衷方案。對(duì)于設(shè)計(jì)成在大公路網(wǎng)行駛的系統(tǒng)，與規(guī)劃中節(jié)省的時(shí)間相比，值得在引導(dǎo)中做更多的工作（基于當(dāng)前的技術(shù)）。此外，當(dāng)前可利用的實(shí)時(shí)計(jì)算技術(shù)允許多個(gè)任務(wù)同時(shí)(tngsh)執(zhí)行。一旦計(jì)算出足夠的能夠進(jìn)行初始路徑跟蹤的行駛指令，其余的工作可在后臺(tái)執(zhí)行。畢竟車載導(dǎo)航系統(tǒng)是實(shí)時(shí)嵌人計(jì)算機(jī)的應(yīng)用?？紤]到地圖匹配定位的簡(jiǎn)單化，基于基本層（最低層）報(bào)告當(dāng)前車輛的位置更加容易。換言之，基于層次數(shù)據(jù)庫(kù)規(guī)劃出的路徑對(duì)于引導(dǎo)來說可能不夠詳細(xì)，應(yīng)該生成對(duì)于引導(dǎo)來

48、說具有足夠的詳細(xì)信息的基本路段的行駛指令列表。在層次的實(shí)現(xiàn)方式中，行駛指令的生成工作包括把一系列路徑的所有高層路段分解成基本路段。同時(shí)(tngsh)把行駛指令和轉(zhuǎn)彎類型信息添加到行駛指令列表中。 共九十六頁(yè)層次地圖數(shù)據(jù)庫(kù)如果采用慢速的輔助存儲(chǔ)器或遠(yuǎn)程批處理裝置，我們需要有效地利用內(nèi)存空間，至少把路徑規(guī)劃所需的信息放人主存以便檢索與路段(l dun)相關(guān)的信息。換言之，當(dāng)數(shù)據(jù)庫(kù)存儲(chǔ)在低速的存儲(chǔ)裝置時(shí)，為了使規(guī)劃效率達(dá)到最大，規(guī)劃所需要的信息應(yīng)該與定位、行駛指令的生成和路徑跟蹤分開存放。路徑規(guī)劃完成后，僅需要在主存為行駛指令列表中的路段(l dun)和與車輛鄰接的路段(l dun)存儲(chǔ)詳細(xì)的信息。

49、為了節(jié)省存儲(chǔ)空間，我們同時(shí)也放棄路徑規(guī)劃所使用的，對(duì)路徑引導(dǎo)不再需要的任何數(shù)據(jù)。 為了有效地存取數(shù)據(jù)應(yīng)該采用良好的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)應(yīng)該有助于系統(tǒng)避免窮舉的搜索，避免一經(jīng)要求就計(jì)算和相同區(qū)域的重復(fù)存取。理想地，一旦找到路徑上的一條路段，辨別即將出現(xiàn)的路段應(yīng)該像存取一個(gè)結(jié)構(gòu)字段或沿著指針查找一樣簡(jiǎn)單。一個(gè)可接受的數(shù)據(jù)結(jié)構(gòu)是一個(gè)行駛指令雙向鏈表，前項(xiàng)指針指向剛剛存取的行駛指令，后項(xiàng)指針指向下一個(gè)行駛指令。旅行代價(jià)的計(jì)算結(jié)果可存儲(chǔ)起來以限制路徑引導(dǎo)期間一經(jīng)要求就計(jì)算的弊端。如果沒有足夠的與其他導(dǎo)航任務(wù)共享的可利用主存，可利用高速緩沖存儲(chǔ)器管理數(shù)據(jù)存取，避免從輔助內(nèi)存對(duì)相同數(shù)據(jù)的重復(fù)請(qǐng)求。高速緩沖

50、存儲(chǔ)器是一組數(shù)據(jù)存儲(chǔ)單元，邏輯上是輔助內(nèi)存的一部分，但是由于性能原因保留在主存。換言之，高速緩沖存儲(chǔ)器在主存提供一個(gè)高速緩沖區(qū)作為輔助內(nèi)存的臨時(shí)數(shù)據(jù)存儲(chǔ)?？傊?，應(yīng)該盡可能少地在主存存儲(chǔ)引導(dǎo)數(shù)據(jù)，而仍能提供快速存取和在時(shí)間、空間的折衷達(dá)到較好的平衡。共九十六頁(yè)4.規(guī)劃路徑的跟蹤 如果車輛的當(dāng)前位置能夠準(zhǔn)確地確定，途中引導(dǎo)是不困難的。一旦車輛的位置是已知的，并把該位置與規(guī)劃的路徑對(duì)比(dub)后，可以為司機(jī)準(zhǔn)備或提供適當(dāng)?shù)男盘?hào)和指令。規(guī)劃的路徑包括通往目的地的一系列路段，這些路段是由系統(tǒng)設(shè)計(jì)或由司機(jī)選擇的規(guī)劃標(biāo)準(zhǔn)所確定的規(guī)劃條件下產(chǎn)生的。在途中的任一點(diǎn)，車輛應(yīng)行駛在規(guī)劃出的路徑中的某一路段上。路徑

51、跟蹤的任務(wù)是緊密監(jiān)視車輛處于該路段上的位置以確定何時(shí)采用適當(dāng)?shù)囊龑?dǎo)行動(dòng)。這些行動(dòng)通過人機(jī)接口提供給司機(jī)。簡(jiǎn)言之，路徑引導(dǎo)模塊的主要功能應(yīng)該是確定何時(shí)及如何引導(dǎo)司機(jī)行駛。 共九十六頁(yè)一旦路徑跟蹤識(shí)別出司機(jī)下一步的行駛指令，它必須借助于一種方式把該指令信息傳遞給司機(jī)。目前導(dǎo)航系統(tǒng)所采用的最流行方法是提供一個(gè)或一系列聲音預(yù)告以事先通知司機(jī)即將到來的行駛指令，這樣他或她可以采取適當(dāng)?shù)男袆?dòng)（見下圖）。另一種方法是把行駛指令以人工控制方式或自動(dòng)方式顯示在屏幕上，或提供簡(jiǎn)單的聲調(diào)等?？赏ㄟ^揚(yáng)聲器利用事先錄制的人的聲音或語(yǔ)音合成發(fā)出預(yù)告。 消息預(yù)告的定時(shí)建議，許多是基于實(shí)際路徑引導(dǎo)系統(tǒng)獲得的經(jīng)驗(yàn)。行駛指令定時(shí)

52、取決于道路的類型和距離或者后面的行駛指令。這意味著道路類型、交叉路口類型、行駛速度和距離及車道數(shù)是設(shè)計(jì)路徑引導(dǎo)模塊中的行駛指令定時(shí)所考慮的重要因素。其他推理技術(shù)也可以和所有相關(guān)因素結(jié)合起來使用，確定最佳的定時(shí)。此外，提前消息，譬如”早期消息”和”準(zhǔn)備消息”的精確定時(shí)不是至關(guān)重要的；但是，轉(zhuǎn)彎消息，例如”到達(dá)消息”的定時(shí)是重要的。如果行駛指令存儲(chǔ)在低速的輔助內(nèi)存中，可能需要采取預(yù)先取出技術(shù)或高速緩沖存儲(chǔ)以便在一條預(yù)期(yq)的行駛指令到來時(shí)可以使用這些行駛指令。無論采用哪一種方法，子系統(tǒng)的主要目的是避免太早或太晚預(yù)告即將到來的行駛指令，這樣，司機(jī)可以從這些指令受益以提高安全性和取得最大的運(yùn)行性能

53、。共九十六頁(yè)5.偏離路徑的引導(dǎo) 司機(jī)可能由于各種原因偶爾地偏離規(guī)劃的路徑行駛。他們可能在指示的交叉路口轉(zhuǎn)錯(cuò)了彎，對(duì)于一個(gè)交叉路口可能不能行駛到正確的車道，也可能臨時(shí)離開路徑等等。一旦系統(tǒng)確定車輛不再行駛在給定的路徑（或沒有行駛在預(yù)先確定的附近任何路段上），系統(tǒng)必須具有使車輛回到正確路徑上的機(jī)制。 可采用不同的方法解決這個(gè)問題。一旦確定車輛偏離了路徑，一個(gè)簡(jiǎn)單的解決辦法是提醒司機(jī)注意(zh y)車輛偏離了它的路徑，接著在屏幕上顯示一個(gè)方向箭頭指向原來目的地方向。司機(jī)應(yīng)該利用這一大致方向返回到原來的道路或者找到一條到達(dá)目的地的道路。另一種解決辦法是通知司機(jī)車輛已經(jīng)偏離了路徑，需要重新規(guī)劃一條通往目

54、的地的路徑。重新從當(dāng)前偏離路徑位置規(guī)劃一條到達(dá)原出的地的最短路徑是另一種選擇。在車輛偏離路徑的地方，其路段后面緊接著的路段在這種情況下可作為間接的目的地，也可以使用原來的目的地重新規(guī)劃一條路徑。這一解決辦法的棘手問題是路徑規(guī)劃系統(tǒng)如何確定新的起點(diǎn)。如果出現(xiàn)偏離路徑后車輛停下來，車輛的當(dāng)前位置可作為起點(diǎn)；否則，必須在車輛當(dāng)前行駛方向前面選擇起點(diǎn)。一個(gè)好的候選起點(diǎn)是這樣的點(diǎn)，假如必須重新規(guī)劃新的路徑，到達(dá)該點(diǎn)的行駛時(shí)間等于最大值。 共九十六頁(yè)這里討論的所有方法是假設(shè)車輛偏離了規(guī)劃路徑，但仍在路上。如何(rh)引導(dǎo)偏離道路的車輛呢?顯然，偏離道路的車輛也偏離了規(guī)劃路徑。一個(gè)策略是通知司機(jī)車輛偏離了道

55、路，必須返回最近的路段。系統(tǒng)不斷地監(jiān)視車輛，看它是否已經(jīng)返回到道路網(wǎng)。一旦系統(tǒng)確定車輛又處在道路上，可采用前面的方法引導(dǎo)車輛。也可以通過屏幕上顯示的方向指示引導(dǎo)司機(jī)返回到最近的道路，或者確定和顯示司機(jī)應(yīng)該返回的最近路段。除這里提及的方法外，有許多其他方法可用于偏離道路的復(fù)位。共九十六頁(yè)5.利用動(dòng)態(tài)信息的引導(dǎo) 在前面的討論中，我們隱含地假設(shè)路徑引導(dǎo)模塊是基于靜態(tài)的路徑規(guī)劃。基于靜態(tài)路徑規(guī)劃系統(tǒng)利用每條路段的靜態(tài)旅行代價(jià)計(jì)算最小代價(jià)路徑并引導(dǎo)車輛沿著該路徑行駛。在真實(shí)的世界環(huán)境，實(shí)際的代價(jià)取決于特定時(shí)間的交通條件的動(dòng)態(tài)值。因此，按照改進(jìn)路徑引導(dǎo)的觀點(diǎn)，基于動(dòng)態(tài)路徑規(guī)劃的系統(tǒng)是可取的。理想地，用于引

56、導(dǎo)的路徑要基于每條特定路段的實(shí)時(shí)代價(jià)來計(jì)算。更具體地說，動(dòng)態(tài)行駛代價(jià)應(yīng)該基于鏈路代價(jià)，它是路段代價(jià)與行駛中從交通控制中心或交通管理中心接收到的轉(zhuǎn)彎代價(jià)之和。記住左轉(zhuǎn)彎、右轉(zhuǎn)彎、在停止(tngzh)信號(hào)處轉(zhuǎn)彎和在交通燈處轉(zhuǎn)彎的代價(jià)都取決于特定的道路。 這里僅討論自治型動(dòng)態(tài)路徑誘導(dǎo)情況。 假設(shè)車內(nèi)系統(tǒng)能夠從控制中心或信息中心（如交通信息中心）接收、過濾和存儲(chǔ)信息，路徑引導(dǎo)模塊必須為規(guī)劃路徑采取適當(dāng)行動(dòng)以響應(yīng)到來的擁擠報(bào)告。 共九十六頁(yè)在動(dòng)態(tài)路徑引導(dǎo)系統(tǒng)中，我們必須面對(duì)與系統(tǒng)結(jié)構(gòu)有關(guān)的三個(gè)重要問題：第一是，需要確定(qudng)的動(dòng)態(tài)（靜態(tài)）信息是否應(yīng)該由中心系統(tǒng)還是由車載系統(tǒng)處理；第二是，需要確定

57、(qudng)動(dòng)態(tài)信息的更新頻率；第三是，需要確定(qudng)所使用的通信介質(zhì)以確保交通設(shè)施和車輛之間平滑的信息流。這一節(jié) ，將討論車上的靜態(tài)行駛信息存儲(chǔ)結(jié)構(gòu)及由控制中心或交通管理中心周期地提供的動(dòng)態(tài)信息。假設(shè)信息更新頻率足以反映道路的交通條件和在車上進(jìn)行路徑規(guī)劃?，F(xiàn)在討論一個(gè)可用于這種結(jié)構(gòu)的動(dòng)態(tài)路徑引導(dǎo)算法（見下圖）。共九十六頁(yè)共九十六頁(yè)這一算法的主要思想是盡可能多地依靠(yko)動(dòng)態(tài)行駛代價(jià)進(jìn)行路徑引導(dǎo)。為了達(dá)到這一目的，車載導(dǎo)航計(jì)算機(jī)必須能夠接收動(dòng)態(tài)代價(jià)數(shù)據(jù)，這樣把靜態(tài)數(shù)據(jù)庫(kù)變成動(dòng)態(tài)數(shù)據(jù)庫(kù)。一個(gè)簡(jiǎn)單的方法是在車上保留一個(gè)靜態(tài)數(shù)據(jù)庫(kù)。在路徑引導(dǎo)過程中，該數(shù)據(jù)庫(kù)能動(dòng)態(tài)地更新以反映新的代價(jià)信

58、息。 利用行駛時(shí)間作為路徑規(guī)劃代價(jià)。正如在第2章所了解的那樣，路段長(zhǎng)度和速度限制是靜態(tài)地圖數(shù)據(jù)庫(kù)所使用的屬性。如第5章所討論的那樣，這些屬性能容易地轉(zhuǎn)換成用于路徑規(guī)劃的行駛時(shí)間。用行駛時(shí)間作為代價(jià)，靜態(tài)路徑規(guī)劃系統(tǒng)能夠?yàn)樗緳C(jī)生成最小行駛時(shí)間的路徑。該路徑是在一定假設(shè)下導(dǎo)出的，即司機(jī)通常以每條路段所限制的速度行駛。提供行駛代價(jià)信息的較好方法是利用靜態(tài)數(shù)據(jù)庫(kù)。由于車輛并不總是以允許的限制速度行駛，該數(shù)據(jù)庫(kù)更準(zhǔn)確地反映實(shí)際行駛條件。共九十六頁(yè)這種類型的一個(gè)例子是把數(shù)據(jù)庫(kù)和歷史文件結(jié)合起來。該文件最初是由脫機(jī)過程獲得的。回想一下，每一鏈路表示一條路段與轉(zhuǎn)彎延遲信息(xnx)的和。這一過程利用交通流模型

59、（由道路網(wǎng)和其他數(shù)據(jù)來支持）的詳細(xì)表達(dá)，在一天內(nèi)的每一時(shí)間為起始目的旅行表估算鏈路行駛時(shí)間和流量。把一天24小時(shí)分成不同的區(qū)段，這樣能適當(dāng)?shù)毓烙?jì)每一鏈路的行駛時(shí)間。該模型也可和交通延遲函數(shù)（它包括轉(zhuǎn)彎運(yùn)動(dòng)和信號(hào)控制參數(shù)）結(jié)合起來。當(dāng)與實(shí)際結(jié)合時(shí)，這些鏈路行駛時(shí)間是確認(rèn)的，并且利用從交通檢測(cè)車輛或其他交通傳感器和軼事信息接受到的實(shí)際數(shù)據(jù)進(jìn)行更新。檢測(cè)車輛是實(shí)時(shí)報(bào)告其行駛道路交通數(shù)據(jù)的車輛。這一歷史簡(jiǎn)況數(shù)據(jù)可作為數(shù)字地圖數(shù)據(jù)庫(kù)編譯器的輸入。編譯后，以文件方式存儲(chǔ)的鏈路行駛時(shí)間成為導(dǎo)航數(shù)據(jù)庫(kù)的屬性。與路徑引導(dǎo)算法結(jié)合使用時(shí)，系統(tǒng)可提供一條真實(shí)的路徑。系統(tǒng)基于新交通數(shù)據(jù)布置后，假如這一特性包含在系統(tǒng)中

60、，歷史文件可以周期間隔得到進(jìn)一步的改進(jìn)。盡管這一改進(jìn)是通過限定速度作為行駛代價(jià)，但系統(tǒng)建議的路徑將仍然基于數(shù)據(jù)庫(kù)預(yù)先存儲(chǔ)的靜態(tài)代價(jià)。只有使用動(dòng)態(tài)代價(jià)時(shí)，路徑引導(dǎo)系統(tǒng)才真正成為動(dòng)態(tài)的。 共九十六頁(yè)上頁(yè)圖描述的算法首先使用靜態(tài)代價(jià)規(guī)劃路徑。司機(jī)沿著規(guī)劃的路徑行駛時(shí)，車載系統(tǒng)不斷地監(jiān)視由交通控制中心或交通管理中心廣播的新消息。為簡(jiǎn)單起見，假設(shè)消息包含車輛正在行駛區(qū)定消息是否包含車輛附近的鏈路信息。如果消息包含這樣的數(shù)據(jù)，在靜態(tài)數(shù)據(jù)庫(kù)受影響的鏈路使用新的鏈路代價(jià)信息進(jìn)行更新。為快速存儲(chǔ)和檢索，更新數(shù)據(jù)可放人主存。這不僅便于動(dòng)態(tài)數(shù)據(jù)庫(kù)的維護(hù)，而且有益于有效的路徑規(guī)劃與引導(dǎo)。如果一個(gè)或幾個(gè)受影響的鏈路恰好