禁忌搜索算法在編組站調機運用計劃中的應用

王 爍，何世偉，黎浩東，申永生

（北京交通大學 交通運輸學院，北京 100044）

禁忌搜索算法在編組站調機運用計劃中的應用

王 爍，何世偉，黎浩東，申永生

（北京交通大學 交通運輸學院，北京 100044）

在分析論述調機運用計劃編制方法的基礎上，提出應用禁忌搜索算法進行編組站調機運用計劃的編制。分別以最小化延遲解體列車和編組列車加權數量為目標建立數學模型，以解編順序作為優化對象，設計禁忌搜索算法對其進行求解，并以解體順序為例，采用兩兩交換(2-opt)方式構建鄰域，以該操作前后列車解體順序的變化作為禁忌對象構建禁忌表，利用軟件編程實現模型計算，并通過算例驗證該算法的可行性和有效性。

編組站；調機運用計劃；解編順序；禁忌搜索算法

1 概述

調機運用計劃是編組站階段計劃的關鍵內容之一，用于合理安排每臺調車機車在本階段必須完成的調車工作，以及這些調車機車的作業時間，即確定到達列車的解體順序、出發列車的編組順序，以及安排取送車等問題。在實際作業中，解體或編組作業所占用調機的時間通常在解體或編組最早允許開始時刻和最晚必須完成時刻之間的范圍內。而由于調機能力有限、到達車流過多等原因，可能會造成部分作業無法按時完成，這時調機運用計劃還需要決定哪些列車允許晚點，哪些列車必須保證準點[1]。

目前，處理調機運用計劃編制問題的方法主要有排序方法[1]和圖論方法[2-3]。排序方法是把編組站調機運用計劃看作是具有不同開工、完工時間窗口的單機排序問題，如以最小化晚點列車的加權數量為優化目標，運用排序理論對調機運用問題進行了研究[1]。圖論方法分為圖染色理論方法和網絡分解方法[2]。由于調機運用計劃屬于完全 NP 問題，尚不存在較好的精確算法。因此，各種智能算法被應用到調機運用計劃的編制問題中，如蟻群算法[1]、模擬退火算法[3]、遺傳算法[4]等。禁忌搜索算法是 Glove F.為模擬智能過程而提出的一種具有記憶功能的全局逐步優化算法[5]，它是一種串行優化算法，通過記憶近期操作的存儲結構來避免某狀態的重復出現，并結合特赦規則實現全局快速搜索。禁忌搜索算法自提出以來，已被廣泛應用于函數優化和組合優化[6]、電路設計[7]、生產調度[8]、機器學習及模式識別[9]等領域。在編組站調機計劃的編制中，運用禁忌搜索算法通過兩兩交換 (2-opt) 方式構建鄰域，并記錄該操作前后列車解體順序的變化，以構建禁忌表進行算法設計，實現編組站調機運用計劃的優化編制。

2 數學模型

2.1 解體順序數學模型

解體順序數學模型遵循的假設條件：①編組站為單溜放駝峰，調機一次只能無中斷完成1列車的解體作業；②列車到達時刻可以在計劃編制開始時得到，不考慮列車到達車站時刻、各項作業時間等因素的隨機波動性影響；③在解體計劃編制之前已經完成配流計算；④不考慮其他輔助生產作業時間的影響 (交接班、整場、吃飯、整備等)，不考慮取送、調移等作業時間。

通過上述定義，編組站調機運用問題可以描述為：假定到達列車 i 最早開始解體、最晚結束解體的時間窗是[,]，即列車應該在[]時間段內解體完畢。設第 k 個時段解體的列車 i 實際解體結束時刻是+，如果+≤，表明工作按期完成，則取 U＝0；如果+>，則列車 i 受到晚點懲罰，取 Uk＝1，晚點懲罰系數為 wi。

綜上所述，以最小化延遲解體列車加權數量為目標構建編組站的調機運用計劃編制優化模型為：

模型中，約束⑵表示每列車只能在一個時段被解體；約束⑶表示每個時段只能解體1列列車；約束⑷表示第 k＋1 時段對應列車的解體開始時間必須在第 k 時段對應列車的解體結束時刻之后；約束⑸保證被安排在時段 k 上的列車開始解體時刻晚于其最早開始解體時刻；約束⑹和約束⑺保證如果時段 k 上的列車解體結束時刻晚于最晚解體結束時刻，則 Uk＝1，否則 Uk＝0。

