面向调移车辆数优化的摘挂列车调车作业计划编制方法

2020-04-16张博健彭其渊鲁工圆

铁道学报 2020年3期

张博健，彭其渊，李力，鲁工圆

(1. 西南交通大学交通运输与物流学院，四川成都 610031；2. 西南交通大学综合交通运输智能化国家地方联合工程实验室，四川成都 610031)

调车作业计划是规定车辆如何调移及其作业程序的具体行动计划[1]。按站顺编组摘挂列车是一类较为复杂且重要的车站日常调车作业，调车作业计划质量对技术站及中间站的工作效率有重要影响。

许多学者对此展开了深入研究，为保证按站顺编组摘挂列车调车作业计划质量，文献[2]提出了“落表法”，其特点是所有车辆只进行一次溜放，并使占用的调车线数达到最少。文献[3]提出了“统筹对口调车法”理论，将编组调车过程描述为一系列连续的对口过程，该方法可使选编调车的连挂钩数达到最优。文献[4]提出了“分析计算法”，该方法使用换算溜放钩数评估整个调车方案的调车钩数和调动车数，并据此对方案进行选优。文献[5]提出了“消逆法”理论，在可用调车线数量受限和可变的条件下使牵推钩数最优。文献[6]针对“消逆法”连挂钩数较多的问题进行优化。文献[6-7]针对“统筹对口调车法”牵推钩数较多的问题进行优化。文献[8]将车组下落问题抽象为排序问题，提出一种基于排序二叉树的调车作业计划编制方法。文献[9]基于基数排序算法对调车作业计划进行编制。文献[10]针对可用调车线数量受限情况下的编组调车问题，设计了“位串法”。

随着高速铁路的迅猛发展，动车运用成为制约通过能力的一个重要因素。动车所调车作业计划的优化编制等问题也成为了研究的热点，为摘挂列车调车作业计划的优化提供了新的思路。文献[11]以最小化调车钩总数为目标，构建动车所调车作业计划整数规划模型，设计了粒子群算法进行求解。文献[12]以动车运用所内动车组总延误时间最小为目标建立优化模型，并设计微进化算法进行求解。

综上所述，既有文献中调车作业计划编制的目标多以连挂钩数最少、调车钩数最优(连挂钩与溜放钩的加权调车钩数最少)为目标，而对每一调车钩执行过程中调移的车辆数多少考虑较少。调车钩执行过程中，每钩调移车辆数的变化直接导致每一钩调车机车带动重量的不同，一方面会影响调车机车启动、制动效率，另一方面也影响着调车机车的能源消耗，综合两方面因素来看，更少调移车辆数的调车作业计划将意味着能够以更少的能源消耗、更快的速度以及更少的作业量完成调车作业过程，对于调车工作效率的提高有着重要意义。

基于上述思路，本文提出了在调车钩数最优的基础上，对调移车辆数进行优化的摘挂列车调车作业计划编制方法。首先，建立了面向调移车辆数优化的调车作业计划编制0-1线性规划模型；其次，设计了基于消逆规则启发式算法对模型进行求解；最后通过算例对模型及算法的有效性进行验证，归纳了相关结论。

1 问题描述

1.1 问题相关定义

按站顺编组摘挂列车调车作业计划编制问题可描述为：对多个任意编组顺序的待解编车组，通过连挂或摘解作业，确定一个将其改编为编组符合站顺要求的调车作业计划。

为了提高调车作业计划的编制质量，应使摘挂列车编组过程中的调车作业量最少，在既有文献中多以调车钩数多少作为调车作业计划质量的评价标准[3,5,8-9]，其中以连挂钩数最少为目标最为常见[3,8-9]。在保证调车钩数最优并以调移车辆数最少为编制目标的情况下，调车作业计划编制的问题描述并无变化，但需引入如下定义：

(1) 车辆调移

调车机车在执行调车作业的各行程中车辆移动的过程，机车每连挂一个车辆即产生一个连挂车辆调移，每溜放一个车辆则产生一个溜放车辆调移，统称为车辆调移。

(2) 调车钩调移车辆数

单一调车钩移动的车辆数量。如果某钩作业为连挂作业，则其移动车辆数称为连挂钩调移车辆数，由连挂钩推送行程中移动的车辆数和连挂钩回拉行程中的移动车辆数组成；若为溜放作业，则为溜放钩调移车辆数，由溜放钩推送行程中移动的车辆数和回拉行程中移动的车辆数组成。

(3) 调车作业计划调移车辆数

调车作业计划各调车钩的调移车辆数总和。一个调车作业计划所有连挂钩移动的车辆数称为连挂作业调移车辆总数，所有溜放钩移动的车辆数称为溜放作业调移车辆总数。

