諶永榮

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，武漢 430074)

網(wǎng)絡(luò)平衡設(shè)計(jì)問題[1]可分為兩類:一是對(duì)已有路段改造以增加其通行能力,另一則是添加新路段.前者被稱作“連續(xù)網(wǎng)絡(luò)設(shè)計(jì)問題”(CNDP)[2,3],這里的“連續(xù)”是指路段通行能力的增加量是連續(xù)的; 而后者被稱作“離散網(wǎng)絡(luò)設(shè)計(jì)問題” (DNDP)[4-6].

對(duì)于連續(xù)網(wǎng)絡(luò)設(shè)計(jì)問題,由于問題中的目標(biāo)函數(shù)是連續(xù)的(甚至還可以進(jìn)一步要求它是可微的、凸的),便于數(shù)學(xué)處理，所以一直以來受到大家的關(guān)注，并且已經(jīng)有了一些很好的求解算法[7].但在前面的這些文獻(xiàn)中，都是假定網(wǎng)絡(luò)中各路段的行駛費(fèi)用只與本路段的流量有關(guān)，這在很多情況下是合理的，此時(shí)問題可建成一個(gè)二層規(guī)劃模型，然后對(duì)二層規(guī)劃模型提出算法.但實(shí)際網(wǎng)絡(luò)中，很多時(shí)候各路段的行駛費(fèi)用不僅與自身的流量有關(guān)，還與其他路段上的流量有關(guān)，而且路段費(fèi)用向量關(guān)于路段流量變量的雅克比矩陣是非對(duì)稱的，這時(shí)網(wǎng)絡(luò)設(shè)計(jì)問題中下層的用戶平衡就不能寫成一個(gè)數(shù)學(xué)規(guī)劃模型，本文中將此時(shí)的下層用戶平衡條件采用變分不等式來描述，并針對(duì)該模型設(shè)計(jì)了求解方法,模型求解中,上層問題采用遺傳算法，而下層問題采用對(duì)角化方法求解.

1 連續(xù)網(wǎng)絡(luò)平衡設(shè)計(jì)模型

若以路網(wǎng)的運(yùn)行費(fèi)用與投資費(fèi)用為目標(biāo)，則有如下模型.

上層問題：

s.t.ya≥0,?a∈A.

下層問題：

求x*使得?x∈F′，均有(x-x*)Tt(x*,y)≥0，

其中F′={x|x=Δf,x≤c,Λf=q,f≥0}.

因模型中既有路段變量x又有路徑變量f，因此利用關(guān)系式x=Δf可將模型中路段變量x去掉，記T(f,y)=ΔTt(Δf,y)，

則下層模型可寫為：

求f*使得?f∈F，均有(f-f*)TT(f*,y)≥0，

其中F={f|Δf≤c,Λf=q，f≥0}.

2 求解算法

2.1 求解上層問題的遺傳算法

由于上層問題沒有明確的解析表達(dá)式，它里面的變量x是由求解下層問題來給出的，所以求解這類問題一般采用啟發(fā)式算法.遺傳算法[8]，它最早由美國密執(zhí)安大學(xué)的Holland教授提出，起源于20世紀(jì)60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究.該算法通過對(duì)生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)理的模仿，來完成對(duì)問題最優(yōu)解的自適應(yīng)搜索過程.

(1)適應(yīng)度函數(shù).遺傳算法對(duì)個(gè)體的評(píng)價(jià)是通過個(gè)體的適應(yīng)度的大小來實(shí)現(xiàn)的，所以算法中適應(yīng)度函數(shù)的選取非常重要.這里的適應(yīng)度函數(shù)我們可以直接取為模型中上層規(guī)劃中的目標(biāo)函數(shù)，即：

(2)編碼.由于實(shí)數(shù)編碼不需要編碼和解碼過程，且精度高，故本問題的求解采用實(shí)數(shù)編碼.

(3)選擇算子.本文中采用基本的3種遺傳操作算子，即選擇、交叉和變異.選擇算子采用比例選擇算子，也叫賭盤選擇，即每個(gè)個(gè)體被選中并遺傳到下一代的概率與該個(gè)體的適應(yīng)度大小成正比.

