發(fā)生吸引量不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型

陸化普，蔚欣欣，卞長志

（1.清華大學(xué)交通研究所，北京100084；2.中國城市規(guī)劃設(shè)計(jì)研究院,北京100044）

發(fā)生吸引量不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型

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

（1.清華大學(xué)交通研究所，北京100084；2.中國城市規(guī)劃設(shè)計(jì)研究院,北京100044）

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

離散交通網(wǎng)絡(luò)設(shè)計(jì)；發(fā)生吸引量不確定；雙層規(guī)劃；遺傳算法

0 引言

在交通網(wǎng)絡(luò)設(shè)計(jì)問題中，往往是由政府部門在給定的約束條件下，確定規(guī)劃方案，最優(yōu)化交通系統(tǒng)性能，但是它不能控制出行者的選擇行為；而出行者隨著網(wǎng)絡(luò)特性的改變調(diào)整決策，最小化出行費(fèi)用。這是一個(gè)典型的領(lǐng)導(dǎo)者-追隨者對策問題，通常采用下面的雙層規(guī)劃模型進(jìn)行描述[1,2]。

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

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

但是以上的傳統(tǒng)的固性需求交通網(wǎng)絡(luò)設(shè)計(jì)，都沒有考慮決策中存在的不確定性。交通需求不確定時(shí)，不同需求水平下的網(wǎng)絡(luò)設(shè)計(jì)方案差異很大，決策者將面臨較大的風(fēng)險(xiǎn)，為了降低交通網(wǎng)絡(luò)設(shè)計(jì)方案對于不確定性的敏感性，需要利用不確定優(yōu)化理論。

本文假定OD需求是服從一定概率分布的隨機(jī)變量，進(jìn)一步認(rèn)為交通發(fā)生吸引量是不確定的，采用隨機(jī)規(guī)劃方法和交通分配方法描述交通發(fā)生吸引量不確定情況下的交通網(wǎng)絡(luò)設(shè)計(jì)決策，進(jìn)而構(gòu)建隨機(jī)雙層規(guī)劃模型，并給求解的方法。本文還將用算例表明這種考慮了發(fā)生吸引量不確定的交通規(guī)劃模型是有實(shí)際應(yīng)用前景的。

1 隨機(jī)規(guī)劃理論

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

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

在期望約束下，使目標(biāo)函數(shù)的期望值達(dá)到最優(yōu)的數(shù)學(xué)規(guī)劃，稱為期望值模型。期望值模型是隨機(jī)數(shù)學(xué)規(guī)劃中最常見的形式之一，典型形式如下：

補(bǔ)償隨機(jī)規(guī)劃（Stochastic Programming with Recourse）是一類典型的期望值模型，由運(yùn)籌學(xué)大師Dantzig（1955）最先進(jìn)行研究，該類模型的主要思路是在觀察到隨機(jī)變量實(shí)現(xiàn)之前便作決策，該決策可能產(chǎn)生對原約束條件的偏離，待隨機(jī)變量實(shí)現(xiàn)之后，采取應(yīng)急策略以對原約束條件的偏離今年新補(bǔ)償[4]。帶補(bǔ)償?shù)膬呻A段隨機(jī)規(guī)劃的典型形式如下：

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

其中q(y)是一個(gè)費(fèi)用函數(shù)，Wj(y)是給定決策變量x和隨機(jī)變量ζ的實(shí)現(xiàn)之后關(guān)于應(yīng)急策略y的一個(gè)約束函數(shù)。本文采用這種方法為基礎(chǔ)。

2 網(wǎng)絡(luò)隨機(jī)規(guī)劃模型

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

3 基于發(fā)生吸引量不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型的建立

3.1 符號定義

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

A：交通網(wǎng)絡(luò)的路段集合；

Or：交通發(fā)生點(diǎn)r的發(fā)生交通量；

Ds：交通吸引點(diǎn)s的吸引交通量；

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

xa：路段a的交通流量；

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

ya：路段a對應(yīng)的決策變量，ya∈{0,1}，其中ya=1表示路段采取新建或擴(kuò)建策略，ya=0表示維持現(xiàn)狀；

Ca：路段a的通行能力；

La：路段a的長度；

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

B：新建或擴(kuò)建所有路段的預(yù)算；

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

ω：不確定交通需求的任一實(shí)現(xiàn)；

pω：不確定交通需求情景ω的實(shí)現(xiàn)概率；

ρ：規(guī)劃決策者對于網(wǎng)絡(luò)出行時(shí)間均值和方差的權(quán)重；

ζ:交通分布/交通分配組合模型參數(shù)。

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

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

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

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

3.3 雙層規(guī)劃模型建立

假定發(fā)生吸引交通量是滿足給定分布的隨機(jī)變量，其中情景ω對應(yīng)的起點(diǎn)的發(fā)生交通量為，終點(diǎn)S的吸引交通量為，該情景的發(fā)生概率為pω。