车辆调移及调移车辆数的定义目的在于对同一调车钩内对各个车辆的操作进行微观描述。应注意的是，车辆调移发生在调车机车的每一次行程中，一次行程包含多个车辆调移，一个调车钩可以包含多个行程，其调移车辆数统计时应涵盖每一次行程中的调移车辆个数。一个连挂钩的调移车辆数，应是图1(a)推送行程的2个车辆调移与图1(b)回拉行程4个车辆调移之和，即该连挂调车钩产生了6个车辆调移。

1.2 问题假设

为便于模型建立，本文研究的按站顺编组的摘挂列车调车作业计划编制问题基于以下假设：

(1) 任意一列车列的调车作业由一台调机完成，调车作业在一端咽喉进行，且调车过程中不允许出现中断。

(2) 调机的牵引性能、牵出线的存车能力、调车线的存车能力不受到限制。

2 模型构建

2.1 符号说明

为建立问题模型，定义参数及集合如下：

K为车辆调移作业编号集合，K={1,2,…,k,…,|K|，k∈N+}，按车辆调移先后顺序进行排序，同一调车钩行程产生多个车辆调移时，调机连挂车列末位车辆的调移作业先于其他车辆调移。k为车辆调移作业次序索引，|K|为调车作业过程最后一次车辆调移作业的编号。

D为按站顺排列的车辆编组去向集合，D={1,2,…,d,…,|D|，d∈N+}。d为编组去向索引，1为距离本站最远的车辆去向，|D|为距离本站最近的车辆去向。

T为调车场调车线集合，t为调车线编号。

O为机带车列中车辆位置集合O={1,2,…,o,…,|O|，o∈N+}，按照距离调机远近进行排序。o为机带车列中车辆位置索引。将机带车列中距离调机最近的车辆位置称为机带车列首位置，首位置车辆称为机带车列首位车辆；将机带车列中距离调机最远的车辆位置称为末位置，末位置车辆称为机带车列末位车辆。

P为调车线上停放的车列中车辆位置集合，P={1,2,…,p,…,|P|，p∈N+}，按照距离牵出线的远近进行排序。p为调车线上车辆位置索引。将各调车线上停放车列中距离牵出线最远的车辆位置称为停放车列首位置，首位置车辆称为停放车列首位车辆；将各调车线上停放车列中距离牵出线最近的车辆位置称为停放车列末位置，末位置车辆称为停放车列末位车辆。

机带车列及停放车列中车辆位置等参数示意见图2。

建模过程以每个车辆的调移为单位建立决策变量，主要决策变量如下:

(1) 车辆分布状态变量

(2) 车辆连挂调移作业相关变量

(3) 车辆溜放调移作业相关变量

2.2 目标函数

基于上述决策变量定义，可建立调车钩数最优前提下面向调移车辆数优化模型的目标函数

minZ=α×yc+β×yh+γ×xc+δ×xh

( 1 )

式中：α为每一连挂调移车辆数的权重；yc为调车作业计划连挂钩调移车辆总数；β为每一溜放调移车辆数的权重；yh调车作业计划溜放钩调移车辆总数；γ为每一连挂钩的权重；xc为实际连挂钩总数；δ为每一溜放钩的权重；xh为实际溜放钩总数。

为保证基于调车钩数最优讨论调移车辆数优化，可以调整α、β、γ、δ的取值，使调车钩的权重γ、δ远远大于调移车辆数的权重α、β。

( 2 )

( 3 )

xc和xh的计算为

( 4 )

( 5 )

上述公式含有非线性项，其线性化方法将在后文介绍。

2.3 约束条件

为使用所定义决策变量描述调车作业计划过程，引入如下约束条件：

(1) 车辆调移作业执行约束

当每一车辆调移作业(连挂或溜放)执行时，将导致机带车列的末位车辆发生变化，对应的其中一条调车线上末位车辆也会发生变化。该类约束可表示为

∀k,k+1∈Ko∈Od∈D

( 6 )

∀k,k+1∈Kt∈Tp∈Pd∈D

( 7 )

(2) 调车钩作业车辆守恒约束

车辆调移作业执行时，机带车列的车辆变化会导致调车场内车辆的相应变化为

( 8 )

( 9 )

模型规定调机每次只能连挂或溜放一辆车，约束为

(10)

(11)

(3) 溜放车辆调移作业操作车辆数约束

溜放车辆调移作业执行时，调机溜放调移机带车列末位一个车辆，同时该车辆溜放进调车场后只能溜放至某条调车线停靠车列的末位。该类约束可表示为

