易富君 鄧 衛(wèi) 王 晨 周竹萍

(東南大學(xué)交通學(xué)院1) 南京 210096) (招商局重慶交通科研設(shè)計(jì)院有限公司2) 重慶 400068) (江蘇省交通工程建設(shè)局3) 南京 210004)

在經(jīng)濟(jì)全球化進(jìn)程中,城市區(qū)域化和區(qū)域城市化正在成為城鎮(zhèn)系統(tǒng)演化的一個(gè)基本態(tài)勢,進(jìn)而形成了以一個(gè)或多個(gè)中心城市為核心的經(jīng)濟(jì)圈[1].公路網(wǎng)作為促使經(jīng)濟(jì)圈形成的一個(gè)重要條件,在規(guī)劃和建設(shè)的時(shí)候,不但要滿足交通需求,還要追求出行的舒適、安全、快速,以及可持續(xù)發(fā)展等多項(xiàng)目標(biāo)[2].本文在分析經(jīng)濟(jì)圈公路網(wǎng)絡(luò)布局的要求和特點(diǎn)的基礎(chǔ)上,建立起基于經(jīng)濟(jì)圈公路網(wǎng)絡(luò)布局優(yōu)化特點(diǎn)的多目標(biāo)雙層規(guī)劃布局優(yōu)化模型.上層規(guī)劃為決策者的設(shè)計(jì)方案,下層規(guī)劃為使用者的出行選擇,即交通流量分配.下層不能改變方案,但能根據(jù)自身的需要選擇合適的出行路線,上層必須考慮出行信息,綜合路網(wǎng)的基本要求和實(shí)際的出行需要對方案進(jìn)行調(diào)整,是一個(gè)典型的雙層規(guī)劃模型,并應(yīng)用遺傳-模擬退火混合優(yōu)化策略算法(GASA)對模型進(jìn)行求解.

1 經(jīng)濟(jì)圈公路網(wǎng)布局的特點(diǎn)及要求

經(jīng)濟(jì)圈公路網(wǎng)是指連接經(jīng)濟(jì)圈內(nèi)各城市的公路所構(gòu)成的公路網(wǎng)絡(luò)系統(tǒng).本文所研究的經(jīng)濟(jì)圈公路網(wǎng)是連接經(jīng)濟(jì)圈內(nèi)各城市的公路所構(gòu)成的公路網(wǎng)絡(luò)系統(tǒng),包括連接城市與城市之間的高速公路、一級公路、二級公路、三級公路、四級公路等五類公路.

國家級各類公路網(wǎng)由于路網(wǎng)規(guī)模較大、結(jié)點(diǎn)層次較高,路網(wǎng)布局的重點(diǎn)是解決結(jié)點(diǎn)之間的宏觀通道性運(yùn)輸聯(lián)系問題,因而路網(wǎng)布局主要集中在宏觀層次[3-4].布局的主要任務(wù)是確定尚未連通的各結(jié)點(diǎn)之間是否連通、連通后的技術(shù)等級,以及目前已經(jīng)連通的各結(jié)點(diǎn)之間的路線是否改造、改造后的等級.基于此,文中提出的多目標(biāo)雙層規(guī)劃模型能夠?qū)崿F(xiàn)經(jīng)濟(jì)圈公路網(wǎng)布局優(yōu)化的多元要求.

2 雙層布局優(yōu)化模型

2.1 目標(biāo)函數(shù)及約束條件

由于經(jīng)濟(jì)圈公路網(wǎng)絡(luò)建設(shè)投資巨大,因此建設(shè)運(yùn)營資金總量成為公路網(wǎng)布局優(yōu)化問題的一個(gè)總量限制,同時(shí)為了滿足經(jīng)濟(jì)圈內(nèi)各個(gè)城市間的快速通達(dá)性,還需要是路網(wǎng)的連接度最大,即模型上層規(guī)劃的目標(biāo)函數(shù)為建設(shè)投資金額最少并使路網(wǎng)連接度最大.根據(jù)《公路工程技術(shù)標(biāo)準(zhǔn)》給出了路段等級、建設(shè)費(fèi)用及其他屬性,如表1所列.表中假定高速公路路段的屬性固定,即在優(yōu)化過程中屬性不變,不能進(jìn)行改建.假設(shè)路段單位改造費(fèi)用為改造后單位建設(shè)費(fèi)用與改造前單位建設(shè)費(fèi)用之差,同時(shí)上層規(guī)劃中還要考慮選擇可行域、服務(wù)水平以及迂回率(非直線系數(shù))等約束條件.

