范厚明， 徐振林， 李 陽， 劉文琪， 耿 靜

(大連海事大學 a. 交通運輸工程學院； b. 戰(zhàn)略管理與系統(tǒng)規(guī)劃研究所， 遼寧 大連 116026)

面對激烈的市場競爭，物流配送企業(yè)追求的目標已經(jīng)從僅要求完成配送任務轉(zhuǎn)變?yōu)橐笤诒ＷC配送任務完成的基礎上，通過整合資源，提高資源利用率，降低配送總成本.車輛路徑問題(Vehicle Routing Problem，VRP) 是物流配送企業(yè)運營管理的核心問題，VRP自提出以來，陸續(xù)有研究人員提出各種拓展模型并對其進行了深入研究.經(jīng)典VRP是針對一系列已知地理位置的客戶，設計出滿足一定約束條件的行車路線進行送貨服務(或收貨服務)，以使得整個物流服務過程達到期望的目標(如費用最低、路徑最短等).

隨著業(yè)務的拓展，一些連鎖超市、快遞企業(yè)或快消企業(yè)等為降低遠距離配送引起的高額成本以及提高配送時效，會選擇在某一區(qū)域內(nèi)設有多個配送中心聯(lián)合完成企業(yè)的配送業(yè)務.此類配送模式可歸結(jié)為多中心車輛路徑問題(Multi-depot Vehicle Routing Problem，MDVRP)，MDVRP作為經(jīng)典VRP的一類拓展問題，是工程技術(shù)、經(jīng)濟管理、信息科學等諸多領域內(nèi)很多復雜問題的集中概括和簡化形式，有著重要的實際利用價值.鑒于此，近些年許多研究人員對此類問題進行了深入研究.由于MDVRP屬于非確定性多項式(Non-deterministic Po-lynomial, NP)完全類問題，傳統(tǒng)的精確算法不太適用于較大規(guī)模問題的求解，而各類啟發(fā)式算法則在此方面有著不錯的表現(xiàn)，如Allahyari等[1]應用自適應貪婪隨機算法、Oliveira等[2]應用合作進化算法、Jabir 等[3]應用混合蟻群變鄰域算法對該問題進行了求解；Zhou等[4]對兩級配送網(wǎng)絡的MDVRP進行了研究，并采用多種群遺傳算法進行求解；文獻[5]和[6]分別利用變鄰域算法和量子遺傳算法對多車型MDVRP進行了求解；Mancini[7]利用大規(guī)模鄰域搜索算法對多周期多車型MDVRP進行求解；文獻[8]利用遺傳算法對存在車輛租賃及共享且有時間窗的MDVRP進行了研究；此外，文獻[9]和[10]則分別采用嵌入局部搜索的自適應鄰域選擇算法及粒子群算法對同時取送貨MDVRP進行了深入研究.遺傳算法是一種以自然選擇和遺傳理論為基礎，利用生物進化過程中適者生存規(guī)則和種群內(nèi)部染色體信息隨機交換機制相結(jié)合的方式搜尋全局解的一種概率優(yōu)化算法.僅利用適應性信息，以點集而非點在整個空間中做大范圍并行搜索，具有很強的搜索能力.由于剛提出時的遺傳算法還較為簡單，現(xiàn)在通常稱之為傳統(tǒng)遺傳算法，后來的研究人員不斷探索，又提出了各種改進遺傳算法.本文在傳統(tǒng)遺傳算法的基礎上，針對MDVRP的特征設計了一種混合遺傳算法(Hybrid Genetic Algorithm，HGA)，通過設計新型編解碼方式、混合算子以及廣度搜索與深度搜索平衡策略，有效地提升算法性能，旨在通過該算法以獲得較高質(zhì)量的滿意解.

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

