供給與需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型

陸化普 李 悅 蔚欣欣

(1清華大學(xué)交通研究所，北京 100084)

(2交通運(yùn)輸部規(guī)劃研究院，北京 100028)

供給與需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型

陸化普1李 悅1蔚欣欣2

(1清華大學(xué)交通研究所，北京 100084)

(2交通運(yùn)輸部規(guī)劃研究院，北京 100028)

考慮到交通規(guī)劃中供給需求及決策準(zhǔn)則的不確定性，提出了一種基于不確定理論的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型.首先，假設(shè)供給和需求為隨機(jī)變量，使用半標(biāo)準(zhǔn)差和風(fēng)險(xiǎn)價(jià)值來度量不確定性，建立了考慮決策者風(fēng)險(xiǎn)態(tài)度的多目標(biāo)雙層優(yōu)化模型.隨后，使用基于帕累托概念的SPEA2算法對(duì)網(wǎng)絡(luò)優(yōu)化模型進(jìn)行求解.以研究中常用的Nguyen-Dupuis網(wǎng)絡(luò)作為算例進(jìn)行計(jì)算，結(jié)果表明:引進(jìn)風(fēng)險(xiǎn)價(jià)值可以有效度量交通規(guī)劃中決策者的風(fēng)險(xiǎn)態(tài)度;多目標(biāo)規(guī)劃中不同目標(biāo)之間存在替代關(guān)系;增加建設(shè)資金可以有效提高網(wǎng)絡(luò)性能，但是當(dāng)投入資金增加到一定額度以后，改善效果并不明顯.

離散交通網(wǎng)絡(luò)設(shè)計(jì);供給與需求不確定;風(fēng)險(xiǎn)態(tài)度;風(fēng)險(xiǎn)價(jià)值;雙層模型

傳統(tǒng)的雙層模型交通網(wǎng)絡(luò)優(yōu)化方法缺乏對(duì)決策中存在的不確定性的考慮，其上層模型的優(yōu)化目標(biāo)往往僅選擇為系統(tǒng)總走行時(shí)間最小，而沒有考慮決策者的風(fēng)險(xiǎn)態(tài)度對(duì)于網(wǎng)絡(luò)優(yōu)化方案的影響，這與實(shí)際情況不符.因此，針對(duì)上層模型進(jìn)行目標(biāo)函數(shù)改進(jìn)，使其反映決策者的決策行為，是網(wǎng)絡(luò)優(yōu)化問題的研究重點(diǎn)之一.

Yang等［1］對(duì)于網(wǎng)絡(luò)優(yōu)化問題的目標(biāo)函數(shù)進(jìn)行了總結(jié)，發(fā)現(xiàn)在雙層規(guī)劃模型中，通常將目標(biāo)函數(shù)設(shè)定為系統(tǒng)總走行時(shí)間最小.Williams等［2］以出行者剩余最大化作為網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)，建立了網(wǎng)絡(luò)優(yōu)化模型，并且分析了交通網(wǎng)絡(luò)性能改善措施對(duì)于出行者消費(fèi)剩余的影響.對(duì)于其他單目標(biāo)優(yōu)化問題，在上層模型中，決策者可以選用其他優(yōu)化目標(biāo)，如交通網(wǎng)絡(luò)可靠性最大化［3］、網(wǎng)路使用時(shí)環(huán)境污染最小化［4］、交通網(wǎng)絡(luò)公平性最大化［5］等.文獻(xiàn)［6-7］建立了一種同時(shí)考慮系統(tǒng)總走行時(shí)間、網(wǎng)絡(luò)建設(shè)成本等多個(gè)目標(biāo)的交通網(wǎng)絡(luò)優(yōu)化模型并進(jìn)行了求解.文獻(xiàn)［8-10］研究了基于需求不確定的連續(xù)交通網(wǎng)絡(luò)設(shè)計(jì)問題，以總走行時(shí)間的期望和標(biāo)準(zhǔn)差的算數(shù)加權(quán)平均值最小化作為上層模型的優(yōu)化目標(biāo).

