黃戈文 蔡延光 湯雅連

(1．嘉應(yīng)學(xué)院 信息網(wǎng)絡(luò)中心，廣東梅州 514015;2．廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006)

VRP［1－2］自1959年Dantzig和Ramser首先提出以來就引起了人們的高度重視。VRP的實(shí)用性強(qiáng)，應(yīng)用廣泛。車輛路徑問題一般定義為:對(duì)一系列送貨點(diǎn)和收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件 (如貨物需求量、發(fā)送量、送發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下，達(dá)到一定的目標(biāo) (如路程最短、費(fèi)用極小、時(shí)間盡量少、使用車輛數(shù)盡量少等)。在現(xiàn)實(shí)生活中存在這樣的情況，不同客戶需要多種零件商品，而這些零件商品由于性質(zhì)、特征和用途的差異，又存在某種聯(lián)系，即存在貨物性質(zhì)關(guān)聯(lián)性，客戶常常為了保證其需求不受影響而將所有的零件商品供貨交付給一個(gè)物流運(yùn)輸公司來為其配貨，將關(guān)聯(lián)的貨物配套運(yùn)輸更有利于后期的運(yùn)作或經(jīng)營，如一臺(tái)手機(jī)的組件必須包括一個(gè)充電器，一個(gè)液晶屏、手機(jī)按鍵、外殼、電池等，一個(gè)螺栓對(duì)應(yīng)一個(gè)螺釘，它們存在某種數(shù)量關(guān)系，客戶的這種需求我們稱之為需求關(guān)聯(lián)。零件商品在被客戶使用，即在加工組成成品的過程中，零件的使用也有一定的先后順序，我們稱零件商品具有時(shí)間關(guān)聯(lián)性。這時(shí)，物流公司為需要這種貨物性質(zhì)的客戶配送貨物，應(yīng)該考慮怎樣進(jìn)行貨物任務(wù)分配、車輛分配、時(shí)間分配，并尋求最優(yōu)配送路線以達(dá)到最低的物流成本，上述問題我們統(tǒng)稱為關(guān)聯(lián)運(yùn)輸調(diào)度問題 (Incident Vehicle Routing Problem，IVRP)，此類問題在現(xiàn)實(shí)生活中普遍存在，因而極具現(xiàn)實(shí)意義。

量子進(jìn)化算法 (Quantum Evolutionary Algorithm，QEA)是20世紀(jì)90年代后期新興的一種進(jìn)化算法。由于其良好的性能，已廣泛應(yīng)用于諸多領(lǐng)域，如物流運(yùn)輸調(diào)度、智能交通領(lǐng)域、網(wǎng)格入侵檢測(cè)、網(wǎng)格任務(wù)調(diào)度、非線性規(guī)劃等［3－4］。Mohammed A M等人［3］提出了基于量子交叉的量子遺傳算法 (quantum crossover－based quantum genetic algorithm，QXQGA)對(duì)非線性規(guī)劃問題求解;蔡延光等人［4］針對(duì)量子進(jìn)化算法計(jì)算量大、收斂速度慢以及容易出現(xiàn)早熟等問題，提出混沌混合量子進(jìn)化算法，并證明其可較好地應(yīng)用在智能交通領(lǐng)域。研究車輛路徑優(yōu)化問題 (Vehicle Routing Problem，VRP)是研究IVRP的基礎(chǔ)。目前，國內(nèi)外采用QEA及其改進(jìn)算法對(duì)VRP或其擴(kuò)展問題的研究文獻(xiàn)不少，有一定的借鑒意義。Cui L等人［5］提出了一種帶混合局部搜索的改進(jìn)量子進(jìn)化算法 (improved quantum evolution algorithm，IQEA)對(duì)帶容量約束的VRP(capacitated vehicle routing problem，CVRP)求解;Wang L等人［6］提出了一種改進(jìn)量子進(jìn)化算法 (Quantum－Inspired Evolutionary Algorithm，IQEA)對(duì)帶時(shí)間窗的VRP(vehicle routing problem with time windows，VRPTW)求解;葛顯龍等人［7］根據(jù)隨機(jī)需求信息把動(dòng)態(tài)配送問題轉(zhuǎn)換成一系列靜態(tài)配送問題，設(shè)計(jì)基于并行節(jié)約算法動(dòng)態(tài)插入隨機(jī)需求信息的混合量子遺傳算法，對(duì)動(dòng)態(tài)模型實(shí)時(shí)再優(yōu)化;之后，葛顯龍等人［8］又采用量子比特位設(shè)計(jì)染色體結(jié)構(gòu)，改進(jìn)遺傳算法中交叉與變異算子，避免優(yōu)秀基因被破壞，設(shè)計(jì)快速尋優(yōu)機(jī)制與最優(yōu)保留機(jī)制，增強(qiáng)求解效率對(duì)以配送總費(fèi)用最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型求解;Zhang J等人［9］提出了一種自適應(yīng)網(wǎng)格多目標(biāo)量子進(jìn)化算法 (multi－objective quantum evolutionary algorithm，MOQEA)對(duì)帶客戶滿意度的多目標(biāo)VRP(multiobjective vehicle routing problem considering customer satisfaction，MVRPCS)求解;Michallet J等人［10］研究了非常嚴(yán)格的帶時(shí)間窗的周期性VRP，并提出了混合整數(shù)線性模型和多起點(diǎn)迭代局部搜索算法;Crispin A等人［11］提出了一種量子模擬算法對(duì)帶容量約束的VRP求解;Zheng T等人［12］提出了量子差分進(jìn)化算法對(duì)調(diào)度問題求解;Zhou L等人［13］針對(duì)傳統(tǒng)的遺傳算法不能保證收斂到最優(yōu)解的最大概率，提出了對(duì)小規(guī)模求解具有快速收斂和良好搜索能力的量子遺傳算法，對(duì)VRP求解;Ning T等人［14］結(jié)合量子粒子群優(yōu)化算法和模擬退火算法，提出了混合量子粒子群優(yōu)化算法對(duì)帶時(shí)間窗的VRP求解;彭典軍［15］在其碩士論文中，主要研究了一種量子進(jìn)化算法在車輛路徑問題中的應(yīng)用，具體求解了有能力約束車輛路徑問題、開放式車輛路徑問題、動(dòng)態(tài)網(wǎng)格車輛路徑問題、動(dòng)態(tài)需求車輛路徑問題;劉勇等人［16］為求解給定期限條件的應(yīng)急設(shè)施選址問題，將量子個(gè)體作為博弈者參與到競(jìng)爭(zhēng)決策中，利用量子位、疊加態(tài)等理論提高競(jìng)爭(zhēng)群體多樣性，縮小群體規(guī)模，提出了一種量子競(jìng)爭(zhēng)決策算法;寧濤［17］在其博士論文中，提出混合量子粒子群優(yōu)化算法對(duì)帶時(shí)間窗車輛路徑問題求解;提出模擬退火算法與量子算法對(duì)不確定需求車輛路徑問題的數(shù)學(xué)規(guī)劃模型求解;結(jié)合精英量子均值和混沌擾動(dòng)理論的量子進(jìn)化算法對(duì)帶同時(shí)取送貨需求的車輛路徑問題求解;蔡蓓蓓等人［18］構(gòu)造了一種混合量子遺傳算法，即在傳統(tǒng)量子遺傳算法隨機(jī)全局搜索的基礎(chǔ)上引入一個(gè)免疫算子，通過該算子的局部搜索實(shí)現(xiàn)線路內(nèi)次序的再優(yōu)化;李川［19］在其碩士論文中，對(duì)隨機(jī)需求的車輛路徑問題進(jìn)行研究，通過設(shè)計(jì)不同混合量子進(jìn)化算法對(duì)建立的帶時(shí)間窗和基于模糊預(yù)約時(shí)間的多目標(biāo)問題模型求解;任偉［20］提出了一種混合量子免疫進(jìn)化算法對(duì)帶時(shí)間窗的車輛調(diào)度問題求解;吳斌等人［21］針對(duì)量子進(jìn)化算法中旋轉(zhuǎn)角取值的離散性使其解空間的搜索具有跳躍性，提出了基于混沌理論的精英均值計(jì)算旋轉(zhuǎn)角算法，對(duì)具有同時(shí)集送貨需求車輛路徑問題求解;趙燕偉等人［22］針對(duì)帶時(shí)間窗的隨機(jī)需求車輛路徑問題，建立了基于模糊滿意度的多目標(biāo)數(shù)學(xué)規(guī)劃模型，提出了一種基于量子進(jìn)化算法和粒子群算法分段優(yōu)化的方法求解Pareto解;李熠等人［23］提出了一種新的混合量子優(yōu)化算法，即量子蟻群算法對(duì)旅行商問題求解。以上學(xué)者或研究人員都取得了不錯(cuò)的成果。IVRP由蔡延光教授首次提出，相關(guān)文獻(xiàn)還相當(dāng)有限，且同時(shí)考慮關(guān)聯(lián)特征、載重約束、多車場(chǎng)多車型、車場(chǎng)與客戶硬時(shí)間窗等因素的IVRP的研究文獻(xiàn)還沒有發(fā)現(xiàn)，本文提出混合混沌量子進(jìn)化算法對(duì)該問題求解。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

有 i個(gè)客戶 (1，2，…，l)，第 i個(gè)客戶的需求量為 gi(i=1，2，…，l)，m(m=1，2，…，M)個(gè)車場(chǎng)，車輛裝載貨物后，配送給相應(yīng)的客戶。假設(shè)客戶i所需貨物有θ種，即該客戶的貨物種類可表示為，這θ種貨物之前的需求關(guān)系可表示為，則存在種數(shù)量關(guān)系，比如，關(guān)系式之一，，即表示個(gè)貨物就需要與個(gè)貨物關(guān)聯(lián)配送。車場(chǎng)m有h(h=1，2，…，H)種車型的貨車k(k=1，2，…，K)輛，每種車型車輛的載重為qh，已知qh，客戶硬時(shí)間窗為［eti，lti］，假定一個(gè)客戶所有貨物的送貨時(shí)間窗一致。Ti表示車輛到達(dá)i的時(shí)間。不考慮裝卸貨時(shí)間。以表示車場(chǎng)m中車型h的車輛k從i到j(luò)的單位運(yùn)輸成本 (距離、費(fèi)用、時(shí)間等)，路徑具有對(duì)稱性，即。車型h的車輛k從客戶i到j(luò)之間的距離為，車輛最大行駛里程約束為Dmax。為車輛從車場(chǎng)實(shí)際出發(fā)的時(shí)間，為車輛從返回原車場(chǎng)的時(shí)間，車場(chǎng)硬時(shí)間窗［etm，ltm］。v為通過交通數(shù)據(jù)擬合的平均速度。目標(biāo)函數(shù)為考慮路況約束、載重約束、多車場(chǎng)多車型、客戶與車場(chǎng)硬時(shí)間窗等情況下，滿足客戶需求，并使總成本最小。

1.2 建立數(shù)學(xué)模型

假設(shè)客戶編號(hào)為1，2，…，l，車場(chǎng)編號(hào)為l+m。決策變量如下:

目標(biāo)函數(shù):

約束條件:

式 (3)為目標(biāo)函數(shù)，表示總成本最小。式 (4)和式 (5)表示每個(gè)客戶只能由某車場(chǎng)某車型中的一輛車服務(wù)。式 (6)表示車輛的行駛里程約束。式 (7)表示車輛從所在的車場(chǎng)出發(fā)，完成配送任務(wù)后，回到原車場(chǎng)。式 (8)和式 (9)表示每輛車所運(yùn)送的貨物重量不能超過此類型車輛的載重限制。式 (10)tij表示i到j(luò)的行駛時(shí)間。式 (11)－式 (12)表示車輛出發(fā)時(shí)間和返回時(shí)間必須嚴(yán)格遵守車場(chǎng)時(shí)間窗。式 (13)表示車輛送貨時(shí)間嚴(yán)格遵守客戶時(shí)間窗。式 (14)消除了車輛不是從車場(chǎng)出發(fā)的現(xiàn)象。

2 算法設(shè)計(jì)

本文采用實(shí)數(shù)對(duì)個(gè)體進(jìn)行編碼，與文獻(xiàn)［4］的方法一致，采用混沌初始化方法產(chǎn)生初始種群，采用簡(jiǎn)單量子旋轉(zhuǎn)門更新當(dāng)前種群中的非最優(yōu)個(gè)體，設(shè)計(jì)基于目標(biāo)函數(shù)梯度信息和混沌變換序列的量子旋轉(zhuǎn)門更新當(dāng)前種群中的最優(yōu)個(gè)體，采用混沌變異策略抑制早熟現(xiàn)象，提出了混合混沌量子進(jìn)化算法。

2.1 編碼

設(shè)X=(x1，x2，…，xn)T為所求問題模型的可行解，則對(duì)任意xi(i=1，2，…，n)，存在唯一實(shí)數(shù)θi∈［0，1］使 (15)成立，顯然，θi與xi是一一對(duì)應(yīng)的。

2.2 產(chǎn)生初始種群

設(shè)種群規(guī)模為 N ，隨機(jī)生成 n 個(gè)實(shí)數(shù) θ1，i，0 ＜ θ1，i＜ 1 ，θ1，i≠0.5 ，i=1，2，…，n 。對(duì)每個(gè) i(i=1，2，…，n)，把 θ1，i作為 Logistic 映射的初始值，產(chǎn)生第 i個(gè)混沌序列 {θ2，i，θ3，i，…，θN，i}，如式 (16)所示，其中，j=1，2，…，N 。

2.3 非最優(yōu)個(gè)體更新策略

采用簡(jiǎn)單量子旋轉(zhuǎn)門對(duì)當(dāng)前種群中的非最優(yōu)個(gè)體進(jìn)行更新。設(shè)全局最優(yōu)個(gè)體為B=(θ1b，θ2b，…，θnb)T，即進(jìn)化到目前為止的最優(yōu)個(gè)體，Θ =(θ1，θ2，…，θn)T為當(dāng)前種群中的任一非最優(yōu)個(gè)體。當(dāng)前種群中的最優(yōu)個(gè)體是指當(dāng)前種群中對(duì)應(yīng)的目標(biāo)函數(shù)值最小的個(gè)體，Θ的第i個(gè)基因θi的量子旋轉(zhuǎn)門的旋轉(zhuǎn)角Δθi按式 (17)選取，其中θ0為基本旋轉(zhuǎn)角，且0＜θ0＜1。

令

2.4 最優(yōu)個(gè)體更新策略

基于目標(biāo)函數(shù)的梯度信息和混沌變換序列，構(gòu)造量子旋轉(zhuǎn)門更新當(dāng)前種群中的最優(yōu)個(gè)體。設(shè)preGen為當(dāng)前進(jìn)化代數(shù)，maxGen為最大進(jìn)化代數(shù)，m為解連續(xù)為得到改進(jìn) (即無效進(jìn)化)的進(jìn)化代數(shù)，無效進(jìn)化代數(shù)的上限為M(預(yù)先給定的正整數(shù))，假定進(jìn)化尚未結(jié)束且無效進(jìn)化代數(shù)未達(dá)到上限 (即preGen＜maxGen，m ＜M)。設(shè)Θ =(θ1，θ2，…，θn)T為當(dāng)前種群中的最優(yōu)個(gè)體。接著，對(duì)Θ進(jìn)行更新，當(dāng)求解最小值時(shí)，只有沿著與目標(biāo)函數(shù)負(fù)梯度方向成銳角的方向搜索，目標(biāo)函數(shù)值才有可能下降。為此，根據(jù)目標(biāo)函數(shù)的梯度信息設(shè)計(jì)量子進(jìn)化擾動(dòng)參數(shù)βi，i=1，2，…，n，βi按式 (20)選取，其中▽f(θi)為f在Θ處對(duì)θi的偏導(dǎo)數(shù)，若f的偏導(dǎo)數(shù)不存在，則用f在Θ的某個(gè)充分小鄰域內(nèi)的任意點(diǎn)對(duì)θi的函數(shù)值變化率來代替，D為預(yù)先給定的大于1的常數(shù)。

Θ 的第i個(gè)基因 θi的量子旋轉(zhuǎn)門的旋轉(zhuǎn)角 Δθi按式 (21)選取，其中 θ*i=4θi(1 － θi)(i=1，2，…，n)是Logistic映射產(chǎn)生的混沌序列。

θ'i如式 (18)所示，Θ的第i個(gè)基因按式 (19)更新，其中θi″是Θ的第i個(gè)基因的新值。

通過此方法，當(dāng)前種群中的最優(yōu)個(gè)體一般會(huì)沿著目標(biāo)函數(shù)負(fù)梯度方向成銳角的方向進(jìn)化，有利于引導(dǎo)整個(gè)種群朝著全局最優(yōu)解的方向進(jìn)化。

2.5 抑制早熟策略

假定進(jìn)化尚未結(jié)束且無效進(jìn)化代數(shù)達(dá)到上限，則意味著進(jìn)化陷入局部最優(yōu)，出現(xiàn)了早熟現(xiàn)象。采用Logistic映射對(duì)當(dāng)前種群全部個(gè)體的基因進(jìn)行混沌變異，以改變種群的個(gè)體分布，避免早熟現(xiàn)象。設(shè)(θk1，θk2，…，θkn)T為當(dāng)前種群的第k個(gè)個(gè)體，k=1，2，…，N 。個(gè)體k的第i個(gè)基因按式 (22)更新，其中θ'ki為個(gè)體k的第i個(gè)基因的新值。

2.6 算法流程

1)設(shè)定參數(shù):種群規(guī)模N，最大進(jìn)化代數(shù)maxGen，正常數(shù)D，最大無效進(jìn)化代數(shù)M，基本旋轉(zhuǎn)角 θ0。

