周 蓉 沈維蕾

合肥工業(yè)大學(xué)機械工程學(xué)院，合肥，230009

0 引言

裝卸一體化車輛路徑問題(vehicle routing problem with simultaneous pickup and delivery,VRPSPD)是車輛路徑問題的一類重要擴展。該問題涉及的客戶同時具有送貨和取貨兩種需求，且要求服務(wù)車輛將產(chǎn)品配送至客戶的同時從該客戶處取走其他物品，如汽車、家電等行業(yè)制造商將新產(chǎn)品運送至客戶，同時回收客戶的廢舊產(chǎn)品[1]。該問題不受送貨與取貨先后順序的限制，能有效減少車輛空載、降低運作成本并提高服務(wù)效率[2]。但是雙重需求及波動變化的車輛承載特征使得問題結(jié)構(gòu)明顯不同于單一需求的車輛路徑問題，它涉及更為復(fù)雜的客戶分配和車輛載重量界定，求解難度更大[3]。

國內(nèi)外有關(guān)VRPSPD的文獻較多，求解目標多以最小化車輛行駛距離為主，但現(xiàn)實中可能存在由租賃費用產(chǎn)生的單次派出成本，需要綜合考慮單次派車成本和配送路徑成本。雖然少數(shù)文獻增加了車輛數(shù)目方面的分析，但缺乏對總配送成本、車輛數(shù)目、車輛行駛距離等多種目標的系統(tǒng)性分析。如TASAN等[4]以最小化車輛行駛距離為目標，提出一種基于遺傳算法的方法來求解VRPSPD，并利用Augerat標準數(shù)據(jù)集部分算例進行驗證，結(jié)果證明該方法較數(shù)學(xué)規(guī)劃工具Cplex具有更好的穩(wěn)定性。NAGY等[5]提出采用插入式啟發(fā)式方法求解單個/多個車場的帶回程車輛路徑問題，并設(shè)計了包含VRPSPD問題在內(nèi)的5類標準數(shù)據(jù)集。柳毅等[6]提出采用改進人工魚群算法求解相同目標問題，并利用NAGY標準數(shù)據(jù)集中的10組算例進行仿真分析，結(jié)果證明該算法雖然計算時間較長，但尋優(yōu)性能較文獻[5]的插入式啟發(fā)式算法更加優(yōu)越。彭春林等[7]在求解VRPSPD問題時增加了派出車輛數(shù)目標，但對算法的性能分析只針對NAGY標準數(shù)據(jù)集中的兩組算例，算法驗證缺乏普適性。龍磊等[8]針對相同目標問題提出采用一種粗粒度并行遺傳算法進行求解，并以NAGY標準數(shù)據(jù)集中的14組算例進行驗證，證明該算法在大部分實例上超過了已知最優(yōu)解。TANG等[9]以最小化車輛數(shù)目、最小化車輛行駛距離為目標，提出采用一種基于局域迭代搜索的禁忌搜索算法進行求解，并以多個標準測試集進行了算法準確性和有效性的驗證。WASSAN等[10]提出一種能自動調(diào)節(jié)禁忌長度的自適應(yīng)禁忌搜索算法，結(jié)果表明該算法性能在絕大部分算例上優(yōu)于文獻[9]的禁忌搜索算法。WANG等[11]以最小化總配送成本、最小化車輛數(shù)目、最小化車輛行駛距離為目標，并考慮時間窗約束，提出采用聯(lián)合進化遺傳算法進行求解，結(jié)果表明該方法較基本遺傳算法和數(shù)學(xué)規(guī)劃工具Cplex具有更好的尋優(yōu)性能。

上述研究表明，VRPSPD問題的優(yōu)化目標多以配送距離為主，部分文獻考慮了配送車輛數(shù)目，幾乎沒有文獻將配送距離、車輛數(shù)目及配送成本進行系統(tǒng)性分析；求解算法大多集中在以經(jīng)典C-W節(jié)約法為基礎(chǔ)的啟發(fā)式方法和以群體智能為基礎(chǔ)的元啟發(fā)方法。遺傳算法(genetic algorithm，GA)作為一種魯棒性較強的元啟發(fā)方法，在許多車輛路徑與調(diào)度問題的求解應(yīng)用中已被證明具有良好的優(yōu)化性能[4,7-8,11]。GA在搜索處理后期容易出現(xiàn)兩難窘境：要么收斂速度較慢耗時長，要么早熟收斂陷入局部最優(yōu)，因此，必須在進化過程中改善種群的多樣性和優(yōu)良基因的遺傳性，以提高算法整體搜索性能[7,11]。受到該思想的啟發(fā)，本文將包含多樣性種群和高質(zhì)量種群的雙種群并行策略引入基本遺傳算法，提出一種自適應(yīng)并行遺傳算法求解包含多種目標的VRPSPD問題，并通過算例仿真和結(jié)果對比驗證所提算法的可行性和有效性。

