基于PSO的自动化集装箱码头双小车岸桥和AGV的协同调度

马孙豫 杨勇生 梁承姬

(上海海事大学物流科学与工程研究院 上海 201306)

0 引 言

随着一带一路的政策逐渐实施，我国沿海港口集装箱吞吐量逐步增加，船舶逐渐大型化，港口对装卸效率的要求越来越高，目前建造自动化集装箱码头已经形成一种趋势。双小车岸桥和自动导引车(AGV)的运用，是自动化集装箱码头的主要特征，自动化集装箱码头水平运输系统的效率直接影响了船舶停靠时间。AGV是水平运输系统的主要设备，而决定水平运输系统效率的是码头各个装卸设备的调度情况[1]。因此，研究双小车岸桥和AGV的调度情况，对于提高自动化集装箱码头的整体效率有着巨大的意义。

目前，国内外学者对AGV调度问题已经进行了许多研究[2]。Xin 等[3]针对自由搜索生成无碰撞轨迹的问题，提出了一种多载AGV调度的混合整数规划模型，以减少自动化码头装卸时间；Angeloudis等[4]针对不确定性环境下的AGV任务分配问题，通过采用滚动时域，减少船舶在港时间，从而提高自动化码头的装卸效率；Danijela等[5]使用数据包络法对AGV调度进行进一步分析，建立仿真模型和效率评估，通过改变调度及AGV和任务数量来分析卸船集装箱的作业效率；康志敏等[6]考虑两种AGV调度方法，提出了基于成本的调度方法，建立了以等待时间最少为目标函数值的调度模型，利用遗传算法来求解模型；霍凯歌等[7]基于多载AGV，以最小化AGV作业成本为目标函数，并采用GUROBI和遗传算法对该问题进行求解，与单载AGV结果进行比较，证明该模型的实用性；柯冉绚、任亚东等[8-9]基于两种AGV调度模式的优缺点，建立了以AGV等待时间为目标函数的整数规划模型，以Netlogo构建仿真模拟，证明模型的实用性。

国内外学者为解决AGV调度问题提出很多智能方法[10]。Jin等[11]考虑AGV运输时间和任务的优先顺序，设计一种以最小化岸桥装卸的完成时间和标准差动态多AGV调度模型，利用遗传算法进行求解；Kim等[12]基于AGV静态调度，提出了一种多标准的AGV调度策略，以岸桥延误时间和AGV空驶距离最小化为目标函数，使用多目标进化算法进行求解；李晔等[13]通过改变双小车岸桥上的中转平台容量限制，以岸桥前小车装卸延迟时间和岸桥后小车与AGV间的等待时间之和最小为目标函数，设计启发式算法求解后小车时间窗，采用遗传算法进行求解；宗辰光等[14]采用多层编码粒子群-遗传算法融合，对成本优化问题进行了仿真研究，给出了成本变化曲线及AGV调度甘特图，来证明算法的有效性。

通过上述可知，目前相关文献的研究主要围绕时间窗的调度、路径规划的调度、任务指派的调度，但是考虑的大都是单一设备装卸问题，求解算法以遗传算法为主。随着AGV数量的增加，水平运输系统的复杂化，遗传算法求解的效率和有效性会大大降低。为此，本文采用多层编码粒子群算法，以AGV调度为主，岸桥等设备为辅，通过改变装卸任务和AGV的数量进行算法求解，并通过实验结果进行分析比较，提高自动化码头运作效率。

1 问题描述

自动化码头与传统码头的最大的区别就是自动化码头的布局是垂岸式，所谓垂岸是指堆场的布局垂直于码头[15]。自动化集装箱码头如图1所示。

图1 自动化集装箱码头布局图

