技術站單組列車編組計劃的禁忌搜索算法研究

張海艦

(鄭州鐵路局安陽車務段，河南 安陽 455000)

?

【交通運輸】

技術站單組列車編組計劃的禁忌搜索算法研究

張海艦

(鄭州鐵路局安陽車務段，河南 安陽 455000)

摘要：技術站列車編組計劃是鐵路運輸組織工作中的難點之一。國內現有對單組列車編組計劃的研究，以運用0-1規劃研究編組去向的車流遞推關系最為典型，這類研究的本質在于優化各支車流的第一到站?；诖?，本文設計了一種實數編碼的禁忌搜索算法，可用來求解路網性列車編組計劃。算例表明該算法能快速、有效地求解技術站單組列車編組計劃。與LINGO軟件相比，禁忌搜索算法只需較少的時間便可搜索到全局最優解。

關鍵詞：編組計劃；技術直達列車；0-1規劃；禁忌搜索算法

列車編組計劃在鐵路運輸組織工作中具有重要作用，用來確定各支車流的編掛方案，其優劣直接關系到鐵路設備的利用率和運輸成本[1]。技術站列車編組計劃作為編組計劃的核心，又分為單組列車編組計劃和分組列車編組計劃[2]。因我國鐵路以開行同一到站的單組列車為主，國內對技術站單組列車編組計劃的研究較為成熟。這類研究多是在給定各技術站的有關參數、車流量及車流徑路的條件下，求解使所有車流的車小時消耗最少的編組方案，其中，以運用0-1規劃法研究編組去向的車流遞推關系最為典型[3-6]。技術站列車編組計劃問題屬于超大規模的組合優化問題[3]，問題的非線性更是增加了求解難度，適合運用現代優化算法求解，如模擬退火算法[3]、遺傳算法[4]、鄰域搜索算法[7]、以及禁忌搜索算法[8]等。

就技術站單組列車編組計劃而言，其實質上是為每一支技術站車流選擇第一到站，要么直達送至終到站，要么直達送至第一改編站。同時，由于問題規模會隨路網車站數增加呈指數型增長，列車編組計劃適于用鄰域搜索算法求解，但是存在易于陷入局部最優解的缺陷。本文選擇采用全局迭代尋優能力較強的禁忌搜索算法來進行求解，將各支技術站車流的第一到站編碼為一位整數，編碼簡單易于操作，通過求解算例路網，驗證了算法的實用性和高效性。

1技術站單組列車編組計劃模型

1.1參數定義

V為節點站集合，代表實際路網中的技術站，i∈V。A為直達去向集合，對于N個車站構成的網絡，最多有N×(N-1)個去向，(i,j)∈A。Y(i,j)為經由i站到達j站車流的發送站集合，s∈Y(i,j)。E(i,j)為從i站發出途中經由j站車流的到達站集合，s∈E(i,j)。D(i,j)為車流i→j途中經過的技術站集合(不含i站和j站)，s∈D(i,j)。Ci為技術站i的集結參數。mij為技術站i至技術站j去向的平均列車編成輛數。vij為車流i→j的大小。τk為車流在k站改編產生的相對延誤。CRk為k站可利用的改編能力。CTi為i站的有效調車股道數。fij為從i站發出、終到j站的車流量大小，中間變量。gij為i→j去向所吸引的車流強度，中間變量。

定義0-1決策變量為：

xij：i→j去向是否為直達去向，是為1，否為0，(i,j)∈A。

1.2模型假設

(1)模型僅研究技術站單組列車編組計劃的優化問題，且車流徑路已知。

(2)相鄰技術站間(開行直通或區段列車)已存在直達去向[6]。

1.3模型建立

(1)

(2)

(3)

(4)

(5)

(6)

(7)

xij∈{0,1}, ?i,j∈V,

(8)

(9)

