基于時間目標函數(shù)的交通網(wǎng)絡(luò)規(guī)劃研究

基于時間目標函數(shù)的交通網(wǎng)絡(luò)規(guī)劃研究

1機動車總量和交通堵塞近年來，隨著人民生活水平的不斷提高，汽車的剛性需求保持了旺盛，汽車用量保持了快速增長的趨勢。據(jù)統(tǒng)計，2016年新增車輛2752萬輛，新增車輛21212萬輛，均處于歷史最高水平。根據(jù)調(diào)查研究表明,交通堵塞問題十分嚴峻,在全國范圍內(nèi),平均每天浪費接近十億小時在交通堵塞問題上本文在文獻2節(jié)點-至目的點為了進一步分析本文提出的問題,本章給出了相關(guān)路網(wǎng)信息的定義。其中,路網(wǎng)、起-終點、可達路徑的相關(guān)定義均參考文獻定義1(路網(wǎng)W)利用一個有向集合表示路網(wǎng)W,現(xiàn)將W用一個點相關(guān)的矩陣來表示,代表路網(wǎng)的拓撲結(jié)構(gòu)。定義W∈R由圖1所示的路網(wǎng)拓撲圖,從節(jié)點(1)到節(jié)點(4),一共有4個節(jié)點和6條路段。其中,在節(jié)點(1)時,路段1、路段4和路段5可駛出車輛,所以在矩陣中用數(shù)字1表示;路段2將匯入車輛,所以用數(shù)字-1表示;節(jié)點(1)在路段3既沒有車輛匯入也沒有匯出,記為數(shù)字0。同理可寫出其他節(jié)點在各個路段的表達,即可寫出W的表達式,如圖2所示。定義2(起點-終點c)定義c是一個列向量,為m×1的矩陣,表示車輛從起始節(jié)點到目的節(jié)點的一個描述符,宏觀地描述起點-終點,不同車輛的起始點可能各不相同,記為c定義3(空載時間T定義4(可達路徑)為了確保車輛能從起始節(jié)點S到目的節(jié)點D,用行向量x假設(shè)本文所研究的車輛可以人為來主觀地控制,要協(xié)作地分配這些車輛的路徑,最基本的原則是所有的車輛必須有一條路徑可選擇,確保到達所期望的目的地。在數(shù)學(xué)表達上,要保證到達目的地的所有車輛可以表示為以下的網(wǎng)絡(luò)流守恒方程:3車輛行駛時間的目標函數(shù)在不考慮車輛協(xié)作和利他的情況下,若從某個起點到某一終點,當所有人都選擇最優(yōu)路徑,將會導(dǎo)致這條道路出現(xiàn)嚴重堵塞,整個路網(wǎng)上所有車輛總的用時必然增多當路網(wǎng)上有p輛車時,現(xiàn)用一個集合來表示所有車輛選擇的路徑,可以表示為X=(x假設(shè)某一路段的流量為q,這一路段的最大流量為q式(2)中,v當在同一路段上,距離是一定的,根據(jù)距離s、速度v與時間t的三者關(guān)系:由式(3)、(4)可將式(2)推廣為:本文中,從起點S到終點D,當整個路網(wǎng)有p輛車時,它們各自對應(yīng)的行駛路徑為X=(x式(6)中,T通過上面的推導(dǎo),可得出t是一個1×p的矩陣,t=(t車輛行駛時間的目標函數(shù)可由下式表示:4模型解決方案和利益因素的確定4.1拉格朗日函數(shù)和互補松弛函數(shù)根據(jù)前一章節(jié)對問題的描述,以及列出的問題模型,本章利用拉格朗日乘子法假設(shè)該問題可解,且存在最優(yōu)的x令h(x構(gòu)成一個新的函數(shù):滿足KKT條件:條件(1)為拉格朗日必要條件;條件(2)為拉格朗日系數(shù)約束;條件(3)為不等式約束;條件(4)為互補松弛條件;條件(5)與條件(6)稱為原約束條件。在上述6個約束條件下,可求出滿足目標函數(shù)的解x綜合車輛行駛時間目標函數(shù)的建立和求解,拉格朗日求解算法可通過如下偽代碼實現(xiàn):算法1拉格朗日求解算法4.2渡到系統(tǒng)均衡社會導(dǎo)航,就是給人們提供出行路徑的一個決策,但是又包含有“社會”的概念,從傳統(tǒng)的用戶均衡過渡到系統(tǒng)均衡,旨在使整個路網(wǎng)上所有車輛所用的時間最小,并不只是為了減少個人的出行時間。利他因子(?)是社會導(dǎo)航中一個關(guān)鍵性的參數(shù),在本文中,利他因子?表示當整個路網(wǎng)上有p輛車時,其中從某個起點S到終點D的最優(yōu)路徑為x從上文已得出使整個路網(wǎng)上所有車輛所用時間最少的最優(yōu)出行路徑為X5模擬結(jié)果與分析5.1信息收集通過深入分析人車融合發(fā)展趨勢及人、車、環(huán)境協(xié)同需求5.2最優(yōu)路徑出行仿真為了驗證模型的正確性和可行性,本文在MATLAB環(huán)境假設(shè)起始節(jié)點為(1),目的節(jié)點為(6),可知從節(jié)點(1)到節(jié)點(6)的最優(yōu)路徑為(1)→(3)→(6),次優(yōu)路徑為(1)→(2)→(4)→(6),其中最優(yōu)路徑上的空載時間為120min,次優(yōu)路徑上的空載時間為180min。另外,假設(shè)路網(wǎng)上總的車輛數(shù)p為100輛,橫軸表示選擇最優(yōu)路徑的車輛數(shù),縱軸表示整個路網(wǎng)上總的時間。通過仿真可知,當選擇最優(yōu)路徑的車輛數(shù)為何值時,總時間的變化趨勢,以及a、b參數(shù)對道路的影響力,結(jié)果分別如圖4、圖5所示。如圖4所示,當橫軸值為0時,表示選擇最優(yōu)路徑的車輛數(shù)為0,即所有車輛都選擇次優(yōu)路徑,整個路網(wǎng)總時間為最大;其次,當橫軸為100時,即所有車輛均選擇最優(yōu)路徑,會造成部分堵塞,因此總的時間也會上升。以圖中綠色曲線為例,由拉格朗日算法求出的最優(yōu)出行路徑為:其中,x當控制a為定值0.4時,考慮b的取值對時間的影響時,結(jié)果如圖5所示。同樣發(fā)現(xiàn),當橫軸值為0時,表示選擇最優(yōu)路徑的車輛數(shù)為0,即所有車輛都選擇次優(yōu)路徑,整個時間肯定是最大的;其次,當橫軸為100時,即所有車輛均選擇最優(yōu)路徑,定會造成部分堵塞,因此總的時間也會稍稍上升;最后,發(fā)現(xiàn)不是所有車輛都選擇最優(yōu)路徑時整個路網(wǎng)的時間是最少的,當一部分車輛犧牲自己選擇不是最優(yōu)路徑時,總的時間總能有一個近似最優(yōu)的值,說明仿真結(jié)果與前面的理論分析是相符合的。當參數(shù)a的值不變時,考慮b的取值對時間的影響,會發(fā)現(xiàn),當b的值越大,路網(wǎng)上總的時間越小,同時它的最小值點越向右偏移,說明b的值越大,最優(yōu)路徑的道路承受能力越強。如圖3所示的六節(jié)點路網(wǎng)示意圖,從起始節(jié)點(1)到目的節(jié)點(6),最短路徑為(1)→(3)→(5),路徑(1)→(2)→(4)→(5)→(6)、(1)→(3)→(4)→(5)→(6)、(1)→(3)→(4)→(6)均為備選路徑。仿真過程中,為了固定變量,假設(shè)a=0.4,b=1.0,驗證當p=50,p=100,…,p=300時,不考慮社會導(dǎo)航,所有車輛全部選擇最優(yōu)路徑時與考慮社會導(dǎo)航時,對比兩種情況下整個路網(wǎng)上總的行駛時間,結(jié)果如圖6所示。如圖6所示,當路網(wǎng)上車輛數(shù)越多時,全局總時間也在逐漸增多。當路網(wǎng)上有50輛車時,沒有超出道路負載,全部走最優(yōu)路徑時的時間比使用社會導(dǎo)航所用的時間少。但是,當有100輛甚至更多車輛的時候,使用社會導(dǎo)航時整個路網(wǎng)總時間要比無社會導(dǎo)航時的時間少。綜上,由仿真結(jié)果可以看出與理論分析相一致,證明社會導(dǎo)航算法可以在全局上優(yōu)化總行駛時間。針對不同的起點S和終點D,無論路網(wǎng)上車輛數(shù)為何值,當使目標函數(shù)(即整個路網(wǎng)上時間)最小時,都能求出所有車輛的路線,將所求出的X通過對目標函數(shù)的求解,得出以下仿真結(jié)果,如表1所示。由上述仿真結(jié)果可知,對不同的起始點-目的節(jié)點,不同的車輛數(shù)下,相較于所有車輛同時選擇最優(yōu)路段,社會導(dǎo)航算法通過利他系數(shù),減少路網(wǎng)總的行駛時間,實現(xiàn)了城市場景下的路網(wǎng)負載的全局均衡與最優(yōu)。另外,當車輛數(shù)越多時,更能清楚地看出來有社會導(dǎo)航比無社會導(dǎo)航節(jié)省的時間越多,在車輛數(shù)較多的路網(wǎng)上優(yōu)化效果更加明顯。6仿真實驗結(jié)果本文通過對道路交通路網(wǎng)進行分析,將道路信息表示為矩陣的形式,并在此基礎(chǔ)上定義矩陣路網(wǎng)模型;其次,建立車輛行駛時間目標函數(shù)