劉 慧,楊 超,楊 珺

(華中科技大學(xué)管理學(xué)院,武漢430074)

具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型研究

劉 慧,楊 超*,楊 珺

(華中科技大學(xué)管理學(xué)院,武漢430074)

由于交通網(wǎng)絡(luò)設(shè)計(jì)決策的長(zhǎng)期性,許多參數(shù)會(huì)隨時(shí)間而變化,因此在魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題中考慮不確定性因素至關(guān)重要.當(dāng)OD需求不確定時(shí),同時(shí)考慮期望行程時(shí)間和最大遺憾值,引入一種新的魯棒性度量標(biāo)準(zhǔn),將α-魯棒解的概念應(yīng)用到交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題中,提出了一種具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型.然后設(shè)計(jì)遺傳算法求解模型,得出不同遺憾值下網(wǎng)絡(luò)設(shè)計(jì)的最佳方案.最后,以Nguyen-Dupius網(wǎng)絡(luò)作為算例證明了遺傳算法求解魯棒性問(wèn)題的有效性.詳細(xì)分析了期望行程時(shí)間與最大遺憾值之間的權(quán)衡關(guān)系,權(quán)衡曲線表明,最大遺憾值的降低并不一定導(dǎo)致期望行程時(shí)間的較大增加;并將魯棒優(yōu)化模型與隨機(jī)優(yōu)化模型作比較,結(jié)果表明,魯棒優(yōu)化模型比隨機(jī)優(yōu)化模型更能規(guī)避不確定性帶來(lái)的風(fēng)險(xiǎn).

系統(tǒng)工程;交通網(wǎng)絡(luò)設(shè)計(jì);遺傳算法;魯棒優(yōu)化;遺憾值

1 引 言

交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題就是在各種給定的約束條件下,選擇路段新建(離散)或改善(連續(xù)),使其滿足某種均衡條件,最優(yōu)化交通網(wǎng)絡(luò)的系統(tǒng)性能.許多文獻(xiàn)將此問(wèn)題描述為雙層規(guī)劃或者帶均衡約束的數(shù)學(xué)規(guī)劃,關(guān)于交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的一些模型和算法,可以參考文獻(xiàn)[1-5].在實(shí)際的交通網(wǎng)絡(luò)設(shè)計(jì)中,許多參數(shù)(如OD需求、路徑的容量和費(fèi)用等)在網(wǎng)絡(luò)運(yùn)行中是不確定的.考慮不確定性對(duì)網(wǎng)絡(luò)設(shè)計(jì)的影響是投資者應(yīng)考慮的重要方面.如果為了問(wèn)題的簡(jiǎn)化而不考慮這些不確定因素對(duì)網(wǎng)絡(luò)設(shè)計(jì)的影響,將得到網(wǎng)絡(luò)設(shè)計(jì)的次優(yōu)方案.網(wǎng)絡(luò)在實(shí)際運(yùn)行中,參數(shù)一旦偏離預(yù)測(cè)值,將會(huì)造成運(yùn)行效率和服務(wù)水平低下、資源的浪費(fèi)等.

