末端配送選址及路線優化案例研究

鄧納納 孫曉燕 陳慧敏

(1.廣西財經學院，廣西 南寧530003，2.北京經濟管理職業學院 ，北京 100102)

0 引言

互聯網電商平臺的發展，深刻影響了人們的購物消費行為和傳統零售業的發展[1]。隨著中國直播電商模式的興起，以及健康生活理念的提倡，越來越多的生鮮農產品銷售加入了電商行業，據數據顯示，2019年中國生鮮市場交易規模約2.04萬億元，生鮮電商行業交易額為1 620億元[2]，且數據還在迅猛增長，這就對物流行業帶來了巨大的考驗，因生鮮農產品存在時效性和易腐性的特性，電商物流除了加快冷鏈物流發展外，需要關注物流末端“最后一公里”配送。目前在電商物流環節中，末端“最后一公里配送” 存在配送成本過高且實效性差的問題，一定程度制約電商的收益和最終用戶的用戶體驗。

本文以廣西財經學院相思湖校區M直播平臺校園末端配送為例，提出采用精確重心法，構建配送成本最小的數學模型，選出配送中心，然后模擬商旅問題(Salesman Traveling Problem，STP)，利用免疫算法的特點對其配送路徑進行優化，以此求解合理具體合理的校園配送路線，為電商物流末端配送提供參考。

1 末端配送選址

1.1 選址模型構建

廣西財經學院相思湖校區M直播平臺在相思湖校區有A、B、C、D、E、F、G共7個主要目標市場，如圖1所示。假定M平臺配送中心的經緯度坐標為(x0，y0)，7個配送點A、B、C、D、E、F、G的經緯度坐標可以分別表示為(x1，y1)(x2，y2)(x3，y3)(x4，y4)(x5，y5)(x6，y6)(x7，y7)。

圖1 配送中心與各配送點的實際位置分布

利用精確重心選址方法確定配送中心的地址。精確重心法模型的具體構建如下：

di=R×arccos[sin(p0)sin(pi)+cos(p0)

cos(pi)cos(w0-wi)]

(1)

其中，w0，p0，wi，pi為配送中心和各配送點的經緯度角度轉化對應的弧度，轉化的具體表達式為w0=x0π/180，p0=y0π/180，wi=xiπ/180，pi=yiπ/180，總的費用表達式為：

cos(pi)cos(w0-wi)]

(2)

第二步：根據總費用最小原則，通過極值求解，解出配送中心(x0,y0)的表達式為：

(3)

簡化后得配送中心O的坐標點為：

(4)

式(4)被稱為重心公式。

第三步：算法驗證迭代，具體計算步驟為：

(1)初始時，假設配送中心坐標為(x0，y0)。根據公式(2)計算出A、B、C、D、F、G這7個配送點與配送中心(x0，y0)的總費用S0。

(3)計算A、B、C、D、E、F、G 7個配送點與(x(1)，y(1))相應的總費用S1。

(4)檢驗。將迭代后更新的配送中心與前一初始配送中心的總費用進行對比，即比較S1和S0，如果S1< S0，則返回步驟(2)繼續計算配送中心的改善地點(x(2)，y(2))，如此反復計算下去，直到第k次迭代后得到Sk+1≥ Sk，此時得最優解(x(k)，y(k))，即最優的配送中心的位置坐標是(x(k)，y(k))。

1.2 選址模型求解

1.2.1 模型假設

(1)假設供應商到配送中心點費用忽略不計；

(2)假設配送中心配送的貨物為單一品，以件量為計算，重量忽略不計；

(3)假設配送中心的貨量，能夠滿足其服務范圍內所有需求點；

(4)假設采用電車騎行配送，配送過程中配送人員的平均行駛速度保持一致；

(5)將需求點內學生公寓樓每個宿舍作為一個需求衡量基點；

(6)假設單位配送成本為1元/千米；

(7)配送點簡化為一個點，便于算出具體信息。

1.2.2 數據來源

(1)根據百度地圖可以測得每個配送點的經緯度坐標，并通過wi=xiπ/180、pi=yiπ/180計算其相應弧度。

(2)需求量ni依據M平臺2020年11月銷售量統計，通過整理得到求解模型所需的數據如表1所示。

表1 M平臺在廣西財經學院各配送點的實際數據

1.2.3 計算

(w*k-1-wi)]。

令k=1，得7個配送點A、B、C、D、E、F、G到配送中心的初始距離di,0(i=1,2,…,7)分別為268，186，166，134，15，216，275。

