陳　亮，　盧厚清

(1.解放軍蚌埠汽車士官學(xué)校 運(yùn)輸勤務(wù)系, 安徽 蚌埠 233011；　2.解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院, 江蘇 南京 210007 )

?

雙層智能優(yōu)化算法求解時(shí)變網(wǎng)絡(luò)最短路徑問題

陳亮1，盧厚清2

(1.解放軍蚌埠汽車士官學(xué)校 運(yùn)輸勤務(wù)系, 安徽 蚌埠 233011；2.解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院, 江蘇 南京 210007 )

摘要邊成本為一般函數(shù)的時(shí)變網(wǎng)絡(luò)最短路徑問題(TDSP)，已被證明不存在多項(xiàng)式時(shí)間算法。同時(shí)智能優(yōu)化算法被廣泛地用于求解該類問題，但多數(shù)沒有考慮節(jié)點(diǎn)的可等待約束。提出了求解TDSP問題的雙層智能優(yōu)化算法，內(nèi)層遺傳算法優(yōu)化每條可行路徑的各節(jié)點(diǎn)離開時(shí)間，外層蟻群算法優(yōu)化構(gòu)建的路徑，最終搜索到從起始點(diǎn)到終點(diǎn)的最短時(shí)間路徑。實(shí)驗(yàn)結(jié)果表明：雙層智能優(yōu)化算法能快速尋優(yōu)，并且收斂速度和最優(yōu)路徑較同類算法更優(yōu)秀。

關(guān)鍵詞時(shí)變網(wǎng)絡(luò)；最短路徑；雙層優(yōu)化；智能優(yōu)化算法

Time-dependent Shortest Path Problem in Solution to Two-level Intelligent Optimization Algorithm

CHEN Liang1,LU Houqing2

(1. Department of Transportation Service, Bengbu Automobile NCO Academy, Bengbu Anhui 233011, China；2. College of Field Engineering, PLA Univ.of Sci.& Tech.Nanjing Jiangsu 210007, China)

AbstractIt is proven there is no polynomial time algorithm for the time-dependent shortest path (TDSP) occurring when marginal cost is a general function. Also, intelligent optimization algorithms are extensively used in solving such problems, but most of them have not considered the waiting constraint of the nodes. This paper brings out the two-layer intelligent optimization to solve out TDSP problem: at internal layer, optimize the leaving time of each node of each feasible path with genetic algorithm; at external layer, optimize the built path with ant colony algorithm. In this way, the shortest time path from a starting point to an end point is obtained. The experimental result shows, the two-level intelligent optimization algorithm is able to identify the optimization and the convergence speed with optimized path is better than other algorithms.

Keywordstime-dependent networks; shortest path problem; two-layer optimization; intelligent optimization algorithm

在戰(zhàn)時(shí)配送運(yùn)輸過程中，選擇到達(dá)時(shí)間最短的路徑，可以達(dá)到快速開進(jìn)、降低損耗的目的。但是，戰(zhàn)時(shí)組織軍事配送運(yùn)輸，由于戰(zhàn)場環(huán)境的惡劣、多變、復(fù)雜，以及敵人的襲擊破壞，使得軍事配送運(yùn)輸網(wǎng)絡(luò)的邊權(quán)(如配送距離、時(shí)間等)具有動態(tài)可變性，相對于邊權(quán)不發(fā)生變化的靜態(tài)網(wǎng)絡(luò)，這類網(wǎng)絡(luò)被稱為動態(tài)網(wǎng)絡(luò)。動態(tài)網(wǎng)絡(luò)按照邊權(quán)的特性，又可分為隨機(jī)網(wǎng)絡(luò)(Stochastic Network，SN)、模糊網(wǎng)絡(luò)(Fuzzy network，F(xiàn)N)和時(shí)變網(wǎng)絡(luò)(Time-Dependent Network，TDN)，SN中的邊權(quán)是隨機(jī)變量，F(xiàn)N中邊權(quán)是模糊不定的，而TDN中的邊權(quán)表現(xiàn)為時(shí)間的函數(shù)，本文主要研究時(shí)變網(wǎng)絡(luò)最短路徑(Time-Dependent Shortest Path，TDSP)問題。

