学习型混合差分进化算法优化月台调度问题

吴秀丽，张雅琦

(北京科技大学 机械工程学院，北京 100083)

0 引言

近年来，为了满足不断提升的物流需求，配送中心的自动化与智能化建设发展迅速。配送中心主要指为下游客户提供配送、仓储、流通加工等服务的物流活动场所。每天都有大量的配送车辆到达配送中心，并进行装卸货作业，为提高车辆的装卸货效率，配送中心一般都建有月台。配送中心的月台也称站台，一般指进行装卸货物作业的高于地面的平台，是配送中心的重要设施。月台相较于车辆所在地面有一定高度，工作人员进行装卸货物作业时减少了搬运的高度差，使得装卸货物更加高效、省力，因此，月台已成为配送中心的标配。

月台在配送中心系统中起着重要的作用，是仓库与运输车辆进行装卸货物作业的资源交汇处，处于配送中心物流系统的咽喉位置，是连接配送中心中仓库与配送车辆的关键节点，是货物进出仓库必经之路[1]。由此可见，月台影响着物流运作效率[1]和供应链的整体运作效率，所以配送中心需要特别重视对月台的科学管理。月台调度管理旨在根据配送车辆的月台预约信息和可用的月台资源合理地为车辆安排作业月台与作业时间，使月台与运输车辆之间的作业更加紧密、有序地进行。如果没有进行合理的月台调度管理，会给仓库与运输人员双方造成困扰。对于仓库，如果没有事先掌握月台的占用情况、车辆的到达时间、货物的装卸作业进程等信息，没有进行合理的月台调度，从而合理安排仓库的出入库作业、月台资源分配，容易造成月台装卸货作业忙闲不均，不能充分地利用人力、设备资源；对于运输人员，如果没有事先进行月台调度，可能会需要长时间滞留排队等待作业，导致无效挪车、道路拥堵，甚至可能引发人员冲突。而在根据月台、运输车辆作业的相关信息进行合理的月台调度后，对于仓库便可以实现月台人力、设备资源的高效率利用，对于运输车辆可以实现高效装卸货作业。

然而，目前我国配送中心的月台仍旧主要采取人工搬运装卸货物，月台调度决策也主要采用简单的调度规则进行，如根据车辆到达园区时间、车辆预约时间[2]等顺序按照先到先服务(First Come First Served, FCFS)规则进行调度，这样的方法可能导致很多有效信息被忽略，从而导致月台资源利用率低，车辆等待时间长，配送中心管理水平滞后。有少数企业开始使用月台管理系统对月台资源进行调度，根据《物流管理国际期刊》发布的《技术使用调研》报告可知，仅有8%的公司使用月台管理系统对月台进行管理[3]。但随着物联网、大数据、人工智能以及移动通信技术等技术的快速发展，近几年来一些企业在智慧物流园区建设方面不断发力，智能月台调度系统已逐渐推广使用[3]。上海富勒信息科技有限公司提供的FLUX WMS仓库管理系统提供了月台管理的相关模块，系统会根据月台数量、月台类型、车辆类型、车辆预约时间、车辆历史作业信息等信息使用算法对月台资源进行管理[1]。普洛斯旗下的际链科技研发了独立的智能月台调度系统，系统实现了通过调度管理引导车辆准确停靠、及时离开月台[1]。结果表明，智能化的管理方法提高了园区的管理水平，提高了月台作业效率。但是，高效的月台调度算法还比较缺乏。

月台调度问题可以建模为不相关并行机调度问题，众多学者在文献中广泛地研究了不同目标下的不相关并行机调度问题，目标主要包括最小化最大完工时间、最小化总延迟时间、最小化总提前/延迟时间等。下面将从不同目标分别总结不相关并行机调度问题研究现状。

对以最小化最大完工时间为目标的不相关并行机调度问题，国内外学者针对不同约束条件下的问题展开了研究。FANJUL-PEYRO等[4]针对具有稀缺作业资源约束下的问题，建立了两个整数线性规划模型，分别提出了3种数学策略。对于具有设置时间的问题，FANJUL-PEYRO等[5]提出一种新的混合整数线性规划和基于数学规划的算法，BAEZ等[6]提出一种结合贪心随机自适应搜索算法和变邻域搜索的混合算法，EWEES等[7]提出基于萤火虫算法的改进樽海鞘群算法。AVEDEENKO等[8]针对具有释放时间的问题提出一种动态规划方法，采用了一种自适应的方法来减少搜索空间。

