基于模擬退火算法的泗陽鮮桃物流配送路徑優化研究

文/王淋 梁子婧 馬衛東

1.引言

“互聯網+”時代背景下，電商行業蓬勃發展，人們對農產品需求日益上升。文中運用模擬退火算法對農產品的物流配送車輛進行路徑優化，減少物流車輛行駛總路程，節省物流運送時間，以達到節能減排、提質增效的目標。

2.模擬退火算法模型

2.1 模擬退火算法介紹

模擬退火法是一種非常典型的概率模擬算法，是基于Monte-Carlo迭代求解策略的一種尋優算法[2]。模擬退火算法通過模擬熱力學當中固體退火過程與一般組合優化問題之間的相似性結合概率突跳性是局部最優解能概率性地跳出并趨于全局最優的模式[3]。

2.2 模擬退火算法模型構建步驟

Step1：初始解采用隨機的方式產生，記為x0，然后令xbest=x0，并計算目標函數值E（0x0）；k=0；t0tmax。

Step2:設置一個初始溫度，記為T0將S記為迭代起點，令迭代次數i=1，如果在這個溫度到達內循環的時候停止，則直接到Step3；如果當這個溫度到達內循環的時候沒有停止，則從目前最優解xbest的鄰域N（xbest）中隨機選擇一個變量作為xnew，除了計算新的目標函數值E（new）外，還要計算目標函數值的增量ΔE=E（xnew）。若計算出來的結果是 ΔE＜0，則 xbest=xnew；否則ΔE＞0；當 exp（-ΔE/tk）＞時，xbest=xnew。

Step3：有 tk+1=d（tk）；k=k+1，如果達到設定的條件則終止計算，如果沒有達到則回到Step2。輸出最優解為xbest；否則，回到step2。

2.3 算法路徑求解步驟：

設解空間為S，S是恰好遍訪每個銷售點一次的所有回路，是（1，…，n）的所有循環排列的集合，S中的成員記為（w1，w2…，wn），并記作 wn+1=w1。初始解可選的范圍為（1，…，n）。此時的目標函數就是訪問完所有銷售點的總路程，也稱為代價函數，需要做的就是求此代價函數的最小值。新的解隨機產生在1和n之間，記為 k和 m，若 k＜m，則將（w1，w2，…，wk，wk+1，…，wm，wn）變為（w1，w2，…，wm，wm-1，…，wk+1，wk，…，wn）；如果是 k＞m，則將（w1，w2，…，wk，wk-1，…，wm，wn）變為（wm，wm-1，…，w1，wm+1，…，wk-1，wn，wn-1，…，wk）。

2.4 算法實現的技術問題

（1）解的形式和鄰域結構

鄰域的構造直接決定解的表現形式，比如：（f x）=x2，0≤x≤100，x∈Z的解可以采用0-1編碼。

（2）狀態轉移概率(接受概率)

狀態轉移概率是指從一個狀態xold(一個可行解)向另一個狀態xnew(另一個可行解)的轉移概率，簡而言之就是接受一個新的解，作為當前的解的概率。狀態轉移概率與當前的溫度參數T有關，概率隨溫度下降而減小；一般采用Metropolis準則：

（3）初始溫度

通過實驗得知，當設置的初始溫度越大，獲得高質量解的概率就會越大，但是計算的時間也會大大增加；當初始溫度過低時，則會使算法過早的結束，落入局部最優陷阱。因此，初始溫的確定應折中考慮優化質量和優化效果。t0=Kδ，K為充分大的數；δ=max{f（j），j∈D}-min{f（j），j∈D}，在實際計算中，可以令K等于整數試驗值。

（4）冷卻進度T(t)

冷卻進度表是指一個高溫的狀態T0冷卻至低溫的狀態整個過程的降溫管理表。需要綜合考慮解的質量和算法運算速度，經典模擬退火算法的降溫方式為快速模擬退火算法的降溫方式為（為保證較大的搜索空間，α一般取接近于1的值）

常用的兩種簡單下降方式：tk+1=αtk，其中0＜α＜1其中K為算法溫度下降的總次數