2.2 編組順序數學模型

編組順序數學模型遵循的假設條件：①峰尾只有1臺編組調機，調機一次只能無中斷完成1列車的編組作業；②列車最早開始編組時刻和最晚結束編組時刻可以在計劃編制開始時得到，不考慮列車到達車站時刻、各項作業時間等因素的隨機波動性影響；③在編組作業之前已經完成配流計算；④不考慮輔助生產作業時間的影響 (交接班、整場、吃飯、整備等)，不考慮取送、調移等作業時間。

模型參數定義：階段出發列車數為n，j＝1,…,n為出發列車的編號；,,,,分別表示列車 j 的出發時刻、出發技檢時間、編組時間、最早編組開始時刻、最晚編組結束時刻；wj為列車 j 的延遲編組懲罰系數，是一個權值；k' ＝1,…,n 為編組作業時段，每個時段對應1列車的編組作業；M 為一個足夠大的整數；決策變量表示第 k' 個時段列車的開始編組時刻；0-1 決策變量xj，k′表示列車 j 是否被安排在第 k' 個時段編組，是則取值為 1，否則取值為 0；0-1 決策變量 Uk’表示安排在時段 k' 上的列車是否能按時完成編組，是則取值為 0，否則取值為 1。

綜上所述，以最小化延遲編組列車加權數量為目標構建編組站的調機運用計劃編制優化模型為：

模型中，約束⑼表示每列車只能在一個時段被編組；約束⑽表示每個時段只能編組1列車；約束⑾表示第 k'＋1時段對應列車的編組開始時刻必須在第 k' 時段對應列車的編組結束時刻之后；約束⑿保證被安排在時段 k' 上的列車開始編組時刻晚于其最早開始編組時刻；約束⒀和約束⒁保證如果時段k' 上的列車編組結束時刻晚于最晚編組結束時刻，則 Uk'＝1，否則 Uk'＝0。

3 模型求解算法

3.1 禁忌搜索算法

禁忌搜索算法是對人類智力過程的一種模擬，通過對局部鄰域搜索的擴展，對解空間進行更加深入的搜索，以實現全局逐步尋優。其主要思想是在搜索的過程中標記已經找到的局部最優解，在進一步的搜索過程中避開這些局部最優解 (置于禁忌表中)，從而達到跳出局部循環，尋找全局最優解的目的。

利用禁忌搜索算法求解組合優化問題時，首先產生一個初始解作為當前解，然后在當前解的鄰域中搜索若干個解，取其中的最好解作為新的當前解。為了避免對已搜索過的局部最優解的重復，禁忌搜索算法使用禁忌表記錄已搜索過的局部最優解的歷史信息，這使得算法可在一定程度上避開局部最優點，從而開辟新的搜索區域。

3.2 禁忌搜索算法求解調機運用計劃

以解體過程為例，其算法步驟如下。

步驟1：選定一個初始解為當前解 xnow，令禁忌表 H＝φ；設置當前迭代步驟 Nc＝0。

禁忌表的構建：禁忌對象為通過2-opt方式構建鄰域后，前后列車解體順序的變化；禁忌長度在程序調試中決定。

步驟 2：構造當前解的鄰域，生成候選集合V。

鄰域構造：交換相鄰兩列車的解體順序所得的列車解體順序為當前解的鄰居，所有鄰居構成的集合為當前解的鄰域。

步驟3：在候選集中選取評價值最好的解，更新為當前解；并判斷該解是否優于當前最優解 x*，若是，則該解作為新的最優解。

步驟 4：更新禁忌表H。

步驟 5：重復步驟2至步驟 4，直到 Nc達到最大迭代步數 N，N 在程序調試過程中決定；輸出計算結果，結束計算。

4 應用算例

以單溜放駝峰、峰尾1臺調機的編組站為例，列車的解體和編組各由1臺調機擔當。原始數據取自文獻[1]，到達列車車流數據如表1所示，到達列車解體時間如表2所示。

表1 到達列車編組信息

表 2 到達列車解體時間表

以先到先解的原則設定解體順序的初始解，禁忌長度取為10，迭代次數為50。模型算法運用VC++6.0編程實現，在AMD Turion 2.0 GHz、2 G RAM計算機上運行求解，所求得的優化結果如表3所示。

