發生吸引量不確定的離散交通網絡設計模型

陸化普，蔚欣欣，卞長志

（1.清華大學交通研究所，北京100084；2.中國城市規劃設計研究院,北京100044）

發生吸引量不確定的離散交通網絡設計模型

陸化普1，蔚欣欣1，卞長志2

（1.清華大學交通研究所，北京100084；2.中國城市規劃設計研究院,北京100044）

交通網絡設計是交通規劃的核心內容之一，而網絡設計由依靠交通需求預測技術。為了改進傳統的以確定性需求為基礎的網絡設計，文章以交通需求不確定性為基本前提，認為交通發生吸引量也是不確定的，并使用隨機雙層規劃、均值方差和交通分配理論建立了發生吸引量不確定離散交通網絡設計的基本模型。為了求解發生吸引量不確定的離散網絡設計問題，開發了基于Monte Carlo模擬、遺傳算法和交通分配算法的方法。Nguyen Dupuis網絡的計算結果表明，需求不確定程度和政府決策者風險偏好等對規劃方案具有重要影響。

離散交通網絡設計；發生吸引量不確定；雙層規劃；遺傳算法

0 引言

在交通網絡設計問題中，往往是由政府部門在給定的約束條件下，確定規劃方案，最優化交通系統性能，但是它不能控制出行者的選擇行為；而出行者隨著網絡特性的改變調整決策，最小化出行費用。這是一個典型的領導者-追隨者對策問題，通常采用下面的雙層規劃模型進行描述[1,2]。

其中y=y(x)是x的隱函數，由下面的問題決定：

上層模型（1）是規劃者改善交通網絡系統性能的最優決策問題。下層模型（2）是給定交通網絡規劃方案的出行者平衡問題。假設對于任意給定的上層決策變量x，都可以從下層問題求得唯一的平衡交通流量y=y(x)，稱y(x)為反應或響應函數，反映網絡用戶的路徑選擇行為。交通網絡設計模型就是在滿足投資預算等約束條件下，考慮網絡用戶路徑選擇行為，尋找最佳網絡設計決策方案x使系統目標函數F(x,y)最優。

但是以上的傳統的固性需求交通網絡設計，都沒有考慮決策中存在的不確定性。交通需求不確定時，不同需求水平下的網絡設計方案差異很大，決策者將面臨較大的風險，為了降低交通網絡設計方案對于不確定性的敏感性，需要利用不確定優化理論。

本文假定OD需求是服從一定概率分布的隨機變量，進一步認為交通發生吸引量是不確定的，采用隨機規劃方法和交通分配方法描述交通發生吸引量不確定情況下的交通網絡設計決策，進而構建隨機雙層規劃模型，并給求解的方法。本文還將用算例表明這種考慮了發生吸引量不確定的交通規劃模型是有實際應用前景的。

1 隨機規劃理論

經典數學規劃理論與方法包括線性規劃、非線性規劃、多目標規劃、動態規劃等。然而，在管理科學、工程技術、軍事決策等諸多領域都存在很多人為的或客觀的不確定性因素，經典規劃理論處理這類不確定的方法是靈敏度分析，即假定輸入數據存在微小擾動，考察模型輸出可能的變化。但是對于目標函數和約束條件相對復雜的問題，靈敏度分析方法很難取得前瞻性的結論。為了能夠對不確定進行前攝處理，必須在建模階段引入變量的不確定性，其中就包括本文使用的方法-隨機規劃（stochastic programming）方法。

當確定性問題中出現了隨機變量ζ，則問題成為隨機規劃問題。在隨機規劃中，參數的不確定性使用概率分布函數來描述，其目標函數和約束條件需要根據概率意義理解[3,4]。基本的隨機規劃模型如下：

在期望約束下，使目標函數的期望值達到最優的數學規劃，稱為期望值模型。期望值模型是隨機數學規劃中最常見的形式之一，典型形式如下：

