0 引言

隨著新零售時代的到來，傳統(tǒng)生鮮電商的單一線上模式已經(jīng)難以滿足顧客即時配送和生鮮品質(zhì)等全方位的需求，于是生鮮電商企業(yè)開始由單一線上模式轉(zhuǎn)化為線上平臺+線下體驗(yàn)的新模式來滿足顧客多樣化的需求，提出了一種新的倉配模式——前置倉。前置倉是在生鮮貨物送往目的地前的最后一個倉庫和站點(diǎn)，也是最靠近消費(fèi)者的一個節(jié)點(diǎn)，為了滿足分鐘級的配送，前置倉的服務(wù)半徑通常約為3～5公里，采用這種模式能夠大幅度縮短生鮮貨物的運(yùn)輸時間，盡可能保證商品的新鮮度，提升商品的品質(zhì)[1-3]。

前置倉屬于末端物流配送中心，與傳統(tǒng)物流配送中心不同的是，前置倉對時效性要求更高，目前對于前置倉的研究主要聚焦在前置倉模式分析層面上，在具體實(shí)施層面上關(guān)于前置倉選址問題的研究較少[4]。近年來關(guān)于物流配送中心選址問題主要從單目標(biāo)、多目標(biāo)及求解算法等方面進(jìn)行了研究。肖建華等引入了非等覆蓋半徑的思想建立了生鮮農(nóng)產(chǎn)品配送中心選址模型并提出了一種基于自適應(yīng)遺傳算法的動態(tài)膜進(jìn)化算法[5]，魏潔等建立了最小距離約束的生鮮農(nóng)產(chǎn)品多配送中心連續(xù)選址模型并設(shè)計了由模糊C均值聚類算法與改進(jìn)模擬退火算法嵌套而成的FCM-ISA算法[6]，Dou等針對冷藏食品易腐爛的特點(diǎn)引入新鮮度和時間窗等約束條件建立了冷鏈物流配送中心選址問題的數(shù)學(xué)優(yōu)化模型，并提出了一種免疫狼群混合算法[7]；隨著研究復(fù)雜度的提升，有學(xué)者將單目標(biāo)選址問題延伸至多目標(biāo)選址問題，Zhang等從顧客對生鮮商品需求不確定性的角度建立了生鮮配送中心選址模型并提出了一種改進(jìn)的果蠅優(yōu)化算法[8]，宋英華等綜合考慮了災(zāi)后應(yīng)急物資動態(tài)需求和實(shí)際道路狀況建立了多周期多目標(biāo)應(yīng)急物資配送中心快速選址模型并采用耦合Dijkstra算法的分層序列法進(jìn)行求解[9]，黃露等針對延誤情境下配送中心選址問題提出了雙層規(guī)劃模型，并利用層次遺傳算法進(jìn)行求解[10]。從對配送中心選址的研究成果來看，目前關(guān)于選址的模型多為考慮成本的單目標(biāo)選址模型，且從顧客時間需求的角度來考慮的配送中心選址研究還較少。

基于時效性對前置倉的重要程度，本文將時間滿意度引入前置倉選址問題中，建立了配送成本最小和時間滿意度最大的雙目標(biāo)優(yōu)化模型，在傳統(tǒng)的遺傳算法基礎(chǔ)上基于進(jìn)化逆轉(zhuǎn)的思想提出了進(jìn)化突變操作并引入了精英保留策略[11]，用于提高遺傳算法的尋優(yōu)能力與收斂速度，最后通過算例對模型和算法進(jìn)行驗(yàn)證。

1 問題描述及模型建立

1.1 問題描述

本文研究的生鮮前置倉選址問題可描述為，在由前置倉、顧客需求點(diǎn)構(gòu)成的二級物流網(wǎng)絡(luò)中，已知顧客需求點(diǎn)的位置與需求量，在滿足兩個目標(biāo)函數(shù)總配送成本最小和時間滿意度最大并達(dá)到最優(yōu)的情況下，從候選點(diǎn)中選出P個前置倉建設(shè)點(diǎn)。

1.2 模型假設(shè)

（1）每個需求點(diǎn)的顧客對時間滿意感知程度是一樣的，時間滿意度只與配送時間有關(guān)且時間滿意度函數(shù)是呈嶺形分布，不考慮因配送時間所造成的生鮮貨物的損耗。

（2）每個需求點(diǎn)的位置和需求量已知，并且需求量保持不變，前置倉配送可以直接送達(dá)每個需求點(diǎn)，由于前置倉的建設(shè)成本為固定成本，所以不必算入成本目標(biāo)函數(shù)中。