（5）內循環終止準則。內循環終止條件也被稱為Metropolis抽樣穩定準則，作用是決定在各種溫度下產生的候選解的數目。常用的方法：①固定長度：在每一個溫度選取相同的迭代步數，步數的選取與問題有關，一般情況下采用與鄰域的大小直接相關的準則。②：伴隨著溫度的下降，就要將同一個溫度的迭代步數增加。

（6）外循環終止準則。外循環終止準則就是整個算法的終止條件，常用的包括:①零度法:設置一個終止溫度的閾值，將閾值設為：小正數ε；②循環總數控制法：；③基于不改進規則的控制法:算法搜索到的最優值連續若干步保持不變。根據上述的模擬退火算法模型，將各項指標設置并帶入算法，利用算法來對泗陽鮮桃物流車輛的路徑進行優化[4]。

3 實例分析

3.1 銷售點分布統計。本文主要講述泗陽鮮桃在宿遷市宿城區各個超市站點路徑規劃問題，文章主要選取了宿城區客流量較大的10個超市（圖1、表1所示）來進行舉例分析。

圖1 泗陽鮮桃宿城區10個銷售點分布圖

表1 泗陽鮮桃宿城區10個銷售點地址統計表

3.2 銷售點經緯度

現選取這10個銷售點的經緯度如表2所示，并計算得出這10個地方兩兩之間的距離。這10個銷售點用序號1到10依次表示。[5]。

表2 泗陽鮮桃宿城區10個銷售點經緯度統計表

3.3 銷售點距離計算

除了需要各個銷售點的經緯度之外還需要計算這10銷售點任意兩點之間的距離。設：1銷售點的坐標為(x1，y1)，2銷售點坐標為(x2，y2)。地球半徑為R=6370km，則兩點距離為d=R·arccos[cos（y1）·cos（y2）cos（x1-x2）+sin（y1）·sin（y2）][5]。

表3 10個銷售點任意兩點之間的距離

此時解空間S里的n=10，集合里面所有成員，解空間S就物流車輛走遍每個銷售點的所有路徑。基于模擬退火算法得出泗陽鮮桃物流運輸車輛優化前后對比[6]。（如圖2、表4所示）

表4 優化前后路徑信息

圖2 泗陽鮮桃配送路徑優化前后對比

通過表4可以輕松得知泗陽鮮桃優化前的配送總路程為213km，優化后為175km。優化后比優化前節省路程38km,運送泗陽鮮桃的物流車輛能更快完成運送任務的同時還節省了物流運輸成本[7]。

4.結論與展望

文章通過對泗陽鮮桃從產地向各銷售點之間配送的數據查找和收集，了解到在配送上面產生了較大物流運輸成本。首先對模擬退火算法進行了步驟分析進而利用圖表分析法清楚地表達出算法優化前后的對比分析。最后利用了模擬退火算法來對泗陽鮮桃的配送路徑進行優化，選擇最優、最短、最省的路徑來對泗陽鮮桃進行配送。

引用出處

[1]張欣,梁子婧,蔡志群,等."互聯網+"背景下農村快遞發展的影響因素與對策研究--以蘇北地區為例[J].2021(2017-16):137-138.

[2]Kwanho Kim,Hyunjin Kim,Sang-Kuk Kim,Jae-Yoon Jung.I-RM:Anintelligentrisk managementframework for context-aware ubiquitouscoldchainlogistics[J].ExpertSystems With Application,2016,46(46).

[3]Giosa.New assignment algorithms for the multi-depot vehicle routing problem[J].Journal of the Operational Research Society2017

[4]姚新,陳國良.模擬退火算法及其應用 [J].計算機研究與發展,1990(7):1-6.

[5]楊真真,方秀男.模擬退火算法及實例應用 [J].中國科技信息,2021(15):2.李偉，楊延梅，劉漢英，等.城市末端物流配送路徑優化研究[J].鐵道貨運，2019，37(03)：5-10.

[6]裴小兵,賈定芳.基于模擬退火算法的城市物流多目標配送車輛路徑優化研究[J].數學的實踐與認識,2016,46(2):105-113.

[7]楊志清.城市快遞配送條件下的多目標車輛路徑優化研究[D].哈爾濱工業大學，2015.