具有遺憾值約束的魯棒性交通網絡設計模型研究

劉 慧,楊 超,楊 珺

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

具有遺憾值約束的魯棒性交通網絡設計模型研究

劉 慧,楊 超*,楊 珺

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

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

系統(tǒng)工程;交通網絡設計;遺傳算法;魯棒優(yōu)化;遺憾值

1 引 言

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

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

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

2 模型的建立

2.1 遺憾模型

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

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

或,等價地

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

式中 pw表示情景w實現的概率;Θ是對于所有問題(Qw)的可行解集合.

2.2 具有遺憾值約束的魯棒性交通網絡設計模型

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

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

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

流量;

pww情景實現的概率;

α最大遺憾值;

ra路段a的現有通行能力;

va對路段a采用擴建策略,路段a增加的通行能力;

γa擴建路段a的成本;

y{1,路段a采用擴張策略,

a

0,路段a維持現狀不變.

應用以上符號,本文提出的具有遺憾值約束的魯棒性交通網絡設計問題可以描述為以下雙層規(guī)劃模型:

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

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

3 算法設計

3.1 遺傳算法

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

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

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

3.1.2 計算個體的適應度

個體適應度根據上層規(guī)劃的目標函數值來計算.問題(Pro)帶有約束(5)和(6),本算法利用罰函數法來處理約束條件(5),使用下列改進的適應度:

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

g是決策者調節(jié)的參數,用來懲罰違反遺憾值約束的個體.

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

3.2 算法步驟

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

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

Step 2 根據Y的值,更新網絡中的參數;

Step 3 對于每種情景,利用Frank-Wolfe算法求解下層用戶均衡問題;

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

Step 5 根據個體適應度,對群體進行選擇、交叉、變異運算,形成新一代種群Y;

Step 6 用函數transform()將個體對應的解轉化為可行解;

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

4 算法的實現與算例分析

4.1 算例的設計

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

圖1 Nguyen-Dupius網絡Fig.1 Nguyen-Dupius test network

表1 Nguyen-Dupius網絡參數Table 1 Network parameters for the Nguyen-Dupius network

表2 Nguyen-Dupius網絡的期望OD需求對Table 2 The expected OD demand for the Nguyen-Dupius network

4.2 遺傳算法性能測試

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

4.3 數值結果與分析

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

圖2 Nguyen-Dupius網絡設計種群進化過程Fig.2 Population evolution process for designing Nguyen-Dupius network

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

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

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

顯然,最大遺憾值的較快降低并不一定以目標函數值的較大增加為代價.例如,當α=0.578 2時,最大遺憾值降低26.39%,而目標函數值僅增加2.55%,這說明較強的魯棒性不一定意味著期望行程時間的較大增加.從圖3也可以清楚地看到這一點,圖3中的權衡曲線比較陡峭,尤其是最大遺憾值較大時,說明較少的增加期望行程時間可能換來遺憾值的較大降低.根據期望行程時間與最大遺憾值之間的權衡關系,交通網絡的設計者可以根據期望行程時間,計算出最大遺憾值;或者根據最大遺憾值的限制,計算出期望行程時間.

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

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

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

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

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

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

5 研究結論

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

[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ù)交通網絡設計的魯棒優(yōu)化模型[J].交通運輸系統(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] 陸化普,蔚欣欣,卞長志.OD需求不確定的離散交通網絡設計模型研究[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

國家自然科學基金資助項目(70871044,71172093);教育部人文社會科學研究青年基金項目(10YJC630331).

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

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