謝桃楓,陳國慶*,曹瑾鑫

(內(nèi)蒙古大學(xué)a.數(shù)學(xué)科學(xué)學(xué)院,呼和浩特010021;b.交通學(xué)院運輸工程系,呼和浩特010070)

修建成本不確定的交通網(wǎng)絡(luò)設(shè)計問題

謝桃楓a,陳國慶*a,曹瑾鑫b

(內(nèi)蒙古大學(xué)a.數(shù)學(xué)科學(xué)學(xué)院,呼和浩特010021;b.交通學(xué)院運輸工程系,呼和浩特010070)

交通網(wǎng)絡(luò)設(shè)計問題是交通規(guī)劃理論的一個重要組成部分,即在資金有限且考慮出行者決策行為的情況下,制定最優(yōu)投資策略.由于人工費、材料費和使用費等的不確定性,路段的修建成本存在不確定性.本文通過改進預(yù)算投資約束,應(yīng)用魯棒優(yōu)化的方法同時考慮出行者的路徑選擇行為,建立路段修建成本不確定的交通網(wǎng)絡(luò)設(shè)計的魯棒模型,并利用基于割約束的混合整數(shù)線性規(guī)劃算法求解此模型,進而得到一個受修建成本擾動較小的魯棒最優(yōu)解.通過算例表明,在修建成本不確定的交通網(wǎng)絡(luò)設(shè)計中,本文提出的魯棒優(yōu)化方法可以得到比傳統(tǒng)確定性問題更加可靠的解.

城市交通;不確定混合整數(shù)線性規(guī)劃;不確定投資成本;魯棒優(yōu)化法;交通網(wǎng)絡(luò)設(shè)計

1 引 言

交通網(wǎng)絡(luò)設(shè)計問題的主要目標(biāo)是通過對現(xiàn)有交通網(wǎng)絡(luò)增加新的路段或提高已有路段的通行能力,從而使整個交通網(wǎng)絡(luò)某種系統(tǒng)性能達(dá)到最優(yōu).一般來說,交通網(wǎng)絡(luò)設(shè)計問題可分為三類,即連續(xù)交通網(wǎng)絡(luò)設(shè)計問題、離散交通網(wǎng)絡(luò)設(shè)計問題和混合交通網(wǎng)絡(luò)設(shè)計問題.長期以來,交通網(wǎng)絡(luò)設(shè)計問題一直被認(rèn)為是交通研究領(lǐng)域中難度最大的問題之一.目前在交通網(wǎng)絡(luò)設(shè)計問題方面,國內(nèi)外已經(jīng)有許多學(xué)者做過大量的研究,并設(shè)計了求解算法.

Sumalee在路段的造價方面,利用GA-AS算法進行求解[1].Meng把雙層規(guī)劃模型利用臨界價值函數(shù)轉(zhuǎn)化為連續(xù)可微的單層規(guī)劃模型,且用增廣拉格朗日算法尋找精確局部解[2].Wang針對連續(xù)網(wǎng)絡(luò)設(shè)計問題進行討論,通過把雙層規(guī)劃問題近似為一個混合整數(shù)線性規(guī)劃問題來尋找近似全局最優(yōu)解[3].此方法是先對非線性函數(shù)離散化,再用線性函數(shù)近似非線性函數(shù).Edmunds和Bard針對雙層規(guī)劃問題進行研究,文中要求下層模型的目標(biāo)函數(shù)是凸二次函數(shù),所有的約束條件都是線性的,再利用分支定界法對混合整數(shù)非線性雙層規(guī)劃模型求解全局最優(yōu)解[4].Luathep把文獻[3]中的連續(xù)交通網(wǎng)絡(luò)設(shè)計問題推廣到混合交通網(wǎng)絡(luò)設(shè)計問題中,把混合非線性網(wǎng)絡(luò)設(shè)計問題利用分段線性法轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題,最終得到近似全局最優(yōu)解或近似全局最優(yōu)解的上界[5].