可行域約束即給決策變量一個(gè)可行范圍,提高搜索效率,文中先確定一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)是否有連接的可能性,排除不能連接的邊,使路網(wǎng)設(shè)計(jì)在此范圍內(nèi)進(jìn)行;服務(wù)水平約束即表示在未來OD流量在路網(wǎng)進(jìn)行分配的時(shí)候應(yīng)滿足一定的服務(wù)水平,即V/C比在一定適合的范圍內(nèi);迂回率主要是保證經(jīng)濟(jì)圈內(nèi)的重要節(jié)點(diǎn)之間的時(shí)間或空間距離不能超過一定的標(biāo)準(zhǔn).在下一節(jié)的雙層規(guī)劃模型中將給出每種約束的數(shù)學(xué)表達(dá)式[5-6].

表1 道路等級及其對應(yīng)值

2.2 模型的建立

由2.1所得到的目標(biāo)函數(shù)及約束條件,建立經(jīng)濟(jì)圈混合公路網(wǎng)絡(luò)設(shè)計(jì)的上層規(guī)劃模型如下.

上層規(guī)劃模型

式中：la為路段a的長度;I(xa)為路段a改造后的建設(shè)費(fèi)用;I(xa)0為路段a改造前的建設(shè)費(fèi)用;ki為第i節(jié)點(diǎn)所連接的邊數(shù);n為經(jīng)濟(jì)圈內(nèi)規(guī)劃所應(yīng)連通的節(jié)點(diǎn)數(shù);rlow為最小允許的V/C;rsup為最大允許的V/C;為現(xiàn)狀路段a的等級;xa為優(yōu)化方案中路段a的等級;uij為任意2個(gè)重要節(jié)點(diǎn)之間的迂回率;umax為允許的最大迂回率;sij為初始可行路網(wǎng)中任意重要節(jié)點(diǎn)之間的最短距離;dij為規(guī)劃路網(wǎng)中任意重要節(jié)點(diǎn)之間的最短距離;Nim為重要節(jié)點(diǎn)集.

下層規(guī)劃模型

3 基于遺傳-模擬退火混合優(yōu)化策略的算法(GASA)

3.1 算法求解的關(guān)鍵要點(diǎn)

設(shè)路網(wǎng)最大可能的路段數(shù)為n,則染色體x1, x2,x3,…,xn表示網(wǎng)絡(luò)優(yōu)化的一個(gè)方案.其中決策變量為xa=(0,1,2,3,4,5,6,7),對應(yīng)值如表2所列.

表2 決策變量與對應(yīng)值

本模型的適應(yīng)度函數(shù),可采用乘除法將上層規(guī)劃問題中的目標(biāo)函數(shù)轉(zhuǎn)化為式(3)的形式,然后使適應(yīng)度函數(shù)與轉(zhuǎn)化過后的目標(biāo)函數(shù)對應(yīng).

適應(yīng)度函數(shù)主要需滿足單值、連續(xù)、非負(fù)和最大化等特點(diǎn),本文采用的適應(yīng)度函數(shù)如下.

式中：V為式(4)右邊第二部分的最大值;O(i)為第i個(gè)個(gè)體的轉(zhuǎn)化后目標(biāo)函數(shù)值;N為種群個(gè)數(shù).

約束條件處理與算子設(shè)計(jì)：(1)可行域根據(jù)路網(wǎng)的可能連接關(guān)系確定備選路段;(2)服務(wù)水平采用懲罰函數(shù)進(jìn)行處理,在可行范圍之外的方案進(jìn)行懲罰;(3)本文采用3個(gè)遺傳算子,即復(fù)制(選擇)、交叉、變異,其中交叉采用兩點(diǎn)交換的原則,變異采用單點(diǎn)變異.

3.2 計(jì)算步驟

步驟1 初始化.根據(jù)實(shí)際產(chǎn)生各點(diǎn)的可能連接邊,生成初始可能連接圖：(1)設(shè)定遺傳算法中的選擇概率 px,交叉概率pc,變異概率pm,每一代產(chǎn)生的種群(染色體)數(shù)目N,最大進(jìn)化代數(shù)以及收斂判斷步長,并令初始進(jìn)化代數(shù)g=0;(2)設(shè)定模擬退火算法中的內(nèi)循環(huán)次數(shù)M,溫度的初始值令

步驟2 對初始方案實(shí)施連通性檢查,確定重點(diǎn)節(jié)點(diǎn)的連通,并得到各路段的通行能力,設(shè)計(jì)車速等相關(guān)參數(shù).

步驟3 根據(jù)模型上層問題的優(yōu)化目標(biāo)函數(shù)確定合理的適應(yīng)度函數(shù)形式,并確定對模型優(yōu)化決策變量進(jìn)行編碼的方式,產(chǎn)生初始種群令g=1.

步驟4 計(jì)算各個(gè)個(gè)體對應(yīng)的工程造價(jià)和路網(wǎng)連接度的比值,即目標(biāo)函數(shù),對比值進(jìn)行排序,將比值不大于當(dāng)前最優(yōu)值的個(gè)體轉(zhuǎn)入下層規(guī)劃進(jìn)行配流,計(jì)算V/C.

