铁路集装箱中心站多轨道吊柔性协同调度优化

周勇，张杰，钟祾充，李文锋，王国栋

(1.武汉理工大学，交通与物流工程学院，武汉430063；2.辽宁港口集团有限公司，专业能力中心，辽宁大连116001)

0 引言

铁路集装箱中心站(简称“中心站”)是集装箱多式联运的重要节点，中心站轨道吊承担着进出站列车的绝大部分装卸作业，其运作效率对整个多式联运系统的作业效率有着重要影响。多轨道吊协同调度主要指根据装卸调度模式和作业规则确定轨道吊的装卸作业序列，使轨道吊的总完工时间最小，提高铁路中心站的生产运营效率。

国内外学者针对铁路中心站轨道吊协同装卸调度(Rail Mounted Gantry Crane Collaborative Scheduling，RMGCS)问题做了诸多研究，根据轨道吊作业区域的限定，可以将其装卸调度模式分为固定范围和柔性范围。固定范围装卸调度模式研究方面：王力等[1]通过划分轨道吊的作业区域避免多轨道吊之间的作业冲突；HE等[2]将固定范围内轨道吊调度问题转换成路径规划问题以及软时间窗约束问题；KRESS等[3]将多轨道吊的调度优化问题分解为集装箱任务分配问题和轨道吊作业区域动态划分问题；陈雷雷等[4]建立了固定范围模式下单轨道吊多类型任务复合作业下的整数规划调度模型；OTTO等[5]将多轨道吊调度问题分解为单轨道吊的作业序列规划问题。柔性范围装卸调度模式研究方面：刘勇等[6]将中心站轨道吊配置问题划分为轨道吊柔性调度问题和数量优化配置问题，设计了基于使用权分配的遗传算法进行求解；王力[7]建立了考虑多轨道吊间非交叉和安全距离约束的柔性范围装卸混合调度优化模型，使用遗传算法求解模型并和固定装卸范围下的调度模型进行对比；常祎妹等[8]在建立铁水联运混合整数规划模型中考虑了多龙门吊间的干扰和安全距离的现实约束。

综上所述，固定范围装卸调度模式通过划分静态或动态的轨道吊固定作业区域来避免轨道吊间可能产生的作业冲突问题，但是同时也增加了各轨道吊的空闲时间，降低了利用率。柔性范围装卸调度模式则可以满足灵活的任务分配需求，每台轨道吊均可得到充分利用，获得更高的作业效率和负荷均衡率。然而，柔性范围协同调度问题可能存在因安全距离和多轨道吊间干涉约束导致的轨道吊相互避让现象，如何判断轨道吊间的干涉，从而减少避让产生的等待时间，也是需要解决的问题。因此，本文针对柔性范围协同调度问题，基于轨道吊的连续运行模式，提出同时考虑作业干涉约束和安全距离约束的多轨道吊柔性协同装卸调度策略。

麻雀搜索算法(Sparrow Search Algorithm，SSA)是XUE[9]提出的一种新型群智能优化算法，具有自组织性好、前期收敛速度快等优点，但易陷入局部最优。一些研究对该算法进行改进，例如，文献[10]和文献[11]等。这些改进虽然提高了算法跳出局部最优的能力，但是仍存在发现者的安全值适应度不足，加入者的局部搜索精度差等缺点。本文针对RMGCS 问题，提出一种改进的麻雀搜索算法(Improved Sparrow Search Algorithm，ISSA)，该算法利用自适应步长因子非线性动态递减更新发现者安全值，通过修改加入者向最优位置的移动方式提高搜索精度，从整体上降低算法计算复杂度，最后，采用LOV 规则将麻雀个体从实数向量转换成集装箱作业序列，快速、高效地实现求解RMGCS 问题，并与常用的群智能优化算法进行了对比研究。

1 问题描述与建模

1.1 问题描述

