雙層智能優化算法求解時變網絡最短路徑問題

陳　亮，　盧厚清

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

?

雙層智能優化算法求解時變網絡最短路徑問題

陳亮1，盧厚清2

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

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

關鍵詞時變網絡；最短路徑；雙層優化；智能優化算法

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

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

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

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

本文考慮節點等待約束的情況下，分層次優化TDSP問題，內層采用遺傳算法優化每條可行路徑各節點離開時間，得到某條路徑的最短時間路徑；外層采用蟻群系統算法優化路徑本身，最終得到最優路徑方案。

1蟻群系統算法

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

1.1旅行商問題

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

1.2蟻群系統算法

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

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

(1)

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

(2)

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

(3)

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

2時變網絡數學模型

定義1[9]43G={V,E,F(t)}，其中V={1,2,…n}是有限節點集合，E={(i,j)|i≠j,i,j∈V}是邊的集合，F(t)={fij(t)|(i,j)∈E}為邊權函數的集合，其中fij(t)是時間t的函數，t∈[a,b],b>a≥0，則稱G為時變網絡TDN。a是所有結點的最早的允許出發時間，b是所有節點的最晚允許到達時間。

定義2[9]44在TDN中，設PS,D(a)表示從節點vS在a時刻出發到達節點vD的路徑，即：

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

min(Z(x,t))=

(4)

(5)

(6)

(7)

模型中：式(4)為目標函數Z(·)；式(5)為1至n路徑合法性約束；式(6)為節點離開時間約束；式(7)為從1至n路徑中，節點i的到達時間約束。其中，a為節點1最早允許出發時刻。

3雙層智能優化算法

模型中有2組變量xi,j和li需要優化，因此本文采用分層的思想，外層利用蟻群系統算法優化變量xi,j，構建一條從起始節點1到目標節點n的路徑；內層利用遺傳算法優化路徑中每個節點的最佳出發時間li，從而找到最短時路徑。

3.1ACS算法構建路徑

ACS算法優化路徑步驟如下：

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

式中，n表示為節點規模；Cnn是任意一條從起始點1到終點D的路徑的時間長度。同時設置算法迭代次數。

2) 將m只螞蟻放在起始點1。

3) 根據式(1)選擇下一個訪問節點j，啟發式信息ηij=1/fij(li)，fij(li)為螞蟻在li時刻由節點i到節點j所經歷的時間。按照式(3)更新該邊上的信息素。

5) 當m只螞蟻構建完路徑后，按照式(2)更新至今最優路徑上的信息素。

6) 達到了給定的迭代次數，則停止；否則轉步驟2)。

3.2遺傳算法優化內層函數

內層函數需優化節點i的最優離開時刻li，使得對應路徑的走行時間最短。依據內層函數的優化目標和約束條件，可建立以下優化模型[10]33：

(8)

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

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

因此，可設計內層遺傳算法[10]33-34：

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3雙層智能優化算法

將外層優化路徑的蟻群系統算法和內層優化節點離開時間的遺傳算法結合起來，可形成求解TDSP的雙層智能優化算法。算法主要步驟如下：

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

2) 將m只螞蟻放在起始點1。

3) 按照式(1)計算螞蟻轉移概率，并選擇下一個節點j，更新該邊的信息素。

(1) 隨機產生nSize個染色體作為初始種群。

(2) 交叉操作。

(3) 變異操作。

(4) 計算染色體評價函數。

(5) 選擇操作。

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

6) 更新當前的最短時間路徑和對應的最短時間。

7) 達到了給定的迭代次數，則算法停止；否則轉步驟2)。

4算例分析

設某一地域有27個交通節點(如圖1)，各交通節點之間的通行成本為時間的函數(見表1)。某保障分隊以摩托化開進方式從駐地1出發，目的地為節點27，最早開進時間為a1=0。求保障分隊的最優開進方案(路途中所耗時間最少，含節點等待時間)。

圖1　時變網絡示意圖

頂點ibi弧fij(t)頂點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

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

4.1雙層智能優化算法優化過程

利用雙層智能優化算法進行實驗，最短路徑的進化過程如圖2所示，當迭代到87代時，問題收斂于19.77 min。當算法取得最短時路徑時，的進化過程如圖3所示，當迭代到56代，問題收斂。最短時路徑為：1→5→10→15→20→25→27，開進方案如表2所示。

圖2　最短路徑進化過程

圖3　最短路徑時間li的進化過程

min

從最優開進方案來看，在起始點1等待1.75 min出發是最佳出發時刻，到達節點5立刻出發，在節點10等待0.59 min，在節點15等待0.02 min，在節點20等待0.03 min，在節點25等待0.03 min，最后到達終點27，總花費時間為19.77 min。與文獻[10]的最優開進方案時間25.12 min相比，有較大提高。

4.2與文獻[10]中算法比較

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

表3中的最短時路徑長度、平均長度體現本文算法的收斂精度和尋優能力優于GA-GA算法；最長時路徑長度、標準偏差體現了本文算法的魯棒性和對抗局部極值的能力強于GA-GA算法；結合平均收斂時間，表明本文算法收斂效率優于GA-GA算法。

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

5結 束 語

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

參考文獻(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]譚國真，高文.時間依賴的網絡中最小時間路徑算法[J].計算機學報，2002，25(2)：165-172.

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

[4]韓平陽，羅五明，王志敏，等.動態網絡中的最短路徑改進算法[J].軍事運籌與系統工程，2007，21(1)：46-50.

[5]劉堅強，劉粉明.動態網絡最佳路徑的遺傳算法求解[J].信息工程大學學報，2004，5(3)：14-18.

[6]劉永強，常青，熊華鋼.改進蟻群算法求解時變網絡中最短路徑問題[J].北京航空航天大學學報，2009，35(10)，1245-1248.

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

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

[9]李引珍．不確定環境下交通運輸網絡路徑求解方法及應用研究[D]．成都：西南交通大學，2005：43-44.

[10]何瑞春，李引珍.時間依賴網絡路徑模型及雙層優化智能算法研究[J].鐵道學報，2008，30(1)：32-37.

(編輯：李江濤)

中圖分類號TP301

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

文獻標志碼A DOI10.3783/j.issn.2095-3828.2016.01.025

作者簡介陳亮(1981-)，男，講師，主要研究方向為智能優化。chenbb0708@163.com

基金項目國家社會科學基金資助項目(13GJ003-069)

收稿日期2015-01-08

盧厚清，男，教授，博士生導師。