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

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

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