面向多車場冷鏈物流配送的改進(jìn)正余弦算法

路世昌，劉丹陽

遼寧工程技術(shù)大學(xué)工商管理學(xué)院，遼寧 葫蘆島 125105

冷鏈物流運輸是指客戶所需貨品在整個運輸網(wǎng)絡(luò)體系中始終處于預(yù)先設(shè)定的低溫環(huán)境中，從而確保貨品的質(zhì)量。近年來，社會經(jīng)濟的快速發(fā)展推動了居民飲食結(jié)構(gòu)體系的轉(zhuǎn)變，人們對瓜果、水產(chǎn)品及新鮮肉禽制品等冷鏈?zhǔn)称返男枨罅靠焖偕仙?。一方面，高品質(zhì)的生活需求極大地促進(jìn)了我國冷鏈產(chǎn)業(yè)的發(fā)展。同時，以上貨品對環(huán)境溫度、運輸包裝等因素敏感性強，且存在易腐爛、易變質(zhì)、新鮮度難以長效保持等特征，必須依托冷鏈物流進(jìn)行配送[1-2]。結(jié)合以上背景，開展冷鏈物流配送方面的研究具有極為重要的意義。

冷鏈物流運輸問題可歸結(jié)為復(fù)雜問題特征、目標(biāo)體系和約束限制下的車輛路徑問題（vehicle routing problem，VRP）[3]。本文所研究的多車場冷鏈物流配送問題相比于經(jīng)典的VRP模型增加了以下三方面的復(fù)雜因素：（1）以總成本為指標(biāo)、優(yōu)化目標(biāo)組成結(jié)構(gòu)復(fù)雜，成本體系囊括了車輛成本、運輸成本、制冷成本和貨損成本；（2）考慮了多中心聯(lián)合配送，需要兼顧不同中心的運輸線路構(gòu)造特征以及配送能力（具體表現(xiàn)為各中心運輸車數(shù)目約束）；（3）要求遵循嚴(yán)格的時效約束，即嚴(yán)格限制每個客戶接受服務(wù)的最晚時間，旨在確保每個客戶能夠在滿意的時間范圍內(nèi)獲取所需貨品。VRP 問題已被證明具有NP 難復(fù)雜性，而當(dāng)前模型的復(fù)雜特征更加劇了問題的求解難度。鑒于此，決策算法的設(shè)計開發(fā)在冷鏈物流配送研究中占據(jù)重要地位。

冷鏈物流配送問題的決策方法可分為精確算法、構(gòu)造式算法和進(jìn)化算法三大類[4]。精確算法包括整數(shù)規(guī)劃建模、分支定界、分支定價等，例如：Deng 等[5]研究了一類帶有時效約束、貨物不兼容因素、取送同步等特征冷鏈物流配送問題，并構(gòu)建了分支定價算法以優(yōu)化運輸、制冷和貨損成本總和。盡管此類方法獲取小規(guī)模問題的精確解，但運行時間隨著問題規(guī)模的增加呈現(xiàn)爆炸式增長，且該類方法無法處理具有復(fù)雜約束和目標(biāo)的問題。構(gòu)造式算法通過組合調(diào)度規(guī)則獲取運輸方案，該算法對問題設(shè)置有較高依賴性，對當(dāng)前模型的約束、目標(biāo)進(jìn)行調(diào)整將導(dǎo)致原先性能較優(yōu)的調(diào)度規(guī)則生成糟糕方案的情形[6]。近年來，進(jìn)化算法取得了長足發(fā)展，這為具備復(fù)雜目標(biāo)體系和約束條件的冷鏈物流配送問題提供了新的求解思路。Zhang等[7]研究了一類考慮碳排放因素的冷鏈物流配問題，借助蟻群算法構(gòu)建決策方法體系，優(yōu)化包含運輸成本、貨損、碳排放等六類成本指標(biāo)總和，該研究通過實例分析以驗證算法的有效性。Dou等[8]學(xué)者對冷鏈物流配送與中心選址的組合問題進(jìn)行了建模，構(gòu)建以最優(yōu)化總成本指標(biāo)為目標(biāo)的數(shù)學(xué)模型，并創(chuàng)立了免疫狼群混合求解算法，該研究通過算法對比實驗驗證了所構(gòu)建算法的高效性。盡管如此，借助進(jìn)化算法求解冷鏈物流配送問題仍需合理解決以下問題：（1）構(gòu)建高效的編解碼方法，實現(xiàn)算法與問題適配；（2）提升基本算法的搜索性能，克服易陷入局部最優(yōu)、搜索停滯等缺陷[9]。鑒于此，本文構(gòu)建了改進(jìn)正余弦算法（ESCA）求解多車場冷鏈物流配送問題。

