諶永榮

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

求解離散網(wǎng)絡(luò)平衡設(shè)計問題的遺傳算法

諶永榮

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

針對離散網(wǎng)絡(luò)平衡設(shè)計二層規(guī)劃模型,提出了一種新的求解算法,對上層問題采用遺傳算法,而對下層問題采用平衡交通分配的Frank-Wolf算法.數(shù)值試驗結(jié)果表明:該算法是有效的,能夠較快地求解這類網(wǎng)絡(luò)平衡設(shè)計二層規(guī)劃模型.

二層規(guī)劃模型;遺傳算法;Frank-Wolf算法

隨著社會經(jīng)濟的持續(xù)快速發(fā)展,都市化進程的不斷推進,城市交通需求急劇增加,交通擁擠問題已成為一個世界性難題.而城市交通網(wǎng)絡(luò)設(shè)計問題(簡稱NDP)是交通問題中的一個重要的組成部分.城市交通網(wǎng)絡(luò)設(shè)計問題就是通過在現(xiàn)有交通網(wǎng)絡(luò)中增加新的路段或更新、改善已有路段的能力,從而達到使整個交通網(wǎng)絡(luò)某種系統(tǒng)性能最優(yōu)的目的.因此城市交通網(wǎng)絡(luò)設(shè)計問題的研究具有非常重要的現(xiàn)實意義.

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

對于連續(xù)網(wǎng)絡(luò)設(shè)計問題,由于問題中的目標函數(shù)是連續(xù)的(甚至還可以進一步要求它是可微的、凸的),便于數(shù)學(xué)處理,所以一直以來受到大家的關(guān)注,并且已經(jīng)有了一些很好的求解算法[7,8].但是實際上遇到更多的是離散網(wǎng)絡(luò)設(shè)計問題,因為即使是對已有路段改進,一般也是增加車道,而增加車道所導(dǎo)致通行能力的增加就不是連續(xù)漸變的,而是一次跳躍,其實這就是一個離散問題.文獻[9]、[10]通過考慮道路改造的級別,既探討增加車道后對交通狀況的改善情況,也考慮投資費用問題,提出了離散網(wǎng)絡(luò)平衡設(shè)計問題的一種新的二層規(guī)劃模型.本文提出了一種該二層規(guī)劃模型的新的求解方法,模型求解中,上層模型采用遺傳算法,而下層問題直接利用Frank-W olf算法求解.數(shù)值試驗計算結(jié)果顯示,本文設(shè)計的算法可以快速有效地求解這類網(wǎng)絡(luò)平衡設(shè)計的二層規(guī)劃問題.

1 具有多級選擇的路網(wǎng)改造平衡設(shè)計模型

考慮道路網(wǎng)絡(luò)G=(N,A),其中N為網(wǎng)絡(luò)節(jié)點集,A為有向弧集(路段集合),設(shè)Aˉ?A為擬改造路段集,可記為

以下約定xa為路段a上的交通量,它們組成的向量為X={…,xa,…};

ca為路段a的現(xiàn)有容量,即為該路段允許通過的最大交通量(若a為新增路段,則ca=0);

bi為路段a實施第i(i=1,2,…,n)級改造的擴a容量,它們組成的矩陣記為B=(bai)m×n,則進行i級改造后路段a的容量為ca+bai;

di為路段a進行i級改造所需投資額,它們組成a的矩陣記為D=(dai)m×n;

ta(xa)為路段a上的行駛時間(或費用);

fkrs為O-D對(r,s)間路徑k上的交通量;

yai為路段a上的投資決策變量,i=1,2,…,n為改造的等級,它們組成的矩陣記為為 路 段 與 路 徑 關(guān) 聯(lián) 矩 陣,若以路網(wǎng)的運行費用與改造投資費用為目標,則有如下二層規(guī)劃模型:

上層:

下層:

其中θ為目標函數(shù)的加權(quán)系數(shù),它同時也起量綱轉(zhuǎn)換作用.

2 多級別路網(wǎng)平衡設(shè)計問題的求解算法

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

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法.它最早由美國密執(zhí)安大學(xué)的Holland教授提出,起源于20世紀60年代對自然和人工自適應(yīng)系統(tǒng)的研究.該算法通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿,來完成對問題最優(yōu)解的自適應(yīng)搜索過程.

遺傳算法的運算過程[11]如下.

步驟1:初始化.設(shè)置進化代數(shù)計數(shù)器t:=0;設(shè)置最大進化代數(shù)T;隨機生成M個個體作為初始化群體.

步驟2:個體評價.計算當前群體中各個個體的適應(yīng)度.

步驟3:選擇運算.將選擇算子作用于群體.步驟4:交叉運算.將交叉算子作用于群體.

步驟5:變異運算.將變異算子作用于群體.當前群體經(jīng)過選擇、交叉、變異運算之后得到下一代群體.

步驟6:終止條件判斷.若t≤T,則t:=t+1,轉(zhuǎn)到步驟2;否則,輸出最優(yōu)解,終止計算.