∀k∈Ko,o+1∈O

(12)

∀k∈Kt∈Tp,p+1∈P

(13)

(4) 连挂车辆调移作业操作车辆数约束

连挂车辆调移作业执行时，调机仅从调车场内某条调车线上的车列末位挂走一个车辆，同时该车辆只能连挂至机带车列的末位。该类约束可以表示为

∀k∈Ko,o+1∈O

(14)

∀k∈Kt∈Tp,p+1∈P

(15)

(5) 容车能力约束

机带车列与每一条调车线的每个位置最多停放一个车辆。该类约束可表示为

(16)

(17)

∀k∈Kt∈Tp∈P

(18)

∀k∈Kt∈Tp∈P

(19)

(6) 车辆调移作业选择与顺序约束

每一个车辆调移最多只能执行连挂车辆调移作业与溜放车辆调移作业中的一个，该约束可表示为

(20)

(21)

式(20)保证第k钩只能选择连挂车辆调移作业与溜放车辆调移作业其中的一个，或者两者都不选，式(21)保证车辆调移作业从编号1开始逐一执行。

(7) 车辆初始状态及目标顺序约束

调车作业开始前，机带车列及各调车线停放车列中车辆位置及去向为车辆初始状态为

(22)

(23)

调车作业计划应在车辆初始状态的基础上进行编制，调车作业在车辆达到目标顺序时停止。

∀o,o+1∈O

(24)

(8) 非线性项处理

∀k-1k∈Kt∈T

(25)

(26)

(27)

因此，式( 2 )可被式(27)线性化的表示出来。同理，式( 3 )可以线性化的表示为

∀k-1k∈Kt∈T

(28)

(29)

(30)

剩余的绝对值项可进一步线性化，并可在商业求解器中方便处理，在此不再赘述。

3 调车作业计划模型的求解算法

本文所建立模型为0-1线性规划模型，可使用商业求解器求解。当问题涉及的车辆数、调车线数、去向数等规模变大时，问题规模将大大增加，使得求解器在短时间内很难求得最优解。本文根据模型中连挂钩与溜放钩决策变量为0-1变量的特点，设计了启发式规则下的分支定界算法。在介绍算法之前，首先明确“逆序”概念及其计算方法。

3.1 逆序计算方法

逆序是指待编车列中的相对车位(车辆位置)顺序与目标车位顺序相反的状态，逆序数是指车列中逆序数量的总和。逆序数的大小代表着待编车列车位顺序与目标车位顺序的偏离程度，逆序数越大，待编车列中存在逆序的车辆就越多，即与目标车位顺序相差越远。当逆序数的值为0时，待编车列中不存在逆序车辆，即待编车列达到目标顺序。

随着调车作业过程中车辆的调移，待编车列中逆序及其数量不断发生变化，调车作业过程中待编车列逆序数的计算方法如下。

(1) 机带车列总逆序nl计算方法

(31)

(32)

式(32)计算机带车列中任意两车的位置顺序关系并加和。

(2) 调车线停放车列总逆序数ns计算方法

(33)

(34)

式(34)计算每条调车线上任意两车的位置顺序关系并加和。

(3) 逆序总数计算方法

n=nl+ns

(35)

式中：n为机带车列与调车线车列的总逆序。

基于逆序定义，进一步设计启发式算法对调车作业计划的编制问题进行求解。

3.2 基于消逆规则的分支定界算法

本文使用“消逆法”中的消逆思想(调车作业过程中，待编车列的逆序总数逐渐下降)，设计了具有“消逆规则”的分支定界算法对调车作业计划进行进一步优化，下面对算法节点、分支过程以及算法中所设计的启发式规则进行介绍。

(1) 算法节点及分支过程

(2) 消逆规则

根据节点定义，算法中每个节点均对应一个车辆调移作业；根据节点分支过程，算法中每个节点均由其父节点进行分支得到，并可继续分支得到其子节点；根据3.1节中逆序的计算方法，每个节点都能够计算出该节点的逆序总数。

本文使用的“消逆规则”描述为：进行溜放分支得到的节点逆序总数不能大于其父节点的逆序总数，也即是每个节点进行溜放分支得到的子节点逆序总数不能大于该节点的逆序总数，对于违背以上规则的节点及分支进行剪支。因此，“消逆规则”为算法中的剪支规则，从而保证随着算法分支的进行，节点逆序总数逐渐减少，直至为0。

(3) 逆序最速下降法

本文使用“逆序最速下降法”求解初始上界。逆序最速下降法是指：在求解初始上界时，算法总是优先选择逆序总数减少最多的节点进行分支，直至求解得到一个可行解。算法将该可行解作为问题的初始上界。虽然逆序最速下降法不能保证得到的调车作业计划质量，但可以快速的求解初始上界，提高算法效率。

