包晓琼，鹿飞燕，胡志华

(1.上海海事大学 电工电子实验中心，上海 201306;2.上海海事大学 物流研究中心，上海 201306)

装卸搬运作业常见于自动化集装箱码头中，即码头前沿桥吊将集装箱卸载至水平运输设备，水平运输设备衔接码头前沿和堆场，龙门吊将集装箱装载至堆场，故又称之为三级装卸搬运[1]。“搬运”作为“装”和“卸”的衔接环节，其高效运作可提高码头整体效益。自动化导引车(automatic guided vehicle, AGV)，又称无人导引车，是自动化集装箱码头最常见的水平运输设备。在搬运作业中，若一台40 ft AGV搬运一个20 ft的集装箱，其装载率仅为50%，造成资源浪费。因此，采用由两台20 ft的AGV配对搬运40 ft的集装箱或40 ft AGV独立搬运40 ft的集装箱，20 ft集装箱仅由20 ft AGV独立搬运的新工艺，即为AGV混合配对调度。

新工艺的关键是配对调度，指多辆运输设备协同搬运一个货物，HU等[2]称此类运输问题为多车辆单任务问题 (multi-vehicle and one-cargo transportation，MOVC)。MOVC常见于大件物流运输和船舶分段运输，如JOO等[3]考虑了配送限制的约束条件，以最小化惩罚时间为目标建立数学模型，并设计了基于遗传算法(GA)和自进化算法(SEA)的元启发式算法。PARK等[4]将船舶分段运输问题转化为带有优先级约束和顺序相关初始时间的并行调度问题。MOVC对同步性提出了更高要求，如IOACHIM等[5]将同步性概念应用到船舶分段运输，并通过动态规划算法进行求解。GSCHWIND[6]考虑节点同步装载的运输问题，在列生成算法的基础上设计4种分支定界算法并进行比较。SALAZAR-AGUILAR等[7]将同步弧路径问题引入除雪作业中，设计了混合整数规划模型。ROUSSEAU等[8]设计带有同步约束的灵活启发式算法以研究车辆动态分配问题。HU等建立混合整数规划模型，并设计贪婪算法和改进遗传算法求解该模型。综上所述，AGV配对调度是带有同步约束的MOVC问题。

多载AGV可以提高AGV装载率和利用率，针对此问题，GRUNOW等[9]利用运输车辆的有效性，提出了基于优先权调度算法和MILP模型。LEVITIN等[10]则设计了基于LIFO规则的算法求解多载AGV最短路径。

基于此，笔者采用由两台20 ft的AGV配对搬运一个40 ft集装箱和一台40 ft AGV独立搬运40 ft集装箱，20 ft集装箱仅由20 ft AGV搬运的新工艺，以研究AGV混合配对调度问题。以最小化完成时间和空载时间为目标，建立混合整数规划模型并求解。并设计算例，研究AGV和搬运任务的数量配置、规格配置与运输时间的敏感性，以期为优化自动化集装箱码头AGV配对调度方案提供参考。

1 问题描述

受限于自动化集装箱码头车辆配置且集装箱装卸搬运作业密集，AGV装载率和利用率直接影响码头整体效益。笔者采用由两台20 ft的AGV配对搬运一个40 ft集装箱和一台40 ft AGV独立搬运40 ft集装箱的新工艺，其关键点是配对调度。配对调度分为3个阶段[11]：①选择，为搬运任务选择相应数量AGVs；②配对并搬运，AGVs配对成具有相应荷载能力的搬运车并将集装箱从装载点搬运到卸载点；③分离，集装箱卸载后，AGVs自动分离，等待后续作业命令。

假设有4个搬运任务和3台AGV。每个搬运任务对应一个集装箱，集装箱的装载位置Pi和卸载位置Di均已知，并引入虚拟起点S和虚拟终点T。任务1的集装箱尺寸为40 ft，由一台40 ft的AGV将其从装载位置P1搬运至卸载位置D1；任务2和任务3的集装箱尺寸均为20 ft，分别由一台20 ft AGV搬运；两台20 ft AGV各自完成20 ft搬运任务后，配对成具有40 ft荷载容量的运输车，将任务4中40 ft集装箱由装载位置P4搬运至卸载位置D4。混合配对调度示意图如图1所示。

图1 AGV混合配对调度示意图

现有以下假设：

假设1集装箱尺寸及其装卸载位置确定。

假设2AGV尺寸、数量、位置信息及可调度时间确定。

假设3AGV配对和分离操作时间忽略不计。

假设4不考虑交通堵塞、AGV电量不足等不确定因素，AGV全程无故障，匀速行驶且忽略启动时间。

2 模型构建

集合设置如下：

I20={120,220,…，i20，…,N20}为20 ft搬运任务集合，i20表示搬运任务i的尺寸为20 ft， 即i20∈I20；

I40={140,240,…,i40,…，N40}为40 ft搬运任务集合，i40表示搬运任务i的尺寸为40 ft，即i40∈I40；

I=I20∪I40∪{S,T}为搬运任务总集合，其中S与T分别表示虚拟起点和虚拟终点，即i∈I；

V20={120,220,…,|V20|}为20 ft AGV集合，v20表示第v台AGV尺寸为20 ft，即v20∈V20；

V40={140,240,…,|V40|}为40 ft AGV集合，v40表示第v台AGV尺寸为40 ft，即v40∈V40；

V=V20∪V40为AGV总集合，即v∈V。

目标函数及约束条件如下：

minf=(fMakespan,fEmpty)

(1)

(2)