其中，式(1)為目標函數，式(2)～(9)為約束條件。模型以技術站總的車小時消耗最小為目標，包括集結車小時消耗和改編車小時消耗兩部分。式(2)為從i站發出、終到j站的車流表達式，共包含兩部分車流：i站自身產生的終到j站的車流，以及在i站改編終到j站的車流。式(3)為車流改編方案唯一性約束，以車流i→j為例，其或直達送至j站，或在途中的某個技術站k進行第一次改編作業，只能選擇其中一種方案運送。式(4)為車流改編邏輯約束，當車流i→j在k站改編時，應確保直達去向i→k存在。式(5)為技術站改編能力限制約束，在k站改編的車流不得超出k站的改編能力。式(6)為直達去向車流強度的計算公式，以i→j去向為例，其吸引的車流既包括從i站發出終到j站的車流，也包括從i站發出至j站改編的車流。式(7)為調車線容車約束，技術站集結直達去向所占用的股道數不得超出該站可供集結占用的調車線數，當車流強度每增加200車需多占用一條股道[6]。式(8)、式(9)為變量邏輯約束。

2禁忌搜索算法

2.1算法概述

禁忌搜索算法(Tabu Search，TS)是最早由Glover在1986年提出的一種元啟發式算法，是對局部鄰域搜索算法的推廣[9]。TS算法通過設置禁忌表來禁忌已經歷的操作，并利用特赦準則來解禁一些優良狀態，可在一定程度上接受劣解，使其在搜索過程中能跳出局部最優解，從而實現全局優化。禁忌對象、禁忌長度、鄰域結構、評價函數和候選集的確定是禁忌搜索算法設計的核心，此外還包括特赦規則和終止規則的確定[10]。

2.2算法設計

2.2.1編碼及初始解生成

對N個點構成的路網，最多有O-D流N×(N-1)股。本文在進行解的編碼時，針對任一個O-D去向，采用1位整數表示這一去向的第一到站，可為終到站，也可為第一改編站。這樣，將所有O-D流的車流運送方案編碼為一個長度為N×(N-1)的一維數組，格式為：

s12s13… s1Ns21… s2N… sij… sN1… sN(N-1),

式中,sij表示O-D流i→j的第一到站。若sij=j，O-D流i→j被直達運至j站；若sij≠j，O-D流i→j要先隨i→sij去向直達列車運至sij站進行第一次改編作業，并在sij站與sij→j去向車流合并為一股車流。

2.2.2評價函數

評價函數是指用于選取候選解的一個公式，一般是將目標函數作為評價函數。通過分析模型可以發現，式(5)和式(7)為難約束，不能保證算法的每次迭代都滿足，因此，不能直接將目標函數用作評價函數。這里采用外點法構造罰函數，將評價函數公式由目標函數式(1)轉化為:

(10)

其中，κ1、κ2均為取值為正的懲罰系數。

2.2.3鄰域結構

Step1：判斷i→j去向是否開直達列車，若sij=j，i→j為直達去向，變更第一到站為改編站，轉Step2；否則，i→j去向在sij站改編，變更第一到站為j站或其他改編站，轉Step3。

2.2.4禁忌移動

若某個禁忌候選解的目標函數值優于當前最優解，則解禁此候選解為當前狀態和新的當前最優解。算法在連續50次最優車流運送方案不發生改變時終止運行。

3算例分析

為驗證算法的有效性，設計由8個技術站構成的算例路網如圖1所示。路網中技術站的相關參數取值如表1所示。各車站間車流量如表2所示。各支車流的走行徑路為最短路。

圖1　算例路網圖Fig.1　Railway network diagram of a numerical example

站名改編參數集結參數改編能力股道數13.59.86001524.110.54801034.311.7300644.111.1420853.511.8280563.511.5400874.210.85501284.311.24509

表2　車流OD數據

此算法已利用MATLAB 2012b編寫實現，并在CPU為雙核2.40 GHz、內存為4 GB的硬件配置的PC機上調試通過。其中參數設置如下：n=20，l=5，pm=0.1，κ1=150，κ2=200。算法在運行到第93代時收斂，求解時間為47 s，最優目標函數值為24 477.1車小時，迭代收斂曲線如圖2所示。共開行直達去向33個，其中非相鄰技術站間開行直達去向17個，非相鄰站間的直達列車開行情況如圖3所示。各支O-D車流的第一到達站如表3所示。