正弦余弦優(yōu)算法，簡稱SCA，是由Mirjalili[10]于2016年提出的一種新型的高效進(jìn)化算法。SCA 算法具有架構(gòu)簡單、控制參數(shù)少、迭代效率高等優(yōu)勢，相關(guān)研究表明SCA算法相較于遺傳、粒子群等經(jīng)典進(jìn)化算法具有更優(yōu)的尋優(yōu)性能[11]。目前，SCA已經(jīng)在眾多工程領(lǐng)域獲取了應(yīng)用，包括機器人路徑規(guī)劃、圖像處理、車間調(diào)度等[12]。例如：馬瑩瑩等[13]構(gòu)建了基于SCA 的混合算法，并將其應(yīng)用于機器人路徑規(guī)劃問題，通過各類環(huán)境的下算法的對比實驗證明了改進(jìn)算法求解機器人路徑規(guī)劃問題的高效性。鑒于SCA 算法的良好表現(xiàn)，本文將其運用于本文所研究的冷鏈物流配問題。

由以上文獻(xiàn)綜述可知，盡管本文所研究的冷鏈物流問題的特征在相關(guān)文獻(xiàn)中有所涉獵，但綜合考慮客戶單邊硬時間窗、多中心聯(lián)合調(diào)度和各中心車輛使用數(shù)約束的冷鏈物流調(diào)度研究相對較少，同時鮮有文獻(xiàn)構(gòu)建基于SCA算法這一優(yōu)質(zhì)進(jìn)化算法的冷鏈調(diào)度方法。由No-Free-Lunch 理論可知，尚不存在一種決策方法能夠完美地解決所有的冷鏈調(diào)度問題[14]。鑒于冷鏈物流的實際意義和調(diào)度算法研究的工程價值，本文針對一類考慮多中心聯(lián)合配送和時間窗約束的冷鏈物流配送問題進(jìn)行了建模，并提出了改進(jìn)正余弦算法，通過案例研究和算法對比實驗證明了該算法的優(yōu)化性能。

1 問題模型

1.1 問題描述

如圖1所示，展示了當(dāng)前所研究的多車場冷鏈物流配送問題的示意圖。

圖1 問題示意圖Fig.1 Schematic diagram of considered problem

運輸車從多個中心出發(fā)向客戶供應(yīng)物資，為提升配送效率與客戶滿意度，需綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)、客戶需求、車輛載荷和配送時效等因素，在此基礎(chǔ)上合理規(guī)劃配送方案。本文從成本優(yōu)化視角對當(dāng)前問題進(jìn)行建模，力求在滿足客戶需求的同時降低運輸過程所產(chǎn)生的成本費用，具體包括車輛成本、運輸成本、制冷成本和貨損成本。

為對當(dāng)前運輸網(wǎng)絡(luò)進(jìn)行合理化建模，在此作如下假設(shè)：（1）配送中心和客戶的空間位置已知，網(wǎng)絡(luò)中任意兩點間的路徑距離和用時均已知且為定值；（2）每個中心的車輛總數(shù)已知，運輸車從各自中心出發(fā)、完成配送任務(wù)后返回所屬中心；（3）所有客戶的需求均已知，且要求每個客戶接受服務(wù)的時間不得晚于規(guī)定的時間閾值；（4）采用同型運輸車負(fù)責(zé)配送任務(wù)，當(dāng)前車型的載荷和成本系數(shù)等均一致且為已知量；（5）規(guī)劃期內(nèi)每輛運輸車只能被調(diào)度一次，運輸過程不得超載；（6）每個客戶僅能由一輛運輸車訪問一次，不允許需求拆分；（7）相比于不同空間節(jié)點之間的運輸用時而言，每個客戶點處的裝卸時長較短，建模過程不予考慮。

為實現(xiàn)降本增效的目標(biāo)，需合理決策以下三個子問題：（1）確定每個中心覆蓋的客戶范圍；（2）指定每輛運輸車服務(wù)的客戶集合；（3）規(guī)劃各輛運輸車的行進(jìn)路線。

1.2 符號定義

基于以上問題描述，在此定義問題參數(shù)和決策變量以便于構(gòu)建多車場冷鏈物流配送問題的數(shù)學(xué)模型。

（1）集合

ND：配送中心集合。

NC：客戶節(jié)點集合。

N：所有位置節(jié)點集合，即N=ND∪NC。

K：車輛集合。

（2）下標(biāo)

k：車輛索引，k∈K。

i,j：節(jié)點索引，i,j∈N。

（3）參數(shù)

dij：i和j間的路徑距離，i,j∈N且i≠j。

τij：i和j間的路徑用時，i,j∈N且i≠j。

qi：客戶點i的需求量，i∈Nc。

Q：運輸車的載重。

Li：客戶點i允許的最晚到達(dá)時間，i∈NC。

Ki：配送中心i處可用的車輛總數(shù)，i∈ND。

cveh：運輸車啟動成本。

cvar：單位里程的油耗成本。

cpri：單位需求量的單價。

r：需求的損耗系數(shù)。

