楊 鵬，楊陽梅

(長沙理工大學(xué)交通運輸工程學(xué)院，湖南長沙410076)

交通網(wǎng)絡(luò)設(shè)計問題(NDP)是交通科學(xué)研究的熱點問題之一.NDP問題通常分為連續(xù)交通網(wǎng)絡(luò)設(shè)計問題(CNDP)和離散交通網(wǎng)絡(luò)設(shè)計問題(DNDP)兩種，前者針對改擴建，后者針對新建道路，而在實際交通網(wǎng)絡(luò)設(shè)計中，這兩種情況往往同時存在，稱之為混合交通網(wǎng)絡(luò)設(shè)計問題(MNDP).

1973年Morlok首次提出交通網(wǎng)絡(luò)設(shè)計問題，近30年來國內(nèi)外學(xué)者在交通網(wǎng)設(shè)計模型和算法研究中取得很多成果，并在實際應(yīng)用中取得不錯成效.Ben－Ayed［1］給出交通網(wǎng)絡(luò)設(shè)計雙層規(guī)劃模型的一般公式.孫華等［2］考慮交通發(fā)生、吸引量是確定的，而OD需求是不確定情況下連續(xù)交通網(wǎng)絡(luò)設(shè)計問題，提出了利用魯棒優(yōu)化方法建立用戶均衡約束下的極大極小模型.陸化普等［3］假定OD需求是滿足給定概率分布的隨機變量，采用隨機抽樣的方式形成需求情景集合，建立了OD需求不確定的離散交通網(wǎng)絡(luò)設(shè)計雙層規(guī)劃模型.周和平［4，5］研究混合網(wǎng)絡(luò)設(shè)計模型時，將連續(xù)交通網(wǎng)絡(luò)設(shè)計轉(zhuǎn)化為離散交通網(wǎng)絡(luò)設(shè)計問題，建立混合交通網(wǎng)絡(luò)設(shè)計模型.

目前，傳統(tǒng)的“四階段法”忽視需求的不確定性，雖有學(xué)者提出不確定的來源有:內(nèi)在不確定性、輸入不確定性以及傳播不確定性，但預(yù)測模型產(chǎn)生的結(jié)果卻是唯一的，這樣的預(yù)測結(jié)果具有很大的風(fēng)險性.自Moore提出區(qū)間分析以來，由于區(qū)間數(shù)在度量交通需求不確定的特殊優(yōu)勢，帶區(qū)間參數(shù)的多屬性決策優(yōu)化方法成為研究的熱點.Martorell［6］提出一種解決區(qū)間約束的遺傳算法.Averbakh對帶區(qū)間數(shù)的后悔網(wǎng)絡(luò)優(yōu)化問題進行了研究.Kasperski［7］對帶區(qū)間數(shù)的 Minmax后悔優(yōu)化問題進行了研究，并提出一種近似算法.Kasperski在其專著中，采用最小最大后悔值模型，對帶區(qū)間數(shù)的離散優(yōu)化問題進行研究，給出了最短路、最小割集、指派問題等經(jīng)典問題的求解算法.徐澤水等［8］提出基于可能度的區(qū)間數(shù)排序法，該方法具有較強的實用性，故本文涉及的區(qū)間數(shù)排序采用此方法.區(qū)間數(shù)排序公式如下:

前文已經(jīng)論述了交通網(wǎng)絡(luò)設(shè)計問題分為離散型交通網(wǎng)絡(luò)設(shè)計和連續(xù)型交通網(wǎng)絡(luò)設(shè)計問題，將連續(xù)交通網(wǎng)絡(luò)問題轉(zhuǎn)化為離散交通網(wǎng)絡(luò)設(shè)計問題;周和平提出一種方法，可同時得到公路的等級與車道數(shù).根據(jù)《公路工程標準》，公路分為5個等級，車道數(shù)可分為2，4，6，8，12等，將公路等級和車道數(shù)進行組合編號，并以此作為決策變量，如表1所示.

表1 決策變量及其對應(yīng)值

1 模型建立

給定交通網(wǎng)絡(luò)G=(N，C)，定義N為網(wǎng)絡(luò)節(jié)點的集合，C為網(wǎng)絡(luò)邊的集合，其中，A為改造路段的集合，B為新建路段的集合;R和S為網(wǎng)絡(luò)中起點和訖點的集合為路段交通量，包括改造和新建路段交通量，組成向量xa為改造路段決策變量，xb為新建路段決策變量;H為路段總投資概算.

本文運用雙層規(guī)劃模型，上層為區(qū)間需求下系統(tǒng)總時間最小值模型，下層為區(qū)間需求下交通分配用戶均衡模型.

1.1 目標函數(shù)

以系統(tǒng)總時間最小值為目標，建立優(yōu)化模型，即:

1.2 約束條件

1.2.1 投資約束

公路網(wǎng)絡(luò)建設(shè)耗資巨大，一旦網(wǎng)絡(luò)設(shè)計不當，將造成無法挽回的損失，故將整個網(wǎng)絡(luò)的投資預(yù)算作為約束條件，即:

其中:la為已有路段a的長度，lb為新建路段的長度;ca(xa)為已有路段a的投資函數(shù);cb(xb)為新建路段b的投資函數(shù);H為整個網(wǎng)絡(luò)的投資總額.

1.2.2 可行域約束

給決策變量一個可行范圍，可以有效減小搜索空間，提高搜索效率.首先確定整個路網(wǎng)的鄰接關(guān)系，剔除不能連接的邊，建立備選路段.

