基于非等覆蓋半徑的前置倉選址

趙琨　趙剛　趙永健　梁晨

摘要：為解決城市物流配送中心出現的配送效率低的問題，研究配送中心前置倉選址問題。基于非等覆蓋半徑思想，結合前置倉選址特性，建立以企業總成本最低和客戶滿意度最高為目標的前置倉選址優化模型。結合第二代非支配排序遺傳算法（nondominated sorting genetic algorithm Ⅱ， NSGAⅡ）與差分進化（differential evolution， DE）算法對模型進行求解。利用Python進行算例分析，得出企業總成本與客戶滿意度之間的Pareto解集，給出Pareto解集在二維空間的分布。該研究可為不同類型企業提出多種前置倉選址方案。

關鍵詞：? 前置倉; 非等覆蓋半徑; 多目標遺傳算法; 客戶滿意度

中圖分類號：? U113;F272文獻標志碼：? A

Location selection of front warehouses based on

unequal coverage radius

Abstract： In order to solve the problem of low distribution efficiency in urban logistics distribution centers， the location issue of distribution centers’ front warehouses is studied. Based on the idea of the unequal coverage radius， combined with the characteristics of the front warehouse location， a front warehouse location selection optimization model with the goals to minimize the total cost of an enterprise and maximize the customer satisfaction is established. The model is solved combined with the nondominated sorting genetic algorithm Ⅱ （NSGAⅡ） and the differential evolution （DE） algorithm. Through the example analysis by Python， the Pareto solution set between the enterprise total cost and the customer satisfaction is obtained， and the distribution of the Pareto solution set in the twodimension space is given. The research can propose a variety of front warehouse location selection solutions for different types of enterprises.

Key words： front warehouse; unequal coverage radius; multiobjective genetic algorithm; customer satisfaction

引言

21世紀以來，中國電子商務產業迅速興起，市場規模逐年擴大[1]，2014年全國線上零售額僅27 898億元，到2019年已增長至106 324億元[2]。城市交通壓力的不斷增加，以及新制造模式和新零售模式的不斷發展，對城市快速物流配送提出了新的要求，前置倉就在這種情況下應運而生。前置倉是一種倉配模式，中央大倉只需對門店供貨，就能夠覆蓋“最后一公里”，具有距離客戶近、輻射范圍有限、選址相對靈活、初期資金投入高等特性。前置倉可以滿足客戶的及時化、分散化、定制化需求[3]，因此探討和研究前置倉的選址問題具有重要的理論與實踐意義。

目前前置倉可分為兩大類：一類是以大型電商企業為主體，采用“總倉+分倉”二級倉儲形式布局，此類前置倉倉儲規模較大，輻射半徑可達600 km左右;另一類是基于O2O服務模式的電商，采用“城市配送中心+前置倉”的模式，將前置倉布局在市中心，此類前置倉的規模較小，倉儲面積為80～100 m2，輻射半徑一般在3～5 km。相較于傳統的選址問題，前置倉選址一般選在離消費者較近但人流量很少的地方，比如某個辦公樓或者社區內的小型倉庫等;由于前置倉僅提供配送服務而不對外營業，所以前置倉的選址對地理位置的要求很低，選址時只需要做到覆蓋住戶數量大、環境有利于貨物儲存即可。

國內外學者對物流設施選址問題進行了深入研究，已經取得了諸多成果。周愉峰等[4]建立了一個適用于震后救援初期的應急設施選址分配模型，并設計了一種混合遺傳算法進行求解。賴志柱等[5]建立了多目標應急物流中心選址的確定型模型和魯棒優化模型。馬云峰等[6]建立了考慮時間滿意度的選址模型，并提出拉格朗日松弛求解算法。肖建華等[7]提出非等覆蓋半徑選址概念，設計一種基于自適應遺傳算法的動態膜算法求解模型。陳誠等[8]建立了基于分級顧客滿意度的選址路徑優化模型。武明帥等[9]建立了以配送中心總成本最低為目標函數的選址模型，應用布谷鳥算法進行求解。李茂林[10]提出一種基于非線性調節因子的猴群優化算法對選址模型進行優化。倪衛紅等[11]以新冠肺炎為背景，采用聚類重心法對應急物流配送中心選址問題進行研究。

