技术站单组列车编组计划的禁忌搜索算法研究

张海舰

(郑州铁路局安阳车务段，河南 安阳 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