如圖1所示，根據計算結果，將配送中心(圖1中的五角星)和各配送點(圖2中方塊)坐標的實際經緯度坐標畫到坐標系中，可以得到配送點與配送中心的分布情況，如圖2所示。圖中7個配送點對應的序號分別為：2→A，3→B，4→C，5→D，6→E，7→F，8→G以及配送中心1→O。

2 末端配送路徑優化

2.1 路徑優化模型

末端配送網點路線的優化問題可以轉化成商旅問題(Salesman Traveling Problem，STP)進行求解。當已知各配送點的實際坐標位置時，假設配送人員從配送中心出發，向配送點進行配送，最后返回配送中心。為了節省時間，配送路線不重復，即每個配送點只配送一次，不回頭配送。這樣末端配送網點路線的優化問題可以歸結為：求M平臺配送中心O向7個需求點A、B、C、D、E、F、G送貨時，如何安排配送路線，讓整個配送路線距離最短。距離矩陣D=(dij)9×9，其中dij表示i，j兩點的距離，i,j=1，2，…，8，9(1)，這里D為實對稱矩陣。則問題是求一個從點1出發，走遍所有中間所有點，到達9(回到起點1)的一個最短路徑。

2.2 免疫優化算法原理

免疫算法是模擬生物免疫系統抗原抗體而生成的一種新型智能計算方法[3]。免疫算法保留了生物免疫系統超強學習力、記憶力和自適應的優點，同時也彌補了遺傳算法容易過度早熟收斂的不足。免疫系統由抗原、記憶細胞、抗體等組成。其運算原理是模擬了生物免疫系統中，如細胞通過分裂產生大量的抗體來抵抗各種抗原，借助自身優異的學習能力、識別能力、記憶能力以及具有保持群體多樣性的特點，能夠有效的辨別外界的有害信息，從而保證整個系統的安全穩定。免疫算法是一種對多峰值函數進行多峰值檢索，經過多次迭代，尋找全局最優的算法[4]。優化算法[5]能夠有效克服尋求最優解的過程中出現的問題，從而獲得全局最優解。

2.3 算法流程圖

算法的流程圖如圖2所示。

圖2 免疫優化算法基本流程

2.4 算法步驟

免疫算法的具體實現步驟如下：

第一步：初始化免疫個體維數為配送點個數N(將配送中心O點也當成一個配送點)，將免疫種群個體數參數設計為NP=200，最大免疫代數為G=10(一般G取100～500，但考慮本研究問題所選取的坐標數據比較小)。為了便于觀察，最大免疫代數相應取小，克隆個數為Ncl=10，導入數據，計算任意兩配送點的距離矩陣。

第二步：在免疫算法中隨機產生初始種群，然后計算相應個體的親和度(即路徑距離)，按親和度進行升序排列。

第三步：在取親和度前，對NP/2個個體進行克隆操作，并對每個源個體產生的克隆個體進行隨機交換兩個配送點的變異操作；然后計算親和度情況，進行克隆抑制操作是為了保留親和度最高的個體，從中得到新的免疫種群。

第四步：隨機生成NP/2個個體的新種群，并計算個體親和度；此時免疫種群和隨機種群合并，按親和度進行排序，下一步免疫迭代。

第五步：判斷是否滿足終止條件。如若滿足，結束整個搜索過程，輸出優化值；如若不滿足，則繼續進行迭代優化。

2.5 計算結果

初始種群的一個隨機數，其具體路徑為：1—>7—>3—>6—>2—>5—>8—>4—>1，軌跡如圖3所示。計算得到初始配送路徑總距離為2.2603千米。

圖3 初始隨機路線

采用免疫優化算法進行優化后，得到最短配送路徑距離為1.1616千米，對應的最優路線是：1—>8—>7—>6—>5—>4—>2—>3—>1，其的路線軌跡如圖4所示。親和度進化曲線如圖5所示。

圖4 優化后的路徑軌跡圖

圖5 親和度進化曲線

從親和度進化曲線可以看出，優化前后路徑距離已經得到明顯改進，且迭代速度非?？?，在第2代以后路徑距離已經維持不變了，可以認為此時達到了最優解，最優路徑距離為1.1616千米，比初始路徑距離減少了48.6%。由此可知免疫算法可以優化末端配送路徑，為現實問題的應用進行客觀的指導。

3 結語

物流配送作為電子商務線上銷售后的最終環節，它面向著消費者，配送服務質量影響著消費者的購物體驗，間接影響著消費者對網絡購物的體驗[6]。提高末端配送水平既可以提升客戶滿意度，也可以降低企業運營成本。數據表明，廣西財經學院相思湖校區M直播平臺，在校園末端配送中有效進行末端配送選址和優化配送路徑后，能有效節省配送成本和提高配送效率，為電商物流末端配送研究提供借鑒參考。