2)初始化種群:置進(jìn)化代數(shù)preGen=0，無效進(jìn)化代數(shù)m=0，按2.2節(jié)方法產(chǎn)生初始種群。

3)對(duì)種群中的所有個(gè)體按式 (1)解碼得到對(duì)應(yīng)的可行解，找出當(dāng)前種群中的最優(yōu)個(gè)體。

4)若preGen=0，置當(dāng)前種群中的最優(yōu)個(gè)體為全局最優(yōu)個(gè)體B(如果當(dāng)前種群中的最優(yōu)個(gè)體不止一個(gè)，則任選一個(gè)作為全局最優(yōu)個(gè)體，下同)。

5)若preGen＜maxGen，轉(zhuǎn)至下一步;否則輸出全局最優(yōu)個(gè)體B對(duì)應(yīng)的解及對(duì)應(yīng)的目標(biāo)函數(shù)值fB，算法結(jié)束。

6)對(duì)于preGen＞0，若當(dāng)前種群中的最優(yōu)個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值小于fB，置當(dāng)前種群中的最優(yōu)個(gè)體為B，并置m=0;否則置m=m+1。

7)采用2.3節(jié)所述方法更新當(dāng)前種群中的非最優(yōu)個(gè)體。

8)如果m＜M，采用2.4節(jié)方法對(duì)當(dāng)前種群中的最優(yōu)個(gè)體進(jìn)行更新;否則按2.5節(jié)所述方法對(duì)當(dāng)前種群中的每個(gè)個(gè)體基因進(jìn)行混沌變異。

