求解卸裝一體化的車輛路徑問題的混合啟發(fā)式算法(

1、求解卸裝一體化的車輛路徑問題的混合啟發(fā)式算法*Supported by the National Basic Research Program of China under Grant No., 2006CB705500 (國家“九七三”重點基礎研究發(fā)展規(guī)劃項目資助) 作者簡介: 陳萍(1981)，女，山東東明人，博士生，主要研究領域為車輛路徑優(yōu)化算法、元啟發(fā)式以及組合優(yōu)化；黃厚寬(1940)，男，教授，博導，主要研究領域為人工智能、機器學習、數據倉庫、數據挖掘、決策支持系統(tǒng)以及多智能體系統(tǒng)等；董興業(yè)(1974)，男，博士生，主要研究領域為調度理論和算法、組合優(yōu)化。 陳萍+, 黃厚寬, 董興業(yè)

2、(北京交通大學 計算機科學與信息技術學院 北京 100044)() 摘 要:提出一種結合蟻群系統(tǒng)（Ant Colony System, ACS）和變鄰域下降搜索（Variable Neighborhood Descent, VND）的混合啟發(fā)式算法ACS_VND，求解卸裝一體化車輛路徑問題。利用基于插入的ACS解構造方法產生多個弱可行解，再逐個轉換成強可行解，并選擇其中最好的作為VND的初始解。在VND過程中使用三種不同的鄰域結構：插入、交換和2-opt依次對解進行迭代優(yōu)化。對55個規(guī)模為22199的benchmark算例的求解結果表明，算法ACS_VND能在較短時間內獲得52個算例的已知最好

3、解，并且更新了其中44個算例的已知最好解，求解性能優(yōu)于現有算法。關鍵詞: 卸裝一體化車輛路徑問題；混合啟發(fā)式算法；蟻群系統(tǒng)；變鄰域下降搜索；組合優(yōu)化；NP難中圖法分類號:TP 301.6文獻標識碼: A1 引言 車輛路徑問題（Vehicle Routing Problem, VRP）一直是運籌學、管理學、計算機科學等領域的研究熱點問題，在現實生活中有著廣泛的應用， 如物流配送、郵政投遞、校車路徑安排、鐵路和飛機的調度等，是一個具有重要理論意義和實際應用價值的研究課題。近年來，逆向物流的發(fā)展使得VRP中另一形式的問題卸裝一體化車輛路徑問題（Vehicle Routing Problem with

4、 Simultaneous Delivery and Pickup，VRPSDP）引起研究者的關注。卸裝一體化車輛路徑問題可簡單描述如下：安排車輛為一定數量的客戶送貨，并從客戶處收集一定數量的物品（如貨物包裝材料、垃圾等）。每個客戶的地理位置以及卸貨、裝貨需求事先已知。要求在滿足一定約束條件（如車輛容量限制等）的前提下，安排車輛滿足客戶需求使得總的車輛行程長度最短。VRP自1959年由Dantzig1提出后，幾十年來已取得大量研究成果，然而關于VRPSDP的研究卻非常少。1989年Min2針對一個圖書館配送的實例首次定義了該問題。以后的十年中，幾乎沒有關于該問題的討論。逆向物流的興起使得研究者

5、重新開始對該問題進行研究和探討。文獻2-5討論了該問題的若干應用實例。由于VRP是NP難問題，因此，VRPSDP也是NP難的，而且比基本VRP問題更復雜，因此，對此類問題的求解方法研究主要集中在能在較短時間內給出較優(yōu)解的啟發(fā)式算法（heuristic）和元啟發(fā)式算法（metaheuristic），現已取得一定的研究成果，主要有構造性算法，如文獻6中Dethloff提出的帶有參數的插入法，文獻7中的先聚類后插入算法；禁忌搜索，如文獻8中Crispim等提出的基于禁忌搜索的混合算法，文獻9中Tang Montané等提出的基于四種鄰域結構和兩種搜索策略的禁忌搜索，文獻10中Chen和Wu

6、提出一種基于“記錄”和禁忌表的混合啟發(fā)式算法。最近，Bianchessi和Righini提出一些構造性算法、局部搜索算法以及禁忌搜索算法并加以比較，其中重點討論了基于復合多鄰域結構的禁忌搜索算法11。Tang Montané等9給出一組測試算例解的下界，這些下界表明現有算法雖能在一定程度上解決VRPSDP，但求解質量還有較大改進空間。蟻群優(yōu)化（Ant Colony Optimization, ACO）是一種基于群體的元啟發(fā)式算法，最初的靈感來源于真實螞蟻搜尋食物的行為12以信息素作為媒介間接進行信息交換。目前蟻群優(yōu)化已經成功應用于多個NP難的組合優(yōu)化問題求解。變鄰域搜索（Variab

7、le Neighborhood Search, VNS）最早由Hansen和Mladenovi1314提出，其核心思想是：鄰域結構定義了搜索空間的拓撲特性，不同的鄰域結構對應搜索空間的不同區(qū)域。一般地，問題解空間中某個區(qū)域的特性不同于其它區(qū)域，因此，動態(tài)使用不同的鄰域結構能夠增加解的多樣性。變鄰域下降（Variable Neighborhood Descent, VND）是VNS的一種變形，它通過一種確定的方式來改變鄰域結構的使用。根據文獻14中對元啟發(fā)式算法的分類，蟻群優(yōu)化屬于基于群體的算法，而變鄰域下降搜索則是屬于軌跡法。基于群體的元啟發(fā)式算法的優(yōu)勢在于善于發(fā)現搜索空間中的可能存在最優(yōu)解的

8、區(qū)域，而軌跡法的優(yōu)勢在于善于探索搜索空間中較好的區(qū)域。因此，將二者結合可以充分利用各自的優(yōu)勢，提高算法的搜索性能和效率。本文將蟻群優(yōu)化中的一種蟻群系統(tǒng)（Ant Colony System, ACS）與VND相結合，提出一種混合啟發(fā)式算法ACS_VND用于求解VRPSDP。利用55個benchmark測試算例進行實驗，并與文獻2以及文獻611和中的算法求解結果比較，驗證本文算法的有效性。2 卸裝一體化車輛路徑問題描述2.1 問題描述本文利用有向帶權圖G描述卸裝一體化車輛路徑問題：假設，其中，是頂點集（0表示配送中心，其它表示客戶）；是連接各頂點的弧集；是權重矩陣，cij表示從客戶i到客戶j的距離

9、。任意客戶都有一定卸貨需求di與裝貨需求pi。安排車輛為所有客戶服務（假設所有車輛為同一車型，車輛最大容量為Q），要求滿足以下條件并使得車輛總行程長度最短：a) 每輛車都從倉庫出發(fā)，并最終返回倉庫；b) 每個客戶都只被一輛車服務，且僅被服務一次；c) 任一車輛在行程過程中，載重始終不能超過Q。2.2 解的可行性設是VRPSDP問題的一個解，其中ri對應一條車輛路徑。由2.1節(jié)中的VRPSDP問題描述可知，s是VRPSDP問題的一個可行解的充分必要條件是：對任意ri，都滿足1) ri上所有客戶的總的卸貨需求D(x)不超過Q；2) ri上所有客戶的總的裝貨需求P(x)不超過Q；3) 車輛訪問ri上