現(xiàn)有的區(qū)域內(nèi)多配送中心配送多采用分區(qū)域獨立配送模式.多個配送中心雖同屬于一家企業(yè)，但一般情況下，企業(yè)會根據(jù)行政區(qū)劃為每個配送中心劃分一個業(yè)務范圍，各配送中心間相對獨立.在分區(qū)域獨立配送模式下，一個客戶會固定從屬于某一特定配送中心，而不會根據(jù)客戶的地理分布和需求特性進行調(diào)整，易導致各配送中心間任務分配不均.從理論研究的角度來看，此類求解MDVRP的方法是“先分組后路徑”，即分區(qū)域規(guī)劃思想，將各配送中心割裂開來.分區(qū)的結(jié)果會直接影響區(qū)內(nèi)路徑的規(guī)劃結(jié)果，不合理的分區(qū)算法常常會導致較差的路徑規(guī)劃.為避免此類問題的出現(xiàn)，本文采用整體配送模式，引入一個與所有的實際配送中心相連且距離為0的虛擬配送中心，所有車輛均從該虛擬配送中心出發(fā)，經(jīng)過實際配送中心對客戶進行服務，然后再經(jīng)實際配送中心返回該虛擬配送中心.

則多中心車輛路徑問題的數(shù)學模型如下：

(10)

圖1 編解碼方式示意圖Fig.1 Coding mode diagram

式(1)為最小化運輸總成本；式(2)為車輛容量約束；式(3)為車輛數(shù)約束；式(4)為各節(jié)點進出平衡約束；式(5)為所有車輛均從虛擬配送中心出發(fā)并最終全部返回虛擬配送中心；式(6)為各配送中心間不能有車輛直接相連；式(7)保證任一客戶由且僅由一輛車進行配送；式(8)為消除子回路約束；式(9)和(10)為決策變量屬性.

2 混合遺傳算法設計及實現(xiàn)

遺傳算法一般由編解碼、個體適應度評價以及遺傳運算三大主要部分組成.在遺傳算法中，常定義種群為所編碼后的染色體集合，而個體是其相應染色體的表現(xiàn)型.

2.1 編解碼方式

傳統(tǒng)遺傳算法的編解碼方式多采用二進制編碼，然而對于VRP，采用二進制編解碼則可能需要額外的修復機制對產(chǎn)生的不可行解進行修復，從而導致問題的求解時間變長.為避免此類情況發(fā)生，現(xiàn)有文獻對VRP多采用自然數(shù)編解碼，如由1個配送中心(編號為0)、10個客戶(編號為1～10)以及3輛車組成的配送網(wǎng)絡中，編碼0340278105690，解碼后表示路徑0-3-4-0、0-2-7-8-1-0以及0-5-6-9-0.考慮到車輛容量限制會導致車輛實際裝載量不固定，進而致使所用車輛總數(shù)不固定.即在該編碼方式下，染色體長度可能會因為配送方案的不同而不固定，從而導致計算效率下降.因此，本文在傳統(tǒng)編解碼方式的基礎上，提出一種能夠有效表達客戶信息、配送中心信息以及車輛路徑信息的編解碼方式.

一個完整的配送網(wǎng)絡信息由兩部分組成：①編碼：本文的編碼采用全客戶編碼，這一部分記錄所有客戶的先后服務順序，體現(xiàn)在染色體上，其長度固定(即客戶數(shù)目)；②解碼：為不改變編碼長度，本文的解碼分為兩個階段，第一階段是對首尾客戶位置進行解碼，這一階段記錄每輛車第一個服務的客戶以及最后一個服務的客戶在染色體中的位置，解碼長度與所用車輛數(shù)有關(guān)；第二階段是路徑解碼，這一階段記錄每輛車所屬的配送中心以及所服務的全部客戶.如圖1所示，現(xiàn)有2個配送中心(編號為1～2)、10個客戶(編號為3～12)和3輛車的配送網(wǎng)絡，全客戶編碼為8-3-7-12-9-5-4-10-6-11.首尾客戶位置解碼為[1,3]、[4,7]、[8,10]，即第1輛車從第1個客戶(客戶8)開始服務，服務完第3個客戶(客戶7)返回配送中心.同理，該染色體對應的路徑解碼則表示為R1：1-8-3-7-1、R2：1-12-9-5-4-1、R3：2-10-6-11-2.