近年來,不確定交通網(wǎng)絡(luò)設(shè)計問題主要集中于對不確定需求的研究.Yin和Lawpongpanich研究不確定需求下的靜態(tài)連續(xù)均衡的網(wǎng)絡(luò)設(shè)計問題[6].Ordonez和Zhao制定和解決了一個靜態(tài)的網(wǎng)絡(luò)設(shè)計模型,其需求和旅行時間控制在一個靜態(tài)的多面體集合中[7].Mudchanatongsuk等延續(xù)了Ordonez和Zhao的工作,通過考慮一些不確定需求的推廣假設(shè),研究一個道路約束的網(wǎng)絡(luò)設(shè)計問題,并引入列生成方法解決帶有多面體不確定集合的魯棒網(wǎng)絡(luò)設(shè)計問題[8].Ban等認(rèn)為魯棒道路收費問題包含多個流量分配方案[9].Yin等確定了需求不確定條件下的魯棒優(yōu)化道路網(wǎng)絡(luò)改善計劃[10].Lou等描述了一個離散網(wǎng)絡(luò)設(shè)計問題,用戶均衡流是基于不確定預(yù)算的概念,利用切平面法求解問題[11].

在文獻[5]中,預(yù)算投資約束是用一個簡單線性函數(shù)表示,即每一條路段的修建成本是確定的.由于人工費、材料費和使用費等的不確定性,路段的修建成本存在不確定性.為了克服現(xiàn)有方法在處理投資成本不確定性方面的局限性,通過改進預(yù)算投資約束,本文提出了基于魯棒優(yōu)化方法的投資成本不確定的交通網(wǎng)絡(luò)設(shè)計問題,利用割約束的混合整數(shù)線性規(guī)劃算法對模型進行求解.通過算例證明魯棒優(yōu)化方法可以得到比傳統(tǒng)確定性優(yōu)化方法更可靠的解.

2 主要符號說明

A1——不擴建道路的集合;

A2——擴建道路的集合;

A3——新建道路的集合;

A——道路的集合,A=A1∪A2∪A3,|A|=α;

?——交通網(wǎng)絡(luò)節(jié)點的集合,? =R;

O——所有起點的集合,O??;

D——所有終點的集合,D??;

?——凸多面體的極點的集合;

?——指標(biāo)集,?={0,…,M,M+1,…,M +N};

o——起點,o∈O;

d——終點,d∈D;

s——極點指標(biāo),s∈?;

xa——第a條道路的流量,?a∈A;

xsa——凸多面體的第s個極點,?a∈A;

qod——起點o至終點d的出行需求;

vod——起點o至終點d路段a的流量,?a∈A;

a

ya——擴建道路a增加的容量,?a∈A2;

y*——新建道路a的固定容量,?a∈A;

a3

x-——路段a的最大流量,?a∈A;

a

y-a——擴建道路a的原始容量,?a∈A2; y-——擴建道路a后增加的容量,?a∈A;

a2

y-*——新建道路a的最大容量,?a∈A;

a

3

X——路段流量組成的向量;

Qod——起點o至終點d的出行需求形成的R ×1向量;

vod——起點o至終點d路段流量的向量;

Λ——由發(fā)生變量組成的R×α發(fā)生矩陣;

χa——

g(ya)——擴建道路的價值函數(shù),?a∈A3;

ta(xa)——沒有擴建道路的出行時間函數(shù),?a∈A1;

ta(xa,ya)——擴建道路的出行時間函數(shù),?a∈A2;

ta(xa,y*

a)——新建道路的出行時間函數(shù),?a∈A3;

tij(xij)——起點是i,終點是j的道路的出行時間;

t0——起點是i,終點是j的道路的自由出行

ij時間;

在利用分段函數(shù)線性化時,引入如下變量:

M——對xa分M段;

N——對ya分N段;

λma——?a∈A1∪A3;

κma——?a∈A1∪A3;

μma——SOS1變量,即至多有一個變量是正值,其他都為零,μma∈ [0,1],?m=1,2,…, M,a∈A2;

υna——SOS1變量,υna∈[0,1],?n=1,2,…,N,a∈A2;

Γηa——SOS2變量,至多有兩個變量是非零值,若兩個值是正值,則這兩個值是相鄰的,?η∈?,a∈A2;