為了能夠更好地描述現(xiàn)實(shí)問題，本文假定交通需求和交通供給是服從一定概率分布的隨機(jī)變量，基于VaR理論建立了考慮決策者風(fēng)險(xiǎn)態(tài)度的不確定網(wǎng)絡(luò)優(yōu)化模型.隨后，給出了求解該模型的算法，并使用實(shí)驗(yàn)網(wǎng)絡(luò)對(duì)其進(jìn)行了驗(yàn)證.

1 基于風(fēng)險(xiǎn)價(jià)值的不確定交通網(wǎng)絡(luò)優(yōu)化模型

1.1 風(fēng)險(xiǎn)價(jià)值理論

統(tǒng)計(jì)學(xué)和金融學(xué)中度量風(fēng)險(xiǎn)的經(jīng)典指標(biāo)有:①半方差和半標(biāo)準(zhǔn)差的風(fēng)險(xiǎn)度量;②均值-絕對(duì)偏差風(fēng)險(xiǎn)度量;③ 絕對(duì)偏差風(fēng)險(xiǎn)度量;④ 極大化極小策略的風(fēng)險(xiǎn)度量［11］.這些傳統(tǒng)的基于偏離度的風(fēng)險(xiǎn)度量往往無法概括分布的特征以及小概率的事件.為了克服這一缺點(diǎn)，在風(fēng)險(xiǎn)管理的實(shí)踐中，研究者們提出了基于風(fēng)險(xiǎn)價(jià)值理論的風(fēng)險(xiǎn)度量方法［12］.所謂風(fēng)險(xiǎn)價(jià)值就是在給定的置信水平下，發(fā)生不超過某一目標(biāo)區(qū)域范圍的預(yù)期最大虧損額度，即

式中，Δp表示收益;－Δp表示虧損;V表示給定置信水平τ下的風(fēng)險(xiǎn)價(jià)值.由此可知，風(fēng)險(xiǎn)價(jià)值V描述了一種分布特征，該分布具有單調(diào)性、固定轉(zhuǎn)換性、同質(zhì)性和次加性.

給定網(wǎng)絡(luò)設(shè)計(jì)中某個(gè)路段走行時(shí)間的風(fēng)險(xiǎn)價(jià)值為

式中，Xa為路段a的路段交通流量，其均值為xa，標(biāo)準(zhǔn)差為σxa;λ為給定置信水平下的分位數(shù);Ta為路段a的走行時(shí)間函數(shù);ω∈Ω為任意一隨機(jī)情景，對(duì)應(yīng)的概率為pω.

對(duì)于整體網(wǎng)絡(luò)來說，走行時(shí)間的標(biāo)準(zhǔn)差為

式中，ρij為2條路段走行時(shí)間的相關(guān)系數(shù);Xi為路段i的路段交通流量，其均值為xi，標(biāo)準(zhǔn)差為σxi;Ti為路段i的走行時(shí)間函數(shù).

網(wǎng)絡(luò)的風(fēng)險(xiǎn)價(jià)值可表示為

式中，U為由N條路段組成的網(wǎng)絡(luò).

當(dāng) ρij=0 時(shí)，有

當(dāng) ρij=1 時(shí)，有

現(xiàn)實(shí)中不同路段走行時(shí)間不可能完全正相關(guān)，路徑走行時(shí)間的波動(dòng)性小于路段走行時(shí)間的波動(dòng)性.為了計(jì)算的方便，以下分析中均假設(shè)ρij=0.

1.2 模型設(shè)計(jì)

1.2.1 多目標(biāo)模型Ⅰ

