技術(shù)站單組列車(chē)編組計(jì)劃的禁忌搜索算法研究

張海艦

(鄭州鐵路局安陽(yáng)車(chē)務(wù)段，河南 安陽(yáng) 455000)

?

【交通運(yùn)輸】

技術(shù)站單組列車(chē)編組計(jì)劃的禁忌搜索算法研究

張海艦

(鄭州鐵路局安陽(yáng)車(chē)務(wù)段，河南 安陽(yáng) 455000)

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

關(guān)鍵詞：編組計(jì)劃；技術(shù)直達(dá)列車(chē)；0-1規(guī)劃；禁忌搜索算法

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

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

1技術(shù)站單組列車(chē)編組計(jì)劃模型

1.1參數(shù)定義

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

定義0-1決策變量為：

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

1.2模型假設(shè)

(1)模型僅研究技術(shù)站單組列車(chē)編組計(jì)劃的優(yōu)化問(wèn)題，且車(chē)流徑路已知。

(2)相鄰技術(shù)站間(開(kāi)行直通或區(qū)段列車(chē))已存在直達(dá)去向[6]。

1.3模型建立

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

(9)

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

2禁忌搜索算法

2.1算法概述

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

2.2算法設(shè)計(jì)

2.2.1編碼及初始解生成

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

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

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

2.2.2評(píng)價(jià)函數(shù)

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

(10)

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

2.2.3鄰域結(jié)構(gòu)

Step1：判斷i→j去向是否開(kāi)直達(dá)列車(chē)，若sij=j，i→j為直達(dá)去向，變更第一到站為改編站，轉(zhuǎn)Step2；否則，i→j去向在sij站改編，變更第一到站為j站或其他改編站，轉(zhuǎn)Step3。

2.2.4禁忌移動(dòng)

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

3算例分析

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

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

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

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

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

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

圖3　非相鄰技術(shù)站間的直達(dá)列車(chē)開(kāi)行情況Fig.3　Direct train connection services between non-adjacent technical service stations

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

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

圖4　LINGO求解結(jié)果Fig.4　LINGO result

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2]陳崇雙,王慈光,薛鋒,等.貨物列車(chē)編組計(jì)劃國(guó)內(nèi)外研究綜述[J].鐵道學(xué)報(bào),2012,34(2):8-20.

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

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

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

[6]林柏梁, 田亞明, 王志美,等. 基于最遠(yuǎn)站法則的列車(chē)編組計(jì)劃優(yōu)化雙層規(guī)劃模型[J].中國(guó)鐵道科學(xué), 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]邢文訓(xùn), 謝金星. 現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社,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

作者簡(jiǎn)介：張海艦(1986-)，男，助理工程師，研究方向?yàn)榘踩芾怼?/p>

中圖分類(lèi)號(hào)：U292.31

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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