本文通過將配送網(wǎng)絡信息分開表示，在遺傳操作時，只對編碼長度固定的第一部分信息進行操作，遺傳操作完成后，第一部分全客戶編碼即已完成，此時根據(jù)車輛容量約束重新為每個車輛分配客戶，解碼獲得第二部分的首尾客戶位置，再根據(jù)首尾客戶位置計算出最近的配送中心，從而再解碼獲得最終的路徑.也就是說第一部分全客戶編碼決定了后面的解碼，只要第一部分信息是正確的，則由其產(chǎn)生的最終路徑編碼也一定是正確的，即通過此編碼方式產(chǎn)生的個體進行擾動產(chǎn)生的新個體一定為原問題的可行解.且該編碼方式有利于計算機實現(xiàn)，運算效率較高.

2.2 擾動過程

傳統(tǒng)遺傳算法的擾動算子主要包括交叉和變異，其中交叉算子模擬自然界有性繁殖，采用兩個父代個體繁殖子代個體，對于整數(shù)編碼的問題，簡單隨機交叉產(chǎn)生的子代個體很可能不再是原問題的可行解，故在VRP中常使用部分匹配交叉(Partially Mapped Crossover，PMX)、順序交叉(Order Crossover，OX)等復雜交叉算子.單親遺傳的所有遺傳操作均在一條染色體上完成，計算效率能夠得到很大提升，但由于各個體間缺乏基因交流，易陷入“進化瓶頸”；而雙親遺傳中子代則能夠繼承父代兩個體的優(yōu)良基因，遺傳過程中父代基因得到充分的交流，有利于突破“進化瓶頸”，然而雙親遺傳也存在一些缺陷，如計算效率較低等.針對單親遺傳與雙親遺傳各自的特點，本文算法的擾動過程采用單親遺傳算子與雙親遺傳算子相結(jié)合的方式.

2.2.1單親遺傳算子 單親遺傳算子一般有3種操作：

(1) 插入算子(Insertion Operator).選擇一個客戶并插入到某個客戶后面.如圖2(a)所示，選擇路線A上客戶1，插入客戶3之后的位置，形成插入后路線A′.

(2) 互換算子(Reciprocal Exchange Operator).選擇兩個客戶并交換兩個客戶位置.如圖2(b)所示，選擇線路A上客戶1與客戶3，互換位置后形成路線A′.

(3) 反序算子(Inversion Operator).選擇兩個客戶并將兩客戶間所夾客戶進行反序.如圖2(c)所示，選擇線路A上客戶1與客戶5，將所夾客戶2～4進行反序形成線路A′.

圖2 單親遺傳算子示意圖Fig.2 Partheno-genetic operator

圖3 雙親遺傳算子示意圖Fig.3 Parent genetic operator

在傳統(tǒng)雙親遺傳算法中，一般隨機選取兩個體進行交叉，此方式保證了所有個體間基因的充分交流，但也會導致優(yōu)秀基因不能擁有更多的交流，故本文在采用傳統(tǒng)交叉方式的同時，還模擬生物界繁衍模式——首領的基因擁有更多的機會傳遞給下一代，在雙親遺傳算子中采用全局最優(yōu)個體與父代中任意個體交配的方式產(chǎn)生子代個體.

以文獻[13]中算例為例分析各遺傳算子在求解時間和質(zhì)量上的差異(設置種群規(guī)模 pop_size=200，最大遺傳代數(shù)M=100)，對各算子分別求解10次，求解結(jié)果如表1所示，在表1的基礎上分別對求解時間和求解質(zhì)量進行對比，對比結(jié)果如圖4和5所示.由圖可知，單親遺傳算子(算子1～4)的求解時間明顯較短，而在各單親遺傳算子中，混合單親遺傳算子較單個單親遺傳算子的求解質(zhì)量要高.雙親遺傳算子(算子5～7)的求解時間較單親遺傳算子而言求解時間明顯較長，在求解質(zhì)量上，由于隨機交叉算子(算子5)的目的在于種群內(nèi)的基因充分交流，使得解保持多樣性，而忽略了優(yōu)秀個體的基因?qū)蟠獾馁|(zhì)量的影響，致使獲得解的質(zhì)量最低；首領交叉算子(算子6)注重于種群中最優(yōu)秀個體(首領)