1 問題描述與模型

VRPSPD問題可以描述如下：物流中心擁有一定數(shù)量的相同車輛，車輛從配送中心出發(fā)，在一定時間內(nèi)完成確定數(shù)量客戶集的送貨與取貨后返回物流中心。每個客戶的送貨與取貨由同一車輛同時完成。要求合理安排車輛配送路線，在派出車輛數(shù)目最小、車輛行駛距離最短的情況下，實現(xiàn)總配送成本最小。采用符號體系描述如下：假設(shè)物流中心共有N個客戶，采用i、j表示客戶編號(i，j=1，2，…，N)，0表示物流中心；Z為總配送成本；客戶的送貨量和取貨量分別為di、pi；客戶之間的距離為cij，物流中心到客戶i的距離為c0i；車輛單位距離行駛成本為g，單車指派成本為f，最大裝載量為Q；車輛總數(shù)為K，車輛k(k=1，2，…，K)離開客戶i時車上載重量為Uik，車輛的最大行駛距離為L。

根據(jù)上述描述，建立VRPSPD問題的混合整數(shù)規(guī)劃模型如下：

(1)

滿足約束條件：

(2)

(3)

(4)

(5)

?i=0,1,…,N;k=1,2,…,K

(6)

(7)

(8)

(9)

(10)

Uik≥0 ?i=0,1,…,N;k=1,2,…,K

(11)

式(1)考慮了車輛指派成本、運輸路徑成本的總配送成本Z最小目標，隱含車輛數(shù)目最小、車輛行駛距離最短兩個子目標；式(2)確保每個客戶只被服務(wù)一次且僅由一輛車服務(wù)；式(3)確保使用車輛數(shù)不超過車輛總數(shù)K；式(4)為流量守恒式，即到達和離開每個客戶的車輛相同；式(5)～式(8)為容量約束，式(5)表示當xijk=1時，確保車輛k在離開客戶i后，服務(wù)客戶j時車上載重量不超過車容量Q；式(6)表示任何一輛車服務(wù)的所有客戶的貨物都是由物流中心配送的，保證車輛從物流中心出發(fā)時的載貨量等于其所服務(wù)的客戶的送貨需求量之和；式(7)、式(8)分別確保每輛車服務(wù)的所有客戶送貨需求量總和、集貨需求量總和均不超過車容量Q；式(9)為車輛最大行程約束；式(10)和(11)為決策變量屬性。

2 自適應(yīng)并行遺傳算法

2.1 雙種群并行策略

為解決GA在搜索過程中出現(xiàn)的兩難窘境，本文提出一種包含多樣性種群和高質(zhì)量種群的雙種群并行策略，其中多樣性種群以改善種群多樣性為主要目的，高質(zhì)量種群以強化尋優(yōu)能力為主要目的。雙種群并行策略框架結(jié)構(gòu)見圖1。該策略通過對雙種群同時執(zhí)行不同的遺傳操作(針對多樣性種群執(zhí)行多樣性交叉變異操作、針對高質(zhì)量種群執(zhí)行自適應(yīng)交叉變異操作)，并針對雙種群中最優(yōu)個體執(zhí)行特殊變異和后優(yōu)化的局域搜索，使得算法在擴大搜索空間的同時能夠進行深度搜索并保持優(yōu)良基因的遺傳性狀，從而有效避免陷入局部最優(yōu)。

圖1 雙種群并行策略框架結(jié)構(gòu)Fig.1 Frame structure of bi-group parallel strategy

2.2 編碼及解碼

染色體結(jié)構(gòu)為N個1～N之間互不重復(fù)的自然數(shù)排列(N為客戶總數(shù))，該排列是一條以自然數(shù)序列表示客戶服務(wù)順序的無分段大路徑[12-13]。染色體解碼采用基于深度優(yōu)先搜索的大路徑分割方法[14]，考慮車輛裝載能力、最大行駛里程等約束。