10、任何客戶之后載重都不超過Q。若都滿足條件（1）（2）（3），則稱s滿足強可行性條件，是強可行解；若都滿足條件（1）（2），但不滿足條件（3），則稱s滿足弱可行性條件，是弱可行解。由于Mosheiov3 已經證明，如果D(x) 和P(x)都不超過車輛容量限制，則ri一定可以通過某種轉化成為可行路徑。因此，若s是弱可行解，則一定可以通過某種方式轉化為強可行解。3 混合啟發(fā)式算法ACS_VND3.1 信息素初始化首先使用最近鄰啟發(fā)式（Nearest Neighborhood Heuristic, NNH）構造一個強可行解s0，并根據式（1）設定信息素初值。 其中，n是客戶數量。NNH構造解的步驟如下

11、：步驟1：從尚未訪問的客戶節(jié)點中，選擇距離配送中心最小的客戶，開始一條新的車輛路徑r；步驟2：若V0不為空，則從中選擇距離r上最后一個客戶最近的客戶，作為下一個訪問的節(jié)點；否則，轉步驟1，直到所有客戶都已被訪問。這里，將V0定義為尚未被訪問，且加入r后，使得r仍能約束強可行性條件的所有客戶節(jié)點的集合。3.2 構建可行解由于弱可行性條件檢查比較簡單，在算法ACS_VND的構建解階段，首先產生一組弱可行解，然后轉化成強可行解。在ACS解的構造方式的基礎上，算法ACS_VND中使用一種基于插入的啟發(fā)式方法構造弱可行解。首先，從配送中心0出發(fā)，隨機選擇一個客戶，開始一條新的路徑r；然后，根據偽隨機比例

