（運籌學與控制論專業(yè)論文）多類別多目標交通網(wǎng)絡均衡研究.pdf

論文獨創(chuàng)性聲明 本論文是我個人在導師指導下進行的研究工作及取得的研究成果。論文中除 了特別加以標注和致謝的地方外，不包含其他人或其它機構已經發(fā)表或撰寫過的 研究成果。其他同志對本研究的啟發(fā)和所做的貢獻均已在論文中作了明確的聲明 并表示了謝意。 。 作者簽名： 論文使用授權聲明 日期：生! ：少 本人完全了解復旦大學有關保留、使用學位論文的規(guī)定，即：學校有權保留 送交論文的復印件，允許論文被查閱和借閱；學?？梢怨颊撐牡娜炕虿糠謨?容，可以采用影印、縮印或其它復制手段保存論文。保密的論文在解密后遵守此 規(guī)定。 作者簽名：芝叁壘拉導師簽名：日期：尊墨：彳 摘要 現(xiàn)代社會中，隨著通訊手段、交通方式越來越發(fā)達，人與人之間的聯(lián)系越來 越緊密，關系錯綜復雜，各種網(wǎng)絡結構也在社會生活中日趨增多。我們常見的基 礎網(wǎng)絡支撐著我們整個經濟和社會活動，為商業(yè)、科學、技術、社會系統(tǒng)以及教 育提供了所需的各種基礎設施。另外，無形的邏輯網(wǎng)絡，如信息交流網(wǎng)絡等，也 是基礎網(wǎng)絡的重要的補充形式，使人們能夠更加高效的完成更為復雜的活動或任 務。網(wǎng)絡結構無處不在，他們的作用超乎想象，離開了網(wǎng)絡，人類將無所適從。 由于網(wǎng)絡系統(tǒng)在人類生活占據(jù)著越來越重要的地位，對網(wǎng)絡及網(wǎng)絡均衡的研 究也越來越引起學者的興趣。在網(wǎng)絡系統(tǒng)中，參與的實體數(shù)量很多，各自擁有自 己的行為方式和目的，網(wǎng)絡經過長期的運行，能否達到均衡，或達到怎樣的一種 均衡狀態(tài)是目前研究的焦點。而建立什么樣的模型來描述網(wǎng)絡及其用戶之間的關 系才能更確切的體現(xiàn)實際背景也是研究的熱點。網(wǎng)絡均衡的建模和求解這兩方 面，構成了網(wǎng)絡均衡研究領域的核心內容。 本文研究的主要是具有多類別多目標的交通網(wǎng)絡均衡問題，結合經典均衡理 論和人工智能領域的m u l t i - a g e n t 技術，建立m a s ( m u l t i - a g e n t s y s t e m ) 仿真模 型，通過系統(tǒng)循環(huán)運行的過程求得均衡解。文中首先概括的描述7 具有無窮類出 行者，每位出行者都具有多個目標的無限維網(wǎng)絡均衡問題，并對其解的存在唯一 性條件作了說明。為了符合工程計算和仿真系統(tǒng)的基本要求，提出了一種離散化 的方法，將無限維交通網(wǎng)絡均衡問題轉化成有限維的網(wǎng)絡均衡問題，并對收斂性 和精度都進行了分析證明，從而從理論上保證了求解無限維交通網(wǎng)絡均衡問題的 近似解完全可以基于離散化后的有限維形式。在此基礎上，將模型轉為基于 m u l t i a g e n t 技術的仿真系統(tǒng)，定義了出行者a g e n t d 網(wǎng)絡a g e n t 的屬性和方法，設 計了一套有效的系統(tǒng)工作流程，并從理論上分析了收斂性和精度。本文最后將這 種m a s 仿真建模的方法擴展到更復雜的均衡模型一港口競爭策略設計問題。不 僅涉及到靜態(tài)均衡的求解，還擴展到兩個處于競爭關系的港口帶有博弈性質的策 略設計，使模型的意義拓展到策略設計和均衡狀態(tài)互相影響的層面。 總之，本文的主要貢獻在于，建立了m a s 交通均衡仿真系統(tǒng)，為無限維多 目標的交通均衡問題提供了一種便于工程計算和操作的解決方法，也為其他更復 雜的均衡問題求解提供了新的思路。 關鍵詞：網(wǎng)絡均衡，無限維，多目標，m u l t i - a g e n t ，仿真 中圖分類號：f 2 2 4 3 3 a b s t r a c t i nm o d e m s o c i e t y , v a r i o i l sc o m m u n i c a t i o nm e a n sa n dt r a n s p o r t a t i o nm e t h o d sa r ed e v e l o p i n g w i t hv e r yf a p i ds p e e d , t h e r ea m a n y 咖cc o n n e c t i o n sa m o n gp e o p l e wt h a ns e v e r a ly e a r sa g o , l o t so fu e t w o r kf r a m e w o r k ss h o wt h e i rb e n e f i t st oo u rp r o d u c t i o na n dl i f em o r ef r e q u e n t l y , a n d t h e yh a v em y f o r m s b a s i cn e t w o r k ss u p p o r tm l fe c o n o m i ca n ds o c i e t ya c t i v i t i e s , a n dp r o v i d e v a r i o u si n f r a s l m c t u r e sf o rb u s i n e s s , s c i 蛐o e t e c h n o l o g y , a n de d u c a t i o n t h o s en e t w o r k sw h i c h h a v en od e f i n i t ef o r m , s u c ha si n f o r m a t i o ne x c h a n g en e t w o r ka m o n gp e o p l e , a r ea l s ot h e s u p p l e m e n t st ob a s i cn e t w o r k , a n dt h e yh e l pu sa c c o m p l i s hm o r ec o m p l i c a t ea c t i v i t i e so rt a s k s n e t w o ai se v e r y w h e r e , i n c l u d i n gt r a n s p o r t a t i o nn e t w o l k ，c o m p u t e rn e t w o r k , f i n a n c i a ln e t w o 盤 a n dc o m m u n i c a t i o nn e t w o r ke t e ，a n dp e o p l eu t i l i z en e t w o r kt or e a l i z em o v e m e n to fg o o d sa n d f u n d s , t r a v e lo fp e o p l e a n dm a n yi n f o r m a t i o ne x c h a n g e w em s a yt h a to u rs o c i e t yw i l lb ei n m o s sw i t h o u tn e t w o r k s i n c en e t w o r ks y s t e m sb e m e 肼ea n dm o r ei m p o r t a n ti nh u m a n s o c i e t y , t h en e t w o r ka n d i t se q u i l i b r i u ma r i s ev a r i o u sr e s e a r c h e si np a s td e c a d e s i nn o r m a ln e t w o r ks y s t e m ， m i l l i o n so fe n t i t i e sa r ei n v o l v e di no n en e t w o r k , a n dt h e yh a v en oc o m i l l o nb e h a v i o r a n do b j e c t i v e w h e t h e rt h er e i t e r a t i o no ft h eu s e r s c h o i c e sw i l lr e s u l ti na n e q u i l i b r i u mw h i c hm e a n st h a tt h e r ea 托n on e t w o r ku s e r sw h oc a ni m p r o v eh i s h e r s i t u a t i o nt h r o u g ha n yu n i l a t e r a la c t i o n s , a n df u r t h e rw h a tt h ee q u i l i b r i u mw i l lb ef li ti s a c h i e v a b l e b e c o m ea t t r a c t i v ea r e ao fr e s e a r c h t h em o d e l i n ga n ds o l v ef o rt h ee q u i l i b r i u mo f t h e n e t w o r k s y s t e m s a l e m u s t i u l p o r tr e s e a r e h e s 虹t h i s 銣r e a ht h i sw o r kw ec o n s i d e ra ne q u i h l d r i n mp r o b l e mw i t hi n f i n i t e l ym a n yd i f f e r e n t i a t e d c u s t o m e r sa n dm u t io b j e c t i v e s w ec u l l i g e t ee x i s t i n gv a r i a t i o n a li n e q u a l i t yp r o b l e mt h e o r i e sa n d m u l t i - a g e n tt e c h n o l o g yw h i c hs e e m sh e a ni m p r e s s i v ep r o d u c t i o ni nt h ea r e ao fa r t i f i c i a l i n t e l l i g e n c e , t oe s t a b l i s hme f f e c t i v em o d e lf o rs o l v i n gt h ee q u i l i b r i u mp r o b l e mw eh a v e m e n t i o n e d t h i sp a p e rf i r s tp r o v i d e st h es u m m a r i z a t i o no ft h ee q u i l i b r i n mw o h i e m , a l s ow i t h i l l u m i n a t i o no ft h ee 】i s t e n c ea n du n i q u e n e s sa n a l y s i sf o ri t ss o l u t i o n ad i s c r e t i z a t i o na p p r o a c hi s a l s oc o n s t r u c t e dt o f a c i l i t a t et h ee n g i n e e r i n gc o m p u t a t i o na n dm a ss i m u l a t i o ns y s t e m , w h i c h e n a b l e smt o 燈a u s f e rt h ci n f i n i t e l yd j m e n t i o n a ip r o b l e mi n t of i n i t e l yo a n dw ee v e np r o v et h e c o n v e r g e n c ea n da c c u r a c yo f s u c ham e t h o d , w h i c he n s u r et h ef e a s i b i l i t yo ft h es i m u l a t i o ns y s t e m b a s e do nm u l t i - a g e n t as i m u l a t i o nm o d e lo ft h et f a f f i cu e t w o r ke q u i l i b r i u mi sp r o p o s e d t h e m o d e ld e s 口抽dd i f f e r e n tb e h a v i o ro tv a r i o u st r a v e l e r sa sw e l la st h e i rd e c i s i o n sm a k i n g a n dt h e a g g r e g a t i o ne f f e c to nt h ew h o l en e t w o r ki so b s e r v e dt h r o u g ht h es i m u l a t i o n w i t ht h ec l a s s i c a l 2 t h e o r yf o rt h ee q u i h b r i u m , w eo b t a i n e dan c ws o l u t i o nt ot r a 伍cn e t w o r ke q u i h b r i n mp r o b l e mt h a t i sn m i n t o i t i o n i s f i ca n de f f i c i e n t a tt h ee n do ft h i s p a p e r , t h em o d e lo ft r a f f i cn e t w o r k e q u h b r i n m 豇e x p a n d e dt os t r a t e g yd i 罟丑i n go f c o m p e t i t i v eh a v e n s ，w h i c hm e a nm o r ec o m p l e x b a c k g r o u n df o r 刪c h e s t h ei n n o v a t i v ep o i n to f t h i st h e s i sl i e si nt h ef o l l o w i n ga s p e c t s ：( 1 ) i ti n t m d u c 8t h em o d e lo f 仃棚cn e t w o r ke q u i l i b r i u mw i t hi n f i n i t e l ym a n yd i f f e r e n t i a t e dc u s t o m e r sa n dm u l t i - o b j e c t i v e s ( 2 ) t h em a sm o d e lj se x p a n d e dt os t r a t e g yd e s i g n i n go fc o m p e t i t i v eh a v e n s , w h i c hl e a d st h en w t h i n k i n gt oal n o r ep r o s p e c t i v ea r e a k e yw o r d s ：n e t w o r ke q u i l i b r i u m , i n f i n i t e l yd i m e n t i o n a l ，m u l t i - o b j e c t i v e s , m u l t i - a g e n l s i m u l a t i o n c l c ：f 2 2 4 3 3 3 多類別多目標交通網(wǎng)絡均衡研究 第一章緒論 1 1 問題背景 網(wǎng)絡系統(tǒng)在人類社會生活中扮演著重要的角色，支撐著我們整個社會經濟系 統(tǒng)，提供了商業(yè)、科學、技術、社會系統(tǒng)以及教育所需的基礎設施。交通網(wǎng)絡、 計算機網(wǎng)絡、通信網(wǎng)絡、金融網(wǎng)絡等，是我們日常生活中常見的網(wǎng)絡，人們通過 網(wǎng)絡實現(xiàn)物流運輸，出行旅游，資金轉移，以及各種信息的溝通交流。離開了網(wǎng) 絡，人類的生活幾乎無法正常運行。交通網(wǎng)絡為我們提供了出行的硬件支持，使 我們可以去走親訪友，旅行并拓展我們的視野等，并且它支撐了生產系統(tǒng)的運作 和原材料的運輸，以及最終產品的分銷派送。我們擁有各種各樣的方式實現(xiàn)人和 物的空間轉移，如飛機，火車，汽車，輪船等。通訊網(wǎng)絡使我們能夠跨越國界， 打破地域限制與同事、朋友，親人交流感情，信息，數(shù)據(jù)等，通過通訊方式的一 些革新，例如因特網(wǎng)和移動電話的發(fā)展，通訊網(wǎng)絡甚至改變了我們今天的生活， 創(chuàng)造了新的工作和學習的方式。能源網(wǎng)絡對網(wǎng)絡經濟的存在至關重要，它為交通 網(wǎng)絡，通訊網(wǎng)絡，金融網(wǎng)絡等提供必需的動力儲備。金融網(wǎng)絡將社會中閑置的資 金集中起來，為那些需要資金迅速擴張的企業(yè)，實體提供關鍵的資金支持，使得 他們能夠最好的適應客戶的需求。 目前，研究比較集中和成熟的主要有交通網(wǎng)絡、計算機網(wǎng)絡、運輸網(wǎng)絡等。 網(wǎng)絡的基本特征是具有節(jié)點、弧、容量，節(jié)點表示網(wǎng)絡中的中轉點，弧表示節(jié)點 間的聯(lián)系，節(jié)點或弧可以接納的最大量稱為容量。網(wǎng)絡的優(yōu)勢是能夠清晰表示網(wǎng) 絡參與者之間的復雜關系，可以用互相聯(lián)系的觀點和方法來分析網(wǎng)絡中單個節(jié)點 和弧或者整個網(wǎng)絡。對網(wǎng)絡的研究可以分成以下幾個方面，一是網(wǎng)絡結構特征研 究，二是網(wǎng)絡中流量分配，三是網(wǎng)絡設計和規(guī)劃。 在典型網(wǎng)絡中，如交通網(wǎng)絡，網(wǎng)絡中的客流是出行者自行決定得出的，每位 出行者自行選擇所行道路，既追求出行時自j 盡量短，又希望出行成本盡量低。因 此，出行者是具有多目標的。而網(wǎng)絡中的出行者往往不是同質的，對多個目標， 不同的出行者會有不同的優(yōu)先關注程度，這使得路徑選擇更加復雜化。 另一方面交通網(wǎng)絡的成本結構不是固定不變的，它受到客流分配的影響。路 徑的出行成本是與流量密切相關的，因此出行者對路徑的選擇受客流分配的影 響；反之，路徑選擇又導致路徑流量的變化，從而影響路徑出行成本，如此循環(huán) 4 反復，最后達成一種均衡狀態(tài)。在其他很多網(wǎng)絡中，其實都存在著這樣的均衡， 因此研究具有多目標多類別出行者的網(wǎng)絡均衡問題將具有更大的實際意義。 從網(wǎng)絡設計決策者的角度出發(fā)，均衡的狀態(tài)未必是所期望的狀態(tài)，他們需要 考慮采取某種手段來控制或影響網(wǎng)絡使用者的選擇，影響網(wǎng)絡均衡，來優(yōu)化整個 系統(tǒng)。當網(wǎng)絡中有多個設計決策者，并且他們之問是競爭關系，那么網(wǎng)絡的均衡 狀態(tài)將受到他們競爭策略設計的影響。 關注具有多類別用戶的網(wǎng)絡均衡問題，以及基于這類網(wǎng)絡均衡的競爭策略設 計問題，引發(fā)了本文的研究。 1 2 相關研究綜述 n a s h 均衡理論的提出是2 0 世紀最重大的科學進展之- 1 1 1 ，它對經濟學和社 會科學的影響巨大。 近年來，均衡理論被用來分析很多管理科學問題，特別是供應鏈管理問題， 交通網(wǎng)絡問題。均衡理論解的存在性、理論和算法的研究，已引起國內外眾多學 者的極大興趣，并得到了很多結果。研究結果大部分是關于存在性【2 ，3 】和應用。 經典的交通網(wǎng)絡均衡問題，是指交通網(wǎng)絡中的所有出行者都尋求從出發(fā)點到 目的地的成本最低的出行路線。這個問題最早是n h p i g o u 在1 9 2 0 提, q 4 來的，并且 基于網(wǎng)絡中只有兩個頂點和兩條路線的假設。 w a r d r o p 在1 9 5 2 年提出了定義交通均衡的兩個原則： ( 1 ) 從一個起點到一個終點，所有用到的路線上的旅行時間是相同的，并且 不超過未被用到的那些路線上的旅行時間。 ( 2 ) 整個交通網(wǎng)絡系統(tǒng)中，平均的旅行時間達到最小。 1 9 5 6 年b e c k m a n n 等人提出的在成本函數(shù)可分離情況下的網(wǎng)絡均衡最優(yōu)化方 法，進一步促使了網(wǎng)絡均衡理論有了飛躍性的發(fā)展，使其在實際問題中的應用得 到了長足的進步。b e c k m a n n 等人還實現(xiàn)了通過一個優(yōu)化問題和k t 條件來求均衡 解。但是，用優(yōu)化問題來求解均衡解是基于成本函數(shù)可分離的假設的，而對一般 的非對稱交通網(wǎng)絡，這樣的方法并不有效。在過去的幾十年中，交通網(wǎng)絡均衡問 題無論在模型還是算法方面都經歷了快速的發(fā)展。1 9 8 0 年d a f e r m o s 成功實現(xiàn)了用 變分不等式求解一般的非對稱交通網(wǎng)絡均衡問題。包括有多個起點和多個終點的 情況，以及有多類別出行者的情況，這是最引入注目的成果和進步。 1 9 6 6 年，學者p h i l i ph a r t m a n 和g u i d os t a m p a c , c h i a 幾乎同時提出了變分不等式 的概念，并0 , 4 s t a m p a c c h i a 對此類問題進行了推廣。變分不等式問題描述為：在可 行集合c 中，尋找向量x ，使得對于任何的x e c ，向量x 滿足不等式 ( f o 玲一z ) 2 0 an a g u m e y 4 和p a t r i c k t h a r k e r , j o n g - s h ip a n g 5 系統(tǒng)地回顧 5 和總結了傳統(tǒng)單調條件下的變分不等式問題的理論、算法和應用，為我們的學習 提供了方便有效的參考。 變分不等式雖然為一般交通均衡問題的求解提供了有效的求解途徑，但是變 分不等式本身的算法都是基于一些連續(xù)的運算，如積分等，并且為了確保算法的 收斂性，還會受到用很多條件的約束。因此，變分不等式雖然使得交通均衡問題 在理論意義上得到了很好的解決方式，但是在實際離散化的工程計算和應用中， 還是具有很大的局限性。 1 9 9 4 年，d lz l l u 和p m 刪t t e 6 提出了一種具有無限類出行者，且每位出 行者具有多目標的擴展的交通網(wǎng)絡均衡問題，并對均衡解存在性進行了分析證 明，最后提出了基于變分不等式的有效算法。d lz l l u 和p m a r c o t t e 在1 9 9 r 7 年又 提出了一種更有效的算法陰。這兩種算法從理論上提供了解決具有無限類、多 目標出行者的交通網(wǎng)絡均衡問題的方法，但是仍然沒有避免連續(xù)性算法的局限 性，工程應用的可操作性不強。 本文將更多的從應用角度出發(fā)，并考慮具有多類別、多目標出行者的情況， 希望基于離散化方法，并借助人工智能領域的技術，得到有效的模型及解法。 1 3 人工智能前沿一智能主體( a g e n t ) 伴隨著人工智能的高速發(fā)展，智能主體作為人工智能發(fā)展的前沿技術引起了 人們的廣泛注意。a g e m 理論是一個計算機科學和人工智能中發(fā)展很快的前沿領 域，目前，a g e n t 己經成為許多領域中通用的概念【8 ，9 】，它代表著一種新的研究 方法的誕生，并推動著人工智能走出低谷從而獲得新的生機。在國內，a g e n t 有 多種譯法，如：“主體”、“智能主體”、“智能代理”等等。但大多還是直接以a g e n t 出現(xiàn)。a g e n t 理論研究十分重視跨學科之間的交叉和橫向聯(lián)系，因此具有很大的 難度與挑戰(zhàn)性。它所涉及的知識面更是極為廣泛，包括計算機科學、人工智能乃 至哲學、經濟學、社會學、系統(tǒng)論、博弈論等各學科領域。更重要的是，a g e u 理論在人工智能的發(fā)展史上首次深入的將人類智能活動的社會性作為研究和應 用領域。它使原本基于物質和硬件的人工智能具有了豐富而深刻的社會內涵，能 表現(xiàn)出人類智能中來源于社會行為的復雜性和多樣性，并突破了傳統(tǒng)人工智能研 究一般僅集中于個體智能而回避由個體之間的社會互動性而產生集體效應的局 限性。同時它無論從概念還是方法上都有著一系列本質的創(chuàng)新，使我們能從一個 全新的視角，來看待和研究經典的問題，最終促使我們對人工智能的研究達到一 個更為深刻的洞察與把握。 6 1 4 本文研究的問題 在具有多目標多類別出行者的交通網(wǎng)絡均衡問題中，根據(jù)出行者某一主要特 性的區(qū)別，將其描述為用一個連續(xù)概率分布表示的差異化群體，我們定義這樣的 網(wǎng)絡為無限維交通網(wǎng)絡。本文主要針對這一類無限維的交通網(wǎng)絡均衡問題，結合 經典的變分不等式理論和人工智能領域正在迅速發(fā)展中的a g t 理論展開研究。 最后還將模型拓展到港口競爭策略設計這一更復雜的背景。 第二章：無限維交通網(wǎng)絡均衡問題的離散化。這一章首先描述了無限維的交 通網(wǎng)絡均衡問題的基本構架和形式，提出了存在唯一均衡解的條件，并從經典理 論的角度進行了分析和闡述。在這基礎上，為了保證工程計算和基于a g e n t 理論 的仿真系統(tǒng)的可行性，我們對這個連續(xù)形式的無限維網(wǎng)絡均衡問題進行了離散 化，并證明了在某些條件的約束下，離散化后的有限維交通網(wǎng)絡均衡問題的解存 在且唯一，且當分割細度足夠小的情況下，離散化問題的均衡解通過一定的變換 將逼近無限維問題的均衡解。離散化的工作為下面基于m u l t i - a 罾c n t 的仿真系統(tǒng)來 求解近似均衡解奠定了基礎。 第三章：a g e n t 技術的發(fā)展及應用介紹。介紹了a g e n t 的概念特征、模型結 構等。同時又引入了系統(tǒng)仿真方面的基本原理，和基于m u l t i a g e n t s y s t e m ( m a s ) 的系統(tǒng)仿真建模。介紹了廣泛應用于面向對象技術中的統(tǒng)一建模語言u m l ，并 推廣到適用于面向a g e n t 系統(tǒng)的a u m l 擴展性建模語言，為第四章中m a s 建模 和仿真系統(tǒng)的運行提供了技術支持。 第四章：基于a g e n t 理論的網(wǎng)絡均衡模型。在這一章，我們在第二章得到的 離散化形式的基礎上，建立t m u l t i - a g e n t 仿真系統(tǒng)，將交通網(wǎng)絡中不同類別的出 行者和網(wǎng)絡本身都作為a g e n t 參與到模擬循環(huán)過程中，最終通過一定的學習法則、 判斷法則使系統(tǒng)在達到近似均衡狀態(tài)時停止，從而求得了近似均衡解。同時，還 對這種系統(tǒng)的工作過程的可行性進行了分析，證明了在一定的條件下，通過這樣 的循環(huán)和學習過程，系統(tǒng)必能在有限時間內達到可接受范圍的近似均衡狀態(tài)，即 收斂性得到了保證。最后，還將模型拓展到港口競爭策略設計問題，建立了更復 雜、更具應用背景的m a s 模型，從而將a g e n t t 里論的應用推廣到了更廣闊的層面。 第五章：總結與展望?？偨Y全文的觀點，并對應用m u l t i - a g e n t 技術解決均衡 闖題的下一步研究方向進行展望。 7 第二章無限維網(wǎng)絡均衡問題及離散化 2 1 問題描述 我們假設在一個由頂點和邊組成的交通網(wǎng)絡系統(tǒng)中，出行者是具有多類別和 多目標的。所謂多目標，是指出行者既追求出行時間盡量短，又希望出行成本盡 量低。因此，將這兩個目標結合起來，所有出行者都根據(jù)自身的特征，追求效用 的最大化。這里“效用”是一個廣義“成本”的概念，指的是出行時間和道路收 費的加權總和，即將旅行時間乘以一個v o t ( v a l u eo f t i m e ) 參數(shù)后再與道路收 費相加得到的指標量。這里出行者是具有多類別的，每個出行者的v 0 哦參數(shù)并不 是固定的，而與出行者本身的特征有關，并假設出行者的數(shù)量在整個系統(tǒng)中關于 v 0 t 參數(shù)值服從一定的連續(xù)的概率分布。出行者選擇任何路線的成本將視為經過 該路線所包含的所有道路的成本累加。 我們假設： ( 1 ) 出行者經過任意一條邊a 的時間花費函數(shù)只( x ) 是關于x 連續(xù)單調的。 ( 2 ) v ( ) t 參數(shù)的概率密度函數(shù)妒似) 是連續(xù)的。 本文以后的討論，都將基于以上假設，后面不再重述。 為了更清楚的描述模型，將所用的標志符號列于下表： g = ( n a ) 網(wǎng)絡系統(tǒng) 頂點集( 包括出發(fā)點，目的點，中間連接點) k網(wǎng)絡中所有連接出發(fā)點和目的點的路線集合 b需要通過出發(fā)點和目的點的總出行者流量 口 出行者的v o t 參數(shù)，滿足a e 0 , a 。】 妒位) v i 弧參數(shù)的概率密度函數(shù) x 國 邊上( 關于參數(shù)口) 的流量密度o a z 陋)以向量形式表示的網(wǎng)絡中各邊上的流量密度 x 邊4 上的總流量：x - p 缸矽a r- x以向量形式表示的網(wǎng)絡中各邊上的總流量 以 ) 路線七k 上( 關于參數(shù)口) 的流量密度 h ( a ) 以向量形式表示的網(wǎng)絡中各路線上的流量密度 8 h t 路線七足上( 關于參數(shù)口) 的總流量：日t f ：o - - h k ( a ) d a h 以向量形式表示的網(wǎng)絡中各路線上的總流量 e 暖) 出行者經過邊口的時間花費函數(shù) f 伍) 向量形式的各邊的時間花費函數(shù) l 邊n 的道路收費 t各邊的道路收費組成的向量 為了確保模型的合理性，必須使流量守恒且非負，加入以下約束條件： 薈 ， ) 1 6 妒 ) v 口 h p 以) 0 v k e k ，v a 邊流量與路線流量之間應有如下對應關系： 毛 ) 。薹6 以以) v a e a , v 口 其中 ?；碛诼扶?可以將屯，v a e a ，、f p e k 組成一個系數(shù)矩陣，則邊與路線的對應關系可寫為 矩陣形式： 工( 口) - a ( 睇) 和x - a h h ( a ) - a r x ( a ) f l 鉑h 一鰱x 于是有 q ) - 偽 ) 之o ：丕 ) - 6 妒 ) z 似) 一a q ( 口) - x ( 口) ：| j l ) q 似) ：x ) - a h ( a ) ) 其中妒( 口) 是處處非負的概率密度函數(shù)，且符合緊約束： 妒( a ) ) - 0 口矗 ，：_ 妒 一1 邊形式網(wǎng)絡均衡問題就是找均衡流量工滿足變分不等式： x z ( f 暖) + 叮，工一工) o v x z ( 2 。1 ) 其中，z 是缸( 0 ，口。爐l 的子集，且 9 z 。* 缸( 0 ，爐：工o ) z ) ，v a 如，v ) 一f 如 ) v ) p 口 路徑形式網(wǎng)絡均衡問題就是找均衡流量h 滿足變分不等式： 礦q(2-2) p ( f 餌) + 0 1 3 ，y h + ) o q 其中q 是仁( o ，口蝴目的子集，令雄。陋i ，彳。也1 ，1 l ， q l e l 2 ( o ，口。) p ：a h ( a ) 。6 妒( 口) ， ( 口) 急0 v 口f o ，a 一】 ， 它的含義是，對任意的v 滲數(shù)傻，它所對應的那些出行者分布在各條路徑上的 流量之和應該等于他們的總數(shù)。這是符合網(wǎng)絡流的基本原則的。 根據(jù)均衡的定義，所有出行者根據(jù)成本向量f 僻) + 胡和自己的v o t 參數(shù) 值選擇了成本最小的路線，這時系統(tǒng)狀態(tài)一定構成了網(wǎng)絡均衡狀態(tài)x 2 2 解的存在唯一性分析 在這一節(jié)中，我們將圍繞上文介紹問題的解的存在性和唯一性作一些討論， 存在性是討論一切其他問題的前提，解的唯一性也將使很多討論大大簡化。由 2 1 的定義，邊形式和路徑形式網(wǎng)絡均衡只是從不同角度來描述均衡狀態(tài)，在本 質上是一致的，因此在本文中，我們僅對路徑形式的網(wǎng)絡均衡問題作研究。 我們首先引入這樣一個無窮維線性規(guī)劃問題： l p ： 曾p ( f ( 廁4 - a t ) , y ) q - b 仁( o ，) ：a y ( a ) 6 妒 ) ) ，以) 0v 口( o ，) 其中廳為固定向量。這個線性規(guī)劃對分析變分不等式( 2 2 ) 有著重要的作用。 目標函數(shù)代表了在假定網(wǎng)絡成本函數(shù)固定( 與流量分配無關) 的情況下，所有網(wǎng) 絡出行者成本的累加，也就是說，當所有出行者都選擇了對自己成本最低的路徑， 則目標函數(shù)也一定是達到了最小。 我們定義 ，q 一侈r 。：a y b ，y 2 0 凸是一個線性空間，則可以進一步的將( 2 - 3 ) 拆分成無窮個線性規(guī)劃問題： v a 【o ，) l o l p ( a ) ： 嘧( r ( f ( a 西+ a t ) ，y ) ( 2 4 ) q 。p 足。：a y b ，y 土0 顯然對于任意固定的口值，l p ( a ) 是一個普通的線性規(guī)劃問題。根據(jù)( 2 2 ) 中a 的定義，6 是個緊凸集，上，陋) 的最優(yōu)解是存在的，且必定是6 的某個( 可 能是多個) 極點，使得目標函數(shù)最小。從直觀意義上來說，即v i 時參數(shù)為口的出 行者選擇了成本最低的路線，當( 2 4 席多個最優(yōu)解時，代表出行者有多條路線選 擇使成本最低。 為了進一步研究( 2 3 ) 和( 2 - 2 ) ，我們引入以下定義和條件。 令礦，f - 1 ，為6 的n 個極點，并且 f i 兩- ( a r f ( a a 一) ： t - ( r t ，y ) ， i - 1 ， 定義2 1 凸集6 的極點在廳處是受控的，假如它滿足 f i + 砑。m r a i n 。兩+ 砑7 ，v a e o , a 。1 如果不滿足這個關系，則稱一在廳處是非受控的。 前面已假設了，函數(shù)的連續(xù)性，因此根據(jù)定義2 1 可以推出：如果極點一在 廳處是受控的，則它必然在廳的某個鄰域內是受控的。 不失一般性，假設前( 西個極點在廳處是非受控的，并按照它們對應的r 值作降序排列 t 1 乏t 2 乏t ( 盯) 接下來，我們將引入一個關于各極點y l 的非退化的假設。 條件a ：對緊凸集q 的任意兩個不同的極點y j 和y ，對應有t 一t j 于是，在條件a 成立的情況下，有 t 1 t 2 ， t ( ) 我們已假設( 廳) 個極點都是非受控的，則有 f 1 兩 r 2 ) i r 唧 f 1 ( 矛) ，2 ( 兩f ”而( 礦) o - c r o 假，) q 假，) ( 茸) 假) 一口一 我們已經求得了l p 的最優(yōu)解的形式，它是以非受控極點為分割點的分段函 數(shù)，因此 肛汀，口) 一) ，佤a l l 2 - f 一眇餌：口) 一) ，( 豆口1 弘口 一f 一擴曰，口) 一y 口夥2 ( a ) d a 主西劬三缸。| 3 鼯) j q 口，) 一q ( 別 其中，西為緊凸集q 的直徑，妒一2t 蚴艫 ) ：口( o 口一h 由分割點的定義： 口；( 廳- ) 一一( ，“( 曰) 一f ( 廳r ) ) i ( t “1 一r ) ，i 一1 ，( 廳) 一1 并且f 在6 上李普希斯連續(xù)，所以，必然存在李普希斯常數(shù)工面，y 兩在q 上關于島李普希斯連續(xù)，即 肛田，口) 一y 口硼2 瑤修一硎： 下面，我們來看y ( d ： i ) ，西一y 萬) | | 2 - | 1 ) ，餌一y 田) | | 2 ；圳廳- o i l ： - 島盱m ) 一訛矽口) | | 2 s 瑤廣晤o ) 一矛 ”2 d a 一瑤肛一矛1 2 于是，得到) ，西作為關于i 缸( 0 ，口。) p 的函數(shù)，是關于塢李普希斯連續(xù)的。 2 3 離散化的方法 根據(jù)問題的定義，所有出行者的v o t 參數(shù)值在整個系統(tǒng)中服從連續(xù)的概率 密度函數(shù)妒 ) ，因此要得到網(wǎng)絡均衡解，必須求解無限維連續(xù)的變分不等式 ( 2 2 ) ，但是在實際應用，特別是在工程計算中，往往只有離散的，有限維的數(shù) 值計算才能被計算機所支持，因此我們所提出的這個問題必須被離散化為有限維 的形式才能在更廣泛的領域中應用，體現(xiàn)更好的實際價值。 在這一節(jié)中，我們將提出一個可用的離散化方法，并在下文中對它的收斂性 和算法精度作詳細的分析。 我們還是先從2 2 中引入的無限維線性規(guī)劃問題( 2 - 3 ) a 手： 凹 嘧( r ( f ( a 西+ 叮) ，y ) q 。b 仁( 0 ，口一) p ：a y ( a ) 6 妒( 口) ，) ( 口) o v a 0 ，口。1 考慮將上述l p 問題離散化為有限維的線性規(guī)劃問題。我們用一個離散的概 率密度函數(shù)來逼近l p 規(guī)劃中連續(xù)的概率密度函數(shù)妒 ) 針對連續(xù)概率密度函數(shù)妒 ) ，口【0 ，口一】，我們構造這樣一個離散化規(guī)則： d p ，r ”，砂) ，其中口”i p o ，展，見 是區(qū)間【o ，口?！康囊唤M分割點，且有 o i 風 屆 島 基于d ( b o o , p ，p 0 , ) 的離散化形式，) 代表了v o t 參 1 4 數(shù)a 落在區(qū)間【屆。，成】中的出行者在各路徑上的加總流量。那么是否當d 。一0 時，( 2 7 ) 的解也會逼近( 2 - 3 ) 的解呢? 下面就來討論這個問題。 前面我們已經得到了( 2 3 ) 的解，基于同樣的假設和方法，我們很容易得到( 2 - 7 ) 的解，我們把它表示成關于路徑流量廳的函數(shù)： ) ，。( 而一兩l 。 y ? ，y a p p la o y i ( t t l y 2 aq n f 3 再、p l a n 潭1 - 1 y i a m 圓1 l - 1 ，雄 可以發(fā)現(xiàn)( 2 7 ) 的解，( 廳) 是有限維的，不可能直接去逼近無限維線性規(guī)劃問題 ( 2 3 ) 的解。不過，我們可以基于y 4 ( 而來構造一個無限維的向量，我們同樣表示 為關于廳的函數(shù)： 歹“( 豆a ) - y ，。( 西( 屈一層一。) i - l c 1 ， ，i 口【屈。，屈】 即近似的認為v o t 參數(shù)值處于同一區(qū)間【屆。，層】的所有出行者數(shù)量是分布均勻 的，且都選擇同樣的路徑。下面我們將證明羅。兩在苊一c o 時逼近( 2 - 3 ) 的解 y ( 而 要證明羅4 ( 而在 一m 時逼近) ，( 而，必然考慮逼近誤差0 ) ，( 兩一夕“( 而8 定理2 1 對任意給定的廳6 和滿足逼近概率密度函數(shù)妒 ) 口( 0 ，a 一) 條件的 離散化規(guī)則d 俾，p ，尸n ) ，都有 | ) ，回一夕。唰| - o 瓴) ，當以- - - , 0 證明：將分割點口，口，何h 和局，成。合并作為新的分割點集合，則( o 口) 被分割為開+ ( 廳) 一1 個小區(qū)間。我們將所有包含q ，i 一1 ，( 兩一1 的小區(qū)間 組成的集合記為 ，l ，其余的記為 1 2 ，則“) 中最多有2 ( ( 而一1 ) 個元素。根 據(jù)y ( 而和夕。( 而的結構，我們知道只有弘) 中的區(qū)間上，_ ) ，( 而和少( 西才可能 會取不同的極點，并且) ，( 莉和羅4 ( 莉都是有界的，因此，存在某一大于0 的常 數(shù)厶，使得 ，i y 口) 一歹。江口1 p 口列西一班- 斛m a x ，l a ，一n 一2 ( ( 百) 一1 ) d 。一o ( d 。) 當d h + 0 而在仉 中的區(qū)問上，_ ) ，( 西和羅。取相同的極點，由前面定義的( 2 。6 ) ，可以 計算仉 上的累積誤差，即存在某一大于0 的常數(shù)厶，使得 臚 小歹4 口枷吐扣一層。帥川- l 2 d 2 , , = 0 當d z - - 0 最后，得到夕。( 西與) ，( 而之間的逼近誤差為 堋e - 1 1 ) ，回節(jié)咧p 口。沙 小以鼠口枷+ 捌) ， 小羅”何川 a l d 一0 ( 以)當以一0 其中為某一大于0 的常數(shù)。 這樣就證明了羅“( 兩在弗一0 0 時逼近y ( 而 上面這些討論都是在圍繞著( 2 3 ) 這個無限維線性規(guī)劃和它的離散化形式展 開的，而我們最終要討論的是逼近無限維變分不等式( 2 2 ) 的離散化形式，以及它 的收斂性。 回顧2 1 中提出的( 2 - 2 ) 的形式： q ( a ( f ( a h ) + a r ) , s h ) o v q q 一扛仁( 0 ，口。) ) 。：御似) 一卻q ) ， ) z o v a e 【o 0 我們仍然采用離散化規(guī)則d ( 砂) ，p ，p 軸) 對妒缸) 進行離散化，可以得到以下有 限維變分不等式作為( 2 2 ) 的離散化形式： 賽( a r ( ，( 砉a f ) + ，n 一一 ；) = 。怕，q ，( 2 o ，一概：a h j - 鋤，h j o ) ，1 ，月， 其中，h - ( j ) j 5 螄，h 。- o ；) j 5 l 一， 進一步，記 ，( ?！镜V( f ( 善a ) + 乃”j ， 則( 2 - 8 ) 可以被寫成一個更規(guī)范的形式： ( j o ?！币籬 。) - 0 鐘( ”) q _ - 伽- 鴨) 舯，睜，：a h ，一，h ，o 在進行其他討論以前，我們先來證明( 2 - 9 ) 的解的存在性。首先引入證明存在性需 要的一個定義。 定義2 2 假設q 是自反的b r a n c h 空間y 的一個子集，v 是它的對偶空間，是 從q 到v 的映射。，被稱為l i o n s 定義下的偽單調( 本文中涉及的偽單調均為 l i o n s 定義下的偽單調，后面不再說明【1 0 】) ，假如- ，在q