9)preGen＜preGen+1，轉(zhuǎn)步驟3)。

3 算例仿真

3.1 算例

以http://www.bernabe.dorronsoro.es/vrp/網(wǎng)站上的C101的50個(gè)客戶點(diǎn)位置作為某物流公司帶服務(wù)的客戶位置，原車場(chǎng)作為第1個(gè)車場(chǎng)，調(diào)換原車場(chǎng)的縱坐標(biāo)和橫坐標(biāo)位置，作為第2個(gè)車場(chǎng)。車場(chǎng)信息表如表1所示，客戶信息表如表2所示，這些客戶主要需要兩大類貨物 (I和II)或者傾向于某一類，其中每類貨物有多種型號(hào)。每個(gè)車場(chǎng) (配送中心)都有這兩大類貨物。每輛車的最大配送里程為180個(gè)里程單位?？蛻?6、19、49、40、20及22的時(shí)間窗為 ［8∶00 10∶00］，其余客戶的時(shí)間窗為［8∶00 11∶30］。為保證模型有可行解，將兩個(gè)車場(chǎng)的時(shí)間窗設(shè)為 ［8∶00 12∶00］，車輛平均速度為50個(gè)速度單位。

表1 車場(chǎng)信息

表2 客戶信息

客戶 坐標(biāo) 需求關(guān)系 單位重量/kg 客戶 坐標(biāo) 需求關(guān)系 單位重量/kg 13 (22，75) λ113 =30 λ113 =3 38 (0，40) λ318 =20，λ328 =40 g318 =2，g328 =1 14 (22，85) λ114 =20，λ124 =30 g114 =2，g124 =3 39 (0，45) λ319 =120，λ329 =20 g319 =1，g329 =2 15 (20，80) λ115 =20，λ125 =100 g115 =2，g125 =2 40 (36，18) λ410 =60 g410 =2 16 (20，85) λ126 =30 g126 =1 41 (35，32) λ411 =30，λ421 =10 g411 =2，g421 =3 17 (18，75) λ117 = λ127 =10 g117 =g127 =3 42 (33，32) λ412 = λ422 =100 g412 =2，g422 =1 18 (15，75) λ118 =50，λ128 =40 g118 =2，g128 =3 43 (33，35) λ413 =30 g413 =2 19 (15，80) λ119 =10，λ129 =20 g119 =4，g129 =2 44 (32，20) λ424 =10 g424 =4 20 (30，50) λ210 =40 g210 =3 45 (30，30) λ415 =60，λ425 =20 g415 =1，g425 =3 21 (30，56) λ211 =20，λ221 =10 g211 =2，g221 =4 46 (34，25) λ426 =20 g426 =4 22 (28，52) λ212 =10，λ222 =20 g212 =2，g222 =2 47 (30，35) λ417 =20，λ427 =100 g417 =1，g427 =1 23 (14，66) λ213 =30 λ213=3 48 (36，40) λ418=30 g418 =4 24 (25，50) λ214 =20，λ224 =30 g214 =2，g224 =3 49 (48，20) λ419 =200，λ429 =10 g419 =3，g429 =5 25 (22，66) λ215 =20，λ225 =10 g215 =2，g225 =2 50 (26，32) λ520 =20 g520 =4