對于TDSP問題，學(xué)者做了大量工作。文獻(xiàn)[1]首次指出傳統(tǒng)的最短路徑算法不適用于時(shí)變網(wǎng)絡(luò)最短路徑問題，須建立嚴(yán)格的一致性約束條件才能求解。文獻(xiàn)[2]將TDN分為FIFO(First-in First-out)網(wǎng)絡(luò)和非FIFO網(wǎng)絡(luò)兩類，證明可用Dijkstra算法求解FIFO網(wǎng)絡(luò)的TDSP問題；在假定時(shí)間離散狀態(tài)下，給出了一種利用逆序動態(tài)規(guī)劃思路求解的非FIFO網(wǎng)絡(luò)的TDSP方法。文獻(xiàn)[3]在研究時(shí)變網(wǎng)絡(luò)模型和理論的基礎(chǔ)上，給出了最短時(shí)間路徑的充要條件，提出了一種可同時(shí)適合FIFO網(wǎng)絡(luò)和非FIFO網(wǎng)絡(luò)的最短路徑算法。文獻(xiàn)[4]提出了等待時(shí)域和最佳出發(fā)時(shí)間理論，給出了一種求解TDSP問題的改進(jìn)Dijkstra算法。但這些算法對時(shí)間是有要求的，要么是離散的，要么需對時(shí)間進(jìn)行離散化處理。因此，算法的時(shí)間效率不高，針對這些問題，文獻(xiàn)[5]用基因插入和基因刪除對單親遺傳算法進(jìn)行了改進(jìn)，并用于求解TDSP問題，取得了不錯(cuò)效果。文獻(xiàn)[6]將遺傳算法和蟻群算法相結(jié)合，對蟻群算法構(gòu)建的路徑進(jìn)行單點(diǎn)交叉，有效避免算法陷入停滯，提高了算法收斂效率。文獻(xiàn)[7]提出了一種改進(jìn)的蟻群算法，將交通流密度因子引入到信息素更新策略中，并對蟻群算法構(gòu)建的路徑進(jìn)行交叉處理，新算法能有效解決時(shí)間交通系統(tǒng)中的最短路徑問題。

但這些算法均未考慮節(jié)點(diǎn)的可等待約束，在軍事配送運(yùn)輸過程中，由于道路破壞、阻塞，車輛的運(yùn)輸時(shí)間是依時(shí)間變化的，即路阻函數(shù)是時(shí)間的函數(shù)。運(yùn)輸車輛在某個(gè)節(jié)點(diǎn)做適當(dāng)停留是允許的，并且很可能是必要的。因此研究節(jié)點(diǎn)可等待約束的TDSP對于戰(zhàn)時(shí)配送運(yùn)輸具有重要的指導(dǎo)和現(xiàn)實(shí)意義。

本文考慮節(jié)點(diǎn)等待約束的情況下，分層次優(yōu)化TDSP問題，內(nèi)層采用遺傳算法優(yōu)化每條可行路徑各節(jié)點(diǎn)離開時(shí)間，得到某條路徑的最短時(shí)間路徑；外層采用蟻群系統(tǒng)算法優(yōu)化路徑本身，最終得到最優(yōu)路徑方案。

1蟻群系統(tǒng)算法

蟻群系統(tǒng)算法是一種模擬螞蟻群體智能行為的群智能優(yōu)化算法，它具有優(yōu)良的分布式計(jì)算機(jī)制、魯棒性等優(yōu)點(diǎn)，并且易于與其他優(yōu)化方法相結(jié)合。為了說明蟻群系統(tǒng)算法，首先介紹旅行商問題(Traveling Salesman Problem, TSP)。

1.1旅行商問題

一般的，TSP問題可描述如下[8]：G={N,A}是一個(gè)帶權(quán)完全圖，其中N={1,2,…n}是n個(gè)城市的集合，A={(i,j)|i,j∈N}是所有邊的集合。每一條邊(i,j)∈A都分配一個(gè)權(quán)值dij，代表城市i與城市j之間的距離，其中i,j∈N。TSP的目標(biāo)是尋找圖中一條長度最短的哈密爾頓回路，即找出對N={1,2,…n}中n個(gè)城市訪問且只訪問一次的最短的一條封閉路徑。TSP問題可分為對稱型和非對稱型，在對稱TSP中，集合A的所有邊均滿足dij=dji；在非對稱TSP中，至少存在一條邊(i,j)，使得dij≠dji。

1.2蟻群系統(tǒng)算法

蟻群系統(tǒng)算法(Ant Colony System,ACS)是基于螞蟻系統(tǒng)(Ant System,AS)的改進(jìn)算法，其性能比AS有明顯的提高。改進(jìn)部分體現(xiàn)在3個(gè)方面：