fMakespan≥zi,∀i

(3)

f≥0,zi≥0,∀i

(4)

zi≥Ai,∀i

(5)

zi≥Rv+TLv,Pi+Ti,∀i,v

(6)

zj+(1-xijv)M≥zi+Tj+TDi,Pj,∀i≠j,v

(7)

(8)

(9)

xijv+xjiv≤1,∀v

(10)

(11)

(12)

(13)

(14)

(15)

(16)

式(1)为目标函数，表示最小化完成时间和空载时间；式(2)为各AVG的空载时间之和；式(3)～式(7)规定搬运任务的完成时间；式(8)～式(10)为作业流约束，即入度与出度相等；式(11)和式(12)表示虚拟起点和虚拟终点分别是初始任务和末任务；式(13)～式(15)规定了40 ft集装箱的AGV分配方案；式(16)表示20 ft集装箱仅分配一台20 ft AGV，否则任务不能被处理，一直处于等待状态。

3 算例分析

算例有6台AGV 和16个搬运任务(包含虚拟起点和虚拟终点)，任务完成时间和AGV空载时间分别为16 413和34 651，作业衔接序列如表3所示。第1台和第3台AGV为40 ft，其余AGV的尺寸为20 ft。20 ft和40 ft集装箱比例设置为1:1，其中20 ft集装箱编号分别为2、4、6、8、12和14，40 ft集装箱编号分别为1、3、5、7、9、11和13。第1台40 ft AGV先后独立完成40 ft搬运任务7、13和9；第3台40 ft AGV独立完成第3个40 ft搬运任务；第2台和第4台20 ft AGVs配对完成第5个40 ft搬运任务；第4台和第6台20 ft AGVs配对完成第1个40 ft搬运任务；第5个和第6个20 ft AGVs配对完成第11个40 ft搬运任务。20 ft集装箱均由20 ft AGV独立搬运。

表1 搬运任务参数值

表2 AGV参数设置

应用GUROBI求解器并使用PYTHON语言编译求解模型，得到AGV配对调度时序图时间和

表3 AGV作业衔接序列

空载时间。AGV配对时序图如图2所示，矩形区域中的数字表示第v台AGV参与完成第i个搬运任务，矩形的长度表示运输时间的长短。

图2 AGV配对时序图

4 实验

为进一步分析搬运任务、AGV的规格、数量和运输时间变化对结果的影响，在16个搬运任务和6台AGV 算例的基础上设计4组实验场景，场景描述及参数调整如下：

(1)实验场景1分析AGV规格配置对结果的影响。搬运任务和AGV数量等参数保持不变，在原有2∶1配置比例基础上，按照[1∶5，1∶2，1∶1，5∶1]调节 40/20AGV规格。搬运任务完成时间和AGV空载时间变化如图3所示，可以看出AGV空载时间对不同规格AGV配置比例的敏感性较低，而AGV配置比例对任务完成时间的影响较大。随着40 ft AGV配置数量的减少，任务完成时间不断减小，当40/20的AGV配置比例为2∶1时，任务完成时间达到最小，且完成时间和空载时间之和最小。因此，当搬运任务数量和AGV数量已知时，可通过调整AGV规格配置比例，优化调度方案以减少搬运任务的完成时间和AGV空载时间。

图3 AGV配置比例对结果的影响

图4 集装箱配置比例对结果的影响

(2)实验场景2分析集装箱规格配置对结果的影响。搬运任务和AGV数量等参数保持不变,在原有1∶1的基础上，按照[1∶6，2∶5，1∶1，5∶2，6∶1]调节40/20集装箱规格。搬运任务完成时间和AGV空载时间变化如图4所示，可以看出任务完成时间对不同规格集装箱配置比例的敏感性很低，基本没有受到影响。而随着配置比例的变化，AGV空载时间波动变化，当40/20集装箱配置比例为1∶1时，空载时间和完成时间之和最小。因此，在AGV数量和配置比例已知，且搬运任务数量确定的条件下，调整集装箱配置比例可减少任务完成时间和AGV空载时间。

(3)实验场景3分析集装箱数量变化对结果的影响。保持40/20集装箱规格配置比例1∶1不变，按照-50%，-25%，25%，50%调节集装箱数量。搬运任务完成时间和AGV空载时间的变化如图5所示，可以看出随着集装箱数量的增加，搬运任务完成时间持续上升，而AGV空载时间呈波动变化。可见AGV空载时间对集装箱数量变化的敏感性较强，而搬运任务完成时间对集装箱数量变化的敏感性较低。

图5 集装箱数量变化对结果的影响

(4)实验场景4分析运输时间变化对结果的影响。保持其他参数不变，按照-75%，-50%，-25%，25%，50%，75%调节运输时间。搬运任务完成时间和AGV空载时间的变化如图6所示，可以看出随着运输时间的增加，完成时间和空载时间均呈上升趋势，且空载时间上升幅度大于完成时间。可见对于运输时间的变化，空载时间的敏感性较强，完成时间的敏感性相对较低。

图6 运输时间变化对结果的影响

5 结论

为了提高自动化导引车的空间利用率，针对40 ft集装箱搬运问题，采用由两台20 ft AGV配对搬运和一台40 ft AGV独立搬运的混合配对调度新工艺，以最小化完成时间和空载时间为目标，建立混合整数规划模型并求解。实验结果表明，任务完成时间对运输时间敏感性较低，而空载时间对运输时间敏感性较高。通过调整AGV和搬运任务的数量和规格，可获得合理的配置参数和配对调度方案，模型具有良好的可行性。