γm,n——連續(xù)變量,γm,n∈[0,1],?m=1,aa…,M,n=1,…,N,a∈A2,

φa——雙線性變量,φa=xaχa,?a∈A3;

Ca——增加單位容量所需的費用,?a∈A2;

da——新加一條路所需的費用,?a∈A3;

K——新建路段的最大流量;

B——預(yù)算投資;

U——足夠大的正常數(shù);

3 交通網(wǎng)絡(luò)設(shè)計模型及其魯棒優(yōu)化方法

3.1 交通網(wǎng)絡(luò)設(shè)計模型

混合整數(shù)線性規(guī)劃模型是在混合交通網(wǎng)絡(luò)設(shè)計模型的基礎(chǔ)上利用分段線性函數(shù)法對非線性函數(shù)進行線性化.線性化后得到的確定性混合整數(shù)線性規(guī)劃模型[P1]為

式(1)表示目標(biāo)函數(shù),達(dá)到總的出行時間最小.式(2)表示預(yù)算約束.式(3)表示滿足UE條件的變分不等式約束.式(4)～式(9)表示路段流量、路段容量、旅行時間的范圍約束.式(10) ～式(16)表示不修建道路和新建道路的分段線性函數(shù)約束.式(17)～式(29)表示擴建道路的分段線性函數(shù)的約束.式(30)～式(32)表示雙線性項φa= xaχa的線性約束.

3.2 交通網(wǎng)絡(luò)設(shè)計模型的魯棒優(yōu)化方法

魯棒優(yōu)化考慮的是最壞情況下的最好,它代表一種保守的觀點,得到的優(yōu)化解并不一定是最優(yōu)的,但是當(dāng)不確定參數(shù)發(fā)生擾動時,得到的解仍然是可行的.魯棒優(yōu)化方法可以把不確定的系數(shù)控制在一個有界區(qū)間,從而得到受修建成本擾動較小的魯棒解.目前,魯棒凸優(yōu)化有很大的發(fā)展.Goh基于線性決策規(guī)則用模塊結(jié)構(gòu)對不確定的線性規(guī)劃問題求近似魯棒解,文中介紹了隔離不確定性導(dǎo)出新的決策規(guī)則的方法[12].Chen通過不對稱分布改善不確定集,對變化的約束問題有更好的近似魯棒解[13].Sim對價格的魯棒化做了大量的工作,把傳統(tǒng)的魯棒結(jié)構(gòu)轉(zhuǎn)化為線性結(jié)構(gòu)、二次結(jié)構(gòu)、二階錐結(jié)構(gòu)等,這樣的形式轉(zhuǎn)變使得模型求解容易[14]. Janak對混合整數(shù)線性規(guī)劃中確定的參數(shù)進行魯棒優(yōu)化,由于隨機變量符合不同的分布函數(shù),得到不同的不確定模型[15].在交通網(wǎng)絡(luò)設(shè)計問題中,通常情況下,假設(shè)修建道路的成本是定值,而忽略了不確定性成本在模型優(yōu)化方面和可行性方面的影響.然而,由于實際成本和預(yù)算成本的不同,最終得到的優(yōu)化解可能是不可行的,或是不能達(dá)到系統(tǒng)性能最優(yōu).在文獻[5]中,投資價值函數(shù)g(ya)用一個簡單的線性形式表示,即g(ya)=Caya.但事實上,該函數(shù)中的線性系數(shù)Ca在實際中普遍存在不確定性.因此,有必要對約束條件式(2)中的投資成本進行魯棒化.從而得到

式中 ξa2,ξa3,ξB是獨立隨機變量,ε ＞0是給定的不確定水平.

考慮不等式(33)的可行性,該不等式可以寫成下列形式:

根據(jù)實值和名義值的關(guān)系,式(34)可以寫為

可進一步化簡為

設(shè)隨機變量的和為

考慮下列形式:

該約束迫使不確定不等式的違反概率至多為k.

定義概率分布函數(shù)為

從而生成一個對于給定的不確定水平ε,不可行容限δ,可靠性水平k的基本可行的決定性約束.

通過對問題進行魯棒化,得到不確定的交通網(wǎng)絡(luò)模型[P2],即

