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

楊飛

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

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

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）04-0270-02

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

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

1 相關(guān)工作

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

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

2 模擬退火算法原理

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

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

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

3）假如[?f≤0]，則接受新點(diǎn)，當(dāng)做下一次模擬的初始點(diǎn)；

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

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

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

1）解空間和初始解

5 結(jié)束語

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

參考文獻(xiàn)：

[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)濟(jì)， 2018（11）： 103-105.

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

[6] 李陽， 李文芳， 馬驪， 等. 混合退火算法求解旅行商問題[J]. 計(jì)算機(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)編輯：張薇】