煤炭堆场空间调度的GRASP算法研究

2020-11-12赵习强郑澜波陈致远

武汉理工大学学报（信息与管理工程版） 2020年5期

赵习强，郑澜波,陈致远

(1.武汉理工大学物流工程学院，湖北武汉 430063；2.神华黄骅港务有限责任公司，河北沧州 061113)

煤炭是我国目前使用的主要能源之一，“北煤南运”、“西煤东运”的运输格局使得港口成为煤炭供应链中重要的一环。堆场是煤炭在港口中转运输的缓冲区，堆场作业的流畅程度直接影响到港口整体作业效率的提升。但由于堆场资源的有限性，堆场调度往往成为港口作业的瓶颈环节。堆场调度包括堆场设备的调度和堆场空间的分配。如颜佳佳[1]从黄骅港煤炭码头的实际数据出发，基于翻堆作业系统建立模型，通过Witness仿真软件对翻车机、堆料机、皮带机进行调度及优化。樊小波[2]总结了散货码头露天条形堆场空间分配和封闭筒仓堆场空间分配问题的研究现状。

还有学者采用数学优化的方法来研究开放垛位模式的堆场空间分配，如BOLAND等[3]以纽卡斯尔港的煤炭堆场调度为研究内容，考虑堆取料机的分配作业，建立数学模型，提出3种堆场规划方法，通过实验分析发现基于整数规划的结构算法的性能最好。BELOV等[4]在文献[3]的基础上，采用大邻域搜索的约束规划方法在更短的时间内搜索到最优解。SAVELSBERGH等[5]以澳大利亚猎人谷煤炭供应链问题为背景，以最小化船舶平均延迟为目标建立动态模型，并设计了一种树搜索算法来解决堆场调度在时间、空间两个维度上的最优化问题。文灿[6]以最小化煤堆占用堆场的时间为目标，分别建立基于特殊顺序约束二维装箱问题的整数线性规划(MIP)模型和约束规划(CP)模型，并生成实验数据，利用分支定界算法和约束规划算法进行求解，通过实验证明了CP算法的求解效果更好。但CP算法随着数据规模的增大求解耗时增加，且能求解的数据规模有限。

文献[3]的研究结果表明，基于煤堆占据场地的空间和时间建立时空图，堆场空间调度问题可以转化为一个二维装箱问题。二维装箱是一个NP-hard问题，目前对二维装箱问题的研究主要包括3类求解方法：①构造近似算法。如BAKER等[7]提出的 BL(bottom left)算法，其策略是将选中的物体放在箱子的右上角，然后尽量向下向左做连续移动，直到不能移动为止。②精确算法。根据求解机制的不同，精确算法可分为数学规划方法和约束规划方法。如DELL′AMICO等[8]提出一种求解带时间窗约束二维装箱问题的分支定界算法，并通过大量计算实验进行了验证。PISINGER等[9]则将约束规划方法对一刀切等特殊约束的强大建模处理能力和分解算法对整数线性规划模型的高效求解能力很好地结合在一起，可有效求解一般二维装箱问题。③智能优化算法。如WEI等[10]针对带有卸载约束的二维条形装箱问题，利用最佳适应(best fit)算法来生成给定物品序列的装箱方案，并通过随机局部搜索改变物品序列的方式来改进求解，最后实验验证了该方法的有效性和优越性。

笔者针对堆场空间调度问题，结合GRASP算法[11]和求解二维装箱问题的经典算法即BL 算法，加入可以处理特殊位置约束的repair算子，实现可以求解更大规模样本数据的GRASP算法，弥补现有研究利用精确算法求解的数据规模局限性，通过实验确定影响GRASP的关键参数，并对比分析基于CP的精确求解算法和基于GRASP的启发式算法各自在不同规模样本数据上的效果。

1 煤炭堆场空间调度模型

1.1 煤炭堆场空间调度问题描述

在煤炭堆场空间调度问题中，堆场场地多为长条矩形，实际作业时，通常每个煤堆在堆场的高度都一致且覆盖了条形场地的整个宽度，故以煤堆占据条形场地长度的不同来表示煤堆占据堆场空间大小的不同。煤堆占据堆场空间的时间由堆料时间、堆积时间、取料时间3部分组成，其中堆料时间、取料时间分别对应堆料机、取料机作业于该煤堆的时间，因堆料机、取料机工作速率恒定，故堆料时间、取料时间与煤堆大小成正比，而堆积时间是指从堆料结束至取料开始的时间，受堆料时间和取料时间共同影响。

建立堆场煤堆调度的时空图，如图1所示。其中，一个矩形代表一个煤堆的堆场调度，纵轴方向向上点H1为煤堆在堆场的起始堆放位置，横轴方向点L1为煤堆的堆料开始时间，点L3为取料的开始时间。根据煤堆的需求量和场地单位空间容纳能力可以计算出煤堆长度，确定煤堆在场地的末端位置，即点H2。同理，根据需求量和堆料机、取料机的速率可以计算出煤堆的堆料时间和取料时间，确定煤堆堆料完成时间(点L2)和取料完成时间(点L4)。煤堆堆料完成时间与取料开始时间的差值就是煤堆的堆积时间。