对以最小化总延迟为目标的不相关并行机调度问题，以下学者针对不同约束条件下的问题进行了研究。ATENCIO等[9]根据一个泊位分配实例，比较了3种著名的元启发式方法的性能。DIANA等[10]研究了带有序列、机器相关的设置时间的问题，提出6种变邻域搜索的邻域结构，并分析证明了用变邻域下降算法替代局部搜索算子可以提高元启发式算法的性能。ZHANG等[11]研究了具有设定时间依赖和机器—作业资格考虑的动态不相关并行机问题，使用Q学习算法，并采用5种启发式方法作为动作，实验结果表明该方法优于单独使用这5种启发式方法。

对于以最小化总提前/延迟时间为目标的不相关并行机调度问题，以下学者针对不同约束条件下的问题进行了研究。对于具有交货时间窗约束的问题，ZEIDI等[12]设计了一种集成遗传算法与模拟退火算法的智能算法，CHENG等[13]使用改进的遗传算法和分布式释放时间控制机制来获得近似最优解。王宏等[14]针对带有到达时间窗、序列相关设置时间的多跑道飞机调度问题设计了一种遗传算法进行优化求解。EKICI等[15]以一个电视生产商为研究对象，研究了存在时序相关的设置、不相等的释放时间、机器—作业兼容性限制和工作负载平衡要求为约束的问题，提出了4种启发式方法，分别为：顺序启发式算法、禁忌搜索算法、随机集合划分算法和基于禁忌搜索的元启发式算法。

总结现有文献，可以发现：

(1)不相关并行机调度问题广泛存在于各种作业活动中，如泊位调度[9]、飞机调度[14]、车间调度[16]等。目前，众多学者们针对不同背景环境下的不相关并行机问题展开了研究，根据研究背景确定作业的目标以及约束条件，再采用不同的算法设计出智能优化方案对该问题进行优化求解。然而，很少有学者针对以月台调度为背景的不相关并行机问题展开研究。

(2)不同的作业活动往往存在不同的约束条件，包括序列相关的释放时间[15]、设置时间[5,10,14]、交货时间窗[12]、到达时间窗[14]、机器-作业兼容性限制[15]等，其中对具有设置时间的问题研究较多，而对机器—作业兼容性限制等约束条件研究较少。

(3)大多数学者研究的调度问题为静态问题[4-7,9,10,12-15]，少数学者研究了动态问题[8,11]。

(4)学者们大多使用算法对不相关并行机调度问题进行求解，包括模拟退火算法[12]、樽海鞘群算法[7]、遗传算法[12-13]、萤火虫算法[17]、禁忌搜索算法[15]、Q学习算法[11]等，只有少数学者采用精确求解或启发式规则的方式[4-5]求解不相关并行机调度问题。因此，本文将针对静态的月台调度问题提出智能优化方案。

信息化、自动化和智能化是当今物流行业的必然发展趋势，月台作为配送中心中连接仓库仓储作业与车辆运输作业的关键环节，也正向着智能化方向提升发展。本文将在充分了解国内外配送中心月台调度方法研究现状的基础上，针对配送中心月台管理系统中的智能调度模块，利用智能优化算法，提出智能、高效的月台调度方法。本文主要贡献包括：①根据实际的月台调度问题进行分析与建模；②提出学习型混合差分进化算法，根据问题特征设计了编/解码算法，结合超启发式算法(Hyper Heuristic, HH)，设计了学习型算子选择机制，使算法可以学习选择算子的经验，并选择对当前有利的算子，结合变邻域搜索算法(Variable Neighborhood Descent, VND)，提高算法的搜索能力。

1 月台调度模型

1.1 问题描述

本文研究的月台调度问题可以描述为：车辆需要提前一天预约装卸货作业的时间。有N辆预约成功的车辆，有M个可以进行装卸货作业月台。由于车型、月台作业设备、供应商、配送地点等因素影响，车辆与月台有不同的作业类别，车辆与月台之间存在兼容性约束，一个类型的车辆只能在可以处理该类型车辆作业的月台上进行装卸货作业。车辆在信息系统上预约进行作业的时间窗口，使用调度算法进行调度，调度结果中车辆到达时间与离开时间可以超出预约的时间窗口范围，但需接受不同的提前、拖后惩罚，调度算法优化的目标为最小化总加权作业的提前、延迟惩罚。并且，为了给重要客户提供更好的服务，为重要客户设置更高的提前、拖后惩罚权重。