最大覆蓋選址問題（maximal covering location problem，MCLP）已被證明是最有用的選址模型之一。傳統的最大覆蓋選址模型更多從企業的角度建立模型，并且存在各設施點的最大覆蓋半徑難以確定的問題，同時在傳統的最大覆蓋選址模型中，所有設施點的覆蓋半徑均相同，較少考慮需求點的不同參數對設施點覆蓋半徑的影響。前置倉設置在城市中，需要根據實際情況對各個前置倉的覆蓋范圍進行靈活調整，因此對選址模型中設施點覆蓋半徑的確定有著較高的要求。本文引入非等覆蓋半徑的思想，結合前置倉的特性，構建基于非等覆蓋半徑的前置倉選址模型。結合第二代非支配排序遺傳算法（nondominated sorting genetic algorithm Ⅱ， NSGAⅡ）與差分進化（differential evolution， DE）算法對模型進行求解。本文將該組合算法記為DENSGAⅡ。通過算例驗證模型和算法的有效性和可行性。

1基于非等覆蓋半徑的前置倉選址模型構建該模型主要包括各需求點的最大選址半徑計算、前置倉候選區域確定、前置倉數量確定和前置倉選址優化模型構建四部分。

1.1需求點的最大選址半徑計算

候選區域的人口狀況、經濟狀況等直接影響前置倉的選址。因此，選擇候選區域人口狀況作為關鍵指標來確定各需求點的最大選址半徑。

候選區域人口狀況主要從人口密度、人口年齡結構和人口性別結構方面來描述。

人口密度。前置倉的選址不僅需要考慮人口規模，還需要結合土地面積綜合分析人口在一定區域的分布。本文將人口密度分為五級，由一級到五級人口密度遞減。用ki表示需求點i的人口密度等級，ki∈{1，2，3，4，5}，ki越小，該需求點的人口密度就越大。

人口年齡結構。生鮮電商主要消費群體的年齡為20～35歲，年齡稍大的人群主要通過菜市場、線下實體水果店等滿足需求。用αi表示需求點i的20～35歲人口數占總人口數的比例。

人口性別結構。一般認為女性較男性有更明顯的消費動機，但事實并非如此。統計數據顯示，2019年男性使用生鮮電商產品的比例為60.3%，略高于女性。用ρi表示需求點i的女性數量占比。

在客戶實際下單過程中，客戶可能會選擇自提或進店消費（例如叮咚買菜、盒馬鮮生等），此時訂單不需要配送，但并不會影響以配送業務為主的前置倉選址。自提或進店消費占比λi=（qi-q′i）/qi，這里qi為需求點i的需求量，q′為需求點i的配送量。

在實際配送過程中，需求點的最大配送服務半徑與配送運輸速度相關，而配送運輸速度又與路況系數有關。本文引入需求影響因子μi，則需求點i的最大配送服務半徑可表示為 式中：wi和li分別為需求點i的人口年齡結構和人口性別結構影響因子，且wi+li=1;ri為路況系數，ri ∈[0，1]，路況越好，前置倉服務半徑越大;vi為平均運輸速度。

1.2前置倉候選區域確定

利用求解出的需求點最大配送服務半徑和平面圓交集覆蓋理論，確定前置倉候選區域。Ci表示以需求點i為圓心，以βi為半徑的圓;（xi，yi）為需求點i的位置;d′ij為需求點i到需求點j的距離。

每個需求點所對應的配送中心必須位于該需求點的最大配送服務半徑內，才能滿足需求點的需求。對于2個需求點，基于非等覆蓋半徑思想，對前置倉候選區域分3種情況討論，見表1。前置倉候選區域示意圖見圖1。

