基于魯棒非線性規(guī)劃的連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)模型

孫 華，趙方霞

（1.航天海鷹機(jī)電技術(shù)研究院有限公司，北京 100070；2.北京交通大學(xué)，北京 100044）

基于魯棒非線性規(guī)劃的連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)模型

孫 華1，趙方霞2

（1.航天海鷹機(jī)電技術(shù)研究院有限公司，北京 100070；2.北京交通大學(xué)，北京 100044）

通過運(yùn)用魯棒非線性優(yōu)化理論提出了連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)(Continuous Network Design Problem,CNDP)魯棒非線性模型。通過采用靈敏度分析方法，將其魯棒對(duì)應(yīng)（Robust Counterpart，RC）模型轉(zhuǎn)換成一系列帶互補(bǔ)約束的數(shù)學(xué)規(guī)劃問題(Mathemtical Progrms Complementarity Constraints，MPCC),并采用松弛算法進(jìn)行求解。數(shù)值實(shí)驗(yàn)顯示，提出的不確定需求在橢球集合下的基于用戶均衡的CNDP模型更加靈活。

魯棒非線性優(yōu)化；連續(xù)交通網(wǎng)絡(luò)；靈敏度分析；帶互補(bǔ)約束的數(shù)學(xué)規(guī)劃問題

1 引言

過去的連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)問題（Continuous Network Design Problem,CNDP）研究主要考慮確定性問題。但是，現(xiàn)實(shí)的交通系統(tǒng)往往存在各種不確定因素，并且很難知道這些不確定因素的隨機(jī)分布。因此，近年來越來越多的學(xué)者利用魯棒優(yōu)化研究連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)問題。比如，Yin和Lawphongpanich[1]研究了不確定需求在橢球集合下基于用戶均衡的CNDP問題，并提出一種割平面的方法來求解其魯棒對(duì)應(yīng)模型。Yin等[2]和Yin等[3]將他們提出的模型應(yīng)用到高速公路連續(xù)設(shè)計(jì)問題和基于C-Logit的連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)問題。Lou等[4]提出了基于有限理性用戶均衡的魯棒收費(fèi)模型。然而，上面的研究都沒有把相應(yīng)的魯棒非線性約束轉(zhuǎn)化為易于求解的魯棒線性約束，因此得到的魯棒解比較保守。本文基于Houska和Diehl[5]的魯棒非線性規(guī)劃，提出了一個(gè)不確定需求在橢球集合下的基于用戶均衡的CNDP模型。通過靈敏度分析，將模型轉(zhuǎn)化為一系列MPCC問題，并采用松弛算法求解。

2 RC模型

2.1 Yin和Lawphongpanich[1]的RC模型

為討論方便，首先定義一些符號(hào)：

N：網(wǎng)絡(luò)上節(jié)點(diǎn)集合；

A：路段集合，a∈A：

W：OD對(duì)集合，w∈W；

Rw：OD對(duì)w之間的路徑集合，p∈Rw；

xa：路段a∈A的流量，x=(...,xa,...)；

ya：路段a∈A增加的通行能力，y=(...,ya,...)；

ta(xa,ya)：路段a∈A的走行時(shí)間函數(shù)；

Q：不確定需求集合；

d：不確定需求，d∈Q；

ha(ya)：路段a∈A的投資函數(shù)；

B：總預(yù)算。

基于上面的符號(hào)，CNDP的RC模型能夠?qū)懗桑?/p>

λw是OD對(duì)w∈W 的最小走行時(shí)間，式（1）和式（8）表示極小化最壞情況下的系統(tǒng)走行時(shí)間；式（2）是投資約束，式（4）-式（7）是用戶均衡條件，式（9）是路段a∈A增加能力的非負(fù)約束。

2.2 CNDP的魯棒非線性對(duì)應(yīng)模型

首先將上面的RC模型轉(zhuǎn)化如下：

μ1,μ2,μ3,μ4,μ5為式（12）-式（15）和式（17）對(duì)應(yīng)的拉格朗日乘子。

如果w=w1，I{w,w1}=1，否則 I{w,w1}=0。從式（39）-（45）可以看出，模型RC1的求解關(guān)鍵是。下面利用靈敏度的方法得到

2.3 靈敏度分析

首先假定f*＞0是路徑流量可行域F(d)的極點(diǎn)，則有：