调度月台资源时，需要根据车辆的类型、预约作业时间窗口、提前惩罚、拖后惩罚与月台的类型、作业情况等信息为车辆合理分配月台，减少所有作业车辆的总加权作业的提前、延迟惩罚。调度完成后，如果预约车辆到达配送中心的时间早于调度结果时间，则安排车辆在停车场等待；如果预约车辆到达配送中心的时间晚于调度结果时间，即车辆迟到，则需对该车辆作业进行现场调度，为该车辆分配合适的月台进行装卸货作业。

为了简化月台调度问题，作出如下假设：

(1)在零时刻所有月台可以使用；

(2)在零时刻所有车辆可以开始作业；

(3)车辆预约作业时间窗口的长度大于等于该车辆需要的作业时间；

(4)每个车辆仅可以在一个月台进行装卸货作业；

(5)装卸货作业一旦开始便不允许中断；

(6)每个月台一次只能接受一个车辆的装卸货作业；

(7)不考虑为车辆进行实时调度；

(8)不考虑在作业时间内月台设备出现故障。

1.2 符号定义

本文数学模型中使用的参数、变量和决策变量的符号以及定义如下：

(1)参数

M为总月台数量；

Mj为第j个月台，j=1, 2,…,M；

lmj为月台Mj可以处理的车辆类型集合，j=1, 2,…,M；

N为总预约车辆的数量；

Ji为第为i个车辆，i=1, 2,…,N；

lni为车辆Ji作业的类型，i=1, 2,…,N；

dsi为车辆预约作业窗口开始时间，表示车辆可以在dsi时间点后开始作业，i=1, 2,…,N；

dei为车辆预约作业窗口结束时间，表示车辆需要在dei时间点前结束作业，i=1, 2,…,N；

pi为车辆Ji进行装卸货作业所需要的时间，i=1, 2,…,N；

ai为车辆Ji单位时间的提前惩罚，i=1, 2,…,N；

bi为车辆Ji单位时间的拖期惩罚，i=1, 2,…,N。

(2)变量

Rj为月台Mj上的作业车辆序列，j=1, 2,…,M；

si为车辆Ji开始作业的时间，i=1, 2,…,N；

ei为车辆Ji结束作业的时间，i=1, 2,…,N。

(3)决策变量

Xij为0-1变量，若车辆Ji在月台Mj上进行作业，则Xij=1，否则Xij=0，i=1, 2,…,N，j=1, 2,…,M；

Yiy为0-1变量，若车辆Ji在车辆Jy前进行作业则Yiy=1，否则Yiy=0，i,y∈Rj，i≠y，j=1, 2,…,M。

1.3 优化模型

本文研究的问题的数学模型表示为：

bi×max{0,ei-dei})。

(1)

s.t.

(2)

Xij×lni∈Xij×lmj,∀i∈[1,N],∀j∈[1,M];

(3)

dsi≥0,∀i∈[1,N];

(4)

dei-dsi≥pi,∀i∈[1,N];

(5)

si≥0,∀i∈[1,N];

(6)

ei=si+pi,∀i∈[1,N];

(7)

Yiy×ei≤Yiy×sy，∀j∈[1,M]；

(8)

pi>0，∀i∈[1,N]；

(9)

Xij∈{0,1}，∀i∈[1,N]，∀j∈[1,M]；

(10)

Yiy∈{0,1}；∀i,y∈Rj，i≠y，∀j∈[1,M]。

(11)

式(1)为本文研究月台调度问题的目标函数，表示最小化总加权提前、延迟的惩罚。式(2)保证每个车辆的装卸货作业只分配给一个月台，并保证了每个预约车辆都进行了作业。式(3)表示一个类型的车辆只能在可以处理该类型车辆作业的月台上进行装卸货作业，即满足车辆—月台兼容性限制。式(4)表示每个车辆预约作业时间窗口的开始时间大于等于零。式(5)表示每个车辆预约作业时间长度大于车辆所需的作业时间。式(6)表示车辆开始作业的时间大于等于零。式(7)表示一个车辆结束作业的时间等于开始作业的时间加上该车辆的作业时间。式(8)表示在一个月台上，一个车辆开始装卸货作业的开始时间不小于前一个车辆作业的结束时间，保证了一个月台一次只能接受一个车辆进行装卸货作业。式(9)表示车辆的作业时间不能小于零。式(10)～式(11)表示决策变量的取值。

2 学习型混合差分进化算法

2.1 算法流程设计