補償隨機規劃（Stochastic Programming with Recourse）是一類典型的期望值模型，由運籌學大師Dantzig（1955）最先進行研究，該類模型的主要思路是在觀察到隨機變量實現之前便作決策，該決策可能產生對原約束條件的偏離，待隨機變量實現之后，采取應急策略以對原約束條件的偏離今年新補償[4]。帶補償的兩階段隨機規劃的典型形式如下：

其中Q(x,ζ)是由于某些約束被違反而產生的一個額外補償費用，定義如下：

其中q(y)是一個費用函數，Wj(y)是給定決策變量x和隨機變量ζ的實現之后關于應急策略y的一個約束函數。本文采用這種方法為基礎。

2 網絡隨機規劃模型

基于隨機規劃理論的不確定交通網絡設計模型，假定交通需求是服從已知概率分布的隨機變量，以隨機雙層規劃模型求解最優網絡規劃方案。Liu等（2007）建立需求不確定的連續交通網絡設計雙層模型，上層模型是期望總出行時間和投資成本的加權和，下層模型是不同需求情景實現下的UE模型，該文使用基于模擬的遺傳算法進行了算例研究[5]。Sun和Turnquist（2007）建立了需求不確定的交通網絡設計模型，該模型假定需求是分布已知的離散隨機變量，對于需求的每個實現，交通流滿足Probit隨機用戶均衡，上層目標是預算約束條件下極大化系統容量；考慮到雙層規劃求解的難度，設計了基于模擬退火的算法，并對美國集裝箱港口網絡進行了實例計算[6]。Ukkusui等（2007）研究需求不確定的連續交通網絡設計問題。假定OD矩陣元素是概率分布已知的隨機變量，以總出行時間期望值和標準差的加權平均作為優化目標。并以遺傳算法進行求解，不同規模網絡和預算水平的計算表明模型和算法的有效性。案例網絡的計算結果還顯示，魯棒解與固定需求的網絡設計解顯著不同，忽略不確定性將過低估計網絡范圍的影響[7]。Partriksson（2008）以隨機雙層規劃模型嚴格考慮需求的不確定性，其中上層規劃極小化目標函數的期望值，下層是變分不等式表示的均衡條件。將魯棒性定義為全局最優解相對于需求概率分布擾動的穩定性，并從數學理論上證明了特定隨機雙層規劃模型具有魯棒性[8]。

3 基于發生吸引量不確定的離散交通網絡設計模型的建立

3.1 符號定義

N：交通網絡的節點集合；

A：交通網絡的路段集合；

Or：交通發生點r的發生交通量；

Ds：交通吸引點s的吸引交通量；

Prs：OD對rs之間的路徑集合；

xa：路段a的交通流量；

ta(x)：路段a的行程時間阻抗函數；

ya：路段a對應的決策變量，ya∈{0,1}，其中ya=1表示路段采取新建或擴建策略，ya=0表示維持現狀；

Ca：路段a的通行能力；

La：路段a的長度；

Ga(ya)：新建或擴建路段a的成本；

B：新建或擴建所有路段的預算；

Ω：不確定交通需求的所有可能情景集；

ω：不確定交通需求的任一實現；

pω：不確定交通需求情景ω的實現概率；

ρ：規劃決策者對于網絡出行時間均值和方差的權重；

ζ:交通分布/交通分配組合模型參數。

3.2 交通分布/交通分配組合模型

交通分布/分配組合模型的目的是克服傳統四階段預測模型存在的不一致。研究始于20世紀60～70年代，Tomlin（1971）首先進行了嘗試[9]。Florian等（1975）和Evans（1976）提出了交通分布與交通分配的組合模型，其中交通分布使用指數阻抗函數的引力模型刻畫，交通分配服從UE均衡，并應用凸規劃理論完整地論述了等價于組合問題的最優化模型的存在性和解的唯一性[10,11]。針對FW算法求解組合模型存在的問題，Evans（1976）給出了二階段求解算法（Evans算法）。Huang和Lam（1992）對該算法進行了進一步優化改進[12]。周溪召（2000）基于Logit模型建立了混合交通分布/交通分配組合模型[13]。Xu等（2008）對交通分布/交通分配組合模型提出了改進的基于起點的求解算法[14]。