以大连铁路集装箱中心站为例，其主作业区包括：两条铁路装卸线、堆场、集卡通道、3台轨道吊和若干集卡等。本文以列车集装箱装卸作业为研究对象，针对RMGCS 问题，基于轨道吊连续运行模式，采用多作业线柔性范围装卸混合调度模式进行研究。其中，由于采取的是柔性范围调度模式，即未限定各轨道吊的作业区域，各轨道吊在作业期间可能出现相互干涉，因此，需要在数学模型中设置安全作业距离约束来保证各轨道吊不会出现干涉甚至交叉现象。为清晰阐述所研究问题，对列车、轨道吊、堆场进行编号，方法如下：

(1)沿铁路装卸线，将列车车头至车尾方向定义为正方向，依次对车厢和堆场列位编号。

(2)以垂直并远离铁路装卸线的方向定义为正方向，依次对堆场排位编号。

(3)沿列车车头至车尾方向依序对轨道吊编号。

根据上述规定，中心站多轨道吊作业场景编号具体如图1所示，其中，m为堆场总排位数，u为堆场总列位数。

图1 中心站主堆场编号示意Fig.1 Numbering diagram of main yard in railway container terminal

1.2 模型假设

建立的中心站多轨道吊调度优化模型遵照以下假设：

(1)集装箱箱型一致，均为40 ft；

(2)集装箱装卸计划已知；

(3)轨道吊的平均速度已知；

(4)每个集装箱的装卸视为1个任务；

(5)相邻轨道吊的安全距离设为4个贝位；

(6)轨道吊为连续运行模式，即正常情况下轨道吊作业不暂停。

1.3 模型的构建

模型同时考虑轨道吊大车和小车的移动，模型所涉及的符号和说明如表1所示。

表1 模型中的符号和说明Table 1 Symbols and descriptions in model

(1)目标函数

本文以总完工时间为性能指标，目标函数为

(2)约束条件

式(2)表示各轨道吊装卸任务的总量等于集装箱的总箱量；式(3)表示进行装卸任务的轨道吊数量约束，每1 集装箱仅由1 台轨道吊完成；式(4)和式(5)表示每台轨道吊进行集装箱装卸作业的前、后作业约束，式(4)表示每1个集装箱至多有1个紧前任务，式(5)表示每1个集装箱至多有1个紧后任务；式(6)表示每台轨道吊完成单个集装箱的时长约束；式(7)表示每个轨道吊两个连续作业间的时间关系约束；式(8)表示所有集装箱任务只被分配1 次；式(9)表示轨道吊之间的安全作业距离约束，表示在柔性调度过程中，各轨道吊在作业总完工时间内的任意时刻两相邻轨道吊之间的距离必须大于安全距离，同时，满足此条件又可以保证各轨道吊之间不会出现交叉，即满足轨道吊间的非交叉作业约束。

本文构建数学模型的思路与文献[7]类似，目标函数都是集装箱任务总完工时间，但在约束条件设置过程中有所区别。文献[7]对轨道吊大车和小车采用的是相同的平均运行速度，本文依据实际情况，区别了轨道吊大车和小车的平均运行速度，同时，分别计算轨道吊大车和小车的运行时间后，取较大值作为执行单个任务或空走过程的运行时间。此外，文献[7]将安全距离约束设置为：在装卸集装箱时，需保证编号较大的轨道吊所操作的集装箱的起始和终止贝位都大于编号较小的轨道吊所操作的集装箱的起始和终止贝位。而本文的安全距离约束条件式(9)设置为：保证相同时刻下相邻轨道吊间保持安全距离即可，保留了获取更多满足安全距离约束的调度方案的可能性。同时，本文将非交叉作业约束蕴含到安全距离约束中，而文献[7]区分两个约束。

2 算法设计与模型求解

2.1 麻雀搜索算法的改进