单机器的总加权延迟最小化的调度问题是NP-hard问题[17]，因此本文研究的多个机器的总加权提前、延迟问题也是NP-hard问题。NP-hard问题求解难度很高，且随着问题规模的增加，求解过程的时间以及存储空间会随着问题规模的增加而呈现爆炸式增长的趋势，无法采用精确求解方法进行求解。因此，本文尝试使用智能算法进行求解。近年来差分进化算法(Differential Evolution，DE)[18]在车间调度[19]、信号处理[20]、电子设计[21]、经济学[22]等领域得到了广泛应用，具有结构简单、自适应能力强、收敛速度快、鲁棒性强等特点，但是DE算法也存在一些问题：①算法对变异算子、交叉算子有着很强的依赖，使用不同的算子对结果会产生很大的影响，以往学者的普遍做法是分别采用不同的算子进行仿真实验从而找到一个最优算子作为算法的算子，这样的做法消耗了大量的时间；②种群容易提前收敛，陷入局部最优解。因此，本文针对这些问题对标准的DE算法进行改进：①设计多个变异算子与交叉算子，结合HH算法设计了一种学习型算子选择机制，可以在线学习算子的表现情况,为算法选择优秀的算子;②添加局部搜索策略，对种群中的个体进行局部搜索，使算法可以跳出局部最优解，增加算法的寻优能力。

本文提出的学习型混合差分进化算法流程如图1所示，具体流程如下：

步骤1初始化参数，设置终止条件、记录奖励值的滑动时间窗表格，进入步骤2。

步骤2产生初始化种群，进入步骤3。

步骤3计算种群适应度，进入步骤4。

步骤4判断是否满足终止条件，若是则结束并输出最优结果；否则，进入步骤5。

步骤5使用学习型算子选择机制选择一个算子组合，并对当前种群执行算子组合的操作得到交叉种群，进入步骤6。

步骤6计算交叉种群中个体的适应度，进入步骤7。

步骤7根据父代种群与交叉种群适应度值执行选择操作得到选择种群，进入步骤8。

步骤8计算算子组合的奖励值，更新记录奖励值的滑动时间窗表格，进入步骤9。

步骤9判断是否满足执行局部搜索的条件，若是则进入步骤10，否则，进入步骤3。

步骤10对选择种群执行局部搜索操作，进入步骤3。

2.2 详细设计

2.2.1 编码

在进行优化前，需要将问题空间映射为解空间，因此首先将问题的解编码为染色体，每一条编码对应一个解。假设每个车辆ri的作业月台为ki，则定义染色体的基因向量为[r1,r2, …,rN,k1,k2, …,kN]，其中加工任务的总数为N，染色体的总长度为2×N，染色体分为两个部分:第一部分为车辆序列，第二部分为对应车辆作业的月台，如图2所示，染色体的第一部分与第二部分的第一位基因表示车辆3在月台1作业。

2.2.2 初始化种群

种群初始化要兼顾考虑种群中个体的质量与种群多样性，因此本文采用调度规则产生部分染色体提高种群个体质量，并随机产生剩余部分染色体保证种群多样性，初始化种群规模为Np。

2.2.3 适应值计算

首先，对染色体进行解码：根据染色体得到每个月台停靠的车辆及其停靠的次序，之后分别计算每个月台停靠车辆的开始作业时间和结束作业时间。然后，根据式(1)计算目标函数值得到该条染色体的适应度值。

对解码过程进行详细说明。记Rj={rj1,rj2, …,rjw, …,rjW}为月台Mj车辆停靠作业的次序向量，月台Mj共有W项作业。若车辆u与车辆v满足su=ev，即车辆u与车辆v是连续作业的，则称车辆u与车辆v的作业组成一个块Block。对月台Mj上的车辆进行解码，假设现在已经完成了前λ个车辆的解码工作，得到了前λ个车辆的si与ei，并得到了Z个Block，分别为Block1，Block2，…，Blockz，…，BlockZ，得到了每个块的开始作业时间osz与结束作业时间oez，按照如下方法对月台Mj上第λ+1个车辆rj(λ+1)进行解码。判断oeZ与dsrj(λ+1)的大小关系，分为如下几种关系进行讨论：

(1)如果满足oeZ=dsrj(λ+1)，如图3所示，其中横轴为时间轴，实线框为已经解码完成的块以及rj(λ+1)解码后的作业时间，虚线框为车辆rj(λ+1)的预约作业时间窗。车辆rj(λ+1)的作业开始时间可以安排为预约时间窗的开始时间，车辆rj(λ+1)与BlockZ中的作业是连续进行的，将rj(λ+1)加入到BlockZ中。那么，车辆rj(λ+1)的开始作业时间等于oeZ，车辆rj(λ+1)的结束作业时间等于车辆rj(λ+1)的开始作业时间加上所需的作业时间，srj(λ+1)=oez，erj(λ+1)=srj(λ+1)+prj(λ+1)。之后，更新BlockZ的结束时间等于车辆rj(λ+1)的结束作业时间，oeZ=erj(λ+1)。在这种情况下车辆rj(λ+1)的作业调度没有受到惩罚，该染色体的适应度值没有变化。

