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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、的鄰域中進(jìn)行局部搜索，直到找到局部最優(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，算法結(jié)束。3.4.2 鄰域結(jié)構(gòu)在使用變鄰域下降搜索之前，需要定義一組鄰域結(jié)構(gòu)。算法ACS_VND中分別使用三種求解VRP問題時(shí)常用的鄰域結(jié)構(gòu)：插入（insert）、交換（swap）和2-opt。1. 插入（insert）將解s中的某個(gè)客戶i從當(dāng)前位置p1移到s的另一個(gè)位置p2（p1與p2可屬于同一路徑，也可屬于

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

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

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

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

20、8: END WHILE9: 根據(jù)式(7)進(jìn)行局部信息素更新；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: 根據(jù)式(8)(9)進(jìn)行全局信息素更新；18: iter = iter + 1；19： 更新、q0；20：END WHILE21：輸出ssb，算法結(jié)束。4 實(shí)驗(yàn)結(jié)果與比較分析為測試算法A

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

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

23、a = min(xa/ya, ya/xa)，然后分別計(jì)算da = ra*ta，pa=(1-ra)*ta，得到該客戶的卸、裝貨需求，其中，ta是基本VRP的benchmark問題中該客戶的需求。而另一個(gè)算例CMTxY，僅是卸、裝請求與CMTxX相反，其他與CMTxX相同。算法ACS_VND用C+實(shí)現(xiàn)，運(yùn)行在Pentium IV 2.93G處理器上，內(nèi)存為1GB。通過大量實(shí)驗(yàn)，確定參數(shù)設(shè)置如下：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，當(dāng)歷史最優(yōu)解連續(xù)5次無改進(jìn)時(shí)，q0 = qmin，否則，令q0 = qmax。4.1 混合算法的性能為了驗(yàn)證混合啟發(fā)式算法的性能，我們分別進(jìn)行三組實(shí)驗(yàn)。第一組實(shí)驗(yàn)只使用ACS，第二組實(shí)驗(yàn)只使用VND，第三組實(shí)驗(yàn)是本文提出的混合算法ACS_VND，三組實(shí)驗(yàn)中的其他設(shè)置相同。不失一般性，我們選擇Salhi和Nagy算例作為實(shí)驗(yàn)測試數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如表1所示，其中第一列是算例名稱，第二列是算例中的客戶個(gè)數(shù)。每組實(shí)驗(yàn)中找到的最好解的路徑總長度L，車輛個(gè)數(shù)k以及CPU時(shí)間t（s）也都在表中列出（L

25、、k和t在本文其它表中的含義均同此表）；表1中最后一行給出三組實(shí)驗(yàn)分別求得的平均結(jié)果。表1 混合算法ACS_VND的性能測試結(jié)果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求解質(zhì)量明顯優(yōu)于單獨(dú)使用ACS或VND，表明將ACS和VN

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

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

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 微機(jī)，2.0 GHz b秒，Pentium IV 微機(jī)，2.93 GH

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

37、VND和現(xiàn)有算法在Dethloff算例上分組平均結(jié)果的比較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 微機(jī)，2.0 GHzb秒，微機(jī)，1.6 GHzc秒，Pentium IV 微機(jī)，2.93 GHzSalhi和Nagy算例有兩種類型的數(shù)據(jù)：實(shí)數(shù)型需求和整數(shù)型需求。其中實(shí)數(shù)型需求是根據(jù)上文所述方法產(chǎn)生，而整數(shù)型需求則是通過對實(shí)數(shù)型需求四舍五入得到。除文獻(xiàn)9其余現(xiàn)有算法均使用實(shí)數(shù)型需求，各算法求得最好解分別在表5和表6種給出。通過表5可以看出，算法ACS_VND求得的最好解使用的車輛數(shù)（k）遠(yuǎn)遠(yuǎn)少于文獻(xiàn)7中算法結(jié)果，略少于文獻(xiàn)10中算法結(jié)果，與

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

40、法相比，算法ACS_VND在算例CMT2X、CMT2Y、CMT12X、CMT12Y、CMT11Y和CMT5X上都能找到車輛數(shù)比前者少1的解，其余算例則相同；從解的路徑長度看，算法ACS_VND最大提高24.17%，最小提高-0.75%，平均提高9.18%。表5算法ACS_VND和現(xiàn)有算法在Salhi和Nagy算例上的最好解比較（實(shí)數(shù)型需求）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 微機(jī)，350 MHz c秒，Pentium IV 微機(jī)，1.6 GHzd秒，Pentium IV 微機(jī)，2.93 GHz表6算法ACS_VND和現(xiàn)有算法在Salhi和Na

44、gy算例上的最好解比較（整數(shù)型需求）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 微機(jī)，2.0 GHz b秒，Pentium IV 微機(jī)，

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

47、中算法相比，由于算法ACS_VND使用的機(jī)器運(yùn)行速度較快，因此，算法ACS_VND運(yùn)行時(shí)間較長。即使考慮運(yùn)行環(huán)境性能的差異，算法ACS_VND運(yùn)行時(shí)間仍然比文獻(xiàn)10中算法運(yùn)行時(shí)間短。由表3、表5和表6可以看出，對于較小規(guī)模問題，算法ACS_VND能夠在很短時(shí)間內(nèi)獲得較好解，隨著問題規(guī)模的增大，雖然算法ACS_VND所需CPU時(shí)間增長較快，但是對于規(guī)模較大的問題如n=199，仍能在2min之內(nèi)獲得較好解。表7 各算法運(yùn)行環(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 結(jié)論結(jié)合不同元啟發(fā)式方法的優(yōu)點(diǎn)和策略，設(shè)計(jì)更有效的混合啟發(fā)式算法是組合優(yōu)化問題研究領(lǐng)域的一個(gè)熱點(diǎn)。結(jié)合蟻群系統(tǒng)和變鄰域下降搜索，本文提出一種混合啟發(fā)式算法ACS_VND，用于求解卸裝一體化車輛路徑問題。利用蟻群系統(tǒng)的搜索多樣性與變鄰域下降搜索較強(qiáng)的局部尋優(yōu)能力，提高求解質(zhì)量，加速算法的收斂。通過實(shí)驗(yàn)驗(yàn)證了混合算法ACS_VND性能優(yōu)于單一算法ACS和VND。另外，對55個(gè)benchmark算例的求解結(jié)果表明，算法ACS_VND能在較短時(shí)間內(nèi)獲得52個(gè)算例的已知最好解，并且更新了44個(gè)算例的已知最好解，表明本文算法的表現(xiàn)優(yōu)于現(xiàn)有算法。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