图1 堆场煤堆调度时空图

考虑实际作业情况，煤炭堆场空间调度问题还有以下特点：①时空图中的煤堆矩形不能相互重叠。②同一艘船舶的煤堆的最早取料开始时间不得早于煤堆的最晚堆料完成时间。③同一艘船舶的煤堆必须按照一定的取料顺序进行取料。

因此，煤炭堆场空间调度问题可描述为：在一定数量的长度、宽度确定的条形堆场中，给定一定时期内船舶所需的煤堆种类和每种煤堆的需求量，决策所有煤堆在条形堆场中占据堆场的长度位置和占据该位置的时间，使最后一艘船舶的离开时间最早，即最后一个煤堆的取料完成时间最早。

1.2 与二维条形装箱问题的转化

二维条形装箱问题的定义为：设有一个长度为L、高度不限的长条形箱子和一组矩形物品集合J={j1,j2,…,jn}，矩形物品的高度和长度集合分别为H={h1,h2,…,hn}和L={l1,l2,…,ln}，寻求一种将所有矩形物品放入长条形箱子并保证物品占用箱子的总高度最小的方法。

二维条形装箱问题和煤炭堆场空间调度的示意图如图2所示，可以看出二者有很大的相似性。若把二维条形装箱问题中的每个矩形物品看作一个煤堆，则矩形物品的宽度代表煤堆占用场地的长度，矩形物品的长度代表煤堆占用场地的时间，最小化箱子总长度代表最小化最后一个煤堆的取料完成时间，这样两个问题就可以进行很好的转化。两个问题的不同之处在于：①煤炭堆场空间调度的煤堆矩形由于煤堆堆积时间的不确定性而导致煤堆矩形的时间长度不确定；②煤炭堆场空间调度问题中，煤堆矩形之间有特殊的先后关系。

图2 二维条形装箱问题和煤炭堆场空间调度示意图

综上可知，煤炭堆场空间调度问题可以转化为一个带特殊位置约束的二维条形装箱问题。文献[6]对煤炭堆场空间调度问题转化为带特殊位置约束的二维条形装箱问题后的数学模型给出了详细的描述，在此不再赘述。

2 GRASP算法设计

2.1 GRASP 算法原理

随机贪婪自适应搜索(GRASP)算法是一种迭代算法，其思路是先基于贪婪随机原则构建一个可行的初始解，再从该初始解出发不断改进，通过多次迭代，最终得到最优解。每次迭代主要包含随机贪婪构造阶段和局部搜索改进阶段两个独立的阶段。即每次迭代中，首先通过随机贪婪构造阶段构造出一个初始可行解，然后在局部搜索子过程利用邻域搜索算法来优化随机贪婪构造阶段产生的初始解，找到局部最优解，当局部最优解比当前最优解更好时，则用局部最优解替换当前最优解。迭代完成后，所得的当前最优解即为最终的全局最优解。

具体而言，在随机贪婪构建阶段，初始化可行解f为空，同时初始化候选集C并对候选集的每一个元素进行评估，判断是否可以加入限制候选列表(restricted candidate list，RCL)。随后从RCL中随机选择一个元素与当前解f进行合并直到不满足条件，更新候选集的元素并对候选集中每一个元素重新进行评估。在局部搜索阶段，对初始可行解的邻域进行局部搜索，若相邻解f′比当前最优解f*更好，则更换f*=f′，直到找到局部最优解。

2.2 算法实现

2.2.1 随机贪婪构建阶段

(1)BL算法。在随机贪婪构建阶段，从RCL中选出元素加入当前解S时，采用二维装箱问题经典的启发式构造算法即BL算法来确定加入的元素在当前解中放置的位置。

(2)贪婪函数。贪婪函数的作用是在随机贪婪构建阶段评价候选集C中的元素，以判断该元素是否能进入RCL。考虑煤堆矩形的长度和宽度两个变量，选取煤堆矩形的长度ls、煤堆矩形的高度hs、煤堆矩形的长高和(hs+ls)、煤堆矩形的面积(hsls)作为贪婪函数。

(3)贪婪参数α。贪婪参数α的作用是控制贪婪程度。α=0对应完全贪婪的过程，α=1则对应完全随机的过程。实际求解时，为了避免完全贪婪破坏随机作用的扰动性，通常设置贪婪参数α的取值范围为[0.5,1.0]，笔者设定贪婪参数α=0.5,0.6,0.7,0.8,0.9,1.0，再通过实验来选取合适的贪婪参数值。

(4)repair算子。由于同一艘船舶不同煤堆矩形之间存在特殊的位置顺序约束，文献[6]将这一约束转化为同一艘船舶不同煤堆的堆料完成时间一致的最优性定理约束，故在随机贪婪构建阶段，当同一艘船舶的煤堆矩形都加入当前解S后，还需要对煤堆矩形的位置进行修复，使得当前解S成为可行解。