(2)若满足oeZ

(3)如果满足oeZ>dsrj(λ+1)，如图5所示。车辆rj(λ+1)的作业开始时间可以暂时安排为BlockZ中最后一个车辆的作业结束时间，然后再做调整。车辆rj(λ+1)与BlockZ中的作业是连续进行的，将rj(λ+1)加入到BlockZ中。那么，车辆rj(λ+1)的开始作业时间等于oeZ，车辆rj(λ+1)的结束作业时间等于车辆rj(λ+1)的开始作业时间加上所需的作业时间，srj(λ+1)=oeZ，erj(λ+1)=srj(λ+1)+prj(λ+1)。之后更新BlockZ的结束时间等于车辆rj(λ+1)的结束作业时间，oeZ=erj(λ+1)。

在这种情况下，若车辆rj(λ+1)的作业调度受到了惩罚，导致该染色体的适应度值增加，则需要考虑块BlockZ的前移能否减小该月台上已完成解码作业的总惩罚值，即适应度值，设BlockZ的前移距离为x，则BlockZ中的车辆整体向前移动x时间单位后的适应度值函数如式(12)所示。

bi×max{0,ei-x-dei})。

(12)

求解式(12)的最小值点对应的x值，计算过程参考LEE等[23]提出的计算惩罚函数斜率的方法，并令x=max{x, 0}。BlockZ向前移动直到遇到下面3种情况之一后停止：

(1)移动距离达到使目标函数达到最小值点的距离x；

(2)当BlockZ为该月台上的第一个块时，移动距离达到了osZ，即BlockZ不能够再向前移动；

(3)当BlockZ不是该月台上的第一个块时，移动距离达到了osZ-oeZ-1，即BlockZ向前移动直到与BlockZ-1相连接。

当遇到第3种情况停止后，BlockZ与BlockZ-1合并，需要重复块向前移动的过程，求出新的块向前移动的距离。

2.2.4 变异操作

(1)反转变异

wr∈[1,Np]。

(13)

反转变异操作的流程如下：随机产生不同的两个1～N之间的数字作为发生变异的位置，然后，分别对位于个体染色体第一部分与第二部分两个变异位置之间的基因序列颠倒顺序，如图6所示。

(2)基于优先工序交叉的差分变异

(14)

式中POX()表示采用基于优先工序交叉。

基于优先工序交叉的流程为：进行操作的两个个体分别记为父代1与父代2。对于染色体的第一部分与第二部分执行相同的操作，随机选择复制父代1中的基因到变异个体，编号的位置与父代1相同，并删除父代2中目前子代中包括的车辆作业编号，同时将父代2中剩余的基因按照顺序填入变异个体的空位中，如图7所示。

(15)

(3)随机插入变异

变异个体产生的方式如式(16)所示。

wr∈[1,Np]。

(16)

随机插入操作的流程为：从个体染色体的第一与第二部分中删除随机个数的相同位置基因，按照删除的顺序，对于染色体第一部分删除的每一个基因，可以得到该车辆可以进行作业的月台集合，并随机选择一个该车辆可以进行作业的月台，将车辆与随机选择的月台分别插入到染色体第一部分与第二部分的一个随机位置。

2.2.5 交叉操作

(1)基于优先工序交叉

交叉个体产生的方式如式(17)所示：

(17)

式中POX()表示采用基于优先工序交叉操作。基于优先工序交叉的流程见2.2.4节中基于优先工序交叉的差分变异中所述的基于优先工序交叉的流程。

(2)优先级保存交叉

交叉个体产生的方式如式(18)所示：

(18)

式中PPX()表示采用优先级保存交叉操作。

优先级保存交叉的流程为：将进行操作的两个个体分别作为父代1与父代2。产生一个由数字1和2组成的随机列表，表的长度为父代基因长度的一半。对染色体的第一部分与第二部分执行相同的操作。从随机列表最左侧的第一个位置开始，若随机列表的数字为1，则取出父代1中的最左侧没有在子代中出现的基因；若为2，则取出父代2中的最左侧没有在子代中出现的基因，直到读取到随机列表的最后一位，如图8所示。

2.2.6 学习型算子选择机制