ccool：單位時長的制冷成本。

（4）變量

xijk：若車輛k從i駛向j,xijk=1；否則，xijk=0,其中i,j∈N,k∈K,且i≠j。

yki：若節(jié)點i由車輛k服務(wù)，yki=1；否則，yki=0,其中i∈NC,k∈K。

ti：節(jié)點i接受服務(wù)的時間，i∈N。

1.3 數(shù)學(xué)建模1.3.1 成本分析

（1）車輛成本

冷鏈物流依托冷藏車向所有客戶供應(yīng)所需物資，啟動冷藏車需耗費一筆車輛成本，其組成包括駕駛員工資、車輛折舊與保養(yǎng)費用等。冷鏈物流配送所需車輛成本僅與所啟動的車輛數(shù)目相關(guān)，計算公式為：

其中，cveh表示單輛冷藏車的啟動成本。

（2）運輸成本

運輸成本的核心組成為車輛配送過程所消耗的燃油成本，其數(shù)值大小與車輛總行駛距離呈正相關(guān)。借鑒同類相關(guān)研究成果[7]，運輸成本f2的計算公式定義為：

其中，cvar表示冷藏車單位里程的油耗成本。

（3）制冷成本

冷鏈配送的制冷成本主要來自維持車廂內(nèi)溫度所消耗的制冷劑成本。研究表明，制冷劑的消耗量與運輸車的裂化程度、車廂內(nèi)外溫度、車輛輻射面和傳熱率等因素相關(guān)。鑒于本文中的運輸網(wǎng)絡(luò)采用同型運輸車，車輛各類參數(shù)均一致，同時配送過程中車廂內(nèi)外環(huán)境相對穩(wěn)定。參考同類研究[7]，制冷成本近似為與車輛運輸時長正相關(guān)，公式為：

其中，ccool表示單位時長所產(chǎn)生的制冷成本。

（4）貨損成本

隨著運輸時間的增長，所配送產(chǎn)品（包括疫苗、生鮮等）將產(chǎn)生一定貨損。依據(jù)相關(guān)研究[7]，選取公式α=1-e-r·t表述產(chǎn)品損耗量占比與運輸時長的關(guān)系，其中α為損耗量，r表示當(dāng)前貨品對時間的敏感系數(shù)，t為運輸時長，基于此貨損成本可定義為：

其中，cpri表示單位需求量的單價。

1.3.2 數(shù)學(xué)模型

基于問題描述、符號定義及成本分析，參照相關(guān)文獻(xiàn)研究[7]，構(gòu)建多車場冷鏈物流配送問題的數(shù)學(xué)模型，內(nèi)容如下：

其中，公式（5）為目標(biāo)函數(shù)，表示優(yōu)化整個運輸網(wǎng)絡(luò)的總成本，包括車輛成本、運輸成本、制冷成本和貨損成本。約束（6）表示每個客戶點僅被一輛車服務(wù)一次，約束（7）和（8）表示每個客戶節(jié)點的出入度均為1，約束（9）表示每輛運輸車從配送中心出發(fā)且完成配送任務(wù)后再返回原配送中心，約束（10）用于約束車輛不在配送中心間通行，約束（11）表示用于限制每個中心可使用的車輛數(shù)，約束（12）表示運輸車的裝載能力約束，約束（13）表示配送連續(xù)性約束，約束（14）用于限制每個客戶接受服務(wù)的時間不得晚于規(guī)定的閾值，約束（15）～（17）用于表示自變量取值范圍約束。

2 基本算法原理

本文提出的ESCA算法以SCA算法為模板，同時融合了生物搜索算法（symbiotic biology search algorithm，SOS）的進(jìn)化機制，在此歸納相關(guān)的算法原理。

2.1 SCA算法

SCA算法以隨機方法構(gòu)建初始解，同時借助正余弦變換生成子代解，相關(guān)內(nèi)容包括：

（1）構(gòu)建初始解

以D表示編碼長度，?d=1,2,…,D，各維編碼取值范圍定義為。以D維數(shù)組x=(x1,…,xd,…)表示解，其初始化公式為：

其中，rand(0,1)為[0，1]上的隨機量。

（2）生成子代解

給定候選解x，SCA算法借助正余弦變換以及候選解同當(dāng)前最優(yōu)解間的位置差分量生成子代解x′，數(shù)學(xué)公式為：

其中，xd和x′d分別為父代解向量和子代解向量在維度d上的編碼取值，x*d為當(dāng)前最優(yōu)解x*在維度d上的編碼取值。r2、r3和r4為隨機參數(shù)，r2∈[0,2π],r3∈[0,2],r4∈[0,1]。r1為自適應(yīng)參數(shù)，其更新公式為：

其中，a為常數(shù)，建議取值為2，g為當(dāng)前迭代次數(shù)，G為最大迭代次數(shù)。迭代初期，r1取值較大，算法側(cè)重全局搜索；迭代后期，r1取值較小，算法傾向于局部開發(fā)。

