改進的模擬退火算法在放射形專用線取送車優化中的應用

董 鵬 吳艷群

（蘭州交通大學交通運輸學院 蘭州 730070）

0 引 言

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

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

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

1 問題描述與分析

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

圖1 放射形專用線示意圖

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

圖2 送車和取車實際徑路

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

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

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

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

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

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

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

圖3 取送車作業時序圖

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

下面根據實例建立調機總等待時間（見表2～表5）的計算公式.現有如下貨運站，共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條專用線的各項作業所需時間 min

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

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

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

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

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

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

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

所以調機總等待時間為：0＋10＋40＋0＝50 min.

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

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

2 建立數學模型

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

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

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

3 算法設計

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

編碼方式.

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

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

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

圖4 順序編碼和3種算子的運算結果

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

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

4 仿真結果與分析

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

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

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

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

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

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

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

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

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

圖7 算例3的100次仿真結果分布圖

算法尋優能力分析.

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

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

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

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

5 結束語

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

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

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

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

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

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

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

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

［8］雷友誠，吳志飛.改進的蟻群算法在放射形專用線取送車優化中的應用［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］王 凌.智能優化算法及其應用［M］.北京：清華大學出版社，2001.

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

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

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