滿足約束條件式(3)～式(32).

4 不同概率分布的不確定交通網(wǎng)絡(luò)設(shè)計模型

上一節(jié)在隨機變量ξa2,ξa3,ξB的分布函數(shù)是未知的情況下進行討論,為了能得到精確的概率測度,在本節(jié)將討論隨機變量滿足均勻概率分布和正態(tài)概率分布的情況.首先介紹魯棒解的定義:

命題1(y,x)是一個魯棒解,若(y,x)滿足下列條件:

(1)(y,x)是原始問題的可行解.

(2)不等式(33)的概率測度至多是k,即

4.1 隨機變量滿足均勻概率分布

假設(shè)在成本約束中只有一個不確定的參數(shù),它可以寫為

或

或

式中 ξa2,ξa3,ξB是在區(qū)間[-1,1]滿足均勻分布的隨機變量.

定理1給定不確定水平,不可行容限δ和可靠性水平k,隨機變量滿足均勻分布,不確定的交通網(wǎng)絡(luò)設(shè)計模型[P2]可以寫成下列形式:

或

或

滿足約束條件式(3)～式(32).其中a2*,a3*表示系數(shù)是不確定的道路.

證明設(shè)(y,χ)滿足下列條件:

若Ca2*是不確定系數(shù),則

若da3*是不確定系數(shù),則

若B是不確定的常數(shù),則

4.2 隨機變量滿足正態(tài)概率分布

假設(shè)隨機變量ξa2,ξa3,ξB的分布滿足期望為0,標(biāo)準(zhǔn)差為1的標(biāo)準(zhǔn)正態(tài)分布,則式(35)中的ξ的分布是期望為0,標(biāo)準(zhǔn)差為的正態(tài)分布.記ζ=

定理2給定不確定水平,不可行容限δ和可靠性水平k,隨機變量滿足期望為0,標(biāo)準(zhǔn)差為ζ的正態(tài)分布,則不確定的交通網(wǎng)絡(luò)設(shè)計模型[P2]可以寫成下列形式:

滿足約束條件式(3)～式(32).

在此λ=F-1

n(1-k),λ和k滿足下列關(guān)系:

式中 ξ是標(biāo)準(zhǔn)正態(tài)分布的隨機變量.證明設(shè)(y,χ)滿足下列條件:

在此λ=Fn-1(1-k),Fn-1是標(biāo)準(zhǔn)正態(tài)分布函

[證畢]

數(shù)的逆函數(shù),則

[證畢]

由于

也是標(biāo)準(zhǔn)正態(tài)分布的隨機變量,則最終形成一個混合整數(shù)非線性規(guī)劃問題.

5 算 法

混合整數(shù)線性規(guī)劃問題可由CPLEX12.4有效求解.本文中,有界凸多面體的極點由有限生成算法得到[16].有限生成的混合整數(shù)線性規(guī)劃算法是先通過有限生成算法得到多面體的所有極點,再對混合整數(shù)線性規(guī)劃模型進行松弛,得到松弛混合整 數(shù)線性規(guī)劃模型[P3],即

滿足約束條件式(4)～式(32).

求解松弛混合整數(shù)線性規(guī)劃模型的優(yōu)化解即得混合整數(shù)線性規(guī)劃的優(yōu)化解.

基于割約束的混合整數(shù)線性規(guī)劃算法(MILPCCA)步驟如下:

第一步 求凸多面體的任意一個極點s,令i =0,X(i)=[x1(i),x2(i),…,xa(i)].

第二步 解混合整數(shù)線性規(guī)劃模型[P3],得到的解為ω(i).

第三步 利用解ω(i),求解公式

第四步 若解ω(i)滿足

停止,否則,轉(zhuǎn)到第五步.

第五步對有界多面體Ω的極點進行更新, X(i+1)=X(i)∪*,令i=i+1,轉(zhuǎn)第二步.

6 數(shù)值試驗

本節(jié)通過兩個算例對本文所提的算法進行驗證.本試驗在Inter Core 2 Duo、CPU 2.10 GHz、內(nèi)存2.00GB PC機上使用 Microsoft Visual Studio 2008和CPLEX 12.4函數(shù)庫編程實現(xiàn).