表1 各遺傳算子求解結(jié)果統(tǒng)計表Tab.1 Results of various genetic operators

圖4 各算子求解時間對比Fig.4 Efficiency comparison of operators

圖5 各算子求解質(zhì)量對比Fig.5 Solution quality comparison of operators

基因的遺傳，故而在解的質(zhì)量上有所提高；混合交叉算子(算子7)是對算子5～6的混合，綜合考慮了不同雙親遺傳算子中對解的質(zhì)量與解的多樣性的影響，求解質(zhì)量進一步提高；本文算子(算子8)則綜合采用了單親遺傳算子與雙親遺傳算子的優(yōu)勢，在求解時間和求解質(zhì)量取得一定的平衡，使得整體效果最佳.

2.3 選擇操作

遺傳算法選擇操作有輪盤賭、錦標賽以及精英策略等多種方法，本文采用精英策略與輪盤賭混合選擇策略.對每代種群pop_size條染色體先進行擾動操作，產(chǎn)生包含C_pop_size條染色體的子代種群，首先通過精英策略選擇適應度值最高的αn條染色體，之后從其余的C_pop_size-αn條子代種群中采用輪盤賭策略選取(1-α)n條染色體，通過控制參數(shù)α可以調(diào)節(jié)子代種群中精英個體和非精英個體的比例，從而實現(xiàn)深度搜索與廣度搜索的平衡.α∈[0,1]，且α的值越大，種群中精英個體越多，則算法偏向于深度搜索；反之，則偏向于廣度搜索.根據(jù)pop_size大小，一般α取 0.05～0.15.

此外，在利用輪盤賭選擇子代個體時，為防止較差解進入子代，本文用參數(shù)β控制C_pop_size-αn條染色體中參與輪盤賭的個體比例，平衡種群多樣性與種群質(zhì)量.β∈(0,1]，且β的值越大，參與輪盤賭的個體越多，種群多樣性越好；反之，則參與輪盤賭的個體越少，種群中精英個體越多，種群質(zhì)量越好.根據(jù)C_pop_size-αn大小，一般β取0.05～0.15.

文獻[13]中3個配送中心及30個客戶組成的配送網(wǎng)絡規(guī)模適中，故以文獻[13]中算例分析不同選擇操作對解的影響，除選擇方式不同外，所用算法其他部分完全一致，對各選擇操作分別求解10次，求解結(jié)果如表2第2～4列所示，從表中可知，3種選擇方式策略中，解的質(zhì)量從高到低依次為本文的混合選擇策略、精英+輪盤賭方式策略、輪盤賭方式策略，圖6為3種選擇方式策略10次求解算例的結(jié)果，由圖6可知，采用輪盤賭方式策略獲得的解整體質(zhì)量較差，且解的波動程度較大；采用精英+輪盤賭方式策略獲得的解雖然在質(zhì)量上有所提升，但依然不夠穩(wěn)定，本文采用的選擇方式策略則能獲得較高質(zhì)量的解，且解的穩(wěn)定性較好.

表2 不同選擇策略下的求解結(jié)果Tab.2 Results under different selection strategies

圖6 不同選擇策略下的求解結(jié)果對比Fig.6 Result comparison under different selection strategies

2.4 自適應搜索范圍策略

由于群體在進化過程中，各階段需要的進化壓力不同.需要平衡搜索深度與搜索廣度之間的關(guān)系，故本文除在選擇算子中采用精英機制與輪盤賭相結(jié)合的策略以外，還構(gòu)造了一種自適應搜索范圍策略來進一步平衡此種關(guān)系：