表3 到達列車解體順序

通過計算結果可以看出，有2列到達解體列車26027、85991無法在最晚解體結束時刻之前按時完成解體作業，列車的編組和出發將因此晚點。算例結果證明，禁忌搜索算法可行，并且具有較高的效率 (運行時間在1 s以內)。在測試過程中，禁忌長度在 5～20 范圍內調整，雖然運算時間有細微變化，但算法均能收斂至相同的最優解，而且都保持在1 s之內，說明算法具有較好的穩定性。最終求得的最優解在迭代第4步獲得，這表明算法在求解過程中收斂較早。本文所求得的解體順序與文獻[1]給出的解體順序略有不同，但目標函數值相同，說明列車解編方案存在多樣性而不是惟一的。在不同的搜索策略、相同的目標函數值條件下，求得的解編方案可能會有所不同。

5 結束語

通過研究禁忌搜索算法在編組站解編調機運用計劃編制中的運用，以最小化延遲解體列車加權數量和最小化延遲編組列車加權數量為目標，構建調機運用優化的數學模型，以解體過程為例設計相應的禁忌搜索算法，采用 2-opt 方式的策略構建鄰域，同時以該操作前后列車解體順序的變化作為禁忌對象構建禁忌表。最后，通過實例計算驗證了所設計的禁忌搜索算法的有效性。在此基礎上需要進一步研究禁忌搜索策略在編組站配流和階段計劃編制方面的綜合應用。

[1] 王世東，鄭 力，張智海. 蟻群算法在調機運用計劃中的應用[J]. 中國鐵道科學，2007，28(3)：120-125.

[2] 李文權，王 煒，杜 文，等. 鐵路技術站調機運用模型及算法[J]. 系統工程學報，2000，15(1)：38-43.

[3] 徐 杰，杜 文，李宗平，等. 基于模擬退火算法和圖著色的調車機車安排研究[J]. 鐵道學報，2003，25(3)：24-30.

[4] 何世偉，宋 瑞，胡安洲. 編組站階段計劃剛性與柔性優化的協調研究[J]. 鐵道學報，1999，21(4)：1-8.

[5] Glover F. Tabu search：part I [J]. Journal on Computing，1989，1(3)：190-206.

[6] Blue，J.A.，Bennett K.P. Hybrid extreme point tabu search[J]. European Journal of Operational Research，1998，106(2/3)：676-688.

[7] Sait S.M，Youssef H. Coms/Bicmos mixed design using tabu search[J]. Electronics Letters，1998，34(14)：1395-1396.

[8] Lutz C.M，Davis K.P. Sun M. Determining buffer location and size in production lines using tabu search[J]. European Journal of Operational Research，1998，106(2/3)：301-316.

[9] Al-Sultan K.S，Fedjki C.A. A tabu search- based algorithm for the fuzzy clustering problem[J]. Pattern Recognition，1997，30(12)：2023-2030.

[10] 何世偉，宋 瑞，朱松年. 編組站階段計劃解編作業優化模型及算法[J]. 鐵道學報，1997，19(3)：1-8.

Application of Tabu Search Algorithm on the Scheduling Problem of Shunting Locomotive

WANG Shuo, HE Shi-wei, LI Hao-dong, SHEN Yong-sheng

(School of Traffic and Transportation, Beijing JiaoTong University, Beijing 100044, China)

Based on analyzing the scheduling method of shunting locomotive, this paper puts forward the scheduling plan by using tabu search algorithm. Establishing the mathematical model by taking the minimized weighted number of tardy uncoupling and formation trains as targets,and designing the tabu search algorithm to make solution by taking the sequence of train uncoupling as optimized object. Then the tabu search algorithm is designed to make solution by using 2-opt strategy with example of sequence of uncoupling, and the tabu table was established by taking the change of breaking up sequence before and after the operation as tabu object, and the model calculation was realized by using software programme. The algorithm was proved feasible and effective by the examples.

Marshalling Station; Scheduling Problem of Shunting Locomotive; Sequence of Train Uncoupling; Tabu Search Algorithm

1003-1421(2011)02-0083-05

U268.2

A

2010-08-02

國家自然科學基金項目(60776825)；北京交通大學優秀博士生創新基金(141076522)；北京交通大學研究生創新項目(2009YJS042)

責任編輯：馮姍姍