改進的模擬退火算法在放射形專用線取送車優(yōu)化中的應(yīng)用

董 鵬 吳艷群

（蘭州交通大學(xué)交通運輸學(xué)院 蘭州 730070）

0 引 言

在較大的鐵路貨運站、技術(shù)站和大型企業(yè)鐵路專用線的各種運輸作業(yè)中，取送車作業(yè)都是非常重要的工作，其效率高低直接關(guān)系到車輛周轉(zhuǎn)率和貨物送達的速度，進而影響企業(yè)的經(jīng)營效益.因此，對取送車作業(yè)進行優(yōu)化，能夠有效縮短車列的停留時間，加速車輛周轉(zhuǎn)率，對于提高運輸效率和企業(yè)的經(jīng)濟效益意義重大.

鐵路專用線按裝卸作業(yè)點的不同布置形式，分為放射形和樹枝形2大類［1］.本文主要討論放射形專用線取送車優(yōu)化問題.宋建業(yè)等［2－3］采用表上移動法以取送同序方案為初始狀態(tài)，通過在方案計算表上移動相鄰送車順序或取車順序，使各作業(yè)地點中斷時間的最大值降低到最小程度，從而得到一個最優(yōu)取送順序方案，方法相對易于實現(xiàn).王慈光等［4］針對該問題給出了送車需要時間和取車需要時間的計算公式，并用送車增量和取車增量替代目標(biāo)函數(shù)簡化計算.用分部求解的思路尋求最佳取送方案，本質(zhì)是在送車狀態(tài)樹上采用隱枚舉法進行搜索.牟峰、王慈光等［5－6］將取送車作業(yè)作為一個系統(tǒng)進行整體考慮，以貨車在站停留的總車小時消耗最小為優(yōu)化目標(biāo)，建立了數(shù)學(xué)模型，并采用基于云模型的參數(shù)自適應(yīng)蟻群遺傳算法進行求解.上述若干文獻對問題本身的研究透徹，建立的數(shù)學(xué)模型成熟，后期的研究則主要集中于智能優(yōu)化算法的設(shè)計和仿真分析，力圖提高計算速度.文獻［7］設(shè)計了單親遺傳算法，文獻［8］提出了一種基于遺傳算法信息素更新策略的改進蟻群算法，并結(jié)合算例進行仿真，也都取得了較好的效果.

本文針對放射形專用線直達車流取送車問題設(shè)計了一種專門的模擬退火算法，并結(jié)合算例進行仿真和分析.

1 問題描述與分析

放射形專用線的布置圖形可抽象為圖1，其中節(jié)點0為貨運站，節(jié)點1，2，3分別為3條專用線.放射形專用線直達車流取送車問題可描述為：若干直達列車整列到達貨運站（節(jié)點0）后，首先在貨運站解編成車列；然后由一臺調(diào)車機車將其中一個車列由貨運站送往對應(yīng)的專用線，到達專用線后將車列摘下進行裝卸作業(yè)，調(diào)車機車立即返回貨運站，這就完成了一次送車作業(yè)；重復(fù)執(zhí)行上一步，直到所有車列都送往專用線為止，這一過程稱為送車過程；接下來開始取回車列，調(diào)車機車從貨運站開到最先完成裝卸作業(yè)的專用線，連掛車列并返回貨運站，完成一次取車作業(yè)；重復(fù)執(zhí)行上一步，直到所有車列都取回到貨運站為止，這一過程稱為取車過程.

圖1 放射形專用線示意圖

放射形專用線的布置形式?jīng)Q定了調(diào)車機車每次將一車列由貨運站送到專用線后，必須返回到貨運站，才能開始送下一車列.取車過程也是一樣.通常取送車作業(yè)只由一臺調(diào)車機車完成.按節(jié)點1→2→3的順序送車過程見圖2a），按節(jié)點2→1→3的順序取車的過程見圖2b）.

圖2 送車和取車實際徑路

定義I為專用線集合，I＝｛1，2，3，…，n｝.其中：n為是專用線的最大數(shù)量.

衡量取送車作業(yè)的好壞必須考慮如下3種時間耗費.

1）裝卸作業(yè)時間Li各專用線的裝卸作業(yè)所需時間各不相同，用Li表示，i∈I.

2）取送作業(yè)時間Ti一次完整的送車作業(yè)包括調(diào)機連掛車列自貨運站開往專用線和調(diào)機單機自專用線返回貨運站2個單程，而取車作業(yè)也同樣包括2個單程.一般將每個單程所需時間認(rèn)為相等，因此取車作業(yè)時間和送車作業(yè)時間也相等.設(shè)調(diào)機自貨運站開往專用線i的所需單程時間為ti，那么：調(diào)機完成一次取車或送車作業(yè)的時間Ti＝＝2ti，i∈I，通常：Li?Ti.