在實際選址中，假設有n個需求點，每個需求點的最大配送服務半徑和位置坐標已知，則n個需求點對應的Ci是否相交的判斷可以轉化為求解以下不等式組是否有解：

若不等式組有解，則可在交集區域建立前置倉，否則需建立多個前置倉來滿足需求。

1.3前置倉候選區域中的前置倉數量確定

前置倉選址具有靈活性，可以在已知的候選區域充分利用閑置、偏僻的物業、地下室等資源，因此可先對候選區域內可用作前置倉的位置進行粗選，再利用數據包絡分析法、層次分析法等定量方法進行細選，按比例選出一定的前置倉候選點。一般在每個候選區域內，選擇2～3個候選點即可。

1.4前置倉選址優化模型構建

前置倉選址優化問題屬于一個NP難問題。模型假設如下：僅在前置倉候選區域內進行選址;為前置倉配送貨物的配送中心位置確定，且貨量充足;已知每個需求點的位置和需求，并在一段時間內需求無波動;每個需求點有且僅有一個前置倉為其提供配送服務;已知各候選前置倉的建設費用和運營管理費用;忽略競爭對前置倉選址的影響;忽略貨物在運輸過程中的損耗;忽略天氣因素的影響。

符號和變量說明：I為需求點集合（也為顧客集合），i∈I;J為前置倉集合，j∈J;S（tij）為顧客i對前置倉j的配送時長滿意度函數;p為要設置的前置倉個數;qi為需求點i的需求量;mj為前置倉j的最大貨物儲存量;Qj為前置倉j的最大處理能力;Aj為前置倉j的建設成本;Bj為前置倉j單位產品的運營成本;dij為需求點i到前置倉j的距離;dj為配送中心到前置倉j的距離;cij為從前置倉j到需求點i的單位運費;cj為從配送中心到前置倉j的單位運費;xij為01變量，xij=1表示前置倉j可以覆蓋需求點i，否則xij=0;yj為01變量，yj=1表示在候選點j設置前置倉，否則yj=0。

通過上述對前置倉選址特點的分析，從企業角度和客戶角度出發，確立兩個目標：企業總成本最低和客戶滿意度最高。由于前置倉選址對時間的敏感度較高，故需要選擇一種能準確反映客戶對時間偏好的滿意度函數。根據前期調研可知：當配送時間超出客戶可接受范圍時，客戶將感到十分不滿意，嚴重降低客戶對平臺的忠誠度;當配送時間在客戶可接受范圍內時，客戶滿意度也會隨配送時間增加而降低。因此，本文引入路況系數，選擇凹凸時間等待成本函數來擬合客戶滿意度：式中：[T1，T2]為客戶可接受的配送時間窗;η為時間敏感系數;貨物從前置倉j配送到顧客i的時刻tij=dij/（rivi）。

綜上，綜合企業總成本最低和客戶滿意度最高的前置倉選址模型如下：（1）

（2）（3）

（4）

（5）

（6）

xij∈{0，1}，yj∈{0，1}（7）式（1）和（2）為2個目標函數：式（1）表示企業總成本最低，該成本包括前置倉建設成本、從配送中心到前置倉的配送成本、前置倉運營成本和從前置倉到客戶的配送成本;式（2）表示客戶滿意度最高。式（3）～（7）為約束條件：式（3）表示顧客的總需求量不超過前置倉的最大處理能力;式（4）表示設置的前置倉數量小于候選前置倉數量p;式（5）限制每個需求點只能被一個前置倉覆蓋;式（6）表明前置倉與需求點之間的關系，需求點只能在前置倉被選中時才被該前置倉覆蓋;式（7）是對決策變量的01約束。

2模型求解算法

