基于區間需求下系統總時間最小的混合交通網絡設計優化模型*

楊 鵬，楊陽梅

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

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

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

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

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

表1 決策變量及其對應值

1 模型建立

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

本文運用雙層規劃模型，上層為區間需求下系統總時間最小值模型，下層為區間需求下交通分配用戶均衡模型.

1.1 目標函數

以系統總時間最小值為目標，建立優化模型，即:

1.2 約束條件

1.2.1 投資約束

公路網絡建設耗資巨大，一旦網絡設計不當，將造成無法挽回的損失，故將整個網絡的投資預算作為約束條件，即:

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

1.2.2 可行域約束

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

對于已有路段，假定改造后路段的服務能力不能低于現有路段的服務能力，即:

對于新建路段，決策變量在規定的范圍內取值即可:

1.3 數學模型

上層混合交通網絡設計模型［MNDP］

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

2 算法設計

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

計算步驟如下:

步驟1:根據實際網絡狀況，生成可能的初始交通網絡圖，生產備選方案集，包括新建的路段集A和需要改進的路段集B;

步驟2:設定種群規模Np、交叉概率pc、變異概率pm和最大迭代次數Nh的值.根據交通網絡圖的可能連接關系隨機生產生成一個種群并設置初始進化代數gen=0;

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

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

步驟5:如果迭代次數gen?Nh，轉Step 10，否則Gen=Gen+1，轉入下一步;

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

步驟7:算法終止，輸出結果.

3 算例分析

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

圖1 交通網絡圖

表2和表3分別為OD需求矩陣和各路段相關參數.

表2 OD流量矩陣

表3 路段相關參數

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

圖2 區間數種群進化示意圖

圖3 區間數方案路段服務水平示意圖

圖3是種群進化示意圖，算法在22代得到最優解，適應度函數值為5.2 ×104，對應的染色體編碼為［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 是方案路段服務水平，可以看出方案各路段交通狀況良好.

4 結論

本文研究了需求不確定條件下，建立基于系統總時間最小的混合交通網絡設計優化模型，將區間分析和遺傳算法相結合，設計求解算法.該模型能夠避免交通網陷入Braess詭異，同時考慮交通需求的不確定性，具有很強的應用價值.

［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需求下連續交通網絡設計的魯棒優化模型［J］.交通運輸系統工程與信息，2011，(2):70－76.

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

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

［5］周和平，晏克非，徐汝華，等.基于遺傳算法的公路網絡設計的雙層優化模型［J］.同濟大學學報(自然科學版)，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］徐澤水，達慶利.區間數排序的可能度法及其應用［J］.系統工程學報，2003，(1):67 －70.