馬艷芳，李保玉，楊屹夫，馮翠英

1.河北工業(yè)大學 經濟管理學院，天津 300401

2.浙江工業(yè)大學 經貿管理學院，杭州 310014

隨著人們生活水平的提高，對肉制品、水產品、牛奶、新鮮果蔬等生鮮產品的需求不斷增加，冷鏈物流行業(yè)也在快速發(fā)展。國家發(fā)改委、交通運輸部門等24部門于2019年發(fā)布了《關于推動物流高質量發(fā)展促進形成強大國內市場的意見》，文中強調鞏固物流降本增效成果，增強物流企業(yè)活力，提升行業(yè)效率效益水平，暢通物流全鏈條運行。據統(tǒng)計，在生鮮運輸過程中腐爛的水果和蔬菜價值每年高達700億元，造成了巨大的經濟損失[1]。因此，如何提高生鮮產品冷鏈物流的運輸效率，降低物流配送成本，成為優(yōu)化生鮮冷鏈物流系統(tǒng)的主要研究方向之一。

近年來，為降低生鮮產品高昂配送成本，學者們對其進行了廣泛研究。馬艷芳等[1]建立了基于沖突合作關系的生鮮選址-路徑多主體優(yōu)化模型，主導層以系統(tǒng)總成本最低為目標，從屬層考慮運輸相關成本最小化，并設計GAPSO算法求解模型。馮杰和史立[2]構建了有客戶軟時間窗約束和車輛里程約束的生鮮產品配送路徑優(yōu)化模型，并采用蟻群算法進行求解。李軍濤等[3]針對冷鏈物流配送系統(tǒng)中總成本較高但車輛有效利用率低的問題，在考慮擁堵指數的基礎上，構建多目標多車型路徑優(yōu)化模型，并提出自適應遺傳模擬退火算法。Chen等[4]研究了冷鏈配送過程中具有一些實際約束的多隔間車輛路徑問題，開發(fā)自適應大鄰域搜索算法求解。Yao等[5]將生鮮海產品配送問題建模為多倉庫車輛路徑問題，以總配送成本最小為目標，采用蟻群算法求解。從以上文獻中可以看出，目前生鮮產品冷鏈物流背景下的車輛路徑問題研究較為豐富，但大多考慮單級車輛路徑，能檢索到的考慮兩級車輛路徑問題的文獻還不多。

此外，由于生鮮產品的易腐性，顧客十分重視生鮮產品的質量和新鮮度。對于配送企業(yè)而言，若想獲取客戶信任，提高市場競爭力，不僅要關注物流配送成本，也需要考慮客戶滿意度[6-7]?？蛻魸M意度已成為配送企業(yè)競爭的重要考量因素[8]，這也促使學者們開始對如何提高客戶滿意度進行研究。李軍濤等[3]驗證了采用多車型配送、使用改進的自適應遺傳模擬退火算法以及適當定價三種策略均可從不同程度上提高客戶滿意度。張惠珍等[9]通過綜合考慮客戶時間窗和食物新鮮度來提高客戶滿意度，并采用單親遺傳混合蟻群算法求解多目標車輛路徑模型。夏揚坤等[10]研究了客戶分級和客戶需求依背包拆分的生鮮車輛路徑問題，以降低物流配送成本并提高客戶滿意度。任騰等[11]構建在客戶允許服務時間范圍內以總成本最小為目標的冷鏈車輛路徑優(yōu)化模型，以滿足企業(yè)經濟和社會效益。戶佐安等[12]以客戶對服務時間和貨物完好性的要求衡量客戶滿意度，建立以客戶滿意度最大和運輸成本最小為目標的優(yōu)化模型。可見，在生鮮物流市場競爭日益激烈的今天，配送企業(yè)若想穩(wěn)固在競爭市場中的地位，在考慮經濟成本的同時，客戶滿意度也不容忽略。且從以上文獻中可以看出，目前對于車輛路徑問題中客戶滿意度的研究較為豐富，但從客戶分類角度提高客戶滿意度的文獻較少。因此，本文考慮了客戶分類，通過將客戶按重要性進行分類以提高客戶滿意度。優(yōu)先滿足重要客戶的期望時間窗，提高重要客戶的期望時間窗滿足率，這樣，既保持了配送企業(yè)的優(yōu)質客戶資源，也提高了其整體客戶滿意度。

兩級容量有限車輛路徑問題（Two-Echelon Capacitated Vehicle Routing Problem，2E-CVRP）可視為兩個車輛路徑問題（Vehicle Routing Problem，VRP）的組合，VRP已是典型的NP難問題，可知2E-CVRP的求解難度更大。精確方法適用于求解小規(guī)模問題，對于復雜優(yōu)化問題常采用啟發(fā)式算法進行求解。啟發(fā)式算法在求解VRP問題時展現出了優(yōu)越的性能[1-5，9]，然而，單一的啟發(fā)式算法具有一定的局限性。遺傳算法（Genetic Algorithm，GA）具有較強的全局搜索能力，但容易過早收斂，易于陷入局部最優(yōu)解，因而算法效率不高。模擬退火算法（Simulated Annealing，SA）局部搜索能力較強，但全局搜索能力較弱。綜合兩種算法的優(yōu)缺點，將改進的遺傳算法和模擬退火算法相結合，求解2E-CVRP優(yōu)化模型。

