考慮時間滿意度的生鮮前置倉雙目標選址優(yōu)化

0 引言

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

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

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

1 問題描述及模型建立

1.1 問題描述

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

1.2 模型假設(shè)

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

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

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

1.3 符號說明

表1 符號含義說明

1.4 配送成本及時間滿意度

（1）配送成本

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

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

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

1.5 模型構(gòu)建

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

約束條件為：

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

2 算法設(shè)計

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

2.1 K-means聚類算法

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

Step1：首先隨機抽取K個需求點作為最初的聚類中心。

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

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

2.2 改進的遺傳算法

（1）編碼及解碼操作

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

染色體解碼操作如下：

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

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

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

（2）選擇、交叉、變異

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

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

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

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

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

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

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

圖1 交叉操作示例

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

圖2 變異操作示例

（3）進化突變

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

圖3 進化突變示例

（4）精英保留

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

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

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

3 數(shù)值實驗

3.1 實驗設(shè)計

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

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

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

3.2 算例求解

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

圖4 改進遺傳算法的時間滿意度迭代過程

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

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

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

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

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

3.3 結(jié)果分析

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

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

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

表5中CPLEX的求解結(jié)果均為雙目標優(yōu)化的帕累托最優(yōu)解，決策者可根據(jù)自身的偏好，選擇相應(yīng)的最優(yōu)解。本文選取ω=0.4、0.6時，成本為171.8327萬元，時間滿意度為240.2521作為CPLEX的最終求解結(jié)果。在GA的求解結(jié)果中，當ω=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é)果進行對比，除了ω的取值為0.5和0.6的情況下，CPLEX求出的成本不僅比GA小，并且時間滿意度還比GA大，求解結(jié)果完全優(yōu)于GA。在ω=0.5和0.6時，雖然CPLEX所計算出的成本與時間滿意度均高于GA，但仔細比較來看，在成本上CPLEX與GA的成本差異幅度較小，在時間滿意度上CPLEX與GA差異的幅度要高于成本的差異幅度，說明CPLEX求解的將聚類中心作為候選點的選址方案成本效用更高。綜上分析，將聚類中心作為候選點的選址效果要優(yōu)于將需求點作為候選點的選址效果。

4 結(jié)束語

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