由于各个设备之间的操作不连贯、不协调，出现岸桥等待AGV或AGV等待时间过长的现象。自动化码头作业包括自动化码头作业包括岸边作业、水平运输作业和堆场作业[16]。双小车岸桥和轨道吊分别负责岸边和堆场作业的主要装卸设备，AGV是负责在岸边到堆场间水平运输的主要设备。在卸船过程中，岸桥前小车将船舶上的集装箱放置于岸桥中转平台上，岸桥后小车从中转平台上将集装箱吊起装载于AGV上，而后AGV选择路径运输至堆场，轨道吊将集装箱从AGV上取走存放在堆场指定位置[17]。装船过程与卸船过程相反。

双小车岸桥按照已知确定的卸船顺序依次卸载集装箱，由于存在中转平台的限制，一般中转平台只能存放2个集装箱，当超过2个容量时，前小车不再放置集装箱至中转平台，需等待后小车将中转平台中的集装箱放置于AGV上。在这整个过程中，需要对AGV的任务进行调度分配，来减少AGV的装载运输时间和岸桥的等待时间，从而达到缩短船舶停靠时间的目的。因此，该问题实质是AGV的调度问题。

本文针对自动化码头新设备，以小型自动化码头为例，以AGV为研究对象，已知岸桥卸船作业顺序的情况下，建立以岸桥作业时间最短为目标的AGV调度混合整数规划模型。本文研究的问题主要设备涉及到了双小车岸桥和AGV，为了保证算法的精确性和完整性，将箱区主要运输设备轨道吊RMG(Rail-Mounted Gantry Crane)也纳入考虑范围。采用粒子群算法进行求解，CPLEX软件和GA进行对比分析验证粒子群算法的有效性,实现整个系统的最优化调度，提高码头装卸运输效率，减少在港口时间。

2 数学模型

2.1 模型假设

根据自动化码头实际情况，对相关问题进行简化：

(1) 岸桥作业装卸顺序已知且只卸不装；

(2) 岸桥后小车装载集装箱到AGV上的时间已知；

(3) AGV采用作业面装卸且一次只能运输一个集装箱；

(4) AGV匀速行驶，不考虑加减速和运输过程中冲突死锁问题；

(5) 每个箱区使用一个RMG进行装卸作业。

2.2 参数及决策变量

(1) 参数变量:

S：一个虚拟任务的开始，OS=D∪S；

F：一个虚拟任务的结束，OF=D∪F；

D：集装箱数量集合，i,j∈D；

K：岸桥数量集合，k,l∈K；

P：集装箱堆存位置集合，(n,b)∈p，(n,b)表示在箱区b的第n个位置；

B：箱区数量集合，b,a∈B；

V：AGV数量集合；

C：轨道吊(RMG)数量集合；

T：岸桥后小车将集装箱卸载到AGV的时间为固定值；

Nk：岸桥k卸载的集装箱数量；

(i,k)：岸桥k卸载第i个集装箱；

h(i,k)：岸桥完成集装箱i卸载工作的时间；

s(i,k)：岸桥前小车将集装箱卸载到中转平台上的时刻；

r(i,k)：岸桥后小车将集装箱从中转平台卸载的时刻；

d(i,k)：AGV执行岸桥k的第i个任务的时刻；

f(k,b)：AGV在岸桥k和箱区b之间的运行时间；

e(i,k)：RMG开始处理集装箱i的时刻；

φ(n,b)：RMG运行到箱区b的第n的位置的时间；

u(i,k)：岸桥前小车开始卸载集装箱i到中转平台的时刻；

M：一个较大的整数。

(2) 决策变量:

2.3 基本模型

(1) 目标函数:

MIN=MAX(u(i,k)+h(i,k))

(2) 约束条件:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

s(j+1,l)+r(j,l)-s(j,l)+T≤d(j,l)

∀(j,l)∈oF,j=1,2,…,Nk-1

(11)

(14)

u(i,k)≤s(i,k)≤r(i,k)≤d(i,k)≤e(i,k)≤φ(n,b)

∀i∈D,∀k∈K

(15)

(16)

(17)

u(1,k)=0

(18)

∀(i,k)(j,l)∈o,∀(n,b)∈p,∀b∈B

(19)