3）調(diào)機等待時間Wi當(dāng)全部送車作業(yè)完成之后，只有其中一條專用線完成裝卸作業(yè)之后調(diào)機才能開始取車作業(yè)，因此可能需要調(diào)機等待裝卸作業(yè)完成，這一時間稱為該專用線的調(diào)機等待時間，用Wi表示，i∈I.假如某貨運站有兩條專用線，取送作業(yè)和裝卸作業(yè)所需時間見表1，那么調(diào)車機車按先1后2的順序送車，就會在到專用線1取車之前產(chǎn)生調(diào)機等待時間W1.

圖3為取送車作業(yè)時序.圖中方塊1～10表示調(diào)車機車往返過程，0～60min為送車過程，80～150min為取車過程.其中白色方塊5（60～80 min之間）是全部送車任務(wù)結(jié)束后，要等待專用線1完成裝卸作業(yè)而耗費的時間W1（方塊上方畫有虛線箭頭），白色方塊8（100～110min之間）表示為等待專用線2完成裝卸作業(yè)而耗費的時間W2.由圖3可見，調(diào)車機車只需要在一條專用線裝卸作業(yè)完成之時趕到即可，而不是等裝卸作業(yè)完成之后才去取車.所以圖中1號專用線的裝卸作業(yè)從車列送達后開始，送車過程真正提供的裝卸作業(yè)時間只有＝t＋2t（10～60min之間），12但取車過程又可以提供時間（80～90min之間），加起來正好是T1＋T2＝2（t1＋t2）.

表1 2條專用線的各項作業(yè)所需時間 min

圖3 取送車作業(yè)時序圖

放射形專用線直達車流取送車問題的優(yōu)化目標(biāo)只能是各種作業(yè)時間之和最小，而不可能是取送車走行路徑最短.因為對每條專用線來說，調(diào)車機車取送各一次，路徑長度是固定的.在3種作業(yè)時間中，裝卸作業(yè)時間由裝卸任務(wù)和裝卸能力決定，由于裝卸能力通常是穩(wěn)定的，所以一個裝卸任務(wù)所需的裝卸時間是固定的；取送作業(yè)所需時間由取送作業(yè)走行長度和機車走行速度決定，在線路條件和機車類型沒有較大改進的情況下也不會有太大變化；只有調(diào)機等待時間會由于取送車順序的不同而有所不同.因此最好的取送車方案是使調(diào)機等待時間最小的方案，而這與送車順序和取車順序密切相關(guān).

下面根據(jù)實例建立調(diào)機總等待時間（見表2～表5）的計算公式.現(xiàn)有如下貨運站，共4條專用線，分別用1，2，3，4進行編號，即I＝｛1，2，3，4｝.

送車順序用S（s1，s2，s3，s4）表示，如果有4條專用線，送車順序為4－1－2－3，則s1＝4，s2＝1，s3＝2，s4＝3，即 S＝（4，1，2，3）.取車順序用Q（q1，q2，q3，q4）表示.

表2 4條專用線的各項作業(yè)所需時間 min

送車過程為各專用線所提供的裝卸作業(yè)時間為θsi：

各專用線還需要的裝卸作業(yè)時間為φsi

表3 送車順序為4－1－2－3時還需要的裝卸作業(yè)時間min

對于任意的取車順序Q（q1，q2，…qn）：

也就是說，對于要去取車的專用線如果還沒有完成裝卸作業(yè)，調(diào)機就必須等待一段時間；否則等待時間為0.同理：

下面針對表3計算出的結(jié)果采用2種不同的取車順序所得到的調(diào)機總等待時間.見表4、表5.

表4 取車順序為1－4－3－2時的計算結(jié)果min

所以調(diào)機總等待時間為：0＋10＋40＋0＝50 min.

表5 取車順序為1－2－4－3時的計算結(jié)果min

這時的調(diào)機總等待時間為：0＋0＋0＋20＝20 min.兩者相比，在送車順序一定的情況下，顯然第二種取車順序更好.

2 建立數(shù)學(xué)模型

根據(jù)對放射形專用線直達車流取送車問題的分析可知，使各專用線的調(diào)機等待時間最小的取送車方案才是最好的方案，而這由取送車順序決定.假定某一貨運站有n條專用線，用集合I＝｛1，2，…，n｝表示.送車順序用S（s1，s2，…，sn）表示，取車順序用Q（q1，q2，…，qn）表示.

