考虑缓冲区容量的岸桥、AGV和堆场起重机集成调度

黄 永 付， 胡 志 华， 王 耀 宗

( 上海海事大学 物流研究中心， 上海 201306 )

0 引 言

随着全球贸易量的持续增长和集装箱船舶大型化的趋势日益明显[1]，在有限的时间和资源约束下优化码头的作业流程来提高自动化集装箱码头(automated container terminal，ACT)的运营效率成为了提高码头核心竞争力的重要手段．与传统码头相比，ACT增加了堆场侧缓冲区，卸船过程中，自动化导引车(automated guided vehicle，AGV)把从岸桥(quay crane，QC)处接来的集装箱运送至缓冲区中存放以等待堆场起重机(yard crane，YC)的执行，此时AGV将被释放去执行其他任务．缓冲区的存在改变了传统码头中AGV和YC、YC和外集卡直接交接集装箱的作业模式，实现了作业设备之间的解耦，对简化ACT的运营过程起到了举足轻重的作用．现实中由于码头场地的限制，缓冲区的容量是有限制的，只有缓冲区中存在空的缓存位时才可接受新的集装箱存放，所以研究缓冲区容量对集成调度过程的影响具有重要的现实意义．

1 研究背景

国内外许多文献研究了ACT装卸设备调度问题，其中包括单一设备调度、两种设备的集成调度和3种设备的集成调度问题，且大多采用群智能算法、启发式算法或两者结合的策略求解．首先，对于单一设备的调度问题，Al-Dhaheri等[2]使用基于仿真的遗传算法求解了QC调度问题．He等[3]提出了集成遗传和粒子群的优化仿真算法，对YC的调度问题进行了求解，遗传算法用于全局搜索，粒子群算法用于局部搜索．Choe等[4]提出了在线优先级学习启发式来求解AGV作业序列，该算法可以动态地调整策略使AGV应对ACT中的变化情况．对于两种设备的集成调度问题，马孙豫等[5]研究并采用多层编码的粒子群算法求解QC与AGV的集成调度问题．Cao等[6]为ACT装货过程中关于集卡和YC的协同调度建立了混合整数规划模型，并使用了Benders 分解方法求解．ACT是一个多装卸设备相互影响和制约的整体[7]，单一设备的调度和两个设备的集成调度只是对ACT的局部优化，只有通过3种设备的集成调度才可以从全局的角度对ACT运营过程进行优化．仲美稣等[8]设计并使用了求解质量和速度更优的启发式混合粒子群算法求解装卸混合模式下的QC、AGV和自动化轨道吊的协同调度问题．Yang等[9]设计基于拥塞预防规则的双层遗传算法有效地求解了考虑AGV路径规划的QC、AGV和YC的集成调度问题．添玉等[7]以最小化船舶在港时间和主要设备作业成本为目标，构建了QC、顶升式AGV和YC集成调度的混合整数非线性规划模型，并提出了启发式遗传算法求解．

ACT是一个多装卸设备统一的整体，堆场侧缓冲区的存在实现了设备之间解耦，简化了码头实际运输过程，具有重要的实际意义，未来对码头更加深入的研究必定会考虑缓冲区的约束[10-11]．针对自动化堆垛起重机(ASC)和AGV的集成调度问题，文家献等[12]以最小化总任务完成时间和总任务延迟时间为目标，考虑了时间窗和缓冲区容量约束，在确定缓存位对任务分配的基础上实现ASC任务序列的优化．秦琴等[11]研究了考虑缓冲区的设备协调调度问题，基于缓冲有限的柔性流水车间调度理论建立了集成调度优化模型，并设计了启发式和遗传算法对问题求解，实验结果表明ACT缓冲区的设置能够有效地提高不同设备之间的作业协调性，显著减少AGV的使用数量与作业完工时间．

本文在研究卸船过程中QC、AGV和YC集成调度问题的基础上，考虑缓冲区的容量约束，以最小化卸船任务完工时间为目标建立混合整数线性规划模型，实现各装卸设备最优作业序列和缓存位-任务的分配，以优化码头设备协调作业，提高AGV利用率和码头运营效率．

2 问题描述

集装箱卸船过程中，当船舶停靠在被分配的泊位，首先QC从船舶指定贝位抓取集装箱并卸载到空载AGV(不考虑QC的中转缓冲区)；然后AGV将穿过水平运输区域把集装箱卸载至目的堆场侧交接缓冲区内的空缓存位中；最后YC从缓存位内提取集装箱并堆存至箱区指定贝位(如图1所示)．在上述过程中，若缓冲区满(缓冲区内无空缓存位)，则带载AGV必须等待空缓存位的出现以卸载集装箱，此时AGV在交接任务时会出现较长的延迟时间，不仅影响AGV利用率，加重水平运输区域压力，还会造成船舶滞留在泊位从而影响码头效率．