上述基本模型是一个混合整数规划模型，其中目标函数为最小岸桥卸货操作时间。式(1)表示AGV每个任务都有一个后序任务；式(2)表示AGV每个任务都有一个紧前任务；式(3)保证每个集装箱在箱区中都有位置；式(4)保证每个箱区的位置只能放少于一个集装箱；式(5)表示如果集装箱被分配到了箱区b中，可以放在任意位置；式(6)表示RMG每个任务都有一个后序任务；式(7)表示RMG每个任务有一个紧前任务；式(8)表示AGV将集装箱运到箱区交接处，RMG才能开始处理该集装箱任务；式(9)表示只有当AGV完成前一个任务才能开始后一个任务；式(10)表示RMG只能完成前一个任务才能开始后一个任务；式(11)约束岸桥中转平台上的集装箱数量；式(13)表示只有后小车将集装箱放到AGV上，AGV才能开始任务；式(14)表示参数之间的关系；式(15)为对任务操作时间需要满足的实际情况；式(16)和式(17)表示对于同一设备，如果(i,k)是(j,l)的前置任务，那么(i,k)就不可能再是(j,l)的后序任务，即任务流向是单向的；式(18)表示设定岸桥卸载第一个集装箱的时刻为0；式(19)为0-1变量。

3 PSO求解

PSO是进化计算的一种，因其算法简单，易于实现而常被用来解决非线性连续函数优化、约束优化、多目标优化等问题[18]。利用PSO算法求解AGV调度优化模型的流程是：设计并初始种群粒子，每个粒子是问题的一个可行解，粒子的位置表示一个调度的方案，通过粒子个体间的相互协作逐步在搜索空间中寻找最优解。在每一次迭代的过程中，当前粒子的位置和速度都是由上一代粒子的位置和速度所决定[19]。利用上述模型定义的适应值函数，通过粒子不断迭代进化寻找全局最优解。

3.1 编 码

为验证PSO的有效性，在设计算法时，采用多层编码粒子的方法来表示自动化码头的调度问题，以求得全局最优解。假设有3台岸桥，15个装卸任务，使用3辆AGV进行运输，随机运载到4个箱区中,其中箱区编号为RMG编号，则第i个任务的编码表示为：编号为第v辆AGV将第i个任务运送到并由第b个RMG运输到箱区中。多层编码即初始种群示例如图2所示。

图2 初始种群

3.2 控制参数的选择

(1) 学习因子 PSO中的粒子无法通过GA中交叉变异来进行更新，粒子只能通过内部速度进行更新。学习因子c1和c2为非负常数，c1调节粒子飞向最好位置方向的步长，c2则是调节粒子飞向全局最好位置方向的步长[19]。在本文中，设置c1=c2=1.494 45。

(2) 初始速度 为了防止算法在迭代过程中粒子离开搜索空间，通常设定最大速度vmax和最小速度vmin，设置种群初始速度vmax= 1，vmin=-1。

(3) 惯性权重w为惯性权重，取较大值时，粒子群具有较强的全局搜索能力，较小时，则倾向局部搜索。本文采取线性递减的取值方法，其大小变化如下：

w=wmax-(wmax-wmin)×g/Tmax

式中:wmax=0.9，wmin=0.4，g为进化代数，Tmax为最大迭代数，Tmax=200。

4 算例验证

以图1的码头布局为模型，参照某自动化码头实际数据，对参数进行初步设定。假定码头有2个箱区，随着任务数量的改变，双小车岸桥和AGV的数量也进行改变。为验证算法解决此问题的有效性，采用MATLAB实现PSO和GA，同时采用CPLEX12.6对约束条件进行求解，对比结果如表1。

表1 PSO与CPLEX、GA对比