表1總結了車輛調度問題中與生鮮配送、兩級路徑和客戶分類相關研究。從表1中可以看出，目前關于VRP的研究已取得了較為豐碩的成果，但在生鮮冷鏈物流背景下的兩級車輛路徑研究較少，且少有研究在兩級車輛路徑中考慮客戶分類，而考慮客戶分類對配送企業(yè)維持優(yōu)質客戶資源，提高企業(yè)經濟和社會效益具有重要意義?；诖?，本文研究生鮮產品配送背景下考慮客戶分類的兩級容量有限車輛路徑問題（Two-Echelon Capacitated Vehicle Routing Problem with Customer Classification，2E-CVRP-CC）。并設計兩階段啟發(fā)式算法進行求解：第一階段使用改進的GA-SA算法求解二級配送網絡，第二階段使用精確方法求解一級配送網絡。最后，基于Set2、Set5兩組基準算例集進行算法對比分析，證明算法的尋優(yōu)能力，并測試算法的收斂性，然后結合實際案例模擬驗證2E-CVRP-CC模型的適用性。

表1 相關文獻特征Table 1 Characteristics of relevant literature

1 問題與模型

1.1 符號說明

集合：

設N(V,E)為生鮮產品運輸網絡，其中，V=D?S?C。

D：中心倉庫，D={0}；

S：配送中心集合，S={1,2,…,s}；

C：客戶集合，C={1,2,…,n}；

B：一級運輸車輛集合，B={1,2,…,b0}；

K：二級運輸車輛集合，K={1,2,…,k0}；

P1：由倉庫和配送中心組成的節(jié)點集合，P1=D?S；

P2：由配送中心和客戶組成的節(jié)點集合，P2=S?C；

指標和參數：

i/j：物流網絡中節(jié)點的索引；

QS i：配送中心i∈S的容量；

QB：一級同質運輸車輛的容量；

QK：二級同質運輸車輛的容量；

FD：中心倉庫的建設成本；

FS i：配送中心i∈S的建設成本；

FB：一級運輸車輛的固定成本；

FK：二級運輸車輛的固定成本；

a1：一級運輸車輛的單位運輸費用；

a2：二級運輸車輛的單位運輸費用；

d ij：節(jié)點i與節(jié)點j之間的距離，i,j∈V；

ρ：價值損耗系數，即單位時間內單位生鮮產品的價值損耗；

qi：客戶i∈C的需求量；

：一級運輸車輛b∈B在弧線(i,j)之間的裝載量，i,j∈P1；

：二級運輸車輛k∈K在弧線(i,j)之間的裝載量，i,j∈P2；

/：二級運輸車輛k∈K到達節(jié)點i/j的時間，

i,j∈P2；

：二級運輸車輛k∈K從節(jié)點i駛向節(jié)點j的時間，i,j∈P2；

：二級運輸車輛k∈K在客戶點i∈C的等待時間；

：二級運輸車輛k∈K在客戶點i∈C的服務時間；

Tmax：二級配送網絡中，每條路線允許車輛行駛的最長時間；

[ET i,LT i]：客戶i∈C的期望時間窗；

ci：客戶i∈C單位時間窗偏離量費用；

決策變量：

y i：0-1變量，如果配送中心i∈S開放，則為1，否則為0；

xijb：0-1變量，如果車輛b∈B通過弧(i,j)，則為1，否則為0，i,j∈P1；

y ijk：0-1變量，如果車輛k∈K通過弧(i,j)，則為1，否則為0，i,j∈P2；

zik：0-1變量，如果客戶i∈C由車輛k∈K進行配送，則為1，否則為0。

1.2 客戶分類

在運輸過程中，生鮮產品價值隨著時間而衰減，按時交付生鮮產品可以防止質量下降，并且能夠提高顧客對于配送企業(yè)的可信度和滿意度。優(yōu)化模型考慮了顧客對于期望時間窗的要求，然而，帶軟時間窗的車輛路徑問題容易降低客戶滿意度，且配送企業(yè)在提供配送服務時要權衡成本與效益。因此，為保持配送企業(yè)優(yōu)質客戶資源，將客戶按重要性分為重要客戶與普通客戶兩類，通過增大重要客戶的時間窗偏離量懲罰程度，優(yōu)先滿足重要客戶的期望時間窗，提高重要客戶的期望時間窗滿足率，進而提高整體客戶滿意度，形成一個考慮客戶分類的2E-CVRP。

