基于退火算法的物流配送網的求優研究

段敬民，常躍軍，李贊祥，崔建明

(1.三門峽職業技術學院建筑工程系，河南三門峽472000;2.西南交通大學橋梁及結構工程系，成都610031;3.河南工程技術學校建筑工程系，河南焦作454000;4.長安大學信息工程學院，西安710064)

1 前言

模擬退火算法［1］(simulated annealing，SA)原理就是模擬在某個溫度下，金屬分子停留在能量小的狀態時刻的概率要比停留在能量大的狀態的概率要大。

模擬退火算法與爬山算法對比，爬山算法是一種簡單的貪婪搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。

爬山算法的主要缺點是會陷入局部最優解，而不一定能搜索到全局最優解。如圖1所示:假設C點為當前解，爬山算法搜索到A點這個局部最優解就會停止搜索，因為在A點無論向哪個方向小幅度移動都不能得到更優的解。

爬山算法是完完全全的貪心算法，每次都以較小的步長選擇一個當前最優解，因此只能搜索到局部的最優值。模擬退火算法其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優解，達到全局的最優解。以圖1為例，模擬退火算法在搜索到局部最優解A后，會以一定的概率接受到D的移動。也許經過幾次這樣的不是局部最優的移動后會到達E點，于是就跳出了局部最大值A的范圍。

圖1 最優解搜索最優示意圖Fig.1 Schematic diagram of search for the optimal solution

在物流的配送網絡中［2］，存在尋優的網絡方案，如果采用這種優選方案，對物流配送企業來說會節省資金，增加配送速度;對貨物接收方來說能夠在較為合理的時間內接收物品，從而節省生產成本或消費成本。

2 模擬退火算法數學描述

若

即移動后得到更優解，則總是接受該移動;若

即移動后的解比當前解要差，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低(逐漸降低才能趨向穩定)。這里的“一定的概率”的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。根據熱力學的原理，在溫度為T時，出現能量差為dE的降溫的概率為P(dE)，可表示為

其中，k是一個常數，e表示自然指數，且dE＜0。

公式是指:溫度越高，出現一次能量差為dE的降溫的概率就越大;溫度越低，則出現降溫的概率就越小。又由于dE總是小于0(這是模擬退火的本質決定的)，因此dE/kT＜0，所以P(dE)的函數取值范圍是(0，1)，隨著溫度T的降低，P(dE)會逐漸降低。

將一次向較差解的移動看做一次溫度跳變過程，以概率P(dE)來接受這樣的移動。

終止條件:設置一個接近于0的較小的值，例如 0.3。

3 模擬退火算法的程序語言描述

3.1 模擬退火算法流程

模擬退火算法流程如圖2所示。

圖2 模擬退火算法流程Fig.2 Process of simulated annealing

3.2 參數與函數定義

在計算程序中的各個參數與函數的定義說明如下:

J(y):在狀態y時的評價函數值;Y(i):表示當前狀態;Y(i+1):表示新的狀態;r:用于控制降溫的快慢;T:系統的溫度，系統初始應該要處于一個高溫的狀態;T_min:溫度的下限，若溫度 T達到T_min，則停止搜索。

3.3 模擬退火算法偽代碼

//函數exp(dE/T)的取值范圍是(0，1)，dE/T越大，則exp(dE/T)也變大。

}

T=r* T; //降溫退火 ，0＜r＜1。r越大，降溫越慢;r越小，降溫越快

/*

＊若r過大，則搜索到全局最優解的可能會較高，但搜索的過程也就較長。若r過小，則搜索的過程會很快，但最終可能會達到一個局部最優值

*/

i++;}

4 模擬退火算法在區域交通流預測示例

4.1 區域物流配送示例

圖3為一簡單配送網絡圖，該網絡表示在一個區域中進行配送分配問題，等同于最優化問題，表述模型表達式見式(4)。

圖3 配送網絡圖Fig.3 Network diagram of distribution and delivery

式(4)中，q為OD(origin-destination)量;xa為路線a上的流量;Ca為路線a的路阻函數。

用退火算法解決此類問題，假設道路損耗的時間和經濟價值如(2，3，5，1，4)和(2，5，8，3，6)。

可行解采用0和1的序列表示，如i=(10101)表示選擇1，3，5線路，不選擇2和4。

4.2 計算進行步驟

第一步，初始化，假設初始解i=(11001)，初始溫度為10℃，計算開始。

第二步，在溫度T下局部搜索，直到“平衡”;降溫時機用在同一溫度下反復進行Metropolis［3］演算，假設次數為3，搜尋法則，隨機改變某一位的0，1或交換某兩位0，1的值。假設產生新解j=(11100)，f(j)=2+5+8=15＞13，所以接受新解。假設產生的新解j=(11010)，f(j)=2+5+3=10 ＜13，計算接受概率 P(T)=exp((10－13)/10)≈0.741，在(0，1)范圍內產生一個隨機數，如果隨機數小于接受概率，則接受j為新解，否則不接受。

第三步，降溫，假設溫度降為T=T－1，如果沒有達到結束標準，則返回第二步繼續執行。

4.3 計算結果

通過以上步驟的計算，i=(10010)，即選擇線路1和4作為最優解。存在2個最優的原因是結束過早，如果把成本計算進行的終止條件設置為0.03，則結果將是i=(00010)，即結果4為最優解。

5 結語

模擬退火算法同其他各類人工智能算法相似，是一種隨機算法，該算法并不一定能找到全局的最優精確解，但是可以比較快地找到問題的近似最優解，這是由算法本身決定的。但是作為一種在物流配送路徑中的最優預測模型，可以認為是比較好的工具。模擬退火算法缺點在于如果參數設置不當，很容易造成得到結果耗費大量的時間，這無疑近似于窮舉算法，這是科研工作者不希望看到的，故此參數設置將是模擬退火算法需要注重的一步。

［1］Kathleen M Carley，David M Svoboda.Modeling organizational adaptation as a simulated annealing process［J］.Sociological Methods Research ，1996，25(1):138 －168.

［2］池 潔，李 莉.物流中配送區域與配送路線的網絡優化法［J］.運籌與管理，2003，12(2):124－126.

［3］Beichl I，Sullivan F.The metropolis algorithm［J］.Computer in Science ＆ Engineering，2000，2(1):65 －69.