發(fā)生吸引量不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型由上層規(guī)劃（8）和下層規(guī)劃（8）共同組成，上下層規(guī)劃通過網(wǎng)絡(luò)決策變量y和路段交通量x相互聯(lián)系。上層規(guī)劃模型（8）是在資金預(yù)算約束下，政府決策者和規(guī)劃人員選擇新建和改建路段，最小化隨機(jī)發(fā)生吸引需求在所有情景實(shí)現(xiàn)條件下的系統(tǒng)總出行時(shí)間均值和標(biāo)準(zhǔn)差。下層規(guī)劃模型（9）是在上層規(guī)劃模型確定的網(wǎng)絡(luò)改進(jìn)決策條件下，每種發(fā)生吸引量情景對應(yīng)的交通分布/交通分配組合模型。

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

路段a的出行時(shí)間使用BPR函數(shù)描述。

均值和標(biāo)準(zhǔn)差之間的權(quán)衡使用權(quán)重系數(shù)ρ表示，ρ∈[0,1]，反應(yīng)政府決策者和規(guī)劃人員對不確定性的平均性能和偏離平均性能離散程度的偏好；ρ取值越大，規(guī)劃決策者對不確定性導(dǎo)致的風(fēng)險(xiǎn)厭惡越強(qiáng)。

4 模型求解算法

4.1 算法流程

采用基于模擬的遺傳算法[15]求解發(fā)生吸引量不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型，算法流程如圖1，具體步驟如下：

(1)初始化

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

②確定發(fā)生吸引量抽樣規(guī)模，生成初始種群。在初始種群個(gè)體生成時(shí)，執(zhí)行預(yù)算約束判斷，直到獲得足夠數(shù)量的初始可行解。

(2)對每一代種群中的每個(gè)個(gè)體進(jìn)行處理

①根據(jù)染色體編碼方案，更新交通網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)；

②發(fā)生吸引交通量隨機(jī)抽樣，對每個(gè)發(fā)生吸引交通量實(shí)現(xiàn)進(jìn)行交通分布/交通分配組合模型計(jì)算；

③根據(jù)所有發(fā)生吸引量情景下的路段流量和時(shí)間，計(jì)算上層目標(biāo)函數(shù)。

(3)使用GA更新種群

①根據(jù)上層目標(biāo)函數(shù)計(jì)算個(gè)體適應(yīng)度；

②根據(jù)適應(yīng)度進(jìn)行個(gè)體選擇；

③執(zhí)行交叉和變異操作；

④對產(chǎn)生的中間種群個(gè)體執(zhí)行預(yù)算約束判斷；

⑤形成新一代種群。

(4)生成最優(yōu)解

在第（2）步執(zhí)行發(fā)生吸引交通量的隨機(jī)模擬過程時(shí)，為了保證區(qū)域發(fā)生和吸引交通量的平衡，需用利用發(fā)生交通量對吸引交通量進(jìn)行平衡。即執(zhí)行如下步驟：

4.2 下層模型求解算法

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

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

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

下面給出整個(gè)算法的具體步驟：

(4)確定步長。

(5)更新流量。

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

表1 Nguyen Dupuis網(wǎng)絡(luò)基本屬性

5 案例研究

5.1 網(wǎng)絡(luò)結(jié)構(gòu)

本論文研究采用Nguyen和Dupuis（1984）的測試網(wǎng)絡(luò)作為案例，該網(wǎng)絡(luò)擁有13個(gè)節(jié)點(diǎn)，19條路段，4個(gè)OD對。網(wǎng)絡(luò)基本結(jié)構(gòu)如圖2，其中紅色節(jié)點(diǎn)表示交通需求發(fā)生點(diǎn)，藍(lán)色節(jié)點(diǎn)表示交通需求吸引點(diǎn)，實(shí)線表示現(xiàn)狀路段，虛線表示待新建路段，表1是網(wǎng)絡(luò)的基本屬性信息，包括自由流時(shí)間、路段現(xiàn)狀通行能力、規(guī)劃通行能力、建設(shè)成本等。表2是OD需求信息，包括確定性需求和截尾正態(tài)分布交通需求兩種情況。

表2 OD交通需求基本情況

表3 情景基本參數(shù)

表4 計(jì)算結(jié)果

5.2 計(jì)算結(jié)果

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

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

（1）其它參數(shù)相同時(shí)，發(fā)生吸引量不確定程度不同，交通網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)方案不同。

（2）比較情景I和情景V的計(jì)算結(jié)果可以發(fā)現(xiàn)，在發(fā)生吸引總量相同的條件下，下層模型（如交通分布/分配組合模型或是用戶均衡模型）的不同將導(dǎo)致網(wǎng)絡(luò)設(shè)計(jì)方案不同。

（3）情景II～I(xiàn)V的對比可以看到，發(fā)生吸引量隨機(jī)程度相同，網(wǎng)絡(luò)規(guī)劃方案由上層決策者的風(fēng)險(xiǎn)偏好決定。

6 結(jié)論

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

[1]騰春賢,李智慧.二層規(guī)劃的理論與應(yīng)用[M].北京:科學(xué)出版社,2002.

[2]高自友,宋一凡,四兵鋒.城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計(jì)理論與方法[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]周溪召.混合交通運(yùn)量分布與均衡配流組合模型研究[J].系統(tǒng)工程學(xué)報(bào)，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.

（責(zé)任編輯/亦民）

U491.1

A

1002－6487（2011）06－0008-05

教育部博士點(diǎn)基金資助項(xiàng)目（20070003065）；國家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目（863計(jì)劃）（2007AA11Z202；2007AA11Z233）

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