另外，不同類別客戶的單位時間窗偏離量費用c i是不同的，重要客戶的c i值較普通客戶更大，為保持企業(yè)優(yōu)質客戶資源并提高整體客戶滿意度，應盡量滿足重要客戶的期望時間窗。[0,Tmax]為配送中心點i∈S的硬時間窗約束，Tmax是二級配送車輛可允許行駛的最長時間。[ET i,LT i]為每個客戶點i∈C的期望時間窗，如果顧客的期望時間窗未得到滿足，則會施加懲罰成本。懲罰成本與客戶滿意度呈負相關關系，懲罰成本越高，說明未被滿足的顧客期望時間窗越多，客戶滿意度也就越低。因此，可以用懲罰成本的高低反映客戶滿意度水平。

1.3 生鮮兩級車輛路徑問題

兩級容量有限車輛路徑問題（2E-CVRP）可描述如下：在生鮮產品物流配送網絡中有一個中心倉庫和多個期望客戶，在中心倉庫和客戶之間有固定數量的配送中心。位于城區(qū)邊緣位置的倉庫通過大型同質冷藏運輸車（一級配送車輛）向位于城區(qū)中的各配送中心運送生鮮產品，其中倉庫和配送中心的地理位置已知，有裝載量和數量限制的一級配送車輛從倉庫出發(fā)，配送完成后返回倉庫（一級配送網絡）；在配送中心，生鮮產品被轉移到小型同質冷藏運輸車上（二級配送車輛），然后車輛從配送中心出發(fā)，通過規(guī)定的優(yōu)化路線為指定的顧客服務，最終再返回配送中心（二級配送網絡）。具體的物流網絡結構圖如圖1所示。

圖1 2E-CVRP物流網絡示意圖Fig.1 Logistics network diagram of 2E-CVRP

2E-CVRP在已知中心倉庫和配送中心的容量和地理位置、各級配送車輛容量、顧客地理位置、需求量等條件下，規(guī)劃各級配送車輛運輸服務路徑，從而使整個物流配送網絡總成本最低。物流配送網絡總成本包括倉庫和配送中心的建設成本、車輛固定成本、車輛運輸成本、生鮮產品損耗成本以及未滿足顧客期望時間窗要求而產生的懲罰成本。其中，倉庫和配送中心的建設成本主要包括場地租賃費、冷藏設備購置費、水電費以及員工工資等；車輛固定成本主要指駕駛員工資以及車輛折舊費用等；車輛運輸成本主要包括電能消耗費用以及車輛維修費用等；損耗成本指生鮮產品在配送過程中因腐爛變質而產生的損失費用。問題假設如下：

（1）中心倉庫有足夠數量的存貨，可以滿足所有配送中心的需求；

（2）配送中心和客戶的數量、地理位置已知，各級配送車輛固定成本已知；

（3）各節(jié)點間距離按歐式距離計算，各級配送車輛單位運輸成本已知；

（4）各級配送車輛容量已知，各運輸路徑上車輛載重量不能超過其容量限制；

（5）配送途中交通狀況良好，車輛均勻速行駛；

（6）客戶需求和期望時間窗是獨立且預先確定的；

（7）各級配送車輛離開并最終返回相同的起始節(jié)點位置；

（8）為減少生鮮產品損耗，一級配送車輛到達配送中心并卸下產品后，產品會立即被裝載到二級配送車輛上，此時產品在配送中心的處理成本忽略不計；

（9）僅計算二級配送網絡中生鮮產品的損耗成本。

1.4 數學模型

目標函數式（1）為最小化物流配送系統(tǒng)的總成本，包括倉庫和配送中心的建設成本，一、二級配送網絡中車輛的固定成本和運輸成本，二級配送網絡中生鮮產品的損耗成本以及因未滿足顧客期望時間窗要求而產生的懲罰成本，分別如式（2）～（6）所示。其中，二級配送網絡中生鮮產品的損耗成本Z4與車輛到達顧客節(jié)點的時間呈正相關，生鮮產品的價值損耗系數ρ由文獻[13]提出，表示單位時間內單位生鮮產品的價值損耗。約束條件式（7）確保離開倉庫的生鮮產品總量等于顧客總需求量；式（8）是一級配送車輛的容量約束；式（9）保證每個配送中心最多只能被一輛一級配送車輛服務一次；式（10）保證一級配送網絡中每個節(jié)點的進出車輛相同；式（11）表明在倉庫之間沒有車輛路徑；式（12）表示分配給各配送中心的生鮮產品數量不能超過其自身容量；式（13）是二級配送車輛的容量約束；式（14）保證每位顧客只能被一輛二級配送車輛服務一次；式（15）保證二級配送網絡中每個節(jié)點的進出車輛相同；式（16）說明在配送中心之間沒有車輛路徑；式（17）是車輛載重量守恒約束，消除子約束，滿足每位顧客的需求；式（18）和（19）確保所有車輛空車返回其原始倉庫或配送中心；式（20）和（21）保證從倉庫和配送中心發(fā)出的車輛總數不能超過其擁有的最大數量；式（22）是硬時間窗約束，也是二級配送車輛最長運輸時間限制；式（23）計算二級配送車輛的等待時間；式（24）計算二級配送網絡中，二級運輸車輛到達節(jié)點j∈C的時間。

