基于阶段计划的取送车调车作业计划编制优化研究

郭垂江

(成都信息工程大学 物流学院，四川 成都 610103)

车站阶段计划是班计划分阶段3 h或4 h的工作安排，由车站调度员编制。取送调车作业计划是根据阶段计划安排取送车顺序和整个作业的起止时间，由调车领导人根据调车场内待送车辆和装卸地点待取车辆停留情况进行编制。

阶段计划编制过程中，本阶段所必须完成的取送车作业的车组及车数可在制定列车配流计划时确定，取送车调车作业计划确定本阶段的取送作业批次、顺序、每批作业的开始时间和延续时间。不同的取送作业批次划分、不同的批次开始作业时间及批次内不同的取送车顺序，将会影响配流计划的最终实现。

一批取送调车作业是指调车机车(以下简称调机)从调车场(车站)出发，往相关货物作业点进行取、送、调移作业后，返回调车场(车站)的技术作业过程。按照实际作业内容的不同，一批取送车作业可分为单一送车、单一取车、送取结合、送兼调移、取兼调移、送调取结合6种作业形式。相应地，具体的货物作业点作业有取车、送车、连送带取3种作业形式。双重货物作业车完成一次货物作业的平均货车停留时间比一次货物作业车短，车站应尽量利用本站卸空后的空车装车，以加速车辆周转，因此存在车组从卸车作业点调移至相应的装车作业点的调移作业。

针对树枝形货物作业点取送车作业问题，石红国等[1]认为树枝形专用线取送车问题是一个求解哈密尔顿最短回路问题，分别对专用线节点较少和节点较多的两种情况下近似求解问题进行了研究。黄向荣[2]同样将其转化为求哈密尔顿最短回路问题, 利用精确算法——最小生成树算法进行求解。雷友诚等[3]建立了大型企业树枝形专用线的取送车作业问题的数学模型，利用遗传蚁群算法(GACA)进行求解，并将其与标准蚁群算法(ACA)进行比较。李斌等[4]把取送车问题的顺序、时间和批次作为一个系统进行优化，建立适用于多种作业方式，考虑了调机的牵引能力和装卸区的容车能力约束的数学模型，并提出遗传蚁群算法求解该取送车优化问题。郭垂江等[5-8]将树枝形专用线取送车顺序确定问题转化为求解哈密尔顿最短回路问题，分别利用动态规划算法、C-W节约改进算法、破圈连接法、模拟退火算法求解最优解或满意解。

取送车系统是铁路车站调度系统中一个子系统，它与车站其他作业系统联系紧密，孤立地对该系统进行理论研究难以取得具有较高应用价值的成果。本文从整个车站作业计划编制系统角度研究取送车调车作业计划编制问题，以完成阶段内所有批次取送车作业所耗的时间最小为优化目标，考虑货物作业的车组的最迟返回车站时间约束、解体时刻约束、批次开始时刻约束、调机能力约束和调移作业所要求的调机访问优先权等约束，建立了基于阶段计划的取送车调车作业计划编制优化模型，运用改进的禁忌搜索算法确定满意的取送车作业顺序、批次划分及取送时间，研究成果有助于编制更加实用的取送车调车机车运用计划，为车站综合自动化系统的作业计划智能编制提供理论支持。

1 研究假设

由于铁路车站作业场景比较复杂，本文研究是在以下假设条件下进行的：

(1)车站所衔接的货物装卸地点呈树枝形分布。

(2)由1台调车机车负责车站的取送车作业。

(3)调车机车在各货物作业点(车站)间的走行时间已知。

(4)所有车组所接续的出发列车及编组开始时刻在阶段计划中已确定。

(5)所有车组解体到相应调车线的时刻已确定。

(6)各货物作业点在阶段内需取送的车组及车辆数在阶段计划中已确定。

2 符合说明

(1)参数符号

(2)变量符号

3 目标函数

每批调机取送车时间是指每批作业时，调机离开调车场(车站)起，至完成该批取送作业任务后返回调车场(车站)止所延续的时间，而调机取送车总时间为阶段内所有批次调机取送车时间之和。所有批次调机取送车总时间越少，意味着调机作业效率越高，在阶段内作业批次间有更多的时间间隔进行休整或进行其他调车活动，因此本文以调车机车完成阶段内所有批次取送调车作业任务的取送车作业总时间最小为优化目标。调机取送车作业总时间由调机在货物作业点(调车场或车站)间的走行时间和调机到达货物作业点时由于车辆未装卸完毕需等待的时间组成。优化目标为

(1)

4 约束条件

4.1 车流接束时间约束