(11)

式中：Ng為第g代個體的搜索范圍，即第g代個體進行鄰域擾動的次數(shù)；r1為最小搜索范圍；r2為自適應搜索范圍.

顯然子代種群規(guī)模C_pop_size=Ngpop_size.圖7所示為相應的示意圖.

圖7 自適應搜索范圍策略Fig.7 Adaptive search range strategy

由圖7可知，在進化初期，由于種群朝著適應度值高的方向進化速度較快，以擴大搜索廣度為主，故擾動次數(shù)較少，在每個個體的附近搜索范圍較?。坏S著種群的進化速度越來越慢，搜索廣度已不是制約進化速度的主要因素，搜索深度則對種群進化的影響越來越大，故擾動次數(shù)越來越多，在每個個體的附近搜索范圍越來越大.通過對每個個體的潛在進化能力進行激發(fā)，促使其跳出局部最優(yōu)解.

為分析本文所提自適應搜索范圍策略的效果，仍以文獻[13]中算例為例與固定搜索范圍策略相對比，在對比之前，先給出以下命題及其證明：

命題采用如式(11)所示的自適應搜索范圍策略進行搜索時，當最大遺傳代數(shù)較大時，平均每代搜索的次數(shù)主要取決于最小搜索范圍和自適應搜索范圍.

證明證明過程如下：

(12)

證畢

3 實驗與結(jié)果分析

實驗1為驗證本文所提出混合遺傳算法的有效性，采用文獻[13]算例，以MATLAB R2012a為編譯平臺，在雙核奔騰G2020/2.9 GHz微機上運行程序.實驗數(shù)據(jù)如表3所示，實驗參數(shù)設定如下：種群規(guī)模pop_size=40，最大遺傳代數(shù)M=100，控制參數(shù)α=0.15、β=0.1，最小搜索范圍r1=30，自適應搜索范圍r2=50.

在邊長為20 km的正方形區(qū)域內(nèi)的配送網(wǎng)絡中有3個配送中心和30個客戶，其中每個客戶的貨物需求均不超過2 t，每個配送中心有4輛最大裝載量為10 t的車輛，車輛單次配送的最大行駛路程均為50 km.文獻[11-12]均采用先分組后路徑的配送方式將多中心車輛路徑問題轉(zhuǎn)化為一般車輛路徑問題，然后分區(qū)配送，這本質(zhì)上是一種局部優(yōu)化求解思想；而本文采用先路徑后分組的配送方式對配送網(wǎng)絡整體進行考慮，進行全局優(yōu)化.已知該算例的目前最優(yōu)解為 116.01，圖8所示為本文算法求解得到的最優(yōu)路徑安排圖(圖中括號內(nèi)為該客戶點的需求量)，表4給出了本文的混合遺傳算法對該算例進行20次重復求解結(jié)果與文獻[11]中的禁忌搜索算法、文獻[12]中的聚類分層算法以及文獻[13]中的云量子遺傳算法的對比.

由表4可以看出，本文設計的混合遺傳算法求得的最優(yōu)結(jié)果為 115.39，相比禁忌搜索算法求得的最優(yōu)結(jié)果 177.53 提高了 35.00%，比聚類分層算法以及云量子遺傳算法求得的最優(yōu)結(jié)果也分別有著 6.44% 和 0.53% 的提高.通過對最優(yōu)解、最劣解、平均解以及計算時間等各項性能參數(shù)的統(tǒng)計可以發(fā)現(xiàn)：本文算法與其他3種算法相比，在求解時間方面至少縮短20倍以上，求解時間降幅達 95.58%，雖然考慮到計算機硬件等因素的不同，但也是很大的提升；在算法穩(wěn)定方面的提升也超過了20%.即本文算法相較于禁忌搜索算法、量子遺傳算法以及云量子遺傳算法，無論是在求解時間上還是在解的質(zhì)量上都有著明顯的改進，說明本文算法的求解時間更短、全局尋優(yōu)能力更強、算法穩(wěn)定性更好.