由于不確定性對(duì)交通網(wǎng)絡(luò)設(shè)計(jì)的重要性,近年來(lái)逐漸有文獻(xiàn)開(kāi)始考慮其對(duì)網(wǎng)絡(luò)設(shè)計(jì)的影響. Ukkusuri等[6]研究了基于情景的需求不確定網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題,目標(biāo)是最小化均值和方差的線性組合,分析不同權(quán)重下交通網(wǎng)絡(luò)設(shè)計(jì)的最優(yōu)結(jié)構(gòu). Ukkusuri等[7]同時(shí)考慮需求不確定和需求彈性的多階段網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題.Chen等[8]研究了需求不確定下交通網(wǎng)絡(luò)設(shè)計(jì)的隨機(jī)多目標(biāo)模型,提出了期望值、機(jī)會(huì)約束和概率函數(shù)的多目標(biāo)雙層規(guī)劃模型來(lái)規(guī)避需求不確定帶來(lái)的風(fēng)險(xiǎn).Sharmal等[9]建立了基于需求不確定的多目標(biāo)網(wǎng)絡(luò)設(shè)計(jì)模型,同時(shí)最小化均值和方差.Dimitriou和Stathopoulos[10]使用均值模型和機(jī)會(huì)約束規(guī)劃模型來(lái)研究可靠性隨機(jī)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題.Yin等[11]采用“盒子”作為不確定需求的集合,研究了基于隨機(jī)用戶均衡下的連續(xù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題.Chen等[12]采用條件風(fēng)險(xiǎn)值作為風(fēng)險(xiǎn)指標(biāo)去優(yōu)化交通系統(tǒng)的總體性能.Lou等[13]考慮了需求不確定的離散容量擴(kuò)張,其目標(biāo)是最小化最大值.Chootinan等[14]提出了新的容量可靠性指標(biāo),即路段的交通量小于其容量的概率,并以這個(gè)指標(biāo)來(lái)設(shè)計(jì)隨機(jī)網(wǎng)絡(luò).Karoonsoontawong和Waller[15]考慮短期的交通動(dòng)態(tài)分配和長(zhǎng)期的OD需求不確定性,研究了魯棒性動(dòng)態(tài)連續(xù)網(wǎng)絡(luò)設(shè)計(jì)模型.Ng和Waller[16]將系統(tǒng)行程時(shí)間小于一定值的概率作為約束,研究了均值方差模型.Chen等[17]系統(tǒng)綜述了不確定環(huán)境下的網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題,并提出了雙目標(biāo)可靠性網(wǎng)絡(luò)設(shè)計(jì)模型.孫華等[18]假設(shè)OD需求不確定且屬于一個(gè)有界區(qū)間,建立用戶均衡約束的交通網(wǎng)絡(luò)設(shè)計(jì)的極小極大模型.陸化普等[19]在需求不確定情況下,基于隨機(jī)雙層規(guī)劃和均值方差理論,建立網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型.

以上的研究均表明考慮不確定因素在交通網(wǎng)絡(luò)設(shè)計(jì)中至關(guān)重要.本文在以上研究的基礎(chǔ)上,引入一種新的度量魯棒性的標(biāo)準(zhǔn),同時(shí)考慮期望行程時(shí)間和最大遺憾值兩個(gè)目標(biāo),提出具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型.首先介紹遺憾模型的定義,建立具有遺憾值約束的雙層交通網(wǎng)絡(luò)設(shè)計(jì)模型,并設(shè)計(jì)遺傳算法求解模型,得出不同遺憾值下,網(wǎng)絡(luò)設(shè)計(jì)的最佳方案.最后,利用數(shù)值算例說(shuō)明算法的有效性,分析了期望行程時(shí)間與遺憾值之間的權(quán)衡關(guān)系,并將魯棒優(yōu)化模型與隨機(jī)優(yōu)化模型進(jìn)行比較.

2 模型的建立

2.1 遺憾模型

假設(shè)Ω是情景的集合.令(Qw)表示情景w下確定性最優(yōu)化問(wèn)題.對(duì)于每個(gè)情景w∈Ω,令表示問(wèn)題(Qw)的最優(yōu)目標(biāo)函數(shù)值.假設(shè)＞0 (?w∈Ω).

定義 設(shè)α≥0是一個(gè)給定的常數(shù).令X是所有問(wèn)題(Qw)的可行解,zw(X)是問(wèn)題(Qw)在解X下的目標(biāo)函數(shù)值.X稱為α-魯棒解,若對(duì)于所有的w∈Ω有

或,等價(jià)地

式(1)左端稱為情景w下的相對(duì)遺憾,絕對(duì)遺憾為zw(X)-z*w,下文中提到的遺憾都是指相對(duì)遺憾.將α-魯棒解應(yīng)用于最小化期望目標(biāo)函數(shù)值則得到如下遺憾模型:

式中 pw表示情景w實(shí)現(xiàn)的概率;Θ是對(duì)于所有問(wèn)題(Qw)的可行解集合.

2.2 具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型

在一個(gè)交通網(wǎng)絡(luò)G=(N,A)中,N表示節(jié)點(diǎn)的集合,A表示路段的集合.網(wǎng)絡(luò)中OD需求是不確定的,本文使用情景分析法對(duì)OD需求可能出現(xiàn)的情景進(jìn)行描述,假設(shè)情景發(fā)生的主觀概率可以設(shè)定.

在給定的預(yù)算下,通過(guò)改善已有路段的通行能力,使其在滿足用戶均衡條件和α-魯棒解約束下,系統(tǒng)的期望行程時(shí)間最優(yōu).

為了表述的方便,先將文中用到的參數(shù)和變量定義如下:

流量;

pww情景實(shí)現(xiàn)的概率;

α最大遺憾值;

ra路段a的現(xiàn)有通行能力;

va對(duì)路段a采用擴(kuò)建策略,路段a增加的通行能力;

γa擴(kuò)建路段a的成本;

y{1,路段a采用擴(kuò)張策略,

a

0,路段a維持現(xiàn)狀不變.

應(yīng)用以上符號(hào),本文提出的具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題可以描述為以下雙層規(guī)劃模型:

模型(Pro)由上層規(guī)劃U和下層規(guī)劃L組成.上下層規(guī)劃通過(guò)決策變量y和路段交通量x相互聯(lián)系.上層表示系統(tǒng)的目標(biāo)函數(shù)最優(yōu),系統(tǒng)的目標(biāo)函數(shù)是行程時(shí)間的期望值.約束(5)是魯棒解約束.約束(6)是預(yù)算約束.約束(7)表示y為0-1變量.下層函數(shù)是用戶均衡問(wèn)題.路段行程時(shí)間用BPR函數(shù)表示:.其中FFTa表示路段a上的自由行程時(shí)間;Ca表示路段a的容量;σ和β是BPR參數(shù).

模型(Pro)區(qū)別于一般的網(wǎng)絡(luò)設(shè)計(jì)模型在于:下層L考慮了需求的不確定性;上層U不僅最優(yōu)化期望的行程時(shí)間,還要滿足約束(5).約束(5)表明:模型(Pro)的最優(yōu)解在任何情景實(shí)現(xiàn)時(shí)的目標(biāo)函數(shù)值與該情景下確定性問(wèn)題最優(yōu)目標(biāo)函數(shù)值相對(duì)差在給定的范圍內(nèi).α稱為遺憾值,約束(5)稱為遺憾值約束.當(dāng)α=∞時(shí),約束(5)失效,此時(shí)的問(wèn)題為在預(yù)算約束下,最小化期望行程時(shí)間,即交通網(wǎng)絡(luò)設(shè)計(jì)的隨機(jī)優(yōu)化模型,記為(Psp),問(wèn)題(Psp)僅考慮系統(tǒng)行程時(shí)間的期望,而不考慮遺憾值.

3 算法設(shè)計(jì)

3.1 遺傳算法

由于模型(Pro)的非線性和非凸性,傳統(tǒng)的方法很難用來(lái)解具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型.本文使用遺傳算法(Genetic Algorithm)來(lái)解模型(Pro),主要技術(shù)描述如下:

3.1.1 編碼與解碼規(guī)則

本問(wèn)題只對(duì)y進(jìn)行編碼,再將y代入下層規(guī)劃求解用戶均衡問(wèn)題(UE Assignment),算例中采用Frank-Wolfe來(lái)解下層用戶均衡問(wèn)題,Frank-Wolfe算法參考Sheffi(1985)[20].決策變量y為二進(jìn)制變量,每個(gè)變量可表示成1或0,1表示對(duì)路段a采用擴(kuò)建策略,0表示路段a維持現(xiàn)狀不變.

3.1.2 計(jì)算個(gè)體的適應(yīng)度

個(gè)體適應(yīng)度根據(jù)上層規(guī)劃的目標(biāo)函數(shù)值來(lái)計(jì)算.問(wèn)題(Pro)帶有約束(5)和(6),本算法利用罰函數(shù)法來(lái)處理約束條件(5),使用下列改進(jìn)的適應(yīng)度:

式中 I(x)是示性函數(shù),定義如下:

g是決策者調(diào)節(jié)的參數(shù),用來(lái)懲罰違反遺憾值約束的個(gè)體.

對(duì)于約束條件(6),本算法使用貪婪法將違背預(yù)算約束條件的解轉(zhuǎn)化為可行解.若當(dāng)前種群中的個(gè)體y′不滿足預(yù)算,即,先求出,然后依次將中最小且y′a=1的路段變?yōu)閥′a=0,直到滿足約束條件(6)為止.該操作在算法中用函數(shù)transform()表示,此函數(shù)將違背預(yù)算約束的解轉(zhuǎn)化為可行解.

3.2 算法步驟

假設(shè)最大迭代次數(shù)為K.遺傳算法求解模型(Pro)具體步驟如下:

Step 1 生成初始種群Y,k←0;

Step 2 根據(jù)Y的值,更新網(wǎng)絡(luò)中的參數(shù);

Step 3 對(duì)于每種情景,利用Frank-Wolfe算法求解下層用戶均衡問(wèn)題;

Step 4 將得到的路徑流量帶入適應(yīng)度(11);

Step 5 根據(jù)個(gè)體適應(yīng)度,對(duì)群體進(jìn)行選擇、交叉、變異運(yùn)算,形成新一代種群Y;

Step 6 用函數(shù)transform()將個(gè)體對(duì)應(yīng)的解轉(zhuǎn)化為可行解;

Step 7 若k＞K,算法終止;否則k←k+1,轉(zhuǎn)到Step 2.

4 算法的實(shí)現(xiàn)與算例分析

4.1 算例的設(shè)計(jì)

本節(jié)的算例中使用Nguyen和Dupius (1984)[21]網(wǎng)絡(luò),說(shuō)明遺傳算法求解具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型的有效性.網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示,Nguyen-Dupius網(wǎng)絡(luò)被廣泛用于交通均衡問(wèn)題的研究中.對(duì)魯棒性交通設(shè)計(jì)問(wèn)題用MATLAB對(duì)第3節(jié)提出的算法進(jìn)行編碼,然后在CPU為Intel Core i5-2450M 2.50GHz,內(nèi)存為4.00GB的計(jì)算機(jī)上進(jìn)行試驗(yàn).Nguyen-Dupius網(wǎng)絡(luò)的參數(shù)見(jiàn)表1.表2為OD需求的均值,所有OD對(duì)之間獨(dú)立.假設(shè)需求的變異系數(shù)取0.5,群體的大小取pop_size=25.采用無(wú)回放余數(shù)隨機(jī)選擇,交叉概率取在0.7-0.95之間,變異概率取在0.01-0.2之間.最大循環(huán)次數(shù)為500,違背魯棒性約束的懲罰因子g=50.假設(shè)若對(duì)路段a采用擴(kuò)建策略,則路段a通行能力增加100%,則擴(kuò)建后路段a通行能力Ca=(1+ya)ra.算例中相對(duì)遺憾值取0.65.

圖1 Nguyen-Dupius網(wǎng)絡(luò)Fig.1 Nguyen-Dupius test network

表1 Nguyen-Dupius網(wǎng)絡(luò)參數(shù)Table 1 Network parameters for the Nguyen-Dupius network

表2 Nguyen-Dupius網(wǎng)絡(luò)的期望OD需求對(duì)Table 2 The expected OD demand for the Nguyen-Dupius network

4.2 遺傳算法性能測(cè)試

用第3節(jié)提出的算法對(duì)魯棒優(yōu)化模型(Pro)進(jìn)行求解,遺傳算法的進(jìn)化過(guò)程如圖2所示,當(dāng)進(jìn)化進(jìn)行到大約200次時(shí),用遺傳算法求得的解逐漸收斂到最優(yōu)解.為了測(cè)試不同參數(shù)對(duì)遺傳算法結(jié)果的影響,本節(jié)還對(duì)OD需求變異系數(shù)分別取0.3和0.6的情況,隨機(jī)生成OD需求,進(jìn)行測(cè)試.算例均表明,遺傳算法在進(jìn)化到200次左右,遺傳算法的解逐漸收斂到最優(yōu)解.

4.3 數(shù)值結(jié)果與分析

根據(jù)4.1節(jié)設(shè)計(jì)的算例,OD需求的變異系數(shù)取0.5,隨機(jī)生成需求量,利用本文第3節(jié)設(shè)計(jì)的遺傳算法,在不同遺憾值下求得的最優(yōu)解和最優(yōu)值如表3所示,表3最后一行表示模型(Pro)的目標(biāo)函數(shù)值,即總的系統(tǒng)行程時(shí)間(TSTT,total system travel time).從表3可以看出,隨著遺憾值的增加,期望行程時(shí)間降低.

圖2 Nguyen-Dupius網(wǎng)絡(luò)設(shè)計(jì)種群進(jìn)化過(guò)程Fig.2 Population evolution process for designing Nguyen-Dupius network

具有遺憾值約束的魯棒性交通網(wǎng)絡(luò)設(shè)計(jì)模型的一個(gè)重要目的是降低最大遺憾值(通過(guò)選擇不同的α)的同時(shí)盡可能減少期望行程時(shí)間的增加,即期望行程時(shí)間與最大遺憾值之間的權(quán)衡.為了闡述這種權(quán)衡關(guān)系,本節(jié)通過(guò)調(diào)節(jié)α的值來(lái)生成期望行程時(shí)間與最大遺憾值的權(quán)衡曲線.首先,令α=∞,求解模型(Pro),即求解隨機(jī)交通網(wǎng)絡(luò)設(shè)計(jì)模型(Psp),記錄最優(yōu)值和最大遺憾值,見(jiàn)表4中第二行.然后,逐漸降低α的值,求解模型(Pro),直到可行解集為空集為止.不同遺憾值下的目標(biāo)函數(shù)值和最大遺憾值如表4所示.第一列表示用來(lái)求解模型(Pro)的不同遺憾值;第二列表示利用遺傳算法求得的目標(biāo)函數(shù)值;第三列表示目標(biāo)函數(shù)值相對(duì)于α=∞時(shí)增加的百分比;第四列表示各種情景下的最大遺憾值;第五列表示最大遺憾值相對(duì)于α=∞時(shí)降低的百分比.期望行程時(shí)間與最大遺憾值的權(quán)衡曲線如圖3所示.

表3 不同遺憾值下魯棒優(yōu)化模型的最優(yōu)解Table 3 The optimal solution of robust network design model for different value of α

表4 不同遺憾值下的目標(biāo)函數(shù)值與最大遺憾值Table 4 The optimal objective value and the maximum regret value for different value of α

顯然,最大遺憾值的較快降低并不一定以目標(biāo)函數(shù)值的較大增加為代價(jià).例如,當(dāng)α=0.578 2時(shí),最大遺憾值降低26.39%,而目標(biāo)函數(shù)值僅增加2.55%,這說(shuō)明較強(qiáng)的魯棒性不一定意味著期望行程時(shí)間的較大增加.從圖3也可以清楚地看到這一點(diǎn),圖3中的權(quán)衡曲線比較陡峭,尤其是最大遺憾值較大時(shí),說(shuō)明較少的增加期望行程時(shí)間可能換來(lái)遺憾值的較大降低.根據(jù)期望行程時(shí)間與最大遺憾值之間的權(quán)衡關(guān)系,交通網(wǎng)絡(luò)的設(shè)計(jì)者可以根據(jù)期望行程時(shí)間,計(jì)算出最大遺憾值;或者根據(jù)最大遺憾值的限制,計(jì)算出期望行程時(shí)間.

圖3 期望行程時(shí)間與最大遺憾值的權(quán)衡曲線Fig.3 Trade-off curve of objective value and the maximum regret value

4.4 魯棒優(yōu)化模型與隨機(jī)優(yōu)化模型的比較

本節(jié)將帶有遺憾值約束的魯棒優(yōu)化模型(Pro)與隨機(jī)優(yōu)化模型(Psp)的結(jié)果進(jìn)行比較.針對(duì)上述設(shè)計(jì)的交通網(wǎng)絡(luò),分別用魯棒優(yōu)化模型(Pro)和隨機(jī)優(yōu)化模型(Psp)對(duì)交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題進(jìn)行求解,在兩個(gè)模型參數(shù)保持一致的情況下,比較兩者的性能.

令w情景下確定性模型(Pw)最優(yōu)目標(biāo)函數(shù)值為,魯棒優(yōu)化的解對(duì)在情景w下的目標(biāo)函數(shù)值為,隨機(jī)優(yōu)化的解在情景w下的目標(biāo)函數(shù)值為.取與的相對(duì)遺憾值100%,與的相對(duì)遺憾值100%.數(shù)值計(jì)算結(jié)果如表5所示.隨機(jī)優(yōu)化模型的最優(yōu)解在各種情景下目標(biāo)函數(shù)的平均值為924 604,魯棒優(yōu)化模型的最優(yōu)解在各種情景下目標(biāo)函數(shù)的平均值為965 167.顯然,隨機(jī)優(yōu)化模型的平均值小于魯棒優(yōu)化模型的平均值,后者與前者的相對(duì)差值為4.38%.但是,這只是目標(biāo)函數(shù)值的差異,而二者同確定性問(wèn)題最優(yōu)值的差異,即和,也不容忽視.從表5可以看出,隨機(jī)優(yōu)化的解在10種情景下,最大遺憾值為54.70%,最小遺憾值為1.03%,而魯棒優(yōu)化的解在10種情景下,最大遺憾值為39.64%,最小遺憾值為21.75%.前者遺憾值的方差為2.97%,而后者遺憾值的方差僅為0.27%.表明前者遺憾值的波動(dòng)較大,而后者較小.魯棒優(yōu)化模型的最優(yōu)值雖然比隨機(jī)優(yōu)化的最優(yōu)值增加了4.38%,但是前者遺憾值的波動(dòng)比后者降低了90.94%.

本節(jié)隨機(jī)生成的其他算例也表明,魯棒優(yōu)化模型的設(shè)計(jì)結(jié)果雖然比隨機(jī)優(yōu)化模型期望值大,但是前者遺憾值的波動(dòng)較小.即魯棒優(yōu)化與隨機(jī)優(yōu)化相比,目標(biāo)函數(shù)值的增加較小,但是卻能使最大遺憾值和遺憾值的波動(dòng)都有較大的降低.人們對(duì)交通網(wǎng)絡(luò)設(shè)計(jì)決策的評(píng)價(jià)往往是不確定性情景實(shí)現(xiàn)后(可以觀測(cè)到具體的參數(shù)值)做出的,利用魯棒優(yōu)化模型,使人們對(duì)交通網(wǎng)絡(luò)系統(tǒng)決策方案評(píng)價(jià)的波動(dòng)更小.網(wǎng)絡(luò)系統(tǒng)對(duì)各種情景表現(xiàn)出不敏感性,使得網(wǎng)絡(luò)設(shè)計(jì)的魯棒性更強(qiáng).因此,魯棒優(yōu)化模型設(shè)計(jì)出的交通網(wǎng)絡(luò)能夠較好地規(guī)避不確定性帶來(lái)的風(fēng)險(xiǎn).

表5 魯棒優(yōu)化與隨機(jī)優(yōu)化的結(jié)果比較Table 5 Comparison between the results of robust optimization and the stochastic optimization

5 研究結(jié)論

許多不確定因素影響著交通網(wǎng)絡(luò)的設(shè)計(jì),明確考慮這些不確定因素對(duì)網(wǎng)絡(luò)設(shè)計(jì)方案的影響至關(guān)重要.研究不確定性問(wèn)題的方法主要有隨機(jī)優(yōu)化和魯棒性優(yōu)化兩種.本文結(jié)合隨機(jī)優(yōu)化和魯棒性優(yōu)化的優(yōu)點(diǎn),在假設(shè)OD需求不確定的情況下,引入一種新的度量魯棒性的標(biāo)準(zhǔn),即α-魯棒性,提出具有遺憾值約束的魯棒優(yōu)化模型,即在后悔值帶有約束的情況下,最小化期望系統(tǒng)行程時(shí)間.數(shù)值算例說(shuō)明了最大遺憾值的較快降低并不一定以目標(biāo)函數(shù)值的較大增加為代價(jià),即較強(qiáng)的魯棒性不一定意味著期望行程時(shí)間的較大增加.與隨機(jī)優(yōu)化模型相比,魯棒優(yōu)化模型設(shè)計(jì)出的交通網(wǎng)絡(luò)能夠更好地規(guī)避不確定性帶來(lái)的風(fēng)險(xiǎn).本文提出的具有遺憾值約束的交通網(wǎng)絡(luò)設(shè)計(jì)模型為決策者提供了一種新的魯棒性標(biāo)準(zhǔn),使交通網(wǎng)絡(luò)的性能在參數(shù)攝動(dòng)的情況下魯棒性更強(qiáng).然而,本文的算法用于中等規(guī)模的網(wǎng)絡(luò)和數(shù)量較小的情景時(shí)比較有效,對(duì)于大規(guī)模的網(wǎng)絡(luò)和大量的情景,計(jì)算時(shí)間顯著增加,設(shè)計(jì)有效的算法是以后深入研究的問(wèn)題.采用系統(tǒng)總走行時(shí)間的總阻抗的期望是不確定模型中最常用的目標(biāo),處理不確定問(wèn)題的模型還有機(jī)會(huì)約束模型、概率模型、α可靠性模型等,如何將α-魯棒解與這些模型結(jié)合起來(lái),也是今后我們要研究的一個(gè)重要問(wèn)題.

[1] Unnikrishnan A,Lin D Y.User equilibrium with recourse:continuous network design problem[J]. Computer-Aided Civil and Infrastructure Engineering, 2012,27(7):512-524.

[2] Chiou S.Bilevel programming for the continuous transport network design problem[J].Transportation Research,2005,39(4):362-383.

[3] Davis G A.Exact local solution of the continuous network design problem via stochastic user equilibrium assignment[J].Transportation Research,1994,28 (1):61-75.

[4] Farvaresh H,Sepehri M.A single-level mixed integer linear formulation for a bi-level discrete network design problem[J].Transportation Research Part E: Logistics and Transportation Review,2011,47(5): 623-640.

[5] Xu T Z,Wei H,Hu G H.Study on continuous network design problem using simulated annealing and genetic algorithm[J].Expert Systems with Applications, 2009,36(2):1322-1328.

[6] Ukkusuri S V,Mathew T V,Waller S T.Robust transportationnetworkdesignunderdemand uncertainty[J].Computer-AidedCiviland Infrastructure Engineering,2007,22(1):6-18.

[7] Ukkusuri S V,Patil P.Multi-period transportation networkdesignunderdemanduncertainty[J]. TransportationResearchPartB:Methodological, 2009,43(6):625-642.

[8] Chen A,Kim J Y,Lee S,et al.Stochastic multiobjective models for network design problem[J]. Expert Systems with Applications,2010,37(2): 1608-1619.

[9] Sharmal S,Ukkusuri S V,Mathew T V.Pareto optimalmulti-objectiveoptimizationforrobust transportationnetworkdesignproblem[J]. TransportationResearchRecord:Journalofthe Transportation Research Board,2009,2090:95-104. [10] Dimitriou L,Stathopoulos A.Reliable stochastic design of road network systems[J].International Journal of Industrial and Systems Engineering,2008,3(5): 549-574.

[11] Yin Y,Madanat S M,Lu X.Robust improvement schemes for road networks under demand uncertainty [J].European Journal of Operation Research,2009, 198(2):470-479.

[12] Chen A,Kim J,Zhou Z,et al.Alpha reliable network design problem[J].Transportation Research Record, 2007,2029:49-57.

[13] Lou Y,Yin Y,Lawphongpanich S.A robust approach to discrete network designs with demand uncertainty [J].Transportation Research Record,2009,2090: 86-94.

[14] Chootinan P,Wong S C,Chen A.A reliability-based network design problem[J].Journal of Advanced Transportation,2005,39(3):247-270.

[15] Karoonsoontawong A,Waller S T.Robust dynamic continuousnetworkdesignproblem[J]. Transportation Research Record,2007,2029:58-71. [16] Ng M,Waller S T.Reliable system-optimal network design:convex mean-variance model with implicit chance constraints[J].TransportationResearch Record,2009,2090:68-74.

[17] Chen A,Zhou Z,Chootinan P,et al.Transport network design problem under uncertainty:a review and new developments[J].Transport Reviews:A Transnational Transdisciplinary Journal,2011,31 (6):743-768.

[18] 孫華,高自友,龍建成.不確定OD需求下連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(2):70-76.[SUN H,GAO Z Y, LONGJC.Therobustmodelofcontinuous transportation network design problem with demand uncertainty[J].Journal of Transportation System Engineering and Information Technology,2011,11 (2):70-76.]

[19] 陸化普,蔚欣欣,卞長(zhǎng)志.OD需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型研究[J].公路交通科技,2011, 28(5):128-132.[LU H P,WEI X X,BIAN C Z. Modelandalgorithmofdiscretenetworkdesign problem under OD dem and uncertainty[J].Journal ofHighwayandTransportationResearchand Development,2011,28(5):128-132.]

[20] Sheffi Y.Urban transportation networks:equilibrium analysiswithmathematicalprogrammingmethods [M].Prentice-Hall,Englewood Cliffs,NJ,1985.

[21] Nguyen S,Dupius C.An efficient method for computing trafficequilibriainnetworkswithasymmetric transportation costs[J].Transportation Science, 1984,18(2):185-202.

Robust Transportation Network Design Modeling with Regret Value

LIU Hui,YANG Chao,YANG Jun
(School of Management,Huazhong University of Science&Technology,Wuhan 430074,China)

Based on long-term transportation network design decisions and potential parameter variations,it is important that demand uncertainty is considered in transportation modeling.In this paper,we present a novel robustness measure that combines the two objectives by minimizing the expected travel time while bounding the relative regret in each scenario facing uncertain origin-destination demand(OD demand).The concept of α-robust solution is introduced into the transportation network design problem.We propose a robust transportation network design model with regret value constraints,then design an algorithm based on the genetic algorithm to solve the problem and obtain the optimal solutions for different regret values. Finally,numerical results based on the Nguyen-Dupuis network validate the effectiveness of the algorithm. While detailed analysis on trade-offs,between the expected travel time and the maximum regret value,shows that large reductions in maximum regret do not necessarily result in a great increase in expected travel time. Meanwhile,we compared the robust model presented with the stochastic model and numerical examples demonstrate that the robust planning network is more reliable and less risky than the stochastic model if demand uncertainty is considered in modeling.

system engineering;traffic network design;genetic algorithm;robust optimization; regret value

U491

: A

U491

A

1009-6744(2013)05-0086-07

2012-10-17

2013-01-29錄用日期:2013-02-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(70871044,71172093);教育部人文社會(huì)科學(xué)研究青年基金項(xiàng)目(10YJC630331).

劉慧(1982-),女,湖北谷城人,博士生.

*通訊作者:chao_yang@mail.hust.edu.cn