12、規(guī)則(2)(3)，從V1中選擇客戶k并將它插入到當前路徑r上節(jié)點i與j之間，這里，V1是指滿足以下條件的客戶節(jié)點k的集合：k尚未被訪問，且若k加入r仍能保證r滿足弱可行性條件。k的定義如式(4)，它決定了客戶k被選中的可能性大小，其中，i和j是當前路徑r上的兩個相鄰的節(jié)點。的定義如式(5)，ik和kj是插入k后新增的兩條弧(i, k)和(k, j)上的信息素，ij是刪去的弧(i, j)上的信息素。ijk是啟發(fā)式信息，定義如式(6)，其中第一項考慮了客戶與配送中心之間的距離，以避免距離倉庫較遠的客戶插入得較晚，從而增加額外的代價；第二項表示將客戶k插入到當前路徑上客戶i與客戶j之間時增加的路徑長

13、度。，是和ijk的相對影響因子。不斷地從V1中選擇客戶，直到V1為空，結束當前路徑r的構造；若所有客戶都已在當前解中，結束算法；否則，重新開始一條新的r并重復上述構造過程。為取得利用歷史信息和隨機選擇之間的平衡，算法ACS_VND中動態(tài)調整q0的大小，使其取值為qmin或qmax。 S：算法ACS_VND中利用與文獻10相同的方法將弱可行解轉化成強可行解，即從頭至尾逐個掃描每一條路徑r上的客戶，若訪問當前客戶后r不能滿足強可行性條件，則跳過當前客戶掃描下一個；否則，繼續(xù)掃描下一個；最后，按照逆序將在第一次掃描中被跳過的客戶逐個重新加入r，即可得到一個強可行解。3.3 局部信息素更新根據式（7）

14、，利用構造的每一個解s進行局部信息素更新，其中，0<1<1是信息素揮發(fā)系數，0是信息素初值。3.4 變鄰域下降搜索變鄰域下降搜索的基本步驟是：從初始解出發(fā)，選擇一種鄰域結構進行局部搜索，直到找到局部最優(yōu)解；以當前局部最優(yōu)解為初始解，使用另一種鄰域結構繼續(xù)進行局部搜索；當使用任何一種鄰域結構都不能繼續(xù)改進當前解時，結束VND過程。3.4.1 VND過程算法1 VND過程 1: 輸入初始解s, 選擇一組鄰域結構Nk，k = 1, , kmax；令p = 0；2: WHILE p < kmax DO3: k = 1；4: WHILE k kmax DO5: 以s為初始解，在Nk定義

15、的鄰域中進行局部搜索，直到找到局部最優(yōu)解s*；6: IF f(s*) < f(s) THEN 7: s = s*；8: p = 0；9: ELSE10: p = p+1；11: END IF12: k = k+1；13: END WHILE14: END WHILE15: 輸出s，算法結束。3.4.2 鄰域結構在使用變鄰域下降搜索之前，需要定義一組鄰域結構。算法ACS_VND中分別使用三種求解VRP問題時常用的鄰域結構：插入（insert）、交換（swap）和2-opt。1. 插入（insert）將解s中的某個客戶i從當前位置p1移到s的另一個位置p2（p1與p2可屬于同一路徑，也可屬于