2.3 種群初始化

由于初始解質(zhì)量對遺傳算法求解的速度和質(zhì)量影響較大，本文以C-W節(jié)約法為基礎(chǔ)，設(shè)計3種基于雙重需求的啟發(fā)式種群初始化方法，并采用大部分個體隨機生成、部分優(yōu)良個體采用種群初始化方法生成的方式得到初始種群。隨機產(chǎn)生方法遵循兩條原則：第一，不允許產(chǎn)生相同個體；第二，隨機產(chǎn)生個體與已產(chǎn)生個體的目標值之差應(yīng)不小于某一數(shù)值Δ[13]。

2.3.1基于雙重需求的最低成本插入法

C-W節(jié)約法根據(jù)待插入位置所能帶來的成本(或距離)節(jié)約值中的最大值來決定最佳插入位置[15]。為降低車輛超載率并提高車輛裝載率，VRPSPD客戶服務(wù)排序須考慮集貨量與送貨量之間的關(guān)系，通常將具有較大配送需求、較小取貨需求的客戶提前安排，或?qū)⒕哂休^大取貨需求、較小送貨需求的客戶延后安排。本文設(shè)計了一種基于雙重需求的最低成本插入法(簡稱PDCW法)，新的節(jié)約值根據(jù)取貨量與送貨量之間的關(guān)系對客戶在不同插入點產(chǎn)生的空間效益差異影響進行定義，其計算公式為

(12)

Sij=c0i+c0j-cij

2.3.2基于雙重需求的多參數(shù)最低成本插入法

PDCW法雖然考慮了客戶需求量對改進節(jié)約值的不同影響，但未考慮不同節(jié)點之間運輸費率或運輸距離對節(jié)約值的權(quán)重影響。MESTER等[16]提出了一種改進OSMAN節(jié)約值[17]的多參數(shù)最低成本插入準則，插入點的成本節(jié)約值受到插入點與其緊前、緊后節(jié)點之間成本(或距離)的權(quán)重影響。受此啟發(fā)，本文設(shè)計了一種基于雙重需求的多參數(shù)最低成本插入法(PDMPCW法)，通過同時考慮客戶需求量及新弧對節(jié)約值的影響程度來改進成本節(jié)約值。改進后的成本節(jié)約值計算公式為

(13)

2.3.3基于雙重需求的多參數(shù)隨機最低成本插入法

為了在搜索空間中產(chǎn)生多個較為分散且質(zhì)量優(yōu)良的初始染色體，本文提出基于雙重需求的多參數(shù)隨機最低成本插入法(PDMPRCW法)。該方法以PDMPCW法為基礎(chǔ)，先將染色體前面k個客戶固定，后面N-k個客戶采用PDMPCW法根據(jù)最大成本節(jié)約值準則插入。k的取值根據(jù)客戶總數(shù)N，按一定百分比可以取不同的整數(shù)值，如N=34時，k按0.3N,0.4N,…,0.9N進行向上取整，將分別得到固定前11、14、17、21、24、28、31個客戶的7條染色體。

2.4 適應(yīng)度值

總配送成本同時受到車輛派出數(shù)量和配送路徑距離的影響。相比具有較低車輛派出數(shù)量的父代，優(yōu)良子代更容易從具有較短配送距離的父代染色體中遺傳優(yōu)良基因。為有效避免早熟收斂并體現(xiàn)不同染色體的配送路徑距離在整個種群中的影響，本文采用配送路徑距離在整個種群中的評級，同時考慮種群大小的方式確定適應(yīng)度值。適應(yīng)度值的計算公式為

FitV(x)=PS-Rank(x)

(14)

其中，F(xiàn)itV(x)表示染色體x的適應(yīng)度值，PS表示種群大小，Rank(x)表示染色體x的配送路徑距離在整個種群中的評級，即配送路徑距離在種群中按從小到大排序后的級別。如染色體x的配送路徑距離在種群中的排序為5，則Rank(x)=5。

2.5 交叉操作

交叉操作是產(chǎn)生新個體并將優(yōu)良基因遺傳給子代的主要方法，是決定算法收斂性能的關(guān)鍵。針對多樣性種群，本文采用傳統(tǒng)的部分匹配交叉方式(partially mapped crossed，PMX)，為更大程度地提高種群多樣性，直接以父代染色體作為交叉對象。針對高質(zhì)量種群，本文采用邊重組交叉算子和PTL片段交叉算子。