基于以上描述，如圖2展示了SCA算法的完整運行流程。

圖2 SCA算法框架Fig.2 Framework of SCA

2.2 互利共生進(jìn)化

SOS 算法通過模擬生態(tài)系統(tǒng)中生物間的共生行為實現(xiàn)數(shù)學(xué)問題的決策尋優(yōu)，其運行過程包括互利共生、偏利共生、寄生三點概念[15]。本文借鑒并升級SOS算法的互利共生行為以強化SCA算法的尋優(yōu)性能，以x和x?分別表示當(dāng)前種群的兩個相異個體，SOS算法的婚禮共生環(huán)節(jié)采用以下公式生成子代個體x′和x?′：

其中，MV表示x和x?的共同載體，rand(0,1)為[0，1]上的隨機數(shù)，x*為當(dāng)前最優(yōu)解，學(xué)習(xí)參數(shù)BF1、BF2 為隨機整數(shù)，取值集合為{0，1}。

3 ESCA算法設(shè)計

3.1 編碼與解碼

編碼過程：采用實數(shù)編碼機制，編碼長度等于客戶總數(shù)|NC|，取值范圍定義[0，1]。

解碼過程：采用最小位置值規(guī)則將實數(shù)編碼映射為1～|NC|的客戶優(yōu)先級排列，其中位置靠前的客戶享有較高優(yōu)先級接受配送[16]?；诖巳诤蠁l(fā)式規(guī)則構(gòu)造配送線路，規(guī)則包括：（1）選中客戶序列中尚未接受配送服務(wù)的第一個節(jié)點作為新配送線路的首客戶；（2）綜合考慮各中心車輛使用數(shù)約束和最短距離規(guī)則確定發(fā)車中心，若所有中心均無剩余用車，則構(gòu)建虛擬路線，發(fā)車中心選中距離最近的中心；（3）遍歷客戶序列中尚未接受服務(wù)的客戶節(jié)點，依據(jù)運輸車裝載能力和各客戶的時間窗約束確定配送線路。

如圖3 所示，給出示意說明以輔助理解上述過程，問題參數(shù)定義如下：（1）兩個中心服務(wù)11 個客戶，客戶的需求量均設(shè)置為1（單位：t），中心1、2的車輛數(shù)分別置為3和2，車輛載重為3 t；（2）在空間維度，圖3中各個節(jié)點的坐標(biāo)位置反應(yīng)了各個設(shè)施（中心或客戶）間的遠(yuǎn)近；（3）在時間維度，為方便闡述，假設(shè)各個設(shè)施間的路徑用時均為10（單位：min），除客戶9～11 接受服務(wù)的最晚時間設(shè)置為30 min，剩余客戶最晚時間設(shè)置為10。給定編碼（0.08，0.18，0.46，0.61，0.28，0.32，0.62，0.71，0.73，0.36，0.45），采用最小位置值規(guī)則可得序列（1，2，7，8，3，4，9，10，11，5，6），并依照上述路徑構(gòu)造規(guī)則生成圖中的五條線路。

圖3 編碼與解碼示意圖Fig.3 Encoding and decoding diagram

3.2 個體評估方法

結(jié)合前述內(nèi)容可知，本文提出的編解碼方法綜合考慮了就近裝載、中心可使用車輛數(shù)、車輛裝載能力和客戶時間窗約束等問題特征，簡潔高效、易于實現(xiàn)。同時，鑒于部分節(jié)點的時間窗約束和中心車輛數(shù)約束尚未滿足，在此借助懲罰函數(shù)法構(gòu)造評價函數(shù)以協(xié)助種群進(jìn)化，數(shù)學(xué)公式為：

其中，F(xiàn)和f分別表示候選解的評價函數(shù)和目標(biāo)函數(shù)值，后兩項分別表示時間窗與中心用車數(shù)這兩類約束的違反量總和，懲罰系數(shù)λ1和λ2取值為正。

3.3 反向?qū)W習(xí)初始化

隨機初始化方法一定程度上限制了尋優(yōu)效率，鑒于此，本文將反向?qū)W習(xí)機制嵌入種群初始化過程，旨在提升初始解的質(zhì)量[17]。

給定編碼長度D,?d=1,2,…,D，編碼取值范圍置為。候選解以D為數(shù)組x=(x1,…,xd,…) 表示，x對應(yīng)的反向解定義如下：

基于此，給出改進(jìn)初始化的運行流程：

步驟1令i←1，d←1，轉(zhuǎn)步驟2。

步驟2若滿足i≤P轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟7。

步驟3若滿足d≤D轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟5。

步驟4隨機生成，據(jù)此獲取，轉(zhuǎn)步驟5。

步驟5令d←d+1，若滿足d ＞D轉(zhuǎn)步驟6；否則轉(zhuǎn)步驟3。