16、不同路徑），產生新解。例如，解s = 0357012460，將客戶3從當前的2號位置移到4號或6號位置，產生新解 = 0573012460或=0570132460。當某條路徑上沒有客戶節(jié)點時，刪去該路徑，從而使得車輛個數減少。例如，解s = 01250036470，刪去空的子路徑后，得到s = 0125036470。2. 交換（swap）將解s中的客戶i和j的位置互換（i和j可屬于同一路徑，也可屬于不同路徑），產生新解。例如，解s = 0357012460，交換同一路徑上的客戶3與7，產生新解 = 0753012460；解s = 0357012460，交換不同路徑上的客戶3與2，產生新解= 0

17、257013460。3. 2-opt解s中同一路徑上的兩個客戶i和j，在解s中的位置分別為pi與pj（pi < pj）。2-opt是指將pi+1位置上的客戶與j交換，并將pi+1和客戶j（不包括pi+1位置上的客戶和客戶節(jié)點j）之間的客貨節(jié)點按逆序訪問。例如，解s = 0195740263810110，對兩條路徑分別通過2-opt優(yōu)化后，得到新解 = 0147590210836110。3.4.3 搜索策略在搜索過程中，只考查滿足如下條件的移動（move）：至少引入一條弧(i, j)，使得或，其中，其中取值為min或max，從而能夠動態(tài)改變考查的鄰域空間大小。在使用一種鄰域結構局部搜索時只

18、接受最好的鄰域解，直到陷入局部最優(yōu)。實驗中發(fā)現，按照先插入、再交換最后2-opt的順序算法性能表現最好，因此，在第4節(jié)的實驗中，均按此順序使用這三種鄰域結構。3.5 全局信息素更新每次迭代結束后，根據全局信息素更新規(guī)則(8)(9)，使用歷史最優(yōu)解ssb進行全局信息素更新。3.6 算法ACS_VND本小節(jié)給出整個算法ACS_VND的過程。首先，給出相關符號的含義：螞蟻個數ant_num，信息素揮發(fā)系數、1，閾值q0，以及相對影響因子和；最大迭代次數MaxIter，最大連續(xù)無改進代數MaxConsNoImprove；迭代數計數iter，連續(xù)無改進迭代數計數cons_no_improve。算法2 A

19、CS_VND算法偽碼1: 初始化參數ant_num，、1，q0，MaxIter，MaxConsNoImprove；令iter = 0, cons_no_improve = 0；本次迭代最優(yōu)解sib，歷史最優(yōu)解ssb，令f(ssb)為一足夠大的正數；2: 初始化信息素：令s0NNH()；0 = 1/n*f(s0)；3: WHILE iter < MaxIter && cons_no_improve < MaxConsNoImprove DO4: k = 0；5: WHILE k < ant_num DO6: 根據3.2節(jié)的方法構造解sk；7: k = k +1；

20、8: END WHILE9: 根據式(7)進行局部信息素更新；10: 從解種群中選出sib，以sib為初始解，執(zhí)行VND過程，步驟同3.4.1節(jié)中算法1；11: IF f(sib) < f(ssb) THEN12: ssb= sib；13: cons_no_improve = 0；14: ELSE15: cons_no_improve = cons_no_improve + 1；16: END IF17: 根據式(8)(9)進行全局信息素更新；18: iter = iter + 1；19： 更新、q0；20：END WHILE21：輸出ssb，算法結束。4 實驗結果與比較分析為測試算法A

21、CS_VND的性能，我們利用文獻中三組測試算例進行實驗：Min算例2，Dethloff算例6以及Salhi和Nagy算例7，分別是圖書館應用實例，隨機生成的VRPSDP算例，以及基本VRPbenchmark問題的擴展。Min算例是一個圖書館配送的實例。從一個公共圖書館為其他22個分館發(fā)送并收集圖書、膠片、磁帶等，已知各館之間的距離以及所有分館的卸、裝貨請求，車輛容量限制為10,500，卸貨請求總和為20,300，裝貨請求總和為19,950，因此，至少需要兩輛車才能完成配送任務。Dethloff算例是文獻6中隨機生成的40個算例，問題規(guī)模都是50。根據地理位置的分布以及最少需要車輛數的不同，可將