因货物作业点呈树枝形分布，所以每批货物作业的车组取回时刻是相同的，不管车组集中出发还是分散出发，都需满足所有车组的最晚出发时刻，否则将会影响相应列车的正点出发。因此要求该批作业的取回时刻须不大于该批所有车组的编组开始时刻，即

(2)

4.2 可选择车组时间约束

一批作业可选择送往货物作业点的车组只能从送车前已经在调车场(车站)集结的车辆中选择。每批含有送车的取送车作业开始时刻须大于送车组的解体完毕时刻，即

(3)

4.3 批次开始时刻约束

一批取送车作业的开始时刻不能早于上一批次的取送车完毕调机返回调车场(车站)的时刻，第1批取送车作业开始时刻不能早于本阶段开始时刻，即

(4)

(5)

4.4 机车牵引重量约束

取送车作业受调机牵引能力的限制，每一批调车作业过程中调机所连挂的车辆数不能超过其最大牵引能力,即

(6)

4.5 调移作业优先权约束

假如阶段计划内取送车作业中存在调移作业，则调机必须首先访问卸车作业点取出空车，再送往相应的装车作业点进行装车，所以存在调机访问这2个作业点先后顺序的约束，即

(7)

(8)

(9)

5 求解方法

求解基于阶段计划的取送车调车作业计划编制优化模型的重点和难点在于寻找最优的取送作业的作业顺序及批次。将阶段计划内所有作业涉及的车组视为一个整体时，取送车作业的完整方案包含1个取送车作业顺序方案和1个取送车作业批次划分方案。显然，货物作业点数为n的取送车作业问题对应n!个取送车作业顺序方案，1个取送车作业顺序方案又对应2n-1个取送车作业批次方案。因此，货物作业点数为n的取送车作业问题实际上拥有n!×2n-1个完整的取送车作业方案(无论方案是否可行)。另一方面，哈密尔顿图最短回路问题是NP问题，树枝形货物作业点取送车作业方案问题是具有特殊形式的哈密尔顿图最短回路问题，按照问题的归约关系，取送车作业方案优化问题也应是NP问题，因此必须采用高效的启发式算法求解，以在可接受的时间内得到满意解或最优解[9-11]。

本文采用以下思路进行求解：首先按照初始解的构造规则产生满足调移作业货物作业点优先关系的初始取送车顺序和批次划分；然后应用禁忌搜索算法和文献[6]所述的启发式算法对取送车顺序和批次划分进行循环优化，得到满意的取送车顺序、批次划分和开始时刻[12-18]。

(1)禁忌搜索算法求解思路

利用禁忌搜索算法求解树枝形货物作业点基于阶段计划的取送车调车作业计划编制优化模型的实现步骤为:

Step1选取一个初始解Snow并计算相应的评价值f(Snow)；令禁忌表H=Ø。

Step2若满足终止准则，转Step 4；否则，在Snow的邻域N(Snow)中选出满足禁忌要求的候选集，转Step 3。

Step4输出计算结果，停止。

各车组最早可能取送时刻si为

(10)

(2)初始解的构造

首先将一日时间转化为[0,1 440]中的数字，按照以下规则产生模型的初始解：

① 根据式(10)计算得到各项取送车作业的si值，按si值从小到大对阶段计划所涉及的货物作业点进行排序，若几个货物作业点的si值相同，就按照车组的数量的从大到小进行排序。

② 调移作业点对遵循卸车作业点未访问前装车作业点不访问的原则进行排序。

这样就得到了一个能完成阶段计划规定的取送车作业且满足式(7)的货物作业点全排列，并将每项取送作业单独设定为1个取送车作业批次，即初始批次数m=n，这样，可得到一个满足式(7)的初始解。

(3)邻域的构造方法

可随机采用以下规则构造邻域解：

① 调移作业的卸车点、装车点前后跨批次移动

如图1(a)所示，阶段计划要求将作业点的车辆调移至作业点。保持装车点的所在批次和位置不变，在目前解中可将卸车点的位置插入到装车点所在位置前任何位置。如位置插入到v8前，则随机将v2、v0一起插入到v8之前得图1(b)所示的解；随机将v2、v0一起插入到v8之后得图1(c)所示的解。再保持卸车点v2的所在位置和批次不变，在目前解中可将作业点v4插入到卸车点v2所在位置后的任何位置，图2(a) 表示将作业点v4插入到v9前，则随机将v4、v0一起插入到v9之前得图2(b)所示的解，随机将v4、v0一起插入到v9之后得图2(c)所示的解。最后运用文献[6]的启发式算法对每个批次内的货物作业点顺序进行优化，从而得到1个新的邻域解。

图1 卸车点位置前后移动图

图2 装车点位置前后移动图