步驟6生成隨機解xi和反向解，令i←i+1，轉(zhuǎn)步驟2。

步驟7選擇中表現(xiàn)良好前P個解組建初始種群。

其中，P為種群規(guī)模，xi為采用隨機方式生成的第i個解，為xi的反向解，和分別表示xi和在維度d上的編碼數(shù)值。上述過程將構(gòu)造隨機解和反向解這兩類集合，隨后挑選其中優(yōu)質(zhì)解組建初始種群。

3.4 混合進(jìn)化機制

ESCA算法通過耦合SCA和SOS兩種算法，構(gòu)建以正余弦進(jìn)化和互利共生進(jìn)化為特征的兩階段混合進(jìn)化機制，旨在增強標(biāo)準(zhǔn)SCA算法的性能，實現(xiàn)內(nèi)容梳理如下：

（1）正余弦進(jìn)化

在算法每次迭代的初期，采用隨機方式將整個種群分成兩個大小相等的子種群Pop1和Pop2，兩個子種群分別采取正弦和余弦方式構(gòu)建子代解：

其中，xd和分別表示父代解向量x和子代解向量x′在維度d上的編碼取值，為當(dāng)前最優(yōu)解x*在維度d上的編碼取值。r2、r3和r4為隨機量，r2∈[0,2π],r3∈[0,2],r4∈[0,1]。自適應(yīng)參數(shù)r1采用非線性調(diào)節(jié)機制[18]：

其中，g和G分別為當(dāng)前和最大迭代次數(shù)。

（2）互利共生進(jìn)化

種群完成正余弦進(jìn)化后，算法采用隨機方式匹配Pop1和Pop2中的解。以x和?表示一對配匹配個體，子代個體x′和x?′更新如下：

其中，rand(0,1)為區(qū)間[0，1]內(nèi)的隨機量，x*為當(dāng)前最優(yōu)解，?為采隨機選擇的解個體，參數(shù)BF1 和BF2 調(diào)整為連續(xù)量。

3.5 鄰域搜索方法

為進(jìn)提升算法后期跳出局部最優(yōu)的能力，本文將變鄰域下降搜索融合于ESCA算法[19]。變鄰域下降搜索具有較優(yōu)的局部發(fā)掘能力，該方法通過系統(tǒng)地探索候選解的鄰居解以獲得問題的優(yōu)質(zhì)局部解，其核心在于鄰域結(jié)構(gòu)的設(shè)計。本文采用交換和插入兩種鄰域結(jié)構(gòu)，對應(yīng)的實現(xiàn)過程梳理如下：

（1）交換：隨機選擇候選解的兩處位置，交換相應(yīng)的編碼生成新的解（圖4（a））。

圖4 變異算子Fig.4 Mutation operators

（2）插入：隨機選擇候選解的兩處位置，并將其中一處位置上的編碼插入到另一處位置前面生成新的解（圖4（b））。

3.6 ESCA算法流程

結(jié)合前述內(nèi)容，圖5 給出了基于ESCA 算法求解多車場冷鏈物流配送問題的框架。

圖5 ESCA算法框架Fig.5 Framework of ESCA

4 仿真實驗

為驗證ESCA 算法求解多車場冷鏈物流配送問題的尋優(yōu)性能，在此開展數(shù)值仿真實驗。實驗包括以下兩部分：（1）實例仿真分析，旨在展示當(dāng)前模型和算法的有效性；（2）算法性能驗證，開展不同規(guī)模算例的仿真實驗，分析改進(jìn)策略的有效性，驗證ESCA 算法同其他優(yōu)秀算法相比的有力競爭性。模擬平臺選用Matlab2017b，計算機處理器參數(shù)為2.4 GHz、內(nèi)存4 GB、Intel?CoreTMi5-2430M。

4.1 實例仿真分析

4.1.1 實例參數(shù)

某市25個客戶點亟需物資供應(yīng)，表1歸納了每個客戶點的空間位置坐標(biāo)（以x、y坐標(biāo)表示，單位：km）、需求量（單位：t）和時間窗（單位：min）。同時，存在三個中心提供物資配送服務(wù)，表2梳理了每個中心的空間位置坐標(biāo)以及可供使用的運輸車數(shù)目。

表1 客戶點參數(shù)Table 1 Information of clients

表2 配送中心參數(shù)Table 2 Information of distribution centers

在配送過程中，車輛勻速行駛且車速為30 km/h，車輛額定載荷Q值為1.2 t。同時，整個運輸網(wǎng)絡(luò)體系中不同節(jié)點間的距離數(shù)值選用歐氏距離。其他參數(shù)定義如下：運輸車啟動成本參數(shù)cveh設(shè)定為50 元/車，油耗成本參數(shù)cvar設(shè)定為5 元/km，需求量單價參數(shù)cpri設(shè)定為2 000 元/t，需求損耗參數(shù)r設(shè)定為0.005，制冷成本參數(shù)ccool設(shè)定為40 元/h。