6.1 離散交通網(wǎng)絡(luò)設(shè)計試驗

本文以圖1中12個結(jié)點和一個 (O,D)對 (1,12)組成的網(wǎng)絡(luò)為基準(zhǔn)進行試驗.圖1表示12個結(jié)點的交通網(wǎng)絡(luò)圖,包含12個結(jié)點、17條現(xiàn)有路段(實線表示)、6條備選新建路段(虛線表示).已存在道路的自由出行時間由實線上的數(shù)字表示,新建道路的自由出行時間由括號中的第一個值表示,新建道路的投資成本值由括號中的第二個值表示,新建道路的標(biāo)號由括號中第三個值表示.每條路的旅行時間函數(shù)表示為tij(xij)=t0ij+0.008x4ij.假設(shè)O-D的總需求是20.假設(shè)參數(shù)的概率分布滿足均勻分布,不確定水平 ε=5%,不可行容限δ=20%和可靠性水平k=24%.

圖1 12個結(jié)點的網(wǎng)絡(luò)Fig.1 The 12-node network

計算結(jié)果如表1所示,它表明隨著政府預(yù)算投資的增大,用戶的旅行時間會變小.在預(yù)算投資達(dá)到一定的時候,用戶的旅行時間會趨于一個定值.由于投資成本的不確定,魯棒解會趨于定值,最終名義解和魯棒解達(dá)到一致.這說明預(yù)算投資足夠大時,投資成本對用戶旅行時間影響很小.

表1 例1的計算結(jié)果Table 1 The results for 12-node network

6.2 連續(xù)交通網(wǎng)絡(luò)設(shè)計試驗

圖2表示由6個結(jié)點,8條路段,一個(O,D)對(1,6)組成的交通網(wǎng)絡(luò)圖.道路標(biāo)號由括號中的第一個值表示,自由出行時間由括號中的第二個值表示,擴建投資成本由括號中的第三個值表示.圖中有8條現(xiàn)有路段,假設(shè)現(xiàn)需擴建這8條路段,隨機變量的概率分布滿足均勻分布,不確定水平ε =5%,不可行容限δ=20%和可靠性水平k= 24%.每條路的旅行時間函數(shù)表示為 tij(xij)=

從表2中可以看出,政府的投資越多,擴建的道路越多,每條道路的旅行時間越小,這樣用戶可以降低每條路的旅行時間;同時政府在擴建同一路段時,投資可多可少,這也反映了擴建成本的不確定性.在預(yù)算投資不同的情況下,可看出名義解的變化很大,但是魯棒解卻在一定范圍內(nèi)變化,這也說明了魯棒解更可靠.

圖2 6個結(jié)點網(wǎng)絡(luò)道路Fig.2 The 6-node network

表2 例2的計算結(jié)果Table 2 The results for 6-node network

7 研究結(jié)論

本文考慮了路段修建成本不確定的魯棒交通網(wǎng)絡(luò)設(shè)計問題,由于交通網(wǎng)絡(luò)上的路段修建成本存在不確定性,應(yīng)用魯棒優(yōu)化的方法同時考慮出行者的路徑選擇行為,建立交通網(wǎng)絡(luò)設(shè)計的魯棒模型.該方法把不確定的系數(shù)控制在一個有界的區(qū)間,進而得到一個受修建成本擾動較小的魯棒最優(yōu)解.由于隨機變量滿足不同的概率分布,文中分別討論分析滿足均勻分布和正態(tài)分布的不確定交通網(wǎng)絡(luò)設(shè)計問題,并運用基于割約束的混合整數(shù)線性規(guī)劃算法對滿足均勻分布的不確定交通網(wǎng)絡(luò)設(shè)計模型求解.算例表明,在投資成本不確定的交通網(wǎng)絡(luò)設(shè)計問題中,本文提出的魯棒優(yōu)化方法可以得到比傳統(tǒng)確定性優(yōu)化方法更加可靠的解.本文提出的求解算法適用于線性情況,開發(fā)針對非線性情況的求解算法將是下一步研究的內(nèi)容之一.此外,本文只對修建成本不確定的交通網(wǎng)絡(luò)設(shè)計問題進行詳細(xì)的說明,O-D需求和修建成本同時不確定的交通網(wǎng)絡(luò)設(shè)計問題是今后另外一個重要的研究內(nèi)容.