假定路段通行能力和OD需求是服從一定概率分布的隨機(jī)變量，建立基于風(fēng)險(xiǎn)價(jià)值的多目標(biāo)網(wǎng)絡(luò)設(shè)計(jì)模型Ⅰ.該模型為雙層規(guī)劃模型，上層模型為決策者決定新建或者擴(kuò)建的路段集合，共包含2個(gè)目標(biāo)函數(shù):①系統(tǒng)總走行時(shí)間的均值最小;②系統(tǒng)總走行時(shí)間的風(fēng)險(xiǎn)價(jià)值最小.約束條件為建設(shè)資金投入小于預(yù)算資金.上層模型可表示為

式中，Z為上層模型的目標(biāo)函數(shù);ˉCa為新建或者擴(kuò)建路段新增的通行能力;Ua為新建或者擴(kuò)建路段的投資成本函數(shù);ˉA為交通網(wǎng)絡(luò)中新建或者擴(kuò)建路段的集合;ya為決策變量，且ya=1表示新建路段，ya=0表示不建路段;Q為新建或者擴(kuò)建路段的資金預(yù)算.

假設(shè)X=X(yaˉCa)為ya的隱函數(shù)，由下層模型決定.下層模型為基于期望效用理論的均衡模型，可表示為

式中，T為下層模型的目標(biāo)函數(shù);R為交通網(wǎng)絡(luò)中交通發(fā)生點(diǎn)的集合;r為任意一個(gè)交通發(fā)生點(diǎn);S為交通網(wǎng)絡(luò)中交通吸引點(diǎn)的集合;s為任意一個(gè)交通吸引點(diǎn);Prs為OD對(duì)之間的路徑集合;Qrs為OD對(duì)r，s之間的需求量，其均值為qrs，殘差項(xiàng)為 εrs，標(biāo)準(zhǔn)差為為OD對(duì)r，s之間路徑k的流量，其均值為frsk.

假設(shè)路段通行能力是獨(dú)立的隨機(jī)變量，則路徑走行時(shí)間可以表示為

式中，ta0為路段a的自由流走行時(shí)間;Ca0為路段a的原有通行能力;α，β為路段通行時(shí)間函數(shù)的參數(shù).Ca0，yaˉCa分別服從于參數(shù)為 θa0，θa的均勻分布的隨機(jī)變量.

路段建設(shè)投資函數(shù)Ua可表示為

式中，la為新建或者擴(kuò)建路段的長度;γ為單位長度路段單位通行能力新建或者擴(kuò)建的成本.

上下層規(guī)劃由決策變量ya和路段交通量Xa聯(lián)系.

1.2.2 多目標(biāo)模型Ⅱ

假定路段通行能力和OD需求是服從一定概率分布的隨機(jī)變量，建立基于風(fēng)險(xiǎn)價(jià)值的多目標(biāo)網(wǎng)絡(luò)設(shè)計(jì)模型Ⅱ.其上層模型為決策者決定新建或者擴(kuò)建的路段集合，共包含3個(gè)目標(biāo)函數(shù):①系統(tǒng)總走行時(shí)間的均值最小;② 系統(tǒng)總走行時(shí)間的風(fēng)險(xiǎn)價(jià)值最小;③ 網(wǎng)絡(luò)總投資最小.下層模型為基于期望效用理論的均衡模型.模型Ⅱ可表示為

式(11)中的路段走行時(shí)間可用式(9)來表示，路段建設(shè)投資函數(shù)Ua可用式(10)來表示.

2 模型求解算法

為了解決基于VaR理論的多目標(biāo)不確定交通網(wǎng)絡(luò)設(shè)計(jì)模型問題，本文使用了基于蒙特卡洛模擬的遺傳算法，其具體步驟如下.

1)初始化.

①設(shè)計(jì)遺傳算法染色體的編碼方案，確定優(yōu)化問題的適應(yīng)度函數(shù).確定種群規(guī)模O、種群進(jìn)化的最大代數(shù)T以及交叉概率和變異概率.