邊重組交叉算子是由STARKWEATHER等[18]提出的一種強化父代路徑上邊之間鄰接關(guān)系遺傳性狀的個體交叉方式，具有較好的基因繼承特性。文獻[7]曾提出一種改進邊重組交叉算子并將其用于求解VRPSPD，該算子采用概率方式選擇鄰接節(jié)點，在強化子代遺傳性狀的同時保證了種群多樣性。本文采用該改進邊重組交叉算子[7]，以染色體解碼后的路徑集合為父體產(chǎn)生對應(yīng)鄰接表，依次隨機選擇染色體中的客戶節(jié)點，從鄰接表中選擇其前繼節(jié)點及(或)后繼節(jié)點，最終形成新的染色體。

由于兩個交叉父體可能相同，本文設(shè)計一種PTL片段交叉，使相同序列交叉后得到不同的新序列。不同于直接以染色體交叉的PTL兩點交叉[19]，PTL片段交叉以父體分割后的路徑集合為交叉對象，隨機地選擇屬于某一路徑的客戶作為交叉片段，交叉時將所選片段分別置于對方的前面，消去與交叉片段相同的客戶節(jié)點，形成新的子代個體。具體交叉過程見圖2。

圖2 PTL片段交叉示意圖Fig.2 Schematic diagram of PTL segment crossover

2.6 變異操作

為擴大個體搜索空間并在其附近進行深度探索，算法對染色體執(zhí)行特殊變異。特殊變異包含兩部分內(nèi)容：去除重插入變異、兩點互換變異。特殊變異本質(zhì)上是對個體進行局域深度搜索，算法中主要用于高質(zhì)量種群中的精英個體。

去除重插入變異是一種較大程度上的變異。變異時，先將父代染色體解碼后的路徑集合去除部分客戶，然后以O(shè)sman最大成本插入準則依次重新插入所去除客戶后形成的子代染色體。

兩點互換變異以染色體分割后的兩條路徑為父體，分別隨機選擇一定數(shù)量的節(jié)點形成多個節(jié)點對；針對各節(jié)點對，以O(shè)sman最大成本節(jié)約插入準則為依據(jù)進行交換，最終選擇具有最大成本節(jié)約值的節(jié)點對執(zhí)行變異并形成子代個體。

2.7 選擇操作

分級選擇法是一種防止早熟收斂而設(shè)計的適應(yīng)度值比例選擇法。精英保留選擇法將種群中最優(yōu)個體保留直接進入下一代，可以有效保證算法尋優(yōu)性能。算法在兩個種群中同時采用精英保留選擇法和分級選擇法，確保在擴大搜索空間、加快搜索速度的同時提高全局搜索質(zhì)量。

2.8 自適應(yīng)策略

遺傳算法搜索性能很大程度上受到交叉概率和變異概率的影響，取值過大容易破壞群體中的優(yōu)良模式；取值過小容易導(dǎo)致產(chǎn)生新個體的能力變差，導(dǎo)致過早收斂。本文采用一種自適應(yīng)策略調(diào)整高質(zhì)量種群的交叉概率和變異概率，以尋求保護種群優(yōu)秀性狀得以遺傳與避免早熟收斂兩者之間的平衡，其交叉概率Pc和變異概率Pm分別為[20]

(15)

(16)

2.9 算法整體流程

自適應(yīng)并行遺傳算法試圖從搜索空間的廣度及深度兩個維度進行擴大搜索，通過引入多樣性種群和高質(zhì)量種群的雙種群并行策略，并針對高質(zhì)量種群中的個體進行自適應(yīng)遺傳操作，以進一步提高高質(zhì)量種群的尋優(yōu)性能。算法流程框圖見圖3，詳細步驟如下。

圖3 自適應(yīng)并行遺傳算法流程圖Fig.3 Flowchart of adaptive parallel genetic algorithm

(1)初始化種群參數(shù)PS、交叉概率Pc、變異概率Pm、最大迭代次數(shù)tmax、全局極值連續(xù)未更新最大次數(shù)gsn；

(2)采用2.3節(jié)的種群初始化方法產(chǎn)生初始種群，種群數(shù)目為PS；