(1)個體.文中對每個個體采用4位長度的符號編碼,每個基因座上的等位基因為0,1,2,3,并按照如下方式將每個個體與對應(yīng)問題的可行解之間相對應(yīng):

設(shè)共有m個待改造路段,每個路段有n個改造級別可供選擇,yia為路段投資決策變量,

它們組成的矩陣為(yia)m×n,現(xiàn)在就是將這種形式的可行解與遺傳算法中的個體對應(yīng)起來.

例如,有4個待改造路段,每個路段有3個改造級別可選,則:

為原問題的一個可行解,它表示第1條路段進行第1級改造,第2條路段不進行改造,第3條路段進行第3級改造,第4條路段進行第2級改造.

則Y對應(yīng)的個體可表示為X=(1,0,3,2),其中分量分別表示改造的級別,因此我們就可以將個體與問題的可行解對應(yīng)起來.

(2)適應(yīng)度函數(shù).遺傳算法對個體的評價是通過個體的適應(yīng)度的大小來實現(xiàn)的,所以算法中適應(yīng)度函數(shù)的選取非常重要.這里的適應(yīng)度函數(shù)我們可以直接取為模型中上層規(guī)劃中的目標函數(shù),即:

(3)遺傳操作.本文中采用基本的3種遺傳操作算子,即選擇、交叉和變異.選擇算子采用比例選擇算子,也叫賭盤選擇,是指每個個體被選中并遺傳到下一代的概率與該個體的適應(yīng)度大小成正比.交叉算子采用單點交叉,變異算子選擇均勻變異,并適當?shù)剡x取交叉概率和變異概率.

2.2 整體算法的迭代步驟

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

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

步驟2:將當前群體P(t)中每個個體轉(zhuǎn)換為對應(yīng)的Y,對每個Y用Frank-W olf算法求解下層規(guī)劃問題的最優(yōu)解.

步驟3:將上層規(guī)劃的目標函數(shù)作為適應(yīng)度函數(shù)評價所有個體.

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

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

3 數(shù)值試驗與結(jié)果分析

圖1為一個9節(jié)點的道路網(wǎng),虛線表示待添加或擴容路段,共有4條,其中(2,5)和(5,8)是對原有路段改造擴容.設(shè)O-D對(1,9),(3,7)的出行量均為55,各路段自由流行駛時間和路段初始容量見表1.

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

表1t0a及ca的值Tab.1 Value oft0aandca

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

本算例中路段a行駛時間采用BPR函數(shù):ta=t0a[1+其中ta0為路段a的自由流行駛時間,α,β為參數(shù).表2是采用本文提出的遺傳算法求解的結(jié)果.

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

對遺傳算法結(jié)果分析如下:

(1)由于權(quán)系數(shù)的大小代表投資費用的重要程度,θ增大,表示決策者著重考慮最小化投資費用,因此路網(wǎng)投資費用隨著θ的增大而減小,計算結(jié)果與之吻合;

(2)遺傳算法迭代簡單,且對模型的性質(zhì)沒有嚴格要求,因此應(yīng)用面廣;

(3)從數(shù)值試驗結(jié)果中可以看出,遺傳算法求解該問題收斂較快,且只在很小的一個范圍內(nèi)進行搜索就得到了很好的解,說明該算法是有效的.

[1] Yang H,BellM G H.M odels and algorithm for road network design:a review and some new developments[J].T ransportation 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].Opt im ization and Engineering,2007,8:241-257.

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

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

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

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

[7] Suwansirikul C,Friesz T L,Tobin R L.Equilibrium decomposed opt im ization: a heuristic for the continuous equilibrium network design problem[J].T ransportation Science,1987,21(4):254-263.

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

[9] 肖海燕,黃崇超.一個新的交通網(wǎng)絡(luò)設(shè)計模型及其算法[J].武漢大學(xué)學(xué)報:理學(xué)版,2006,52(3):301-304.

[10] 黃崇超,肖海燕.具有多級選擇的離散網(wǎng)絡(luò)平衡設(shè)計模型與算法[J].運籌與管理,2008,17(2):15-20.

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

Genetic Algorithm for D iscrete Network Equilibrium Design Problem

Chen Yong rong
(College ofM athematics and Statistics,South-CentralU niversity for N ationalities,W uhan 430074,China)

In this paper,a new algorithm for the bi-level programm ing model of discrete network equilibrium design problem is proposed.The uppermodel is solved by the genetic algorithm and the lowermodel by the Frank-Wolf algorithm.The numerical results show that this algorithm is effective and can solve the problem quickly.

bi-level programm ing model;genetic algorithm;Frank-Wolf algorithm

O 491

A

1672-4321(2011)01-0113-04

2010-12-30

諶永榮(1975-),女,講師,研究方向:系統(tǒng)優(yōu)化與管理決策,E-mail:yongrongchen2000@sina.com