前置倉選址優化問題多采用啟發式算法求解。NSGAⅡ算法在運行后期易出現收斂速度慢的情況，故利用DE算法良好的全局搜索能力進行彌補;NSGAⅡ算法的快速非支配排序和種群多樣性保持策略可以很好地彌補DE算法容易丟失Pareto解的問題：故將兩種算法組合，命名為DENSGAⅡ算法[12]。算法基本流程見圖2。

步驟1將種群個體進行非支配排序分層，見圖3。搜索非支配個體集的具體步驟如下：①選定個體i;②對于種群中其他所有的個體j，按照Pareto最優比較個體i與j之間的支配與非支配關系;③若不存在任何一個個體j優于i，則標記個體i為非支配個體;④遍歷所有個體，直到找出所有的非支配個體。

通過上述步驟得到的非支配個體集是種群的第一級非支配層;忽略這些已標記的非支配個體，再遵循步驟①～④，就會得到第二級非支配層;以此類推，直到整個種群被分層。

步驟2同層個體擁擠度比較，見圖4。

設每個個體的擁擠度為0;針對每個目標，對種群進行非支配排序，令邊界的兩個個體擁擠度為無窮;對其他的個體i進行擁擠度的計算，計算式為2j=1Fj，i+1-Fj，i-1，其中Fj，i+1和Fj，i-1分別表示個體i+1和i-1的第j個目標值。

對種群個體進行非支配排序分層和同層擁擠度計算后，每個個體都會得到兩個屬性：所屬的非支配層和擁擠度。在個體i與j的比較中，個體i只要符合下面的一個條件，則個體i獲勝：（1）個體i所處的非支配層優于個體j所處的非支配層;（2）i、j處于相同層級，但個體i比個體j的擁擠度大。第一個條件確保被選擇的個體屬于較優的非劣等級。對于處于同一非劣等級而不分勝負的兩個個體，第二個條件確保選擇位于較不擁擠區域的個體（有較大擁擠度的個體）。勝出的個體進入下一步操作。

步驟3進行DE算法的變異、交叉、選擇操作確定子代個體，具體步驟如下：

①對候選前置倉采用01編碼方式編碼，生成初始種群。

②采用隨機引導變異方法對種群進行變異操作：式中：下標i表示第i個個體;下標G表示第G代種群;下標r1，r2和r3分別表示第G代的第r1、r2和r3個個體;xi，G是目標向量;vi，G是變異向量;Fi為縮放因子，用于對差分向量進行縮放，控制搜索步長。

③交叉操作。將生成的變異向量vi，G與目標向量xi，G進行交叉，得出實驗向量ui，G。本文采用的二項式交叉方式如下：

xij，G，其他式中：下標“ij，G”表示第G代種群中第i個個體的第j個基因，j=1，2，…，D;rij表示第i個個體的第j個基因對應的[0，1]內的隨機數;jrand為[1，D]內的一個隨機整數;Cr為交叉概率，用來控制算法的收斂速度，Cr∈[0，1]。

④選擇操作。采用高強度貪婪選擇策略，將目標向量與實驗向量進行逐一比較，勝出者為本代子代個體，方法如下：其他步驟4精英選擇策略。在NSGAⅡ算法中，將父代與子代中所有個體混合后進行非支配排序，可較好地避免父代中優秀個體的流失[13]。精英選擇策略如圖5所示：先將第t代迭代后產生的新種群Qt與父代種群Pt合并成種群Rt，種群規模為2N;然后對種群Rt進行非支配排序，產生一系列非支配解集Zi并進行擁擠度計算。因為子代和父代個體都包含在種群Rt中，經過非支配排序后得到的非支配解集Z1在所有非支配解集中是最優的，所以先將Z1放入新的父代種群Pt+1中。如果Pt+1的種群規模小于N，則向Pt+1中填充下一級非支配解集;若添加Z3時Pt+1的規模超出N，則對Z3中的個體進行擁擠度比較，選擇擁擠度大的個體放入Pt+1中，直到Pt+1的規模達到N。

3數值實驗