算法根据待编车列的初始状态开始分支，并以逆序、车辆调移作业次数(调车钩数)、调移车辆数3方面指标作为启发式剪支规则进行剪支、迭代与优化，最终获得调车作业计划。

算法中符号定义见表1。

表1 分支定界算法中的符号定义

算法步骤为：

Step1初始化。输入机带车列以及各调车线上停放的车列中车辆的初始位置及去向、可使用的调车线数量、设置权重α、β、γ、δ的比值。生成根节点，将根节点放入集合Cn中，计算当前待编车列的初始逆序n，以逆序最速下降法计算调车作业计划初始解，并设置当前最优解x*为该初始解，当前上界为UB*，转Step2。

Step4剪支。删除按当前节点，转Step3。

Step5更新当前最优解x*；更新当前最优上界UB*；根据父节点信息生成当前最优调车作业计划；将该节点标记为已分支，转Step3。

Step6找到可行节点。将当前节点加入Cn，转Step3。

4 算例分析

为验证所提出的面向调移车辆数优化的调车作业计划求解方法，本文采用了4组算例实验：(1)模型有效性实验，使用求解器进行模型求解并验证其效果；(2)分支定界算法与求解器的求解效果对比实验，包括求解质量、效率的对比等；(3)分支定界算法与统筹对口法的求解质量对比实验，分析考虑调移车辆数时其求解质量与经典算法的差异；(4)权重取值对算法求解结果影响实验。在本文算例实验中，初始待编车列停放在调车场内，调车机车在右端作业，车列编成后距调车机车最远的车组到站为“1”，从远到近依次编为2，3,…。0-1线性规划模型求解器使用了商业求解器CPLEX，分支定界算法使用C#实现，问题求解实验均在CPU为Inter Core i7 3.4 GHz的个人计算机上执行。

4.1 模型有效性实验

为验证模型有效性，本实验在CPLEX求解器中，使用3种权重取值进行小规模调车作业计划实验，见表2，实验a1以连挂钩最少为目标，实验a2以调车钩数最优为目标；实验a3以基于调车钩数最优的调移车辆数优化为目标。基于文献[13]中关于连挂钩的钩分约为溜放钩的3～5倍的统计，本文将连挂作业与溜放作业的取值设为α∶β=γ∶δ=4∶1。为体现基于调车钩数最优的调移车辆数优化，将调车钩与调移车辆的权重比值设为γ∶α=δ∶β=100∶1。因此本文算例中当四个权重取值不为0时，分别设置为α=4，β=1，γ=400，δ=100，以保证：(1)保证连挂钩和溜放钩数的决定性作用；(2)能够在钩数优化的基础上进行调移车辆数优化；(3)体现连挂钩与溜放钩、连挂调移车辆数与溜放调移车辆数的关系。在各表中分别列出了在不同算例中的权重取值。在给定调车线数量的场景下，针对5个待编车列进行了求解实验，计算结果见表2。

表2 CPLEX计算结果统计

如表2所示，模型能够求解不同权重设置下的调车作业计划。在不同权重设置下，能够求解得到连挂钩最少(实验a1)、调车钩数最优(实验a2)、基于调车钩最优的调移车辆数最少(实验a3)目标下的不同调车作业计划，且能够适应不同调车线数量的问题，从求解结果上来看，模型是可行与有效的。在实验5中CPLEX未求得最优解，其原因在于随着问题规模的扩大、变量规模加大导致解空间大幅增加，使得求解器无法在给定时间内找到最优解。

实验4a中不同求解目标函数下的具体调车作业计划见表3，由对比分析得：(1)连挂钩数最少目标下的调车作业计划只能使得连挂钩数最少，并不能达到对溜放钩数量进行优化的效果；(2)调车钩数最优目标下的调车作业计划可以保证调车钩数最优，但不能达到调移车辆数的优化效果。(3)基于调车钩最优的调移车辆数最少目标下调车作业计划一方面保证了调车钩数的质量，另一方面能够对调移车辆数进行优化。由此可以看出，调车钩数最优的调车作业方案往往并不唯一，对调移车辆数进行优化可以进一步提高计划的编制质量。

表3 不同求解目标函数下算例4a的具体调车作业计划

4.2 分支定界算法与求解器的求解效果对比实验

本实验以基于调车钩数最优的调移车辆数优化为目标，通过求解实验比较分支定界算法与求解器的求解效果。实验中采用了与4.1节中实验a3相同的权重设置，具体实验参数设置及结果见表4，包括连挂钩数、溜放钩数、连挂作业调移车辆数、溜放调移作业车辆数、求解时间等。