π是非負(fù)路徑流量相關(guān)的拉格朗日乘子。當(dāng)僅僅考慮非退化的極點(diǎn)，式（46）-式（49）就變成：

這里c0,f0,Λ0是當(dāng)d=d0,y=y0時(shí)，路徑均衡流量f*0＞0所對(duì)應(yīng)的路徑走行時(shí)間、路徑流量和路段路徑矩陣。式（50）、（51）兩邊做關(guān)于需求d的微分，于是得到：

3 求解算法與數(shù)值算例

3.1 求解算法

應(yīng)用松弛算法[6]求解上面的模型RC1，步驟如下：

第三步：按照上一步計(jì)算得到的?f(d0,y0)/?d和?λ(d0,y0)/?d ，求解模型RC1。如下：

Step 3.1初始αn＞0，置迭代步數(shù)限制M以及更新因子0＜γ＜1，此時(shí)n=0。

Step 3.2設(shè)置輔助參數(shù)α＞0，求解下面的模型RC1-NLP：

其他約束見式（21）-（23）、式（25）-（26）、式（28）-（29）、式（31）-（32）、式（34）-（35）、式（37）-（38）。

Step 3.3如果n≤M ，那么 αn+1=γαn，?t,ω,k，n=n+1，回第2步，否則到第4步。

Step 3.4求救RC1-NLP，如果成功，得到RC1-NLP的精確最優(yōu)解，否則，第3步最后得到的解作為模型的近似解。

第四步：計(jì)算上面的模型RC1得到dw、ya和zk，若(zk+1-zk)/zk≤ε（ε是給定的精度），迭代終止，否則，，轉(zhuǎn)第二步。這里將應(yīng)用GAMS的非線性規(guī)劃求解器CONOPT來求解RC1-NLP模型。

3.2 數(shù)值算例

為驗(yàn)證上面提出的基于魯棒非線性規(guī)劃的連續(xù)網(wǎng)絡(luò)設(shè)計(jì)模型，采用Hearn和Ramana網(wǎng)絡(luò)[7]進(jìn)行數(shù)值實(shí)驗(yàn)。這里路段走行時(shí)間函數(shù)采用如下形式的BPR函數(shù)：

cka表示路段a∈A上現(xiàn)有的通行能力，表示路段a∈A的自由走行時(shí)間（具體取值見文獻(xiàn)[7]）。OD對(duì)w的“代表”值為。路段投資函數(shù)為ha(ya)=ya,a∈A。需要注意的是前面RC模型，將采用割平面[1]算法求解。

圖1 Hearn和Ramana的網(wǎng)絡(luò)

表1描述了當(dāng)B=50時(shí)，“代表”解、RC模型魯棒解和RC1模型的魯棒解，“代表”解是基于“代表”需求計(jì)算得到的。圖2給出了當(dāng)B從10到100變化時(shí)，“代表”解和RC模型魯棒解的相對(duì)差值，以及“代表”解和RC1模型解間的相對(duì)差值的變化情況，這里“代表”解yN和RC模型的魯棒解yRC間的差值定義為：

“代表”解yN和RC1模型的魯棒解yRC1間的差值定義為：

從圖2可以看出，兩組差值都隨著B的增加而減少，當(dāng)B=80,90,100，兩組差值都很小。但是，“代表”解yN和RC1模型魯棒解yRC1之間的差值小于“代表”解yN和RC模型的魯棒解yRC之間的差值，這說明RC1模型比RC模型更加靈活。

表1 投資預(yù)算B=50時(shí)，“代表”解、RC模型的魯棒解和RC1模型的魯棒解

表2給出了模型RC和模型RC1的目標(biāo)函數(shù)以及目標(biāo)函數(shù)的相對(duì)差值。從表2可以看出，RC1模型的目標(biāo)函數(shù)更小，這說明RC1模型更加靈活。

