一類基于拉格朗日的分裂算法求解交通均衡問題

前言（1）選題的目的和意義近年來我國的交通設(shè)施越發(fā)發(fā)達，交通需求量大大增加，便利的交通出行工具為我們提供了很大的方便.但是這也引發(fā)了一系列的社會影響，比如交通堵塞問題的頻繁出現(xiàn)，這已經(jīng)成為了許多城市的發(fā)展瓶頸，大大限制了社會的發(fā)展.所以交通均衡問題就成為了我們不得不面對的話題.交通流量分配是交通規(guī)劃的一個重要的組成成分，在交通規(guī)劃中占據(jù)了核心的地位交通均衡問題是一類約束優(yōu)化問題，交通資源是有限的，出行者的數(shù)量也是有限的.當所有出行者都選擇某一條道路出行時，他們就需要爭奪交通資源.當此條道路的交通資源被耗盡時，會造成交通擁堵情況.所以此時就需要一個控制機制來進行交通資源的分配，這個控制機制需要盡量保證交通流中的每一出行者都能夠充分利用有限的資源，并且不會對道路中的其他出行者造成不必要的干擾，同時得到每個出行者較高的滿意度.這個控制流程就成為交通均衡原則，系統(tǒng)將調(diào)查得到的OD對之間的交通流量進行記錄，從而形成一個OD矩陣，然后再將現(xiàn)有的交通出行流量均勻合理的分配到交通網(wǎng)絡(luò)的各條道路上.研究交通均衡問題，就是要調(diào)節(jié)均衡各個道路上的交通量，做好交通流量的分配任務(wù)，以尋求交通網(wǎng)絡(luò)利益最大化和花費最小化，使得更加科學的利用基礎(chǔ)設(shè)施，實現(xiàn)交通流量需求和流量容納量的均衡發(fā)展.為了對交通網(wǎng)絡(luò)的需求模式進行掌握，我們通常以起點-終點相關(guān)矩陣或需求函數(shù)來描述，交通模型的研究基于當提供給不同的供給和需求時，何時達到花費最小化并且交通網(wǎng)絡(luò)中沒有擁堵現(xiàn)象[1].根據(jù)這一定義，Wardrop等人提出了用戶均衡模型，模型假設(shè)道路使用者的出行需求都是固定的，并且他們都能夠準確的得知道路交通網(wǎng)上的所有出行信息[2].但是交通出行反而是一種隨機現(xiàn)象，并且道路出行者對道路的理解能力也是一個隨機變量，因此這種前提是很難被滿足的，所以有許多學者從事于研究更加適用于現(xiàn)實需要的網(wǎng)絡(luò)交通模型.在1977年由Daganzon和Sheffi等人提出了隨機用戶均衡系統(tǒng)[2]，此隨機用戶均衡模型將交通出行者對于道路的理解程度以及選擇出行道路定義為了一個隨機變量，這就很好的解決了此前Wardrop提出的交通均衡模型難以滿足的問題，隨機用戶均衡體系統(tǒng)一了隨機分布和交通均衡的概念，更適用于現(xiàn)實實際.然而，在中國的城市交通中，交通工具魚龍混雜，研究混合型交通均衡問題更適用于中國的交通體系.混合型交通均衡問題就是各種交通出行方式共存于一個交通網(wǎng)絡(luò)中，因此使用單一的出行模型去描述實際的交通狀況是不適宜的[2].本文通過運用研究變分不等式相關(guān)理論，提出了兩類改進算法，并適用于研究均衡配流問題中.道路出行者可根據(jù)模型求解得到的數(shù)據(jù)進行分析從而得出最優(yōu)出行決策，更好地利用交通資源，使得資源供應量與需求量維持平衡，道路網(wǎng)絡(luò)維持穩(wěn)定[1]．(2)國內(nèi)外文獻綜述：交通分配在交通規(guī)劃中占據(jù)著重要的地位，交通分配就是指將交通流量矩陣在一個指定的道路交通網(wǎng)絡(luò)中，更為合理以及符合實際的分配到道路交通網(wǎng)絡(luò)的每條道路上，從而可以得到道路交通網(wǎng)絡(luò)中的各條路段的實際出行交通流量.近幾十年眾多學者都在進行對于交通流量的分配研究.其實在早些年人們就已經(jīng)認識到交通出行時間、道路擁擠程度等都會影響出行者選擇相應的道路，但是由于缺乏系統(tǒng)的理論知識和計算的算法，人們不得不依靠經(jīng)驗進行判斷[3].20世紀50年代以后，美國人BPR，HR通過研究交通轉(zhuǎn)移率從而提出了一種轉(zhuǎn)移概率曲線的方法，這可以稱之為交通分配理論的初始嘗試[4].1957年，Moore和Dantzin發(fā)布了搜索網(wǎng)絡(luò)中兩點之間的最短路徑的方法，該方法對交通流量的分配原則發(fā)展具有著深遠的影響[5].在Carroll和Schneider等人的努力之后，在20世紀50年代后期，基于最短路徑方法的“全有全無”方法被應用于交通分配問題中[2].“全有全無”方法從出行者的角度考慮，遵從出行者的選擇來進行交通流量的分配，該方法的運行機制是將所有起訖點之間的交通流量需求進行分配.但是顯然結(jié)果與實際交通狀態(tài)不盡相同.為了避免這種不合實際的情況，在隨后的研究中又有許多專家提出不同的分配算法，其中較為符合實際并且計算結(jié)果較好的是Mclanghlin方法[6]，即交通容量限制和概率分配方法.1952年，Wardrop第一個提出交通流均衡的原則，它是交通均衡問題的開端，交通均衡原則指出，道路的出行者會在起止訖點之間選擇出行成本最小的道路通行，而出行成本較高的道路則將不會被選擇.Wardrop的交通均衡原則雖然被較早提出了，但是由于數(shù)學算法的難以實現(xiàn)，其研究一直沒有實質(zhì)性的進展.在1956年，Bankmann基于Wardrop均衡模型進行研究，最終得到了解決Wardrop難以求解問題的方法，完善模型和求解問題提供了很大的幫助，他們的研究已經(jīng)形成了比較完整的均衡理論體系，在交通分配理論體系中占有著很大的權(quán)重.(3)研究的內(nèi)容及預期目標：更加合理地調(diào)節(jié)交通流量配置，從而實現(xiàn)交通需求與道路通行容量的平衡，防止堵塞現(xiàn)象的發(fā)生.第1章：緒論23彈性需求下的用戶均衡配流模型5章：總結(jié)及展望總結(jié)論文的思路結(jié)構(gòu)，提出一些合理化的建議，并提出對未來工作的展望緒論凸優(yōu)化問題凸優(yōu)化問題的研究已經(jīng)進行了很長時間，早期研究的線性最小二乘問題和線性規(guī)劃問題屬于凸優(yōu)化的特殊形式.隨著各個學科領(lǐng)域的交叉融合，凸優(yōu)化問題可以解決許多領(lǐng)域的實際問題，具有著重要的作用[7].一個凸優(yōu)化問題可以描述為：（1-1）其中是一個凸函數(shù)，并且可行范圍為凸集.當問題的目標函數(shù)為可分離的情形時，則有如下式子：（1-2）其中目標函數(shù)為閉凸函數(shù)，，是給定的向量，并且可行集為凸集.由于凸規(guī)劃問題可視為求凸函數(shù)在其定義域上的極小點，可得以下性質(zhì)：凸規(guī)劃的任一駐點是極小點凸規(guī)劃的任一極小點是全局最優(yōu)點變分不等式變分不等式在應用數(shù)學領(lǐng)域中發(fā)揮著重要的作用，它也是偏微分方程的一個重要分支.其求解的數(shù)值方法出現(xiàn)在1972年，后來出現(xiàn)了梯度外推法等一系列算法.目前變分不等式已廣泛應用于均衡、運籌學問題等[8].利用變分不等式的知識，我們更方便的研究與凸優(yōu)化有關(guān)的一系列問題.變分不等式(記為)的一般形式如下：找一點，使得，（1-3）其中是的非空閉凸子集，是到上的一個映射.定理1.2.1若在閉凸集上是連續(xù)的可微凸函數(shù)，假設(shè)是優(yōu)化問題（1-1）的最優(yōu)解，則也是變分不等式（1-3）的一個解.證明如下：分析如下凸優(yōu)化問題，其中是一個的可微凸函數(shù)，，若是問題（1-1）的最優(yōu)解，等同于假設(shè)且，進而等同于假設(shè)于是問題，(1-4)的解.定理1.2.1可以說明在目標函數(shù)連續(xù)可微的條件下，凸優(yōu)化問題與變分不等式可以進行相互轉(zhuǎn)換，即求解（1-1）問題就等于求解（1-5）的變分不等式問題，用符號語言表示為：找一點，使得，(1-5)故由此我們可以了解到數(shù)學中的許多凸規(guī)劃問題，都可以借助轉(zhuǎn)化得到的變分不等式問題進行求解.當凸優(yōu)化的目標函數(shù)為可分離的形式時，我們拿出拆分為三個函數(shù)的形式進行考慮：(1-6)其中目標函數(shù)為閉凸函數(shù)，，是給定的向量，并且可行集為凸集.問題(1-6)的目標函數(shù)是由三個可分離的凸函數(shù)構(gòu)成的，這類優(yōu)化問題在運籌學交通均衡等方面都有著廣泛的應用[7].令為(1-6)中線性約束對應的拉格朗日乘子.則(1-6)的一階優(yōu)化條件為：找一點，使得不等式(1-7)成立.對，令，，(1-8)則(1-7)可以寫成我們尋找一點使得變分不等式(1-5)成立.由此可見，變分不等式問題與凸優(yōu)化問題是緊密相連的.這樣的變分不等式不僅僅是最小化一個目標函數(shù)的簡單優(yōu)化問題，它也可以將凸優(yōu)化問題理解為一類特殊的變分不等式問題.所以求解變分不等式常在凸優(yōu)化理論框架內(nèi)進行研究.1.3預備知識定義1.3.1.給定凸集和，如果滿足下式，則稱關(guān)于是單調(diào)的.(1-9)定義1.3.2.令映射，若滿足下式，則稱在上單調(diào).(1-10)命題1.3.1假設(shè)關(guān)于是單調(diào)的，則序列是有界的，并且收斂到任一.算法及改進增廣拉格朗日算法在凸優(yōu)化問題（1-1）中，可行域通常有如下形式：.為了使有約束問題轉(zhuǎn)換為無約束問題，我們對線性約束引入拉格朗日乘子(可以衡量靈敏度)，得到其Lagrange函數(shù)：(2-1)如果點滿足不等式(2-2)則此點稱為拉格朗日函數(shù)的鞍點，(2-2)可表示為(2-3)若是可微的，記，則(2-3)可表示為(2-4)若令，則(2-4)可表示為，.為了增強對偶上升法的魯棒性和放松目標函數(shù)的強凸約束，我們再引入一個罰參數(shù)，可得到其增廣拉格朗日函數(shù)：(2-5)ALM算法的迭代步驟為：ALM算法也稱為增廣拉格朗日乘子法.ALM算法是一種經(jīng)典的解析方法，引入?yún)?shù)的目的是可以將有約束的優(yōu)化模型問題轉(zhuǎn)化為無約束優(yōu)化模型問題.對于問題1-6，其ALM的迭代步驟為：給定點通過以下步驟產(chǎn)生新的迭代點，其中并行分裂的增廣拉格朗日乘子法是可以很有效的求解優(yōu)化問題.對于約束條件較多、條件較復雜的情況，該方法可以很好地得到計算結(jié)果[9].但在計算過程中，需要同時計算多個原始變量，這是計算量很大的問題，且沒有考慮(1-6)問題可分性問題的特殊性[10].ADMM交替方向乘子法ADMM算法是廣泛使用的一種優(yōu)化算法.它在統(tǒng)計、圖像處理等大規(guī)模優(yōu)化領(lǐng)域的問題中得到了廣泛的應用.它是ALM算法的擴展.ALM算法削弱了對偶上升法的收斂條件，但由于在計算優(yōu)化步驟中引入了一個二次項從而導致不可能分別求解每個原始變量[11].為了改進這一問題，Gabay、Mercier等人希望將乘數(shù)法的收斂性與對偶升序法的可分解可解性相結(jié)合，提出ADMM算法來解決可分凸優(yōu)化問題[12].ADMM是一個經(jīng)典的算法應用在許多領(lǐng)域，如矩陣優(yōu)化、圖像處理等.ADMM算法的求解步驟：(2-6)其中ADMM迭代算法是在原方法的迭代步驟基礎(chǔ)上中又增加了一個高斯賽德爾分解[7]，因此函數(shù)可以被分步計算，大問題被轉(zhuǎn)化為小問題，從而可以簡化目標函數(shù)的迭代，達到使子問題的求解變得更加容易的目的.但是原始變量交替計算需要大量的時間，而且目標函數(shù)為三個及以上的這類凸優(yōu)化問題的收斂性還不能確定，這意味我們不能夠直接運用算法(2-6)去解決(1-6)這類問題.為了解決這一問題He等人提出了PSALM算法來求解這類凸優(yōu)化問題[13].PSALM并行分裂算法PSALM算法的求解步驟：相比于ADMM算法，PSALM算法可以實現(xiàn)優(yōu)化問題分離的特點[8]