鉴于缓冲区的重要作用，本文在传统集成调度问题基础上，考虑缓冲区容量约束，在调度计划生成阶段实现缓存位对任务的最优分配[12]，既保证缓冲区容量的约束，又有利于避免现实码头中AGV因寻找空缓存位造成的等待冲突和交叉冲突现象[13]．设计优先级偏随机密钥遗传算法(priority-based biased random-key genetic algorithm，PBRKGA)和贪婪插入[14](greedy insertion，GI)启发式对问题求解．同时分析缓冲区容量的变化对集成调度过程的影响．

图1 ACT卸船过程示意图

3 模型建立

本文考虑缓冲区容量有限下的集成调度问题，以最小化卸船任务完成时间为目标，建立混合整数线性规划模型，确定并优化装卸设备QC、AGV和YC的作业序列、任务作业时间和缓存位-任务的分配关系，保证调度计划的最优性．鉴于ACT集成调度过程的复杂性，为了简化问题的分析，在建模过程中做出如下假设：(1)任务的起始位置和目标位置在调度计划开始前已确定；(2)每个箱区只使用一个YC作业；(3)不考虑岸桥中转平台，QC与AGV直接交接集装箱；(4)AGV 匀速直角行驶，不考虑加减速和冲突死锁现象．优化模型的相关符号定义如下：

集合

Q：QC集合，q∈Q．N1为QC个数．

K：AGV集合，k∈K．

B：YC或缓冲区集合，b∈B．

参数

决策变量

xij：0-1变量；若QC依次执行i、j，则xij=1；否则，xij=0．

ykij：0-1变量；若AGVk依次执行i、j，则ykij=1；否则，ykij=0．

lki：0-1变量；若AGVk执行i，则lki=1；否则，lki=0．

wsi：0-1变量；若i被分配给缓存位s，s∈S，则wsi=1；否则，wsi=0．

uij：0-1变量；若i比j先分配给缓存位s，s∈S，则uij=1；否则，uij=0．

数学规划模型及其说明如下：

(1)

(2)

(3)

(4)

(5)

式(1)为最小化作业完工时间的目标函数．式(2)～(5)是QC调度约束．其中式(2)和(3)是流量平衡约束，式(4)表示QC执行相邻任务的时间逻辑，式(5)表示QC执行一个任务的时间逻辑．

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

式(6)～(13)是AGV调度约束．其中式(6)～(8)是流量平衡约束；式(9)表示AGV执行相邻任务的时间逻辑；式(10)表示每个任务只能被一辆AGV执行一次；式(11)表示若某任务被分配给AGV，则该任务一定有一个后继任务；式(12)表示AGV执行一个任务的时间逻辑；式(13)表示QC和AGV直接交接任务．

(14)

(15)

(16)

(17)

(18)

式(14)～(18)是YC的调度约束．其中式(14)和(15)是流量平衡约束；式(16)表示YC执行相邻任务的时间逻辑；式(17)表示YC执行一个任务的时间逻辑；式(18)表示由于缓冲区的存在，AGV和YC不直接进行任务的交接．

(19)

(20)

(21)

(22)

(23)

(24)

式(19)～(23)是缓冲区容量约束，实现缓存位对任务的分配．其中式(19)表示每个任务只分配给一个缓存位；式(20)表示被分配给缓存位的任务一定有任务在其后执行；式(21)和(22)表示若两个任务被分配给一个缓存位，则这两个任务一定存在着先后关系；式(23)表示任务进入缓存位的时间逻辑．式(24)是决策变量取值范围．

4 算法设计

ACT集成调度问题属于NP-hard问题[15-16]，缓冲区容量约束加深了问题的复杂性，精确算法难以对问题求解．遗传算法寻优过程中的随机性和自适应性使其能够有效且鲁棒地求解多类组合优化问题．启发式算法虽不能保证解的质量，但因其能够快速求解问题而得到了广泛的应用．本文将研究使用遗传算法和启发式算法对问题求解．

4.1 优先级偏随机密钥遗传算法

基于优先级编码的遗传算法可根据实际问题对需要执行的任务进行优先级排序，染色体上的权值对应任务执行的优先级顺序，可以有效避免非可行解的产生，更符合实际应用，从而使遗传算法求解实际问题的过程更加简单、直接[17]．Lotfi等[18]提出了基于优先级的遗传算法求解固定成本运输问题，求解结果表明该算法在求解中、大型问题的质量和计算时间方面提供了更好的结果．Xu等[19]提出了多优先级排序遗传算法求解异构计算系统的任务调度，计算结果表明该算法在调度质量方面优于两种非进化启发式和随机搜索算法．Jamrus等[20]提出了基于优先级的混合遗传算法求解集装箱运输过程中出现的并箱装载问题，求解结果证明了所提算法的实用可行性．

