高银萍,苌道方*,陈俊贤
(1.上海海事大学 物流科学与工程研究院,上海 201306;2.南洋理工大学 机械与宇航工程学院,新加坡 639798 新加坡)
在“一带一路”建设中,港口承担着举足轻重的作用,近年来中国集装箱吞吐量一直稳居世界第一,但是逐步增长的集装箱吞吐量给码头发展带来了压力,也对码头运营提出了更高要求。随着物联网、计算机通信等技术的发展与成熟,自动化码头成为码头发展的必然趋势,自动化设备的投入提高了码头生产的安全性。由于人的决策减少,智能系统制定的决策并不能应对实际作业过程中发生的不确定场景。交通事故、拥堵等不确定场景的干涉,外集卡的到达时间具备动态性,而根据外集卡预计到达时间制定的自动堆垛起重机(Automated Stacking Crane,ASC)作业计划难以适用,如何调整优化ASC 与外集卡的作业成为提高堆场作业效率的关键问题。
ASC 是自动化集装箱码头堆场内用于处理集装箱的装卸设备,而大多传统码头采用的装卸设备主要是轮胎式起重机,有些文献中也将这类装卸设备称为场桥。目前针对场桥调度的文献主要有:范厚明等[1]针对出口箱区分配问题,提出分区域平衡策略,在此基础上研究了出口箱区多场桥联合作业问题,以场桥的移动成本和空闲成本最小为目标,结合模拟退火算法与遗传算法(Genetic Algorithm,GA)求解该问题。Wu等[2]提出了箱区内多场桥的调度,考虑场桥间的交叉作业、安全距离等约束,以集卡等待时间最短为目标建立连续时间模型,并设计启发式算法求出近似解。Han等[3]研究了自动化码头箱区内双ASC 调度问题,总结了ASC 作业干扰的四种模式,并以完成所有作业需求的时间最少为目标,建立混合整数规划模型,同时设计遗传算法求解,验证了其在大规模算例上的优越性。Kress等[4]在保证陆侧集装箱能准时处理作业的同时,考虑陆侧与海侧轨道式起重机之间的非交叉约束,最小化海侧集装箱的作业时间。Speer等[5]将自动化起重机的移动和干涉等作业特征列入自动化起重机调度算法的考虑因素中,根据实际作业场景中的数据构建仿真模型,以自动化起重机效率和任务的平均作业时间为评价指标,比较了四种不同的自动化起重机系统在码头的作业效率。Gharehgozli等[6]以完成所有任务时间和ASC 等待时间最少为目标,根据ASC 调度方式、集装箱堆存位置、交互区域位置等决策变量设计多种启发式算法,通过仿真实验研究了箱区内交互区域对ASC 性能的影响。
在混合堆存集装箱码头中,Yu等[7]建立混合整数线性规划模型,以集卡等待成本和等待造成的惩罚成本最小为目标,设计滚动时域算法来优化场桥调度。郑红星等[8]研究混堆模式下多场桥调度问题时,考虑了多场桥间的作业约束与内集卡的等待时间,以内集卡等待时间和场桥移动成本最小为目标构建数学模型,并设计改进的遗传算法进行求解。之后郑红星等[9]进一步研究了外集卡提箱时间不确定时多场桥的调度问题,以码头作业成本与倒箱量最小为优化目标,提出滚动时域算法,同时在每个时域中采用嵌入倒箱策略的遗传算法,得出各时间段内场桥的调度方案。
关于不确定调度的研究有:周磊磊等[10]提出了不确定干扰时外集卡提箱策略,运用滚动窗口再调度机制优化集装箱的作业顺序。针对出口箱交箱时间不确定性时的场桥调度问题,邵乾虔等[11]运用马尔可夫链对交箱序列预测:第一阶段构建翻箱次数最小的模型,设计模拟退火算法进行求解;第二阶段构建场桥移动距离最小的模型,提出实时调度算法,即根据出口箱实际到达时间与预测序列,修正预测序列,进行实时堆存与调度。Zheng等[12]采用两阶段随机规划来解决提箱任务时间不确定下的单场桥调度问题,设计基于规则的启发式算法,验证其求解大规模问题的性能。He等[13]提出了集装箱作业任务的到达时间和作业量等信息不确定时的场桥调度问题,通过最小化因不确定因素导致任务完成时间的延误成本和额外损失,设计了基于遗传算法的三阶段算法,求解不确定场景下场桥的作业顺序。Zeng等[14]研究了集卡到达信息部分已知情况下的集装箱作业优化问题,以集装箱翻箱量最小为目标,优化了集装箱作业顺序和翻箱计划,并设计了五种启发式算法求解该模型。马梦知等[15]就送箱集卡随机到港问题,提出送箱集卡预约和场桥调度协同优化,以集卡排队等待时间、集卡调整数量、所有时段内未完成任务所需要场桥的作业时间和每个时段内未完成任务所需要的时间最小为目标,构建双层规划模型,设计并行遗传算法求解。为了应对集卡司机与码头之间的信息缺失问题,李娜等[16]在集卡预约问题中,以集卡预约提箱配额为研究对象,最小化箱区配备的场桥数量和箱区内集卡的平均等待时间,并设计运用非支配排序遗传算法Ⅱ(Non-dominated Sorting Genetic Algorithm Ⅱ,NSGA Ⅱ)求解。Kucuksayacigil等[17]在求解双目标资源约束的调度问题时,改进了NSGA Ⅱ并验证了其优越性。
在集装箱码头堆场装卸设备的研究中,包含了单场桥、多场桥之间的调度,并考虑了场桥间的作业约束,以场桥作业时间和集卡等待时间最小为优化目标,采用遗传算法等智能优化算法进行求解,而在研究ASC 不确定调度时很少考虑进出口集装箱混合堆存模式的堆场特征。在实际作业过程中,动态变化的作业场景会影响ASC 效率,例如,外集卡延迟或提前进场会对实现制定的ASC 作业计划产生干扰。若外集卡因交通状况等因素不能按预计时间抵达堆场,原先计划作业的ASC 会出现等待时间长、无作业等现象,因此需要根据场景变化实时调整ASC 作业计划,避免ASC 空待、外集卡等待等不必要成本。
因此,本文综合考虑ASC 处理不同类型集装箱的需求,以自动化码头混合堆存模式的堆场为研究对象,探究外集卡进场时间动态变化场景下ASC 作业优化问题,并建立了最小化ASC 作业时间和等待时间的双目标混合整数规划模型,设计了基于动态规则的非支配排序遗传算法Ⅱ(Nondominated Sorting Genetic Algorithm Ⅱ based on Dynamic Rules,DRNSGA Ⅱ)求解。
自动化码头混堆模式下进出口集装箱堆放在同一箱区,箱区内分别有两台自动堆垛起重机(ASC)完成进出口箱的作业,进口集装箱堆放在箱区陆侧,出口集装箱则堆放在箱区海侧,箱区中间为进出口集装箱暂存区,而靠近陆侧的ASC 负责外集卡的装卸集装箱任务,靠近海侧的ASC 则负责AGV 的装卸集装箱任务。外集卡进入堆场主要有三种作业需求:一是空集卡进入堆场提箱,箱区靠近陆侧的ASC 提起进口集装箱,装至空集卡上,集卡重载离开;二是重集卡集港,陆侧ASC 卸载集卡上的出口集装箱,将该集装箱放置在箱区的暂存区,海侧ASC 将此集装箱从暂存区提到出口箱区,集卡空载离开;三是重集卡重进重出,重集卡载出口集装箱进场,陆侧ASC 卸载出口集装箱后,再从暂存区移动到陆侧进口箱区,提起进口集装箱,装至空集卡上,集卡载进口箱离开。外集卡进场作业示意图如图1 所示。
在实际作业过程中,外集卡不在码头运营管理范围内,且容易受到码头外部道路交通状况影响,无法按照预计时间抵达堆场,影响外集卡准确到达率。外集卡早于预计时间或晚于预计时间进入堆场,均会干扰码头制定的堆场计划,影响箱区内ASC 作业次序。若外集卡早于预计时间到达码头,原计划为其指定的ASC 可能正在作业,不能为其服务,该集卡则需要在闸口处等待,影响闸口处的道路通畅;若外集卡晚于预计时间到达码头,原计划为其指定的ASC 只能等待,导致设备能耗高。因此,外集卡动态到达场景对码头的运营与成本管理具有负面影响,在此场景下,有必要动态调整ASC 作业任务。
根据混堆模式下不同外集卡作业需求,在外集卡到达时间具有动态性的场景下,研究ASC 作业序列优化问题,并制定了两个优化目标:一是ASC 总作业时间最短,二是ASC 和外集卡的等待时间最短。第一个优化目标的影响因素:一是两台ASC 的干扰,两台ASC 不能相互跨越和相邻太近;二是ASC 等待外集卡,因外集卡延误ASC 无法作业。第二个优化目标的影响因素:一是ASC 等待外集卡;二是外集卡等待ASC。在本文问题中,堆场每个箱区均有一台ASC 专门服务于外集卡,包括集港、提箱等业务需求,各箱区内包含多个贝位,从陆侧至海侧方向按照编号计数,且每个箱区的贝位数相同。出于安全考虑,相邻箱区的ASC 不能同时作业同一贝位,如图2 所示,以防发生碰撞等状况,相邻ASC 作业时需保持一定的安全距离。
1.2.1 模型假设
1)ASC 作业任务由堆场计划给定,包括ASC 处理的集装箱所在贝位等信息;
2)每台ASC 移动速度相同,作业效率相同;
3)不同箱区的ASC 不能相互跨越,相邻ASC 作业的贝位需要留有两个贝位的安全距离;
4)外集卡预计到达时间已知;
5)所有作业集装箱均为普通标准箱;
6)ASC 作业1 辆外集卡即视为1 次作业任务,为一个工序;
7)作业过程中不存在翻箱作业,ASC 可以直接处理目标箱;
8)开始时间计为0 时刻。
1.2.2 数学符号定义
1)参数设置。
B:箱区集合;
A:贝位集合,a∈A;
K:外集卡集合,k∈K;
C:ASC 集合,c=1,2,…,C;
N:任务总数,n=1,2,…,N;
Tk:外集卡k预计到达时刻;
:ASCc处理外集卡k作业时长;
t:ASC 驶过一个贝位的时长;
ωe:权重;
ωl:权重;
2)变量。
:ASCc完成外集卡k任务的时刻;
:ASCc开始处理外集卡k任务的时刻;
:ASCc早于外集卡k开始作业的时长;
:ASCc晚于外集卡k开始作业的时长;
1.2.3 目标函数建立
其中:式(1)表示ASC 完成所有作业时间的最小化;式(2)表示ASC 完成集卡任务的时间;式(3)表示ASC 与外集卡两者等待时间的最小化。
1.2.4 约束条件建立
其中:式(4)表示每个贝位a只能由一台ASC 进行作业;式(5)表示每个外集卡的作业箱只在一个贝位处;式(6)表示ASC 在第n个工序时的作业状态;式(7)~(8)表示每台ASC分工作业,完成所有外集卡k的作业箱在贝位a处的任务;式(9)~(10)表示ASC 在一个工序n里只能完成一个集卡k的作业任务;式(11)表示每台ASC 只有处理了第n个工序,才有可能处理第(n+1)个工序;式(12)表示ASC 开始处理外集卡k作业的时刻至少要大于等于该ASC 之前所有工序的作业时间和工序间的移动时间之和;式(13)表示ASC 在两相邻工序的开始时间之差至少要大于等于该ASC 在两工序间的移动时间以及前一工序的作业时间之和;式(14)~(15)表示两台相邻ASC 的作业位置需要保持两个贝位的安全距离;式(16)~(17)表示ASC 早于和晚于外集卡的等待时长。
在求解多目标优化问题时,非支配排序遗传算法Ⅱ(NSGA Ⅱ)表现出较好的性能[18],NSGA Ⅱ在执行选择、交叉、变异等遗传操作之前,对种群中的个体进行分层排序,确定支配与非支配关系,促使好的个体有更大的机会遗传到下一代中。同时,NSGA Ⅱ中提出了个体的拥挤度来保证种群的多样性,允许父代种群与子代种群的组合,便于父代中优良个体的遗传,因此降低了计算复杂度并尽可能保留满意解。结合混堆模式下集装箱的作业需求与外集卡动态到达的特征,提出ASC 作业序列的优化策略。
本研究设计了DRNSGA Ⅱ进行模型求解,首先初始化种群,当作业任务与计划发生偏差时,依据相同类型任务可替换的规则为ASC 安排新的任务序列,保证初始解的可靠性;其次对个体进行非支配排序及遗传操作,产生子代种群;然后组合父代种群和子代种群,对其非支配排序和拥挤度计算,选出合适的个体作为新的父代种群,进行选择、交叉、变异的遗传操作;最后通过父代与子代种群的迭代进化,保留每一次的合适个体,找到全局最优解。本文所提DRNSGA Ⅱ流程如图3 所示。
以ASC 处理外集卡的工序编号作为编码方式,每条染色体的长度为ASC 处理外集卡的任务总量与ASC 数量之和,染色体的第一部分包含每台ASC 处理任务的编号,第二部分则是每台ASC 处理的任务量,染色体的编码方式如图4 所示,该条染色体表示有6 个任务和2 台ASC,且ASC1 处理编号为1、2、3 的任务,ASC2 处理编号为4、5、6 的任务。
生成初始解时,将所有任务量随机分配给ASC,保证每台ASC 均有任务可做。根据染色体信息,可获取每个任务对应外集卡的预计到达时间和作业需求,由于外集卡到达时间动态变化,需要对相关任务的染色体按照一定规则进行动态调整。动态策略的伪代码如下所示。
首先,确定外集卡抵达堆场的时间,若外集卡晚于预计到时间抵达堆场,则判断计划为该集卡分配的ASC 是否空闲。如果该ASC 正在作业,那么ASC 继续完成作业并等待迟到的外集卡;如果ASC 空闲,那么在已到达的外集卡中寻找与迟到外集卡作业需求相同的替补外集卡。迟到外集卡的情况示例如下:
1)若迟到外集卡为空车进港提箱,判断已到外集卡中是否有进入该ASC 所在箱区内提箱的作业需求。若有相同需求的替补外集卡,优先安排ASC 为有相同提箱需求的替补外集卡作业;否则在已到外集卡中寻找是否有进入该ASC 所在箱区集港需求的外集卡。若有,则安排ASC 为其作业;否则在已到外集卡中寻找是否有需要进入该ASC 所在箱区集港提箱(重进重出需求)的外集卡。若有,则安排ASC 为其作业;否则此ASC 只能等待外集卡。需要说明的是,在寻找迟到外集卡的替补集卡时,因重进重出作业时间长,ASC 优先为与延误外集卡有相同作业需求的已到外集卡服务,最后考虑重进重出作业的外集卡。只要已到达集卡池中有满足进入该ASC 作业需求的外集卡,则安排ASC 为其作业,避免ASC 等待。
2)若迟到外集卡为重车集港,判断已到外集卡中是否有进入该ASC 所在箱区内集港的作业需求。若有相同需求的替补外集卡,优先安排ASC 为有相同集港需求的替补外集卡作业;否则在已到外集卡中寻找是否有需要进入该ASC 所在箱区提箱需求的外集卡。若有,则安排ASC 为其作业;否则在已到外集卡中寻找是否有需要进入该ASC 所在箱区集港提箱(重进重出需求)的外集卡。若有,安排作业;否则此ASC 只能等待外集卡。
3)若迟到外集卡为重进重出需求的集卡,判断已到外集卡中是否有进入该ASC 所在箱区内重进重出的作业需求。若有相同需求的替补外集卡,首先安排ASC 为有相同需求的替补外集卡作业;否则在已到外集卡中寻找是否有需要进入该ASC 所在箱区集港需求的外集卡。若有其他集港需求的替补外集卡,则安排ASC 为其作业;否则在已到外集卡中寻找是否有需要进入该ASC 所在箱区提箱的外集卡,有则为其安排ASC 作业;否则此ASC 只能等待外集卡。需要说明的是,因迟到外集卡的作业需求是重进重出,所以首先安排有相同需求的替补外集卡进场作业,最小化ASC 为原计划外集卡服务和为替补外集卡服务的时间差;其次安排有集港需求的替补外集卡作业,以满足出口箱装船业务;最后考虑安排有提箱需求的外集卡作业。
根据适应度函数fit(f)=比较任意两个染色体的目标函数值,若染色体1 对应解的目标函数值均优于染色体2的对应解,则称染色体1 的对应解支配染色体2 的对应解,且染色体1 对应解为非支配解,对个体进行非支配排序。对于每个目标函数f,个体i拥挤度ni=按拥挤度从大至小排序并依次选取合适个体作为新种群。
交叉操作主要分为两部分,分别对染色体的前后两部分做交叉,交叉过程如图5 所示。在第一部分任意选取两个位置,交换两条染色体所选位置之间的基因,第一步所选两条染色体的基因为3 和1,交换两条染色体前半部分中的3 和1,第二步所选两条染色体的基因为4 和1,交换两条染色体前半部分中的4 和1,第三步所选两条染色体的基因为5 和6,交换两条染色体前半部分中的5 和6;第二部分则选取两个位置,交换ASC 的作业量。
变异操作的第一步是交换染色体第一部分的任意两个基因,第二步是交换任意两台ASC 的作业量,变异过程如图6 所示。
经过交叉、变异操作后,产生的新种群可能会出现不可行解,则需要对其进行基因修复,若两相邻ASC 同一时刻作业的集装箱所在贝位不满足安全距离的约束,可将其中一台ASC 的任务转移给另一台ASC 作业,即染色体第二部分ASC的作业量做增减变化。
根据Hu等[19]研究实验中的参数设置生成算例,设置种群大小为100,交叉概率为0.9,变异概率为0.3,最大迭代次数为500。根据某港口运营数据,设置外集卡延迟到达和提前到达的比例分别为0.8 和0.2。本文算法编写软件为Matlab R2016b,运行环境为Intel Core i5 处理器、内存4 GB。
任务量为20 的算例求出的非支配解函数值如图7 所示。图7 中(f1,f2)为目标函数值,f1为ASC 总作业时间,f2为ASC与外集卡的等待时间。非支配解的作业方案如表1 所示。
表1 中是所求非支配解对应的ASC 作业方案:第一组方案中每台ASC 作业量分别为5、8、5、2;第二组方案中每台ASC 作业量分别为5、2、7、6;第三组方案中每台ASC 作业量分别为5、5、4、6;第四组方案中每台ASC 作业量分别为3、6、5、6;第五组方案中每台ASC 作业量分别为4、6、3、7;第六组方案中每台ASC 作业量分别为4、6、8、2;第七组方案中每台ASC 作业量分别为6、4、4、6。
表1 非支配解作业方案Tab.1 Operation schemes of non-dominated solutions
根据外集卡动态到达场景,本文提出ASC 动态匹配外集卡作业任务的策略,并将其与ASC 随机处理外集卡作业任务的策略对比,不同策略下算例求解结果如图8 所示。整体上看,虽然存在动态策略下部分非支配解结果大于随机策略的结果,但动态策略下得出的非支配解大多在随机策略下的左下方,解的质量明显优于随机策略所得结果,验证所提动态策略的有效性。这是由于针对外集卡到达时间的动态性,本文提出了动态策略即动态调整ASC 所服务的外集卡作业工序,避免了因外集卡未在预计到达时间内进场作业导致车辆与设备的较长等待,尽可能保证ASC 不间断作业,提高了ASC 作业效率。
为了验证DRNSGA Ⅱ在求解本问题时的有效性,在任务量为20、50、80 的不同规模问题下,生成10 个算例,进行多次实验。实验1 是采取ASC 动态调整作业任务策略下运用DRNSGA Ⅱ进行求解;实验2 采取动态策略和运用GA 求解;实验3 采取随机策略运用DRNSGA Ⅱ进行求解;实验4 采用随机策略和运用GA 求解。各算例实验结果如表2 所示。F1~F4为4 组实验的目标函数值(f1,f2),T1~T4为4 组实验的计算时间,P1~P3为实验1 与其他3 组实验之间的差值,
表2 四组实验结果Tab.2 Results of four experiments
差值P1是动态策略下不同算法的比较,差值P2是运用DRNSGA Ⅱ求解时动态策略与随机策略的对比,P1与P2的平均值均随着算例规模的增加而变大,可见本文提出的DRNSGA Ⅱ在求解大规模问题上的优越性;且P2的平均值大于P1的平均值,表明动态策略的选择对优化结果的影响更加突出。实验结果表明,DRNSGA Ⅱ求解的动态策略下目标函数值优于随机策略28.2%,并且动态策略下DRNSGA Ⅱ的求解结果优于遗传算法23.3%。差值P3是不同算法和不同策略的比较,P3的平均值大于P1的平均值和P2的平均值,可见采取随机策略时运用GA 求解该问题产生的误差更大。
实验1 在任务规模为20、50、80 条件下的平均计算时间分别106.54 s、165.28 s 和299.67 s,时间效率均优于其他3组实验,且所求目标函数值优于其他解;实验2 采取与实验1相同的算例,但运用GA 求解,其计算效率与目标函数值均次于DRNSGA Ⅱ求解的实验1。区别在于实验1 和2 采取动态策略,实验3 和4 选择随机策略,同等条件下的算例结果与前两组结果有较大差距,ASC 作业时间与设备等待时间得到了优化,表明本文所提动态策略的优越性。
在算法求解性能上,DRNSGA Ⅱ求解的目标函数值均优于传统GA 的求解结果,且随着算例规模的增加,DRNSGA Ⅱ的优势较为明显。在算法运行时间上,两种算法中各算例求解时间的差距较小,这可能是由于DRNSGA Ⅱ中加入了生成初始解的启发式规则,且相较于传统GA,为保证解的多样性,DRNSGA Ⅱ中包含对所有个体的非支配排序,增加了算法复杂度,从而需要的运行时间较长,但是整体上,DRNSGA Ⅱ中每组算例计算时间效率均优于GA。由此表明,针对外集卡动态到达场景下ASC 的作业优化问题,本文提出DRNSGA Ⅱ的求解效果优于传统GA。
在任务量为100、150 和200时,进行多次实验,表3 中给出了算例结果中最优、最差与平均数据,用于比较DRNSGA Ⅱ与多目标粒子群优化(Multi-ObjectiveParticle Swarm Optimization,MOPSO)算法在解决本文问题时的性能。
表3 DRNSGA Ⅱ与MOPSO算法的对比结果Tab.3 Comparison results of DRNSGA Ⅱ and MOPSO algorithm
不同任务规模时,本文所提DRNSGA Ⅱ求解的目标函数值与计算时间效率均优于MOPSO 算法的结果,任务量增加后,两种算法在求解目标函数值差值的平均值也逐渐由2.8% 增加到6.7%,算法的计算时间也在增长,而DRNSGA Ⅱ的计算时间少于MOPSO 算法,这是由于提出的动态调整策略有利于寻找最优目标函数值的过程。
图9 以散点图模式描述了不同任务量时两种算法的求解结果,任务量为100 和150时,两种算法求出的目标函数值的散点很接近,差距较小;任务量为200时,目标函数值的散点距离增加,从整体增长趋势来看,任务量增加,算法性能差异也有所凸显。通过3 组不同规模的算例实验,验证了本文所提算法在求解本问题时的优势。
本文研究了混堆模式下自动化码头外集卡动态到达场景下ASC 作业优化问题,构建了ASC 作业时间最短和ASC 与外集卡等待时间最短的多目标模型,结合外集卡到达时间动态性的特征,设计了DRNSGA Ⅱ进行求解。由于外集卡到达码头的时间具有不确定性,为了避免此种场景给码头作业效率带来的影响,设计堆场ASC 动态作业的规则,并将这种动态策略嵌入到NSGA Ⅱ中。通过算例验证,根据动态策略制定的ASC 作业方案优于随机策略,ASC 总作业时间及设备的等待时间都有缩减,同时比较了DRNSGA Ⅱ、传统遗传算法与MOPSO 算法在求解本问题时的性能,得出本文方法在求解结果和计算时间效率上的优越性。
传统的场桥作业问题,大多考虑进出口集装箱分开堆存时场桥的优化。而本文提出进出集装箱混合堆存时自动化码头的ASC 作业优化问题,并结合外集卡进场时间的不确定性,根据进出口集装箱不同的作业需求,研究ASC 动态优化。未来的研究会进一步考虑混堆箱区内的翻箱作业,将翻箱量列入ASC 作业优化中,研究混堆模式下翻箱量与作业时间等多目标的ASC 优化问题。