第一，位于城市i的螞蟻k，根據(jù)偽隨機(jī)比例規(guī)則選擇城市j作為下一個(gè)訪問的城市。該規(guī)則由下式給出

(1)

第二，信息素的釋放動作只在至今最優(yōu)路徑的邊上執(zhí)行。更新信息素方式如下：

(2)

第三，螞蟻在構(gòu)建路徑時(shí)，每一次使用邊(i,j)，就會從該邊去掉一定量的信息素

(3)

式中，ε滿足0<ε<1;τ0是信息素量的初始值。改進(jìn)后的局部信息素更新方式，使得螞蟻每經(jīng)過邊(i,j)，該邊的信息素量τij將會減少，從而使得后續(xù)螞蟻選擇該邊的概率降低。也就是說，可以增加螞蟻探索其余路徑的可能性，增強(qiáng)算法開發(fā)的廣度，使得算法不陷入停滯狀態(tài)。同時(shí)，局部更新方式使得更新后的信息素量將在初始信息素量τ0和舊的信息素量之間，保證了該邊在下一次構(gòu)建路徑時(shí)仍然可能被選中。

2時(shí)變網(wǎng)絡(luò)數(shù)學(xué)模型

定義1[9]43G={V,E,F(t)}，其中V={1,2,…n}是有限節(jié)點(diǎn)集合，E={(i,j)|i≠j,i,j∈V}是邊的集合，F(xiàn)(t)={fij(t)|(i,j)∈E}為邊權(quán)函數(shù)的集合，其中fij(t)是時(shí)間t的函數(shù)，t∈[a,b],b>a≥0，則稱G為時(shí)變網(wǎng)絡(luò)TDN。a是所有結(jié)點(diǎn)的最早的允許出發(fā)時(shí)間，b是所有節(jié)點(diǎn)的最晚允許到達(dá)時(shí)間。

定義2[9]44在TDN中，設(shè)PS,D(a)表示從節(jié)點(diǎn)vS在a時(shí)刻出發(fā)到達(dá)節(jié)點(diǎn)vD的路徑，即：

為了方便表述，取起始節(jié)點(diǎn)vS為1，目標(biāo)節(jié)點(diǎn)vD為D。定義下列決策變量與符號：xij，0-1變量，取0表示邊(i,j)不在vS至vD的路徑中，取1表示邊(i,j)在vS至vD的路徑中；ai,表示當(dāng)P1,n(a)給定時(shí)，到達(dá)點(diǎn)i的時(shí)刻；bi，表示節(jié)點(diǎn)i的允許等待的最大時(shí)間；li，表示當(dāng)P1,n(a)給定時(shí)，離開點(diǎn)i的時(shí)刻。則TDSP問題的優(yōu)化數(shù)學(xué)模型如下：

min(Z(x,t))=

(4)

(5)

(6)

(7)

模型中：式(4)為目標(biāo)函數(shù)Z(·)；式(5)為1至n路徑合法性約束；式(6)為節(jié)點(diǎn)離開時(shí)間約束；式(7)為從1至n路徑中，節(jié)點(diǎn)i的到達(dá)時(shí)間約束。其中，a為節(jié)點(diǎn)1最早允許出發(fā)時(shí)刻。

3雙層智能優(yōu)化算法

模型中有2組變量xi,j和li需要優(yōu)化，因此本文采用分層的思想，外層利用蟻群系統(tǒng)算法優(yōu)化變量xi,j，構(gòu)建一條從起始節(jié)點(diǎn)1到目標(biāo)節(jié)點(diǎn)n的路徑；內(nèi)層利用遺傳算法優(yōu)化路徑中每個(gè)節(jié)點(diǎn)的最佳出發(fā)時(shí)間li，從而找到最短時(shí)路徑。

3.1ACS算法構(gòu)建路徑

ACS算法優(yōu)化路徑步驟如下：

1) 按如下公式初始化每條邊上的信息素量

式中，n表示為節(jié)點(diǎn)規(guī)模；Cnn是任意一條從起始點(diǎn)1到終點(diǎn)D的路徑的時(shí)間長度。同時(shí)設(shè)置算法迭代次數(shù)。

2) 將m只螞蟻放在起始點(diǎn)1。

3) 根據(jù)式(1)選擇下一個(gè)訪問節(jié)點(diǎn)j，啟發(fā)式信息ηij=1/fij(li)，fij(li)為螞蟻在li時(shí)刻由節(jié)點(diǎn)i到節(jié)點(diǎn)j所經(jīng)歷的時(shí)間。按照式(3)更新該邊上的信息素。