下面比較“代表”解、RC模型魯棒解和RC1模型魯棒解的差異。為此，每個(gè)OD對(duì)w∈W，在[0.5,1.5]間隨機(jī)產(chǎn)生300個(gè)均勻分布的需求d?w，同時(shí)保證它們屬于集合Q。對(duì)于隨機(jī)產(chǎn)生的需求d?，分別基于三個(gè)解產(chǎn)生的系統(tǒng)走行時(shí)間，圖3比較了三種解產(chǎn)生的目標(biāo)函數(shù)的期望和標(biāo)準(zhǔn)差相對(duì)差值，圖3中有四條曲線，兩條是代表解的期望（標(biāo)準(zhǔn)差）與模型RC魯棒解的期望（標(biāo)準(zhǔn)差）間的相對(duì)差值，另兩條是代表解的期望（標(biāo)準(zhǔn)差）與模型RC1魯棒解的期望（標(biāo)準(zhǔn)差）間的相對(duì)差值。具體定義如下：

從圖3可以看出，模型RC的魯棒解yRC和模型RC1的魯棒解yRC1的系統(tǒng)走行時(shí)間期望都比代表解yN大，但是模型RC魯棒解yRC和模型RC1魯棒解yRC1的系統(tǒng)走行時(shí)間標(biāo)準(zhǔn)差都比代表解yN小。這說明模型RC的魯棒解yRC和RC1模型的魯棒解yRC1比代表解yN更加穩(wěn)定。但是，模型RC的魯棒解yRC比模型RC1的魯棒解yRC1產(chǎn)生更大的期望和標(biāo)準(zhǔn)差，這說明模型RC的魯棒解yRC更加保守。

圖2 代表解和RC模型魯棒解間的相對(duì)差值以及代表解和RC1型魯棒解的相對(duì)差值

表2 不同預(yù)算B下，模型RC和模型RC1的目標(biāo)函數(shù)及相對(duì)差異

圖3 代表解、RC模型和RC1模型產(chǎn)生的目標(biāo)函數(shù)間的期望和標(biāo)準(zhǔn)差相對(duì)差值

4 結(jié)論

本文采用魯棒非線性規(guī)劃研究了不確定需求在橢球集合下的CNDP問題。通過靈敏度分析方法，將模型RC轉(zhuǎn)換成一系列MPCC并采用松弛算法求解。數(shù)值算例表明本文提出的魯棒模型更加靈活。

[1]Yin Y,Lawphongpanich S.A robust approach to continuous network design problems with demand uncertainty[A].Proceedings of 17th International Symposium of Transportation and Traffic Theory[C].2007.

[2]Yin Y,Lawphongpanich S,Lou Y.Estimating investment requirement for maintaining and improving highway systems[J].Transportation Research A,2008,16(2):199-211.

[3]Yin Y.Robust optimal signal timing[J].Transportation Research Part B,2008,42(10):911-924.

[4]Lou Y,Yin Y,Lawphongpainch S.Robust congesting pricing under boundedly rational user equilibrium[J].Transportation Research Part B,2010,44(1):15-28.

[5]Houska B,Diehl M.Nonlinear robust optimization via sequential convex bilevel programming[J].Mathematical Programming,2013,142(1-2):539-577.

[6]Ban X,Liu H X,Ferris M,Ran B.A general MPCC model and its solution algorithm for continuous network design problem[J].Mathematical and Computer Modeling,2006,43(5-6):493-505.

[7]Hearn D W,Ramana M V.Solving congestion toll pricing models[A].Centre for Research on Transportation[C].1998.

Continuous Traffic Network Design Model Based on Robust Nonlinear Programming

Sun Hua1,Zhao Fangxia2
(1.CASC Haiying Mechanical&Electrical Technology Academy Co.,Ltd.,Beijing 100070;2.Beijing Jiaotong University,Beijing 100044,China)

In this paper,based on the robust nonlinear optimization theory,we proposed the robust nonlinear model for the continuous network design problem,then through sensitivity analysis,converted the robust counterpart model into a series of mathematical programming problem with complementary constraints and solved it using the relaxation algorithm.At the end,through a numerical example,we demonstrated the validity of the model proposed.

robust nonlinear optimization;continuous traffic network;sensitivity analysis;mathematical programming problem with complementary constraints

F502

A

1005-152X(2017)07-0109-05

10.3969/j.issn.1005-152X.2017.07.023

2017-06-09

孫華（1980-），男，湖北武漢人，博士，航天海鷹機(jī)電技術(shù)研究院有限公司中級(jí)工程師，研究方向：交通網(wǎng)絡(luò)設(shè)計(jì)、魯棒優(yōu)化、智能交通、智慧城市；趙方霞（1985-），女，山東萊蕪人，博士，研究方向：城市規(guī)劃。