2 求解算法

本文建立的2E-CVRP-CC模型屬于NP難問題，包含兩級配送網絡：一級配送網絡從中心倉庫出發(fā)將生鮮產品運輸至各配送中心，二級配送網絡從各配送中心出發(fā)將生鮮產品配送給終端客戶。文中設計兩階段啟發(fā)式算法求解該模型：第一階段求解二級運輸路徑，由于涉及客戶數目相對較多，采用求解效率較高的改進GASA啟發(fā)式算法，又由于配送企業(yè)將客戶按重要性分為重要客戶和普通客戶，故為區(qū)分兩類客戶，在算法設置數據時，將不同類別客戶的時間窗偏離量費用ci賦予不同的數值，其中重要客戶的時間窗偏離量費用為c1，普通客戶的時間窗偏離量費用為c2，且c1>c2，這樣保證了能夠優(yōu)先滿足重要客戶的期望時間窗。

2.1 第一階段：改進的GA-SA算法求解二級網絡

第一階段求解配送中心與顧客之間的車輛路徑問題，可視為單層VRP。對于2E-CVRP而言，其重點在于第二級配送網絡的車輛路徑規(guī)劃，二級路徑的優(yōu)化可以節(jié)約大量物流系統(tǒng)成本，因此為二級配送車輛規(guī)劃合適的運輸路線至關重要。為了更好地求解二級物流網絡車輛路徑問題，本階段采用改進的混合啟發(fā)式算法（GA-SA），即在算法的迭代過程中，首先使用遺傳操作，然后使用模擬退火操作，以增強找到的最優(yōu)解。

遺傳算法（GA）最早由John Holland提出，是一種模擬達爾文進化理論和自然界優(yōu)勝劣汰機制進行全局最優(yōu)解搜索的啟發(fā)式算法[14]。GA將問題的求解過程轉化成類似生物進化中染色體基因的交叉、變異等過程，通常包括選擇、交叉、變異等基本操作。然而，單一的啟發(fā)式算法都有一定的局限性，像GA在求解大規(guī)模復雜優(yōu)化問題時，存在局部搜索能力較弱、容易過早收斂、易于陷入局部最優(yōu)解的缺陷。

基于單一解的模擬退火算法（SA）可以突破爬山算法的局限性，克服局部最優(yōu)陷于停滯的問題，該算法由Kirkpatrick等[15]提出，以一定的概率接受較差解，從而加強跳出局部最優(yōu)的能力。此外，劉蘭芬和楊信豐[16]證明了將GA和SA結合的遺傳模擬退火算法的有效性。因此，綜合借鑒兩種算法的思路，將改進的GA-SA算法作為第一階段算法。

2.2 解的表示與初始解

初始解的生成方式有隨機生成和啟發(fā)式生成兩種。采用啟發(fā)式生成的初始解更為優(yōu)良，但個體較為集中，易使算法陷入局部最優(yōu)。為保持個體多樣性，且利于改進的GA-SA算法搜索到全局最優(yōu)解，本算法采用隨機方式生成初始種群，以使初始種群盡可能地均勻分布在整個解空間。

本階段研究配送中心與客戶之間的配送路徑問題，用三個向量表示一個完整的解，第一個矢量為車輛向量，第二個矢量為配送順序向量，第三個矢量為車輛所屬配送中心的向量。二級配送網絡編碼解碼中包含有編號為{1,2,…,n}的n位客戶、編號為{1,2,…,s}的s個配送中心以及編號為{1,2,…,k}的k輛二級運輸車輛。

假設有2個配送中心，編號為1,2；可支配二級運輸車輛4輛，編號為1,2,3,4；需要服務的客戶數為15位，編號為1,2,…,15，則配送方案編碼如下：

可以看出，二級配送網絡中，車輛1和車輛4從配送中心1出發(fā)，車輛2和車輛3從配送中心2出發(fā)?？蛻艟幪枌能囕v向量值表示服務該客戶的車輛編號，車輛向量對應的順序向量值表示車輛服務客戶的先后順序。如車輛1服務客戶3,4,8，對應配送順序為2,13,3，對應配送中心1，即車輛1從配送中心1出發(fā)先后服務客戶3,8,4。因此，解碼后得到的四條車輛路線表示如下：

2.3 適應度函數

2E-CVRP-CC模型以物流配送系統(tǒng)總成本最小為目標，考慮到二級配送網絡中顧客期望時間窗和車輛容量約束，對違反約束的染色體添加一個足夠大的懲罰值，以免生成不可行解。而當滿足客戶時間窗和二級車輛容量約束時，目標函數如下所示：

適應度函數的確定要結合求解問題本身而定，根據適應度值判斷個體的優(yōu)劣，并以此進行選擇操作。2ECVRP-CC模型是一個最小化組合優(yōu)化問題，目標函數值越小，對應的個體適應度就越大，解就越優(yōu)良。因此，本算法選用目標函數值加懲罰函數值的倒數作為適應度函數[17]，具體公式為：