22、它們分成四組：SCA3x、SCA8x、CON3x、CON8x。其中，SCA算例中的客戶均勻分布在區(qū)間0,100；而CON算例中一半客戶均勻分布在100/3, 200/3內，另一半則均勻分布在區(qū)間0,100。在0,100內隨機產生客戶的卸貨請求di，并通過pi = (0.5 + i)*di 產生裝貨請求pi，其中，i是0,1上的隨機數。Salhi和Nagy將基本VRP的benchmark 16加以擴展，作為 VRPSDP問題的測試算例，問題規(guī)模范圍是50199。每個規(guī)模都包含兩個算例，其中CMTxX通過以下變換得到：原benchmark中的客戶位置坐標（x, y）保持不變；對每一個客戶a，計算r

23、a = min(xa/ya, ya/xa)，然后分別計算da = ra*ta，pa=(1-ra)*ta，得到該客戶的卸、裝貨需求，其中，ta是基本VRP的benchmark問題中該客戶的需求。而另一個算例CMTxY，僅是卸、裝請求與CMTxX相反，其他與CMTxX相同。算法ACS_VND用C+實現，運行在Pentium IV 2.93G處理器上，內存為1GB。通過大量實驗，確定參數設置如下：ant_num = 6， = 0.2，1 = 0.1，q0 = 0.9， = = 1；MaxIter = 100+ n，MaxConsNoImprove = MaxIter/4；min = 0.75，max

24、 = 1.50，每隔20代更新 = max，其余則令 = min；qmin = 0.7，qmax = 0.9，當歷史最優(yōu)解連續(xù)5次無改進時，q0 = qmin，否則，令q0 = qmax。4.1 混合算法的性能為了驗證混合啟發(fā)式算法的性能，我們分別進行三組實驗。第一組實驗只使用ACS，第二組實驗只使用VND，第三組實驗是本文提出的混合算法ACS_VND，三組實驗中的其他設置相同。不失一般性，我們選擇Salhi和Nagy算例作為實驗測試數據。實驗結果如表1所示，其中第一列是算例名稱，第二列是算例中的客戶個數。每組實驗中找到的最好解的路徑總長度L，車輛個數k以及CPU時間t（s）也都在表中列出（L

25、、k和t在本文其它表中的含義均同此表）；表1中最后一行給出三組實驗分別求得的平均結果。表1 混合算法ACS_VND的性能測試結果ProblemnACSVNDACS_VNDLktaLktbLktbCMT1X50505.28 3 0.58 496.63 30.05 466.77 31.27 CMT1Y50488.58 3 0.56 479.25 30.05 466.77 31.09 CMT2X75833.34 6 0.97 754.50 60.09 693.50 65.11 CMT2Y75799.13 6 1.06 710.36 60.09 666.75 65.46 CMT3X100853.13

26、5 3.36 774.93 50.15 715.51 511.77 CMT3Y100857.46 5 3.41 774.44 50.18 724.98 512.55 CMT12X100823.48 5 3.09 733.35 60.15 669.10 511.77 CMT12Y100844.44 5 2.07 711.39 60.15 662.41 511.65 CMT11X1201055.71 4 9.40 1003.00 40.27 842.58 426.66 CMT11Y120975.19 4 9.29 1009.09 40.25 843.28 430.27 CMT4X1501147.3

27、6 7 6.91 888.61 70.33 843.24 748.95 CMT4Y1501147.82 7 7.20 959.27 70.38 861.40 747.00 CMT5X1991527.40 10 15.28 1228.40 100.74 1074.88 10102.71 CMT5Y1991494.02 10 13.67 1188.95 100.63 1089.88 10102.83 Avg.953.74 5.7 5.49 836.58 5.9 0.25 758.60 5.729.94通過表1可以看出，混合算法ACS_VND求解質量明顯優(yōu)于單獨使用ACS或VND，表明將ACS和VN

28、D結合是有效的。與ACS和VND相比，ACS_VND的時間開銷較大，但仍能在較短時間內求得問題較好解，所有問題的求解時間都在2min之內。4.2 與現有算法的比較為進一步驗證本文算法ACS_VND的性能，我們將算法ACS_VND求得的最好解與現有算法的結果進行比較，如表26，其中目前已知最好解用黑體標出。表2是算法ACS_VND和現有算法在Min算例上的最好解比較。所有算法求得的最好解的車輛個數都是2，故不在表中列出。本文算法求得的最好解的路徑長度與文獻9中算法的結果相同，優(yōu)于文獻2和6中算法結果，而且求解時間極短，僅為0.1s。表2算法ACS_VND和現有算法在Min算例上的最好解比較Pro

