基于模擬退火算法的電商物流配送問題研究

王旭穎，楊金云，陳 哲，倪秋銘，劉朱丹

（徐州工程學院，江蘇 徐州 221008）

0 引言

徐州電商的發展，離不開供應商和消費群體。由于集聚效應，徐州新沂市墨河皮草電商產業園同時聚集了皮草企業、制造商與物流企業，擁有自己的產品展銷區、倉儲物流區、配套服務區、生產廠房區、創業孵化區。影響電商企業成本的重要因素從產業鏈中間環節，變得更加傾向于物流運輸成本。因此，為了更快地將產品送達消費群體，墨河皮草產業園迫切需要改進產品運往皮草店鋪和商城路徑規劃的問題。物流運輸時間越長，需要支付運輸人員的工資和產品所發生的損耗就越多，對電商園區的利潤影響就越大，制訂合理的運輸方案有利于提高企業的成本控制能力。

1 電商產業園物流配送問題的描述

路徑規劃（TSP）問題的本質是從某點出發，依據某些準則，尋找到達終點的最優化路徑。常用的算法有Dijkstra 算法、蟻群算法、遺傳算法等。Dijkstra 算法只對當前做出最優選擇，不能回溯，因此容易出現局部最優解。蟻群算法、遺傳算法都具有全局優化的能力，但蟻群算法容易陷入局部最優，遺傳算法的缺點是運算效率不高。模擬退火算法，也存在收斂速度慢、隨機性大等缺點，但通過多次尋優，調整參數的方法，可以減少隨機性對結果的影響。本文求解從徐州墨河皮草產業園出發，經過徐州都市圈內部分皮草商鋪，最終回到徐州電商產業園的路徑優化問題，通過運用百度拾取坐標系統，獲得產業園和商鋪點的經緯度信息，用A 標識皮草產業園，用B，C，…，U 標識各皮草銷售點，通過軟件繪制分布圖如圖1 所示。

2 模擬退火算法的物流配送路徑優化

2.1 模擬退火算法的原理

模擬退火算法（SA）是一種適用于大規模組合優化問題的有效近似算法，來源于對固體退火過程的模擬。統計力學表明，在給定初始溫度的條件下，通過將溫度緩慢降低，微觀粒子會在各個溫度達到熱平衡狀態，當物體冷卻到常溫時達到基態，內能達到最小。模擬固體退火的過程，給定一個初始溫度和初始解，隨著溫度的下降，每一個溫度狀態下，通過解的變換生成新的解。如果解的目標函數值小于前一個解，接受當前解；否則，以概率接受新解。最終的解是迭代尋優的結果。模擬退火算法以概率突跳性，能夠跳出局部最優陷阱，找到全局最優解。模擬退火算法依據Metropolis 接收準則接受新解，而不是使用完全確定的規則。它構成了模擬退火算法退火過程的基礎。當固體從狀態i 經過降溫變化到狀態j，它所具有的能量從E（i）變化到E（j）。顯然，如果E（j）＜E（i），接受新的狀態j。否則，依據概率P 接受新解。

其中，K 是物理學波爾茲曼常數，T 是固體的溫度。

這種概率，在路徑規劃的問題中，就是當新解的目標函數值小于原來的解的函數值，新解仍被接受的概率。以x 表示溫度T 下的一個解，通過退火，可以生成一個新解x′。那么，接收x′的概率為：

2.2 模擬退火算法模型的建立

2.2.1 目標函數

首先，規定解空間。對銷售點B，C，U 重新進行編號（2，3，…，21），A 點為產業園，既是起點也是終點，將它進行兩次編號，記為1 號和22 號，以便于程序計算。問題轉化為求解從1 出發，走遍所有中間點，到達22 的一個最短路徑。本文通過運用百度拾取坐標系統，獲得產業園和商鋪點的經緯度信息。由于，本文選取的點的范圍在徐州都市圈，兩點之間的曲線距離可以近似看作直線距離。用k1和k2分別表示經度、緯度和千米的換算系數，將經緯度轉換為千米。通過改進坐標距離公式計算距離：