其中，z i為第i條染色體對應的目標函數值，P1和P2分別表示違反客戶時間窗和二級車輛容量約束時產生的足夠大的懲罰成本（當未違反約束時，P1,P2=0，此時目標函數值由公式（25）計算），f i表示第i條染色體的適應度值。

2.4 遺傳操作

輪盤賭選擇：選擇算子以適應度作為衡量標準，對群體進行優(yōu)勝劣汰操作，使得適應度越高的個體被遺傳到下一代種群的概率也越大。然而，這種方法容易導致適應度高的個體大量繁殖，從而造成算法的搜索范圍過于局限。因此，將輪盤賭選擇算子結合精英保留策略，根據適應度值和精英策略，從父代和子代染色體中產生新一代染色體。

精英保留策略：遺傳算法中，后代染色體通常由父代染色體復制而來。采用精英保留策略進行選擇操作時，每一代種群中較好的一部分個體作為精英個體（精英染色體數目為種群規(guī)?！辆⒙剩?，直接保留到下一代，從而保證迄今為止最優(yōu)的個體不會被交叉、變異等遺傳操作破壞。

部分匹配交叉：交叉算子決定算法的全局搜索能力，是遺傳算法中的一種重要算子。它模擬生物自然進化過程，將選擇算子得到的兩條染色體互相交換部分基因，從而形成新個體。本文選用部分匹配交叉策略，通過隨機選擇兩個交叉點確定交叉區(qū)域，然后交換兩組基因的位置并進行沖突檢測，如圖2所示。具體步驟如下：

步驟1根據基于個體適應度值的自適應交叉率選擇父代染色體1和2，然后隨機選擇兩個不同的位置作為交叉點。自適應交叉概率更新公式如下所示：

其中，Pc為交叉率，Pcmax和Pcmin分別為最大交叉概率和最小交叉概率。f為個體的適應度值，fmax和favg分別為染色體適應度值的最大值和平均值。

步驟2將兩條父代染色體位于交叉區(qū)域內的基因進行互換。

步驟3做沖突檢測。本問題中，一個完整的解有三個向量，其中車輛向量和配送中心向量允許出現重復基因，而對于順序向量，每位顧客的配送順序唯一，故順序向量中不允許出現重復基因，因此，要對順序向量中交換的兩條父代染色體進行沖突檢測。其方法是，根據交換的兩組基因建立一個映射關系，如圖2所示，以2?3這一映射關系為例，可以看到父代染色體交換基因后，染色體1存在兩個基因2，這時將其通過映射關系轉變?yōu)榛?。以此類推，直至兩條染色體中的基因沒有沖突為止。

圖2 部分匹配交叉算子Fig.2 Partially-matched crossover operator

單點變異：變異算子決定算法的局部搜索能力，通過改變染色體中部分基因的位置，形成新的染色體，維持種群的多樣性。改進GA-SA算法采用單點變異算子，隨機選擇父代染色體中的兩個變異位置，交換兩個變異位置上的基因，得到一條新的后代染色體。

2.5 模擬退火操作

SA狀態(tài)函數：在算法迭代過程中，完成遺傳操作后，將遺傳操作得到的最優(yōu)解作為模擬退火操作的初始解，然后使用狀態(tài)函數生成新解。本算法中，狀態(tài)函數采用互換操作，隨機選擇每個向量中的四個位置，然后分別將第一個位置和第三個位置、第二個位置和第四個位置的基因進行互換，從而完成對初始解中車輛向量、順序向量和配送中心向量的更新操作。

Metropolis準則：對種群不斷進行遺傳操作的進化過程是一個優(yōu)勝劣汰的除差過程，不斷進化使得種群多樣性逐漸降低，這樣也導致算法容易陷入局部最優(yōu)解。因此，引入模擬退火算法中的Metropolis接受準則，以一定的概率接受較差解，從而使算法避免陷入局部最優(yōu)和過早收斂，具有全局優(yōu)化能力。Metropolis接受準則公式為：其中，T為當前溫度，f1和f2分別為當前解和新解的二級網絡配送成本。

2.6 第二階段：精確方法求解一級網絡

第二階段求解中心倉庫與配送中心之間的車輛路徑問題，同樣可視為單層VRP。由于一級網絡涉及節(jié)點數目不多，可利用精確方法快速得到最優(yōu)解。根據第一階段所求結果，首先計算各配送中心需求量，然后根據一級車輛容量為各配送中心安排車輛，得到一級路徑優(yōu)化方案。最終，得到2E-CVRP-CC模型的最優(yōu)解。綜上，本文所提出的兩階段啟發(fā)式算法流程圖如圖3所示。

圖3 兩階段啟發(fā)式算法流程圖Fig.3 Flowchart of two-stage heuristic algorithm

3 實驗結果與分析

首先，選用經典基準案例進行測試，驗證提出的兩階段啟發(fā)式算法求解2E-CVRP的性能；其次，使用模擬數據進行案例分析，證明2E-CVRP-CC模型的合理性和適用性以及算法的有效性。所有算法都在Dell Inspiron 14計算機上使用Matlab R2016a運行，具體配置為2.50 GHz Intel Core i7-6500U處理器，操作系統(tǒng)為Windows 10 64位。