4.1.2 結(jié)果分析

為演示當(dāng)前模型的有效性和算法的性能，結(jié)合以上參數(shù)分別測算不考慮時間窗和考慮時間窗兩個案例的模型。測試算法選用SCA、ISA（improved simulated annealing algorithm）[20]和ESCA。其中，SCA 和ESCA算法的對比用于驗證總體改進(jìn)措施的有效性，ISA為近年來提出的一種求解車輛調(diào)度問題的高效算法，ISA和ESCA 的對比用于展示本文提出的改進(jìn)算法與目前優(yōu)秀算法的競爭力對比。

依據(jù)實際測試效果及相關(guān)研究，算法參數(shù)設(shè)置如下：所有算法的種群規(guī)模取20、總迭代次數(shù)取500，ESCA算法中鄰域搜索方法的循環(huán)次數(shù)取5，ISA 算法的其他參數(shù)選用參考文獻(xiàn)的推薦數(shù)值。對于每個算例，三種算法均獨立模擬仿真20 次，表3 梳理歸納了三種測試算法所得的最優(yōu)、均值和最劣目標(biāo)函數(shù)值和相應(yīng)的相對偏差百分比RPD（relative percentage deviation），RPD 定義如下[21]：

表3 實例優(yōu)化結(jié)果Table 3 Simulation results of case study

其中，fbest為三種測試算法在共計60 次獨模擬仿真中所得最優(yōu)目標(biāo)函數(shù)值，f對應(yīng)最優(yōu)、均值和最劣目標(biāo)函數(shù)的數(shù)值。

同時，圖6 和圖7 分別給出SCA、ISA 和ESCA 三種算法所獲取的最優(yōu)路徑以及相應(yīng)的算法進(jìn)化曲線對比圖。

圖6 不考慮時間窗的算例的最優(yōu)解Fig.6 Optimum of model without time windows

圖7 考慮時間窗的算例的最優(yōu)解Fig.7 Optimum of model with time windows

此外，對考慮時間窗的算例，表4 歸納了三種算法所獲取的最優(yōu)線路的明細(xì)，表5給標(biāo)識了相應(yīng)的客戶接受服務(wù)的時間。

表4 考慮時間窗模型中的最優(yōu)線路Table 4 Final routes of model with time windows

表5 考慮時間窗模型中的客戶到達(dá)時間Table 5 Reach times of model with time windows

觀察實驗結(jié)果，可得如下結(jié)論：

（1）基于實例參數(shù)，圖6 和圖7 中的路徑曲線、表4中最優(yōu)線路明細(xì)和表5 中每個客戶接受服務(wù)的時間點數(shù)值可驗證三種算法的可行性和有效性，即算法所尋得的結(jié)果均滿足模型的約束設(shè)置，包括中心可供使用的車輛數(shù)約束、每條運輸線路的裝載負(fù)荷約束、時間窗約束等，并且驗證了本文所構(gòu)建的編解碼方法以及個體評估函數(shù)能夠較好地適配算法與決策問題。

（2）對比不考慮時間窗與增加時間窗約束可知，時間窗約束的設(shè)定增加了算法的優(yōu)化難度。具體而言，求解不考慮時間窗約束的配送模型，SCA、ISA和ESCA三種算法所得均值偏差百分比數(shù)值分別為6.82%、5.60%和4.54%；對于增加時間窗約束的配送模型，三種算法所得均值偏差百分比數(shù)值分別為8.85%、6.45%和5.16%。

（3）由算法求解同一模型的結(jié)果對比可知，本文所構(gòu)建的ESCA 算法求解多車場冷鏈物流配送問題在最優(yōu)、均值和最劣三個方面均獲得了最優(yōu)表現(xiàn)。針對不考慮時間窗約束的模型，ESCA算法所得均值百分比偏差為4.54%，相較于SCA 和ISA 算法有2.27%和1.05%的優(yōu)勢；對于增加時間窗約束的模型，ESCA 算法所得均值百分比偏差為5.16%，相較于SCA 和ISA 算法有3.68%和1.29%的優(yōu)勢。

4.2 算法性能驗證

4.2.1 實驗準(zhǔn)備

為進(jìn)一步驗證改進(jìn)措施的有效性和ESCA 算法同其他優(yōu)秀算法相比的有力競爭性，在此開展不同規(guī)模算例的仿真實驗。鑒于當(dāng)前問題尚無標(biāo)準(zhǔn)測試數(shù)據(jù)集，依據(jù)同類研究構(gòu)建不同規(guī)模下多車場冷鏈物流配送問題的算例。

客戶總數(shù)取值范圍為[16，50]且步長為2，中心總數(shù)取3，據(jù)此生成18 個算例。每個算例均可以客戶數(shù)標(biāo)識，例如P-16表示客戶總數(shù)為16的算例，各算例的其他參數(shù)設(shè)置如下：