基于随机密钥编码策略的遗传算法是基于0-1的随机数构成一条染色体，生成问题的一个可行解，通过解码操作来对应解空间内的一个解，相比于传统的遗传算法具有操作简单、收敛速度快和全局寻优能力更好的优点[21]．偏随机密钥遗传算法在交叉操作中采取随机选择的方式选取上一代种群中最优的数个个体中的一个作为当前交叉操作的一个父代，这种交叉方式产生的后代相比于随机密钥遗传算法交叉算子产生的后代更能保存当代种群的优良基因，加快收敛并提高解的质量[22]．Lalla-Ruiz等[23]通过使用偏随机密钥遗传算法求解战术泊位分配问题，通过实验结果的比较得出该算法能够有效地解决所提问题和必要的集装箱码头的其他问题．Lalla-Ruiz等[24]提出了一种基于偏随机密钥遗传算法框架的QAP混合近似方法求解二次分配问题，能在较短的计算时间内得出高质量的解决方案．Correcher 等[25]把偏随机密钥遗传算法用于时不变泊位分配和码头起重机分配问题，结果表明该算法能够为多达40艘船舶的算例找到最佳解决方案，并为多达100艘船舶提供良好的解决方案．Ruiz等[26]使用偏随机密钥遗传算法有效地求解了带有容量和距离约束的车辆路径问题．

本文结合优先级编码策略和偏随机密钥策略设计了优先级偏随机密钥遗传算法．算法分为染色体编码、染色体解码、适应度函数、遗传算子(选择、交叉和变异)和终止准则5个部分．算法流程如下：

步骤1随机生成种群规模为N3的初始种群P，每个个体采取0-1的随机实数编码；

步骤2对P解码生成PD，基于PD计算每个个体p∈P的适应度值f(p)；

步骤3While 不满足终止准则 do

步骤3.1对P执行选择操作，生成P；

步骤3.2对P执行交叉操作，生成P；

步骤3.3对P执行变异操作，生成P；

步骤3.4对P解码生成PD，基于PD计算每个个体p∈P的适应度值f(p)；

步骤3.5End while

(1)染色体编码

染色体采用基于优先级随机密钥编码方式，染色体长度为N2，基因位置为任务编号，基因位的权值由0-1随机实数表示，权值的大小为对应基因位置编号任务被执行的优先级大小(权值越小优先级越大)．如图2(N2=10)中的任务3的优先级最高，任务10的优先级最低，任务1的优先级大于任务2的优先级．

染色体0.620.730.010.590.460.030.320.060.160.89任务编号12345678910

(2)染色体解码

根据染色体基因位权值的大小将染色体解码，生成基于任务优先级排序的任务序列．按照优先级大小排序，从左至右任务优先级由高变低(权值依次增大)．解码过程如图3(N2=10)所示．

图3 染色体解码示意图

(3)适应度函数

设计顺序插入算法[14]作为适应度函数．算法以解码任务序列p∈PD为输入，顺序迭代执行p中的任务，输出p的完工时间f(p)．迭代过程中，使用三维向量νd表示当前设备d∈Q∪K∪B∪S的状态，设备当前时刻执行的任务i、执行任务i的开始时间ti和结束时间ei．随着任务不断被迭代执行，设备d的状态也在不断地更新．算法流程如下：

(3)p：任务序列．

输出f：任务序列完工时间．

变量νd=(itiei)：表示设备QC、AGV、YC和缓存位的状态向量，其中ti和ei分别表示设备d∈Q∪K∪B∪S执行任务i的开始时间和结束时间．

步骤2For ∀i∈p

步骤2.5End for

(4)遗传算子

在交叉操作(图4)中，首先为每个个体p∈P分配一个随机实数c1∈(0，1)，选择c1小于交叉概率pc的所有个体组成P1；其次，选择当前种群最优的10%的个体组成P2；然后，选择V1∈P1作为父代1，随机选择V2∈P2作为父代2，生成0-1的长度为N2的随机数向量c；最后，计算可得子代X=(1-c)V1+cV2，Y=cV1+(1-c)V2．

父代10.620.730.010.590.460.030.320.060.160.89父代20.760.350.680.420.830.180.300.070.090.39随机数向量c0.310.590.980.290.680.850.330.890.550.01子代X0.660.510.670.540.710.160.310.070.120.89子代Y0.720.570.020.470.580.050.310.060.130.40