本文采用的交通分布/交通分配組合模型可以用規劃模型（7）表示。

其中（7）的第一式是目標函數，由交通分配目標函數和交通分布熵兩項共同組成；第二式是路徑流量與OD流量之間的守恒關系；第三式是發生交通量約束條件；第四式是吸引交通量約束條件。

3.3 雙層規劃模型建立

假定發生吸引交通量是滿足給定分布的隨機變量，其中情景ω對應的起點的發生交通量為，終點S的吸引交通量為，該情景的發生概率為pω。

發生吸引量不確定的離散交通網絡設計模型由上層規劃（8）和下層規劃（8）共同組成，上下層規劃通過網絡決策變量y和路段交通量x相互聯系。上層規劃模型（8）是在資金預算約束下，政府決策者和規劃人員選擇新建和改建路段，最小化隨機發生吸引需求在所有情景實現條件下的系統總出行時間均值和標準差。下層規劃模型（9）是在上層規劃模型確定的網絡改進決策條件下，每種發生吸引量情景對應的交通分布/交通分配組合模型。

其中x=x(y)是y的隱函數，由下層規劃問題（9）決定：

路段a的出行時間使用BPR函數描述。

均值和標準差之間的權衡使用權重系數ρ表示，ρ∈[0,1]，反應政府決策者和規劃人員對不確定性的平均性能和偏離平均性能離散程度的偏好；ρ取值越大，規劃決策者對不確定性導致的風險厭惡越強。

4 模型求解算法

4.1 算法流程

采用基于模擬的遺傳算法[15]求解發生吸引量不確定的離散交通網絡設計模型，算法流程如圖1，具體步驟如下：

(1)初始化

①定義GA參數，主要包括：染色體編碼方案，種群規模，種群進化最大代數，代溝，交叉概率，變異概率。

②確定發生吸引量抽樣規模，生成初始種群。在初始種群個體生成時，執行預算約束判斷，直到獲得足夠數量的初始可行解。

(2)對每一代種群中的每個個體進行處理

①根據染色體編碼方案，更新交通網絡結構和參數；

②發生吸引交通量隨機抽樣，對每個發生吸引交通量實現進行交通分布/交通分配組合模型計算；

③根據所有發生吸引量情景下的路段流量和時間，計算上層目標函數。

(3)使用GA更新種群

①根據上層目標函數計算個體適應度；

②根據適應度進行個體選擇；

③執行交叉和變異操作；

④對產生的中間種群個體執行預算約束判斷；

⑤形成新一代種群。

(4)生成最優解

在第（2）步執行發生吸引交通量的隨機模擬過程時，為了保證區域發生和吸引交通量的平衡，需用利用發生交通量對吸引交通量進行平衡。即執行如下步驟：

4.2 下層模型求解算法

本文使用凸組合法求解下層模型。設在第n步迭代上，OD流量為，路徑流量為，通過求解下面的線性規劃問題，我們可以得到目標函數在處的下降方向。

將（10）中的第3、第4式代入第1式中，可以重寫問題（10）為

問題式（11）是運籌學中有名的Hitchcock運輸問題，有成熟的計算方法。決定了后，將其安排到最短路徑上得到路段流量是下降方向。

下面給出整個算法的具體步驟：

(4)確定步長。

(5)更新流量。

解；否則令n=n+1，返回第（1）步。

表1 Nguyen Dupuis網絡基本屬性

5 案例研究

5.1 網絡結構

本論文研究采用Nguyen和Dupuis（1984）的測試網絡作為案例，該網絡擁有13個節點，19條路段，4個OD對。網絡基本結構如圖2，其中紅色節點表示交通需求發生點，藍色節點表示交通需求吸引點，實線表示現狀路段，虛線表示待新建路段，表1是網絡的基本屬性信息，包括自由流時間、路段現狀通行能力、規劃通行能力、建設成本等。表2是OD需求信息，包括確定性需求和截尾正態分布交通需求兩種情況。

表2 OD交通需求基本情況

表3 情景基本參數

表4 計算結果

5.2 計算結果