（1）所有節(jié)點的坐標(biāo)采用隨機方式生成，取值范圍為[0，20]，單位為km，測算選用歐氏距離。

（2）需求量參數(shù)qi采用隨機方式生成{0.2，0.3，0.4}，單位為t。

（3）時間窗參數(shù)Li采用隨機方式生成{20，25，30，35，40，45}，單位為min。

（4）在配送過程中，車輛勻速行駛且車速為40 km/h，車輛額定載荷Q值設(shè)定為0.8 t，運輸車總數(shù)為且均分到每個中心。

（5）運輸車啟動成本參數(shù)cveh為50 元/車，油耗成本參數(shù)cvar為5 元/km，需求量單價參數(shù)cpri為2 000 元/t，需求損耗參數(shù)r為0.005，制冷成本參數(shù)ccool為40 元/h。

4.2.2 改進(jìn)策略分析

為評估改進(jìn)策略的有效性，開展多個版本SCA 算法的對比實驗，包括：（1）SCA；（2）SCA-OBL（SCA with opposition-based learning），即融合反向?qū)W習(xí)初始化方法的SCA 算法；（3）SCA-HUM（SCA with hybrid update mechanism），即融合混合進(jìn)化機制的SCA算法；（4）SCA-NS（SCA with neighbor search），即融合鄰域搜索的SCA算法；（5）ESCA。

依據(jù)實際測試效果及相關(guān)研究，算法參數(shù)設(shè)置如下：種群規(guī)模取20，總迭代次數(shù)取500，ESCA 算法中鄰域搜索方法的循環(huán)次數(shù)取5。對于每個算例，各算法均獨立模擬仿真20 次，表6 梳理歸納了不同SCA 算法仿真結(jié)果。其中，OPT 所在列給出了表示最優(yōu)解數(shù)值，AVG（average）、STD（standard deviation）和RPD 參數(shù)分別標(biāo)識了各算法20 次獨立實驗的均值、標(biāo)準(zhǔn)差和均值的相對偏差百分比。此外，表格的倒數(shù)第2行計算了各算法求解18 個算例的RPD 均值，最后一行定義了當(dāng)前算法求解各算例的排名情況，例如SCA-OBL中的2/4表示該算法在4個算例中RPD值排名第2。

表6 不同SCA算法優(yōu)化結(jié)果Table 6 Simulation results of different SCA-versions

觀察上述實驗結(jié)果可知就RPD 均值而言，ESCA>SCA-HUM>SCA-NS>SCA-OBL>SCA，其平均RPD 值分別為7.84、9.39、9.54、9.78 和12.46。對全部18 個算例，ESCA 算法的平均求解效果均最佳，SCA 算法的平均求解效果均最劣。三種改進(jìn)措施均一定程度上提升了算法的優(yōu)化效果。對于SCA-HUM 算法，其在7 個算例中排名2，在10個算例中排名第3，在1個算例中排名第4；對于SCA-NS 算法，其在7 個算例中排名2，在1 個算例中排名第3，在10個算例中排名第4；對于SCA-OBL算法，其在4個算例中排名2，在7個算例中排名第3，在7 個算例中排名第4。換而言之，混合進(jìn)化機制對SCA算法的性能提升最大，其次是離散鄰域搜索機制，最后反向?qū)W習(xí)機制也在一定程度上提升了SCA算法所得結(jié)果的表現(xiàn)性能。此外，改進(jìn)后的算法所得標(biāo)準(zhǔn)差值均優(yōu)于基本SCA 算法，這表明改進(jìn)措施對于提升尋優(yōu)過程的穩(wěn)定性具有積極意義。

4.2.3 算法對比分析

為進(jìn)一步評估ESCA算法的性能，將其同近年來提出的求解車輛調(diào)度問題的高效算法進(jìn)行對比，具體包括：（1）HGA，混合遺傳算法（hybrid genetic algorithm）[22]；（2）IFWA，改進(jìn)型煙花算法（improved fireworks algorithm）[23]；（3）ISA。

依據(jù)實際測試效果及相關(guān)研究，算法參數(shù)設(shè)置如下：四種算法的種群規(guī)模取20、總迭代次數(shù)取500，ESCA算法中鄰域搜索方法的循環(huán)次數(shù)取5，對比算法的其他參數(shù)維持與參考文獻(xiàn)推薦值相同的取值。對于各測試算例，每個算法均獨立模擬運行20 次，表7 梳理歸納了不同算法的優(yōu)化結(jié)果。其中，OPT所在列給出了表示最優(yōu)解數(shù)值，AVG、STD和RPD參數(shù)分別標(biāo)識了每個算法20次獨立實驗的均值、標(biāo)準(zhǔn)差和均值的相對偏差百分比。此外，表格最后一行定義了當(dāng)前算法在排名情況。此外，表格的倒數(shù)第2 行計算了各算法求解18 個算例的RPD均值，最后一行定義了當(dāng)前算法求解各算例的排名情況。