3.1 算例參數設置

兩階段啟發(fā)式算法涉及的主要參數有，種群規(guī)模，迭代次數，最大、最小交叉概率，變異概率，初始溫度，終止溫度，降溫速度和內循環(huán)迭代次數等。通過一定的實驗測試和文獻參考[1，3]，算法參數設置如下：種群規(guī)模取80，迭代次數取1 000代，Pcmax=0.85,Pcmin=0.5,Pm=0.1,T0=2 000,T=20，降溫速度q取0.95，內循環(huán)迭代次數設置為100代。另外，結合帕累托定律，規(guī)定顧客總數的前20%為重要客戶（若重要客戶數n為非整數，則進行向上取整處理）。

為了測試所提出算法解決2E-CVRP-CC問題的效果，使用2E-CVRP的兩組基準案例進行測試，分別是Perboli等人[18]提出的Set2算例集和Hemmelmayr等[19]提出的Set5算例集。前者包含21個算例（只考慮Set2a和Set2b），包括21～50位客戶；后者包含9個算例（只考慮b系列），包括100或200位客戶。兩個案例包含信息有：中心倉庫和衛(wèi)星（配送中心）的數量及位置，一、二級車輛數量及容量，客戶位置和需求。兩個算例集均可在https：//www.univie.ac.at/prolog/research/TwoEVRP下載。

3.2 算法對比分析

為分析兩階段啟發(fā)式算法的性能，將本文算法求解基準案例的結果與前人的求解結果進行對比分析。同時，為了使求解結果更具有可比性，此處去除了目標函數（1）中的生鮮損耗成本、顧客時間窗懲罰成本以及倉庫和配送中心的建設成本，以使所提出算法的目標成本與各案例所包含成本相匹配。

表2為Perboli的Set2算例集求解結果，前兩列是各案例名稱以及目前已知最優(yōu)解[18](BKS)，3～6列是各算法得到的最優(yōu)結果，最后一列“Gap”表示本文算法求得的最優(yōu)結果(Best)與BKS的差距，計算公式為Gap=100%×(Best-BKS)/BKS。

表2將算法與Hemmelmayr等[19]（ALNS）、Perboli等[18]（Math-Heuristics）、Zeng等[20]（GRASP+VND）和許維勝等[21]（Multi-start）四篇文獻中所用算法進行對比分析。可以看出，ALNS和GRASP+VND算法性能整體表現良好，而Multi-start和Math-Heuristics算法與最優(yōu)結果相差較多。相比而言，兩階段啟發(fā)式算法在6個算例中求得最優(yōu)解，且E-n33-k4-s2-13算例求得的最優(yōu)解優(yōu)于目前已知最優(yōu)解BKS，可見本算法性能與整體表現良好的ALNS和GRASP+VND算法相差不多。另外，求解結果均值565.42最接近于最優(yōu)解BKS均值556.72，且與最優(yōu)解BKS的差距均值僅為1.54%。由此可見，在與其他四種算法的比較中，本文提出的兩階段啟發(fā)式算法可以在一定程度上較好地解決2E-CVRP問題。

表2 Set2算例集求解結果與比較Table 2 Solution results and comparisons of Set2

表3為Hemmelmayr的Set5算例集求解結果，Set5算例集包含100或200位客戶，屬于2E-CVRP問題的大規(guī)模算例，將本文算法與文獻[22]的HCC和BSHV算法、文獻[23]的STS和EDTS算法進行對比分析。

表3中記錄了各算法運行五次的最優(yōu)結果和均值，每個案例的最優(yōu)結果和均值加粗強調，且最優(yōu)解在五次運行測試中至少被檢索一次?？梢钥闯?，兩階段啟發(fā)式算法性能優(yōu)于STS和EDTS算法，與HCC算法最優(yōu)結果和均值的差距分別為8.5%和9.94%，與BSHV算法最優(yōu)結果和均值的差距分別為8.67%和10.49%。由此可見，提出的兩階段啟發(fā)式算法對于大規(guī)模問題能求得其近似最優(yōu)解。

表3 Set5算例集求解結果與比較Table 3 Solution results and comparisons of Set5

綜上，結合Set2算例集和Set5算例集可以看出，提出的兩階段啟發(fā)式算法對于小規(guī)模問題均能找到最優(yōu)解，對于中大規(guī)模問題能求得其近似最優(yōu)解，且與其他算法差距不大，因此本算法具有一定的競爭力。

3.3 算法收斂性分析

文中提出兩階段啟發(fā)式算法求解2E-CVRP-CC模型，其中第一階段求解二級配送網絡使用改進的GASA算法，第二階段求解一級配送網絡使用精確方法。為探究改進的GA-SA算法求解2E-CVRP-CC問題的能力，記錄其求解基準案例的二級配送網絡時每次迭代的運行結果并繪制出迭代圖，選取四個不同的案例迭代圖進行收斂性分析。

