自动化集装箱码头双循环AGV与场桥的集成调度研究

田 宇，周 强，朱本飞

(武汉理工大学物流工程学院，武汉430063)

0 引 言

集装箱码头作为集装箱运输网络的关键节点，其运营效率是港口运输系统的瓶颈，体现港口的关键竞争力.自动化集装箱码头相对于传统码头具有高效、环保、低人力成本等优势，成为集装箱码头未来发展的必然趋势.岸桥、自动导引车(AGV)和场桥是自动化集装箱码头装卸过程的3种重要设备资源，三者相互关联、相互影响.岸桥位于码头前沿，负责船舶上集装箱的装卸，其装卸效率决定船舶在港口的滞留时间.在岸桥装卸次序表已知的情况下，研究如何使AGV和场桥高效协同作业，保证岸桥最小时间完成船舶装卸,具有重要的理论意义和实用价值.

关于AGV的调度问题研究，文献[1]提出基于调度优先级次序的动态调度方法来解决AGV的调度问题；文献[2]针对智能仓库中多AGV调度的路径问题进行研究，提出改进的蚁群算法进行求解.关于自动化集装箱码头AGV与岸桥和场桥的调度问题，文献[3]建立最小化AGV行走时间、岸桥延迟时间、场桥行走时间的多目标混合整数规划模型，设计多层启发式和最大匹配启发式遗传算法进行求解，通过数值仿真分析表明最大匹配启发式算法在寻优和耗时上优于多层启发式算法；文献[4]建立最小完工时间和AGV最小无效行走时间的多目标数学模型，提出混合遗传和禁忌搜索两种算法进行求解；文献[5]针对自由路径AGV的调度与岸桥和场桥进行集成研究，考虑AGV在行走过程中的碰撞问题，提出分层控制方法来实现岸桥、场桥的优化调度以及AGV的路径规划.关于AGV与场桥的集成调度中考虑集装箱堆场位置分配的问题，文献[6]在集成研究中考虑的是进口箱的堆存位置分配，建立以最小化完工时间为目标的混合整数规划模型，根据模型的特点设计遗传算法，通过数值仿真对算法的参数、性能进行分析；文献[7]考虑进出口箱的堆存位置分配，以最小化岸桥延迟时间和AGV行走时间为目标，提出多目标混合整数规划方法和基于模拟退火算法的近似优化方法对问题进行求解.关于卸船过程中的AGV与场桥调度问题，文献[8]考虑出口箱的堆存位置分配，建立以最小化岸桥和场桥的总工作时间以及完工时间为多目标的线性和非线性混合整数规划模型，设计元启发式和遗传算法进行求解；文献[9]考虑进口箱的堆存位置分配，建立以最小完工时间为目标的混合整数规划模型，设计遗传算法进行求解.

综上所述，围绕AGV与其他装卸设备的集成研究中，针对双循环AGV(即AGV 不固定服务某一台岸桥，可以服务多台岸桥的作业模式)与场桥的集成研究比较少.本文通过对集装箱任务统一编号，结合对装卸过程中集装箱的流动特性分析，设计基于任务随机搜索机制的“最早可获得时间(Earliest Available Time,EAT)”“最短路径(Shortest Path,SP)”两种启发式规则进行求解.

1 问题分析与数学建模

1.1 问题描述

在集装箱船舶靠泊后，集装箱的装卸流动主要涉及到码头的3个功能区：岸桥负责的码头前沿装卸区、AGV小车负责的运输区和场桥负责的堆场堆存区，如图1所示.

图1 自动化集装箱码头布局示意图Fig.1 Layout of automated container terminal

在自动化码头生产过程中，船舶的配载图会在装卸前提前给出，以便提前计划出岸桥的装卸次序表.在装卸前，进口箱被卸载到堆场的堆存位置会预留出，以便进口箱在堆场的临时堆存.出口箱在船舶到港之前会被陆续堆集到堆场，以便船舶靠港后进行装载.一般同一艘船舶的进出口箱在堆场的堆存位置分别分配在不同的箱区.集装箱的流动在装船过程与卸船过程中是相反的，其中的卸船过程描述如下：

(1)岸桥按照装卸次序表从船舶上抓取相应的进口集装箱，在岸桥装卸节点将集装箱释放到AGV小车上，岸桥进入下一个任务的装卸；

(2)AGV小车将集装箱运到相应箱区的装卸节点处，负责该箱区的场桥从AGV 上抓取该集装箱后，AGV进入下一个任务的运输；

(3)场桥将集装箱从AGV小车上提取后，释放到堆场相应的堆存位置，回到箱区装卸节点处进入下一个任务的装卸.

本文的优化目标是在船舶装卸过程中，对“AGV的任务分配”“AGV的路径规划”“场桥的任务次序”三者同时做出决策，以便获得船舶最小完工时间.

1.2 数学模型

(1)假 设.

