王 烁，何世伟，黎浩东，申永生

（北京交通大学 交通运输学院，北京 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)

责任编辑：冯姗姗