麻雀搜索算法是基于麻雀群聚寻找食物并躲避捕食者行为的启发而提出的一种群智能优化算法。SSA主要依据发现者、加入者和侦察者各自的更新规则更新位置，适应度值高的麻雀被选择为发现者，麻雀种群中除发现者外其余为加入者，部分比例的麻雀会充当侦察者的角色，SSA算法基本原理和位置更新规则参见文献[9]。本节针对中心站RMGCS问题的特点，改进麻雀搜索算法，提高算法的寻优性能，并完成其离散化，使其能够应用于求解RMGCS问题。

2.1.1 发现者更新公式的改进

根据发现者位置更新规则，安全值Sv为一定值，当警示值R2

因此，本文采取安全值Sv非线性动态递减的策略替换SSA中固定Sv的方式[12]，从而动态调整全局和局部搜索性能。安全值的更新方式为

式中：g为当前迭代次数；gmax为最大迭代次数；Sv、Svmax、Svmin分别为安全值、安全值最大值和安全值最小值。安全值Sv递减曲线如图2所示。

图2 安全值Sv 递减曲线Fig.2 Safety value decreasing curve

由图2 可知，Sv非线性动态递减策略使得Sv在整个迭代过程中呈现一个倒S型的递减趋势，迭代开始时，Sv能在较长时间取值较大，保证大多数麻雀处于非危险状态，便于在全局寻找到更好的觅食位置；迭代后期，种群局部聚集，较小的Sv可增加麻雀采取反捕食行为的概率，提高局部搜索的精度。

2.1.2 加入者更新公式的改进

为减少向原点的收敛趋势，使加入者麻雀在全维度上向所跟随的发现者靠拢，因此，删除加入者时向原点收敛的迭代步骤，同时，简化时的位置更新方式，修改后的加入者位置更新公式为

2.1.3 麻雀搜索算法的离散化

SSA 的连续性特点导致其不能解决离散的RMGCS 问题，因此，本文基于LOV 规则[13]完成迭代过程中产生的非整数麻雀个体向集装箱装卸任务整数作业序列的映射。

式中：δp,q为第p个麻雀降序排列后获得的序列在第q维上的位置；πp,q为第p个麻雀经LOV规则变换后在第q维上的位置。

2.2 编码设计

采用整数顺序编码，每只麻雀表示1组D个集装箱编号组成的序列，位置公式为

式中：D为轨道吊装卸任务包含的集装箱个数；xp,q为第p个麻雀个体第q维上的集装箱的编号。

2.3 适应度函数

麻雀个体的适应度函数Ff表示各轨道吊完成所有任务的总完工时间，以0时刻作为任务开始时间，计算式为

2.4 轨道吊任务分配策略

由于采取的是柔性范围装卸调度模式，未限定各轨道吊的作业区域，即未提前分配好各轨道吊需要执行的集装箱任务，同时，根据本文的编码方式，算法求解是对包含所有集装箱任务的作业序列进行迭代寻优，因此，进行作业序列求解的前提是根据集装箱作业序列和设定的任务分配策略依次将各个集装箱任务分配给各轨道吊。

任务分配过程是体现多轨道吊柔性协同调度优化的关键步骤，因此，为更清楚地描述多轨道吊的任务分配过程，提前给出设计的符号和说明，如表2所示。

表2 任务分配中的符号和说明Table 2 Symbols and instructions in task assignment

根据产生的轨道吊作业序列，按如下流程将作业任务序列分配给各轨道吊：

Step 1 输入作业序列，转到Step 3。

Step 2 随机更新作业序列，转到Step 3。

Step 3 根据作业序列判断当前任务i是否为最后一项任务，若是，则退出分配；如果不是，读取当前任务的位置信息，并转到Step 4。

Step 4 判断当前任务i的Ps,i是否在之前，若不是，转到Step 5；若是，则把当前任务i分配给轨道吊1，进行干涉判断。若不干涉，转到Step 8；若干涉，转到Step 2。

Step 5 判断当前任务i的Ps,i是否在和之间，若不是，转到Step 6；若是，则把当前任务i分配给和中较小的轨道吊，进行干涉判断。若不干涉，转到Step 8；若干涉，则分给另一轨道吊，进行干涉判断(若不干涉，转到Step 8；若干涉，转到Step 2)。