（3）配送成本與運(yùn)輸距離成正比，所有生鮮貨物的單位距離運(yùn)輸成本相同，且擁有足夠的運(yùn)力進(jìn)行運(yùn)輸，不考慮競爭因素。

1.3 符號說明

表1 符號含義說明

1.4 配送成本及時間滿意度

（1）配送成本

配送成本是由從前置倉運(yùn)送生鮮貨物至顧客需求點(diǎn)所產(chǎn)生的物流運(yùn)輸費(fèi)用，配送成本與生鮮貨物運(yùn)輸量、運(yùn)輸距離、單位運(yùn)輸費(fèi)用有關(guān)。由于本文給出的前置倉與需求點(diǎn)的距離為兩點(diǎn)之間的歐氏距離，所以乘以城市道路非直線系數(shù)來轉(zhuǎn)換為貨物的運(yùn)輸路程。配送成本計算方式如公式（1）所示。

（2）時間滿意度函數(shù)

時間滿意度函數(shù)為生鮮貨物從前置倉運(yùn)送至顧客需求點(diǎn)所花費(fèi)時間的滿意程度，當(dāng)所花費(fèi)的配送時間越長，滿意度就越低。配送時間與配送距離和配送速度有關(guān)，配送時間的計算如公式（2）所示，本文選取的是余弦分布時間滿意度函數(shù)[12]，函數(shù)式如公式（3）所示。

1.5 模型構(gòu)建

本文建立了配送成本最小和時間滿意度最大的雙目標(biāo)優(yōu)化模型：

約束條件為：

目標(biāo)函數(shù)式（4）表示最小化總配送成本，目標(biāo)函數(shù)式（5）表示最大化總的顧客需求點(diǎn)的時間滿意度，目標(biāo)函數(shù)式（6）表示使用極大極小歸一化與線性加權(quán)處理將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，約束式（7）表示每一個需求點(diǎn)最多只能被一個前置倉服務(wù)，約束式（8）表示擬建設(shè)的前置倉數(shù)量為P個，約束式（9）表示需求點(diǎn)不能被沒有選中的前置倉候選點(diǎn)服務(wù)，約束式（10）表示需求點(diǎn)的滿意度水平達(dá)到了α?xí)r才能被覆蓋，約束式（11）表示每個前置倉所覆蓋的需求點(diǎn)的需求量之和必須達(dá)到總需求量的β倍，約束式（12）表示總覆蓋需求必須達(dá)到θ以上，約束式（13）表示對決策變量Xj、Yij的0～1約束。

2 算法設(shè)計

針對前置倉選址問題，本文給出了兩種前置倉候選點(diǎn)的選取方式并設(shè)計出相應(yīng)的求解方法。第一種為將需求點(diǎn)通過聚類算法進(jìn)行聚類，將聚類后得到的聚類中心作為候選點(diǎn)，運(yùn)用CPLEX求解器求解整數(shù)規(guī)劃模型。第二種為將顧客需求點(diǎn)本身作為候選點(diǎn)，由于CPLEX不適合求解大規(guī)模問題，所以本文設(shè)計了改進(jìn)的遺傳算法對其進(jìn)行求解。

2.1 K-means聚類算法

利用K-means聚類算法將分散的需求點(diǎn)聚為K簇，將每一簇的聚類中心作為前置倉的候選點(diǎn)，通過MATLAB調(diào)用CPLEX對所建立的模型進(jìn)行求解。聚類操作可以簡述為三步：

Step1：首先隨機(jī)抽取K個需求點(diǎn)作為最初的聚類中心。

Step2：將每個需求點(diǎn)分配到離他們最近的聚類中心，生成K簇。

Step3：對于每個簇，計算出所有被分到該簇的需求點(diǎn)的平均值作為新的聚類中心，重復(fù)步驟2和步驟3，當(dāng)聚類中心的位置不再發(fā)生改變時，迭代停止，聚類完成。

2.2 改進(jìn)的遺傳算法

（1）編碼及解碼操作

編碼方式采用的是實(shí)數(shù)編碼，染色體的長度為待建前置倉數(shù)量加1，每一段染色體對應(yīng)著前置倉候選點(diǎn)的編號，0代表所有未能被待建前置倉所服務(wù)的需求點(diǎn)集合，例如{9,12,47,68,78,31,64,0}為一個完整的染色體。

染色體解碼操作如下：

Step1：判斷需求點(diǎn)是否能滿足當(dāng)前染色體下任意前置倉候選點(diǎn)的最低時間滿意度約束。