，因此這兩類算法對于求解結(jié)構(gòu)性變分不等式問題十分有效，同時PSALM算法可以同時計算多個原始變量，大大的節(jié)省了計算時間，所以PSALM算法更適用于求解大規(guī)模凸優(yōu)化問題. 為了更加容易的求解此類問題，在此之后又有許多學者對此類算法進行了創(chuàng)新和改進.例如，有一些學者采用限制修改算法中對應參數(shù)的取值范圍，從而達到調(diào)整算法的迭代速率的辦法，還有一些學者在研究過程中向子問題中添加一類擾動項，使得子問題的每個對應函數(shù)都完全單調(diào)，從而實現(xiàn)近似解決子問題的目的.例如，He等人利用交替方向法求解具有單調(diào)性的變分不等式問題時，將懲罰參數(shù)控制在一定范圍內(nèi)進行迭代運算，運行得到的結(jié)果效果較好.ADMM-split算法考慮(1-6)情況，首先算法由給定的初值先產(chǎn)生預測的迭代點，再產(chǎn)生修正步，其算法框架如下：.給定，和.令.產(chǎn)生預測點：.修正迭代點：.停機準則：如果則停止，否則令，轉(zhuǎn).對于ADMM-split算法，其預測步驟中三個原始變量迭代求解.校正步驟中算法只對第三個原始變量進行修正，且這種算法是收斂的.考慮到這個因素，本文提出一種新的算法.改進的基于增廣拉格朗日分裂算法2.5.1改進算法1.給定，和.令.產(chǎn)生預測點：(2-7).修正迭代點：.產(chǎn)生預測點：.停機準則：如果則停止，否則令，轉(zhuǎn).其中注2.5.1.1：改進算法1與ADMM-split算法都采用了預測校正技巧，通過先產(chǎn)生一個預測點，然后通過結(jié)合初始迭代值產(chǎn)生新的迭代點，因此改進算法1的工作量與ADMM-split的算法接近.2.5.2改進算法2.給定和.令.產(chǎn)生預測點：(2-7).修正迭代點：其中.停機準則：如果則停止，否則令，轉(zhuǎn).其中注2.5.2.1：在改進算法2中，含有兩個參數(shù).在算法中可視為步長，所以在數(shù)值實驗中我們要選取合適的數(shù)值來加速改進算法的收斂性.相比于改進算法1，我們設(shè)法將每步迭代中的最優(yōu)步長計算出來并參與下一次的迭代，這樣更有益于節(jié)省計算時間，使得程序盡快收斂.且在預測步驟中，第三個自由變量的計算利用了第一，二個自由變量的更新迭代值.改進算法的收斂性分析由于改進算法1，2的證明思路類似，本論文只作出改進算法1的收斂性分析，改進算法2同理引理2.6.1.若并且，則由改進算法的預測步驟中產(chǎn)生的是變分不等式(1-6)的解.證明：因為并且則有，又由則可推知由(2.5.1)預測產(chǎn)生，則由一階最優(yōu)性條件可知，其與下式等價：其中也就是，找一點使得不等式(2-8)將帶入到(2-8)中，有(2-9)記(2-10)(2-11)則由(2-4)中對于的定義，不等式(2.5.2)可化為：(2-12)當，時，我們有，故上式(2-12)化為：故由此可知，則由改進算法的預測步驟中產(chǎn)生的是變分不等式VIP(1-6)的解.注：引理2.6.1表明在不等式中，當時是問題(1-6)的解，所以我們把稱為停止準則.引理2.6.2.令是(1-6)的任意一個解，則由改進算法產(chǎn)生的序列和滿足(2-13)其中記，(2-14)證明：由于是(1-6)的任意一個解，取則根據(jù)(1-7)有：(2-15)即(2-16)又由于則根據(jù)(2-12)有：(2-17)將(2-16)與(2-8)上下兩式相加并經(jīng)整理可得到又因為單調(diào)，所以有由(2-14)的定義，上述不等式又等價于將(1-7)，(2-1)，(2-10)帶入整理得到：即上式左右兩邊同時加上引理2-9即證明.注：引理2.6.2表明是的下降方向，從而可以沿著這個下降方向來產(chǎn)生新的迭代點.引理2.6.3.令是(1-6)的任意一個解，則由改進算法產(chǎn)生的序列是關(guān)于集合單調(diào)的證明：由改進算法的修正迭代步驟得其中為對角陣，因此將(2-6)代入下式有(2-18)又有(2-19)其中再假設(shè)條件為列滿秩下，矩陣Q為對稱正定矩陣當且僅當(2-20)矩陣為對稱正定的.當，時，很容易求證(2-20)中的矩陣為對稱正定矩陣.將(2-19)代入到(2-18)中可得(2-21)引理2.6.3得證，則由改進算法產(chǎn)生的序列是關(guān)于集合單調(diào)的.定理2.6.1.令，，則由改進算法產(chǎn)生的序列收斂到VIP(1-6)的解證明：由(2-21)可知則上式兩邊對求和可得這意味著(2-22)由引理2.6.3可知，由改進算法產(chǎn)生的序列是關(guān)于集合單調(diào)的，則由命題(1.3.1)和(2-22)可知：序列和是有界的；存在常數(shù)使得，在算法的迭代步驟中我們得知序列和是有界的，則有界數(shù)列必有收斂子列，令為的聚點，則存在子列滿足(2-23)又由(2-22)可知(2-24)結(jié)合(2-23)，(2-24)帶入到(2-12)有由此可知序列收斂到VIP(1-6)的一個解，全局收斂性證明完畢.增廣拉格朗日并行分裂算法求解交通均衡問題本文第二章研究了解可分離型帶線性約束的凸優(yōu)化問題的一些算法，并給出了一種新的基于增廣拉格朗日并行分裂算法.由于這類特殊的凸優(yōu)化問題可以被適用于研究各種各樣的應用背景，例如交通分配、網(wǎng)絡(luò)分配、經(jīng)濟等方面，故本章建立了可用來解決交通均衡配流問題的變分不等式模型.交通均衡體系概述交通均衡問題是日益發(fā)達的社會環(huán)境下需要著重考慮的事情，配流問題是指將交通流量通過合理的配置使他們分配到交通網(wǎng)絡(luò)的各個路線上去，使交通流量可以在道路網(wǎng)絡(luò)上均勻分布并且避免出現(xiàn)交通擁堵情況，使得交通資源合理利用，時空分布合理.在實際的道路網(wǎng)絡(luò)中，起止訖點之間與眾多路線.倘若OD對之間有許多條通行道路但是卻沒有那么大量的交通流量，此時交通流量一定會沿著費用函數(shù)最小的道路行駛.但隨著OD對之間交通流量的增多，費用函數(shù)最小的道路上的交通流量也會相應的增多，在交通流量達到了最短路徑對應的可接納容量時，該路徑就會發(fā)生交通阻礙情況[14].此時該路徑的行駛時間就會因為堵塞情況而增加，這時就會有一部分的出行者選擇次短的道路出行.隨著起訖點之間的交通流量持續(xù)增加，當容量增加到一定程度時，OD對之間的所有道路都可能被使用.如何去調(diào)控這個復雜的運行機制就是交通均衡的意義所在.交通均衡問題可以使用變分不等式方法進行求解，經(jīng)濟專家knight首先提出了均衡的概念，而后Wardrop在1952年提出了兩個均衡準則用戶均衡(UE)和系統(tǒng)優(yōu)化(SO)原則[15].給定一個網(wǎng)絡(luò)，如果出行者(用戶)從他自己的角度尋求個人利益的最大化，那么每個人在這個過程中都會成為個人利益最大化的一個限制，最終得到重復博弈后的用戶均衡狀態(tài)，這稱之為用戶均衡原則;另一方面，為了使整個系統(tǒng)的成本降到最低，假設(shè)所有交通出行者都自覺接受系統(tǒng)的調(diào)控，從而使得整個交通網(wǎng)絡(luò)的出行成本最小這就稱之為系統(tǒng)優(yōu)化原則.如圖所示，給出了交通分配模型的分類結(jié)構(gòu).根據(jù)交通流量的變化特點，可以將大體的模型分為兩類動態(tài)交通和靜態(tài)交通.靜態(tài)交通表明道路網(wǎng)絡(luò)流量處于一個穩(wěn)定狀態(tài).交動態(tài)交通分配模型描述了隨時間變化的交通狀態(tài).圖3-1交通分配模型的分類Figure3-1Classificationoftrafficassignmentmodels符號定義交通均衡問題是一類帶線性約束的凸優(yōu)化問題，目前已經(jīng)有一些方法來求解，但如何有效的求解交通流分配問題仍然是許多研究者關(guān)心的課題.本文運用拉格朗日分裂算法來解決一類交通均衡問題，并且通過一個簡單的數(shù)值算例說明該分裂方法的有效性.由于交通網(wǎng)絡(luò)的復雜性，為了便于描述，現(xiàn)做如下符號說明符號說明強連通的有向圖結(jié)點集路段集合路段上的交通流量()起始節(jié)點集合()路段上的實際出行能力()終訖結(jié)點集合連接對的路徑集合，OD對之間的路徑上的潛在需求表示出行者費用的敏感度參數(shù)其中阻抗函數(shù)，也稱交通行駛時間或者交通出行成本.在交通規(guī)劃的交通分配階段，要考慮到某一路段的時間出行成本.可以根據(jù)行駛時間和路段交通流量之間的關(guān)系來確定.其一般形式為，最為常見的路阻函數(shù)是美國聯(lián)邦公路局函數(shù)（BPR）：其中為路段自由行駛時間，為待定系數(shù)，建議取值分別為0.15，4.用戶均衡分配模型定理3.3.1Wardrop第一原理（UE定義）若道路使用者都完全掌握道路網(wǎng)絡(luò)的通行情況，并希望選擇最短路徑出行時，網(wǎng)絡(luò)將會達到到均衡狀態(tài).當交通網(wǎng)絡(luò)達到平衡狀態(tài)時，我們可以對應得到交通網(wǎng)絡(luò)中的最小出行成本所有被使用道路的行駛時間相等且等于最小的行駛時間其他未被利用的道路的行駛時間大于或者等于最小的行駛時間用符號語言表達即（3-1）Wardrop第一均衡狀態(tài)從道路的使用者角度考慮，道路使用者希望通行的道路暢通且具有最小的出行成本，這種選擇方式導致所有被交通使用者選擇后的道路之間具有著相同且最小的行駛時間（即出行成本），因此可以對應得到用戶均衡狀態(tài)下的交通阻抗[16].Wardrop在提出均衡準則后，由于數(shù)值計算的難度性導致這個問題的研究沒有實質(zhì)性進展.后來由Beckmann等人提出了一種滿足UE規(guī)則的數(shù)學模型.提出的模型如下：（3-2）其中該模型稱為用戶最優(yōu)模型（UE）.由定理1.2.1可知，上述凸優(yōu)化問題可以在一定條件下轉(zhuǎn)化為一類變分不等式問題.于是（3-2）對應的增廣拉格朗日函數(shù)為（3-3）如果點滿足不等式則有下式若令，則(3-2)可表示為，.圖形表示為：圖3-2用戶均衡的概念Figure3-2Conceptofuserequalization系統(tǒng)均衡分配模型在系統(tǒng)均衡的條件下，整個系統(tǒng)的出行路線是由所有的道路出行者共同決定的.SO均衡的原則是使得整個道路交通網(wǎng)絡(luò)的出行成本最小，當其中一方道路出行者發(fā)生了道路決策的變化，都會影響最終的總出行成本.這是SO均衡原則與UE均衡原則的不同的地方.定理3.4.1Wardrop第二原理（SO定義）在考慮交通流量超出道路負荷能力后，新增的交通流量對路段的出行成本有影響的網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的交通量應該遵循使網(wǎng)絡(luò)中交通量的總出行成本最小的分配原則進行分配.用戶交通均衡原理它反映了交通網(wǎng)絡(luò)中的出行者選擇出行路線的方法，即選擇的道路最短并且出行成本最小，這種原理所運用得到的結(jié)果是交通出行者會主動選擇的結(jié)果.Wardrop第二原理即系統(tǒng)均衡原理它努力實現(xiàn)使得道路網(wǎng)絡(luò)中的總出行成本達到最小，為了符合這個條件，原理假設(shè)所有的道路出行者都服從指揮的去選擇出行方式.但是在現(xiàn)實的交通道路中這種原則是很難被滿足的，這種原則只是被用來為規(guī)劃城市道路提供一些決策[17].我們可以根據(jù)定義要求歸納為下述模型：該模型稱為系統(tǒng)最優(yōu)模型SO.數(shù)值試驗考慮如下所示的交通網(wǎng)絡(luò)，設(shè)交通起訖點之間的交通運行量為1000輛，定義各路徑的交通費用函數(shù)圖3-3交通網(wǎng)絡(luò)Figure3-3TrafficNetwork若想求得此問題的最優(yōu)交通配流，則這類交通均衡實例可以轉(zhuǎn)化為如下的凸優(yōu)化問題進行求解：（3-4）問題所對應的增廣拉格朗日函數(shù)為實驗結(jié)果：我們利用全有全無分配法得到起始迭代初值為(0，500，500)，選取適當?shù)膮?shù)值后可得運算迭代結(jié)果如下，所有的代碼都是運用MATLABR2008b編寫.表3-1：迭代次數(shù)的結(jié)果比較Table3-1:Comparisonofresultsofiterations初始迭代值迭代次數(shù)改進算法1改進算法2ADMM-split(0，500，500)222(300，300，400)19844(0，1000，0)26454(400，500，100)>100034表3-2：目標函數(shù)值的結(jié)果比較Table3-2:Comparisonofresultsofobjectivefunctionvalues初始迭代值目標函數(shù)值改進算法1改進算法2ADMM-split(0，500，500)(50，290，108)（50，108，178）(50，350，48)(300，300，400)(50，350，219)(50，298，148)(50，350，190)(0，1000，0)(50，349，220)(50，308，180)(50，350，163)(400，500，100)(30，350，219)(50，321，181)(50，350，209)圖3-4繪制誤差圖Figure3-4Drawinganerrorgraph圖3-4中，我們可以看出本文提出的改進算法1中誤差下降的最快，但是由表3-1的迭代次數(shù)可知，雖然改進算法1具有著最快下降速率但是卻需要迭代多次才能得到最優(yōu)解.且選取不同的迭代初值，會使改進算法1的迭代次數(shù)有著較大的波動，甚至可能在超出數(shù)組迭代運行后仍然得不到符合條件的最優(yōu)解.而本文提出的改進算法2中，其誤差的下降速率與ADMM-split算法相近，但迭代次數(shù)卻在每一次實驗中都是最少的，這意味著改進算法2相對于改進算法1具有著很大的改進.通過表3-2中的數(shù)值試驗結(jié)果可以發(fā)現(xiàn)，改進算法2不僅在迭代次數(shù)和迭代時間上有很大的優(yōu)勢，受初值選取的影響不大，都近似維持在10次以內(nèi)，能夠在很短的時間內(nèi)通過迭代得到符合條件的解集..3.6小結(jié)本章主要是將并行分裂的增廣拉格朗日方法（ADMM-split）以及新提出的兩種改進算法應用到求解交通網(wǎng)絡(luò)資源分配問題中，本章中的數(shù)值實驗只是一個很簡單易求解的問題，而現(xiàn)實中的交通網(wǎng)絡(luò)是非常復雜的，我們通過這一簡單的小實驗去驗證了算法的有效性.彈性需求下的用戶均衡配流模型Wardrop所提出的的用戶均衡（UE）模型，是在假設(shè)道路出行者可以完全掌握出行信息，這是一個理想化的假設(shè).但現(xiàn)實生活中，人們并不能夠完全的掌握出行信息，并且只能對出行成本進行一個粗略的估計.并且由于不同出行者存在著個體差異，使得他們對道路出行成本會有不同的估計．于是通過學者們的深入研究，他們對原始的用戶均衡模型進行了一系列的改進，從而得到了基于彈性需求的用戶均衡模型.彈性需求是指，對于道路出行者來說，出行需求是一個順勢而改變的數(shù)值，出行費用過高時有些出行者可能會選擇不出行或者使用公共出行方式，這樣就會使交通需求量變成一個受到道路通行時間影響的一個變量，即當?shù)缆纷钚⊥ㄐ袝r間增大時，有一些使用者會放棄出行.所以彈性需求是一個隨著道路通行時間增大而單調(diào)遞減的函數(shù)[18].即當交通網(wǎng)絡(luò)中的初始截止結(jié)點之間的道路交通流量增加時，這條道路上對應的出行流量就會相應的發(fā)生變化，這條道路的出行量就會降低.我們研究OD對之間交通量可變的情況下的用戶均衡分配問題，可以稱之為彈性用戶均衡問題，原始的用戶均衡分配問題被稱之為固定需求問題.彈性用戶均衡分配問題更適用于動態(tài)性的交通分配問題.該問題可以表達為下述模型：其中如果路段流量和交通需求視為決策變量，由于凸優(yōu)化問題的目標函數(shù)是凸函數(shù)，這意味著區(qū)間流量值和需求也是在彈性需求的用戶均衡狀態(tài)下固定的.同樣，如果將路徑流量視為決策變量，則優(yōu)化問題的一般目標函數(shù)不是嚴格凸的，這意味著考慮彈性需求的用戶平衡狀態(tài)下的路徑流量解決方案并不是唯一的[19].解決優(yōu)化問題的算法與考慮固定需求的算法基本相同.任何解決固定需求問題的算法都適用于考慮彈性需求問題.因此，我們使用經(jīng)過驗證的具有良好收斂性和有效性的改進算法2來進行具體的數(shù)值求解.4.1數(shù)值算例圖4-1算例中的網(wǎng)絡(luò)Figure4-1Networkinthestudy如圖4-1所示，該交通網(wǎng)絡(luò)圖中包含著4個起訖點，并且對應了12個路段.其中的路段出行成本使用傳統(tǒng)的BPR函數(shù)其中為路段自由行駛時間，為待定系數(shù)，取值分別為0.15，4.表4-1路段出行費用函數(shù)的參數(shù)Table4-1Parametersofthelinktravelcostfunction路段a12345610.07.012.07.012.012.0120100120120200220路段a78910111210.012.08.010.010.010.0220240150150150120假設(shè)所有OD對采用如下形式的需求函數(shù)：(4.1.1)給出計算各個路徑需求的參數(shù)如下：表4-2OD對之間的需求函數(shù)Tab