(5)變異算子采用均勻變異.

2.2 求解下層問題的算法

算法步驟如下.

步驟1：初始化.從初始可行點(diǎn)f0∈F開始，令k=1，給定迭代精度ε>0.

步驟2：對(duì)角化.求凸規(guī)劃子問題：

得到解fk.

步驟3：收斂性檢驗(yàn).若‖fk-fk-1‖≤ε，算法停止.否則令k=k+1轉(zhuǎn)步驟2.

算法步驟2中是一個(gè)凸規(guī)劃問題，可以用任何適合的方法求解.

2.3 整體算法的迭代步驟

算法實(shí)現(xiàn)步驟如下.

步驟1：初始化.設(shè)置最大進(jìn)化代數(shù)T，群體規(guī)模M，交叉概率pc，變異概率pm，置t:=0，隨機(jī)產(chǎn)生M個(gè)個(gè)體作為初始群體P(0).

步驟2：對(duì)每個(gè)個(gè)體求解下層規(guī)劃問題的最優(yōu)解.

步驟3：將上層規(guī)劃的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)評(píng)價(jià)所有個(gè)體.

步驟4：根據(jù)群體中每個(gè)個(gè)體的適應(yīng)度值，對(duì)P(t)做選擇運(yùn)算、交叉運(yùn)算和變異運(yùn)算，P(t)經(jīng)過3種運(yùn)算后得到下一代群體P(t+1).

步驟5：終止條件判斷.若t≤T，則t:=t+1，轉(zhuǎn)步驟2；否則停止計(jì)算，輸出最優(yōu)解.

3 數(shù)值試驗(yàn)

本文中的網(wǎng)絡(luò)如圖1所示，兩個(gè)OD對(duì)(1,3)，(5,3),需求量均為55.

圖1 道路網(wǎng)絡(luò)

其中t(x)=Ax+b,Ga(ya)=1.5da(ya)2，

c=(40+y1,45+y2,40+y3,35+y4,40+y5,35+y6,40+y7),

A=

b=(2,2,1,1,3,1,2),d1=d2=2,d3=d4=1,d5=3,d6=d7=2.

計(jì)算可得，路段y1,y2,y3,y4,y5,y6,y7能力增加量分別為1.1085，7.3900，3.7126，1.4956，5.8592，2.6921，8.4106，目標(biāo)函數(shù)值Z=1490.0001.

4 結(jié)束語

本文針對(duì)非對(duì)稱平衡網(wǎng)絡(luò)設(shè)計(jì)問題，采用遺傳算法求解，從數(shù)值試驗(yàn)結(jié)果可知該算法是可行的，而且遺傳算法求解速度快，對(duì)模型沒有特別的要求.在求解下層問題時(shí)，采用收斂性快的凸規(guī)劃的最優(yōu)求解算法，可大大提高算法的運(yùn)算效率.

[1]Yang H,Bell M G H.Models and algorithm for road network design: a review and some new developments[J].Transportation Review,1998,18:257-278.

[2]Gao Z Y,Sun H J,Zhang H Z.A globally convergent algorithm for transportation continuous network design problem[J].Optimization and Engineering,2007,8:241-257.

[3]高自友，張好智，孫會(huì)君.城市交通網(wǎng)絡(luò)設(shè)計(jì)問題中的雙層規(guī)劃模型與算法研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2004,4(1):35-44.

[4]Gao Z Y,Wu J J,Sun H J.Solution algorithm for the bi-level discrete network design problem[J].Transportation Research B,2005,39:479-495.

[5]劉燦齊.交通網(wǎng)絡(luò)設(shè)計(jì)問題的模型與算法研究[J].公路交通科技,2003,20:57-62.

[6]桂 嵐.交通網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化模型及算法[J].系統(tǒng)工程,2006,24(12):25-32.

[7]高自友，宋一凡，四兵鋒.城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計(jì):理論與方法[M].北京：中國鐵道出版社,2000.

[8]周 明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社,2005.

[9]高自友，任華玲.城市動(dòng)態(tài)交通流分配模型與算法[M].北京：人民交通出版社,2005.