②根據(jù)預(yù)算約束生成初始種群P(0)，其中個(gè)體數(shù)量為O.同時(shí)設(shè)外部檔案集合Q(0)為空，種群代數(shù)計(jì)數(shù)器t=1.

2)設(shè)種群個(gè)體計(jì)數(shù)器o=1，對(duì)給定的種群P(t)中的個(gè)體進(jìn)行以下操作:

①根據(jù)染色體P(t)o的方案更新網(wǎng)絡(luò)參數(shù)，設(shè)隨機(jī)供給與需求抽樣計(jì)數(shù)器y=1.

②進(jìn)行供給和需求的隨機(jī)抽樣，根據(jù)抽樣得到的參數(shù)進(jìn)行下層模型的交通分配.

③根據(jù)下層模型的分配結(jié)果，計(jì)算上層模型的目標(biāo)函數(shù)值.

④如果y＜Y，則返回步驟②，且y=y+1;否則，計(jì)算P(t)o對(duì)應(yīng)的目標(biāo)函數(shù)的值，進(jìn)入步驟⑤.

⑤ 如果o＜O，則返回步驟①，且o=o+1;否則，t=t+1，進(jìn)入步驟3).

3)如果t＜T，則執(zhí)行改進(jìn)的強(qiáng)度帕累托進(jìn)化算法(SPEA2);否則，進(jìn)入步驟4).

4)形成帕累托最優(yōu)解，終止計(jì)算.

3 算例

3.1 參數(shù)設(shè)置

采用經(jīng)典的Nguyen-Dupuis測試網(wǎng)絡(luò)進(jìn)行算例分析(見圖1).該網(wǎng)絡(luò)共有13個(gè)節(jié)點(diǎn)、19個(gè)路段和4個(gè)OD對(duì).圖中，A，D為交通需求發(fā)生點(diǎn)，B，C為交通需求吸引點(diǎn)，實(shí)線線段為已建成的現(xiàn)狀路段，虛線線段為待建的路段.網(wǎng)絡(luò)路段的基本信息列于表1，包括路段編號(hào)、起終點(diǎn)、自由流走行時(shí)間、現(xiàn)狀和規(guī)劃通行能力以及均勻分布的參數(shù)、新建或者擴(kuò)建的預(yù)算建設(shè)成本.隨機(jī)OD需求列于表2，本算例中假設(shè)隨機(jī)OD服從截尾正態(tài)分布.

圖1 Nguyen-Dupuis網(wǎng)絡(luò)結(jié)構(gòu)

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

表2 OD交通需求的基本情況

3.2 計(jì)算分析

待建與擴(kuò)建路段共25條，使用二進(jìn)制編碼方法，故染色體長度也為25.用1表示新建或者擴(kuò)建的道路，0表示維持原狀的道路，前6位數(shù)字表示新建道路，其余19位數(shù)字表示擴(kuò)建道路，順序依照路段編號(hào)次序.

情景A為多目標(biāo)模型Ⅰ的不確定離散交通網(wǎng)絡(luò)設(shè)計(jì)問題，其中用戶類型為風(fēng)險(xiǎn)中性.遺傳算法基本參數(shù)設(shè)置如下:進(jìn)化終止代數(shù)為1 000，種群規(guī)模為50，代溝為 0.9，變異概率為 0.15，交叉概率為0.75，走行時(shí)間函數(shù)參數(shù) α =0.15，β =4，其他參數(shù)詳見表3.

