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

張海艦

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

?

【交通運輸】

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

張海艦

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

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

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

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

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

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

1.1參數(shù)定義

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

定義0-1決策變量為：

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

1.2模型假設

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

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

1.3模型建立

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

(9)

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

2禁忌搜索算法

2.1算法概述

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

2.2算法設計

2.2.1編碼及初始解生成

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

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站進行第一次改編作業(yè)，并在sij站與sij→j去向車流合并為一股車流。

2.2.2評價函數(shù)

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

(10)

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

2.2.3鄰域結構

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

2.2.4禁忌移動

若某個禁忌候選解的目標函數(shù)值優(yōu)于當前最優(yōu)解，則解禁此候選解為當前狀態(tài)和新的當前最優(yōu)解。算法在連續(xù)50次最優(yōu)車流運送方案不發(fā)生改變時終止運行。

3算例分析

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

圖1　算例路網(wǎng)圖Fig.1　Railway network diagram of a numerical example

站名改編參數(shù)集結參數(shù)改編能力股道數(shù)13.59.86001524.110.54801034.311.7300644.111.1420853.511.8280563.511.5400874.210.85501284.311.24509

表2　車流OD數(shù)據(jù)

此算法已利用MATLAB 2012b編寫實現(xiàn)，并在CPU為雙核2.40 GHz、內存為4 GB的硬件配置的PC機上調試通過。其中參數(shù)設置如下：n=20，l=5，pm=0.1，κ1=150，κ2=200。算法在運行到第93代時收斂，求解時間為47 s，最優(yōu)目標函數(shù)值為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-

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

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

4結語

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

參考文獻：

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

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

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

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

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

[6]林柏梁, 田亞明, 王志美,等. 基于最遠站法則的列車編組計劃優(yōu)化雙層規(guī)劃模型[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]邢文訓, 謝金星. 現(xiàn)代優(yōu)化計算方法[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