5) 當(dāng)m只螞蟻構(gòu)建完路徑后，按照式(2)更新至今最優(yōu)路徑上的信息素。

6) 達(dá)到了給定的迭代次數(shù)，則停止；否則轉(zhuǎn)步驟2)。

3.2遺傳算法優(yōu)化內(nèi)層函數(shù)

內(nèi)層函數(shù)需優(yōu)化節(jié)點(diǎn)i的最優(yōu)離開時(shí)刻li，使得對應(yīng)路徑的走行時(shí)間最短。依據(jù)內(nèi)層函數(shù)的優(yōu)化目標(biāo)和約束條件，可建立以下優(yōu)化模型[10]33：

(8)

假設(shè)已得到一條路徑P1,n(a)={1,2,3,…n}，顯然，l1∈[a1,a1+b1]，令l1=y1，則必有l(wèi)2∈[a2,a2+b2]，其中a2=y1+f1,2(y1)。

同理可推得l3∈[a3,a3+b3]，其中,a3=y2+f2,3(y2)……

因此，可設(shè)計(jì)內(nèi)層遺傳算法[10]33-34：

1) 編碼及初始化種群。生產(chǎn)均勻隨機(jī)變量y1∈[a1,a1+b1]，令l1=y1，得到：a2=y1+f1,2(y1)；生產(chǎn)均勻隨機(jī)變量y2∈[a2,a2+b2]，令l2=y2，得到：a3=y2+f2,3(y2)……

3) 選擇操作。根據(jù)每條路徑的適應(yīng)度fit(i)，采用輪盤賭的方式從父代染色體中選擇nSize個(gè)染色體作為子代。

4) 交叉操作。按交叉概率Pc選定要進(jìn)行交叉操作的染色體，并依適應(yīng)度大小降序排列，按照首尾對折的方法選擇2個(gè)染色體進(jìn)行交叉操作。假定染色體l1和l2被選中，隨機(jī)均勻生成整數(shù)i∈[1,m)，m表示路徑P1,n(a)包含的節(jié)點(diǎn)數(shù)，i表示交叉位置。交換l1和l2中第i個(gè)基因位，分別檢查l1和l2的可行性，并進(jìn)行修補(bǔ)操作。

(1) 若li滿足：ai≤li≤ai+bi，i∈V，則轉(zhuǎn)步驟(2)；否則轉(zhuǎn)步驟(4)；

(2) 若i=m，則轉(zhuǎn)到步驟(5)，否則i=i+1，計(jì)算ai=li-1+fi-1,i(li-1)；

(3) 若li滿足：ai≤li≤ai+bi，i∈V，則轉(zhuǎn)步驟(5)；

(4) 生成隨機(jī)變量y∈[ai,ai+bi]，令li=y，轉(zhuǎn)步驟(2)；

(5) 染色體可行，停止操作。

5) 變異操作。按交叉概率Pm確定出需要進(jìn)行變異操作的染色體，生成均勻隨機(jī)整數(shù)i∈[1,m]，i表示變異位。

(1) 生成隨機(jī)變量y∈[ai,ai+bi]，令li=y。

(2) 若i=m，則轉(zhuǎn)步驟(4)；否則檢查染色體的可行性，i=i+1，計(jì)算：ai=li-1+fi-1,i(li)。

(3) 若li滿足：ai≤li≤ai+bi，i∈V，則轉(zhuǎn)步驟(4)；否則轉(zhuǎn)步驟(1)；

(4) 染色體可行，停止操作。

3.3雙層智能優(yōu)化算法

將外層優(yōu)化路徑的蟻群系統(tǒng)算法和內(nèi)層優(yōu)化節(jié)點(diǎn)離開時(shí)間的遺傳算法結(jié)合起來，可形成求解TDSP的雙層智能優(yōu)化算法。算法主要步驟如下：

1) 初始化每條邊上的信息素，同時(shí)設(shè)置迭代次數(shù)。

2) 將m只螞蟻放在起始點(diǎn)1。

3) 按照式(1)計(jì)算螞蟻轉(zhuǎn)移概率，并選擇下一個(gè)節(jié)點(diǎn)j，更新該邊的信息素。

(1) 隨機(jī)產(chǎn)生nSize個(gè)染色體作為初始種群。

(2) 交叉操作。

(3) 變異操作。

(4) 計(jì)算染色體評價(jià)函數(shù)。