3.2 參數(shù)設(shè)置及結(jié)果分析

在Intel(R)Core?i5 CPU 3.0GHz、內(nèi)存為8.0G、安裝系統(tǒng)為Windows7的PC機(jī)上采用Matlab R2010b編程實(shí)現(xiàn)。針對(duì)VRP模型和IVRP模型，首先采用HCQEA對(duì)這兩種模型求解，然后采用另外兩種算法對(duì)IVRP求解，各運(yùn)行算法20次。

HCQEA參數(shù)設(shè)計(jì):N=20，maxGen=200，D=1 000，θ0=0.005;QEA參數(shù)設(shè)計(jì):可行解的每個(gè)分量用20個(gè)二進(jìn)制位表示，群體規(guī)模m=20，maxGen=200，基本旋轉(zhuǎn)角自適應(yīng)遺傳算法 (adaptive genetic algorithm，AGA)參數(shù)設(shè)計(jì):種群規(guī)模m=20，最大迭代次數(shù)Gen=200，交叉概率pc=0.9，變異概率pm=0.04，采用最佳保留選擇法選擇算子，多點(diǎn)交叉，均勻變異。

圖1 MDVRPHTW配送網(wǎng)絡(luò) (非關(guān)聯(lián))

圖2 MDVRPHTW配送網(wǎng)絡(luò) (關(guān)聯(lián))

