帶路票約束條件的用戶均衡網(wǎng)絡(luò)模型

帶路票約束條件的用戶均衡網(wǎng)絡(luò)模型

1973年，達(dá)拉提出了管理污水排放的概念，這一概念主要是為了實(shí)現(xiàn)控制污水的排放。近年來,有些學(xué)者將這一思想引薦到交通領(lǐng)域以緩解城市交通擁堵,由此產(chǎn)生了路票交易體系。Yang等1在票款限制下，用戶的基本數(shù)學(xué)模型1.1旅行時(shí)間費(fèi)用首先定義一個(gè)交通網(wǎng)絡(luò)G=(N,A),用W表示起訖點(diǎn)對(duì)(OD對(duì))w,R本文中所涉及的出行成本一般指廣義費(fèi)用,它是對(duì)流量速度關(guān)系、距離、旅行時(shí)間等的總稱。由于旅行時(shí)間直接影響出行者的路徑選擇行為,因此這些屬性中最重要的是旅行時(shí)間。通常情況下用戶出行成本包含車輛本身的運(yùn)行成本(一般包括燃料的消耗、輪胎的磨損等)以及旅行時(shí)間費(fèi)用(即旅行時(shí)間所體現(xiàn)的價(jià)值)。一般情況下,采用旅行時(shí)間來代替廣義費(fèi)用值不會(huì)產(chǎn)生較大的誤差。當(dāng)有路票容量約束時(shí),本文所提及的出行費(fèi)用將包括兩部分:傳統(tǒng)的旅行時(shí)間費(fèi)用和出行時(shí)選擇路徑的路票成本。路票成本則是收取的路票數(shù)量與價(jià)格之積(即pκ式中:t需要解釋的是,式(1)中的旅行時(shí)間和路票的量綱不一致,在后面計(jì)算時(shí)需要通過旅行時(shí)間價(jià)值換算系數(shù)θ來進(jìn)行轉(zhuǎn)換,θ在物理意義上表示駕駛員社會(huì)經(jīng)濟(jì)屬性及收入水平,在本文中的物理意義則表示使用者能夠?yàn)閱挝宦眯袝r(shí)間所承受的價(jià)格。假設(shè)出行者均是同質(zhì)的,則通過變換得到的實(shí)際出行費(fèi)用為:在確定了廣義出行費(fèi)用之后,需要對(duì)出行路徑的選擇作一定的說明。根據(jù)Wardrop第一原理,在假設(shè)所有出行者均能獨(dú)立做出使自己出行成本最小的決策前提下,相同OD對(duì)之間的所有使用路徑的成本相等并且最小,所有未被使用路徑的成本大于或等于使用路徑的成本。該用戶均衡模型可以下式來表示:1.2有路票總量約束的動(dòng)態(tài)分析根據(jù)上文對(duì)出行費(fèi)用及出行路徑選擇定義的描述,對(duì)比前文對(duì)路段及節(jié)點(diǎn)容量約束下的用戶均衡網(wǎng)絡(luò)流模型的建立,路票約束的固定需求模型也可以用下面的非線性規(guī)劃問題來描述:滿足:上述模型中,式(6)和(8)分別表示路徑流量與OD交通量守恒以及路徑流量和與路段流量守恒條件。除此以外,在路票約束下,其本身也存在固有的均衡條件,即在路網(wǎng)中所有路段使用者所繳納的路票總數(shù)應(yīng)小于或等于路票發(fā)行總量K,即式(9)。同時(shí)在路票交易市場(chǎng)中存在一定的清算條件,當(dāng)所有路票均使用時(shí),路票價(jià)格大于零,當(dāng)路票未被完全使用,路票的均衡價(jià)格為零。用公式表示如下:需要特別說明的是,K表示的是路票總量,一般由政府發(fā)放,其取值在很大意義上能夠決定模型是否有最優(yōu)解。當(dāng)K的取值過小時(shí),使用路票無論選擇哪條路徑,路票總量均不夠,模型無解;當(dāng)K的取值過大時(shí),使用者所累積的路票足夠多,這樣就不需要在路票交易市場(chǎng)中存在買賣,通過發(fā)行路票來緩解交通擁堵的作用也就弱化,從一定意義上講路票就成了可有可無的廢票。對(duì)于K的取值,政府可預(yù)先估計(jì)初始值,通過每一期(一般是一個(gè)月)路票的運(yùn)行效果逐步調(diào)整,最后得出路票的最優(yōu)發(fā)行量。帶有路票總量約束條件的用戶均衡模型的目標(biāo)函數(shù)是帶有線性約束的嚴(yán)格的凸函數(shù),該非線性凸規(guī)劃問題有且只有唯一的路段流量最優(yōu)解,路徑交通量不唯一。其最優(yōu)化的充要條件可用(karush-kuhn-tucker,KKT)條件表述。用p表示路票約束的拉格朗日乘子,μ表示路徑流量守恒條件約束的拉格朗日乘子,則該約束模型的KKT條件表述如下:很明顯可以看出上述公式與UE模型是等價(jià)的,其中拉格朗日乘子p在路票交易市場(chǎng)中的物理意義是表示路票的均衡價(jià)格,而拉格朗日乘子μ的物理意義則是最小費(fèi)用。根據(jù)1.1節(jié)中對(duì)于出行成本的定義,本文采用以上就是路票約束下的用戶均衡網(wǎng)絡(luò)流最優(yōu)化問題,對(duì)于一個(gè)給定的路票方案,當(dāng)存在至少一對(duì)OD對(duì)之間的多條路徑的路票收取量不同時(shí),該模型一定存在唯一解。2模型算法的設(shè)計(jì)2.1算法的初始和主要參數(shù)路票約束問題在本質(zhì)上是帶有線性約束的非線性規(guī)劃問題,根據(jù)目標(biāo)函數(shù)的描述,該模型是關(guān)于路段流量的最優(yōu)化凸規(guī)劃問題,具有唯一的最優(yōu)路段解。這類問題的求解,一般都是將問題轉(zhuǎn)化成無約束的最優(yōu)化問題?；诼菲奔s束條件與路段容量約束類似,基于路票約束的模型求解采用增強(qiáng)拉格朗日乘子法在路票交易體系中,均衡網(wǎng)絡(luò)問題可用下面的模型來表述:式中:s是松弛變量,其主要目的是將不等式約束條件轉(zhuǎn)化成等式約束條件。這樣路票約束下的交通網(wǎng)絡(luò)均衡問題與上述問題等價(jià)的模型為對(duì)比式(18)和(19),并求極值,得可以得到下式:由此可以得到路票約束下的增強(qiáng)拉格朗日函數(shù),即更新拉格朗日乘子,可得拉格朗日乘子和懲罰參數(shù)的初值采用以下公式來確定:本文采用的收斂準(zhǔn)則為關(guān)于模型求解的子算法,本文選用牛頓算法,路票約束下的牛頓算法與傳統(tǒng)均衡問題的算法略有不同,主要體現(xiàn)在旅行時(shí)間上。新的路段旅行時(shí)間為算法的步驟如下。初始化:產(chǎn)生路徑解。步驟0:設(shè)置內(nèi)循環(huán)迭代次數(shù)等于零,n=0;所有路段流量等于零,x步驟1:迭代次數(shù)遞增,n=n+1。步驟2:更新路段旅行費(fèi)用;最短路徑搜索,找到最新的最短路k步驟3:在路徑集中添加最新的最短路。如果k均衡化:在路徑集進(jìn)行交通量分配。步驟4:計(jì)算路徑流量的移動(dòng)方向其中,步驟5:如果步驟6:根據(jù)路徑流量的可行性計(jì)算極限步長,步驟7:通過路徑流量的移動(dòng)方向,計(jì)算路段流量的移動(dòng)方向,步驟8:計(jì)算路段流量的最優(yōu)步長,步驟9:綜合路徑、路段流量的要求得出最優(yōu)步長,λ步驟10:更新路徑、路段的流量:收斂判斷:如果滿足下面條件,就停止內(nèi)循環(huán)迭代。步驟11:如果2.2拉格朗日乘子法根據(jù)上文對(duì)路票約束下的增強(qiáng)拉格朗日乘子法的描述,結(jié)合子算法牛頓算法,基于路票約束條件的用戶均衡網(wǎng)絡(luò)流分配算法的流程可表示如下。步驟1:求解傳統(tǒng)交通網(wǎng)絡(luò)均衡模型,得到傳統(tǒng)無約束條件下的路段交通量和路徑交通量的最優(yōu)解。步驟2:給出拉格朗日乘子初值μ步驟3:調(diào)用牛頓算法主循環(huán),運(yùn)用增強(qiáng)拉格朗日乘子法求解帶路票約束的交通分配問題,獲得與乘子及懲罰參數(shù)相對(duì)應(yīng)的路段交通量。步驟3.1:獲得均衡網(wǎng)絡(luò)交通流的初始解。步驟3.2:進(jìn)行收斂性檢驗(yàn),若滿足收斂條件,轉(zhuǎn)入步驟4,否則,轉(zhuǎn)入步驟3.1。步驟4:按照式(25)更新乘子的值μ步驟5:按照式(29)進(jìn)行收斂檢驗(yàn),若滿足,結(jié)束循環(huán);否則轉(zhuǎn)入步驟3。3實(shí)行路票政策后的效應(yīng)如圖2所示,對(duì)于起終點(diǎn)為A、B的OD對(duì)之間,有路徑1和路徑2,分別收取6個(gè)單位和2個(gè)單位的路票數(shù),即k若不實(shí)施路票交易體系,根據(jù)傳統(tǒng)的用戶均衡原理,有下列公式:很容易可以解得x當(dāng)實(shí)行路票交易后,根據(jù)用戶均衡模型原理及路票均衡條件,運(yùn)用增強(qiáng)拉格朗日乘子法,拉格朗日乘子初值取μ根據(jù)所有使用路徑的路徑費(fèi)用都相等,路票交易價(jià)格可用下式求得:通過對(duì)比兩組解,可以明顯看出,在實(shí)行路票政策以后,路徑1上會(huì)有部分流量轉(zhuǎn)移到路徑2上,使高流量路段的交通量減少了25%。相對(duì)于傳統(tǒng)的路徑流量分配不均勻的現(xiàn)象,當(dāng)路徑1和2的道路條件相同,這種流量的轉(zhuǎn)移是非?？上驳?不僅使路徑1的擁擠得到緩解,同時(shí)還能夠充分利用路徑2的道路資源。這也充分說明了路票政策緩解交通擁堵的可能性及原理,即通過引入路票來改變用戶出行費(fèi)用,從而間接影響用戶的出行選擇。4用戶均衡問題傳統(tǒng)求解算法構(gòu)建了路票交易模型并設(shè)計(jì)了求解算法。構(gòu)建所得的模型是帶線性約束的非線性規(guī)劃問題。