容量限制非對稱網(wǎng)絡(luò)設(shè)計模型及算法

諶永榮

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

一般路網(wǎng)中通常假定各路段的行駛費用只與本路段的流量有關(guān)，且關(guān)于路段流量是連續(xù)可微的，這在很多情況下是合理的，稱該網(wǎng)絡(luò)為對稱網(wǎng)絡(luò). 此時，網(wǎng)絡(luò)設(shè)計問題可建成一個二層規(guī)劃模型[1].如果各路段的行駛費用不僅與自身的流量有關(guān)，還與其他路段上的流量有關(guān)，而且路段費用向量關(guān)于路段流量變量的雅克比矩陣是非對稱的，稱該網(wǎng)絡(luò)為非對稱網(wǎng)絡(luò).由于社會經(jīng)濟快速發(fā)展，車流量與日俱增，造成城市交通越來越擁擠，車輛的行駛費用不僅與自身的行駛路段流量有關(guān)，且與網(wǎng)絡(luò)的其他路段流量有關(guān)，因而實際的交通網(wǎng)絡(luò)多為非對稱.這時網(wǎng)絡(luò)設(shè)計問題中下層的用戶平衡就不能寫成一個數(shù)學規(guī)劃模型，大部分用變分不等式和非線性互補問題來描述[2].本文研究帶容量限制的非對稱網(wǎng)絡(luò)設(shè)計問題[3]，上層同時考慮了增加車道后對交通狀況的改善情況和投資費用問題[4],下層問題則是一個變分不等式.

1 容量限制網(wǎng)絡(luò)設(shè)計模型

網(wǎng)絡(luò)設(shè)計模型：

上層

下層

求向量(x*,q*)∈Ω，滿足對任意的(x,q)∈Ω都有：

t(x*)T(x-x*)-D-1(q*)T(q-q*)≥0,

此時Ω={(x,q)|x=Δf,Λf=q,x≤c,f≥0,q≥0}.

2 模型的求解算法

2.1 求解下層問題的算法

本文的下層是一個帶容量限制的變分不等式問題，采用仿真算法[5]求解.

2.2 整體算法的迭代步驟

模型中上層問題采用遺傳算法[6]求解.

整體算法迭代如下.

步驟1：確定遺傳算法的編碼及解碼方法，隨機產(chǎn)生一個由M個染色體構(gòu)成的初始群體P(0)，置t:=0;

步驟2: 將當前群體P(t)中每個染色體轉(zhuǎn)換為對應(yīng)的Y，對每個Y用上述仿真算法求解下層的最優(yōu)解;

步驟3：將步驟2中得到的最優(yōu)解計算上層問題的目標函數(shù)值并將它作為各個染色體的適應(yīng)度值來評價所有染色體;

步驟5：對當前群體P(t)以交叉概率pc進行單點交叉運算;

步驟6：對當前群體P(t)以變異概率pm進行均勻變異運算，并在交叉和變異過程中采用保留最佳個體策略，P(t)經(jīng)過3種遺傳操作運算后得到下一代群體P(t+1);

步驟7：若t≤T，則t:=t+1，轉(zhuǎn)步驟2；否則算法停止，輸出最優(yōu)解.

3 計算實例

圖1為一個9節(jié)點的道路網(wǎng)，其中(2，5)和(5，8)是對原有路段改造擴容.

各備選路段對應(yīng)的擴容量和投資額用下列矩陣表示(單位：103元)：

圖1 道路網(wǎng)絡(luò) Fig.1 Road network

路段a1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t0a 2 2 3 3 1 1 2 2 21212122ca4545 0 03530303536 40 35 35 35 30 40 40

表2 算法結(jié)果Tab.2 Results of the algorithm

4 結(jié)束語

本文討論了帶容量限制的非對稱路網(wǎng)設(shè)計問題，給出了問題的模型和算法，并用一個小型的路網(wǎng)來檢驗算法的可行性，從結(jié)果可知，θ越大，表明決策者越看重投資費用，路網(wǎng)投資費用隨著θ的增大而減小，與表2計算結(jié)果是一致的，表明該算法有效.