Step 6 判断当前任务i的Ps,i是否在和之间，若不是，转到Step 7；若是，则把当前任务i分配给和中较小的轨道吊，进行干涉判断。若不干涉，转到Step 8；若干涉，则分给另一轨道吊，进行干涉判断(若不干涉，转到Step 8；若干涉，转到Step 2)。

Step 7 把当前任务i分配给轨道吊3，进行干涉判断。若不干涉，转到Step 8；若干涉，转到Step 2。

Step 8 更新该轨道吊的时间和位置信息，查询下一任务序号，转到Step 3。

2.5 轨道吊干涉判断

在多轨道吊柔性协同调度优化中，如何判断在任务分配过程中被分配任务的轨道吊在执行任务时是否满足数学模型中设置的轨道吊间的安全作业距离约束是一个关键要点。

在进行轨道吊间的干涉判断过程中，为避免因比较每时刻3 台轨道吊之间的位置而产生的较大计算量，此处设定仅需比较执行任务i过程中，轨道吊大车、小车达到初始位置和目标位置时4个时刻3 台轨道吊之间的距离是否小于安全距离作为干涉判断标准。

以1 个实例进行描述，假设把第i个任务分配给轨道吊2，本文轨道吊运行是建立在连续运行模式之上，因此，可以获得如下数据：为当前任务i的开始时刻；分别为轨道吊2 大车、小车到达当前任务i初始位置的时刻；分别为轨道吊2 大车、小车到达当前任务i目标位置的时刻。

图3 各轨道吊大车在执行任务过程中的位置Fig.3 Location of each RMG during task

2.6 解码设计

解码以一个样本量为12 的装卸算例作为示例。

(1)输入集装箱作业序列Xi=[10,6,1,3,5,9,7,11,2,12,8,4]。

(2)根据任务分配方式，获得每个集装箱分配到的轨道吊的编号，如图4所示。

图4 集装箱作业序列与轨道吊对应图Fig.4 Corresponding diagram of container operation sequence and RMG

(3)计算每个集装箱的完工时间，即

(4)输出集装箱作业顺序和各集装箱匹配的轨道吊，即轨道吊1作业顺序为[1,3,2,4]，轨道吊2作业顺序为[6,5,7,8]，轨道吊3 作业顺序为[10,9,11,12]。

2.7 ISSA算法求解步骤

基于ISSA求解多轨道吊调度优化问题的主要步骤如下：

Step 1 设置麻雀种群规模Mn，发现者占比Pn等参数。

Step 2 在搜索空间内，随机产生初始麻雀种群。

Step 3 根据麻雀种群中各麻雀个体的作业序列进行任务分配。

Step 4 计算每只麻雀的适应度值，选出并记录当前最佳适应度值及其对应麻雀个体，以及当前最差适应度值及其对应麻雀个体。

Step 5 根据发现者更新规则更新发现者序列，并依据LOV规则进行离散化。

Step 6 根据加入者更新规则更新加入者序列，并依据LOV规则进行离散化。

Step 7 根据侦察者更新规则更新侦察者序列，并依据LOV规则进行离散化。

Step 8 判断迭代次数是否满足终止条件，满足则输出最优麻雀个体，结束算法；否则，转到Step 3进行下一次迭代。

ISSA求解RNGCS问题流程如图5所示。

图5 ISSA求解RMGCS问题流程Fig.5 Process of RMGCS problem solved by ISSA

3 算例分析

为验证ISSA算法求解考虑作业干涉约束和安全距离约束的RMGCS 问题的有效性，分别使用SSA、ISSA、标准粒子群算法(PSO)和遗传算法(GA)求解4 种样本量的装卸作业算例。各算法均采用Matlab 编程，操作系统为Win10，处理器为Intel(R)Core(TM)i5-4210@1.70 GHz，内存为4 GB。

