基于魯棒非線性規劃的連續交通網絡設計模型

孫 華，趙方霞

（1.航天海鷹機電技術研究院有限公司，北京 100070；2.北京交通大學，北京 100044）

基于魯棒非線性規劃的連續交通網絡設計模型

孫 華1，趙方霞2

（1.航天海鷹機電技術研究院有限公司，北京 100070；2.北京交通大學，北京 100044）

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

魯棒非線性優化；連續交通網絡；靈敏度分析；帶互補約束的數學規劃問題

1 引言

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

2 RC模型

2.1 Yin和Lawphongpanich[1]的RC模型

為討論方便，首先定義一些符號：

N：網絡上節點集合；

A：路段集合，a∈A：

W：OD對集合，w∈W；

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

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

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

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

Q：不確定需求集合；

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

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

B：總預算。

基于上面的符號，CNDP的RC模型能夠寫成：

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

2.2 CNDP的魯棒非線性對應模型

首先將上面的RC模型轉化如下：

μ1,μ2,μ3,μ4,μ5為式（12）-式（15）和式（17）對應的拉格朗日乘子。

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

2.3 靈敏度分析

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

π是非負路徑流量相關的拉格朗日乘子。當僅僅考慮非退化的極點，式（46）-式（49）就變成：

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

3 求解算法與數值算例

3.1 求解算法

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

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

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

Step 3.2設置輔助參數α＞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的精確最優解，否則，第3步最后得到的解作為模型的近似解。

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

3.2 數值算例

為驗證上面提出的基于魯棒非線性規劃的連續網絡設計模型，采用Hearn和Ramana網絡[7]進行數值實驗。這里路段走行時間函數采用如下形式的BPR函數：

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

圖1 Hearn和Ramana的網絡

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

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

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

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

表2給出了模型RC和模型RC1的目標函數以及目標函數的相對差值。從表2可以看出，RC1模型的目標函數更小，這說明RC1模型更加靈活。

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

從圖3可以看出，模型RC的魯棒解yRC和模型RC1的魯棒解yRC1的系統走行時間期望都比代表解yN大，但是模型RC魯棒解yRC和模型RC1魯棒解yRC1的系統走行時間標準差都比代表解yN小。這說明模型RC的魯棒解yRC和RC1模型的魯棒解yRC1比代表解yN更加穩定。但是，模型RC的魯棒解yRC比模型RC1的魯棒解yRC1產生更大的期望和標準差，這說明模型RC的魯棒解yRC更加保守。

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

表2 不同預算B下，模型RC和模型RC1的目標函數及相對差異

圖3 代表解、RC模型和RC1模型產生的目標函數間的期望和標準差相對差值

4 結論

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

[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-），男，湖北武漢人，博士，航天海鷹機電技術研究院有限公司中級工程師，研究方向：交通網絡設計、魯棒優化、智能交通、智慧城市；趙方霞（1985-），女，山東萊蕪人，博士，研究方向：城市規劃。