(5) 選擇操作。

5) 當(dāng)m只螞蟻搜索完后，求得m條路徑和對應(yīng)路徑時(shí)間長度Tk(k=1,2,…,m)，按照式(2)更新信息素。

6) 更新當(dāng)前的最短時(shí)間路徑和對應(yīng)的最短時(shí)間。

7) 達(dá)到了給定的迭代次數(shù)，則算法停止；否則轉(zhuǎn)步驟2)。

4算例分析

設(shè)某一地域有27個(gè)交通節(jié)點(diǎn)(如圖1)，各交通節(jié)點(diǎn)之間的通行成本為時(shí)間的函數(shù)(見表1)。某保障分隊(duì)以摩托化開進(jìn)方式從駐地1出發(fā)，目的地為節(jié)點(diǎn)27，最早開進(jìn)時(shí)間為a1=0。求保障分隊(duì)的最優(yōu)開進(jìn)方案(路途中所耗時(shí)間最少，含節(jié)點(diǎn)等待時(shí)間)。

圖1　時(shí)變網(wǎng)絡(luò)示意圖

頂點(diǎn)ibi弧fij(t)頂點(diǎn)ibi弧fij(t)151,21,31,41,51,63+te-t2t+3e-4t5+2e-t23+2te-3t24+(3-t)2232,72,86+(2-3t)23t+6e-t2323,23,43,82+3e-t254+(1-t/3)2434,54,96-3e-2t24505,95,103+(3-2t)22+2e-12)t2616,56,1166+(5-t)2737,127,132t+2e-t210808,78,98,1346+(7-t)211929,109,139,149,1558-2e-t29-3e-(t-2)26+(10-t)2/810310,1110,1510,163+2e-t24+(12-t)2/10611011,165+3e-2t212112,1312,1745+2e-t213213,1413,1713,1826+3e-2t27+2e-2t214114,1814,1914,203+(14-t)2/1065+3e-t15215,1415,2015,213+2e-(10-t)235-2e-3t216316,1516,218-3e-(7-t)2517117,1817,223+3e-(6-t)24-2e-t218218,2218,2318,246+3e-2t285+(18-t)2/1019219,1819,2419,259-3e-(20-t)212-3e-(16-t)210+2e-t220120,1920,2120,253+5e-2t25+2e-t23+4e-3t221221,2521,263+(20-t)2/54+(18-t)2/822222,2322,276-3e-(2+t)27+2e-t223123,2423,278+(25-t)2/66+(23-t)2/824224,2524,275+(24-t)2/64+(26-t)2/725325,2625,276+2e-3t20.18+4e-(3+t)226226,2710+3e-4(4-t)2

蟻群系統(tǒng)算法相關(guān)參數(shù)為：螞蟻數(shù)為10，迭代次數(shù)為100次，α,β,ρ和ε分別取1，2，0.1和0.1。遺傳算法相關(guān)參數(shù)為：種群大小為30，Pc=0.8，Pm=0.05，迭代次數(shù)為100次。實(shí)驗(yàn)采用Matlab 2010b編程，運(yùn)行環(huán)境為：Window XP sp2，intel Core i3-2100 CPU 3.10 GHZ，DDR3 1333 MHZ 2 GB PC。

4.1雙層智能優(yōu)化算法優(yōu)化過程

利用雙層智能優(yōu)化算法進(jìn)行實(shí)驗(yàn)，最短路徑的進(jìn)化過程如圖2所示，當(dāng)?shù)?7代時(shí)，問題收斂于19.77 min。當(dāng)算法取得最短時(shí)路徑時(shí)，的進(jìn)化過程如圖3所示，當(dāng)?shù)?6代，問題收斂。最短時(shí)路徑為：1→5→10→15→20→25→27，開進(jìn)方案如表2所示。

圖2　最短路徑進(jìn)化過程

圖3　最短路徑時(shí)間li的進(jìn)化過程

min

從最優(yōu)開進(jìn)方案來看，在起始點(diǎn)1等待1.75 min出發(fā)是最佳出發(fā)時(shí)刻，到達(dá)節(jié)點(diǎn)5立刻出發(fā)，在節(jié)點(diǎn)10等待0.59 min，在節(jié)點(diǎn)15等待0.02 min，在節(jié)點(diǎn)20等待0.03 min，在節(jié)點(diǎn)25等待0.03 min，最后到達(dá)終點(diǎn)27，總花費(fèi)時(shí)間為19.77 min。與文獻(xiàn)[10]的最優(yōu)開進(jìn)方案時(shí)間25.12 min相比，有較大提高。