選取Set2算例中顧客數量為32的E-n33-k4-s3-17、E-n33-k4-s4-5、E-n33-k4-s7-25、E-n33-k4-s14-22四個案例，收斂曲線如圖4所示?？梢钥闯觯惴ńY果在100代以內快速下降，500代左右算法已收斂到最優(yōu)結果附近，500～800代之內算法下降趨勢減弱并逐漸收斂于最優(yōu)結果。

圖4 四個基準案例收斂曲線Fig.4 Convergence curves of four classic benchmarks

4 模擬案例

4.1 單中心倉庫

為驗證2E-CVRP-CC模型的合理性和適用性，本案例擬選用1個中心倉庫，3個備選配送中心，以滿足50位客戶的需求。中心倉庫和備選配送中心的位置、容量和建設成本如表4所示。客戶位置、需求量和時間窗信息如表5所示，其中時間窗以上午9點為基準點，單位為小時，由于版面限制，此處只列出前15位客戶相關信息。

表4 中心倉庫和備選配送中心信息表Table 4 Information sheet for central warehouse and alternative distribution centers

表5 部分客戶信息表Table 5 Information sheet for some customers

本例中使用的部分參數設置如3.1節(jié)所示。根據實際情況和社會經驗，使用的其他參數設置如下：一級車輛容量為200 kg，固定成本200元/輛，單位運輸費用為0.53元/km；二級車輛容量為60 kg，固定成本為100元/輛，單位運輸費用為0.3元/km，行駛速度為30 km/h，最長行駛時間Tmax為6 h；可用一級車輛數為3輛，可用二級車輛數為7輛。單位時間內單位產品的價值損耗系數ρ為0.5元，車輛在客戶點的服務時間與貨物重量有關，單位重量產品的服務時間為0.02 h。另外，由前文可知，顧客總數的前20%為重要客戶（表5中編號加粗者為重要客戶）。重要客戶單位時間窗偏離量費用c1為0.5元，普通客戶單位時間窗偏離量費用c2為0.1元。

基于上述數據，運用前文提出的兩階段啟發(fā)式算法求解本案例，運行算法30次，選擇其中最佳優(yōu)化結果。結果顯示，第一階段算法求出的二級配送網絡選擇開放編號為S1和S2的配送中心，使用二級車輛數為7輛，相關經濟成本為4 840.49元。第二階段算法根據開放的配送中心和二級路徑優(yōu)化方案求解出一級運輸路徑，使用一級車輛數為2輛，相關經濟成本為30 402.71元。解碼后，一、二級網絡路徑優(yōu)化方案如圖5。

圖5 一、二級網絡路徑優(yōu)化方案Fig.5 Primary and secondary network path optimization scheme

表6展示了兩階段啟發(fā)式算法求解2E-CVRP-CC模型的最佳優(yōu)化結果。結果顯示，2E-CVRP-CC模型的物流配送網絡總成本為35 243.20元。從表6中可以看出，車輛1至車輛7的載重量均接近滿載狀態(tài)，這說明運輸車輛不僅滿足了容量限制，而且車輛利用率較高。從運輸成本看，7輛車的運輸成本均不高，這是由于客戶間距離較近造成的。從時間窗懲罰成本看，每輛車都有一定的懲罰成本，其原因是一些客戶的期望時間窗沒有得到滿足。對于10位重要客戶而言，其中8位客戶的期望時間窗得到滿足，重要客戶時間窗的滿足率達到了80%。這說明，對客戶按重要性進行分類處理，通過增大重要客戶時間窗偏離量費用，可以提高重要客戶的時間窗滿足率，進而提高了整體客戶滿意度，并使配送企業(yè)穩(wěn)定了優(yōu)質客戶資源。從損耗成本看，除車輛固定成本、中心倉庫和配送中心的建設成本外，損耗成本在總成本中占比最高。這表明，在滿足客戶時間窗的前提下，盡可能減少生鮮產品的損耗費用，可以使整體目標達到最優(yōu)。

表6 二級網絡最優(yōu)結果Table 6 Optimal result for the second echelon network

4.2 多中心倉庫

為驗證提出的兩階段啟發(fā)式算法對于求解多中心倉庫的生鮮配送兩級車輛路徑問題的性能，本案例擬選用3個備選中心倉庫，5個備選配送中心以滿足100位客戶的需求。將本文算法求得的最優(yōu)結果與標準粒子群算法（PSO）、蟻群算法（ACO）、遺傳算法（GA）和模擬退火算法（SA）求解結果進行對比分析，每種算法的種群大小為80，最大迭代次數為1 000，運行算法30次，選擇其中最佳優(yōu)化結果。

五種算法最優(yōu)結果對比如表7所示。從表7中可以看出，本文算法的最優(yōu)解相較于PSO而言，可使總成本降低4.22%，重要客戶時間窗滿足率提高37.5%；相較于ACO而言，可使總成本降低2.42%，重要客戶時間窗滿足率提高18.75%；相較于GA而言，可使總成本降低1.29%，重要客戶時間窗滿足率提高12.5%；相較于SA而言，可使總成本降低0.61%，重要客戶時間窗滿足率提高6.25%。因此，相較于其他四種算法而言，本文算法得到的結果最優(yōu)。