圖2為情景A的計(jì)算結(jié)果.由圖可知，算法的收斂速度較好.此外，還可以得出:①系統(tǒng)總出行時(shí)間均值和風(fēng)險(xiǎn)價(jià)值具有反向關(guān)系.在預(yù)算約束和需求不確定程度相同的情況下，系統(tǒng)總走行時(shí)間越大，總走行時(shí)間的風(fēng)險(xiǎn)價(jià)值越小;系統(tǒng)總走行時(shí)間越小，總走行時(shí)間的風(fēng)險(xiǎn)價(jià)值越大.②在相同預(yù)算水平下，需求隨機(jī)程度越大，有效前沿的點(diǎn)分布越分散.③ 置信水平越高，風(fēng)險(xiǎn)價(jià)值的數(shù)值越大，對(duì)于風(fēng)險(xiǎn)就更加厭惡.④當(dāng)供給存在不確定性時(shí)，供給隨機(jī)程度越大，相同風(fēng)險(xiǎn)水平下的總走行時(shí)間越大.⑤ 在相同的需求不確定程度下，預(yù)算水平增加，會(huì)造成帕累托有效前沿對(duì)應(yīng)的系統(tǒng)總走行時(shí)間均值和風(fēng)險(xiǎn)價(jià)值下降.

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

圖2 情景A的計(jì)算結(jié)果

圖3 情景B的計(jì)算結(jié)果

情景B為多目標(biāo)模型Ⅱ的不確定離散交通網(wǎng)絡(luò)設(shè)計(jì)問題，其中用戶類型為風(fēng)險(xiǎn)中性.遺傳算法基本參數(shù)設(shè)置為:進(jìn)化終止代數(shù)為1 000，種群規(guī)模為100，代溝為 0.9，變異概率為 0.15，交叉概率為0.75.走行時(shí)間函數(shù)參數(shù) α =0.15，β =4，需求均值為350，變異系數(shù)為0.2，現(xiàn)狀通行能力與規(guī)劃通行能力分布參數(shù)為1，置信水平為90%，供給與需求抽樣規(guī)模為50.圖3表示多目標(biāo)模型Ⅱ種群進(jìn)化到1 000代時(shí)的帕累托有效前沿，其沿3個(gè)坐標(biāo)軸方向的投影如圖4所示.由圖可知，網(wǎng)絡(luò)建設(shè)成本、網(wǎng)絡(luò)系統(tǒng)總出行時(shí)間均值及系統(tǒng)總出行時(shí)間的風(fēng)險(xiǎn)價(jià)值三者之間存在替代關(guān)系.增加建設(shè)資金可以有效地提高網(wǎng)絡(luò)性能，但是當(dāng)投入資金增加到一定額度以后，改善的效果不明顯.當(dāng)建設(shè)資金投入接近0時(shí)，網(wǎng)絡(luò)的性能變得不穩(wěn)定.

圖4 情景B在3個(gè)坐標(biāo)軸方向上的投影

4 結(jié)語

針對(duì)傳統(tǒng)四階段法中對(duì)于現(xiàn)實(shí)條件的不合理假設(shè)，通過假定交通供給和需求是概率分布給定的隨機(jī)變量，基于VaR理論建立了一種考慮決策者風(fēng)險(xiǎn)態(tài)度的不確定多目標(biāo)離散交通網(wǎng)絡(luò)設(shè)計(jì)模型，并給出了基于遺傳算法的求解方法.基于Nguyen-Dupuis網(wǎng)絡(luò)的計(jì)算結(jié)果表明:風(fēng)險(xiǎn)價(jià)值可以有效地度量決策者的風(fēng)險(xiǎn)態(tài)度;網(wǎng)絡(luò)建設(shè)成本、網(wǎng)絡(luò)系統(tǒng)總出行時(shí)間均值、系統(tǒng)總出行時(shí)間的風(fēng)險(xiǎn)價(jià)值三者之間存在替代關(guān)系;增加建設(shè)資金可以有效地提高網(wǎng)絡(luò)性能，但是當(dāng)投入資金增加到一定額度以后，改善的效果不明顯.下一步的研究主要集中在分析參數(shù)的選擇對(duì)于網(wǎng)絡(luò)優(yōu)化結(jié)果的影響上，以便更好地將VaR應(yīng)用于規(guī)劃實(shí)踐.

［1］Yang H，Bell M G H.Models and algorithms for road network design:a review and some new developments［J］.Transport Reviews，1998，18(3):257-278.