② 非调移作业的货物作业点前后跨批次移动

如图3(a)所示，货物作业点v6为非调移作业的货物作业点，可将其移至其他任何一个位置，如将货物作业点v6插入作业点v10前，则将v6、v0一起插入到v10之前得如图3(b)所示的解，将v6、v0一起插入到v10之后得图3(c)所示的解。最后运用文献[6]的启发式算法对每个批次内的货物作业点顺序进行优化，即可得到1个新的邻域解。

图3 非调移货物作业点位置前后移动

③ 2-交换

如图4所示，v6和v7为任意2个货物作业点，若点v6和v7为非调移作业的货物作业点，可交换v6和v7的位置和所在批次，再运用文献[6]的启发式算法对每个批次内的货物作业点顺序进行优化，即可得到1个新的邻域解。

图4 解2-交换图

解的评价可把约束条件式(6)转化成惩罚函数，再把目标函数式与惩罚函数累积起来作为解的评价函数f(S)，即

(11)

式中：M为足够大的正数。

(4)迭代终止准则

迭代终止准则采用最大迭代步数Lmax，当迭代步数达到Lmax时，输出满意的取送车顺序、批次划分和起止时间等。

(5)禁忌对象的确定

禁忌对象是指禁忌表中被禁的局部最优解，本文将每次迭代得到的最好解作为禁忌对象放入禁忌表中。

(6)禁忌长度的确定

禁忌长度是指被禁对象不允许被选取的迭代步数，本文取禁忌长度为一个常数。

(7)候选集合的确定

本文将从当前解的邻域中随机选择若干个邻居作为候选集合。

6 算例分析

某铁路技术站货物作业点布置情况如图5所示，w1,w2,…,w9为道岔岔心；v0为调车场；v1,…,v10为货物作业点，数字为各点(调车场、道岔岔心、作业点)间的机车走行时间。设tvi,vi′=0，这样可保证连送带取货物作业不另产生调机走行时间。

图5 某铁路技术站货物作业点布置示意图

某工作日0:00至03:00间阶段计划内取送车作业的货物作业点、车数、解体完毕时刻、装卸完毕时刻、编组开始时刻等数据见表1，需进行的调移任务为：货物作业点v3需调移3辆至v6，货物作业点v5需调移2辆至v7。调机最大牵引辆数为25辆。制定本阶段内合理的取送车作业的顺序、批次及其起止时间。

表1 某工作日00:00至03:00间取送调车作业内容

表2 满意解的时间指标

(1)不同的禁忌长度条件下解的比较

保持其他参数值不变，采用不同的禁忌长度对以上算例进行多次测试，得到的算法平均运行时间和调机总作业时间比较见表3。

表3 不同的禁忌长度条件下解的比较

由表3可知，不同的禁忌长度参数设置对运行时间影响不大。总体来说禁忌长度越长，所花费的运行时间越长，可能是搜索可行解难度增大的原因。不同的禁忌长度参数设置对得到的满意解质量有一定影响，禁忌长度越长，所得到的解质量越高，但禁忌长度设置为比25更大的数值时，最终解的质量提升不大。

(2)不同的最大迭代步数条件下解的比较

保持其他参数值不变，采用不同的最大迭代步数对算例进行多次测试，得到的算法平均运行时间和调机总作业时间比较见表4。

表4 不同的最大迭代步数条件下解的比较

由表4可知，所设置的最大迭代步数越大，所得到的解质量也越高，但算法运行时间越长。设置45步以上的迭代步数对最终解的质量影响不大，可认为算法已基本收敛。

在铁路实际生产中，调机阶段内所承担取送调车任务的作业点数量一般不是很大，所以以上案例具有一定的代表性。通过对以上案例进行测试，计算时间也可控制在合理范围之内，因此本文所建立的模型和设计的算法是可行和有效的。

7 结论

本文针对阶段内取送车调车作业计划编制问题，以调车机车总走行时间最小为优化目标，综合考虑了每批作业最晚必须返回车站时刻、车组解体完毕时刻、批次开始时刻、调机最大编挂能力和调移作业所要求的调机访问优先权约束，全面地描述了铁路车站树枝形货物作业点的取送车方案问题实质，建立了基于阶段计划的树枝形货物作业点取送车调车作业计划的优化模型，以禁忌搜索算法为求解主框架进行求解。案例验证表明，所建立的模型和设计的算法是可行的和有效的，遵循结合阶段计划编制取送车调车作业计划的思路能使阶段计划更有应用价值。下一步将考虑不同货物作业点布置形式、装卸点作业容量、多取送调车机车等作业场景进行深入研究，以适应现场复杂的设备特点和作业组织形式。