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

文/王淋 梁子婧 馬衛(wèi)東

1.引言

“互聯(lián)網(wǎng)+”時代背景下，電商行業(yè)蓬勃發(fā)展，人們對農(nóng)產(chǎn)品需求日益上升。文中運(yùn)用模擬退火算法對農(nóng)產(chǎn)品的物流配送車輛進(jìn)行路徑優(yōu)化，減少物流車輛行駛總路程，節(jié)省物流運(yùn)送時間，以達(dá)到節(jié)能減排、提質(zhì)增效的目標(biāo)。

2.模擬退火算法模型

2.1 模擬退火算法介紹

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

2.2 模擬退火算法模型構(gòu)建步驟

Step1：初始解采用隨機(jī)的方式產(chǎn)生，記為x0，然后令xbest=x0，并計(jì)算目標(biāo)函數(shù)值E（0x0）；k=0；t0tmax。

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

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

2.3 算法路徑求解步驟：

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

2.4 算法實(shí)現(xiàn)的技術(shù)問題

（1）解的形式和鄰域結(jié)構(gòu)

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

（2）狀態(tài)轉(zhuǎn)移概率(接受概率)

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

（3）初始溫度

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

（4）冷卻進(jìn)度T(t)

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

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

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

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

3 實(shí)例分析

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

圖1 泗陽鮮桃宿城區(qū)10個銷售點(diǎn)分布圖

表1 泗陽鮮桃宿城區(qū)10個銷售點(diǎn)地址統(tǒng)計(jì)表

3.2 銷售點(diǎn)經(jīng)緯度

現(xiàn)選取這10個銷售點(diǎn)的經(jīng)緯度如表2所示，并計(jì)算得出這10個地方兩兩之間的距離。這10個銷售點(diǎn)用序號1到10依次表示。[5]。

表2 泗陽鮮桃宿城區(qū)10個銷售點(diǎn)經(jīng)緯度統(tǒng)計(jì)表

3.3 銷售點(diǎn)距離計(jì)算

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

表3 10個銷售點(diǎn)任意兩點(diǎn)之間的距離

此時解空間S里的n=10，集合里面所有成員，解空間S就物流車輛走遍每個銷售點(diǎn)的所有路徑?；谀M退火算法得出泗陽鮮桃物流運(yùn)輸車輛優(yōu)化前后對比[6]。（如圖2、表4所示）

表4 優(yōu)化前后路徑信息

圖2 泗陽鮮桃配送路徑優(yōu)化前后對比

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

4.結(jié)論與展望

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

引用出處

[1]張欣,梁子婧,蔡志群,等."互聯(lián)網(wǎng)+"背景下農(nóng)村快遞發(fā)展的影響因素與對策研究--以蘇北地區(qū)為例[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]姚新,陳國良.模擬退火算法及其應(yīng)用 [J].計(jì)算機(jī)研究與發(fā)展,1990(7):1-6.

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

[6]裴小兵,賈定芳.基于模擬退火算法的城市物流多目標(biāo)配送車輛路徑優(yōu)化研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2016,46(2):105-113.

[7]楊志清.城市快遞配送條件下的多目標(biāo)車輛路徑優(yōu)化研究[D].哈爾濱工業(yè)大學(xué)，2015.