(3)將上述初始種群復(fù)制兩個，分別命名為多樣性種群ChromOne和高質(zhì)量種群ChromTwo；令迭代次數(shù)t=0；

(4)如果迭代次數(shù)不超過最大迭代次數(shù)tmax或連續(xù)未更新次數(shù)不超過最大次數(shù)gsn，執(zhí)行以下操作：

①針對多樣性種群：

a.計算種群的目標函數(shù)值、適應(yīng)度值；

b.采用精英保留策略，將種群中目標函數(shù)值最小的個體bestChromOne保存并復(fù)制給高質(zhì)量種群ChromTwo；

c.對種群執(zhí)行多樣性交叉變異操作：PMX交叉和兩點互換變異；

d.更新多樣性種群，即將原精英個體bestChromOne加入交叉操作后的種群，得到多樣性種群子代，此時該種群大小為PS+ 1；

e.計算多樣性種群子代的目標函數(shù)值、適應(yīng)度值；

f.采用分級選擇法，從新種群中選擇PS-1個個體，加上原精英個體bestChromOne，形成新的多樣性種群。

②針對高質(zhì)量種群：

a.計算種群的目標函數(shù)值、適應(yīng)度值；

b.采用精英保留策略，將種群中目標函數(shù)值最小的個體bestChromTwo保存；

c.對種群所有個體執(zhí)行自適應(yīng)交叉操作：改進邊重組交叉或PTL片段交叉；

d.對交叉后的種群所有個體執(zhí)行自適應(yīng)兩點互換變異操作；

e.對兩個種群的原精英個體bestChromOne、bestChromTwo執(zhí)行特殊變異；

f.將經(jīng)過步驟e后得到的兩個新精英個體加入經(jīng)過步驟d后得到的種群中，得到高質(zhì)量種群子代，此時該種群大小為PS+ 1 + 1；

g.計算高質(zhì)量種群子代的目標函數(shù)值及適應(yīng)度值，找出目標函數(shù)值最小的精英個體，更新bestChromTwo；

h.采用分級選擇法，從高質(zhì)量種群子代中選擇PS-1個個體，加上精英個體bestChromTwo，最終形成新的高質(zhì)量種群。

③對于兩個種群中的精英個體bestChromOne、bestChromTwo，分別執(zhí)行特殊變異的后優(yōu)化操作，如果后優(yōu)化操作使得該精英個體的目標函數(shù)值進一步降低，則更新該精英個體；否則不更新。選擇目標函數(shù)值較小的精英個體作為全局最優(yōu)個體。

④t←t+1，轉(zhuǎn)步驟①。

(5)輸出全局最優(yōu)個體及其目標函數(shù)值，以及最優(yōu)路徑集合。

3 算例測試與比較

為驗證算法尋優(yōu)性能，選取2個算例進行尋優(yōu)測試。算法采用MATLAB R2009b編程語言實現(xiàn)，微機運行環(huán)境為：CPU i5-2520，主頻2.5 GHz，內(nèi)存4 GB。

3.1 算例選取及參數(shù)設(shè)置

3.1.1算例選取

選取Augerat標準測試集中24組數(shù)據(jù)作為算例1，用于驗證小規(guī)模情況下以總配送距離為目標時算法對模型(式(1))的求解精度。Augerat測試集分為A、B、P三類數(shù)據(jù)，從客戶分布、客戶需求量及車容量等方面體現(xiàn)VRPSPD問題的不同要求，對算法求解精度要求較高。算例1中除客戶集貨需求服從[0，26]的均勻分布[4]外，其余數(shù)據(jù)均采用文獻[21]中的基礎(chǔ)數(shù)據(jù)。

選取NAGY標準測試集中12組數(shù)據(jù)作為算例2，用于驗證大規(guī)模情況下，以總配送成本為總目標、以車輛數(shù)最少和總配送距離最短為子目標時算法對模型(式(1))的求解精度，同時也用于分析雙種群并行策略、種群初始化方法及自適應(yīng)遺傳算子對算法性能的影響。

3.1.2參數(shù)設(shè)置