［2］Williams H C W L，Lam W M.Transport policy appraisal with equilibrium modelsⅠ:generalized traffic and highway investment benefits［J］.Transportation Research Part B:Methodological，1991，25(5):253-279.

［3］許良，高自友.基于連通可靠性的城市道路交通離散網(wǎng)絡(luò)設(shè)計(jì)問題［J］.燕山大學(xué)學(xué)報(bào)，2007，31(2):159-163.

Xu Ling，Gao Ziyou.Urban road transportation discrete network design based on connectivity reliability［J］.Journal of Yanshan University，2007，31(2):159-163.(in Chinese)

［4］劉娟娟，范炳全，祝炳發(fā).雙層規(guī)劃在城市交通污染控制中的一個(gè)應(yīng)用［J］.管理工程學(xué)報(bào)，2005，19(4):87-90.

Liu Juanjuan，F(xiàn)an Bingquan，Zhu Bingfa.An apply of bi-level programming in the urban transport pollution control［J］.Journal of Industrial Engineering and Engineering Management，2005，19(4):87-90.(in Chinese)

［5］ Meng Q，Yang H.Benefit distribution and equity in road network design［J］.Transportation Research Part B:Methodological，2002，36(1):19-35.

［6］ Friesz T L，Mehta N J，Nam K，et al.The multi-objective equilibrium network design problem revisited:a simulated annealing approach［J］.European Journal of Operational Research，1993，65(1):44-57.

［7］Tzeng G H，Tsaur S H.Application of multiple criteria decision making for network improvement plan model［J］.Journal of Advanced Transportation，1997，31(1):48-74.

［8］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(1):6-18.

［9］ Karoonsoontawong A，Waller S T.Robust dynamic continuous network design problem ［J］.Transportation Research Record，2007，2029:58-71.

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

［11］馬孝先.金融優(yōu)化與風(fēng)險(xiǎn)度量［M］.北京:中國財(cái)政經(jīng)濟(jì)出版社，2009.

［12］ Philippe Jorion.Value at risk:the benchmark for controlling market risk［M］.New York:Irwin Professional Publishing，1996.

Discrete traffic network design model under supply and demand uncertainty

Lu Huapu1Li Yue1Yu Xinxin2

(1Institute of Transportation Engineering，Tsinghua University，Beijing 100084，China)
(2Transport Planning and Research Institute of Ministry of Transport，Beijing 100028，China)

Regarding the uncertainty of traffic supply，demand and decision principles in traffic design，a design model for uncertain discrete traffic network based on uncertainty theory is proposed.Firstly，supply and demand elements are assumed to be stochastic variables.The semi-standard error and value at risk are used to measure uncertainty and a multi-objective bi-level optimized model considering decision risk attitude is built.Then，SPEA2(strength pareto evolutionary algorithm 2)based on the conception of Pareto is applied to solve the multi-objective bi-level optimized model.The numerical results of Nguyen-Dupuis network show that the risk value can reflect decision maker's attitude towards risk in measuring traffic design.In various targets there are alternative relations in multi-object design.The increase of the construction funds can effectively improve the network performance.However，such improvement is not obvious when the investment is beyond a certain limit.

discrete traffic network design;supply and demand uncertainty;risk attitude;value at risk;bi-level optimization

U491.1

A

1001－0505(2012)06-1221-06

10.3969/j.issn.1001 －0505.2012.06.036

2012-02-26.

陸化普(1957—)，男，博士，教授，博士生導(dǎo)師，luhp@mail.tsinghua.edu.cn.

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

陸化普，李悅，蔚欣欣.供給與需求不確定的離散交通網(wǎng)絡(luò)設(shè)計(jì)模型［J］.東南大學(xué)學(xué)報(bào):自然科學(xué)版，2012，42(6):1221-1226.［doi:10.3969/j.issn.1001 －0505.2012.06.036］