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

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