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

文/王淋 梁子婧 馬衛東

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）。此時的目標函數就是訪問完所有銷售點的總路程，也稱為代價函數，需要做的就是求此代價函數的最小值。……