BL算法生成的当前解如图3所示。其中，虚线矩形S1、S2、S3是同一艘船舶需求的3个煤堆，a、c、e分别为3个煤堆的堆料开始时间，b、d、f分别为3个煤堆的堆料结束时间，可以看出同一艘船舶需求的煤堆S1、S2、S3的堆料完成时间并不一致，说明采用BL算法构建的当前解并不满足最优性定理的约束。

图3 BL算法生成的解

图4 repair算子修复后的可行解

2.2.2 生成相邻解

ALVAREZ-VALDES等[12]提出一个GRASP中生成相邻解的策略，并通过实验验证了该策略的有效性。该策略生成相邻解步骤为：①去除当前k解中最后k%的矩形(如20%)。②使用确定性构造算法重新将这k%的矩形装入条形中。

笔者选取该策略来生成相邻解，选用BL算法作为重新装填k%的矩形的算法。同时，权衡考虑参数对生成相邻解的时间与质量的影响，设置k=30。

2.2.3 选择相邻解

选择相邻解的策略有首次适应和最优适应两种。首次适应策略是指当第一次搜索到比可行解好的相邻解时，就用该相邻解替换可行解，并以此作为新的起点进行局部搜索。最优适应策略则要求所有的相邻解都被搜索之后，使用最优的相邻解替换可行解。为了保证改进解的质量，笔者选取最优适应策略来选择相邻解。

3 计算实验

3.1 实验设计

按文献[6]生成测试数据的方法生成了6组测试实例，并与文献[6]的CP求解算法进行比较。本次算法实验的代码通过Python 3.6语言编写，求解文献[6]的CP模型调用的求解器为IBM ILOG CPLEX 12.7中的CP Optimizer。本次实验的环境设置：CPU为2.5GHz Intel Core i7-4710MQ，RAM为12GB的戴尔一体机，操作系统为Ubuntn 18.04。

3.2 实验研究

3.2.1 贪婪函数对GRASP算法性能的影响

不同贪婪函数下GRASP算法求解的实验结果如表1所示。其中，最大迭代次数取500，实例编号X10_i表示第X组数据的第i个实例，10表示每个实例中船舶的数量，N表示每个实例需求的煤堆矩形的总数。从表1可以看出，贪婪函数为煤堆高度hs时的实验结果优于其他3种贪婪函数的实验结果，在13个实例上都求得了当前最优解，仅在实例B10_3、C10_1上没有求得当前最优解，但也求得了满意解。

表1 不同贪婪函数下GRASP算法求解的实验结果

3.2.2 贪婪参数对GRASP算法性能的影响

不同贪婪参数值下GRASP算法求解的实验结果如表2所示(最大迭代次数取500)，可以看到当贪婪参数α=1.0时，在 13 个实例上都求得了当前最优解，仅在实例 A10_3、 A10_4上求解的结果稍逊于当前最优解。实验结果表明，贪婪参数α=1.0显著优于其他贪婪参数值。

表2 不同贪婪参数值下GRASP算法求解的实验结果

3.2.3 GRASP算法与CP算法对比分析

GRASP算法与CP算法的实验结果对比如表3所示。其中，由于GRASP算法具有随机性，因此利用GRASP算法求解时分别运行10次，并统计均值、最优值；GRASP算法的最大迭代次数取1 000；贪婪函数为煤堆矩形高度hs；贪婪参数α=1.0。而CP算法是精确算法，求解时只运行一次；CP算法的求解时间上限设为3 600 s。

(1)对比A、B、C 3组数据规模较小的实例求解结果可以看出，在实例A10_2的求解上，CP算法只求得了可行解且耗时达3 600.00 s；除此之外的其他实例，CP算法均能求得最优解，且在求得最优解的实例中，仅A10_5耗时较长，其余实例耗时均未超过1.00 s。GRASP算法仅在实例A10_2、A10_5上的求解耗时小于CP算法，所求解优于或等于CP算法；在B组实例中，虽然GRASP算法在A10_3、A10_4实例上也求得了最优解，但耗时较长；在实例C10_1、C10_2、C10_5、A10_1、A10_3、A10_4的求解上，GRASP算法同样耗时较长，且GRASP算法所求解与CP算法所求解相差10%左右。

表3 GRASP算法与CP算法的实验结果对比

(2)对比D、E、F 3组数据规模较大的实例求解结果可以看出，CP算法仅在F组实例和实例D20_3、D20_4、D20_5上求得了可行解，且耗时较长；而GRASP算法在这些实例上的求解耗时远小于CP算法，且仍能求得与CP算法的偏差在10%左右的满意解，其中GRASP算法在实例F20_3上的所求解甚至优于CP算法；此外，在CP算法未求出可行解的其他实例上，GRASP算法仍能在一定时间内求出可行解。

(3)在GRASP算法求解每个实例的结果中，目标值标准差在0.00～1.83之间，求解结果的离散程度低，算法运行的稳定性较高，具有较好的鲁棒性。综合实验结果可知，对于小规模案例，CP算法的求解效果比GRASP算法更好；但对大规模数据样本，GRASP算法能在更短时间内求得满意解，求解效果优于CP算法。