表4 分支定界算法与求解器的问题求解质量与效率对比

在基于消逆规则的分支定界算法与求解器的算例实验中，从解的质量来看，在小规模算例(编号1～4)中算法与CPLEX所得出的调车作业计划的连挂钩、溜放钩相同，调移车辆数也无区别，两者均找到了问题最优解；在算例编号5中，CPLEX未在给定求解时间内找到最优解，分支定界算法则很快找到了高质量的解；在算例编号6中CPLEX在给定时间内没有找到可行解，而分支定界算法则找到了连挂钩5钩，溜放钩9钩，连挂作业调移车辆数38辆，溜放作业调移车辆数70辆的解。

上述实验表明，本文所提出的基于消逆规则的分支定界算法能够在比求解器更短的时间求解出具有类似质量的调车作业计划。

4.3 分支定界算法与统筹对口法求解质量对比实验

统筹对口法是常用的调车作业计划编制方法，基于开口位置的决策在表格上采用“下落”的方法找到连挂钩数最少的调车作业计划，统筹对口法的优势在于可以使调车作业方案的连挂钩数达到最少，但当存在有多个连挂钩数均为最少的调车作业方案时，统筹对口法在对溜放钩数进行优化并不方便，且在调移车辆数计算方面没有考虑。本实验在4条调车线的场景下，编制初始顺序为“1543253213”、目标顺序为“1122333455”的调车作业计划，实验c1以连挂钩最少为目标，c2以调车钩数最优为目标，实验c3以基于调车钩数最优的调移车辆数优化为目标。采用了统筹对口法与本文所提出分支定界法两种方法进行求解，权重设置与上文中实验一致，求解结果见表5。

表5 统筹对口法和分支定界算法求解算例6的结果

对于该算例统筹对口法可求出56个调车作业方案，表5中实验c1列出了其连挂钩最少(5钩)的方案之一，但该方案并非溜放钩数最少的方案，要获得溜放钩最少方案需将56种可行方案计算出后再逐一比较。在以调车钩数最优为目标的实验c2中，消逆规则下的分支定界算法找到了与统筹对口法相比具有相同连挂钩数且溜放钩数更少(9钩)的调车作业方案；在进一步对调移车辆数进行优化的实验c3中，算法求解得到连挂钩数和溜放钩数与实验c2相同，但调移车辆数更少的调车作业方案，实验c3求解方案与统筹对口法实验c1相比，总调移车辆数下降了20.6%，其中连挂调移车辆数减少了17.4%，溜放调移车辆数降低了22.2%；与实验c2相比，总调移车辆数下降了10.0%，其中连挂调移车辆数减少了11.6%，溜放调移车辆数降低了9.1%。实验结果说明，算法的求解结果能够在保证连挂钩数最少的同时，对溜放钩数进行优化，并且可进一步对调移车辆数进行优化。

4.4 不同权重取值对求解结果影响实验

本文设计了4组对比实验对模型目标函数中权重取值对算法求解结果的影响进行分析，见表6。实验组①为连挂作业调移车辆数权重α变化下的算例实验，实验组②中改变连挂钩及溜放钩权重γ与δ进行实验，实验组③在降低连挂作业调移车辆数权重α条件下，改变连挂钩及溜放钩权重γ与δ进行实验，实验组④进一步降低连挂作业调移车辆数权重α，改变连挂钩及溜放钩权重γ与δ进行实验。

表6 不同权重系数取值下分支定界算法的求解结果

实验组①中实验d1与实验组②中实验d4～d7的结果表明，随着调车钩权重的降低，调移车辆数较少的调车作业方案质量逐渐上升，表明调车钩与调移车辆数之间的权重比值对算法求解结果存在影响；实验组③中实验d8～d11与实验组④中实验d12～d15的结果表明，连挂作业调移车辆数与溜放作业调移车辆数间的权重比值对算法求解结果存在影响。

从上述实验的整体规律上看，可总结出如下结论：(1)调移车辆数最小的方案不一定调车钩最少，亦即：存在调车钩数更多反而调移车辆数更小的调车作业方案；(2)当溜放调移车辆数权重β的比重增大时，算法倾向于找出溜放调移车辆数更少的方案，此时可理解为不使用溜放作业进行平面调车作业的场景。四个权重值在调车作业计划编制中的变化对求解结果存在较大影响，其最优取值对于现场调车作业计划编制具有重要意义，需要配合实际作业过程及需求进行进一步深入分析，这也是本文后续研究工作的重点之一。