29、blemMin2Dethloff6Tang Montané&Galvão 9ACS_VNDMIN2294918888表3是算法ACS_VND和現有算法在Dethloff各算例上的最好解比較。從該表可以看出，在所有算例上本文算法ACS_VND的求解質量都優(yōu)于文獻6中的算法結果；而與文獻9中算法結果相比，在17個算例上二者求解結果相同，而在其余33個算例上，本文算法ACS_VND的求解結果更優(yōu)。對于算例SCA8-2、SCA8-7和CON8-3，本文算法的解比文獻9中算法的解使用的車輛數少1。另外，對所有算例本文算法都能在2s內找到最好解。表3算法ACS_VND和現有算法

30、在Dethloff算例上的最好解比較ProblemnDethloff6Tang Montané&Galvão 9ACS_VNDLktLktaLktbSCA3-050689.0 -640.55 43.37 635.62 41.19 SCA3-150765.6 -697.84 43.25 697.84 41.14 SCA3-250742.8 -659.34 43.52 659.34 41.02 SCA3-350737.2 -680.04 43.31 680.04 41.19 SCA3-450747.1 -690.50 43.43 690.50 41.22 SCA3-55

31、0784.4 -659.90 43.67 659.90 41.01 SCA3-650720.4 -653.81 43.35 651.09 41.16 SCA3-750707.9 -659.17 43.33 659.17 40.81 SCA3-850807.2 -719.47 43.40 719.47 41.12 SCA3-950764.1 -681.00 43.41 681.00 41.07 SCA8-0501132.9 -981.47 94.14 961.50 91.08 SCA8-1501150.9 -1077.44 94.27 1049.65 91.17 SCA8-2501100.8 -

32、1050.98 104.20 1044.48 91.20 SCA8-3501115.6 -983.34 94.17 983.34 91.08 SCA8-4501235.4 -1073.48 94.13 1065.49 90.97 SCA8-5501231.6 -1047.24 94.02 1027.08 91.19 SCA8-6501062.5 -995.59 93.85 971.82 91.40 SCA8-7501217.4 -1068.56 104.22 1052.17 91.32 SCA8-8501231.6 -1080.58 93.85 1071.18 91.19 SCA8-95011

33、85.6 -1084.80 94.20 1060.50 91.09 CON3-050672.4 -631.39 43.64 616.52 41.71 CON3-150570.6 -554.47 43.31 554.47 41.53 CON3-250534.8 -522.86 43.45 518.00 41.23 CON3-350656.9 -591.19 43.28 591.19 41.24 CON3-450640.2 -591.12 43.47 588.79 41.40 CON3-550604.7 -563.70 43.38 563.70 41.27 CON3-650521.3 -506.1

34、9 43.32 501.32 41.20 CON3-750602.8 -577.68 43.51 576.48 41.18 CON3-850556.2 -523.05 43.66 523.05 41.37 CON3-950612.8 -580.05 43.36 578.25 41.24 CON8-050967.3 -860.48 94.19 857.40 91.65 CON8-150828.7 -740.85 93.89 740.85 91.39 CON8-250770.2 -723.32 93.76 712.89 91.65 CON8-350906.7 -811.23 104.12 829.

35、87 91.32 CON8-450876.8 -772.25 93.75 772.25 91.31 CON8-550866.9 -756.91 93.99 754.95 91.45 CON8-650749.1 -678.92 94.04 678.92 91.42 CON8-750929.8 -814.50 94.00 811.96 91.10 CON8-850833.1 -775.59 93.74 767.53 91.60 CON8-950877.3 -809.00 94.13 809.00 91.60 a秒，Athlon 微機，2.0 GHz b秒，Pentium IV 微機，2.93 GH

