基于延遲函數(shù)的次梯度啟發(fā)式道路交通補(bǔ)償策略

基于延遲函數(shù)的次梯度啟發(fā)式道路交通補(bǔ)償策略

0傳統(tǒng)面向全網(wǎng)絡(luò)的流量負(fù)載均衡優(yōu)化問題交通堵塞將給經(jīng)濟(jì)和社會帶來巨大的損失。2016年，美國城市的交通擁堵成本為1010億美元。利用供求關(guān)系分析,當(dāng)需求大于供給時就會發(fā)生阻塞,因此,可以通過增加供給或降低需求來解決擁塞問題上述方法的思路都是針對一些高度擁擠的道路,旨在重新分配流量負(fù)載均勻分布在整個網(wǎng)絡(luò)包括不擁擠的道路。此類方法類似于一種專家策略,并未定義問題的梳理模型進(jìn)行分析,優(yōu)化效果不理想。為此,本文在給出交通定價補(bǔ)償數(shù)學(xué)規(guī)劃模型的基礎(chǔ)上,實現(xiàn)道路交通補(bǔ)償?shù)膬?yōu)化。1數(shù)學(xué)模型1.1交通網(wǎng)絡(luò)圖的分析給定一組具有上限容量的道路,需進(jìn)行收費或者補(bǔ)貼,即交通定價方案。該問題本質(zhì)上是一個容量限制交通分配問題(CTAP)?？紤]G(N,A)是一個交通網(wǎng)絡(luò)圖,其具有N個節(jié)點,A是連接Rue01bN×N上源節(jié)點和目的節(jié)點的道路。道路集的收費/補(bǔ)貼可表示為其中:z是Beckmann最小化目標(biāo)函數(shù);x1.2小樣本中分析實踐證明,CTAP在線性約束條件下是嚴(yán)格凸問題,呈現(xiàn)獨特的道路流量全局最優(yōu)解。考慮w其中,將式(11)代入式(6)和(8)可得利用式(12)(13)可以證明,w在文獻(xiàn)中,beta項也可解釋為在過飽和的道路排隊堆積造成等待時間。如圖1所示,代表通行費或補(bǔ)貼價值的beta項是正數(shù),而補(bǔ)貼應(yīng)該是負(fù)值。接下來,將提出一種策略防止出現(xiàn)任何的負(fù)面循環(huán)。1.3提高出發(fā)時間首先假設(shè)只有收費和沒有補(bǔ)貼。在制定收費標(biāo)準(zhǔn)后,會把模型擴(kuò)大到補(bǔ)貼。考慮延遲函數(shù)t其中:b2基于啟動成本補(bǔ)償策略的送分策略2.1迭代圖的形化式(14)(15)的主要功能是解除過飽和道路的延時功能,直到交通量穩(wěn)定在容量水平內(nèi)。延遲函數(shù)中的初始beta值(beta(β其中:其中:上標(biāo)i和a表示當(dāng)前迭代和各自(過)飽和的道路圖1(a)中,給出式(17)～(19)膨脹延遲函數(shù)的三次迭代圖形化表示形式。在第一次迭代時,沒有初始beta值initialbeta(b在給出這種漸進(jìn)的方法中,如果一個(以上)飽和路發(fā)現(xiàn)是不飽和的,在中間的迭代位置,其相應(yīng)的懲罰是無效的。如圖1(b),即p上面設(shè)定符合在產(chǎn)能分配問題的KKT穩(wěn)定點條件,據(jù)前所述,beta項可解釋為在過飽和的道路排隊堆積造成等待時間,因此對于非飽和路段的beta值最終設(shè)定為0。2.2延遲函數(shù)現(xiàn)在可以把定價補(bǔ)貼包括在模型中。如前所述,一個負(fù)循環(huán)可能破壞整個定價過程。為了避免這種情況,確保道路的旅行時間始終保持為正常值。為此,首先取消所有收費/補(bǔ)助道路的免費通行時間,然后將beta初始化到相應(yīng)的自由流旅行時間。實際上,沒有任何變化,延遲函數(shù)保持不變:具體如圖1(c)所示,在迭代計算的最后一步,根據(jù)beta值,獲得在A或B上的延遲函數(shù)。beta值減去自由流時間β給定最后一次迭代(迭代n)輸出,收費/補(bǔ)貼值(-t2.3迭代算法的改進(jìn)圖2給出收費/補(bǔ)貼的定價方案流程。如果旅行需求高于網(wǎng)絡(luò)的容量,問題就變得不可行,可引入一個通過道路高行程時間與所有區(qū)域相連的虛擬節(jié)點。該算法可以很容易地集成到一個傳統(tǒng)的TAP解決方案中,如弗蘭克—沃爾夫方法。鑒于initial-beta值的逐漸積累,收斂準(zhǔn)則可定義為低于步數(shù)值的一個普通值,具體形式為計算結(jié)果表明:ε=1%就足以獲得可靠的結(jié)果。因此,該算法不終止,除非這兩個標(biāo)準(zhǔn)的相對差距和相對速度值得到滿足。迭代求解容量約束的拉格朗日乘子值的嘗試,事實上相當(dāng)于解決了原來CTAP部分的對偶變換。結(jié)果表明,部分對偶梯度問題導(dǎo)致交通量向量過大,次梯度法被認(rèn)為是一個有效的求解算法。2.4步長選擇機(jī)制上述算法本質(zhì)上是一種次梯度方法,可基于交通量過大的情況,迭代地更新對偶值。子梯度法的一個關(guān)鍵組成部分是步長,它被均勻地應(yīng)用于所有道路,并且可能在迭代過程中變化。為了保證收斂,步長值必須符合一組規(guī)則。相反,本文提出了一個直觀的步長選擇機(jī)制(類似于邊際成本),排斥每一條道路和迭代。上述方法的最優(yōu)性條件和收斂性方面,本文方法的新穎之處是將拉格朗日值轉(zhuǎn)換為通行費/補(bǔ)貼值。為此,當(dāng)CTAP終止時,自由流時間先清零;利用最終的旅行時間和原始的旅行時間函數(shù)的區(qū)別,指定收費/補(bǔ)貼值。3實驗分析3.1基于ip的新能源pc機(jī)該方法利用macro進(jìn)行編碼,這是一種交通規(guī)劃軟件Emme3的專用編程語言,其中無容量限制TAP過程采用弗蘭克—沃爾夫算法求解。使用一臺具有3.60GHz的CPU和16GBRAM的臺式PC機(jī);使用現(xiàn)實生活中的一個大型道路網(wǎng)絡(luò)例子對算法性能進(jìn)行驗證,該道路網(wǎng)絡(luò)案例,來自上海市,如圖3所示。該案例由154個區(qū)、943個節(jié)點和3075條定向道路組成,每小時的車輛通行需求量為56219輛。該城市是由兩個河流一分為二,河流位置位于城市的中間。根據(jù)流量調(diào)查和實地觀察,交通局提出了理想的交通分配,以避免在上午高峰時段發(fā)生重大交通堵塞。圖4中,1~11標(biāo)號為河流上的橋梁。在本研究中,收費/補(bǔ)貼的局部和目標(biāo)流量值是已知的,可由外部給定。為此在表1中,給出包括過境交通量在內(nèi)的過境點的特征量取值,其中t3.2預(yù)期需求的比較該算法迭代運行237次,直到相對間隙和相對步長值分別下降到0.0001和0.01以下,計算時間僅為15s。計算結(jié)果包括交通量、膨脹旅行時間以及通行費/補(bǔ)貼值如表2所示。為滿足交通量的限制,如x如果設(shè)定旅游需求預(yù)計達(dá)到5%,則意味著可達(dá)到59029.94人次。5%的增長可以被視為一年或兩年一次的城市交通增長,這樣就可以獲得一些在收費、補(bǔ)貼金額的年變化上的啟示。下面給出預(yù)計需求的比較結(jié)果,具體如表2實驗數(shù)據(jù)所示。通過收費/補(bǔ)貼公路的總交通流量從24407.3增加到25609.1,相當(dāng)于4.9%的增長。補(bǔ)貼和通行費的數(shù)額也出現(xiàn)了適度的變化,這是對最終結(jié)果穩(wěn)定的一種支持。選取圖3中,橋梁1、5、10、11四個路段進(jìn)行beta值收斂性驗證,其中,路段5位于市中心,其交通處于飽和狀態(tài),橋梁1、10、11路段處于郊區(qū),交通處于非飽和狀態(tài),beta值收斂實驗結(jié)果如圖5所示。根據(jù)圖5可知,選取的橋梁1、5、10、11四個路段均隨著迭代過程收斂,且橋梁1、10、11三個路段的beta值收斂到0值附近,而橋梁5的beta值收斂到非0值。這與前面表述相一致。4實驗結(jié)果和分析本文提出一種基于延遲函數(shù)的次梯度啟發(fā)式道路交通補(bǔ)償策略,是基于Beckmann最小化目標(biāo)函數(shù)實現(xiàn),然后利用庫恩—希爾斯條件和拉格朗日乘子建立模型的條件約束,并基于啟發(fā)式算法建立道路交通的定價補(bǔ)償策略,利用邊際成本建立延遲函數(shù)分析模型,然后基于次梯度法進(jìn)行模型的優(yōu)化。實驗結(jié)果表明,所提算法可有效實現(xiàn)對交通量和旅行時間的優(yōu)化,通過收費/補(bǔ)貼公路的總交通流量從24407.3增加到25609.1,增長4.9%,提高了通行率,并且對beta值的收斂性進(jìn)行了理論和實驗分析。下一步,