混合遺傳算法求解多中心聯(lián)合配送路徑問題

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

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

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

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

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

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

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

(10)

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

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

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

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

2.1 編解碼方式

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

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

本文通過將配送網(wǎng)絡(luò)信息分開表示，在遺傳操作時，只對編碼長度固定的第一部分信息進行操作，遺傳操作完成后，第一部分全客戶編碼即已完成，此時根據(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)等復(fù)雜交叉算子.單親遺傳的所有遺傳操作均在一條染色體上完成，計算效率能夠得到很大提升，但由于各個體間缺乏基因交流，易陷入“進化瓶頸”；而雙親遺傳中子代則能夠繼承父代兩個體的優(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)雙親遺傳算法中，一般隨機選取兩個體進行交叉，此方式保證了所有個體間基因的充分交流，但也會導(dǎo)致優(yōu)秀基因不能擁有更多的交流，故本文在采用傳統(tǒng)交叉方式的同時，還模擬生物界繁衍模式——首領(lǐng)的基因擁有更多的機會傳遞給下一代，在雙親遺傳算子中采用全局最優(yōu)個體與父代中任意個體交配的方式產(chǎn)生子代個體.

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

表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 選擇操作

遺傳算法選擇操作有輪盤賭、錦標(biāo)賽以及精英策略等多種方法，本文采用精英策略與輪盤賭混合選擇策略.對每代種群pop_size條染色體先進行擾動操作，產(chǎn)生包含C_pop_size條染色體的子代種群，首先通過精英策略選擇適應(yīng)度值最高的α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)絡(luò)規(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 自適應(yīng)搜索范圍策略

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

(11)

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

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

圖7 自適應(yīng)搜索范圍策略Fig.7 Adaptive search range strategy

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

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

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

證明證明過程如下：

(12)

證畢

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

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

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

由表4可以看出，本文設(shè)計的混合遺傳算法求得的最優(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倍以上，求解時間降幅達(dá) 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標(biāo)準(zhǔn)算例實驗結(jié)果對比Tab.5 Comparison of the experimental results for MDVRP standard examples

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

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

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

實驗2為了進一步測試本文所提出算法的性能，從標(biāo)準(zhǔn)算例庫(來源：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ù)設(shè)定如下：種群規(guī)模pop_size=40，最大遺傳代數(shù)M=300～1000，控制參數(shù)α=0.05～0.15、β=0.05～0.15，最小搜索范圍r1=30～50，自適應(yīng)搜索范圍r2=70～170.

圖10 標(biāo)準(zhǔn)算例最優(yōu)路徑圖Fig.10 Optimal path of standard examples

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

4 結(jié)語

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

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

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

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

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

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