步驟5 如果 g＞gmax或 gstop＞gmaxstop,所得染色體即為模型的解,輸出結(jié)果,否則轉(zhuǎn)下一步.

步驟8 退溫,令T=0.5T,轉(zhuǎn)步驟4.

4 算 例

本文選取了以高速公路和干線公路為主,根據(jù)長三角經(jīng)濟(jì)圈簡化現(xiàn)狀道路網(wǎng)絡(luò)結(jié)構(gòu)和已有規(guī)劃以及專家意見,在現(xiàn)狀道路網(wǎng)絡(luò)基礎(chǔ)上選擇5條“可能新建路段”組成經(jīng)濟(jì)圈公路網(wǎng)絡(luò)優(yōu)化的初始可行網(wǎng)絡(luò),如圖1所示.圖中路段屬性包括路段編號和長度.節(jié)點(diǎn)1～14為交通小區(qū)作用點(diǎn),節(jié)點(diǎn)總數(shù)為15個(gè),各節(jié)點(diǎn)之間的OD交換量通過預(yù)測各交通小區(qū)節(jié)點(diǎn)的交通生成量后進(jìn)行交通分布得到.由于篇幅有限,交通小區(qū)的OD交換量分布數(shù)據(jù)和道路技術(shù)等級數(shù)據(jù)略去.

圖1 長三角經(jīng)濟(jì)圈現(xiàn)狀公路網(wǎng)絡(luò)優(yōu)化初始可行網(wǎng)絡(luò)

應(yīng)用遺傳-模擬退火算法求解長三角經(jīng)濟(jì)圈公路網(wǎng)布局優(yōu)化模型.在優(yōu)化過程中,種群規(guī)模取37,交叉概率和變異概率分別為0.95和0.05,最大進(jìn)化代數(shù)取300,對不滿足約束條件的路段的懲罰系數(shù)取該路段的2倍,上層模型中路段負(fù)荷約束上限取1,下限取0,當(dāng)進(jìn)化至124代時(shí),算法終止得到滿意的優(yōu)化結(jié)果如表3所列,其中路段名稱中的新建路段以連接兩城市名命名.從表中可以看出需新建四條公路,改建二條,總投資額為72.07億元,最大連接度為5.13.

表3 長三角經(jīng)濟(jì)圈公路網(wǎng)絡(luò)優(yōu)化方案

5 結(jié)束語

本文將混合公路網(wǎng)設(shè)計(jì)的雙層規(guī)劃模型應(yīng)用到經(jīng)濟(jì)圈公路網(wǎng)布局規(guī)劃中,并將混合網(wǎng)絡(luò)設(shè)計(jì)問題中的連續(xù)性網(wǎng)絡(luò)設(shè)計(jì)問題轉(zhuǎn)化為離散型網(wǎng)絡(luò)設(shè)計(jì)問題,使整個(gè)網(wǎng)絡(luò)設(shè)計(jì)問題成為只含離散變量的公路網(wǎng)設(shè)計(jì)問題.對模型的求解問題,本文運(yùn)用了在交通系統(tǒng)領(lǐng)域運(yùn)用最為廣泛的遺傳算法(GA)和模擬退火算法(SA)進(jìn)行融合而成的遺傳-模擬退火混合算法,并應(yīng)有MATLAB開發(fā)了相應(yīng)的算法程序,應(yīng)用實(shí)例表明模型及算法的可行性,所以對我國經(jīng)濟(jì)圈公路網(wǎng)的布局優(yōu)化改善具有重要的理論意義和實(shí)用價(jià)值.

[1]左 峰.經(jīng)濟(jì)學(xué)視野中大城市經(jīng)濟(jì)圈的形成與發(fā)展-論中國三大城市經(jīng)濟(jì)圈的現(xiàn)狀與發(fā)展[J].華東師范大學(xué)學(xué)報(bào)：哲學(xué)社會科學(xué)版,2002,34(5)：89-96.

[2]張 偉.經(jīng)濟(jì)圈的概念、特征及其規(guī)劃探討[J].城市規(guī)劃,2003,127(16)：47-50.

[3]蓋春英.公路網(wǎng)規(guī)劃布局優(yōu)化研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院,2003.

[4]楊忠誓.公路網(wǎng)絡(luò)路線布局優(yōu)化的雙層規(guī)劃模型及算法研究[J].北方交通,2007(11)：42-45.

[5]聶 偉.都市圈道路網(wǎng)絡(luò)優(yōu)化及其評價(jià)理論研究[D].北京：北京交通大學(xué)交通運(yùn)輸學(xué)院,2007.

[6]劉偉銘,姜 山.基于GASA混合優(yōu)化策略的雙層規(guī)劃模型求解算法研究[J].土木工程學(xué)報(bào),2003 (7)：27-32.