圖2　迭代收斂曲線圖Fig.2　 Iteration convergence curve diagram

圖3　非相鄰技術站間的直達列車開行情況Fig.3　Direct train connection services between non-adjacent technical service stations

站名123456781-224667821-335668312-477724323-663256677-676612775-787663456-882234227-

為了驗證算法求解性能的好壞，選擇適合求解非線性規劃的LINGO 11.0軟件求解模型，LINGO在運行2分54秒后，求得目標值為24 477.1的全局最優解，如圖4所示。對比禁忌搜索算法和LINGO內嵌算法的求解效果，在求得相同最優解的情況下，禁忌搜索算法的時間消耗更少，可快速、有效地求解技術站單組列車編組計劃方案。

圖4　LINGO求解結果Fig.4　LINGO result

4結語

列車編組計劃問題是鐵路運輸組織工作中重要且復雜的問題。本文以技術站單組列車編組計劃為研究對象，選擇較為典型的0-1規劃列車編組計劃模型，針對模型求解實質為優化各支技術站車流第一到站的特點，設計了適合問題特點的禁忌搜索算法，該算法可用來求解路網環境下的列車編組計劃問題。算例表明，禁忌搜索算法求解列車編組計劃問題時快速準確，能為車流組織人員提供可行的優選方案。

參考文獻：

[1]李映紅, 吳世貴, 彭其淵.貨物列車編組計劃網絡模型的建立及算法[J].西南交通大學學報, 2002, 37(1):68-71.

[2]陳崇雙,王慈光,薛鋒,等.貨物列車編組計劃國內外研究綜述[J].鐵道學報,2012,34(2):8-20.

[3]林伯梁, 朱松年.優化編組計劃的非線性0-1規劃模型及模擬退火算法[J].鐵道學報, 1994, 16(2): 61-66.

[4]許紅, 馬建軍, 龍昭, 等.技術站單組列車編組方案模型與計算方法的研究[J].鐵道學報, 2006, 28(3):12-17.

[5]耿令乾. 基于遠程改編策略的技術站車流組織優化模型研究[J].鐵道運輸與經濟, 2010, 32(10): 70-75.

[6]林柏梁, 田亞明, 王志美,等. 基于最遠站法則的列車編組計劃優化雙層規劃模型[J].中國鐵道科學, 2011, 32(5): 108-113.

[7]AHUJA R K, JHA K C, LIU J. Solving Real-life Railroad Blocking Problems [J].Interfaces, 2007, 37(5): 404-419.

[8]GORMAN M F. An application of genetic and tabu searches to the freight railroad operating plan problem [J].Annals of Operations Research,1998,78(3):51-69.

[9]邢文訓, 謝金星. 現代優化計算方法[M].北京：清華大學出版社,1999.

[10]GLOVER F, LAGUNA M. Tabu Search [M].Boston: Kluwer Academic Publishers, 1997.

DOI:10.3976/j.issn.1002-4026.2016.03.014

收稿日期：2016-01-05

作者簡介：張海艦(1986-)，男，助理工程師，研究方向為安全管理。

中圖分類號：U292.31

文獻標識碼：A

文章編號：1002-4026(2016)03-0081-06

Tabu search algorithm for the formation plan of single-group train at technical service station

Zhang Hai-jian1

(Anyang Train Operation Depot, Zhengzhou Railway Administration, Anyang 455000, China)

Abstract∶Train formation plan of technical stations is one of key issues for railway transportation schedule. The most popular algorithm is 0-1 program involving train flow recursion relation of train formation destination among the present domestic research on single train formation plan. The essential of such research is to optimize the first arrival station of wagon flows. We therefore devise a real number coded tabu search algorithm that can be applied to solving train formation plan of railway network. Computational cases indicate that it can rapidly and effectively solve formation plan of single-group train at technical service stations. Compared with LINGO software, it can find global optimum solution with only less time.

Key words∶ formation plan; technical through train; 0-1 program; tabu search algorithm