4.2與文獻(xiàn)[10]中算法比較

選取文獻(xiàn)[10]33-35的雙層智能優(yōu)化算法(GA-GA)與本文算法(ACS-GA)做對比測試，算法分別獨(dú)立運(yùn)行20次，實(shí)驗(yàn)結(jié)果如表3所示。其中，LBest是最短時(shí)路徑長度；LWorst是最長時(shí)路徑長度；μ和σ分別表示運(yùn)行20次得到解的平均長度和標(biāo)準(zhǔn)偏差；T為算法的平均收斂時(shí)間。

表3中的最短時(shí)路徑長度、平均長度體現(xiàn)本文算法的收斂精度和尋優(yōu)能力優(yōu)于GA-GA算法；最長時(shí)路徑長度、標(biāo)準(zhǔn)偏差體現(xiàn)了本文算法的魯棒性和對抗局部極值的能力強(qiáng)于GA-GA算法；結(jié)合平均收斂時(shí)間，表明本文算法收斂效率優(yōu)于GA-GA算法。

表3　2種算法總體性能的比較

5結(jié) 束 語

本文針對邊成本為一般函數(shù)和節(jié)點(diǎn)存在可等待約束的TDSP問題，提出了一種雙層智能優(yōu)化算法。選取了包含27個(gè)節(jié)點(diǎn)的時(shí)變網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文算法能夠快速找到最短時(shí)間路徑方案。與同類算法的比較試驗(yàn)表明，本文算法收斂精度和尋優(yōu)能力更優(yōu)，魯棒性和對抗局部極值的能力更強(qiáng)。在配送運(yùn)輸網(wǎng)絡(luò)中，邊權(quán)不僅僅是時(shí)間的函數(shù)，還可能同時(shí)是隨機(jī)變量，也就是說時(shí)變網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)共同存在，求解這類問題，是下一步研究的重點(diǎn)內(nèi)容。

參考文獻(xiàn)(References)

[1]HALL R W.The fastest path through a network with random time dependent travel time[J].Transportation Science，1986，20(3)：182-188.

[2]譚國真，高文.時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(2)：165-172.

[3]何俊，戴浩，宋自林，等.時(shí)間依賴的交通網(wǎng)絡(luò)模型及最短路徑算法[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005，6(6)：541-544.

[4]韓平陽，羅五明，王志敏，等.動態(tài)網(wǎng)絡(luò)中的最短路徑改進(jìn)算法[J].軍事運(yùn)籌與系統(tǒng)工程，2007，21(1)：46-50.

[5]劉堅(jiān)強(qiáng)，劉粉明.動態(tài)網(wǎng)絡(luò)最佳路徑的遺傳算法求解[J].信息工程大學(xué)學(xué)報(bào)，2004，5(3)：14-18.

[6]劉永強(qiáng)，常青，熊華鋼.改進(jìn)蟻群算法求解時(shí)變網(wǎng)絡(luò)中最短路徑問題[J].北京航空航天大學(xué)學(xué)報(bào)，2009，35(10)，1245-1248.

[7]薛國新，王岳.一種改進(jìn)的蟻群算法求解出來的最短路徑問題[J].常州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，24(1)，78-81.

[8]王學(xué)超，孔月萍，董麗麗，等.智能優(yōu)化算法與應(yīng)用[M].西安：西北大學(xué)出版社，2012：164-165.

[9]李引珍．不確定環(huán)境下交通運(yùn)輸網(wǎng)絡(luò)路徑求解方法及應(yīng)用研究[D]．成都：西南交通大學(xué)，2005：43-44.

[10]何瑞春，李引珍.時(shí)間依賴網(wǎng)絡(luò)路徑模型及雙層優(yōu)化智能算法研究[J].鐵道學(xué)報(bào)，2008，30(1)：32-37.

(編輯：李江濤)

中圖分類號TP301

文章編號2095-3828(2016)01-0122-06

文獻(xiàn)標(biāo)志碼A DOI10.3783/j.issn.2095-3828.2016.01.025

作者簡介陳亮(1981-)，男，講師，主要研究方向?yàn)橹悄軆?yōu)化。chenbb0708@163.com

基金項(xiàng)目國家社會科學(xué)基金資助項(xiàng)目(13GJ003-069)

收稿日期2015-01-08

盧厚清，男，教授，博士生導(dǎo)師。