Step2：若無法滿足，則將該需求點(diǎn)歸為未能被待建前置倉所服務(wù)的需求點(diǎn)集合。若能夠滿足，則查找出大于最低時間滿意度的前置倉候選點(diǎn)集合，按照距離遠(yuǎn)近的劃分原則，將需求點(diǎn)分給集合中距離需求點(diǎn)最近的前置倉候選點(diǎn)。

Step3：重復(fù)上述步驟直至所有染色體完成解碼。

（2）選擇、交叉、變異

選擇算子操作，通過適應(yīng)度函數(shù)可以評判各個個體的優(yōu)劣程度，本文的選擇算子通過輪盤賭的方式來進(jìn)行操作，個體的適應(yīng)度越大，該個體的基因遺傳到子代的概率也就越大。

交叉是產(chǎn)生新個體基因的主要來源，交叉的操作如下[13]：

Step1：在任意兩個基因之間隨機(jī)選擇兩個切點(diǎn)，被選中的兩個基因稱之為父代1和父代2。

Step2：從父代1中將兩個切點(diǎn)之間的基因片段復(fù)制給子代1。

Step3：從父代2中排除父代1遺傳給子代1的基因，以此避免重復(fù)，之后從父代2中按照基因出現(xiàn)的順序，逐個復(fù)制基因給子代1，直到子代1的所有位置被填滿。

Step4：將上述操作的父代1和父代2進(jìn)行角色互換，得到子代2。

交叉操作示例如圖1所示。

圖1 交叉操作示例

變異操作有利于維持種群的多樣性，避免算法過早陷入局部最優(yōu)，變異操作為隨機(jī)選擇兩個基本位，按照變異概率將兩個基本位上的基因值替換為個體中從未出現(xiàn)過的基因值。變異操作示例如圖2所示。

圖2 變異操作示例

（3）進(jìn)化突變

基于進(jìn)化逆轉(zhuǎn)的思想，本文提出了進(jìn)化突變操作，進(jìn)化突變是指隨機(jī)替換基因個體上的片段，新替換的基因片段為替換之前個體中所沒有出現(xiàn)過的基因，進(jìn)化體現(xiàn)在，當(dāng)進(jìn)化突變過后的基因個體適應(yīng)度變高，則進(jìn)行突變，否則不進(jìn)行突變。進(jìn)化突變示例如圖3所示。

圖3 進(jìn)化突變示例

（4）精英保留

采用精英保留可以確保優(yōu)良的個體能夠保留得以延續(xù)至下一代，保證子代不會比父代差，精英保留的操作步驟如下：

Step1：將經(jīng)過選擇、交叉、變異、進(jìn)化突變操作后形成的子代與父代放在一起，按照適應(yīng)度高低進(jìn)行排序，遵循從適應(yīng)度高到低的選擇原則，選擇出一定比例適應(yīng)度高的基因。

Step2：將選擇出來的適應(yīng)度高的基因等量替換步驟1中所形成的子代中適應(yīng)度低的子代，此時重新形成的子代為真正的子代，精英保留操作完成。

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計

本文通過算例來證明模型和改進(jìn)的遺傳算法的有效性以及候選點(diǎn)選取方式的優(yōu)劣性，算例的需求點(diǎn)坐標(biāo)來自于文獻(xiàn)[14]，每個需求點(diǎn)的年度需求量的數(shù)值為隨機(jī)生成，取值范圍為0.2千噸到5千噸，需求量數(shù)據(jù)如表2所示。本文是在Windows10系統(tǒng)下進(jìn)行的求解操作，模型采用CPLEX 12.80來進(jìn)行求解，算法使用的是MATLAB 2018a軟件來進(jìn)行編寫。遺傳算法的種群規(guī)模為300，迭代次數(shù)為500，交叉概率為0.9，變異概率為0.1，精英保留比例為0.3。其他相關(guān)參數(shù)如表3所示。

表2 各需求點(diǎn)的需求量數(shù)據(jù)

表3 其他相關(guān)參數(shù)

3.2 算例求解

采用傳統(tǒng)的遺傳算法與本文改進(jìn)之后的遺傳算法分別求解單目標(biāo)下的時間滿意度的最大值，兩種算法的求解次數(shù)均為10次，取10次中的最優(yōu)結(jié)果作為最終時間滿意度的最大值，兩種算法的優(yōu)化過程如圖4所示，通過對比可以發(fā)現(xiàn)本文改進(jìn)后的遺傳算法的尋優(yōu)能力與收斂速度均優(yōu)于傳統(tǒng)的遺傳算法。

