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

（徐州工程學(xué)院，江蘇 徐州 221008）

0 引言

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

1 電商產(chǎn)業(yè)園物流配送問題的描述

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

2 模擬退火算法的物流配送路徑優(yōu)化

2.1 模擬退火算法的原理

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

其中，K 是物理學(xué)波爾茲曼常數(shù)，T 是固體的溫度。

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

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

2.2.1 目標(biāo)函數(shù)

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

計(jì)算得到皮草產(chǎn)業(yè)園和所有銷售點(diǎn)中，任意兩點(diǎn)間的距離，構(gòu)成一個(gè)對(duì)稱矩陣D=（dij）22×22。規(guī)定z1，z2，…，z22中，z2，z3，…z21，是由2～21 隨機(jī)打亂得到的一組數(shù)，則dzizi+1表示所有可能路徑中，第i 個(gè)和第i＋1 個(gè)經(jīng)過的點(diǎn)間的距離。目標(biāo)函數(shù)為運(yùn)輸經(jīng)過所有目標(biāo)的路徑長(zhǎng)度最?。?/p>

2.2.2 模擬退火算法實(shí)現(xiàn)過程

Step 1 初始化

通過MATLAB 隨機(jī)模擬數(shù)給定初始路徑，計(jì)算得到初始路徑長(zhǎng)度。設(shè)定初始溫度T（0）=1。

Step 2 產(chǎn)生新解

運(yùn)用變換法，任選序號(hào)a，b（a＜b），交換a 和b 之間的順序，得到新的路徑：

Step 3 判定標(biāo)準(zhǔn)

新路徑與原路徑長(zhǎng)度的差可以表示為：

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

Step 4 重復(fù)步驟2 和步驟3，進(jìn)行迭代。

Step 5 結(jié)束條件

選用降溫系數(shù)α，令T←αT，得到新的溫度。當(dāng)溫度降至終止溫度，算法結(jié)束，輸出當(dāng)前狀態(tài)。

3 MATLAB 模擬退火算法求解

本文以徐州都市圈為例，運(yùn)用模擬退火算法，對(duì)最優(yōu)路徑進(jìn)行選擇，用MATLAB 軟件計(jì)算結(jié)果。本文研究的是同一起訖點(diǎn)的電商物流配送路徑優(yōu)化問題，實(shí)際上，就是從徐州墨河皮草產(chǎn)業(yè)園出發(fā)經(jīng)過徐州都市圈各省市部分皮草商鋪和商城，最終回到產(chǎn)業(yè)園的問題。本文首先通過百度坐標(biāo)拾取系統(tǒng)，拾取其中20 個(gè)皮草商鋪和商城的坐標(biāo)，并對(duì)其進(jìn)行編號(hào)，如表1 所示。

表1 徐州都市圈個(gè)皮草經(jīng)營(yíng)點(diǎn)經(jīng)緯度坐標(biāo)

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

模擬退火算法的初始溫度參數(shù)不妨假設(shè)為1，溫度變化系數(shù)α 一般取0.95～0.99 之間，本文取變化系數(shù)為0.99。根據(jù)若干次對(duì)初始溫度和終止溫度的調(diào)整，最終得到初始溫度為2 200，終止溫度為9.908 2×10-4。對(duì)徐州都市圈的實(shí)例進(jìn)行1 455 次M ATLAB 仿真計(jì)算。最終計(jì)算得到路徑長(zhǎng)度最小值為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 運(yùn)行計(jì)算結(jié)果過程中，迭代具體變化過程見圖2。

通過MATLAB 運(yùn)行仿真計(jì)算得出最優(yōu)路徑坐標(biāo)，如圖3所示。

圖2 迭代變化過程圖

結(jié)合模擬退火算法結(jié)果和圖中坐標(biāo)，可以得出從徐州新沂市墨河皮草產(chǎn)業(yè)園出發(fā)的車輛配送貨物的順序：新沂市墨河皮草產(chǎn)業(yè)園—墨尚皮草—海州海寧皮草特賣—貴夫人—優(yōu)尚皮草行—泗陽海寧皮草—泗洪海寧皮草城—名媛皮草—睢寧海寧皮草—邳州海寧皮革城—國(guó)亞皮革店—潤(rùn)龍裘皮—云龍海寧皮草—徐州海寧皮草城—埇橋海寧皮草—華東濉溪皮革—名牌之家經(jīng)典皮草行—夢(mèng)源皮革—東方皮草—三星皮草行—麗豪皮草行—新沂市墨河皮草產(chǎn)業(yè)園。

4 結(jié)語

結(jié)合模擬退火算法，本文對(duì)徐州都市圈內(nèi)的電商物流配送路徑進(jìn)行了優(yōu)化研究。模擬退火算法在處理組合優(yōu)化問題時(shí)，展現(xiàn)全局尋優(yōu)的特點(diǎn)。本文通過多次仿真，調(diào)整參數(shù)，在一定程度上克服了算法本身的隨機(jī)性缺陷。

圖3 最優(yōu)路徑圖

實(shí)際生活中，電商物流配送問題在目標(biāo)函數(shù)選擇和算法改進(jìn)方面仍有改善空間。本文將模擬退火算法應(yīng)用于電商物流路徑選擇，旨在為電商物流路徑規(guī)劃方法的創(chuàng)新提供參考。