为保证各算法求解效果的可靠性，选取多组装卸作业算例，以大连铁路集装箱中心站的轨道吊运行数据进行计算求解，其中，轨道吊大车平均运行速度vb=120 m⋅min-1，小车平均运行速度vs=90 m⋅min-1；所有算法的种群规模均为100，迭代1000次，进行各算法的算法参数的独立仿真，最终选定如下参数：SSA 和ISSA 发现者占比为0.4；侦察者占比为0.2；SSA 安全值Sv=0.8；ISSA 安全值最大值Svmax=0.9，安全值最小值Svmin=0.4；GA交叉概率为0.8，变异概率为0.2；PSO 个体学习因子为0.2，群体学习因子为0.1。

本文采用上述的各算法设定参数，对4种样本规模的算例分别进行50 次仿真并取平均值，进行算法性能的比较说明，其中4种样本规模的算例包含从30，60，90，120 个集装箱，即小规模到大规模的算例。求解结果如表3所示，其中，Tavg为平均总完工时间；Ts为平均求解1次需要的时间。

表3 各算法求解结果Table 3 Results of each algorithm

由表3 可知，随着样本规模的扩大，各算法间的求解性能差异逐渐扩大，总体来说ISSA 针对不同样本量均有更好的求解性能，同时，迭代前期收敛速度快，相对标准SSA、PSO 和GA 算法适应性更强。

选取样本规模为45 的装卸作业任务作为算例，具体任务信息如表4所示。

表4 样本量为45的装卸箱作业任务Table 4 Loading and unloading task with sample size of 45

运用本文提出的ISSA算法对算例进行50次仿真，将运算结果与CM装卸调度模式[7](CM，轨道吊固定范围作业，顺序卸装)的求解结果进行比较，结果如表5所示，其中，Tmax为最大的总完工时间；Tmin为最小的总完工时间；TCM为CM 调度模式的总完工时间。

通过表5 的比较结果可知，柔性协同调度模式可使装卸作业的总完工时间缩短15.5%，大大减少了轨道吊的作业时间，提高了中心站轨道吊利用率。

表5 ISSA与CM的比较结果Table 5 Comparison results of ISSA and CM

50 次仿真计算中，获得的最好一次最优解为325.2 s，对应的各轨道吊装卸调度方案如表6所示，此方案下各轨道吊的大车走行图如图6所示。

图6 最优解下轨道吊大车走行图Fig.6 Traveling diagram of RMG under optimal solution

表6 最优作业序列Table 6 Optimal operation sequence

从图6 可以看出，各轨道吊在运行过程中，两两相邻的轨道吊之间会始终保持大于安全距离的间隔，保证各轨道吊在正常的装卸箱作业时不会出现相互干扰，并且，各轨道吊的负荷均衡率较高，3台轨道吊的完工时间也基本接近。

4 结论

(1)针对RMGCS问题，基于轨道吊连续运行模式，提出了同时考虑作业干涉约束和安全距离约束的铁路集装箱中心站多轨道吊柔性协同装卸调度策略，建立了目标函数为最小化集装箱任务总完工时间的混合整数规划数学模型。

(2)结合RMGCS问题特性，提出了一种改进的麻雀搜索算法，首先，设计了能够解决多轨道吊作业冲突的任务分配策略和多轨道吊之间的干涉判断方法；其次，利用自适应步长因子的方式非线性动态递减更新发现者安全值，平衡全局搜索和局部搜索；再次，修改加入者向最优位置的移动方式，增强了加入者搜寻最优位置的能力；最后，采用LOV规则将麻雀个体从实数向量转换成集装箱作业序列，实现了ISSA 算法对考虑作业干涉和安全距离约束的RMGCS问题的求解。

(3)选取不同装卸作业算例，分别使用ISSA与标准SSA、PSO 和GA 算法求解考虑作业干涉和安全距离约束的RMGCS问题。结果表明：所构建的模型和算法能够快速有效求解不同规模的RMGCS问题，同时缩短集装箱任务的总完工时间，提高了轨道吊作业的均衡性和使用效率。