本節利用Python編程求解模型并分析求解結果。所有的工作均在一臺計算機上完成。根據本節數值實驗結果，確定算法的最大迭代次數、交叉概率、變異概率等參數。

3.1算法對比

從多個角度對比DENSGAⅡ與NSGAⅡ，測試DENSGAⅡ的穩定性以及優勢。參數設置：最大迭代次數為5 000，交叉概率為0.8，變異概率為0.1。不同參數下的算法對比見表2。

從算法收斂性能看，DENSGAⅡ比傳統的NSGAⅡ具有更好的收斂性能。從收斂次數看，NSGAⅡ的平均收斂次數是DENSGAⅡ的2倍左右，且求解問題的復雜度越高，DENSGAⅡ的收斂性能就越優。程序迭代動畫顯示，DENSGAⅡ在運行初期便可以較快地收斂到Pareto前沿面，而NSGAⅡ在運行后期也會存在Pareto前沿面刻畫不完全的問題。

從算法求解時間看，DENSGAⅡ與NSGAⅡ的求解時間相差不大。然而，DENSGAⅡ的收斂性優于NSGAⅡ的，因此當需要達到同樣的求解效果時，DENSGAⅡ的求解速度更快。當問題的復雜度足夠高時，不宜采用最大迭代次數為算法結束條件，此種情況下更能凸顯DENSGAⅡ的求解優勢。

從得出的Pareto前沿解看，DENSGAⅡ得出的Pareto前沿解遠多于NSGAⅡ的，較多的Pareto前沿解可以更好地描述多目標解空間的復雜度，更能進行精準的方案選擇。

3.2最大迭代次數確定

算法的最大迭代次數主要與問題規模有關，本節只討論在相同數量級情況下，候選前置倉個數與需求點個數對算法運行速度及結果的影響。

設種群內染色體的數目為100，交叉概率為0.8，變異概率為0.1。不同參數條件下DENSGAⅡ的收斂效果見表3。

綜合算法求解時間、Pareto解個數以及問題規模，得出算法最大迭代次數設置范圍為500～3 000，具體取值可根據問題規模靈活調整。

3.3交叉、變異概率確定

將交叉概率取不同值，將變異概率固定為0.10，計算候選前置倉個數為40、需求點個數為500時的Pareto解個數和算法求解時間。對表4結果進行分析，確定本算法交叉概率為0.90。

然后，將變異概率取不同值，將交叉概率固定為0.90，計算候選前置倉個數為40、需求點個數為500時的Pareto解個數和算法求解時間。對表5結果進行分析，確定本算法變異概率為0.10。

4算例

以某生鮮移動電商在太原市小店區進行前置倉選址為例。對該區80個需求點進行調研得到，該區平均運輸速度為30 km/h，需求點的人口年齡結構和人口性別結構影響因子為[0，1]之間的隨機數，自提或進店消費占比為0.15。需求點位置、需求量、客戶可接受時間窗、路況系數、需求影響因子和人口密度等級等部分數據見表6。利用非等覆蓋半徑選址模型確定候選前置倉位置，并通過調研得出候選前置倉建設成本和運營成本，部分數據見表7。

利用DENSGAⅡ算法，使用Python 3.0編程，在Intel（R） Core（TM） i510210U處理器和16 GB內存的硬件環境下運行，其中變異概率為0.10，交叉概率為0.90，種群密度為50，最大迭代次數為10 000，運行結果見圖6。

考慮到實際選址中過低的客戶滿意度并無意義，從44個Pareto解集中選擇客戶滿意度高于90%的20個選址方案作為候選方案，各方案前置倉選擇、企業總成本及客戶滿意度見表8。

企業可以根據需要選擇不同的前置倉選址方案：（1）若企業資金雄厚且側重于提高客戶滿意度，則可選擇方案15～20，這些方案的客戶滿意度高達99%。（2）若企業側重于節省成本，則可選擇方案1～6，這些方案不僅可使客戶滿意度達到90%以上，而且其選址成本也偏低。（3）若企業同時考慮客戶滿意度和企業總成本，則可選擇方案7～14。