标准离散差分进化算法在解决问题时，通常会直接选定一个交叉算子和变异算子，然而针对不同的具体问题以及使用算法对一个问题进行求解的不同阶段，不同的交叉算子和变异算子组合可能会对问题的寻优过程有着不同的影响，通常学者们会通过仿真确定交叉算子与变异算子的组合，这样的方法会耗费大量的时间，且无法确保可以找到最合适的算子组合。因此，本文设计了一种学习型算子选择机制，根据不同算子的表现情况为算法选择算子。

学习型算子选择机制采用HH算法。HH算法的原理为通过高层次启发式策略来管理和操纵一系列低层次启发式方法以实现算法寻优[25]，本文采用的高层次启发式策略为学习型算子选择机制，低层次启发式策略为变异、交叉算子组合。学习型算子选择机制采用文献[26]提出的一种自适应的多臂赌博机算法，并在奖励记录时引入时间窗机制，其中参数wv为探索概率衰减的速率，本文算法采用文献[26]推荐参数wv=0.95。算子组合采用2.2.4和2.2.5节中介绍的3个变异算子与2个交叉算子的组合，变异与交叉算子组合共有6种，如表 1所示。

表1 算子组合表

学习型算子选择机制的流程如下：

输入：滑动时间窗长度W，算子组合H个，当前迭代次数t，探索概率衰减的速率wv，两个W行H列的表格分别为算子选择记录表s、奖励值记录表r；

输出：s，r。

步骤1根据算子选择记录表s与奖励值记录表r计算每个算子组合a∈[1,H]被选中的次数Nt(a)与每个算子的平均奖励值Qt(a)，进入步骤2。

步骤2计算平均奖励值最小的算子被选择的次数mt，计算探索概率p=wv/wv+mt2，在开区间(0,1)取一个随机数ran，进入步骤3。

步骤3判断ran是否大于p，若是，则进入步骤4，否则进入步骤5。

步骤4选择动作at=argamaxQt(a)，即平均奖励值最大的算子，进入步骤6。

步骤5选择动作at=argaminNt(a)，即被选择次数最少的算子，进入步骤6。

步骤6执行算子，计算执行算子进行运算前后的平均适应值之差f，并将f作为奖励值，进入步骤7。

步骤7判断t是否小于等于W，若是，进入步骤8，否则进入步骤9。

步骤8将选择的算子与奖励值分别记录到滑动时间窗表格s、r中的第t行，结束并输出。

步骤9遵循先进先出的原则，将滑动时间窗表格s、r中的第一行数据挤出表格，将其余行向上移动一行，并将新数据记录到表格中的最后一行，结束并输出。

2.2.7 选择操作

采用贪婪选择的方法，一一对比Xt-1与Ut中的个体，选择适应度值较优的个体组成Xt。

(19)

式中f()表示计算个体的目标值。

2.2.8 局部搜索操作

本文采用VND算法作为局部搜索算法。在每一代种群中随机选取floor(Np×ps×(t/100)2)个个体进行局部搜索，其中:ps为变邻域搜索参数，Np为种群个体数量，floor()表示向下取整，t为当前迭代次数。图9所示为当ps=0.1时，随着迭代次数的增加，执行局部搜索个体数量的散点图，可以观察到，在算法的开始阶段进行局部搜索个体的数目为0，之后随着迭代次数的增加进行局部搜索个体的数量也增加，并且增长的速度越来越快。该方法可以使算法在开始时不对个体进行局部搜索，而在整个解空间中探索，并在算法的后期对大量的个体进行局部搜索，增加了算法跳出局部最优解的能力，增加了算法的寻优能力。

本文采用的局部算法的流程如下：

输入：K个邻域结构，种群规模Np，当前迭代次数t，当前种群P(t)，变邻域下降参数ps；

输出：当前种群P(t)。

步骤1进行局部搜索个体的数量num=0，进入步骤2。

步骤2判断num是否小于floor(Np×ps×(t/100)2)，若是，则进入步骤3，否则，结束并输出结果。

步骤3在种群中随机选择一个个体，进入步骤4。

步骤4令探索的邻域数量k=1，进入步骤5。

步骤5判断k是否小于等于K，若是，则进入步骤7，否则，进入步骤6。

步骤6用局部搜索后的个体替换种群中的原个体，num=num+1，进入步骤2。

步骤7探索该个体的第k个邻域结构，进入步骤8。

步骤8探索完毕后是否发现改进，若是，则转步骤4，否则，进入步骤9。

步骤9令k=k+1，转步骤5。

本文中采用的邻域结构有内部插入、内部交换、外部插入、外部交换，有两种邻域开发顺序：首次改进方法(Best Improvement, BI)和最佳改进方法(First Improvement, FI)，FI和BI的具体操作参考文献[10]。本文采用的邻域结构设置参考文献[10]，使用了采用BI的内部插入邻域结构、采用FI的内部交换邻域结构、采用BI的外部插入邻域结构、采用FI的外部交换邻域结构。

