模擬退火算法在物流線路選擇方面的研究

楊飛

摘要：隨著電子商務(wù)的不斷發(fā)展，互聯(lián)網(wǎng)訂單數(shù)量的不斷增加，線下物流配送的壓力越來越大。如何設(shè)計一個效果優(yōu)良，可靠性強的物流線路選擇方法越來越成為人們關(guān)注的熱點。文章采用模擬退火算法對多節(jié)點物流配送路線最短選擇問題進行了研究，建立了適用于物流配送路線最短問題的模擬退火算法方法。對于物流配送最短路線的優(yōu)化計算提供了算法參考。對于其他行業(yè)關(guān)于多節(jié)點遍歷路線最短問題同樣具有參考意義。

關(guān)鍵詞：模擬退火算法；物流配送；線路選擇

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1009-3044（2019）04-0270-02

隨著電子商務(wù)的不斷發(fā)展，互聯(lián)網(wǎng)訂單數(shù)量的不斷增加，線下物流配送的壓力越來越大。在此背景下，現(xiàn)有諸多電商和物流相關(guān)企業(yè)都在進行物流配送線路選擇的研究和應(yīng)用，如阿里巴巴，京東等。物流配送研究是為了解決物流線路規(guī)劃的問題而存在的，其是一個典型的旅行商問題[1]（Travelling Salesman Problem，TSP），它是一個組合優(yōu)化問題。關(guān)于物流線路選擇問題，可以將每個城市看成一個AOV有向圖的節(jié)點，節(jié)點與節(jié)點之間有的單向連接，有的雙向連接，也有的沒有連接。如圖1所示。

從圖1中選擇任意一個節(jié)點作為開始節(jié)點，找出一條路徑，路徑包含剩余所有節(jié)點，并只包含一次，最后返回到開始節(jié)點，要求這條路徑所花費的代價最少（距離最短），這就是TSP問題。物流線路選擇作為一個典型的TSP問題，當城市個數(shù)增加時，它可能的配送路線數(shù)量是成指數(shù)型增長的，是一個NP[2]難題。眾所周知，NP難問題是很難精確的求出其最優(yōu)解，因此，對于物流線路選擇問題求出近似解是具有意義的。

1 相關(guān)工作

目前，在電商行業(yè)和物流行業(yè)飛速發(fā)展的背景下，關(guān)于物流配送的路徑規(guī)劃方面的研究越來越多。劉婷婷等人根據(jù)物流配送最短路線規(guī)劃的現(xiàn)狀，利用最小生成樹法對現(xiàn)有問題進行分析，通過資料整合、建立實例模型、使用Kruskal算法建立模型、比較權(quán)值大小并用canvas畫布顯示最終路徑圖形等過程，得出物流配送網(wǎng)絡(luò)的最佳路徑，最后用Java實現(xiàn)整個模型，得出最短路徑和最低時耗方案[3]。張倩等人針對 如何更好地確保電商平臺生鮮食品冷鏈物流運作成本和運作效率的問題，提出了一種改進的蟻群算法，優(yōu)化了生鮮電商冷鏈物流的配送路徑，并通過實例仿真驗證了優(yōu)化方法的可行性[4]。王勇等人采用遺傳算法對多節(jié)點物流配送路線最短選擇問題進行了研究，建立了適用于物流配送路線最短問題的遺傳算法方法[5]。

此外，由于物流配送的路徑規(guī)劃本質(zhì)就是TSP問題的研究，所以關(guān)于TSP問題的研究工作是在研究物流配送的路徑規(guī)劃問題時不可避免的。李陽等人為優(yōu)化TSP，結(jié)合禁忌搜索算法（TS）和模擬退火算法（SA）的思想設(shè)計了混合退火算法（TSA）。針對模擬退火算法搜索效果不穩(wěn)定等問題，在初始階段TSA多次禁忌搜索并篩選初始解，確保算法穩(wěn)定地收斂到全局最優(yōu)值，在求解部分設(shè)計了快速退火算法，使其快速退火并收斂。與其他算法相比，TSA求解精度高，求解效果穩(wěn)定魯棒性強，并且求解時間短[6]。Christine等人提出了一種進化分裂與侵占（EDAC）方法，用于替代遺傳算法在硬組合搜索中的應(yīng)用，該方法可以利用對子問題的良好解決方案的知識來改進問題本身的解決方案。文中使用遺傳算法來探索問題細分的空間，而不是解決方案本身的空間，并給出了應(yīng)用于幾何TSP的該方法的一些初步結(jié)果[7]。

2 模擬退火算法原理

SA起源于物理學(xué)中固體退火原理，固體退火過程包括加溫過程、等溫過程和冷卻過程。固體加溫過程中，固體內(nèi)部粒子隨著溫度的上升變成了無序狀，導(dǎo)致內(nèi)能增大。固體等溫過程中，固體內(nèi)部粒子漸趨有序，致使在每個溫度都達到平衡態(tài)。固體冷卻過程中，固體內(nèi)部粒子隨著冷卻達到基態(tài)，內(nèi)能減小為最小。模擬退火法的一般原理如下：

1）初始溫度為[T0]，及初始點[x]，計算該點的函數(shù)值[f（x）]；

2）隨機產(chǎn)生擾動[?x]，得出新點[x'=x+?x]，計算新點函數(shù)值[f（x'）]，和函數(shù)值差[?f=fx'=f（x）]；

3）假如[?f≤0]，則接受新點，當做下一次模擬的初始點；

4）假如[?f>0]，則計算新點接受概率：[p?f=exp -?fK?T]，產(chǎn)生[0，1]區(qū)間上均勻分布的偽隨機數(shù)[r]，[r∈0，1]，若[p（?f）≥r]，則接受新點作為下一次模擬的初始點；否則放棄新點，仍取原來的點作為下一次模擬的初始點。

以上的原理過程也稱為Metropolis過程。可遵循一定的物理退火原理逐步降低物體溫度，重復(fù)Metropolis過程，形成模擬退火算法。

3 物流路線選擇的模擬退火策略

1）解空間和初始解

5 結(jié)束語

本文就物流線路選擇問題，提出了模擬退火算法解決該問題的策略。文中詳細闡述了問題的解空間、初始解、目標函數(shù)、產(chǎn)生新解方式、目標函數(shù)差、Metropolis接受準則和詳細流程圖。最后文中通過兩組實驗證明了本文提出的策略的可靠性和正確性。

參考文獻：

[1] Tao G， Michalewicz Z. Inver-over Operator for the TSP： International Conference on Parallel Problem Solving from Nature[C]， 1998.

[2] Woeginger G J. Exact Algorithms for NP-Hard Problems： A Survey[J]. 2003.

[3] 劉婷婷， 于衛(wèi)紅. 物流配送網(wǎng)絡(luò)最短路線規(guī)劃[J]. 電子商務(wù)， 2018（12）：9-10.

[4] 張倩， 張悟移， Rattapon Incharroen. 電商環(huán)境冷鏈物流路徑優(yōu)化研究[J]. 特區(qū)經(jīng)濟， 2018（11）： 103-105.

[5] 王勇. 遺傳算法在物流配送線路選擇方面研究[J]. 物流科技， 2018（4）.

[6] 李陽， 李文芳， 馬驪， 等. 混合退火算法求解旅行商問題[J]. 計算機應(yīng)用， 2014，34（S1）： 110-113.

[7] Valenzuela C L， Jones A J. Evolutionary Divide and Conquer（I）： A Novel Genetic Approach to the TSP[M]. MIT Press， 1993.

【通聯(lián)編輯：張薇】