計算得到皮草產業園和所有銷售點中，任意兩點間的距離，構成一個對稱矩陣D=（dij）22×22。規定z1，z2，…，z22中，z2，z3，…z21，是由2～21 隨機打亂得到的一組數，則dzizi+1表示所有可能路徑中，第i 個和第i＋1 個經過的點間的距離。目標函數為運輸經過所有目標的路徑長度最小：

2.2.2 模擬退火算法實現過程

Step 1 初始化

通過MATLAB 隨機模擬數給定初始路徑，計算得到初始路徑長度。設定初始溫度T（0）=1。

Step 2 產生新解

運用變換法，任選序號a，b（a＜b），交換a 和b 之間的順序，得到新的路徑：

Step 3 判定標準

新路徑與原路徑長度的差可以表示為：

當路徑差Δf<0 時，用新路徑代替原路徑。否則，以概率exp（-Δf/T）接受新的路徑。

Step 4 重復步驟2 和步驟3，進行迭代。

Step 5 結束條件

選用降溫系數α，令T←αT，得到新的溫度。當溫度降至終止溫度，算法結束，輸出當前狀態。

3 MATLAB 模擬退火算法求解

本文以徐州都市圈為例，運用模擬退火算法，對最優路徑進行選擇，用MATLAB 軟件計算結果。本文研究的是同一起訖點的電商物流配送路徑優化問題，實際上，就是從徐州墨河皮草產業園出發經過徐州都市圈各省市部分皮草商鋪和商城，最終回到產業園的問題。本文首先通過百度坐標拾取系統，拾取其中20 個皮草商鋪和商城的坐標，并對其進行編號，如表1 所示。

表1 徐州都市圈個皮草經營點經緯度坐標

由于通過坐標拾取系統得到的地點坐標的單位是經緯度，與實際生活使用的距離單位不符合，不便于求解分析。本文通過MATLAB 計算得到范圍內近似經度換算系數k1=92.164 4 千米／經度，緯度換算系數k2=111.177 5 千米／緯度。于是根據改進的距離公式，可以得到各鄰接點的距離矩陣D=（dij）22×22：

模擬退火算法的初始溫度參數不妨假設為1，溫度變化系數α 一般取0.95～0.99 之間，本文取變化系數為0.99。根據若干次對初始溫度和終止溫度的調整，最終得到初始溫度為2 200，終止溫度為9.908 2×10-4。對徐州都市圈的實例進行1 455 次M ATLAB 仿真計算。最終計算得到路徑長度最小值為913.822 1千米，最終最短路徑為A-N-M-O-K-L-J-R-G-I-D-F-C-B-QP-U-E-H-T-S-A。在MATLAB 運行計算結果過程中，迭代具體變化過程見圖2。

通過MATLAB 運行仿真計算得出最優路徑坐標，如圖3所示。

圖2 迭代變化過程圖

結合模擬退火算法結果和圖中坐標，可以得出從徐州新沂市墨河皮草產業園出發的車輛配送貨物的順序：新沂市墨河皮草產業園—墨尚皮草—海州海寧皮草特賣—貴夫人—優尚皮草行—泗陽海寧皮草—泗洪海寧皮草城—名媛皮草—睢寧海寧皮草—邳州海寧皮革城—國亞皮革店—潤龍裘皮—云龍海寧皮草—徐州海寧皮草城—埇橋海寧皮草—華東濉溪皮革—名牌之家經典皮草行—夢源皮革—東方皮草—三星皮草行—麗豪皮草行—新沂市墨河皮草產業園。

4 結語

結合模擬退火算法，本文對徐州都市圈內的電商物流配送路徑進行了優化研究。模擬退火算法在處理組合優化問題時，展現全局尋優的特點。本文通過多次仿真，調整參數，在一定程度上克服了算法本身的隨機性缺陷。

圖3 最優路徑圖

實際生活中，電商物流配送問題在目標函數選擇和算法改進方面仍有改善空間。本文將模擬退火算法應用于電商物流路徑選擇，旨在為電商物流路徑規劃方法的創新提供參考。