假定發生吸引量服從截尾正態分布，情景分析發生吸引則{yn-xn,vn-qn}就量不確定程度和決策者風險偏好對網絡規劃方案的影響，其中情景V為并不考慮交通分配與分布的情景。遺傳算法基本參數為：種群規模40，進化代數100，染色體長度為25，代溝0.9，交叉概率0.8，變異概率0.01。

圖3～圖6是遺傳算法求解的種群進化過程，表4是計算結果，可以得到如下結論：

（1）其它參數相同時，發生吸引量不確定程度不同，交通網絡規劃設計方案不同。

（2）比較情景I和情景V的計算結果可以發現，在發生吸引總量相同的條件下，下層模型（如交通分布/分配組合模型或是用戶均衡模型）的不同將導致網絡設計方案不同。

（3）情景II～IV的對比可以看到，發生吸引量隨機程度相同，網絡規劃方案由上層決策者的風險偏好決定。

6 結論

本文假定發生交通量和吸引交通量是概率分布給定的隨機變量，以交通分布/交通分配組合模型描述出行者的終點選擇和路徑選擇行為，并將其作為下層規劃嵌入發生吸引交通量不確定的離散交通網絡設計模型。而利用Monte Carlo模擬和遺傳算法則有效解決了隨機雙層規劃的求解。Nguyen-Dupuis網絡的計算結果表明，需求不確定程度和政府決策者風險偏好等對規劃方案具有重要影響。

[1]騰春賢,李智慧.二層規劃的理論與應用[M].北京:科學出版社,2002.

[2]高自友,宋一凡,四兵鋒.城市交通連續平衡網絡設計理論與方法[M].北京:中國鐵道出版社,2000.

[3]Birge J R,Louveaux F.Introduction to Stochastic Programming[M].New York:Springer,1997.

[4]Danztig G.Linear Programming underUncertainty[J].Management Science,1995,1(3).

[5]Liu Haixu,Hu Ji,Pu Yun.Continuous Network Design Problem Considering Stochastic demand[J].In 1st International Conference on Transportation Engineering,Chengdu,2007.

[6]SunYao,TurnquistMA.Investmentin Transportation Network Capacity under Uncertainty:simulated Annealing Approach[J].Transportation Research Record,2007,2039.

[7]Ukkusui S V,Mathew T V,Waller S T.Robust Transportation Network Design under Demand Uncertainty[J].Computer-Aided Civil and Infrastructure Engineering,2007,22.

[8]Partriksson M.Robust Bi-Level Optimization Models in Transportation Science[J].Philosophical Transactions of the Royal Society A,2008,366.

[9]Tomlin J A.A Mathematical Programming Model for the Combined Distribution-assignment of traffic[J].Transportation Science,1971,5(2).

[10]Florian M,Nguyen S,Ferland J.On the Combined Distribution assignment of traffic[J].Transportation Science,1975,9(1).

[11]Evans,S P.Derivation and Analysis of Some Models for Combining Trip Distribution and Assignment[J].Transportation research, 1976,10(1).

[12]Huang H J,Lam W H K.Modified Evans’Algorithms for Solving the Combined Trip Distribution and Assignment Problem[J]. Transportation Research B,1992,26(4).

[13]周溪召.混合交通運量分布與均衡配流組合模型研究[J].系統工程學報，2000,15(2).

[14]Xu Meng,Anthony Chen,Gao Ziyou.An Improved Origin-Based Algorithm for Solving the Combined Distribution and Assignment Problem[J].European Journal of Operational Research, 2008,188.

[15]Holland J H.Adapation in Natural and Artificial Systems[J].Ann Arbor:The University of Michgan Press,1975.

（責任編輯/亦民）

U491.1

A

1002－6487（2011）06－0008-05

教育部博士點基金資助項目（20070003065）；國家高技術研究發展計劃資助項目（863計劃）（2007AA11Z202；2007AA11Z233）

陸化普(1957-)，男，遼寧鐵嶺人，教授，博士生導師，研究方向：交通需求預測、交通管理、交通控制理論與方法。