表3 MDVRPHTW的具體配送信息 (非關(guān)聯(lián))

表4 MDIVRPHTW的具體配送信息 (關(guān)聯(lián))

求解MDVRPHTW和MDIVRPHTW的配送網(wǎng)絡(luò)圖如圖1和圖2所示。具體配送信息分別如表3和表4所示，可見MDVRPHTW需要使用6輛車，MDIVRPHTW使用了5輛車，減少了一輛車的使用，且總成本降低了27.75%，所以該模型的提出是有意義的。

MDIVRPHTW的一次優(yōu)化過程如圖3所示，HCQEA在第110代求得的總成本為205.69個(gè)費(fèi)用單位，QEA在第170代求得的總成本為213.52個(gè)費(fèi)用單位，AGA在第120代求得的總成本是213.52個(gè)費(fèi)用單位?？梢?，雖然AGA能較早收斂，可是易陷入局部最優(yōu)，而HCQEA的求解速度和得到的解結(jié)果總體來說優(yōu)于另外兩種算法，這主要?dú)w因于引入了混合混沌搜索策略，提高了算法的收斂速度和全局搜索能力。

圖3 MDIVRPHTW的一次優(yōu)化過程

4 結(jié)語

文中提出了引入混合混沌策略的混合混沌量子進(jìn)化算法?？紤]了關(guān)聯(lián)因素對(duì)物流配送的影響，提出了帶多種擴(kuò)展特征 (考慮多車型、客戶和車場(chǎng)硬時(shí)間窗等約束)的IVRP模型，通過HCQEA、AGA和QEA對(duì)模型求解的結(jié)果相比較，證明其優(yōu)越性，也體現(xiàn)出提出模型的有效性，研究更大規(guī)模問題模型及包含多種擴(kuò)展特性 (次序關(guān)聯(lián)、不對(duì)稱、隨機(jī)需求、多周期性、需求可拆分、同時(shí)取送貨、開放式、服務(wù)優(yōu)先級(jí)等)的IVRP及其求解算法將是今后的研究方向。

