模擬退火算法在企業(yè)鐵路車輛調(diào)度中的應(yīng)用

林滿山 郭永輝

（北方工業(yè)大學(xué)信息工程學(xué)院，北京100043）

0 引言

隨著經(jīng)濟的發(fā)展，擁有自備鐵路站的企業(yè)越來越多。這些企業(yè)內(nèi)的鐵路線之間連接情況各不相同，每條線路的長度也不盡相同，各個倉庫在線路上的分布更是千差萬別，如何使將一個站點上的車輛調(diào)度到企業(yè)內(nèi)部各個倉庫站點所行駛的路程最短，是企業(yè)火車調(diào)度所面臨的一個問題。本文將使用模擬退火算法求路程最短的車輛調(diào)度路徑。

1 模擬退火算法

模擬退火算法的思想最早是由Metropolis等提出的，其出發(fā)點是基于固體物質(zhì)的退火過程與一般的組合優(yōu)化問題之間的相似性［1］。模擬退火過程由3部分組成：（1）加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當(dāng)溫度足夠高時，固體將熔為液體，從而消除系統(tǒng)原先存在的非均勻狀態(tài)。（2）等溫過程。對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝著能量減少的方向進行，當(dāng)自由能達到最小時，系統(tǒng)達到平衡狀態(tài)。（3）冷卻過程。使粒子熱運動減弱，系統(tǒng)能量下降，得到晶體結(jié)構(gòu)。模擬退火算法可以求解不同的非線性問題，對不可微分甚至不連續(xù)的函數(shù)進行優(yōu)化，能以較大的概率求得全局最優(yōu)解，該算法還具有較強的魯棒性、全局收斂性、隱含并行性及廣泛的適應(yīng)性，并且能處理不同類型的優(yōu)化設(shè)計變量（離散的、連續(xù)的、混合的），不需要任何的輔助信息，對目標(biāo)函數(shù)和約束函數(shù)也沒有任何要求［2］。

2 最短行程車輛調(diào)度路徑的求解

首先根據(jù)企業(yè)內(nèi)部鐵路線及線上站點所在位置等信息，將鐵路線及站點轉(zhuǎn)化為圖拓?fù)浣Y(jié)構(gòu)，然后利用圖的最短路徑算法求得每2個站點之間的最短距離，最后根據(jù)每2個站點之間的距離，利用模擬退火算法求最短行程路徑。模擬退火算法的求解流程如圖1所示。

圖1 模擬退火算法求解流程圖

算法實現(xiàn)步驟如下：

（1）控制參數(shù)設(shè)置。設(shè)置控制參數(shù)：降溫速率q、初始溫度T0、結(jié)束溫度Tend和鏈長L。

（2）初始解。對問題的解空間進行編碼，對于有n個站點的最短路程的調(diào)度路徑，可以用1～n的一個排列表示，問題的解空間是n的全排列，隨機生成n的一個排列作為初始解。

（3）變換生成新解。隨機選擇當(dāng)前解中的2個站點進行交換，產(chǎn)生新的解。

（4）Metropolis準(zhǔn)則。如果當(dāng)前解S1的路程為f（S1），新解S2的路程為f（S2），路徑差df＝f（S1）－f（S2），則 Metropolis準(zhǔn)則為：

（5）降溫。利用降溫速率q降溫，令T＝qT，若T小于結(jié)束溫度，則停止。

3 仿真結(jié)果與分析

以某企業(yè)鐵路線上的14個站點為例計算最短行程路徑。每2個站點之間的最短距離如表1所示。

表1 每2站點之間的最短距離 單位：km

以降火速率q＝0．9、初始溫度T0＝1 000K、結(jié)束溫度Tend＝0．001K、鏈長L＝200次為參數(shù)，以表1中數(shù)據(jù)為輸入數(shù)據(jù)，模擬退火算法得到的從V1去往全部站點并回到起始位置V1的最短路程是28km，最短路徑是V1→V8→V13→V7→V6→V5→V12→V4→V14→V3→V2→V10→V9→V11→V1。模擬退火算法的進化過程如圖2所示。

圖2 模擬退火算法進化過程

4 結(jié)語

本文針對企業(yè)的鐵路站車輛調(diào)度最短行程的路徑優(yōu)化問題，提出了模擬退火算法的求解過程，并用仿真實例驗證了算法的正確性。

［1］李香平，張紅陽．模擬退火算法原理及改進［J］．軟件導(dǎo)刊，2008（4）

［2］汪靈枝，周優(yōu)軍．一種有效的全局優(yōu)化算法——模擬退火算法［J］．柳州師專學(xué)報，2005（2）