基于區(qū)間需求下系統(tǒng)總時(shí)間最小的混合交通網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化模型*

楊 鵬，楊陽(yáng)梅

(長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙410076)

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

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

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

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

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

1 模型建立

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

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

1.1 目標(biāo)函數(shù)

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

1.2 約束條件

1.2.1 投資約束

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

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

1.2.2 可行域約束

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

計(jì)算步驟如下:

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

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

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

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

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

步驟6:進(jìn)行選擇、交叉、變異操作;

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

3 算例分析

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

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

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

表2 OD流量矩陣

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

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

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

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

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

4 結(jié)論

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

［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è)計(jì)的魯棒優(yōu)化模型［J］.交通運(yùn)輸系統(tǒng)工程與信息，2011，(2):70－76.

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

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

［5］周和平，晏克非，徐汝華，等.基于遺傳算法的公路網(wǎng)絡(luò)設(shè)計(jì)的雙層優(yōu)化模型［J］.同濟(jì)大學(xué)學(xué)報(bào)(自然科學(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］徐澤水，達(dá)慶利.區(qū)間數(shù)排序的可能度法及其應(yīng)用［J］.系統(tǒng)工程學(xué)報(bào)，2003，(1):67 －70.