對于已有路段，假定改造后路段的服務(wù)能力不能低于現(xiàn)有路段的服務(wù)能力，即:

對于新建路段，決策變量在規(guī)定的范圍內(nèi)取值即可:

1.3 數(shù)學(xué)模型

上層混合交通網(wǎng)絡(luò)設(shè)計模型［MNDP］

下層基于區(qū)間需求交通分配用戶均衡模型［IUE］

2 算法設(shè)計

雙層規(guī)劃模型是NP完全問題，用傳統(tǒng)方法很難求解，本文采用基于區(qū)間分析的遺傳算法求解以上模型.本文編碼采用實數(shù)編碼，編碼包括改造方案和新建方案.遺傳算子選擇采用輪盤賭選擇、交叉采用兩點交叉、變異采用基本位突變.

計算步驟如下:

步驟1:根據(jù)實際網(wǎng)絡(luò)狀況，生成可能的初始交通網(wǎng)絡(luò)圖，生產(chǎn)備選方案集，包括新建的路段集A和需要改進的路段集B;

步驟2:設(shè)定種群規(guī)模Np、交叉概率pc、變異概率pm和最大迭代次數(shù)Nh的值.根據(jù)交通網(wǎng)絡(luò)圖的可能連接關(guān)系隨機生產(chǎn)生成一個種群并設(shè)置初始進化代數(shù)gen=0;

步驟3:轉(zhuǎn)入下層進行交通流量分配，將路段交通量和走行時間的計算結(jié)果返回上層;

步驟4:計算各個個體對應(yīng)的目標函數(shù)和適應(yīng)度函數(shù)值，同時驗證各個個體是否滿足約束條件，對不滿足的個體加以懲罰值;

步驟5:如果迭代次數(shù)gen?Nh，轉(zhuǎn)Step 10，否則Gen=Gen+1，轉(zhuǎn)入下一步;

步驟6:進行選擇、交叉、變異操作;

步驟7:算法終止，輸出結(jié)果.

3 算例分析

采用圖1的交通網(wǎng)絡(luò)圖驗證模型和算法的可行性，該網(wǎng)絡(luò)包含有9個節(jié)點，14條路段，其中1～12號路段為改造路段，用實線表示，13～16號路段為新建路段，用虛線表示(見圖1).

圖1 交通網(wǎng)絡(luò)圖

表2和表3分別為OD需求矩陣和各路段相關(guān)參數(shù).

表2 OD流量矩陣

表3 路段相關(guān)參數(shù)

本文采用Matlab的區(qū)間分析工具箱和遺傳算法工具箱實現(xiàn).編碼采用1－5的實數(shù)編碼，染色體長度為16位，前12位為改造路段，后4位為新建路段，根據(jù)道路編號排列;種群規(guī)模為30，進化代數(shù)200次，交叉概率為0.85，變異概率為0.03，投資限額為400億元.計算結(jié)果為:

圖2 區(qū)間數(shù)種群進化示意圖

圖3 區(qū)間數(shù)方案路段服務(wù)水平示意圖

圖3是種群進化示意圖，算法在22代得到最優(yōu)解，適應(yīng)度函數(shù)值為5.2 ×104，對應(yīng)的染色體編碼為［4，5，5，3，3，5，2，5，5，3，3，2，5，4，0，1］，其中改造路段編號為:1，2，3，6，8，9，10，11;新建路段為:13，14，16;方案總投資為356.24億元.圖3 是方案路段服務(wù)水平，可以看出方案各路段交通狀況良好.

4 結(jié)論

本文研究了需求不確定條件下，建立基于系統(tǒng)總時間最小的混合交通網(wǎng)絡(luò)設(shè)計優(yōu)化模型，將區(qū)間分析和遺傳算法相結(jié)合，設(shè)計求解算法.該模型能夠避免交通網(wǎng)陷入Braess詭異，同時考慮交通需求的不確定性，具有很強的應(yīng)用價值.

［1］Ben－Ayed O，Boyce D E，Blair C E.A general bilevel linear programming formulation of the network design problem［J］.Transportation Research Part B:Methodological，1988，(22):311 －318.

［2］孫華，高自友，龍建成.不確定OD需求下連續(xù)交通網(wǎng)絡(luò)設(shè)計的魯棒優(yōu)化模型［J］.交通運輸系統(tǒng)工程與信息，2011，(2):70－76.

［3］陸化普，蔚欣欣，卞長志.OD需求不確定的離散交通網(wǎng)絡(luò)設(shè)計模型研究［J］.公路交通科技，2011，(5):128－132.

［4］周和平，胡列格，裴武.基于優(yōu)先與公平的城市群一體化混合公路交通網(wǎng)絡(luò)設(shè)計模型［J］.系統(tǒng)工程，2007，(7):92－95.

［5］周和平，晏克非，徐汝華，等.基于遺傳算法的公路網(wǎng)絡(luò)設(shè)計的雙層優(yōu)化模型［J］.同濟大學(xué)學(xué)報(自然科學(xué)版)，2005，(7):920－925.

［6］Martorell S，Carlos S，Sánchez A，et al.Constrained optimization of test intervals using a steady－state genetic algorithm［J］.Reliability Engineering＆ System Safety，2000，(3):215－232.

［7］Kasperski A，Zieliński P.An approximation algorithm for interval data minmax regret combinatorial optimization problems［J］.Information Processing Letters，2006，(5):177 －180.

［8］徐澤水，達慶利.區(qū)間數(shù)排序的可能度法及其應(yīng)用［J］.系統(tǒng)工程學(xué)報，2003，(1):67 －70.