［1］Azi N，Gendreau M，Potvin J Y．An adaptive large neighborhood search for a vehicle routing problem with multiple routes［J］．Computers＆Operations Research，2014，41:167－173．

［2］Michallet J，Prins C，Amodeo L，et al．Multi－start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services［J］．Computers＆ Operations Research，2014，41:196－207．

［3］Mohammed A M，Elhefhawy N A，El－Sherbiny M M，et al．Quantum crossover based quantum genetic algorithm for solving non－linear programming［C］//Informatics and Systems(INFOS)，2012 8th International Conference on．IEEE，2012:BIO －145－BIO－153．

［4］蔡延光，張敏捷，蔡顥，等．混合混沌量子進(jìn)化算法［J］．系統(tǒng)工程理論與實(shí)踐，2012，32(10):2207－2214．

［5］Cui L，Wang L，Deng J，et al．A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem［J］．Mathematical Problems in Engineering，2013:17．

［6］Wang L，Kowk S K，Ip W H．Design of an improved quantum－inspired evolutionary algorithm for a transportation problem in logistics systems［J］．Journal of Intelligent Manufacturing，2012，23(6):2227－2236．

［7］葛顯龍，王旭，代應(yīng)．基于混合量子遺傳算法的隨機(jī)需求車輛調(diào)度問題［J］．系統(tǒng)工程，2011，29(3):53－59．