①岸桥装卸次序表已知，②进、出口箱在船舶和堆场的堆存位置已知，③岸桥和场桥对集装箱的操作时间已知，④AGV在任意两节点的行走时间已知.

(2)参数及变量.

①参数.

D为进口箱集合；L为出口箱集合；Q为岸桥集合，为岸桥总数量；v为AGV小车指针，为AGV小车的总数量；n、n′、n″为进出口集装箱任务编号指针；为总的进出口箱数量；q、q′为岸桥指针；b、b′为堆场箱区指针；为AGV小车从岸桥q的装卸节点到堆场箱区b装卸节点行走的时间；为AGV小车从岸桥q′的装卸节点行走到岸桥q装卸节点的行走时间；为AGV小车从堆场箱区b装卸节点到岸桥q装卸节点的行走时间；为AGV小车从堆场箱区b装卸节点到堆场箱区b′装卸节点的行走时间；Hn为岸桥装卸集装箱n时所需要的时间；Kn为场桥装卸集装箱n时所需要的时间.

②变量.

Un为集装箱n在岸桥装卸节点被交接的时间点；Vn为集装箱n在箱区装卸节点被交接的时间点.

(3)模型.

在装卸过程中，岸桥按照装卸次序表执行装卸任务，进口箱区场桥按照“先到先服务”的原则，出口箱区场桥按照先满足岸桥装卸次序并有AGV可指派的先发箱.进口箱在岸桥装卸节点释放时间和出口箱在箱区装卸节点释放时间情况如图2所示.

图2 进口箱在岸桥装卸节点和出口箱在箱区装卸节点的任务关系图Fig.2 Task relationship of import containers at quay crane handling points and export containers at block handling points

图2中(a)～(i)表示集装箱n为进口箱，各种情况下进口箱n在岸桥装卸节点应满足的时间关系如下.

(a)当前集装箱n为岸桥的第一个任务，且为AGV小车的第一个任务时，即

(b)当前集装箱n不是岸桥的第一个任务(前一任务为进口箱n′)，但为AGV小车的第一个任务时，即

(c)当前集装箱n不是岸桥的第一个任务(前一任务为出口箱n′)，但为AGV小车的第一个任务时，即

(d)当前集装箱n是岸桥q的第一个任务，但不是AGV小车的第一个任务(前一任务为岸桥q′负责的出口箱n′)时，即

(e)当前集装箱n是岸桥q的第一个任务，但不是AGV小车的第一个任务(前一任务为堆存在箱区b的进口箱n′)时，即

(f)当前集装箱n不是岸桥q的第一个任务(前一任务为进口箱n″)，也不是AGV小车的第一个任务(前一任务为堆存在箱区b的进口箱n′)时，即

(g)当前集装箱n不是岸桥q的第一个任务(前一任务为进口箱n″)，也不是AGV小车的第一个任务(前一任务为岸桥q′负责的出口箱n′)时，即

(h)当前集装箱n不是岸桥q的第一个任务(前一任务为出口箱n″)，也不是AGV小车的第一个任务(前一任务为堆存在箱区b的进口箱n′)时，即

(i)当前集装箱n不是岸桥q的第一个任务(前一任务为出口箱n″)，也不是AGV小车的第一个任务(前一任务为岸桥q′负责的出口箱n′)时，即

确定进口箱在岸桥装卸节点的交接时间点后，根据各进口箱区场桥“先到先服务”原则确定进口箱在箱区装卸节点的交接时间点Vn,n∈D.

图2中(j)～(o)表示集装箱n为出口箱，各种情况下出口箱n流动在箱区装卸节点应满足的时间关系如下.

(j)当前集装箱n是箱区场桥的第一个任务，且为AGV小车的第一个任务时，即

(k)当前集装箱n不是箱区场桥的第一个任务(前一任务为集装箱n′)，但为AGV小车的第一个任务时，即

(l)当前集装箱n是箱区b场桥的第一个任务，但不是AGV小车的第一个任务(前一任务为堆存于箱区b′的集装箱n′)时，即

(m)当前集装箱n是箱区b场桥的第一个任务，但不是AGV小车的第一个任务(前一任务为岸桥q′负责的集装箱n′)时，即

(n)当前集装箱n不是箱区b场桥的第一个任务(前一任务为集装箱n′)，也不是AGV小车的第一个任务(前一任务为堆存于箱区b′的集装箱n″)时，即

(o)当前集装箱n不是箱区b场桥的第一个任务(前一任务为集装箱n′)，也不是AGV小车的第一个任务(前一任务为岸桥q′负责的集装箱n″)时，即

确定出口箱在岸桥装卸节点的交接时间后，根据集装箱在岸桥装卸节点遵从岸桥装卸次序表原则确定出口箱在岸桥装卸节点的交接时间

2 启发式遗传算法

2.1 编 码

为了方便染色体编码，将任务根据岸桥的装卸次序表以及岸桥编号从小到大的规则统一对需要装卸的任务进行编码.染色体NRSM=randperm()表示在求解过程中对任务的搜索机制.