試驗發(fā)現(xiàn)，種群大小PS、最大迭代次數(shù)tmax在求解精度及計算耗時等方面對算法整體性能影響較大。為尋求種群大小和最大迭代次數(shù)的最佳組合，本文選取7個不同規(guī)模問題(客戶數(shù)為15～199)作為參數(shù)試驗算例，每個算例以不同參數(shù)組合獨立運行20次。表1給出不同參數(shù)組合情況下本文計算最優(yōu)值與文獻最優(yōu)值的偏差百分比，表2給出不同參數(shù)組合情況下平均計算時間。兩表中“均值”一欄是指在同一參數(shù)組合下7個算例結(jié)果的算術(shù)平均值。表1中偏差百分比的計算式為本文最優(yōu)值與文獻最優(yōu)值之差再除以文獻最優(yōu)值，最優(yōu)值的取法如下：①當本文所得車輛數(shù)與文獻車輛數(shù)相同時，最優(yōu)值取為行駛距離；②當本文所得車輛數(shù)比文獻車輛數(shù)小，但行駛距離比文獻距離大時，最優(yōu)值取為車輛數(shù)取，否則最優(yōu)值取為行駛距離；③當本文所得車輛數(shù)比文獻車輛數(shù)大時，最優(yōu)值取為車輛數(shù)。

表1 不同參數(shù)組合最優(yōu)值偏差百分比統(tǒng)計

表2 不同參數(shù)組合最優(yōu)方案計算時間統(tǒng)計

對表1中“均值”數(shù)據(jù)進行分析發(fā)現(xiàn)，在上述9種參數(shù)組合情況下，除種群大小為50外的其余6種組合的偏差百分比均為負數(shù)，說明本文算法在求解上述7個算例時均能得到比文獻算法更好的結(jié)果。其中，150/1 000組合的偏差百分比(-11.9%)最小，說明種群數(shù)越大、迭代次數(shù)越大，計算結(jié)果越好，但由表2知其計算消耗的平均時間也最長。因此，通過對表1、表2統(tǒng)計數(shù)據(jù)進行綜合分析，最終選擇以較少計算時間產(chǎn)生較好計算結(jié)果的150/300為最佳參數(shù)組合方式。

以種群PS=150、tmax=300為試驗基礎(chǔ)，最終確定其他參數(shù)為：交叉概率Pc=0.8，變異概率Pm=0.03， 全局極值連續(xù)未更新最大次數(shù)gsn=100。

3.2 結(jié)果分析

3.2.1算例1分析

表3 算例1計算結(jié)果比較

以算例1的24組算例為基礎(chǔ)數(shù)據(jù)，采用本文算法進行20次獨立仿真計算，得到各算例的最優(yōu)行駛距離。將計算得到的最優(yōu)行駛距離與文獻[4]采用基于遺傳算法的方法(GA based approach，GAA)所得到的最優(yōu)行駛距離進行比較，對比分析情況見表3。表中加粗字體表示行駛距離最優(yōu)值?？梢?，GAA算法在求解A-n38-k5.vrp、A-n39-k5.vrp、B-n39-k5.vrp、P-n23-k8.vrp四個算例時，能取得比本文算法更優(yōu)的行駛距離。而本文算法在24組算例中，除4個算例的最優(yōu)行駛距離大于GAA算法的結(jié)果外，其余20組算例均得到更好的近似最優(yōu)解。在這20組算例中，除算例A-n45-k6.vrp的行駛距離與GAA算法結(jié)果相同外，其余19組算例的決策結(jié)果均優(yōu)于GAA算法。

本文進一步采用t-test顯著性差異檢驗法驗證所提算法的優(yōu)越性。首先采用KS-test檢驗數(shù)據(jù)的正態(tài)分布特性，進行如下KS-test檢驗假設(shè)：

H0表示兩種算法結(jié)果服從正態(tài)分布；

Ha表示兩種算法結(jié)果不服從正態(tài)分布。

設(shè)置置信度為95%，采用SPSS軟件進行“單樣本K-S(1)”檢驗分析，結(jié)果見表4。由于表中兩種算法結(jié)果數(shù)據(jù)的雙側(cè)顯著性取值均大于0.05，因此否定H0假設(shè)并接受Ha假設(shè)，即認為兩種算法結(jié)果均服從正態(tài)分布，可以采用t-test進行顯著性差異驗證。

表4 KS-test檢驗統(tǒng)計分析結(jié)果

進行t-test前，進行如下檢驗假設(shè)：

H0表示兩種算法結(jié)果的均值差等于0；

Ha表示兩種算法結(jié)果的均值差不等于0。