5結論

前置倉作為物流“最后一公里”問題的新的解決方案，其選址是否科學以及布局是否合理關系到整個供應鏈體系的成本和效率。多方面因素的考量、準確簡單模型的建立、快速精確的求解算法、多樣化方案選擇對豐富前置倉選址模型以及指導企業合理實踐具有重要意義。本文針對已有選址模型的不足，引入非等覆蓋半徑的思想，結合選址區域內人口密度、人口年齡結構、人口性別結構等特性，構建基于非等覆蓋半徑的前置倉選址模型。結合第二代非支配排序遺傳算法（NSGAⅡ）與差分進化（DE）算法對模型進行求解。以某生鮮移動電商在太原市小店區的前置倉選址為例，得出多個前置倉選址方案，驗證了模型和算法的合理性。

參考文獻：

[1]何振綺， 陳宏志. 電子商務時代的企業國際供應鏈管理模式研究[J]. 物流技術， 2007， 26（8）： 144146.

[2]巴旭成. 我國生鮮電商新零售模式的研究[J]. 環渤海經濟瞭望， 2020（3）： 2526.

[3]衡歡樂. 基于生鮮前置倉的選址研究[D]. 北京： 北京交通大學， 2019.

[4]周愉峰， 陳娜， 李志， 等. 考慮設施中斷情景的震后救援初期應急物流網絡優化設計[J]. 運籌與管理， 2020， 29（6）： 107112.

[5]賴志柱， 王錚， 戈冬梅， 等. 多目標應急物流中心選址的魯棒優化模型[J]. 運籌與管理， 2020， 29（5）： 7483.

[6]馬云峰， 楊超， 張敏， 等. 基于時間滿意的最大覆蓋選址問題[J]. 中國管理科學， 2006， 14（2）： 4551.

[7]肖建華， 王飛， 白煥新， 等. 基于非等覆蓋半徑的生鮮農產品配送中心選址[J]. 系統工程學報， 2015， 30（3）： 406416. DOI： 10.13383/j.cnki.jse.2015.03.011.

[8]陳誠， 檀曉琳， 鄧穎. 基于分級顧客滿意度的水果電商物流配送網絡選址路徑問題[J]. 華東交通大學學報， 2019， 36（4）： 8894. DOI： 10.16749/j.cnki.jecjtu.2019.04.012.

[9]武明帥， 王巍， 孫理越. 基于布谷鳥搜索算法的物流配送中心選址[J]. 經濟師， 2021（2）： 252253， 255.

[10]李茂林. 基于改進猴群優化算法的物流配送中心選址研究[J]. 太原學院學報（自然科學版）， 2020， 38（2）： 4450. DOI： 10.14152/j.cnki.2096191X.2020.02.0010.

[11]倪衛紅， 陳太. 基于聚類重心法的應急物流配送中心選址[J]. 南京工業大學學報（自然科學版）， 2021， 43（2）： 255263. DOI： 10.3969/j.issn.16717627.2021.02.017.

[12]李巖， 張光武. 混合NSGAⅡ和DE的優化算法及應用[J]. 哈爾濱理工大學學報， 2018， 23（5）： 7579. DOI： 10.15938/j.jhust.2018.05.013.

[13]許玉龍， 潘旭， 王忠義， 等. 利用帕累托非支配關系實現高效三目標差分進化的方法[J]. 計算機應用研究， 2019， 36（3）： 817823， 828. DOI： 10.19734/j.issn.10013695.2017.09.0909.

（編輯趙勉）

收稿日期： 20210321修回日期： 20210821

基金項目： 北京市社會科學基金（17GLB020）

作者簡介： 趙琨（1978—），女，遼寧本溪人，副教授，碩導，博士，研究方向為物流工程、最優化方法、數據挖掘，（Email）piaopiao_zk@163.com