(1)内部插入邻域结构

随机选取一个有提前、拖后成本的月台，删除该月台上的一个车辆并将其插入到该月台的另一个位置。

(2)内部交换邻域结构

随机选取一个有提前、拖后成本的月台，选取两个位置的车辆并交换两个车辆的作业位置。

(3)外部插入邻域结构

随机选取一个有提前、拖后成本的月台Mj，并随机选取另一个月台Mk。从Mj中选取一个车辆，将该车辆从Mj的作业序列中删除，并插入到Mk作业序列中的一个位置。若有改进或者已经探索完所有可能，则返回解；否则选择另一个未选择过的机器，重复上述过程。

(4)外部交换邻域结构

与外部插入流程相似，不同点在于不是将一个作业插入另一个机器，而是交换两个作业的位置。

3 数值实验

3.1 实验设计

3.1.1 实验环境

本文提出的算法使用Python3.6进行编写，在64位的配置Intel(R)Core(TM)i7-8550u CPU 180GHZ处理器、8GB内存、Windows10操作系统的计算机上编译通过。

3.1.2 实验数据

YANG等[27]针对以最小化总延迟时间为优化目标、有不同到期日和机器相关的设置时间的不相关并行机问题提出了计算实例，WAN等[28]针对有到期时间窗约束的单机调度问题提出了计算实例。本文研究的问题为有作业时间窗约束与车辆—月台兼容性约束的不相关并行机问题，目标为总加权提前、拖后惩罚最小。根据问题的特点，参考以上两个实例的生成方法，形成测试算例。

表2 测试数据参数表

3.1.3 实验设计

学习型混合差分进化算法结合了DE、HH与VND算法，因此，将学习型混合差分进化算法记为DE-HH-VND，并将去掉局部搜索部分的学习型混合差分进化算法记为DE-HH。

(1)参数设置试验

开展正交试验，通过对比不同参数水平下算法性能确定参数的最优水平。

(2)算法设计策略验证实验

对DE-HH-VND、DE-HH与采用不同算子组合的DE进行对比，验证学习型算子选择机制与局部搜索策略的有效性。

(3)性能对比实验

比较DE-HH-VND与DE，验证算法的有效性。对DE-HH-VND与目前企业广泛采用的月台调度规则(FCFS规则)进行对比，验证本文提出的算法的实用性。

3.2 实验结果与分析

3.2.1 参数正交试验

本文提出的算法有4个可控因素，每个因素设置4个水平，并设置一个空列用作误差分析，采用正交表L16(45)。因素水平值取值先通过测试得到较好解的参数取值，然后在该参数附近的区间内设置水平，避免算法计算结果差别过大，因素水平表如表3所示。

表3 因素水平表

使用T=0.3，RDD=1.4的问题算例，共16个实验，每个实验进行10次，种群规模设置为200，种群初始化策略为采用FCFS规则产生一条染色体并随机产生其余染色体，算法的终止条件为最大迭代次数为100代或最优方案适应度值为0，进行局部搜索的条件为进化停滞10代，实验结果为10次实验的适应度平均值，测试结果如表4所示，其中表中的数字分别指因素水平。

表4 参数设置试验结果表

(1)直观分析

直观分析数据，计算各因素不同水平的均值k，计算各因素不同水平均值的极差R，如表5所示。极差R越大因素越重要，可以得出4个因素以及空列的重要程度从大到小为pc>ps>W>pm>空列，空列的重要程度最低说明参数设置实验并没有漏掉其他重要因素，因素之间不存在不可忽略的交互作用。对于每一个因素而言，不同水平的均值k越小，该水平越好，由此可以得出每个因素的优水平分别为水平3、水平4、水平3、水平4，如表5所示。

表5 直观分析表

(2)方差分析

使用方差分析研究4个影响因素对结果的影响，需要计算因素的自由度df、离散平方和SS、均方值MS、计算统计量F，如表6所示。在显著性水平α=0.05下，检验问题的临界值为fα(k-1,n-k)≈9.3，由各因素的F值与临界值进行对比可以得出变异概率pm、交叉概率pc、滑动时间窗长度W、变邻域下降参数ps对实验结果没有显著性影响。由于变异概率pm、交叉概率pc、滑动时间窗长度W、变邻域下降参数ps，对算法的运行时间的影响均可接受，对4个因素分别取4个水平中k值最大的水平。综上所述，确定优方案为pm=0.6，pc=0.8，W=45，ps=0.1。

