上海大學(xué)碩士學(xué)位論文 摘要 隨著交通運(yùn)輸業(yè)的發(fā)展，車輛導(dǎo)航系統(tǒng)被越來越多的人們所接受，用來在行 駛過程中，快速準(zhǔn)確地確定車輛的位置，為司機(jī)指出到達(dá)指定目的地的合理路徑。 在車輛導(dǎo)航系統(tǒng)中，如何引導(dǎo)車輛是一個(gè)至關(guān)重要的問題，因?yàn)槿绻捎貌缓线m 的引導(dǎo)策略，導(dǎo)航系統(tǒng)的應(yīng)用可能反而會對交通系統(tǒng)的效率產(chǎn)生負(fù)面影響。事實(shí) 上，傳統(tǒng)的貪婪引導(dǎo)法，也就是將所有車輛都引導(dǎo)到最優(yōu)路徑上，可能會因?yàn)樽?優(yōu)路徑上聚集了超過其交通容量的車流，而造成堵車等現(xiàn)象，從而降低交通系統(tǒng) 的效率。從這個(gè)角度來講，適當(dāng)分流，讓一部分車輛選擇其他路徑行駛，反而會 提高交通系統(tǒng)的整體效率。而如何分流才能使得交通系統(tǒng)中所有車輛的總行駛時(shí) 間最短，是一個(gè)值得探討的問題。 本文提出了一種新型的啟發(fā)式算法一b o l t z m a n n 全局最優(yōu)尋路算法，該算法 為交通系統(tǒng)中從不同起點(diǎn)出發(fā)開往不同終點(diǎn)的所有車輛，尋找近似全局最優(yōu)的交 通流分配方案。該算法的主要思想是反復(fù)迭代地根據(jù)在當(dāng)前的交通狀況下，車輛 通過各路段所要花費(fèi)的行駛時(shí)間，結(jié)合基于q 值的動態(tài)規(guī)劃算法和b o l t z r n a n n 分布 為交通系統(tǒng)尋找擬最優(yōu)路徑，根據(jù)該擬最優(yōu)路徑分配交通流，然后再根據(jù)分配后 的交通流，啟發(fā)式地更新路段行駛時(shí)間，再次尋找新的擬最優(yōu)方案，直到交通系 統(tǒng)中所有的路段行駛時(shí)間收斂，我們找到近似全局最優(yōu)交通流分配方案為止。 該算法分別在靜態(tài)交通系統(tǒng)和動態(tài)交通系統(tǒng)中與g r e e d y 算法，即將所有車輛 都引導(dǎo)到最優(yōu)路徑上的車輛引導(dǎo)算法進(jìn)行了比較。這里，在靜態(tài)交通系統(tǒng)中，我 們假設(shè)流入交通系統(tǒng)的車流量是靜態(tài)不變的；而在動態(tài)交通系統(tǒng)中，從不同起點(diǎn) 出發(fā)到達(dá)不同終點(diǎn)的車流量，都將隨機(jī)不斷生成。實(shí)驗(yàn)結(jié)果顯示，應(yīng)用b o l t z m a n n 全局最優(yōu)尋路算法能夠合理地分配交通流，為交通系統(tǒng)帶來更高的整體效率。 本文所做的主要貢獻(xiàn)有：( 1 ) 結(jié)合基于q 值的動態(tài)規(guī)劃算法，提出了b o l t z m a n n 全局最優(yōu)尋路算法( 2 ) 分別在靜態(tài)和動態(tài)模擬交通系統(tǒng)中對其加以了驗(yàn)證( 3 ) 對實(shí)驗(yàn)結(jié)果進(jìn)行分析和評估，并提出了改進(jìn)建議。 關(guān)鍵詞：q 值；動態(tài)規(guī)劃：b o l t z r n a t m 分布；貪婪算法；全局最優(yōu) v 上海大學(xué)碩士學(xué)位論文 a bs t r a c t n o w a d a y s ，g i l l n a v i g a t i o ns y s t e m sa r ec o m m o n l ya d o p t e di nt h et r a n s p o r t a t i o n s y s t e m st oh e l pc a rd r i v e r sa c c u r a t e l ya n dd y n a m i c a l l yl o c a t et h e i rp o s i t i o n so nt h e m a pa n dt h e nf i n dd e s i r a b l er o u t e sf o rm e i rd e s t i n a t i o n s i n d e e d ，t h es c h e d u l i n g m e t h o d s ，i e ，h o wt r a f f i ci sg u i d e di nv e h i c l en a v i g a t i o ns y s t e m sm o r es p e c i f i c a l l y , h a v ea ni m p o r t a n ti m p a c to nt h es y s t e me f f i c i e n c y , s i n c ea d o p t i n gu n s u i t a b l eg u i d i n g s t r a t e g i e sw o u l dp r o b a b l yr e s u l ti nt e r r i b l ec o n d i t i o n s a c t u a l l y , t h et r a d i t i o n a l m e t h o d st e l l i n ge v e r yd r i v e rt h es h o r t e s tp a t hh a v eah i g hp r o b a b i l i t yt oc a u s et r a f f i c c o n g e s t i o n , b e c a u s es h o r t e rr o m es e c t i o n sm a ya t t r a c tm o r ev e h i c l e s ，w h i c hw o u l d p o s s i b l ye x c e e d st h er o a dd e s i g nc a p a c i t i e s i nt h i ss e n s e ，i n t r o d u c i n ga l t e r n a t er o u t e s m a yp r e s e n tg r e a t e ra d v a n t a g ei ng i o b a lp e r s p e c t i v e ，a n dh o wt om a k et h er o u t e sf o r a l lt h ev e h i c l e si nt h ew h o l et r a f f i cs y s t e mw i t haf e a s i b l ea n dr e a s o n a b l ew a ya r i s e s a sac h a l l e n g i n gt a s kf o r t h ec e n t r a l i z e dt r a f f i cs c h e d u l e r t h e r e f o r e ，i nt h i sp a p e r , w ep r o p o s eah e u r i s t i cm e t h o d b o l t z r n a n no p t i m a l r o u t em e t h o dt r y i n gt of i n dag o o da p p r o x i m a t i o nt ot h eg l o b a lo p t i m u mr o u t ef o r o r i g i n d e s t i n a t i o np a i r st h r o u g hi t e r a t i o n su n t i lt h et o t a lt r a v e l i n gt i m ec o n v e r g e s 1 1 1 eo v e r a l li d e ao fo u rm e t h o di st oi t e r a t i v e l yu p d a t et h et r a v e l i n gt i m eo fe a c hr o u t e s e c t i o na c c o r d i n gt oi t sc o r r e s p o n d i n gt r a f f i cv o l u m e ，a n dc o n t i n u o u s l yg e n e r a t ea n e wg l o b a lr o m eb yqv a l u e - b a s e dd y n a m i cp r o g r a m m i n gc o m b i n e dw i t hb o l t z m a n n d i s t r i b u t i o n f i n a l l y , w ec a ng e tt h eg l o b a lo p t i m u mr o m ec o n s i d e r i n gt h et r a f f i c v o l u m e so ft h er o a ds e c t i o n s t h en e wp r o p o s e dm e t h o di sc o m p a r e dw i t ht h ec o n v e n t i o n a ls h o r t e s t - p a t h m e t h o d g r e e d ya l g o r i t h mi nb o t hs t a t i ct r a f f i cs y s t e mw h e r et h ev o l u m e so fa l lt h e g i v e no r i g i n - d e s t i n a t i o np a i r so fr o a dn e t w o r k sa r es t a t i ca n dd y n a m i ct r a f f i cs y s t e m i nw h i c hd y n a m i ct r a f f i cv o l u m e sa r ec o n s t a n t l yp r o v i d e d t h er e s u l td e m o n s t r a t e s t h a tt h ep r o p o s e dm e t h o dp e r f o r m sb e t t e rt h a nt h ec o n v e n t i o n a lm e t h o di ng l o b a l p e r s p e c t i v e t h ek e yc o n t r i b u t i o n so fo u rr e s e a r c ha r ed e s c r i b e da sf o l l o w ：f i r s t ，w ep r o p o s e aqv a l u e b a s e dd y n a m i cp r o g r a m m i n ga l g o r i t h mw i t hb o l t z r n a n nd i s t r i b u t i o nf o r o p t i m i z i n gt h eg l o b a lt r a f f i cr o u t i n gs t r a t e g y s e c o n d ，t h ep r o p o s e dm e t h o dh a sb e e n s i m u l a t e db o t hi ns t a t i ct r a f f i cs y s t e ma n dd y n a m i ct r a f f i cs y s t e m t h i r d ，b a s e do n e x p e r i m e n t s ，s o m em e t h o d st oe v a l u a t et h ea l g o r i t h mp e r f o r m a n c eh a v eb e e nu s e d a n ds o m es u g g e s t i o nt oi m p r o v et h ep e r f o r m a n c eh a sb e e n p u tf o r w a r d k e y w o r d s ：qv a l u e ；d y n a m i cp r o g r a m m i n g ；b o l t z r n a n nd i s t r i b u t i o n ；g r e e d y a l g o r i t h m ；g l o b a lo p t i m u m v i 上海大學(xué)碩士學(xué)位論文 原創(chuàng)性聲明 本人聲明：所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作。 除了文中特另i ；d h 以標(biāo)注和致謝的地方外，論文中不包含其他人己發(fā) 表或撰寫過的研究成果。參與同一工作的其他同志對本研究所做的 任何貢獻(xiàn)均己在論文中作了明確的說明并表示了謝意。 簽名：盆阻日期： 本論文使用授權(quán)說明 本人完全了解上海大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即： 學(xué)校有權(quán)保留論文及送交論文復(fù)印件，允許論文被查閱和借閱；學(xué) ?？梢怨颊撐牡娜炕虿糠謨?nèi)容。 ( 保密的論文在解密后應(yīng)遵守此規(guī)定) 簽名：金些蟄 翩躲扯 上海大學(xué)碩士學(xué)位論文 第一章緒論 1 1 課題研究的目的和意義 交通運(yùn)輸業(yè)的發(fā)展水平是國家興旺發(fā)達(dá)的重要標(biāo)志之一。交通運(yùn)輸業(yè)的高 速發(fā)展，一方面促進(jìn)了物資交流和人們的往來，大大地縮短了出行時(shí)間，提高 了工作效率；另一方面也帶來了許多弊病，特別是地面汽車交通運(yùn)輸，不論是 在發(fā)達(dá)國家還是在發(fā)展中國家，都存在著不同程度問題。近半個(gè)世紀(jì)以來，交 通擁擠、道路阻塞和交通事故的頻繁發(fā)生正越來越嚴(yán)重地困擾著世界各國的大 城市。為了提高運(yùn)輸網(wǎng)絡(luò)使用效率，解決交通擁擠和交通安全問題，從六十年 代以來，許多發(fā)達(dá)國家都進(jìn)行了城市交通規(guī)劃研究和交通控制研究【l 】。智能運(yùn) 輸系統(tǒng)就是其成果之一。智能運(yùn)輸系統(tǒng)的研究在發(fā)達(dá)國家起步較早，并取得了 一些比較有影響的成果 2 1 1 3 1 1 4 5 】。特別是美國、德國和日本已經(jīng)開發(fā)出了各 具特點(diǎn)的智能運(yùn)輸系統(tǒng)的雛形。雖然與大面積應(yīng)用尚有一定的差距，但初步試 驗(yàn)表明，該系統(tǒng)在加強(qiáng)交通控制與管理功能方面的作用是不可低估的【6 】。 我國是一個(gè)經(jīng)濟(jì)持續(xù)發(fā)展的發(fā)展中國家，改革開放以來，城市化與汽車化 發(fā)展十分迅猛。改革開放前，城市化水平不足1 9 ，目前已經(jīng)發(fā)展到超過3 0 ， 預(yù)測2 0 1 0 年將接近5 0 ；機(jī)動車擁有量目前已達(dá)6 0 0 0 萬輛，并以每年1 0 以 上的速度增長，預(yù)計(jì)2 0 1 0 年達(dá)到1 3 億多輛。我國城市的大氣質(zhì)量惡化，已逐 步由無煙煤污染轉(zhuǎn)變?yōu)闄C(jī)動車尾氣污染，其主要原因是交通擁堵、車速下降以 及車況差、車輛技術(shù)性能低等，致使在世界十大空氣污染最嚴(yán)重的城市中，我 國就占了7 個(gè)。同時(shí)，車輛狀況差也直接影響到城市交通，并己成為制約我國 城市交通的重要因素。以車況較好的北京市為例，平均日故障次數(shù)達(dá)5 0 0 次以 上，給城市交通帶來巨大壓力 7 】。在此背景下，如何充分發(fā)揮交通設(shè)施的效能， 解決交通擁擠的問題已成為擺在我們面前的重要課題。從交通運(yùn)輸?shù)奈磥戆l(fā)展 趨勢看，為我國的大中城市建立智能交通系統(tǒng)是必要的。 上海大學(xué)碩士學(xué)位論文 1 2 智能運(yùn)輸系統(tǒng)簡介 1 2 1 智能運(yùn)輸系統(tǒng) 智能運(yùn)輸系統(tǒng) 8 】( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s ，簡稱i t s ) ，是將先進(jìn)的 信息技術(shù)、計(jì)算機(jī)技術(shù)、數(shù)據(jù)通信技術(shù)、傳感器技術(shù)、電子控制技術(shù)、自動控 制理論、運(yùn)籌學(xué)、人工智能等有效地綜合運(yùn)用于交通運(yùn)輸、服務(wù)控制和車輛制 造，加強(qiáng)車輛、道路、使用者三者之間的聯(lián)系，從而形成一種實(shí)時(shí)、準(zhǔn)確、高 效的綜合運(yùn)輸系統(tǒng)。i t s 代表了一種全新的理論和思維方式，是人們對提高交 通運(yùn)輸效率進(jìn)行探索的最新成果。 智能運(yùn)輸系統(tǒng)研究主要體現(xiàn)在兩個(gè)方面： ( 1 ) i t s 的實(shí)施技術(shù)研究，主要把電子控制技術(shù)、通信技術(shù)、計(jì)算機(jī)處理技 術(shù)、g p s 定位導(dǎo)航技術(shù)等有效地運(yùn)用到i t s 的各項(xiàng)研究中。目前，在實(shí)施技術(shù) 方面的研究進(jìn)展較大，已經(jīng)取得了較為理想的成果。 ( 2 ) i t s 的基礎(chǔ)理論研究，也是交通流誘導(dǎo)系統(tǒng)理論研究。i t s 基礎(chǔ)理論通 常稱“實(shí)時(shí)動態(tài)交通分配( r e a lt i m ed y n a m i ct r a f f i ca s s i g n m e n t ) 。該理論模型 是美國i t s 研究的“出行和運(yùn)輸管理系統(tǒng) 、“出行需求管理系統(tǒng)”、“公共交通 運(yùn)輸管理系統(tǒng)”、“商業(yè)車輛的運(yùn)營系統(tǒng)”、“應(yīng)急情況的管理系統(tǒng) 、“先進(jìn)的交 通控制和安全系統(tǒng)和歐洲的“d r i v e 、“p r o m e t h e u s ”以及日本的“r a c s ”、 “a m t i c s 、“v i c s 、“s s v s 等領(lǐng)域研究的核心內(nèi)容。 1 2 2 交通流誘導(dǎo)系統(tǒng) 交通流誘導(dǎo)系統(tǒng) 1 】( t f g s ) ，也有人稱之為交通路線引導(dǎo)系統(tǒng)( t r g s ， t r a 伍cr o m eg u i d a n c es y s t e m ) 或車輛導(dǎo)航系統(tǒng)( v n s ，v e h i c l en a v i g a t i o n s y s t e m ) 。它利用全球定位系統(tǒng)( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 、電子交通圖 ( e l e c t r o n i cm a po f t r a f f i cn e t w o r k ) 、計(jì)算機(jī)和先進(jìn)的通信技術(shù)，使得車載計(jì)算 機(jī)能夠自動顯示車輛位置、交通網(wǎng)絡(luò)圖和道路交通狀況，為駕駛員找到從當(dāng)前 位置到目的地的最優(yōu)行駛路線，并協(xié)助出行者方便地進(jìn)入原先沒有去過的地方。 2 上海大學(xué)碩士學(xué)位論文 使用這種系統(tǒng)，能夠有效地防止交通阻塞的發(fā)生，減少車輛在道路上的逗留時(shí) 間，并最終實(shí)現(xiàn)交通流量在網(wǎng)絡(luò)中各路段上的最優(yōu)分配。根據(jù)誘導(dǎo)信息作用的 范圍，t f g s 可以分為車內(nèi)誘導(dǎo)系統(tǒng)和車外誘導(dǎo)系統(tǒng)兩大類。在車內(nèi)誘導(dǎo)系統(tǒng) 中，實(shí)時(shí)交通信息傳輸于個(gè)別車輛和信息中心之間，車輛上安裝有定位裝置、 信息接收裝置和路徑優(yōu)化裝置。由于誘導(dǎo)對象是單個(gè)車輛，因而也稱為個(gè)別車 輛誘導(dǎo)系統(tǒng)。這類系統(tǒng)的誘導(dǎo)機(jī)理比較明確，容易達(dá)到誘導(dǎo)目的。目前各發(fā)達(dá) 國家研究的大部分是這種系統(tǒng)。但其對車內(nèi)設(shè)施和信息傳輸技術(shù)要求較高，造 價(jià)相對昂貴。相比之下，車外誘導(dǎo)系統(tǒng)的交通信息是在車流檢測器、信息中心 和可變標(biāo)牌之間傳輸，誘導(dǎo)對象是車流群，因而也稱為群體車輛誘導(dǎo)系統(tǒng)。這 種系統(tǒng)般適用于高速公路或路段較長的城市交通流的誘導(dǎo)。 發(fā)達(dá)國家的t f g s 一般由三部分構(gòu)成：車輛定位模塊、通信模塊和駕駛員 決策支持模塊。車輛定位模塊的功能是跟蹤車輛在路網(wǎng)中的位置。其輸出既包 括車輛當(dāng)前的絕對位置( 經(jīng)度、緯度和高度) ，也包括車輛在電子地圖上的相對 位置。定位過程主要依靠航位測定、地圖匹配和全球定位系統(tǒng)( g p s ) 完成。 通信模塊負(fù)責(zé)完成車輛和交通信息中心的數(shù)據(jù)交換。車輛利用接收器可以獲得 從交通信息中心發(fā)射來的實(shí)時(shí)交通信息( 當(dāng)前路段的行程時(shí)間、堵塞或事故發(fā) 生地點(diǎn)等) 。同時(shí)，車輛作為流動的交通信息探測設(shè)備，把當(dāng)前的交通信息通過 發(fā)射裝置反饋給交通信息中心。目前廣泛使用的通信方式有射頻通信( 無線電 廣播通信) 、紅外通信、微波通信和蜂窩移動電話通信等。駕駛員決策支持模塊 的功能是進(jìn)行最優(yōu)路徑的計(jì)算和路徑引導(dǎo)信息及其他信息的顯示。最佳路徑的 計(jì)算是t f g s 的關(guān)鍵部分。在進(jìn)行計(jì)算之前，首先由用戶輸入目的地，然后該 模塊根據(jù)定位模塊提供的定位信息和通信模塊提供的當(dāng)前交通狀態(tài)信息計(jì)算出 從當(dāng)前位置到達(dá)目的地的最優(yōu)路徑。所得到的最優(yōu)路徑隨駕駛員的需求不同而 不同，可以是路程最短的路徑，也可以是運(yùn)行時(shí)最短的路徑。路徑優(yōu)化采用較 多的是圖論中的最短路算法和人工智能中的啟發(fā)式搜索算法。最優(yōu)路徑的顯示 可以有三種方式：文本方式、聲音方式和圖形方式。其中文本方式用文字在顯 示器上顯示誘導(dǎo)信息，如“在前面路口向右拐”等；聲音方式通過文語轉(zhuǎn)換和 語音合成單元將文本信息以聲音的形式輸出，這是一種最直接、最有效的方式； 3 上海大學(xué)碩士學(xué)位論文 圖形方式是在電子地圖上用特殊顏色的連線表示出最優(yōu)路徑信息，這是一種常 見的比較直觀的屏幕輸出形式。 交通誘導(dǎo)系統(tǒng)自誕生以來，就受到了人們的普遍關(guān)注。許多發(fā)達(dá)國家如美 國、德國、日本等均將其列入國家研究計(jì)劃，投入了大量的人力、物力和財(cái)力 對其進(jìn)行研究、試驗(yàn)和開發(fā)。目前，研究開發(fā)比較成功的有美國的t r a v t e k 系 統(tǒng)、德國的趾i s c o u t 系統(tǒng)和日本的導(dǎo)航系統(tǒng)等。 1 3 國內(nèi)外研究現(xiàn)狀 1 3 1 國外研究概況 在國外，智能交通系統(tǒng)的發(fā)展以美日歐為代表，通過傳播實(shí)時(shí)信息和主動 管理使道路交通更加順暢、舒適；通過智能汽車和自動駕駛技術(shù)的開發(fā)，使得 安全性得以飛速提高；通過對商業(yè)用車提供信息和引進(jìn)電子通關(guān)功能，使運(yùn)輸 效率得以大幅度提高；通過消除道路堵塞，大大減輕了交通對環(huán)境的負(fù)荷?？?結(jié)文獻(xiàn) 9 1 0 1 1 】，各國研究發(fā)展概況如下。 美國對智能運(yùn)輸系統(tǒng)的研究始于1 9 6 7 年，當(dāng)時(shí)稱其為“智能車一高速公路 系統(tǒng)( i n t e l l i g e n tv e h i c l e h i g h w a ys y s t e m s ，簡稱i v h s ) 。其發(fā)展特點(diǎn)是國家統(tǒng)一 規(guī)劃、投資充足、發(fā)展迅速。1 9 9 4 年美國根據(jù)i v h s 的實(shí)際研究項(xiàng)目，認(rèn)為i v h s 的名稱已不能覆蓋其全部內(nèi)容，因而把i v h s 改為i t s ，并于同年9 月，經(jīng)國會 批準(zhǔn)成立了美國智能交通協(xié)會( r r s a ) 。i t s a 的成員包括聯(lián)邦政府、州政府、 地方政府和外國政府機(jī)構(gòu)，與智能運(yùn)輸系統(tǒng)開發(fā)有關(guān)的國家和國際公司，大學(xué)、 獨(dú)立研究機(jī)構(gòu)、對智能運(yùn)輸系統(tǒng)感興趣的公共團(tuán)體及其他從事智能運(yùn)輸系統(tǒng)活 動的團(tuán)體。它的主要活動為：幫助政府制定政策；組織技術(shù)論壇；幫助發(fā)展標(biāo) 準(zhǔn)、處理橫向問題：促進(jìn)國際合作；管理和交換智能運(yùn)輸系統(tǒng)信息；展示智能 運(yùn)輸系統(tǒng)新技術(shù)；支持地方和州范圍的智能運(yùn)輸系統(tǒng)計(jì)劃；提高公眾對智能運(yùn) 輸系統(tǒng)的認(rèn)識。 美國實(shí)施的智能運(yùn)輸系統(tǒng)取得顯著經(jīng)濟(jì)效益和社會效益。如在密西根州， a t m 使高峰小時(shí)車速提高3 5 ；a t m s 使行駛時(shí)間縮短1 9 ；a v c s 使公共汽 車交通事故率降低2 0 ；自動車輛定位節(jié)約4 0 萬美元年；電子收費(fèi)和交通管 4 上海大學(xué)碩士學(xué)位論文 理使收費(fèi)車道上事故降低為0 ；運(yùn)營費(fèi)用降低1 6 萬美元年。根據(jù)i t s a 2 0 0 2 年 初公布的預(yù)測，到2 0 1 1 年左右，美國智能運(yùn)輸系統(tǒng)將達(dá)到如下一些社會效益： 降低交通事故，每年減少死亡5 0 0 0 7 0 0 0 人；緩解交通擁堵，因此每年節(jié)省2 0 0 億美元支出、1 0 億加侖的汽油消耗和1 3 的出行時(shí)間；提供充分的實(shí)時(shí)交通信 息，以利于出行者做出恰當(dāng)?shù)某鲂羞x擇等。 在歐洲，德、英、法等國于2 0 世紀(jì)8 0 年代初期先后各自研究路徑誘導(dǎo)系 統(tǒng)。但各國的誘導(dǎo)系統(tǒng)互不相容的問題對過境車輛和道路交通管理帶來了不便。 歐洲的智能運(yùn)輸系統(tǒng)推進(jìn)組織是成立于1 9 9 1 年的歐洲道路運(yùn)輸通信技術(shù)實(shí)用 化促進(jìn)組織e r t i c o ，它的目的是協(xié)調(diào)和支持全歐洲的i t s 活動。在該組織的 積極參與下，歐盟自1 9 8 8 年以來在智能運(yùn)輸系統(tǒng)領(lǐng)域相繼實(shí)施了五個(gè)骨干計(jì) 劃，具體計(jì)劃中包括許多項(xiàng)目，其中主要的項(xiàng)目分成兩條戰(zhàn)線。一是由歐盟組 織的為完善道路設(shè)施、提高運(yùn)輸服務(wù)水平的d r i v e 計(jì)劃和t - t a p 計(jì)劃，二是 由民間企業(yè)為主導(dǎo)的為提高歐洲汽車競爭力的p r o m e h e u s 計(jì)劃和改善歐洲 運(yùn)輸機(jī)動性的p r o m o t e 計(jì)劃。這些計(jì)劃的共同特點(diǎn)是它們都是跨國合作的大 項(xiàng)目，其中的子項(xiàng)目有全歐聯(lián)合的、局部地區(qū)聯(lián)合的和單個(gè)國家或城市的，大 多數(shù)子項(xiàng)目由下自上通過公開征集確定。從歐盟2 0 世紀(jì)9 0 年代中期以來先后 實(shí)施的兩個(gè)i t s 骨干計(jì)劃來看，均是包括道路交通運(yùn)輸、航空運(yùn)輸、鐵路和水 路運(yùn)輸及多式聯(lián)合運(yùn)輸?shù)木C合性研究開發(fā)計(jì)劃，表現(xiàn)出比日、美更重視綜合運(yùn) 輸?shù)膇 t s 項(xiàng)目。由此可見，強(qiáng)調(diào)國際( 主要是洲際) 合作和標(biāo)準(zhǔn)化、強(qiáng)調(diào)綜合 運(yùn)輸系統(tǒng)智能化是歐洲i t s 發(fā)展的主要特點(diǎn)。 日本的i t s 發(fā)展幾乎與歐洲同時(shí)起步。1 9 7 3 年，日本進(jìn)行其第一個(gè)i t s 項(xiàng) 目c a c s ，這是世界上第一個(gè)動態(tài)路徑誘導(dǎo)系統(tǒng)。2 0 世紀(jì)8 0 年代中期開始，由 運(yùn)輸省等政府部門組織上百家企業(yè)，會同大學(xué)和研究機(jī)構(gòu)進(jìn)行大規(guī)模聯(lián)合開發(fā)， 形成了官、民、學(xué)協(xié)調(diào)體制，極大地推動了智能運(yùn)輸系統(tǒng)的發(fā)展。2 0 世紀(jì)9 0 年代中期，日本相繼完成了路車間通信系統(tǒng)、交通信息通信系統(tǒng)、廣域旅行信 息系統(tǒng)、超智能車輛系統(tǒng)、安全車輛系統(tǒng)以及新交通管理系統(tǒng)等方面的研究。 在此基礎(chǔ)上，1 9 9 4 年1 月，由日本警視廳、通產(chǎn)省、運(yùn)輸省、郵政省和建設(shè)省 等五個(gè)部門聯(lián)合成立了日本道路、交通、車輛領(lǐng)域智能化促進(jìn)協(xié)會，其使命是 5 上海大學(xué)碩士學(xué)位論文 推進(jìn)i t s 的研究、開發(fā)和利用。在新階段，四省一廳于1 9 9 5 年8 月公布了“公 路、交通、車輛領(lǐng)域的信息化實(shí)施方針”，提出了i t s 研究的九大領(lǐng)域；四省一 廳于1 9 9 6 年7 月提出“推進(jìn)i t s 總體構(gòu)想”，開始了面向i t s 采取綜合的、有 體系發(fā)展的對策，并投入巨資進(jìn)行i t s 的研究、開發(fā)與利用，形成以眾多政府 部門參與，重視技術(shù)、產(chǎn)品開發(fā)和場地試驗(yàn)為特點(diǎn)的全面推進(jìn)日本i t s 建設(shè)的 發(fā)展態(tài)勢。 1 3 2 國內(nèi)研究概況 據(jù)文獻(xiàn) 1 1 6 】顯示，我國從2 0 世紀(jì)8 0 年代初就開始從治理城市交通管理 入手，運(yùn)用高科技來發(fā)展交通運(yùn)輸系統(tǒng)。8 0 年代中期，在廣泛開展城市調(diào)查、 規(guī)劃、治理的同時(shí)，著手對城市交通控制技術(shù)進(jìn)行研究。9 0 年代初，一些高校 和交通研究機(jī)構(gòu)開始了城市交通誘導(dǎo)系統(tǒng)技術(shù)的研究和嘗試，并在北京、上海、 南京等城市做了試點(diǎn)。同時(shí)，北京、上海、沈陽等城市先后從英國、澳大利亞 等國引進(jìn)了s c o ot 或s c a t s 控制系統(tǒng)。這些研究和實(shí)踐，開拓了我國交通 研究新領(lǐng)域，也在一定程度上緩和了當(dāng)?shù)氐慕煌ňo張矛盾。9 0 年代中期至上世 紀(jì)末，中國許多地方陸續(xù)開始智能交通系統(tǒng)的研究，內(nèi)容涉及先進(jìn)的交通控制 和管理、信息系統(tǒng)、通信系統(tǒng)、電子收費(fèi)、環(huán)保和規(guī)劃、運(yùn)輸管理等領(lǐng)域。目 前，我國的智能運(yùn)輸系統(tǒng)還處于發(fā)展的初級階段，需要借鑒國外的先進(jìn)經(jīng)驗(yàn)， 同時(shí)更要從我國的國情、路情出發(fā)盡早解決交通擁擠堵塞問題。 1 4i t s 對城市交通系統(tǒng)的影響 智能運(yùn)輸系統(tǒng)的應(yīng)用會給城市交通系統(tǒng)帶來各種各樣的影響，其中包括對 系統(tǒng)效率有益的影響，當(dāng)然也免不了伴隨著一些無益的負(fù)面效應(yīng)。許多研究者 【1 2 都針對智能運(yùn)輸系統(tǒng)對城市交通系統(tǒng)的影響進(jìn)行了研究。在本節(jié)中，我們 總結(jié)文獻(xiàn)來討論這些智能運(yùn)輸系統(tǒng)給城市交通系統(tǒng)帶來的正面促進(jìn)和負(fù)面影 響。 6 上海大學(xué)碩士學(xué)位論文 1 4 1i t s 的正效應(yīng) 有許多文獻(xiàn)表b 韭 1 2 1 1 3 1 智能運(yùn)輸系統(tǒng)會給城市交通系統(tǒng)帶來好的影響，對 城市交通系統(tǒng)的效率起到促進(jìn)的作用。這些正面效應(yīng)可歸納如下。 1 為交通出行者提供便利： 各國提出i t s 計(jì)劃受到廣泛擁護(hù)的主要原因就在于i t s 為出行者提供先進(jìn) 服務(wù)的誘惑。受到i t s 服務(wù)的出行者可以減少出行時(shí)耗，縮短不必要的行駛里 程，從而省時(shí)、省油，并提高行車安全。具體來說，智能運(yùn)輸系統(tǒng)為駕駛員( 包 括小汽車出行、商務(wù)用車出行、貨運(yùn)車輛出行) 提供的服務(wù)包括： 出行前各類信息服務(wù)：出行前查詢路徑擁堵情況和誘導(dǎo)路徑。 在途駕駛服務(wù)信息系統(tǒng) 先進(jìn)的車輛控制系統(tǒng) 車輛導(dǎo)行系統(tǒng) 其為公共交通出行者提供公交車輛的運(yùn)行狀況信息，減少其等車時(shí)間和出 行中由于不知公交車輛運(yùn)行信息所面臨的不確定性( u n c 腳a i n t y ) 。 2 為交通管理者提供有力的支持： 交通管理者需要在充分了解現(xiàn)有道路交通運(yùn)行狀況的基礎(chǔ)上，做出相應(yīng)的 管理決策。i t s 的實(shí)時(shí)信息采集與處理能力使管理者能夠全面地了解交通運(yùn)行 狀況，能裕如地處理各種道路交通異常情況。其發(fā)布信息能力又使管理者及時(shí) 將決策傳達(dá)給交通行為者，從而實(shí)現(xiàn)高效、安全的目標(biāo)。而且i t s 強(qiáng)大的信息 發(fā)布能力能夠使得交通管理者根據(jù)管理目的，在一定范圍內(nèi)實(shí)現(xiàn)對交通需求的 積極、主動引導(dǎo)，有助于改變其被動地適應(yīng)交通需求的局面。具體來說，交通 管理者的得益體現(xiàn)在： 。 應(yīng)急救援 緩解擁擠 為決策和檢驗(yàn)決策效果提供依據(jù) 改善公交服務(wù)和經(jīng)營 對交通設(shè)施的智能化管理：提高交通設(shè)施的運(yùn)行效率，有效地維修設(shè) 7 上海大學(xué)碩士學(xué)位論文 施。如智能交通設(shè)施( i t i ：i n t e l l i g e n tt r a n s p o r t a t i o ni n f r a s t r u c t u r e ) ； 為企業(yè)的物流運(yùn)輸提供更經(jīng)濟(jì)有效、安全的服務(wù)。 當(dāng)然，對于智能運(yùn)輸系統(tǒng)能否減緩擁擠也存在一些有爭議的觀點(diǎn)。如 k a n n i n e n 認(rèn)為 5 】，人們在擁擠時(shí)段的出行決策顯然是基于以往交通信息的優(yōu)化 后作出的，那么現(xiàn)有的交通擁擠也是由于這種已經(jīng)優(yōu)化了的出行決策經(jīng)過長時(shí) 間均衡后而出現(xiàn)的。因此，路網(wǎng)交通信息的發(fā)布不會改變已有的交通擁擠狀況。 但一些小型路網(wǎng)的模擬研究表明，智能運(yùn)輸系統(tǒng)會改善擁擠狀況。 3 社會的得益： 充分利用道路資源，使路網(wǎng)負(fù)荷均勻化，能夠避免出行者因交通信息 不全而致的路網(wǎng)負(fù)荷不均勻情形。但對于因路網(wǎng)結(jié)構(gòu)不合理所致的負(fù) 荷不均勻問題無明顯效果。 如果不考慮智能運(yùn)輸系統(tǒng)本身建設(shè)的成本，具有同樣結(jié)構(gòu)的交通系統(tǒng) 將以一種更低成本( 用戶費(fèi)用、環(huán)境成本) 的方式滿足同樣的出行需求， 較原有交通系統(tǒng)交通量減少、車速提高、污染減輕。同時(shí)智能運(yùn)輸系 統(tǒng)通過提供各種有選擇的信息服務(wù)，能夠使得出行者的路徑選擇向網(wǎng) 絡(luò)均衡的系統(tǒng)最優(yōu)方向接近。 使得交通流運(yùn)行平穩(wěn)，提高交通安全，減少交通事故。 智能運(yùn)輸系統(tǒng)的運(yùn)行需要大量的電子信息產(chǎn)品，智能運(yùn)輸系統(tǒng)的技術(shù) 發(fā)展與市場需求會推動與其相關(guān)的產(chǎn)業(yè)發(fā)展，增加就業(yè)崗位，促進(jìn)經(jīng) 濟(jì)發(fā)展。 1 4 2i t s 的負(fù)效應(yīng) 在i t s 的應(yīng)用得到一片掌聲的同時(shí)，也有研究者提出了反面的意見。b e n - a l d v a 等 1 4 】認(rèn)為i t s 會對車輛的出行行為帶來不良影響，這些不良影響可能會 使交通系統(tǒng)產(chǎn)生以下三種不良現(xiàn)象： ( 1 ) 信息過剩現(xiàn)象( o v e rs a t u r a t i o n ) ： 信息過?，F(xiàn)象是指出行者由于面對大量的可用信息，不知所措，不能正確 處理路徑選擇所需的信息。該現(xiàn)象是一個(gè)人機(jī)交互作用問題。 8 上海大學(xué)碩士學(xué)位論文 ( 2 ) 過激反應(yīng)現(xiàn)象( o v e rr e a c t i o n ) ： 過激反應(yīng)現(xiàn)象即大量的出行者接受信息誘導(dǎo)，并遵循誘導(dǎo)建議時(shí)，可能會 使一條路段的擁擠轉(zhuǎn)移至另一條路段，甚至使道路的使用產(chǎn)生一種振蕩現(xiàn)象。 只有出行者進(jìn)行出行決策時(shí)，正確預(yù)計(jì)了其他出行者對誘導(dǎo)信息做出的反應(yīng)之 后，過激反應(yīng)現(xiàn)象才會消失，而這在現(xiàn)實(shí)中是十分困難的。 ( 3 ) 集聚現(xiàn)象( c o n c e n t r a t i o n ) ： 大量的出行者根據(jù)真實(shí)的路網(wǎng)交通信息選擇其最優(yōu)出行路徑時(shí)，其中具有 相似偏好的人在相同的出行時(shí)刻會集聚到同一路徑上。由此，越多的交通信息 會導(dǎo)致更加嚴(yán)重的交通擁擠。這說明僅僅向出行者提供出行信息并不一定就能 解決交通擁擠問題，還必須研究出行者在知曉信息時(shí)的出行行為。在此基礎(chǔ)上， 依靠向出行者發(fā)布不同的、分層次的信息可能會減輕負(fù)作用。 另外，a m o t t 等甚至在他們的研究中表明 1 5 】，道路交通信息提供的對象越 少，個(gè)體服務(wù)對象從中得益也越大。而當(dāng)交通信息服務(wù)的對象很多時(shí)，個(gè)體服務(wù) 對象的得益也越少。 1 5 本文研究的主要內(nèi)容 傳統(tǒng)智能運(yùn)輸系統(tǒng)中的車輛誘導(dǎo)系統(tǒng)往往只考慮為某一單一出行者選擇最 佳出行路徑，這也是造成交通系統(tǒng)陷入過激反應(yīng)現(xiàn)象和集聚現(xiàn)象等負(fù)面效應(yīng)的原 因之一。事實(shí)上，在越來越多的出行者開始利用智能交通系統(tǒng)所提供的交通信息 選擇出行路徑的情況下，單單只考慮個(gè)體最優(yōu)是不夠的，提供全局最優(yōu)的車輛誘 導(dǎo)方案才是提高整個(gè)交通系統(tǒng)的運(yùn)行效率，避免交通擁擠，并使個(gè)人出行者也同 時(shí)獲利的最佳方案。因此，本文的第三章中提出了一種新型的啟發(fā)式算法 - - b o l t z m a n n 全局最優(yōu)尋路算法，該算法利用基于q 值的動態(tài)規(guī)劃算法【1 6 】，結(jié) 合b o l t z m a n n 分布 2 3 】，為交通系統(tǒng)尋找近似全局最優(yōu)的配流方案。該算法分別在 靜態(tài)流量的交通系統(tǒng)和動態(tài)交通分配模型中與g r e e d y 簣：法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果 顯示，應(yīng)用b o l t z r n a n n 全局最優(yōu)尋路算法能夠有效地減輕導(dǎo)航系統(tǒng)對車輛行為造 成的負(fù)面影響，為交通系統(tǒng)帶來更高的整體效率。 1 6 論文結(jié)構(gòu)安排 本文分為以下幾個(gè)部分： 9 上海大學(xué)碩士學(xué)位論文 第一章：介紹了課題研究的意義，關(guān)于智能交通系統(tǒng)的一些知識背景，國 內(nèi)外的發(fā)展?fàn)顩r以及本文的研究內(nèi)容。 第二章：首先解釋了動態(tài)規(guī)劃的基本原理，介紹了基于q 值的動態(tài)規(guī)劃 算法的具體流程，然后通過與其他傳統(tǒng)最優(yōu)路徑尋路算法的對比，說明了為什 么在本文提出的全局最優(yōu)尋路算法中要采用基于q 值的動態(tài)規(guī)劃算法計(jì)算各個(gè) 路段到終點(diǎn)的最優(yōu)路徑。 第三章：在本章中重點(diǎn)描述了本文提出的b o l t z m a n n 全局最優(yōu)尋路算法的 基本結(jié)構(gòu)和各部分的具體內(nèi)容。 第四章：展示了b o l t z m a n n 全局最優(yōu)尋路算法在靜態(tài)交通系統(tǒng)中的模擬結(jié) 果。 第五章：介紹了動態(tài)交通分配的背景知識，描述了本文的動態(tài)交通系統(tǒng)采 用的動態(tài)交通分配模型。 第六章：展示了b o l t z m a n n 全局最優(yōu)尋路算法在動態(tài)交通系統(tǒng)中的模擬結(jié) 果。 第七章：論文的總結(jié)以及對未來研究工作的展望。 1 0 上海大學(xué)碩士學(xué)位論文 第二章基于q 值的動態(tài)規(guī)劃最優(yōu)路徑算法 2 1 動態(tài)規(guī)劃簡介 基于q 值的動態(tài)規(guī)劃最優(yōu)路徑算法 1 6 ，是利用動態(tài)規(guī)劃的思想，計(jì)算最 優(yōu)路徑的算法。那么什么是動態(tài)規(guī)劃呢? 在本節(jié)中，我們首先對動態(tài)規(guī)劃作一 個(gè)簡單的介紹。 2 1 1 動態(tài)規(guī)劃的來源 在數(shù)學(xué)上和計(jì)算科學(xué)領(lǐng)域，動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相 似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題 的算法策略。 動態(tài)規(guī)劃這一詞起源于1 9 4 0 年r i c h a r db e l l m a n 對解決多階段決策過程的 優(yōu)化問題的表述。1 9 5 3 年，他又將其賦予了模型意義【1 7 】，被i e e e 歸類于系統(tǒng) 分析和工程的課題。1 9 5 7 年r i c h a r db e l l m a n 出版了他的名著d y n a m i c p r o g r a m m i n g ) ) ，這是該領(lǐng)域的第一本著作。為了紀(jì)念b e l l m a n 的貢獻(xiàn)，用來解 決動態(tài)規(guī)劃問題的核心思想的公式被命名為b e l l m a n 公式。 動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面 得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、 裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要 用于求解以時(shí)間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài) 規(guī)劃( 如線性規(guī)劃、非線性規(guī)劃) ，只要人為地引進(jìn)時(shí)間因素，把它視為多階段 決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。 2 1 2 動態(tài)規(guī)劃的基本思想 動態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，適用動態(tài)規(guī)劃的問題必須滿足最 優(yōu)化原理和無后效性。 上海大學(xué)碩上學(xué)位論文 ( 1 ) 最優(yōu)化原理( 最優(yōu)子結(jié)構(gòu)性質(zhì)) 最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài) 和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策 略。簡而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原 理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持， 就不可能用動態(tài)規(guī)劃方法計(jì)算。根據(jù)最優(yōu)化原理導(dǎo)出的動態(tài)規(guī)劃基本方程是解 決一切動態(tài)規(guī)劃問題的基本工具。 ( 2 ) 無后向性 將各階段按照一定的次序排列好之后，對于某個(gè)給定的階段狀態(tài)，它以前 各階段的狀態(tài)無法直接影響它未來的決策，而只能通過對當(dāng)前的這個(gè)狀態(tài)的影 響來間接影響未來的決策。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。 這就是無后向性，又稱為無后效性。 ( 3 ) 子問題的重疊性 動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài) 規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲產(chǎn)生 過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。選擇動態(tài)規(guī)劃算 法是因?yàn)閯討B(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時(shí)間上卻無法承受， 所以我們舍空間而取時(shí)間。 所以，能夠用動態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征：子問題的重疊性。 這個(gè)性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī) 劃算法同其他算法相比就不具備優(yōu)勢。 舉個(gè)例子，在f i b o n a c c i 數(shù)列中，有f 3 = f 1 + f 2 和f 4 = f 2 + f 3 ，這就使 得f 4 和f 3 的計(jì)算都要f 2 ，而f 4 和f 3 又是計(jì)算f 5 的必要條件。簡單的解決 辦法是用f 2 計(jì)算兩次或者兩次以上來得到f 5 ，但是這樣做非常浪費(fèi)時(shí)間。為 了避免這樣的冗余，我們可以先把f 4 和f 3 計(jì)算完畢后，保存起來，用來計(jì)算 f 5 。也就是說，我們每次都把已經(jīng)解決的問題保存起來，然后在解決后續(xù)問題 時(shí)，采用已經(jīng)得到的結(jié)果。如果我們確定某一子結(jié)果在將來不再會用到，我們 1 2 上海大學(xué)碩士學(xué)位論文 就可以將其拋棄掉了。 一個(gè)標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行： 1 ) 劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意 這若干個(gè)階段一定要是有序的或者是可排序的( 即無后向性) ，否則問題就無法 用動態(tài)規(guī)劃求解。 2 ) 選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)將所處于的各種客觀情況用不同的 狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 3 ) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策 和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出 本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但 事實(shí)上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決 策。 4 ) 寫出規(guī)劃方程( 包括邊界條件) ：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通 用形式化表達(dá)式。 一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，4 ) 這一步還是比較 簡單的。動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就 會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值。 2 2 傳統(tǒng)最短路徑尋路算法分析 不論是傳統(tǒng)智能交通系統(tǒng)中的交通誘導(dǎo)系統(tǒng)，還是本文提出的尋找全局最 優(yōu)路徑方案的新方法，都要先利用智能系統(tǒng)提供的交通信息為每個(gè)出行者尋找 一條通往目的地花費(fèi)最小的路徑。單純尋找一條這樣的路徑并不難，有許多著 名的算法比如d i j k s t r a 算法 1 8 】，a 幸算法【1 9 】 2 0 】等都可以解決這一問題。 2 2 1 d i j k s t r a 算法 d i j k s t r a 算法是1 9 5 9 年由荷蘭計(jì)算機(jī)科學(xué)家艾茲格迪科斯徹發(fā)現(xiàn)的。該 算法解決的是有向圖中最短路徑問題。 給出一個(gè)指定起點(diǎn)的有向圖，該算法可以找到從該點(diǎn)起，到圖中任意一點(diǎn) 的最短路徑，當(dāng)然，如果目的地明確，該算法也可以為單一的起點(diǎn)終點(diǎn)尋找最 1 3 上海大學(xué)碩士學(xué)位論文 短路徑。舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開 車行經(jīng)的距離。d i j k s t r a 算法可以用來找到兩個(gè)城市之間的最短路徑。 d i j k s t r a 算法在其計(jì)算的每一步都為每對起點(diǎn)和終點(diǎn)尋找最優(yōu)路徑。其基本 原理是：每次新擴(kuò)展一個(gè)距離最短的點(diǎn)，更新與其相鄰的點(diǎn)的距離。當(dāng)所有邊 的權(quán)都為正時(shí)，由于不會存在一個(gè)距離更短的沒擴(kuò)展過的點(diǎn)，所以這個(gè)點(diǎn)的距 離永遠(yuǎn)不會再被改變，因而保證了算法的正確性。 該算法在其每一步都進(jìn)行全局搜索，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)為乃邊的數(shù)量為層 時(shí)，其時(shí)間復(fù)雜度可以寫成舊和i 明的大0 函數(shù)。 d i j k s t r a 算法最簡單的應(yīng)用，是將其所有節(jié)點(diǎn)的權(quán)值都存貯在有序的鏈中， 這樣對最優(yōu)值得搜索為線性的，其時(shí)間復(fù)雜度為o ( 1 v 1 2 + l e l ) = o ( 1 v 1 2 ) 。 在稀疏圖中，邊的數(shù)量小- 于l v l 2 ，d i j k s t r a 算法可以通過將圖存在領(lǐng)接表 中，另外用二叉堆，對堆或者f i b o n a c c i 堆等排序法尋找最小權(quán)值節(jié)點(diǎn)，來提 高算法的效率。當(dāng)應(yīng)用二叉堆時(shí)，該算法需要的時(shí)間復(fù)雜度為 o ( ( 1 v l + l e i ) , o g l v i ) ；如應(yīng)用f i b o n a c e i 堆，則時(shí)間復(fù)雜度為o ( i e i + i v i l o g i v i ) = d ( 吲) = o ( i v l 2 ) 。d i j k s t r a 算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算 的節(jié)點(diǎn)很多，所以效率低。 2 2 2a 算法 在計(jì)算科學(xué)中，a 幸算法是用來尋找從單一起點(diǎn)到單一終點(diǎn)的最短路徑搜索 算法。該算法與d i j k s t r a 算法很類似，但在計(jì)算邊的權(quán)值時(shí)其引入了一個(gè)啟發(fā) 式函數(shù)。在該算法中，從起點(diǎn)經(jīng)過某一節(jié)點(diǎn)刀到終點(diǎn)的最小權(quán)值為 f ( n ) = g ( ，z ) + j l l ( 咒) ；其中，g ( n ) 是從起點(diǎn)到節(jié)點(diǎn)n 的最小權(quán)，h ( n ) 為從萬到終 點(diǎn)的評估權(quán)。由于h ( n ) 是一個(gè)啟發(fā)式函數(shù)，它的估計(jì)值不能超過從r l 到終點(diǎn)的 真實(shí)距離，以保證算法的正確性。所以在將該算法應(yīng)用在如尋找交通最短路徑 等問題時(shí)，一般會讓其等于兩點(diǎn)之間的直線距離，因?yàn)閺奈锢砩蟻碚f，該距離 是兩點(diǎn)間的最短距離，它總是小于或等于兩點(diǎn)間的實(shí)際行駛距離。 1 4 上海大學(xué)碩士學(xué)位論文 1 9 6 8 年，p a e rh a r t ，n i l sn i l s s o n 和b e r t r a mr a p h a e l 第一次在他們的論文 中描述了該