求VRPTW問題的并行協(xié)同混合差異演化算法

馬立肖

摘要：車輛路徑優(yōu)化問題的研究對物流配送系統(tǒng)的發(fā)展具有重要意義。尋找?guī)r間窗的車輛路由問題的最優(yōu)求解策略是其中的研究熱點之一。該文提出并行協(xié)同混合差異演化算法用于該問題的求解，仿真實驗結(jié)果表明該算法在問題求解中表現(xiàn)出良好的有效性和可靠性。

關(guān)鍵詞:帶時間窗的車輛路徑問題;差異演化算法;協(xié)同進化;合作型協(xié)同進化;競爭型協(xié)同進化

中圖分類號：TP301文獻標(biāo)識碼：A文章編號：1009-3044(2012)20-4970-04

Co-evolutionary Mixed Differential Evolutionary Algorithm for VRP with Time Windows Problem

MA Li-xiao

(Shijiazhuang University of Economics,Shijiazhuang 050031,China)

Abstract：Research on vehicle routing problem is of great importance in logistics distribution system.For the vehicle routing problems with time windows, how to find a optimal strategy is one of difficult problem. In this work, a Co-evolutionary mixed differences evolutionary algorithm is designed to investigate the problem,The results of experiment show its dependability and feasibility.

Key words：VRP with time windows; differential Evolution; co-evolutionary; cooperative coevolution; Competitive collaborative evo? lution

車輛運輸路徑問題（Vehicle Routing Problem，簡記為VRP）[1]的優(yōu)化在物流配送中起重要的決策作用，它是指在車輛調(diào)度中對配送車輛的行駛路線方案的優(yōu)化，找出優(yōu)化后的配送車輛行駛路線方案，以提高貨物運輸效率，降低物流企業(yè)的運營成本。加入時間約束得到的帶時間窗的車輛路徑問題（VRP with Time Windows，簡記為VRPTW）[2]是VRP擴展問題的一個廣泛研究的分支問題。

VRPTW問題在當(dāng)今的經(jīng)濟發(fā)展中具有非常重要的現(xiàn)實意義，也是相關(guān)領(lǐng)域?qū)W者研究的焦點之一。常用的求解方法可以分為精確算法和啟發(fā)式算法。近年來，啟發(fā)式算法以其在求解大規(guī)模復(fù)雜問題方面的優(yōu)越性，廣泛應(yīng)用在VRPTW問題的求解中，例如馬為民[3]在其博士論文中用在線和競爭策略研究了帶時間窗的開放式VRPTW，馮萍[4]在其碩士論文中用插入法、遺傳算法、模擬退火算法研究了帶軟時間窗的車輛路徑問題，東北大學(xué)姜大立[5]等分別針對有時間窗和無時間窗約束下的車輛路徑問題用基因編碼遺傳算法求解，結(jié)果在較快速度下得到了近優(yōu)解。然而，目前的求解方法在大規(guī)模問題求解中，仍無法突破局部最優(yōu)解的局限，因此，如何有效利用問題空間的有效信息，提高算法的局部搜索能力仍是一個值得研究的問題。

該文將差異演化算法與協(xié)同進化機制進行結(jié)合，充分利用了差異演化算法搜索速度快的優(yōu)點，同時通過協(xié)同進化機制，促使種群間進行信息交流，防止陷入局部最優(yōu)。

2.2.3基于并行協(xié)同機制的多種群的生成

步驟1：依據(jù)3.2.2方法隨機生成3個初始化種群POP1，POP2，POP3；

步驟2：生成隨機數(shù)r∈{1，2，3}，將POPr作為進化主種群；

步驟3：將POPr作為合作型種群模板，固定種群中染色體中0基因位，依據(jù)種群生成策略生成3個合作種群POPr1，POPr2，POPr3。

步驟4：生成隨機整數(shù)h和f（h≠f≠r，且h,f∈{1，2，3}），指定種群POPh作為學(xué)習(xí)種群，POPf作為評價種群；

2.2.4 DE的變異、交叉、選擇算子

1)變異

從種群中隨機選擇3個個體Xp1，Xp2，Xp3(且p1≠p2≠p3),執(zhí)行如下操作：Vj

3.1算法實例

某物流中心有5輛配送車輛，車輛的最大載重量均為8T，一次配送的最大行駛距離均為50Km，需要向20個客戶送貨。物流中心的坐標(biāo)為（13.0Km，14.5km），20個客戶的坐標(biāo)及其貨物需求量見表1：

表1物流信息表

要求合理安排行車路線使得配送總里程最短。為了簡化起見，配送車輛在客戶處的卸貨時間不計，各客戶之間及配送中心與客戶之間的距離均采用直線距離，該距離可根據(jù)客戶和配送中心的坐標(biāo)計算得到。3.2實驗環(huán)境及參數(shù)設(shè)置

實驗環(huán)境：CPU-PIV2.8G，內(nèi)存512M；操作系統(tǒng)Microsoft Windows xp，開發(fā)語言Microsoft Visual C++6.0。

實驗參數(shù)設(shè)置如下：種群規(guī)模POPSIZE=20，編碼長度d=26，最大進化代數(shù)T=200，縮放因子F=0.5，交叉概率CR=0.3。

3.3實驗結(jié)果及分析

針對3.1節(jié)的實例，應(yīng)用CODEGA算法與DE算法，隨機運行10次后，實驗結(jié)果如表2所示。

表2 CODEGA算法與DE算法結(jié)果對比

該文針對物流配送中車輛運輸路線優(yōu)化問題的VRPTW問題模型，提出了并行協(xié)同混合差異演化算法，實驗結(jié)果表明應(yīng)用該算法在找到優(yōu)良解的效率和解的質(zhì)量方面均表現(xiàn)出較好的性能，并行協(xié)同進化機制的引入，有效改善了DE算法的求解性能。

[1]紀(jì)壽文,繆立新,李克強.貨運車輛優(yōu)化調(diào)度方法[J].公路交通科技,2003,20(6):109-112.

[2]朗茂祥.物流配送車輛調(diào)度問題的模型和算法研究[D].北京：北方交通大學(xué),2002:135-140.

[3]馬衛(wèi)民.第三方物流配送優(yōu)化問題及其競爭策略[D].西安交通大學(xué),2003.

[4]馮萍.退火遺傳算法在運輸路線規(guī)劃中的應(yīng)用[D].西安交通大學(xué),2001.

[5]姜大立,楊西龍,杜文,周賢偉.車輛路徑問題的遺傳算法研究[J].系統(tǒng)工程理論與實踐,1999,19(6).

[6]范李平.物流配送及其車輛優(yōu)化調(diào)度研究[D].上海海事大學(xué),2004.

[7] Storn R, Price K. Differential evolution–a simple and efficient adaptive scheme for global optimization over continuous spaces. Techni? cal report, International Computer Science Institute, Berkley,1995.

[8] Hillis W D.協(xié)同進化的寄生物改善作為優(yōu)化手段的模擬進化[J].物理學(xué),1990,42(1-3):228-234.

[9] Rosin C D.RKBelew.面向競爭協(xié)同進化的新方法[J].進化計算,1997,5(1):1-29.

[10] CartlidgeJ,BullockS.Combating Coevolutionary Disengagement by Reducing Parasite Virulence [J].Evolutionary computation,2004,12(2): 193.