对于变异操作(图5)，为每个个体p∈P分配一个随机实数c2∈(0，1)，选择c2小于变异概率pm的染色体p执行变异操作，即使用随机实数c3∈(0，1)替换p中随机选择的基因位的权值．

图5 染色体变异示意图

(5)终止准则

使用频率控制原则作为算法的停止准则，即算法不断迭代中，最小值出现次数为N4时，算法停止．

4.2 贪婪插入启发式

5 数值实验

5.1 实验设置

(1)根据洋山港四期ACT垂直海岸线分布的特点，随机生成一系列由集装箱任务及其所在船和堆场的贝(bay)、排(row)、层(tier)和位置坐标(X/m、Y/m)组成的数据集．贝位的长度为13 m，宽度为2.7 m．集装箱位置坐标由集装箱的重心表示．

(2)QC和YC的行驶速度为2 m/s，抓放箱的时间是10 s；AGV以4 m/s的速度沿直角匀速行驶；不考虑QC、YC和AGV的空载和满载速度的变化．不考虑集装箱的翻箱操作．

(3)以集装箱所在箱区贝位的X坐标为YC和AGV交接集装箱的X坐标．

(4)为了提高算法的运行效率，本文通过多组实验确定PBRKGA的相关参数[7]，种群规模N2=40，交叉概率pc=0.8，变异概率pm=0.2，频率控制参数N4=200．本文实验采用Python 2.7.16 编程实现，并在Intel Core i5-8250U CPU @1.60 GHz、1.80 GHz处理器、8 GB内存的笔记本上运行得到实验结果．

5.2 实验设计与分析

基于生成的数据集和实验设置，设计了如表1所示的3组实验，分别用来验证模型和算法的有效性，揭示算法PBRKGA求解性能，分析缓冲区容量对集成调度过程的影响．

表1 实验设计

从表2中可以看出，随着算例规模的增大，Gurobi求解难度不断增加，且缓冲区的变化也影响着Gurobi的求解难度．PBRKGA可以高效地对问题求解．GI启发式可以快速地对问题进行求解，但求解质量不如PBRKGA．

表2 Gurobi、PBRKGA和GI的求解结果对比

表3是PBRKGA求解算例I6所得到的缓存位-任务的分配关系．

表3 缓存位-任务的分配

图6是PBRKGA求解算例I6-c的算法迭代收敛图．横坐标表示迭代次数，纵坐标表示目标值．从图6中看出PBRKGA可以快速地对算例求解．

图6 PBRKGA迭代收敛图

如图7所示，随着任务数量的增多，缓冲区容量的增加可以逐渐缩短QC完工时间．QC完工时间的减少可以缩短船舶在港时间，提高ACT运营效率．所以适当的缓冲区容量可以缩短集装箱船舶在港时间，提高ACT运营效率．

图7 缓冲区容量对QC完工时间的影响

AGV经过水平运输区域将任务集装箱运送至缓存位存储，若缓存位满，AGV会等待空缓存位以放置集装箱，就会产生AGV交接任务时的延迟时间，延迟时间的存在会降低AGV利用率．如图8所示，随着缓冲区容量的增大，AGV交接任务的延迟时间减少，因此适当的缓冲区容量有利于减少AGV延迟时间，提高AGV利用率．此外，缓冲区容量的增加可以降低AGV完工时间，提高AGV利用率，降低ACT水平运输压力，实验结果如图9所示．

图8 缓冲区容量对AGV延迟时间的影响

图9 缓冲区容量对AGV完工时间的影响

6 结 语

自动化集装箱码头的关键设备集成调度有利于缩短船舶在港时间，提高码头整体作业效率．本文在现有研究的基础上，构建考虑实际码头缓冲区容量限制的集成调度模型，并设计优先级偏随机密钥遗传算法(PBRKGA)进行求解，创新之处在于：引入了缓冲区容量约束，建立码头3种关键设备集成调度的混合整数规划模型；设计优先级策略和偏随机密钥策略进行编码，同时提出顺序插入算法作为适应度函数计算目标值．算例实验验证了模型和算法的正确性和有效性，可为描述和求解其他组合优化问题提供理论指导，同时还得出适当的缓冲区容量能够缩短船舶在港时间，降低水平运输压力，提高AGV利用率．

本文的不足之处在于：PBRKGA的寻优策略有待改进，以提升算法的求解性能；仅考虑了卸船过程的集成调度问题．未来将进一步研究使用混合算法或找寻求解质量高且求解时间更快的算法，探讨装卸同时存在的考虑缓冲区容量约束的集成调度问题．