如果在取送過程中為各地點提供的裝卸作業(yè)時間都大于等于其所需時間，那么調(diào)車機車在去各地點取車時裝卸作業(yè)都已完成，無需等待，這是最理想的情況.在一般情況下，由于在車輛取送過程中為某些專用線提供的裝卸時間不足，就會產(chǎn)生調(diào)車機車到部分專用線取車之前必須等待一段時間.對取送車方案的優(yōu)化是使總的等待時間最小.

因此，放射形專用線直達車流取送車問題的數(shù)學(xué)模型可完整表示如下.

3 算法設(shè)計

根據(jù)放射形專用線直達車流取送車問題的特點，設(shè)計了一種改進的模擬退火算法，用于此問題的求解.模擬退火算法是基于Monte Carlo迭代求解策略的一種通用的隨機尋優(yōu)算法，最早由Metropolis等于1953年提出，1983年Kirkpatric等將其應(yīng)用于組合優(yōu)化問題，目前已在VLSI、生產(chǎn)調(diào)度、車輛路徑、機器學(xué)習(xí)等諸多領(lǐng)域得到成功應(yīng)用［9－10］.

編碼方式.

對送車順序采用順序編碼方案，簡單自然.如編碼為［4 2 1 3］的一個方案表示按專用線4－2－1－3的順序送車.而送車順序一旦確定，各專用線完成裝卸的時間也就可以確定下來了.那么此時，到最先完成裝卸作業(yè)的專用線取車顯然是最有利的.

取車順序由裝卸完成的早晚決定，而裝卸完成的早晚是由送車順序決定的，所以，送車順序決定取車順序.如果沒有考慮這一點，n條專用線的送車順序有n！種，取車順序也有n！種，取送車方案總共有n！×n！＝（n?。?種方案；考慮這一特點，問題的解空間則會從（n?。?急劇下降到n！，搜索空間大大縮小，有利于提高算法的尋優(yōu)能力.因此本算法只對送車順序進行編碼，不對取車順序進行編碼.取車順序由裝卸完成的先后來確定.

鄰域的構(gòu)造：在采用順序編碼的模擬退火算法中（例如求解TSP問題），2點交換（SWAP）算子是最常見的鄰域構(gòu)造方法，此外還有反轉(zhuǎn)算子（INV）和插入算子（INS）［11］.如果送車順序是1→2→3→4→5，2個點分別是第二個點和第五個點（見圖4a）），則分別采用2點交換、反轉(zhuǎn)和插入算子得到的新的送車順序見圖4b）～d）.

圖4 順序編碼和3種算子的運算結(jié)果

為了提高算法的尋優(yōu)能力，本算法將上述3種算子結(jié)合起來用于鄰域構(gòu)造，方法是根據(jù)概率來選用不同的算子.具體來說，如果規(guī)定在鄰域構(gòu)造時70%的情況下使用2點交換算子，20%的情況下使用反轉(zhuǎn)算子，10%的情況下使用插入算子，也就是說這三種算子使用的概率分別是0.7，0.2和0.1.那么在實際運用時，首先產(chǎn)生一個［0，1）之間的隨機數(shù)r，如果0.0≤r＜0.7，就使用兩點交換算子，如果0.7≤r＜0.9就使用反轉(zhuǎn)算子，如果0.9≤r＜1.0就使用插入算子.鄰域構(gòu)造方式的多樣化也有利于提高算法的尋優(yōu)能力.

溫度控制：初始溫度為T0＝100，終止溫度為Tf＝0.01，每個溫度下的內(nèi)循環(huán)次數(shù)為100次.降溫函數(shù)定義為：Tk＋1＝αTk.其中：降溫系數(shù)α＝0.96.

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

本文用CJHJ語言編寫程序?qū)崿F(xiàn)了這一算法，對應(yīng).Net Framework版本為4.0.為檢測算法的性能，特地構(gòu)造了如下3個算例，專用線數(shù)量分別是8條、9條和10條.針對每個算例都進行了100次仿真計算，每次計算的隨機數(shù)種子各不相同，得到的最好取送車方案和調(diào)機總等待時間見表6～7.

文中編寫了一個窮舉法的程序，對上述3個算例的全部送車方案一一進行計算（送車方案數(shù)分別為40 320，362 880，3 628 800個），結(jié)果表明，改進的模擬退火算法找到的最好解就是該算例的最優(yōu)解.見表8、圖5～圖6.

表6 3個算例的取送時間和裝卸時間 min

表7 3個算例的最好取送車方案

表8 3個算例的計算時間比較