圖4 改進(jìn)遺傳算法的時間滿意度迭代過程

通過K-means聚類算法將130個需求點(diǎn)聚成11類，得到11個聚類中心，聚類結(jié)果如圖5所示。

圖5 需求點(diǎn)聚類結(jié)果

運(yùn)用CPLEX對模型進(jìn)行求解，最終從11個聚類中心中選出聚類中心1、3、4、5、6、8、9作為前置倉建設(shè)點(diǎn)，最終前置倉覆蓋結(jié)果如圖6所示。運(yùn)用改進(jìn)之后的遺傳算法對模型進(jìn)行求解，得到將需求點(diǎn)17、26、47、61、72、102、117作為前置倉建設(shè)點(diǎn)，最終前置倉覆蓋結(jié)果如圖7所示。

圖6 運(yùn)用CPLEX模型求解前置倉覆蓋結(jié)果

圖7 運(yùn)用改進(jìn)后的遺傳算法模型求解前置倉覆蓋結(jié)果

3.3 結(jié)果分析

根據(jù)上述所給參數(shù)，分別計算出CPLEX軟件與改進(jìn)之后的遺傳算法（下文簡稱“GA”）在兩個目標(biāo)函數(shù)各自為單目標(biāo)函數(shù)情況下的極值，求解結(jié)果如表4所示。

表4 單目標(biāo)求解結(jié)果

將計算出的數(shù)值帶入公式（6）中，ω的取值為0.1～0.9，取值間隔為0.1，CPLEX與GA的計算結(jié)果見表5所示。

表5中CPLEX的求解結(jié)果均為雙目標(biāo)優(yōu)化的帕累托最優(yōu)解，決策者可根據(jù)自身的偏好，選擇相應(yīng)的最優(yōu)解。本文選取ω=0.4、0.6時，成本為171.8327萬元，時間滿意度為240.2521作為CPLEX的最終求解結(jié)果。在GA的求解結(jié)果中，當(dāng)ω=0.5時的結(jié)果要優(yōu)于ω=0.4、0.6、0.7時的求解結(jié)果，所以ω=0.4、0.6、0.7時的解為劣解，應(yīng)予以淘汰，本文選取ω=0.5時，成本為167.9798萬元，時間滿意度為227.2361作為GA的最終求解結(jié)果。

表5 不同ω取值下CPLEX與GA的計算結(jié)果

在ω相同的條件下，將CPLEX與GA計算出的成本與時間滿意度的結(jié)果進(jìn)行對比，除了ω的取值為0.5和0.6的情況下，CPLEX求出的成本不僅比GA小，并且時間滿意度還比GA大，求解結(jié)果完全優(yōu)于GA。在ω=0.5和0.6時，雖然CPLEX所計算出的成本與時間滿意度均高于GA，但仔細(xì)比較來看，在成本上CPLEX與GA的成本差異幅度較小，在時間滿意度上CPLEX與GA差異的幅度要高于成本的差異幅度，說明CPLEX求解的將聚類中心作為候選點(diǎn)的選址方案成本效用更高。綜上分析，將聚類中心作為候選點(diǎn)的選址效果要優(yōu)于將需求點(diǎn)作為候選點(diǎn)的選址效果。

4 結(jié)束語

本文針對前置倉選址問題，在分析現(xiàn)有物流配送中心選址模型的特點(diǎn)和不足的基礎(chǔ)上，從滿足顧客時間需求的角度來考慮前置倉選址問題，引入了時間滿意度這一概念，建立了以總配送成本最小，總顧客需求點(diǎn)的時間滿意度最大的雙目標(biāo)選址模型。在傳統(tǒng)的遺傳算法之上引入了精英保留策略并基于進(jìn)化逆轉(zhuǎn)的思想提出了進(jìn)化突變操作，并用算法對模型進(jìn)行了求解，從理論和具體實(shí)施兩個層面分析了所建模型及算法的有效性。通過對比兩種候選點(diǎn)選取方式的最終求解結(jié)果，發(fā)現(xiàn)以聚類中心作為候選點(diǎn)的方式要優(yōu)于將需求點(diǎn)本身作為候選點(diǎn)的方式?，F(xiàn)有關(guān)于物流配送中心選址和前置倉選址研究較少考慮時間滿意度因素和不同候選點(diǎn)選取方式的優(yōu)劣性，本文在一定程度上豐富了相關(guān)的設(shè)施選址理論及應(yīng)用，為前置倉選址布局提供了決策參考。