2.2 目标函数及适应度函数

染色体的编码表达求解过程中任务的搜索机制，不能直接表达AGV的任务集、AGV的路径以及场桥的任务次序.根据岸桥和场桥的服务规则，结合文献[7]“最近车辆指派”“最早可获得”规则，对AGV的指派设置两种启发式规则：SP和EAT.SP指所有空闲的AGV中距离该集装箱装卸节点最近的指派规则.EAT 指所有空闲的AGV中能最早到达指定集装箱装卸节点的指派规则.

单个染色体的求解流程如图3所示.

图3 单个染色体求解流程Fig.3 Solution process of single chromosome

图3中AAGVZT为5行列的AGV 状态矩阵：NAGVZT(1,:)表示各AGV小车当前的运送任务编号，为0时表示可分配任务；NAGVZT(2,:)表示各AGV小车当前任务在岸桥装卸节点交接的实际时间点；NAGVZT(3,:)表示各AGV小车当前任务在岸桥装卸节点交接的预估时间点；NAGVZT(4,:)表示各AGV小车当前任务在对应箱区装卸节点交接的预估时间点；NAGVZT(5,:)表示各AGV小车当前任务在对应箱区装卸节点交接的实际时间点.

目标值为

2.3 交 叉

染色体的交叉采用两点交叉法.随机从种群中选择染色体作为父代1和父代2，然后随机生成两交叉点并将两点之间的基因段分别作为子代2和子代1对应的基因段，最后将父代1中不同于子代1中的基因逐个编入子代中的空白基因中.

2.4 变 异

采用换位变异，随机生成两个基因位置，再将两个基因的内容进行互换.

3 数值试验及结果分析

运用MATLAB 2016a和CPLEX12.6.1.0，运行环境为windows8，处理器为英特尔i7-4770，处理器频率为3.4 GHz，运行内存为8.00 G.

3.1 参数设置

堆场的布局如图1所示，共有6条箱区，其中1～3为进口箱区，4～6为出口箱区，进出口集装箱在堆场的箱区从对应进出口箱区中随机生成.岸桥对各集装箱的操作时间Hn∈U[30,180]s，AGV 于任意两装卸节点的行走时间参照文献[3]，场桥的操作时间Kn∈U[60,180]s.遗传算法的参数设置：最大迭代数为250，种群数为40，交叉率为0.8，变异率为0.2.

3.2 结果分析

数值试验中，每种情况运行5个算例，每个算例运行5次，分别取平均值、最小值、标准方差以及运行时间的平均值对比分析.结果如图4～图9所示.

图4 EAT 规则的平均值Fig.4 Average of EAT rule

图5 SP 规则的平均值Fig.5 Average of SP rule

图6 EAT 规则的最小值Fig.6 Minimum value of EAT rule

图7 SP 规则的最小值Fig.7 Minimum value of SP rule

图8 EAT 规则的标准方差Fig.8 Sdev of EAT rule

图9 SP 规则标准方差Fig.9 Sdev of SP rule

图4～图7分别是“任务量30-岸桥2”“任务量50-岸桥3”“任务量70-岸桥4”“任务量90-岸桥5”时，AGV数量从4～10个的算例平均值、最小值.两种启发式规则计算结果随着AGV的数量增加，最大完工时间会变小，变小的趋势会变得平缓，说明AGV数量的增加可以提升码头的效率，提升的程度有上限.从图8和图9中得到：随着任务数量、岸桥数量的增加，稳定性会有一定程度的下降，但是两种启发式算法的稳定性比较理想.图8中，当任务量小于70、岸桥数量小于5时，“最早可获得时间”的启发式算法随着AGV数量的增加，表现良好的稳定性.

图10 两种启发式算法的平均值Fig.10 Average of two heuristic algorithms

图11 两种启发式算法的最小值Fig.11 Minimum value of two heuristic algorithms

图10∼图12是不同任务数量、岸桥数量、AGV数量下平均值、最小值、标准方差下的曲线，可以看出：“最早可获得时间”的启发式规则在优化目标以及求解稳定性上都要优于“最短路径”启发式算法.图13是两种启发式算法的求解时间，两种算法的求解时间差别不大，都比较理想；在任务、岸桥数量一定的情况下，随着AGV数量增加呈下降趋势.

图12 两种启发式算法的标准方差Fig.12 Sdev of two heuristic algorithms

图13 两种启发式算法的求解时间Fig.13 Solution time of two heuristic algorithms

4 结 论

针对自动化码头双循环AGV和场桥调度问题进行集成研究，结合码头的工艺特性，对装卸过程中集装箱的流动进行分析并建立数学模型；设计EAT和SP 两种启发式遗传算法进行求解.通过数值仿真，从平均值、最小值以及标准方差等性能指标对两种算法进行对比分析，结果表明EAT 启发式算法优于SP启发式算法.