設(shè)置置信度為95%，采用SPSS軟件進行“比較平均值-成對樣本T檢驗”，得到Sig(雙尾)=0.001<0.05?？梢钥闯鼍芙^H0假設(shè)的概率只有0.1%，故接受Ha假設(shè)，即認為兩種算法結(jié)果均值不相等。但這仍然不能證明本文算法結(jié)果的均值小于GAA算法結(jié)果的均值，因此，需要做進一步的單側(cè)t-test檢驗。重新做出如下假設(shè)：

H0表示本文算法結(jié)果均值-GAA算法結(jié)果均值等于-15；

Ha表示本文算法結(jié)果均值-GAA算法結(jié)果均值小于-15。

設(shè)置置信度為95%，采用SPSS軟件進行“比較平均值-成對樣本T檢驗”，得到Sig(單尾)=0.006<0.05?？梢钥闯鼍芙^新H0假設(shè)的概率只有0.6%，因此，接受新Ha假設(shè)，即認為本文算法結(jié)果的均值小于GAA算法結(jié)果均值。

由此可以推斷，本文算法在求解VRPSPD時具有更好的尋優(yōu)能力。此外，由表3中計算時間來看，本文算法在大部分算例運算時消耗時間更少，證明本文算法具有更高的計算效率。

3.2.2算例2分析

以算例2的12組算例為基礎(chǔ)數(shù)據(jù)，采用本文算法進行20次獨立仿真計算，將所得最優(yōu)值與文獻[5]的啟發(fā)式算法、文獻[9]的禁忌搜索算法、及文獻[10]的自適應(yīng)禁忌搜索算法所得最優(yōu)值進行比較，分析結(jié)果見表5，表中加粗字體表示對應(yīng)算例的最優(yōu)值。顯然，文獻[10]的自適應(yīng)禁忌搜索算法比其他兩種算法效果更好。然而，與自適應(yīng)禁忌搜索算法[10]相比，除了CMT7X、CMT7Y、CMT9Y、CMT13X四個算例外，本文算法在求解其余8組算例時均能取得更好的行駛距離，其偏差百分比最大達到-21.3%。此外，本文算法還對6組算例的車輛數(shù)目進行了改進，其偏差百分比最大達到-30%。

表5 算例2計算結(jié)果比較

由于CMT13X、CMT14Y問題部分節(jié)點呈隨機分布、部分節(jié)點呈叢聚式分布，且具有車輛最大行程及節(jié)點裝卸時間限制的諸多特征，使得它們的求解較其余10組問題更為困難。針對這兩個問題，盡管行駛距離比自適應(yīng)禁忌搜索算法大一些，但使用車輛數(shù)較之少1輛。由于車輛指派成本為一個很大的正整數(shù)，故車輛數(shù)目的減少可以大大降低總配送成本。由此可以推斷，本文算法在求解帶指派成本的VRPSPD時具有更好的優(yōu)化性能。

3.2.3算法性能分析

為進一步分析雙種群并行策略、種群初始化方法及自適應(yīng)交叉變異操作對算法性能的影響，選取算例2中CMT8X作為對比分析對象，以種群大小為150、最大迭代次數(shù)為300、交叉概率為0.8、變異概率為0.03的組合參數(shù)，獨立運算20次，選取最優(yōu)近似解進行分析。

采用雙種群并行策略與采用單一種群時的對比情況見圖4。選取兩種單一種群方式與雙種群并行策略進行對比：一種為舍棄多樣性種群、保留高質(zhì)量種群的單一種群方式，另一種為包含小部分高質(zhì)量個體、大部分多樣性個體的單一種群方式，圖4中分別采用ONE_POP_HQ、ONE_POP_DR_HQ表示，雙種群并行策略采用TWO_POP_PARALLEL表示。由圖4可見，單純采用高質(zhì)量種群可以獲取比較好的初始解，但在搜索過程中由于搜索空間變小很容易陷入局部最優(yōu)；包含部分高質(zhì)量個體、大部分多樣性個體的單一種群方式雖然擴大了搜索空間，在一定程度上改善了種群多樣性，但仍然無法跳出局部最優(yōu)。而雙種群并行策略卻能以較少的迭代次數(shù)取得更小的行駛距離，說明本文提出的雙種群并行策略在遺傳算法求解VRPSPD問題時，不僅能有效幫助算法在有限迭代次數(shù)內(nèi)進行廣度與深度的同步探索，而且能有效避免陷入局部最優(yōu)，最終以較短時間快速尋找到近似最優(yōu)解。