圖中圓點表示在降溫過程中當(dāng)前方案的調(diào)機總等待時間.此圖形象地表示出了模擬退火算法在一次仿真實驗的迭代過程中即能向好的方向搜索，也能向差的方向搜索，溫度較高時波動劇烈，溫度較低時穩(wěn)定性有所提高，即使有較大的偏離也能很快的回到當(dāng)前最好解的附近，在局部搜索和全局搜索2個方面實現(xiàn)了較好的平衡.

圖5 算例3的1次仿真計算的完整迭代過程

圖6 算例3的100次仿真實驗得到的最好方案的調(diào)機總等待時間

對算例3進行了100次實驗得到的最好解的目標(biāo)函數(shù)的分布見圖7，即等待時間為9min的出現(xiàn)了3次，出現(xiàn)最多的是等待時間為12min的方案，共出現(xiàn)85次.

圖7 算例3的100次仿真結(jié)果分布圖

算法尋優(yōu)能力分析.

按照所設(shè)定的溫度控制參數(shù)，設(shè)溫度從初始的100℃下降到0.01℃

設(shè)溫度從初始的100℃下降到0.01℃需要迭代n次，則

將T0＝100，Tf＝0.01和α＝0.96代入式（3）得到n＝226.

根據(jù)算例3進行分析，有10條專用線，送車順序就有10！＝3 628 800種.整個降溫過程從初始溫度到最終溫度共經(jīng)歷226個溫度，在每個溫度下都迭代100次，總共檢查了22 600個解，只占解空間總數(shù)的0.62%，但結(jié)果已經(jīng)令人非常滿意，可見該算法無論是求解速度還是解的質(zhì)量都是比較高的.

5 結(jié)束語

放射形專用線直達車流取送車方案的優(yōu)劣直接影響到車輛周轉(zhuǎn)和貨物送達的時間.針對這一問題在模擬退火算法中，用順序編碼表示送車順序，按一定概率使用兩點交換、插入和反轉(zhuǎn)算子來構(gòu)造鄰域，加快了收斂速度，提高了搜索能力，能夠盡量壓縮調(diào)車機車非生產(chǎn)等待時間，其計算性能通過仿真實驗結(jié)果也得到了充分驗證.這一思想不僅能夠運用到樹枝狀專用線取送車方案的優(yōu)化中，也能運用到一般組合優(yōu)化問題中提高求解速度和尋優(yōu)能力.

［1］彭其淵，王慈光.鐵路行車組織［M］.北京：中國鐵道出版社，2007.

［2］宋建業(yè)，謝金寶.鐵路行車組織基礎(chǔ)［M］.北京：中國鐵道出版社，2005.

［3］宋建業(yè).直達列車多點裝卸取送順序優(yōu)化的表上移動法［J］.蘭州鐵道學(xué)院學(xué)報：自然科學(xué)版，2002（1）：76－79.

［4］王慈光.放射形專用線非直達車流取送車問題研究［J］.交通運輸工程與信息學(xué)報，2006，4（3）：16－23.

［5］牟 峰，王慈光，楊運貴.放射形專用線非直達車流取送車模型及算法［J］.鐵道學(xué)報，2009，31（3）：2－5.

［6］牟 峰，王慈光，左大杰，等.放射形專用線取送車模型及算法［J］.西南交通大學(xué)學(xué)報，2010，45（1）：104－110.

［7］李海軍，朱昌鋒.放射形鐵路專用線直達車流取送車問題的單親遺傳算法研究［J］.鐵道科學(xué)與工程學(xué)報，2011，8（6）：114－117.

［8］雷友誠，吳志飛.改進的蟻群算法在放射形專用線取送車優(yōu)化中的應(yīng)用［J］.控制工程，2012，19（6）：1007－1010.

［9］KIRKPATRIC S，GELATT C D，VECCHI M P.Optimization by simulated annealing［J］.Science，1983，220：671－680.

［10］KIRKPATRIC S，TOULOUSE G.Configuration space analysis of traveling salesman problem［J］.J Phys，1985，46：1277－1292.

［11］王 凌.智能優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2001.

［12］雷友誠，涂祖耀，桂衛(wèi)兵，等.基于遺傳蟻群算法的樹枝型鐵路取送車問題優(yōu)化［J］.中南大學(xué)學(xué)報：自然科學(xué)版，2011（8）：55－58.

［13］夏鴻斌，須文波，劉 淵.自適應(yīng)并行機制的改進蟻群算法［J］.系統(tǒng)工程與電子技術(shù)，2009（12）：102－106.

［14］夏鴻斌，須文波，劉 淵，整合遺傳算法改進的蟻群算法［J］.江南大學(xué)學(xué)報：自然科學(xué)版，2009（2）：44－47.