表7 不同測試算法優(yōu)化結(jié)果Table 7 Simulation results of different test algorithms

由以上測試結(jié)果可知，就RPD 均值而言，ESCA>ISA>IFWA>HGA，其平均RPD值分別為7.84、8.63、8.89和10.06。對全部18 個算例，ESCA 算法的平均求解效果均最佳，HGA算法的平均求解效果均最劣。對于ISA算法，其在12個算例中排名第2，在6個算例中排名第3；對于IFWA算法，其在6個算例中排名第2，在12個算例中排名第3。此外，ESCA 算法所得標(biāo)準(zhǔn)差值均優(yōu)于對比算法，這表明其求解過程更穩(wěn)定。

4.3 總結(jié)與討論

上述仿真實驗證明了本文所構(gòu)建的冷鏈配送模型的有效性，同時驗證了所提出的ESCA算法的有力競爭性。綜合而言，ESCA調(diào)度算法的優(yōu)異性能歸功于以下四點：（1）通過編解碼規(guī)則以及個體評估方法，實現(xiàn)問題模型與決策算法的適配；（2）借助反向?qū)W習(xí)機制創(chuàng)建初始種群，有力提升了初始種群的性能；（3）構(gòu)建了融合雙種群、非線性調(diào)整和隨機解擾動的混合進(jìn)化機制，平衡了搜索過程的全局探索和局部挖掘行為；（4）嵌入了離散鄰域搜索方法，充分發(fā)掘候選解附近的優(yōu)質(zhì)鄰居解，有效避免搜索停滯。

如圖8 所示，展示了不同規(guī)模下ESCA 算法所得RPD值的變動趨勢。據(jù)此可知，RPD值隨著問題規(guī)模的擴大逐步增加，針對客戶總數(shù)為50 的算例，ESCA 算法多次運行結(jié)果的均值誤差百分比達(dá)到12.9%。換而言之，當(dāng)問題規(guī)模較大時，ESCA 算法搜索過程的穩(wěn)定性仍存在提升的空間。同時，ESCA算法基于所有客戶優(yōu)先級序列、并采用啟發(fā)式規(guī)則構(gòu)造路線，算法所需探索的解空間隨著問題規(guī)模的擴大急劇增加，且線路質(zhì)量存在提升空間。

圖8 RPD變動圖Fig.8 RPD under different instance scales

針對以上缺陷，借鑒國內(nèi)外學(xué)者處理大規(guī)模、超大規(guī)模VRP問題方面的學(xué)術(shù)研究[24-25]，后續(xù)求解大規(guī)模算例時可考慮在以下方面進(jìn)一步完善ESCA 算法的運行架構(gòu)：（1）結(jié)合客戶節(jié)點的時空特征，將聚類算法與當(dāng)前尋優(yōu)過程相融合，旨在確保求解精度的前提條件下降低決策難度；（2）組合高效經(jīng)驗式規(guī)則并應(yīng)用于路徑構(gòu)造過程，著力提升線路質(zhì)量；（3）完善路徑構(gòu)造-路徑改善過程，構(gòu)建多階段決策體系，分階段提升所得結(jié)果的性能。

5 結(jié)束語

本文研究了一類多車場冷鏈物流配送問題，綜合考慮運輸網(wǎng)絡(luò)結(jié)構(gòu)、客戶需求、車輛載荷和配送時效等因素，從成本視角建模構(gòu)建了數(shù)學(xué)模型，并提出了ESCA算法。在算法設(shè)計階段，首先創(chuàng)建了融合構(gòu)造式規(guī)則的編碼與解碼方法，并與個體評估函數(shù)相配合，旨在適配問題模型與決策算法。同時，借助反向?qū)W習(xí)機制創(chuàng)建高質(zhì)量的初始種群。此外，構(gòu)建了融合雙種群、非線性調(diào)整和隨機解擾動的混合進(jìn)化機制以平衡算法的全局探索和局部挖掘性能，并通過離散鄰域搜索方法避免搜索停滯。

在實驗部分，通過實例仿真分析展示了模型和算法的有效性。同時，開展了不同規(guī)模算例的仿真實驗，分析了改進(jìn)策略的有效性，并證明了ESCA算法同其他優(yōu)秀算法相比的有力競爭性。

后續(xù)可從客戶滿意、準(zhǔn)時化角度對當(dāng)前模型作進(jìn)一步精準(zhǔn)刻畫，著力貼合實際配送過程。同時，具有動態(tài)因素的多車場冷鏈物流配送問題也具有較高探索價值，諸如考慮時變網(wǎng)絡(luò)、動態(tài)需求等。此外，可考慮將本文提出的ESCA 算法運用于同類問題，例如庫存路徑優(yōu)化、供應(yīng)鏈網(wǎng)絡(luò)優(yōu)化等。