容量限制非對稱網絡設計模型及算法

諶永榮

(中南民族大學 數學與統計學學院，武漢 430074)

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

1 容量限制網絡設計模型

網絡設計模型：

上層

下層

求向量(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：確定遺傳算法的編碼及解碼方法，隨機產生一個由M個染色體構成的初始群體P(0)，置t:=0;

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

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

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

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

步驟7：若t≤T，則t:=t+1，轉步驟2；否則算法停止，輸出最優解.

3 計算實例

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

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

圖1 道路網絡 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 算法結果Tab.2 Results of the algorithm

4 結束語

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