求解動態(tài)最優(yōu)路徑的混合優(yōu)化算法.doc

第7期王江晴等：求解動態(tài)最優(yōu)路徑的混合優(yōu)化算法141求解動態(tài)最優(yōu)路徑的混合優(yōu)化算法王江晴, 覃俊, 李子茂(中南民族大學 計算機科學學院，湖北 武漢 430074)摘 要：對動態(tài)網(wǎng)絡環(huán)境下動態(tài)需求的最優(yōu)路徑搜索問題進行了研究，首次提出了一個能同時利用演化算法的全局優(yōu)化能力和蟻群算法的局部探索能力的混合智能優(yōu)化算法Evo-Ant，并將其應用于DVRP。為了驗證算法的有效性，給出了DVRP的混合整數(shù)規(guī)劃模型，建立了DVRP的動態(tài)性能測試類，并進行了大量的仿真實驗和比較。結果表明，Evo-Ant算法能夠根據(jù)實時接收到的信息對當前規(guī)劃路徑進行及時調(diào)整，具有明顯改善的性能優(yōu)勢。關鍵詞：動態(tài)網(wǎng)絡；路由問題；演化算法；蟻群算法中圖分類號：TP301.6 文獻標識碼：A 文章編號：1000-436X(2008)07-0135-06Hybrid optimization algorithm for routing problem in dynamic networksWANG Jiang-qing, QIN Jun, LI Zi-mao(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)Abstract: A routing problem was investigated where both dynamic network environment and real-time customer requests were considered, a hybrid optimization algorithm called Evo-Ant was proposed. The advantage of the algorithm is that it incorporates ant colony algorithm for exploration and evolutionary algorithm for exploitation, and uses real-time information during the optimization process. In order to discuss the performance of the proposed algorithm, a mixed integral programming model for dynamic vehicle routing problem was formulated, and benchmark functions were constructed. The performance of the algorithm is evaluated by comparing its results with some exact algorithms and heuristic algorithms for randomly generated test problems. The results show that the proposed algorithm can achieve a higher performance gain, and is well suited to problems containing dynamic network environment and real-time customer requests.Key words: dynamic network; routing problem; evolutionary algorithm; ant colony algorithm1 引言收稿日期：2008-01-07；修回日期：2008-06-02基金項目：國家自然科學基金資助項目（60603008）Foundation Item: The National Natural Science Foundation of China (60603008)最優(yōu)路徑搜索主要研究如何在網(wǎng)絡中尋找能夠同時滿足多個約束條件，且具有最小代價的路徑。這類問題在QoS路由、車輛調(diào)度等領域中有著廣泛的應用。在實際的網(wǎng)絡中，最優(yōu)路徑搜索問題分為2種：基于靜態(tài)信息的路徑搜索和基于動態(tài)信息的路徑搜索1。由于更加貼近實際應用的需求，近年來對動態(tài)問題的研究引起了計算機等領域?qū)＜覍W者的廣泛關注24。動態(tài)最優(yōu)路徑問題屬于NP完全問題，目前一般采用現(xiàn)代啟發(fā)式算法求解，如演化算法57和蟻群算法810等。演化算法從模擬自然界的生物演化過程入手，以解決智能系統(tǒng)如何從環(huán)境中進行學習的問題。演化算法的特點是具有隱含并行性，擅長求解全局最優(yōu)問題，但算法的局部搜索能力較差，求解精確度較低。蟻群算法也是一種源于自然界的仿生類算法，它模擬昆蟲王國中螞蟻的行為機制，是一種依照螞蟻覓食原理設計而成的群集智能搜索算法。蟻群算法的特點是具有分布式計算特性，局部探索能力很強，但當問題規(guī)模較大時，算法效率下降得很快，且不能對解空間進行全面的搜索。本文將演化算法和蟻群算法相融合，提出了一個能滿足實際需求的、尋優(yōu)能力強的基于動態(tài)信息的最優(yōu)路徑搜索算法Evo-Ant（evolutionary ant colony algorithm）。該算法充分利用了演化算法的全局性和蟻群算法的局部性，采用演化算法對蟻群算法的信息素矩陣進行編碼和優(yōu)化，擴大了算法對解空間的搜索，提高了蟻群算法找到全局最優(yōu)解的速度。文中將該算法應用于最優(yōu)路徑搜索的典型實例動態(tài)車輛路徑問題（DVRP, dynamic vehicle routing problem），仿真結果顯示了算法的有效性。本文各節(jié)的內(nèi)容安排如下：第2節(jié)給出了DVRP的混合整數(shù)規(guī)劃模型，第3節(jié)提出了Evo-Ant算法，第4節(jié)討論了算法實現(xiàn)過程中的若干關鍵技術，第5節(jié)給出了仿真實驗結果及分析，第6節(jié)為本文的結束語。2 DVRP建模本文考慮動態(tài)環(huán)境下動態(tài)需求的DVRP：在工作日的開始時間完成首次車輛路徑的安排，其任務集合包括前一天未完成的客戶需求以及當天已知的客戶需求，每一客戶需求包括以下信息：需求種類（配送/收集）、給定的貨物量、時間窗以及服務時間長度等；隨后的客戶需求實時到來；車輛的行駛線路是從車場出發(fā)再回到車場；任意兩點間的距離和道路條件是已知的，但行駛時間未知；目標是在滿足給定約束條件的情況下使得總代價最小。2.1 有關符號的定義T：整個工作日劃分的區(qū)段數(shù)，對應的調(diào)度時刻分別為T0 , TT；V：整個工作日涉及到的所有客戶，包括車場（用0表示）、靜態(tài)需求客戶、動態(tài)需求客戶；(cij)：V中所有客戶組成的全互連完全圖的距離矩陣；：在調(diào)度時刻邊i, j的單位公里行駛時間；wi：車輛早于客戶i時間窗下界到達時車輛的等待時間；di：車輛晚于客戶i時間窗上界到達時客戶的等待時間；：系數(shù)，由使用一輛車的成本決定；：系數(shù)，由盈利水平、汽車單位時間所消耗的燃油價格決定；：系數(shù)，反映車輛等待客戶而造成損失的程度；：系數(shù)，反映客戶等待車輛而造成損失的程度。2.2 模型的建立從全局靜態(tài)和局部動態(tài)的角度建立動態(tài)車輛調(diào)度模型：1）假設整個調(diào)度階段0，T系統(tǒng)的信息全部已知，建立系統(tǒng)的混合整數(shù)規(guī)劃模型；2）對于某一給定的調(diào)度時刻Tt，建立對應的動態(tài)環(huán)境下的狀態(tài)轉(zhuǎn)換模型。目標函數(shù)包括最小化車輛數(shù)、最小化車輛行駛時間、最小化車輛在客戶處的等待時間、最小化客戶等待時間，并采用加權法合成一個代價。DVRP的混合整數(shù)規(guī)劃模型如下：車輛數(shù)量：(1)車輛行駛時間：(2)車輛在客戶處的等待時間：(3)客戶等待時間：(4)目標函數(shù)：=min(=min(+)(5)3 算法設計本文提出的Evo-Ant充分利用了演化算法的全局性和蟻群算法的局部性，用蟻群算法對路徑進行實時規(guī)劃，用演化算法對蟻群算法的信息素矩陣進行優(yōu)化以加快其收斂速度，實現(xiàn)了二者的有機結合。為了提高對隨機事件和突發(fā)事件進行實時處理的能力，算法根據(jù)網(wǎng)絡條件和實時獲得的網(wǎng)絡狀態(tài)信息，采用動態(tài)評估模型對網(wǎng)絡中各節(jié)點之間的連接情況進行實時評估，并利用改進的Dijkstra雙桶算法11計算各節(jié)點之間的實時最短路徑。算法流程如下：Step 1 初始化設置Evo-Ant算法的最大迭代次數(shù)AImax；設置蟻群算法的迭代次數(shù)AI和種群規(guī)模AM；設置演化算法的迭代次數(shù)EI和種群規(guī)模EM；設置其他相關參數(shù)。Step 2 生成信息素矩陣利用演化算法迭代EI次生成初始信息素矩陣，個體的評價利用蟻群算法完成，并選取種群中最優(yōu)的螞蟻對應的目標函數(shù)值作為評價依據(jù)。Step 3 若不滿足停機條件，重復以下工作：利用蟻群算法迭代AI次，并在每一次迭代完成后更新信息素矩陣。利用演化算法迭代EI次，對信息素矩陣進行優(yōu)化。Step 4 由最優(yōu)信息素矩陣生成可行解。4 關鍵技術研究對Evo-Ant算法進行分析可知，算法可以找到的最佳路徑由當前的信息素矩陣決定。為了提高執(zhí)行速度和解的質(zhì)量，本算法對信息素矩陣的操作分2階段進行：1）在蟻群算法的迭代過程中，利用蟻群算法的局部探索能力對信息素矩陣進行更新；2）在蟻群算法結束以后，利用演化算法的全局尋優(yōu)能力對信息素矩陣進行優(yōu)化。4.1 信息素矩陣更新方法信息素矩陣的更新采用全局更新法。更新規(guī)則如下(6)其中，為信息素揮發(fā)因子，m為螞蟻數(shù)量，Q為設定的常量，Lk為螞蟻k的目標函數(shù)值，為螞蟻k在邊i，j的信息增量，如果該螞蟻沒有經(jīng)過邊i，j，則。4.2 信息素矩陣優(yōu)化方法信息素矩陣的優(yōu)化由演化算法完成。算法如下：Step 1 以當前的信息素矩陣為一個個體，然后隨機生成EM-1個個體，CurGen=0；Step 2 評價每一個隨機生成的個體；Step 3 while CurGenEI do進行選擇操作，選出EM個父體；進行交叉操作，對每個后代進行評價；進行變異操作，對每個后代進行評價；將父子2代按適應值排名取前EM個構成新種群；CurGen =CurGen+1；Step 4 返回最好個體所對應的信息素矩陣。4.3 由信息素矩陣生成可行解某一時刻Tt的系統(tǒng)狀態(tài)如圖1所示。圖中灰色節(jié)點表示收集型的客戶需求，白色節(jié)點表示配送型的客戶需求，未連線的點表示新的客戶需求，虛線表示已訪問的路徑，實線表示相應車輛前一時刻的規(guī)劃路徑。圖中至少要用3只子螞蟻（對應3輛車）來完成路徑的規(guī)劃。算法中，每只螞蟻（代表一個可行解）由多個子螞蟻構成，而每只子螞蟻對應于一輛車走過的路徑。對每只子螞蟻，將圖中的節(jié)點分為2類：一類是必須爬過的節(jié)點，用1表示；一類是可以爬過的節(jié)點，用2表示。從2中隨機選取若干個節(jié)點和1組成，這樣問題就轉(zhuǎn)換成了由中的節(jié)點、該子螞蟻的起始節(jié)點以及車場構成的一個TSP問題。每只子螞蟻從起始節(jié)點開始，按照給定的轉(zhuǎn)移概率在集合中選擇下一節(jié)點，直至走完所有的節(jié)點。對于剩下的節(jié)點，可以引入一只新的子螞蟻來完成路徑的規(guī)劃。螞蟻的轉(zhuǎn)移概率如下(7)5 仿真實驗由于國內(nèi)外對于DVRP沒有一個通用的benchmark，為了驗證Evo-Ant算法的性能，本文結合實際問題的需要，采用作者所設計的DVRP通用仿真器DVRPSim12及實驗數(shù)據(jù)進行仿真實驗。在實驗中，隨機網(wǎng)絡圖生成算法在矩形區(qū)域0,5000,500中隨機生成100個節(jié)點的交通網(wǎng)絡圖，平均節(jié)點度為4，公路類型為3（高速公路、國道和省級公路）。每個客戶的時間窗在2,10按一致性均勻分布隨機生成，每一個客戶的服務時間按均值0.3、方差0.2的正態(tài)分布隨機生成。每一個動態(tài)客戶到達的時刻按指數(shù)分布生成。目標函數(shù)中的系數(shù)固定為：=20， =2， =3，=3。圖1 螞蟻爬過的路徑5.1 動態(tài)性能測試類動態(tài)性能指標分類如下：1) 客戶需求：R=R1，R2，R3，R1表示客戶需求變化較慢；R2表示客戶需求變化適中；R3表示客戶需求變化快。2) 路況：D=D1，D2，D3，D1表示從交通網(wǎng)絡圖中的所有路徑中選取10%的路徑使其路況發(fā)生變化；D2表示選取30%的路徑使其路況發(fā)生變化；D3表示選取50%的路徑使其路況發(fā)生變化。3) 問題規(guī)模：S=S1，S2，S3，S1表示初始客戶數(shù)量在510之間，動態(tài)生成的客戶均值在12之間；S2表示初始客戶數(shù)量在1020之間，動態(tài)生成的客戶均值為3；S3表示初始客戶數(shù)量在2030之間，動態(tài)生成的客戶均值為4。對于測試實例(R1,D3,(S2)16)，表示客戶動態(tài)需求屬于類別1、路況變化程度屬于類別3、問題規(guī)模屬于類別2、初始客戶數(shù)為16。5.2 實驗結果動態(tài)車輛調(diào)度系統(tǒng)的工作流程如下：客戶通過網(wǎng)絡、電話等方式實時地向調(diào)度中心（即車場）提出需求信息；調(diào)度中心通過車載電話、手機、GPS衛(wèi)星定位系統(tǒng)等實時了解車隊中每一輛車的方位及交通情況，計算各客戶之間的實際行駛時間及最短路徑；調(diào)用Evo-Ant進行實時的路徑規(guī)劃；輸出規(guī)劃結果并向車輛下達調(diào)度指令。為了驗證Evo-Ant的性能，本文將Evo-Ant與分支定界法（B-B）和C-W算法進行比較。對于分支定界法，利用第2節(jié)建立的混合整數(shù)規(guī)劃模型求出問題的精確解；對于C-W算法，將其稍作調(diào)整用于求解DVRP，即對于新到達的收集型需求采用最小代價的方法插入到已有路徑中，對于不能插入的收集型需求和配送型的新需求則重新派出車輛，其路徑生成同樣采用最小代價的方法。由于分支定界法屬于精確算法，只能求解小規(guī)模問題，因此僅用其求解(R1,Dx,Sy)類問題，其中x=1, 2, 3, y=1, 2。算法參數(shù)設置如下：AImax=100，AI=EI=5，AM=EM=10，蟻群算法的轉(zhuǎn)移概率參數(shù)為：=1，=3，信息素揮發(fā)因子=0.8，最小信息素的值min=0.001，Q=10。演化算法的雜交率為pc=0.5，變異率為pm=0.1。從實驗結果中隨機挑選幾組數(shù)據(jù)，如表1表3所示。表1 小規(guī)模輕度動態(tài)需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R1,D1,(S1)5)=1車輛數(shù)444路徑代價2 7082 6872 799車輛等待代價453051客戶等待代價373643總代價5 7425 6525 960計算時間60.002392.15342.996表2 中等規(guī)模中度動態(tài)需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R1,D3,(S2)13)=3車輛數(shù)656路徑代價3 2003 1663 482車輛等待代價272169客戶等待代價221944總代價6 6676 5527 423計算時間80.1321 996.98380.085表3 大規(guī)模重度動態(tài)需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R3,D3,(S3)30)=4車輛數(shù)89路徑代價5 8975 988車輛等待代價73109客戶等待代價8477總代價12 42512 714計算時間155.986155.2315.3 算法分析從表1表3中可以看出，分支定界法找到的解的質(zhì)量最好，但從計算時間來看，其計算開銷遠大于Evo-Ant，不能滿足實時系統(tǒng)的需求；C-W與Evo-Ant的時間開銷比較接近，但對于每一種測試問題，Evo-Ant的計算結果均優(yōu)于C-W。對于一個給定的動態(tài)環(huán)境下動態(tài)需求的DVRP，Evo-Ant在執(zhí)行速度和解的質(zhì)量上均能很好地滿足實時車輛路徑調(diào)度系統(tǒng)的需求。用Xk表示Evo-Ant第k次迭代時的狀態(tài)。由算法的迭代過程可知，k+1時刻的狀態(tài)Xk+1取決于Xk，與以前的狀態(tài)無關。用一個齊時馬氏鏈描述整個迭代過程，Evo-Ant伴隨的馬氏過程收斂到問題的最優(yōu)解。5.4 基于GIS數(shù)據(jù)的實例考慮一個實際的應用問題：初始調(diào)度時系統(tǒng)有15個客戶需求（0為調(diào)度中心），客戶分布如圖2所示。圖2 初始調(diào)度時客戶需求分布第一次調(diào)度時所有路段交通暢通，此時需3輛車完成任務：0-13-8-14-6-12-11-5-10-1-00-4-7-9-2-00-3-15-0第二次調(diào)度時在客戶10和客戶4之間的路段發(fā)生了嚴重交通阻塞，短期內(nèi)不可能緩解，所以調(diào)度算法重新規(guī)劃路徑，繞開了堵車路段：0-13-8-14-6-12-11-10-5-1-00-4-7-9-2-00-3-15-0實驗結果表明，算法能夠根據(jù)交通信息的變化及時調(diào)整車輛的行駛路徑，避開堵車路段，并能實時選取最優(yōu)路徑，從而為決策者提供快速的決策方案。6 結束語針對動態(tài)網(wǎng)絡的最優(yōu)路徑搜索問題，本文提出了一個新的混合優(yōu)化算法Evo-Ant。該算法在充分利用演化算法的全局優(yōu)化能力的同時，又利用了蟻群算法的局部探索能力，能夠獲得更好的執(zhí)行效果。大量仿真實驗表明，對于動態(tài)環(huán)境下動態(tài)需求的最優(yōu)路徑搜索問題，Evo-Ant能有效地找到實時的最佳規(guī)劃路徑，具有明顯改善的性能增益。這對于提高網(wǎng)絡效率、改善服務質(zhì)量、緩解交通擁擠狀況等有著重要的意義。該算法也可應用于其他具有動態(tài)因素的行業(yè)和領域，如郵政投遞、鐵路和飛機的調(diào)度、通信工程以及超大規(guī)模集成電路的設計等。參考文獻：1GAVOILLE C. Technical columns: routing in distributed networks: overview and open problemsJ. ACM SIGACT News, 2001, 32(1): 36-52.2LIN X, SHROFF N B. An optimization-based approach for QoS routing in high-bandwidth networksJ. IEEE/ACM Transactions on Networking, 2006, 14(6): 1348-1361.3LARS M, HVATTU M, ARN E, et al. A branch-and-regret heuristic for stochastic and dynamic vehicle routing problemsJ. Networks, 2007, 49(4): 330-340.4CHEN Z L, HANG X, et al. Dynamic column generation for dynamic vehicle routing with time windowsJ. Transportation Science, 2006, 40(1): 74-88.5潘耘，王行剛，馮煙利等.求解帶度約束多播路由問題的啟發(fā)式遺傳算法J, 通信學報,2007,28(1): 96-102. PAN Y, WANG X G, FENG Y L, et al. Solving degree-constrained multicast routing problem by a heuristic genetic algorithmJ. Journal on Communications, 2007, 28(1): 96-102.6WANG J Q, TONG X N, LI Z M. An improved evolutionary algorithm for dynamic vehicle routing problem with time windowsA. Lecture Notes in Computer ScienceC. 2007. 1147-1154.7FRANKLIN T H, BEATRICE M, OMBUKI-BERMA N. Dynamic vehicle routing using genetic algorithmJ. Applied Intelligence, 2007, 27(1): 89-99.8ZHANG Y, CAI H, LIN Y, et al. An ant colony system algorithm for the multicast routing problemA. Third International Conference on Natural ComputationC. Haikou, 2007.756-760.9TIAN Y, SONG J, YAO D, et al. Dynamic vehicle routing problem using hybrid ant systemA. Proceedings of the IEEE