表6 方差分析表

(3)验证优方案

对优方案进行实验，结果如表 7所示，取10次实验的平均值为57.80，小于等于正交试验中的最优结果57.80，可以确定该方案为此算法的优方案。

表7 优方案实验结果表

3.2.2 算法设计策略验证实验

使用T=0.1，RDD=1.4的实验算例进行实验。分别对DE-HH-VND、DE-HH与DE进行10次实验，其中，DE因为采取不同的变异、交叉操作会产生不同的效果，所以DE算法的实验又分为6个实验，每个实验采取不同的算子组合，采取的算子组合见表1所示，算法的参数取3.2.1节中得出的取值，算法的终止条件为最大迭代次数为150代或最优方案适应度值为0，算法的其他设置均与3.2.1节中的设置相同，计算实验结果的平均值与最优值，实验结果见表8所示，绘制每个算法的收敛曲线，如图10所示。

表8 算法设计策略验证实验结果

由表8和图10可以看出：

(1)DE-HH-VND的结果优于DE-HH，可以得到局部搜索策略增加了算法的寻优能力。

(2)DE-HH结果的平均值优于所有采用不同算子组合的DE，DE-HH结果的最优值优于多数采用不同算子组合的DE，优于“DE+算子组合1”、“DE+算子组合3”、“DE+算子组合4”以及“DE+算子组合6”，差于“DE+算子组合2”、“DE+算子组合5”，可以得到学习型算子选择机制可以在线为算法选择对寻优有帮助的算子组合。

(3)“DE+算子组合2”的结果优于“DE+算子组合1”、“DE+算子组合3”、“DE+算子组合4”、“DE+算子组合5”以及“DE+算子组合6”，可以得到DE算法采用算子组合2的结果优于采用其他算子组合。

3.2.3 性能对比实验

由3.2.2节中的算法设计策略验证实验结果可以得到标准差分进化算法的最佳的算子组合为算子组合2，因此性能对比实验中的标准差分进化算法使用优先操作交叉变异算子与优先操作交叉算子。标准离散差分进化算法的参数设置与本文提出的算法的差分进化部分一样，分别对T={0.1, 0.2, 0.3}，RDD={1.2, 1.4}的小规模与大规模实例进行测试，共12组实验，算法的参数设置与3.2.2节中实验的设置相同，每个实验进行10次，并计算10次实验适应值的平均值与最优值。对比算法与本文提出的算法的结果如表9所示。

表9 性能对比实验结果表

可以得出如下结论：

(1)对于本文中测试的12个算例，DE-HH-VND算法均比DE算法获得了相等或更好的解，可以得出DE-HH-VND具有良好的求解性能。

(2)对于本文中测试的12个算例，DE-HH-VND算法均比目前企业广泛采用的月台调度规则(FCFS规则)获得了更好的解，可以得出DE-HH-VND算法可以帮助企业更好地进行月台调度。

图 11和图 12分别为一个小规模、大规模算例的调度方案甘特图。

4 结束语

本文针对配送中心的月台调度问题进行研究，分析了问题特征，考虑月台—车辆兼容性约束以及车辆作业时间窗约束，建立了以总加权提前、拖后惩罚为目标的数学模型，设计了该问题的编解码方法，并提出一种学习型混合差分进化算法。该算法采用差分进化算法作为框架，结合超启发式算法，提出了学习型算子选择机制，通过学习以前选择算子的经验为算法自动选择对当前优化过程最优的变异算子与交叉算子，并结合变邻域算法作为局部搜索策略，对种群中的部分个体进行局部搜索，帮助算法跳出局部最优解，增加了算法的全局搜索能力。然后，针对问题特征设计了本文研究问题的实验算例，通过正交试验的方法确定了算法的参数的最优水平，通过对比试验证明了学习型算子选择机制与局部搜索策略的有效性，证明了学习型算子选择机制可以为算法自动选择出优秀的算子组合，证明了变邻域算法可以增加算法的全局搜索能力，并与标准差分进化算法和目前企业广泛采用的月台调度规则(先到先服务规则)进行了对比，证明了算法具有良好的优化性能，学习型混合差分进化算法可以帮助企业更好地进行月台调度，提高月台利用率，减少预约车辆的提前作业时间和等待作业的时间，提高企业的服务水平。

接下来可以从以下方面进行后续研究：

(1)对目前提出的算法进行改进，提升算法性能。

(2)考虑动态因素对调度的影响，如车辆没有按照约定时间到达园区、没有进行预约的车辆进行现场预约等因素。