36、z由于文獻11中只給出算法求解的平均解，因此，我們在表4中列出算法ACS_VND以及現有算法求解的平均結果。根據表4中各算法在四組算例上的平均結果，與文獻6中算法相比，算法ACS_VND的求解質量分別提高了9.80%、11.81%、6.04%、10.11%，整體提高9.91%；與文獻9中算法相比，算法ACS_VND的求解質量分別提高了0.11%、1.50%、0.53%、0.10%，整體提高0.66%；與文獻11中算法相比，算法ACS_VND的求解質量分別提高了1.64%、0.67%、1.29%、0.37%，整體提高0.92%。另外，本文算法和文獻11中算法平均使用的車輛數更少。表4算法ACS_

37、VND和現有算法在Dethloff算例上分組平均結果的比較AlgorithmDethloff6Tang Montané&Galvão 9Bianchessi11ACS_VNDLktLkt aLkt bLktcSCA3746.57 - - 674.1643.4684.6459.47673.441.1SCA81166.43 - - 1044.359.24.111035.7917.051028.7291.17CON3597.27 - - 564.1743.44568.5459.36561.1841.34CON8860.59 - -774.319.13.96776.4915

38、.14773.5691.45Avg.842.72 - -764.256.583.73766.36.537.76759.226.51.25a秒，Athlon 微機，2.0 GHzb秒，微機，1.6 GHzc秒，Pentium IV 微機，2.93 GHzSalhi和Nagy算例有兩種類型的數據：實數型需求和整數型需求。其中實數型需求是根據上文所述方法產生，而整數型需求則是通過對實數型需求四舍五入得到。除文獻9其余現有算法均使用實數型需求，各算法求得最好解分別在表5和表6種給出。通過表5可以看出，算法ACS_VND求得的最好解使用的車輛數（k）遠遠少于文獻7中算法結果，略少于文獻10中算法結果，與

39、文獻8中算法結果相同；從路徑長度來看，算法ACS_VND在所有算例上的解都優(yōu)于文獻7和8中的算法；除算例CMT2X、CMT4Y和CMT5Y，本文算法在其余算例上的解都優(yōu)于文獻10中算法。與文獻7中算法相比，算法ACS_VND的求解質量最大提高43.83%，最小提高18.40%；與文獻8中算法相比，算法ACS_VND的求解質量最大提高22.98%，最小提高2.14%；與文獻9中算法相比，算法ACS_VND的求解質量最大提高4.93%，最小提高-1.06%。從平均結果來看，算法ACS_VND的解比文獻7、8和10中算法的解分別提高28.63%、8.59%和1.49%。根據表6中的數據，與文獻9中算

40、法相比，算法ACS_VND在算例CMT2X、CMT2Y、CMT12X、CMT12Y、CMT11Y和CMT5X上都能找到車輛數比前者少1的解，其余算例則相同；從解的路徑長度看，算法ACS_VND最大提高24.17%，最小提高-0.75%，平均提高9.18%。表5算法ACS_VND和現有算法在Salhi和Nagy算例上的最好解比較（實數型需求）ProblemnSalhi&Nagy7Crispim&Brandão 8Chen&Wu10ACS_VNDLktaLktbLktcLktdCMT1X5060161.5 477311.2478.59 37.74 466.77 3

41、1.27 CMT1Y5060351.5 48539.1480.78 37.81 466.77 31.09 CMT2X75873101.2 710624.3688.51 624.86 693.50 65.11 CMT2Y75924121.2 715626.4679.44 612.02 666.75 65.46 CMT3X100923101.6 744537.1744.77 594.06 715.51 511.77 CMT3Y100923101.7 742533.5723.88 5120.66 724.98 512.55 CMT12X100820104.9 731537.1678.46 646.8

42、3 669.10 511.77 CMT12Y100873114.8 860533.7676.23 656.35 662.41 511.65 CMT11X1201500113.4 944432.4858.57 4321.08 842.58 426.66 CMT11Y1201500113.5 1035429.6859.77 5230.72 843.28 430.27 CMT43 915758.1887.00 7501.95 843.24 748.95 CMT4Y1501178154.3 996747.6852.35 7406.32 861.40 747.00 CMT5X1

