第7期王江晴等：求解動態最優路徑的混合優化算法141求解動態最優路徑的混合優化算法王江晴, 覃俊, 李子茂(中南民族大學 計算機科學學院，湖北 武漢 430074)摘 要：對動態網絡環境下動態需求的最優路徑搜索問題進行了研究，首次提出了一個能同時利用演化算法的全局優化能力和蟻群算法的局部探索能力的混合智能優化算法Evo-Ant，并將其應用于DVRP。為了驗證算法的有效性，給出了DVRP的混合整數規劃模型，建立了DVRP的動態性能測試類，并進行了大量的仿真實驗和比較。結果表明，Evo-Ant算法能夠根據實時接收到的信息對當前規劃路徑進行及時調整，具有明顯改善的性能優勢。關鍵詞：動態網絡；路由問題；演化算法；蟻群算法中圖分類號：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)最優路徑搜索主要研究如何在網絡中尋找能夠同時滿足多個約束條件，且具有最小代價的路徑。這類問題在QoS路由、車輛調度等領域中有著廣泛的應用。在實際的網絡中，最優路徑搜索問題分為2種：基于靜態信息的路徑搜索和基于動態信息的路徑搜索1。由于更加貼近實際應用的需求，近年來對動態問題的研究引起了計算機等領域專家學者的廣泛關注24。動態最優路徑問題屬于NP完全問題，目前一般采用現代啟發式算法求解，如演化算法57和蟻群算法810等。演化算法從模擬自然界的生物演化過程入手，以解決智能系統如何從環境中進行學習的問題。演化算法的特點是具有隱含并行性，擅長求解全局最優問題，但算法的局部搜索能力較差，求解精確度較低。蟻群算法也是一種源于自然界的仿生類算法，它模擬昆蟲王國中螞蟻的行為機制，是一種依照螞蟻覓食原理設計而成的群集智能搜索算法。蟻群算法的特點是具有分布式計算特性，局部探索能力很強，但當問題規模較大時，算法效率下降得很快，且不能對解空間進行全面的搜索。本文將演化算法和蟻群算法相融合，提出了一個能滿足實際需求的、尋優能力強的基于動態信息的最優路徑搜索算法Evo-Ant（evolutionary ant colony algorithm）。該算法充分利用了演化算法的全局性和蟻群算法的局部性，采用演化算法對蟻群算法的信息素矩陣進行編碼和優化，擴大了算法對解空間的搜索，提高了蟻群算法找到全局最優解的速度。文中將該算法應用于最優路徑搜索的典型實例動態車輛路徑問題（DVRP, dynamic vehicle routing problem），仿真結果顯示了算法的有效性。本文各節的內容安排如下：第2節給出了DVRP的混合整數規劃模型，第3節提出了Evo-Ant算法，第4節討論了算法實現過程中的若干關鍵技術，第5節給出了仿真實驗結果及分析，第6節為本文的結束語。2 DVRP建模本文考慮動態環境下動態需求的DVRP：在工作日的開始時間完成首次車輛路徑的安排，其任務集合包括前一天未完成的客戶需求以及當天已知的客戶需求，每一客戶需求包括以下信息：需求種類（配送/收集）、給定的貨物量、時間窗以及服務時間長度等；隨后的客戶需求實時到來；車輛的行駛線路是從車場出發再回到車場；任意兩點間的距離和道路條件是已知的，但行駛時間未知；目標是在滿足給定約束條件的情況下使得總代價最小。2.1 有關符號的定義T：整個工作日劃分的區段數，對應的調度時刻分別為T0 , TT；V：整個工作日涉及到的所有客戶，包括車場（用0表示）、靜態需求客戶、動態需求客戶；(cij)：V中所有客戶組成的全互連完全圖的距離矩陣；：在調度時刻邊i, j的單位公里行駛時間；wi：車輛早于客戶i時間窗下界到達時車輛的等待時間；di：車輛晚于客戶i時間窗上界到達時客戶的等待時間；：系數，由使用一輛車的成本決定；：系數，由盈利水平、汽車單位時間所消耗的燃油價格決定；：系數，反映車輛等待客戶而造成損失的程度；：系數，反映客戶等待車輛而造成損失的程度。2.2 模型的建立從全局靜態和局部動態的角度建立動態車輛調度模型：1）假設整個調度階段0，T系統的信息全部已知，建立系統的混合整數規劃模型；2）對于某一給定的調度時刻Tt，建立對應的動態環境下的狀態轉換模型。目標函數包括最小化車輛數、最小化車輛行駛時間、最小化車輛在客戶處的等待時間、最小化客戶等待時間，并采用加權法合成一個代價。DVRP的混合整數規劃模型如下：車輛數量：(1)車輛行駛時間：(2)車輛在客戶處的等待時間：(3)客戶等待時間：(4)目標函數：=min(=min(+)(5)3 算法設計本文提出的Evo-Ant充分利用了演化算法的全局性和蟻群算法的局部性，用蟻群算法對路徑進行實時規劃，用演化算法對蟻群算法的信息素矩陣進行優化以加快其收斂速度，實現了二者的有機結合。為了提高對隨機事件和突發事件進行實時處理的能力，算法根據網絡條件和實時獲得的網絡狀態信息，采用動態評估模型對網絡中各節點之間的連接情況進行實時評估，并利用改進的Dijkstra雙桶算法11計算各節點之間的實時最短路徑。算法流程如下：Step 1 初始化設置Evo-Ant算法的最大迭代次數AImax；設置蟻群算法的迭代次數AI和種群規模AM；設置演化算法的迭代次數EI和種群規模EM；設置其他相關參數。Step 2 生成信息素矩陣利用演化算法迭代EI次生成初始信息素矩陣，個體的評價利用蟻群算法完成，并選取種群中最優的螞蟻對應的目標函數值作為評價依據。Step 3 若不滿足停機條件，重復以下工作：利用蟻群算法迭代AI次，并在每一次迭代完成后更新信息素矩陣。利用演化算法迭代EI次，對信息素矩陣進行優化。Step 4 由最優信息素矩陣生成可行解。4 關鍵技術研究對Evo-Ant算法進行分析可知，算法可以找到的最佳路徑由當前的信息素矩陣決定。為了提高執行速度和解的質量，本算法對信息素矩陣的操作分2階段進行：1）在蟻群算法的迭代過程中，利用蟻群算法的局部探索能力對信息素矩陣進行更新；2）在蟻群算法結束以后，利用演化算法的全局尋優能力對信息素矩陣進行優化。4.1 信息素矩陣更新方法信息素矩陣的更新采用全局更新法。更新規則如下(6)其中，為信息素揮發因子，m為螞蟻數量，Q為設定的常量，Lk為螞蟻k的目標函數值，為螞蟻k在邊i，j的信息增量，如果該螞蟻沒有經過邊i，j，則。4.2 信息素矩陣優化方法信息素矩陣的優化由演化算法完成。算法如下：Step 1 以當前的信息素矩陣為一個個體，然后隨機生成EM-1個個體，CurGen=0；Step 2 評價每一個隨機生成的個體；Step 3 while CurGenEI do進行選擇操作，選出EM個父體；進行交叉操作，對每個后代進行評價；進行變異操作，對每個后代進行評價；將父子2代按適應值排名取前EM個構成新種群；CurGen =CurGen+1；Step 4 返回最好個體所對應的信息素矩陣。4.3 由信息素矩陣生成可行解某一時刻Tt的系統狀態如圖1所示。圖中灰色節點表示收集型的客戶需求，白色節點表示配送型的客戶需求，未連線的點表示新的客戶需求，虛線表示已訪問的路徑，實線表示相應車輛前一時刻的規劃路徑。圖中至少要用3只子螞蟻（對應3輛車）來完成路徑的規劃。算法中，每只螞蟻（代表一個可行解）由多個子螞蟻構成，而每只子螞蟻對應于一輛車走過的路徑。對每只子螞蟻，將圖中的節點分為2類：一類是必須爬過的節點，用1表示；一類是可以爬過的節點，用2表示。從2中隨機選取若干個節點和1組成，這樣問題就轉換成了由中的節點、該子螞蟻的起始節點以及車場構成的一個TSP問題。每只子螞蟻從起始節點開始，按照給定的轉移概率在集合中選擇下一節點，直至走完所有的節點。對于剩下的節點，可以引入一只新的子螞蟻來完成路徑的規劃。螞蟻的轉移概率如下(7)5 仿真實驗由于國內外對于DVRP沒有一個通用的benchmark，為了驗證Evo-Ant算法的性能，本文結合實際問題的需要，采用作者所設計的DVRP通用仿真器DVRPSim12及實驗數據進行仿真實驗。在實驗中，隨機網絡圖生成算法在矩形區域0,5000,500中隨機生成100個節點的交通網絡圖，平均節點度為4，公路類型為3（高速公路、國道和省級公路）。每個客戶的時間窗在2,10按一致性均勻分布隨機生成，每一個客戶的服務時間按均值0.3、方差0.2的正態分布隨機生成。每一個動態客戶到達的時刻按指數分布生成。目標函數中的系數固定為：=20， =2， =3，=3。圖1 螞蟻爬過的路徑5.1 動態性能測試類動態性能指標分類如下：1) 客戶需求：R=R1，R2，R3，R1表示客戶需求變化較慢；R2表示客戶需求變化適中；R3表示客戶需求變化快。2) 路況：D=D1，D2，D3，D1表示從交通網絡圖中的所有路徑中選取10%的路徑使其路況發生變化；D2表示選取30%的路徑使其路況發生變化；D3表示選取50%的路徑使其路況發生變化。3) 問題規模：S=S1，S2，S3，S1表示初始客戶數量在510之間，動態生成的客戶均值在12之間；S2表示初始客戶數量在1020之間，動態生成的客戶均值為3；S3表示初始客戶數量在2030之間，動態生成的客戶均值為4。對于測試實例(R1,D3,(S2)16)，表示客戶動態需求屬于類別1、路況變化程度屬于類別3、問題規模屬于類別2、初始客戶數為16。5.2 實驗結果動態車輛調度系統的工作流程如下：客戶通過網絡、電話等方式實時地向調度中心（即車場）提出需求信息；調度中心通過車載電話、手機、GPS衛星定位系統等實時了解車隊中每一輛車的方位及交通情況，計算各客戶之間的實際行駛時間及最短路徑；調用Evo-Ant進行實時的路徑規劃；輸出規劃結果并向車輛下達調度指令。為了驗證Evo-Ant的性能，本文將Evo-Ant與分支定界法（B-B）和C-W算法進行比較。對于分支定界法，利用第2節建立的混合整數規劃模型求出問題的精確解；對于C-W算法，將其稍作調整用于求解DVRP，即對于新到達的收集型需求采用最小代價的方法插入到已有路徑中，對于不能插入的收集型需求和配送型的新需求則重新派出車輛，其路徑生成同樣采用最小代價的方法。由于分支定界法屬于精確算法，只能求解小規模問題，因此僅用其求解(R1,Dx,Sy)類問題，其中x=1, 2, 3, y=1, 2。算法參數設置如下：AImax=100，AI=EI=5，AM=EM=10，蟻群算法的轉移概率參數為：=1，=3，信息素揮發因子=0.8，最小信息素的值min=0.001，Q=10。演化算法的雜交率為pc=0.5，變異率為pm=0.1。從實驗結果中隨機挑選幾組數據，如表1表3所示。表1 小規模輕度動態需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R1,D1,(S1)5)=1車輛數444路徑代價2 7082 6872 799車輛等待代價453051客戶等待代價373643總代價5 7425 6525 960計算時間60.002392.15342.996表2 中等規模中度動態需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R1,D3,(S2)13)=3車輛數656路徑代價3 2003 1663 482車輛等待代價272169客戶等待代價221944總代價6 6676 5527 423計算時間80.1321 996.98380.085表3 大規模重度動態需求和路況下的計算結果問題集代價類型Evo-AntB-BC-W(R3,D3,(S3)30)=4車輛數89路徑代價5 8975 988車輛等待代價73109客戶等待代價8477總代價12 42512 714計算時間155.986155.2315.3 算法分析從表1表3中可以看出，分支定界法找到的解的質量最好，但從計算時間來看，其計算開銷遠大于Evo-Ant，不能滿足實時系統的需求；C-W與Evo-Ant的時間開銷比較接近，但對于每一種測試問題，Evo-Ant的計算結果均優于C-W。對于一個給定的動態環境下動態需求的DVRP，Evo-Ant在執行速度和解的質量上均能很好地滿足實時車輛路徑調度系統的需求。用Xk表示Evo-Ant第k次迭代時的狀態。由算法的迭代過程可知，k+1時刻的狀態Xk+1取決于Xk，與以前的狀態無關。用一個齊時馬氏鏈描述整個迭代過程，Evo-Ant伴隨的馬氏過程收斂到問題的最優解。5.4 基于GIS數據的實例考慮一個實際的應用問題：初始調度時系統有15個客戶需求（0為調度中心），客戶分布如圖2所示。圖2 初始調度時客戶需求分布第一次調度時所有路段交通暢通，此時需3輛車完成任務：0-13-8-14-6-12-11-5-10-1-00-4-7-9-2-00-3-15-0第二次調度時在客戶10和客戶4之間的路段發生了嚴重交通阻塞，短期內不可能緩解，所以調度算法重新規劃路徑，繞開了堵車路段：0-13-8-14-6-12-11-10-5-1-00-4-7-9-2-00-3-15-0實驗結果表明，算法能夠根據交通信息的變化及時調整車輛的行駛路徑，避開堵車路段，并能實時選取最優路徑，從而為決策者提供快速的決策方案。6 結束語針對動態網絡的最優路徑搜索問題，本文提出了一個新的混合優化算法Evo-Ant。該算法在充分利用演化算法的全局優化能力的同時，又利用了蟻群算法的局部探索能力，能夠獲得更好的執行效果。大量仿真實驗表明，對于動態環境下動態需求的最優路徑搜索問題，Evo-Ant能有效地找到實時的最佳規劃路徑，具有明顯改善的性能增益。這對于提高網絡效率、改善服務質量、緩解交通擁擠狀況等有著重要的意義。該算法也可應用于其他具有動態因素的行業和領域，如郵政投遞、鐵路和飛機的調度、通信工程以及超大規模集成電路的設計等。參考文獻：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潘耘，王行剛，馮煙利等.求解帶度約束多播路由問題的啟發式遺傳算法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