［8］葛顯龍，許茂增，王偉鑫．多車型車輛路徑問題的量子遺傳算法研究［J］．中國管理科學(xué)，2013，1:125－133．

［9］Zhang J，Wang W，Zhao Y，et al．Multiobjective quantum evolutionary algorithm for the vehicle routing problem with customer s atisfaction［J］．Mathematical Problems in Engineering，2012:19．

［10］Michallet J，Prins C，Amodeo L，et al．Multi－ start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services［J］．Computers＆ operations research，2014，41:196－207．

［11］Crispin A，Syrichas A．Quantum Annealing Algorithm for Vehicle Scheduling［C］//Systems，Man，and Cybernetics(SMC)，2013 IEEE International Conference on．IEEE，2013:3523－3528．

［12］Zheng T，Yamashiro M．Quantum －inspired differential evolutionary algorithm for permutative scheduling problems［M］．Rijeka，Croatia:In-Tech．Evolutionary Algorithms，2011，109 －132．

［13］Zhou L，Li R，Li Q．Research on Vehicle Routing Problem Based on Quantum Genetic Algorithm［C］//ICLEM 2010:Logistics For Sustained Economic Development:Infrastructure，Information，Integration．ASCE，2010:2965－2971．

［14］Ning T，Guo C．Using hybrid quantum algorithm to solve VRPTW［C］//Intelligent Control and Information Processing(ICICIP)，2012 Third International Conference on．IEEE，2012:59－62．

［15］彭典軍．車輛路徑問題的量子進(jìn)化算法研究［D］．杭州:浙江工業(yè)大學(xué)，2009．

［16］劉勇，馬良，寧愛兵．給定限期條件下應(yīng)急選址問題的量子競(jìng)爭(zhēng)決策算法［J］．運(yùn)籌與管理，2011，20(3):66－71．

［17］寧濤．混合量子算法在車輛路徑問題中應(yīng)用的研究［D］．大連:大連海事大學(xué)，2013．

［18］蔡蓓蓓，張興華．混合量子遺傳算法及其在VRP中的應(yīng)用［J］．計(jì)算機(jī)仿真，2010，27(7):267－334．

［19］李川．基于混合量子進(jìn)化算法的隨機(jī)車輛路徑問題的研究［D］．杭州:浙江工業(yè)大學(xué)，2011．

［20］任偉．基于量子免疫算法的車輛調(diào)度問題的優(yōu)化［J］．計(jì)算機(jī)科學(xué)，2013，40(5):233－236．

［21］吳斌，錢存華，董敏，等．具有同時(shí)集送貨需求車輛路徑問題的混沌量子進(jìn)化算法研究［J］．2010，25(3):383－387．

［22］趙燕偉，李川，張景玲，等．一種新的求解多目標(biāo)隨機(jī)需求車輛路徑問題的算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18(3):523－530．

［23］李熠，馬良．用量子蟻群算法求解大規(guī)模旅行商問題［J］．上海理工大學(xué)學(xué)報(bào)，2012，34(4):355－358．