圖4 ARALLEL與NO_PARALLEL收斂性對比Fig.4 Comparison of convergence between ARALLEL and NO_PARALLEL

采用2.3節(jié)的種群初始化方法與不采用該方法時的對比情況見圖5。圖例INITIAL_PDCW、INITIAL_PDMPCW、INITIAL_PDMPRCW分別表示單獨采用2.3.1節(jié)、2.3.2節(jié)和2.3.3節(jié)中的初始化方法，圖例INITIAL表示同時采用上述三種初始化方法。圖例NO_INITIAL表示不采用上述初始化種群方法，而以任意產(chǎn)生PS條大路徑序列方式對種群進行初始化?？梢姡贗NITIAL情況下初始行駛距離較INITIAL_PDCW、NO_INITIAL要小很多，但比INITIAL_PDMPCW、INITIAL_PDMPRCW要大一些，這說明，針對具有雙重需求的VRPSPD問題，其初始解質(zhì)量在單純考慮客戶需求量對插入節(jié)點節(jié)約值的影響時最差，在增加考慮不同節(jié)點之間運輸費率或運輸距離對節(jié)約值權(quán)重影響、且不固定客戶節(jié)點時最好，而同時考慮3種初始化方法僅處于中間狀態(tài)。但是，同時考慮3種初始化方法在中后期收斂效果好，行駛距離更小，這說明初始化種群方法對本文算法求解VRPSPD問題的性能具有較大影響，良好的種群初始化方法能促使其收斂加快并保持良好尋優(yōu)能力。

圖5 INITIAL與NO_INITIAL收斂性對比Fig.5 Comparison of convergence between INITIAL and NO_INITIAL

采用自適應(yīng)交叉變異操作與交叉變異概率均恒定不變的對比情況見圖6，圖例分別為ADAPTION、NO_ADAPTION。由圖可見，當交叉變異概率恒定不變時，算法收斂速度慢，容易在階段性收斂后產(chǎn)生停滯從而陷入局部最優(yōu)；而采用適應(yīng)性變動的交叉變異操作能加快收斂速度，提升收斂效果，以較少的迭代次數(shù)搜索到更短的行駛距離。這說明本文提出的自適應(yīng)交叉變異操作在遺傳算法求解VRPSPD問題時，能提高進化早期的全局搜索能力以及進化后期的局部搜索能力，有效提高搜索質(zhì)量。

圖6 ADAPTION與NO_ADAPTION收斂性對比Fig.6 Comparison of convergence between ADAPTION and NO_ADAPTION

4 結(jié)論

裝卸一體化車輛路徑問題是一類具有雙重需求特征的復(fù)雜車輛路徑問題，因其決策目標、決策因素和限制條件較多等特征需要高求解性能的啟發(fā)式方法或元啟發(fā)算法。針對裝卸一體化車輛路徑問題，本文建立了以總配送成本為優(yōu)化目標的混合整數(shù)規(guī)劃模型，提出了求解裝卸一體化車輛路徑問題的自適應(yīng)并行遺傳算法。該算法采用3種基于C-W的改進啟發(fā)式算法產(chǎn)生初始種群，并引入多樣性種群和高質(zhì)量種群的雙種群并行策略，同時采用保留精英及隨著進化過程適應(yīng)性改變交叉變異概率的自適應(yīng)遺傳操作，實現(xiàn)搜索空間在廣度和深度上的同步拓展。針對不同規(guī)模、不同總目標，分別基于兩個算例進行仿真分析。仿真結(jié)果表明，無論是單純以總行駛距離為目標的算例1問題，還是以總配送成本為總目標、以車輛數(shù)最少和總行駛距離最短為子目標的算例2問題，本文提出的自適應(yīng)并行遺傳算法都能以較快的收斂速度找到近似最優(yōu)解，且尋優(yōu)性能強于已有的基于遺傳算法的方法、插入式啟發(fā)式算法、禁忌搜索算法以及自適應(yīng)禁忌搜索算法。由此可見，本文所提算法對具有較大車輛指派成本的物流配送和取貨優(yōu)化問題具有重要的指導(dǎo)意義，同時對離散型組合優(yōu)化問題的進一步研究也具有一定的理論參考價值。