[1]Sumalee A.Multi-concentric optimal charging cordon design [J].Transportmetrica,2007,3(1):41-71.

[2]Meng Q,Yang H,Bell M G H.An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem [J]. Transportation Research Part B,2001,35(1): 83-105.

[3]Wang Z W.Global optimum of the linearized network design problem with equilibrium flows [J]. Transportation Research Part B,2010,44:482-492.

[4]Edmunds T A,Bard J F.An algorithm for the mixedinteger nonlinear bilevel programming problem[J]. Annals of Operations Research,1992,34:149-162.

[5]Luathep P.Global optimization method for mixed transportation network design problem: A mixedinteger linear programming approach [J]. Transportation Research Part B,2011,45:808-827.

[6]Yin Y,Lawpongpanich S.A robust approach to continuous network design with demand uncertainty[J]. Transportation and Traffic Theory,2007,17:111-126.

[7]Ordonez F,Zhao J.Robust capacity expansion of network flows[J].Networks,2007,50:136-145.

[8]Mudchanatongsuk S,Ordonez F,Liu J.Robust solutions for network design under cost and demand uncertainty [J]. OperationalResearch Society, 2008, 59: 652-662.

[9]Ban X,Lu S,Ferris M,et al.Risk-averse secondbest toll pricing.Transportation and Traffic Theory. 2009,18:197-218.

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

[11]Lou Y,Yin Y,Lawphongpanich S.A robust approach for discrete network design under demand uncertainty [C].In the proceedings of the 88th Transportation Research Board Meeting,2008.

[12]Goh J,Sim M.Distributionally robust optimization and its tractable approximations [J].Operations Research,2010,58(4):902-917.

[13]Chen M,Alfa A.A network design algorithm using a stochastic incrementaltraffic assignmentapproach [J].Transportation Science,1991,25(3):215-224.

[14]Sim M.Robust optimization[D].PhD thesis, Massachusetts Institute of Technology,2004.

[15]Janak S,Lin X.A new robust optimization approach for scheduling under uncertainty:II.Uncertainty with known probability distribution[J].Computers and Chemical Engineering,2007,31:171-195.

[16]魏權(quán)齡,閆洪.廣義最優(yōu)化理論和模型[M].北京:科學(xué)出版社,2006.[WEI Q L,YAN H.Generalized optimization theories and models[M].Beijing:Science Press,2006.]

Network Design Problem with Uncertain Construction Costs

XIE Tao-fenga,CHEN Guo-qinga,CAO Jin-xinb
(a.School of Mathematical Sciences,Hohhot 010021,China;b.Department of Transportation Engineering, Inner Mongolia University,Hohhot 010070,China)

The transportation network design problem is an important component of transportation planning theory.With consideration of limited financial resources and travelers'decision-making behavior,it aims to develop the optimal investment strategy.In this paper,a novel network design problem under uncertain construction costs is proposed.Based on the robust optimization method,the budget investment constraints are improved to overcome the limitations of the existing approaches.A global optimization algorithm based on a limited generated method is developed for solving the mixed integer linear programming.A series of comprehensive computational experiments show that in transportation network design problem,the proposed robust optimization method can provide more reliable solutions than the traditional deterministic optimization methods.

urban traffic;uncertain mixed integer linear programming;uncertain investment cost;robust optimization method;transportation network design

U12

A

U12

A

1009-6744(2013)01-0034-09

2012-07-10

2012-09-13錄用日期:2012-09-25

國家自然科學(xué)基金項目(71061010);內(nèi)蒙古自治區(qū)高等學(xué)?？茖W(xué)研究項目(NJ10009);內(nèi)蒙古大學(xué)高層次人才引進科研啟動項目(210221).

謝桃楓(1986-),女,內(nèi)蒙古烏蘭察布市人,碩士生.

*通訊作者:cgq@imu.edu.cn