从表1中可以看出，通过与其他两种方法对比，我们提出的PSO算法可以获得近似最优解。与CPLEX的最优解相比，其运行速度更快，范围从2.42 s到7.55 s且没有剧烈波动，GA运行速度从3.53 s到7.32 s，同样没有剧烈波动。在运行时间方面，CPLEX所需时间远远大于PSO和GA范围。从11.32 s到11 055.28 s，波动剧烈。随着任务数量的增加，三者运行时间都逐渐增长，但当任务数量增长到30时，CPLEX无法在合适的时间得出最优解。在运行结果方面，可以看出，随着任务数量的增加，CPLEX、PSO和GA三者最优解结果差距不大，因此证明了PSO 算法在解决此问题的有效性。从算例6和算例7可以看出，任务数量一定时，增加AGV的数量会提高码头效率，使得卸船作业时间减少，提高作业效率。从算例8和算例9可以发现，并不是AGV数量越多则效率越高，数量过多反而会导致效率降低，而影响这类情况有很多原因。

以算例12为例，基于PSO对模型进行求解所得的甘特图如图3所示。该甘特图中包含了岸桥作业时间、AGV 时间和箱区RMG作业时间，并每个任务编号作业区上标注了岸桥、AGV和箱区RMG编号。在本文中未设置交接区，因此运行过程中，出现了AGV运输到箱区时等待RMG这种情况。以任务编号25为例，1号岸桥将集装箱运输到2号AGV，而后运输到2号箱区，所求得收敛情况如图4所示，最终得到的最优值为1 277 s。

图3 调度甘特图

图4 PSO收敛图

下面讨论不同任务数量下双小车岸桥和AGV数量对最优值的影响。数据均来源于运行多次结果的均值，如图5所示。

图5 不同岸桥及AGV数量变化下目标值的变化

可以看出：

(1) 不同双小车岸桥数量下，最优适应度值达到最低值时的AGV数量不同。当双小车岸桥数量为2时，AGV数量为6时适应度值最小；当双小车岸桥数量为3时，AGV数量为9。双小车岸桥的数量和AGV的数量应相互配合。

(2) 当双小车岸桥数量一定时，随着AGV数量的增加，岸桥卸载作业时间逐渐减少。这是因为当AGV数量较少时，AGV不能及时将岸桥后小车所卸载的集装箱运到箱区。此时，岸桥需等待AGV，使得集装箱堆积在中转平台上。当超过2个集装箱时，岸桥前小车也需等待后小车，但是适应度值并非随着AGV数量的增加而减少。例如图3中岸桥数量为2，AGV数量为7时，可以看出最优值开始增加。出现这种情况的原因是AGV数量较多，导致当AGV将上一个集装箱运输到指定箱区后返回至岸桥后小车前等待运输，而岸桥装载能力有限，不能及时配合AGV运输作业，造成AGV等待。

(3) 当AGV数量一定时，适应度值随着双小车岸桥数量的增加而减少。这是因为随着双小车岸桥数量的增加，岸桥前小车将任务卸载至中转平台，岸桥后小车将其放置于AGV上，期间任务连续，并没有造成AGV等待岸桥后小车的情况。但是，当双小车岸桥的数量较多时，AGV运输能力的限制会导致后小车需要等待AGV。

5 结 语

本文针对AGV调度，基于任务作业最小化建立数学模型，设计了PSO，从双小车岸桥作业及箱区RMG作业时间进行优化分析，在任务数量变化的情况下，改变双小车岸桥数量和AGV数量，进行计算。算例表明，卸船时间随着任务的数量的增加而增加，随着AGV的数量的增加而减少，但是增加到一定程度时卸船时间反而增加。通过与CPLEX的对比分析，证明了本文所提模型和算法的有效性，并能减少卸船作业时间，提高码头运作效率。

在整个作业过程中，并没有设置交接区且是在已知卸船作业顺序情况下进行双小车和AGV的调度，AGV等待的时间过长，阻碍了码头整体效率，且自动化码头调度问题同时还受到岸桥数量、堆场设备数量配置及其他资源分配和调度的影响。此外，码头作业装卸流程和AGV运输过程所造成的拥堵、冲突和死锁问题将是以后研究的重点。