表7 五種算法最優(yōu)結果對比Table 7 Optimal results of five algorithms

算法迭代效果對比如圖6所示。本文采用兩階段啟發(fā)式算法求解該問題，第一階段使用改進的GA-SA算法求解二級網絡，第二階段使用精確方法求解一級網絡。為保證算法對比的統(tǒng)一性，其他四種算法和本文算法保持一致，即第一階段分別使用PSO、ACO、GA和SA求解二級網絡，第二階段求解一級網絡均使用精確方法。因此，圖6的算法迭代對比圖表示各算法求解二級網絡成本的迭代過程。從圖6中可以看出，五種算法都可以得到最優(yōu)結果，但GA-SA求得的結果最優(yōu)。另外，從收斂速度看，GA-SA在450代左右已收斂到最優(yōu)值附近，在580代左右已逐漸收斂于最優(yōu)值；而PSO、ACO和GA均在600代左右才開始收斂于最優(yōu)值附近；SA在300代左右收斂于最優(yōu)值附近，在600代左右逐漸收斂于最優(yōu)值，雖然SA的收斂速度優(yōu)于GA-SA，但其求得的最優(yōu)值劣于GA-SA求得的最優(yōu)值。

圖6 算法迭代對比圖Fig.6 Comparison figure of five algorithms iteration

因此，由上述的對比分析可知，本文提出的算法對于求解多中心倉庫的生鮮配送兩級車輛路徑問題是可行且有效的。

5 結語

本文研究了生鮮產品冷鏈物流背景下的兩級容量有限車輛路徑問題，考慮了客戶分類，將客戶按重要性分為重要客戶和普通客戶兩類，以物流配送網絡總成本最小為目標建立了優(yōu)化模型。設計兩階段啟發(fā)式算法求解該模型，第一階段使用改進的GA-SA算法求解二級配送網絡，第二階段使用精確方法求解一級配送網絡。GA-SA算法改進如下：（1）采用隨機方式生成初始種群，以使初始種群盡可能地均勻分布在整個解空間，保持種群的多樣性；（2）將輪盤賭選擇機制結合精英保留策略，保留優(yōu)秀個體；（3）采用部分匹配交叉算子結合自適應交叉概率，維持種群多樣性，增強算法的全局搜索能力；（4）GA和SA兩種算法的結合避免算法易于陷入局部最優(yōu)解，彌補單一啟發(fā)式算法的局限性。

為驗證提出的兩階段啟發(fā)式算法求解2E-CVRP的能力，選取Perboli提出的Set2算例集和Hemmelmayr提出的Set5算例集，共30個基準案例，分別將所提出算法與四種算法進行對比分析。結果表明，本文算法對于小規(guī)模問題均能找到最優(yōu)解，對于中大規(guī)模問題能求得其近似最優(yōu)解，且與其他算法差距不大。具體而言，對于Perboli提出的21個中小規(guī)?；鶞拾咐瑑呻A段啟發(fā)式算法在6個算例中求得最優(yōu)解，另有1個算例求得更優(yōu)解，整體求得結果與最優(yōu)解的差距Gap均值僅為1.54%。對于Hemmelmayr提出的9個大規(guī)?；鶞拾咐疚乃惴ㄐ阅軆?yōu)于STS和EDTS算法，與HCC算法最優(yōu)結果和均值的差距分別為8.5%和9.94%，與BSHV算法最優(yōu)結果和均值的差距分別為8.67%和10.49%。另外，對算法的收斂性進行了測試分析，結果表明，算法在前期就能快速收斂于最優(yōu)值附近，且在不同算例中表現穩(wěn)定。

為探究提出的2E-CVRP-CC模型與算法的適用性，基于模擬數據進行了案例分析。最終的結果分析表明：（1）車輛載重量均接近滿載狀態(tài)，說明運輸車輛不僅滿足了容量限制，而且車輛利用率較高；（2）對客戶按重要性進行分類處理，通過增大重要客戶時間窗偏離量懲罰程度，可以提高重要客戶的期望時間窗滿足率，進而提高整體客戶滿意度并維持配送企業(yè)優(yōu)質客戶資源；（3）本文提出的兩階段啟發(fā)式算法對于求解多中心倉庫的生鮮配送兩級車輛路徑問題也是可行且有效的。

綜上，本文可為生鮮配送的兩級車輛路徑問題提供決策支持，對保持企業(yè)優(yōu)質客戶資源，提高企業(yè)配送效率和客戶滿意度具有一定參考價值。但是，本文也存在一定的局限性，比如只從經濟角度考慮了物流配送系統(tǒng)總成本最小，而未考慮運輸過程中的實時路況，以及各級網絡的多車型混合配送問題，未來可就此進行進一步的研究。