43、9915091912.3 11361089.41089.22 101055.83 1074.88 10102.71 CMT5Y19914771912.0 11291077.11084.27 10771.71 1089.88 10102.83 Avg.106311.74.73 829.935.739.04770.13 5.9261.28 758.65 5.729.94 a秒，VAX 4000-500 b秒，Pentium II 微機，350 MHz c秒，Pentium IV 微機，1.6 GHzd秒，Pentium IV 微機，2.93 GHz表6算法ACS_VND和現有算法在Salhi和Na

44、gy算例上的最好解比較（整數型需求）ProblemnTang Montané&Galvão 9ACS_VNDLktaLkteCMT1X5047233.73 470.67 31.31 CMT1Y5047034.37 470.67 31.13 CMT2X7569576.91 684.29 65.71 CMT2Y7570077.61 664.54 64.44 CMT3X100721511.04 715.14 514.33 CMT3Y100719512.01 724.38 512.55 CMT12X100880612.23 667.29 514.17 CMT12Y10087

45、8612.80 666.93 510.70 CMT11X120900418.17 839.05 427.91 CMT11Y120910518.04 834.52 432.43 CMT4X150880724.60 841.29 755.89 CMT4Y150878729.07 860.32 749.57 CMT5X19910981151.50 1077.22 10114.61 CMT5Y19910831056.21 1083.63 10117.36 Avg.806.0 6.119.16 732.02 5.7 33.01 a秒，Athlon 微機，2.0 GHz b秒，Pentium IV 微機，

46、2.93 GHz4.3 算法運行時間的比較由于各算法運行環(huán)境不同，因此不能直接比較算法的CPU時間。根據Dongarra的Linpack基準測試17，可以通過Mflops（Million Floationg Point/Second，每秒百萬個浮點操作）標準得到不同微機的大致相對速度。表7中給出了文獻79中各微機的機型主頻、Mflops以及轉換為VAX4000-500上CPU時間的轉換因子（factor）（由于文獻11中未能給出具體的微機型號，故此處略去）。從表5和表7可以看出，算法ACS運行時間遠遠多于文獻7中算法，這是因為，前者是迭代搜索算法，而后者是構造型方法不需要多次迭代。與文獻8和9

47、中算法相比，由于算法ACS_VND使用的機器運行速度較快，因此，算法ACS_VND運行時間較長。即使考慮運行環(huán)境性能的差異，算法ACS_VND運行時間仍然比文獻10中算法運行時間短。由表3、表5和表6可以看出，對于較小規(guī)模問題，算法ACS_VND能夠在很短時間內獲得較好解，隨著問題規(guī)模的增大，雖然算法ACS_VND所需CPU時間增長較快，但是對于規(guī)模較大的問題如n=199，仍能在2min之內獲得較好解。表7 各算法運行環(huán)境性能比較CPUMflopsfactorSalhi&Nagy7VAX 4000-5005.71Crispim&Brandão 8Pentium II，

48、350 MHz69-7410Tang Montané&Galvão 9Athlon，2.0 GHz832-1000170Chen&Wu10Pentium IV，1.6 GHz< 1190< 209ACS_VNDPentium IV ，2.93 GHz1317-14142405 結論結合不同元啟發(fā)式方法的優(yōu)點和策略，設計更有效的混合啟發(fā)式算法是組合優(yōu)化問題研究領域的一個熱點。結合蟻群系統(tǒng)和變鄰域下降搜索，本文提出一種混合啟發(fā)式算法ACS_VND，用于求解卸裝一體化車輛路徑問題。利用蟻群系統(tǒng)的搜索多樣性與變鄰域下降搜索較強的局部尋優(yōu)能力，提高求解質量，加速算法的收斂。通過實驗驗證了混合算法ACS_VND性能優(yōu)于單一算法ACS和VND。另外，對55個benchmark算例的求解結果表明，算法ACS_VND能在較短時間內獲得52個算例的已知最好解，并且更新了44個算例的已知最好解，表明本文算法的表現優(yōu)于現有算法。References: 1 Dantzig GB, Ramser JH. The truck dispatching problemJ. Management Science, 1959, 6(1):80-91.2 Min H. The multiple vehicle routing problem