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