表3 客戶需求信息Tab.3 Information of customer demand

圖8 最優(yōu)路徑Fig.8 Optimal path

表4 算法性能對比分析Tab.4 Contrastive analysis of algorithm performance

注：本文算法性能提升幅度是指本文算法性能比其他3種算法中性能最好的算法性能提升幅度.

表5 MDVRP標準算例實驗結(jié)果對比Tab.5 Comparison of the experimental results for MDVRP standard examples

圖9給出了相應的迭代收斂圖，由圖9可知：對該算例約在40代左右找到最優(yōu)解，說明本文算法能夠在較少的遺傳代數(shù)內(nèi)找到問題的最優(yōu)解，收斂速度快.此外， 從迭代收斂圖還可看出，在30代左右，

圖9 迭代收斂圖Fig.9 Iterative convergence graph

進化進入瓶頸，通過本文所設計的進化策略可以有效逃脫局部最優(yōu)解.

實驗2為了進一步測試本文所提出算法的性能，從標準算例庫(來源：http:∥neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/)中下載MDVRP的相關(guān)數(shù)據(jù)，表5第2列給出了算例P01～P06共6個算例的相關(guān)信息，客戶規(guī)模為50～100.由于客戶規(guī)模不確定，故實驗參數(shù)設定如下：種群規(guī)模pop_size=40，最大遺傳代數(shù)M=300～1000，控制參數(shù)α=0.05～0.15、β=0.05～0.15，最小搜索范圍r1=30～50，自適應搜索范圍r2=70～170.

圖10 標準算例最優(yōu)路徑圖Fig.10 Optimal path of standard examples

表5第4列至結(jié)束給出了本文算法與其他5種算法對比的結(jié)果，圖10所示為本文求解的最優(yōu)路徑圖.從遺傳算法改進的角度來看，本文提出的混合遺傳算法明顯比文獻[16]中基本遺傳算法解的質(zhì)量要高，由此可見本文所設計的混合遺傳算法是有效的，能夠整體提升傳統(tǒng)遺傳算法解的質(zhì)量.與其他算法相比，雖然部分解的質(zhì)量并不是最好，但整體求解效果較好，平均誤差較其他算法更低，且在所有6個算例中有3個算例達到了已知的最優(yōu)解，其他未達到最優(yōu)解的3個算例求解結(jié)果與已知最優(yōu)解的誤差最大也不超過2.5%，表明本文所提出的混合遺傳算法屬于具有一定競爭力的算法.

4 結(jié)語

針對傳統(tǒng)遺傳算法求解MDVRP問題，本文設計了一種混合遺傳算法.主要在以下幾個方面進行了改進：

(1) 提出一種新的編解碼方式，該編解碼方式能夠解決傳統(tǒng)遺傳算法編碼方式對多中心車輛問題編解碼時染色體長度不固定導致的計算效率低下問題.

(2) 擾動過程中使用單親遺傳算子以提高傳統(tǒng)遺傳算法的計算效率，使用雙親遺傳算子以促使個體間的基因交流.

(3) 在選擇操作中引入兩個控制參數(shù)以平衡種群中精英數(shù)量與種群多樣性間的沖突；并設計一種自適應搜索范圍策略，利用該策略可以有效平衡搜索深度與搜索廣度間的關(guān)系.

通過測試算例并與其他文獻進行對比，本文算法將實驗1中的測試算例已知最優(yōu)解提升了 0.53%，驗證了本文算法的有效性；并通過實驗2對6個不同標準MDVRP算例進行求解與對比，結(jié)果證明本文所設計的混合遺傳算法能夠?qū)DVRP進行有效的求解.

本文研究為求解多中心車輛路徑問題這一組合優(yōu)化難題提供了一種新思路，同時也為采用聯(lián)合配送模式的企業(yè)進行配送方案決策提供一定的參考. 限于篇幅及精力，本文還存在一些不足，未來將從聯(lián)合配送的時效性及算法的收斂速度兩方面著手做進一步研究.