自动化码头ALV实时任务分配

宓为建　梁枭　张晓华　夏孟珏　王郡娴　孙思韵

摘要：

为弥补自动化集装箱码头自动装载车（Automated Lifting Vehicle， ALV）先到先服务（First Come First Service， FCFS）分配方式的缺陷，提出基于触发事件的ALV作业任务实时分配方式.设置一组触发事件触发ALV实时分配，以ALV到达任务作业点估计时间最短为目标，建立ALV实时分配模型，选用A*算法对该模型进行求解.通过与贪婪算法的对比，验证A*算法的优越性.对用A*算法求解大型集装箱码头ALV实时分配问题的求解速度和稳定性进行实验测试，结果验证了选用A*算法的可行性.

关键词：

自动化集装箱码头； ALV实时分配； A*算法； 触发事件

中图分类号： U691.31； U656.135

0 引 言

随着集装箱码头整体效率的不断提高，码头水平运输车辆的任务分配问题也成为一个非常重要的问题.解决好车辆任务分配问题，可以使车辆更好地服务于其他设备，提高其他设备的作业效率.然而，随着码头向大型化和自动化方向发展，现有的先到先服务（First Come First Service， FCFS）车辆任务分配方式已经很难满足码头的作业需求，急需提出一种更加高效合理的分配方式来解决水平运输车辆的任务分配问题.[1]

国内外学者对集装箱码头的水平运输车辆任务分配问题已经进行了许多研究.NGUYEN等[2]为自动化集装箱码头的自动装载车（Automated Lifting Vehicle， ALV）分配问题建立混合整数规划模型.ANGELOUDIS等[3]根据不准确的码头作业信息，提出在成本/收益下的车辆分配模型和求解的算法.LEE等[4]考虑起重机的作业时间，建立根据多台岸桥的作业任务顺序分配车辆的混合整数规划模型，应用启发式算法进行求解.RASHIDI等[5]将自动导引车（Automated Guided Vehicle， AGV）的分配问题转化为一个最小成本流问题模型，应用改进的网络单纯形法求解.CAI等[6]研究跨运车的作业时序安排问题，利用装卸和搬运的时间窗解决这个问题，并用分支定界法求解.轩华[7]利用FCFS规则进行水平运输车辆和任务的分配，建立数学模型并用启发式算法进行求解.SONG等[8]针对AGV分配问题提出混合元启发式方法，并与贪婪算法进行仿真实验对比.ICHOUA等[9]针对车辆分配问题提出基于先进先出的按时间的行驶速度模型，通过与固定行驶时间的实验结果的对比，发现按时间的车辆分配方式明显优于固定行驶时间的车辆分配方式.GUJJULA等[10]总结几个AGV分配问题常用的目标，包括岸桥等待时间最短、AGV行驶时间最短、完成作业的时间最短等，也总结了几种常用的AGV分配方式，包括最短的行驶时间、使用车辆的数量最少、先到先服务方式等.LIU等[11]总结了3种AGV分配规则，即最大行驶距离、最小行驶距离和随机规则，并分别对其进行仿真.

然而，上述研究都很难解决大型自动化码头中难以估计车辆的实际行驶时间的问题.在交通布局呈现复杂网络结构的码头，由于运输车辆数量多，交通堵塞经常发生，对车辆的实际行驶时间估计的不准确会严重影响车辆任务分配方案的选择.

1 问题描述

1.1 目前ALV任务分配方式

ALV可以在没有其他设备辅助的情况下，自己提起和放下集装箱.ALV任务分配问题就是在码头作业时为需要作业的任务分配可用的ALV.

目前，码头ALV任务分配主要采用FCFS分配方式，每一个新产生的集装箱运输任务都会被分配一辆空闲的ALV，这辆ALV是在分配时最适合去执行这个运输任务的车.应用FCFS分配方式，在为任务分配了ALV后，即使有更合适的ALV可以选择，也不能作出改变.因此，这样的分配方式虽然操作简单，但不能实时保证水平运输车辆的任务分配方案处于最优状态.在ALV运输时间不确定的大型自动化码头，FCFS分配方式会导致ALV的作业效率大大降低，影响其他设备的作业，因此需要设计一个更加高效的水平运输车辆分配方式.

1.2 ALV实时分配方式

ALV实时分配是在作业过程中的某些条件下进行一次ALV的任务分配，当作业的条件发生变化时对ALV的作业任务进行重新分配.把这些条件作为一组触发事件，每次分配看作一次实时分配，建立一个实时分配模型.一组触发事件和一个实时分配模型组成一个完整的ALV实时分配方式.

由于大型集装箱码头ALV的作业过程中会经常出现过去的最佳ALV分配方案后来不再是最佳分配方案的情况，所以要考虑在某些情况

（岸桥（Quay Crane，QC）或者场桥（Yard Crane，YC）准备吊起下一个集装箱；ALV完成上一个运输任务；已经分配任务的ALV遇到交通拥堵等）下对ALV的任务重新进行分配，尽量使ALV的任务分配方案保持最优.

对上述各种作业条件进行归纳总结，设置一组触发事件.每次触发事件发生时，都需要进行一次实时分配.实时分配是对当时所有的任务和空闲ALV进行分配，分配的目标是使总的ALV到达作业地点的估计时间最短.

2 模型建立

2.1 ALV实时分配模型

由于集装箱码头其他作业的ALV实时分配方式与装卸船作业基本相同，所以本文构建模型时，只以装船和卸船作业为例.根据船的作业量给船配备适当数量的QC和ALV，分配给同一艘船的所有QC共享分配给这艘船的ALV，分配给这艘船的ALV也只服务于为这艘船作业的QC.

2.1.1 模型假设

一辆ALV最多只能运输一个集装箱；

分配给QC的ALV数量足够，不会出现等待运输的集装箱数量大于闲置ALV数量的情况；只预先分配一辆ALV给正在作业的QC.

2.1.2 参数定义

C为起重机即将进行作业的集装箱集合，如装船时YC即将进行作业的集装箱和卸船时QC即将进行作业的集装箱的集合；

c为集合C的元素总数量；Q为正在对同一艘船进行作业的QC的集合.在分配ALV时会考虑将部分空闲的ALV分配给正在作业的QC，这些空闲ALV任务的优先级低于C中任务的优先级.q为集合Q的元素总数量；d为在实时分配时需要考虑的ALV任务数量，包括集装箱运输任务数量和正在作业的QC的数量，d=c+q.将任务d分成两部分是因为两部分的分配优先级不同.A为没有开始作业的ALV的集合；a为集合A的元素总数量；i为任务的标识，i=1，2，…，c，c+1，…，c+q，其中，i=1，2，…，c表示需要运输的集装箱，i=c+1，c+2，…，c+q表示正在对同一艘船进行作业的QC；j为ALV的标识，j=1，2，…，a；vj 为ALVj某一时刻的瞬时速度，ALVj停在停车场时vj=V，V为ALV正常行驶时的平均速度；dij为ALVj到任务i的作业地点的距离；

[WTHX]T[WTBX]为从ALVj到达任务作业地点的估计时间矩阵，由ALVj到任务i的作业地点的距离和ALVj的瞬时速度得出；tij为矩阵

[WTHX]T[WTBX]的元素；M为一个很大的数，作为预计行驶时间的上限；D为一个较小的距离常数，dij

2.1.3 模型构建

式（1）表示xij是01变量，当ALVj分配给任务i时xij=1，否则xij=0.式（2）表示模型的目标为ALV到达作业地点的估计时间最短.由于αβ，会给到达任务地点时间短的ALV分配集装箱运输任务，达到先考虑将空闲ALV分配给急需ALV的集装箱运输任务，再考虑将空闲ALV分配给正在作业的QC的目的.式（3）表示每个集装箱运输任务和每一台正在作业的QC最多只能有一辆ALV为其服务；式（4）表示每辆ALV最多只能分配给一个集装箱运输任务或一台正在作业的QC；式（5）表示尽可能多地为需要考虑的作业任务分配ALV；式（6）表示根据距离和速度得出ALV到达作业地点的估计时间.优先考虑分配与任务地点的距离很近的ALV.

2.2 ALV实时分配触发事件

在ALV作业时，设置一个时间段Δt，在每个时间段末检测ALV的行驶速度.记录在第m次分配时ALV的速度vm，设置速度变化量为正值Δv.第m次分配后，当空闲ALV的速度在某个检测时间段末超出vm±Δv的范围（说明ALV的行驶速度相对于第m次分配时有了巨大变化，可能是因为ALV遇到交通拥堵，也可能是因为ALV的交通拥堵得到缓解，ALV的行驶速度恢复正常）时，需要考虑对ALV进行第m+1次分配.根据大型集装箱码头的特点，列举出一组触发事件：（1）新的集装箱运输任务的产生，即起重机准备对某个集装箱进行作业，需要进行重新分配；（2）ALV完成上一个任务，空闲ALV数量增加，需要进行重新分配；（3）第m次分配后，当已经分配任务的ALV的速度在某个检测时间段末的速度超出vm±Δv且dij>D时，需要对ALV进行第m+1次分配.

3 算法设计

大型高效的集装箱码头ALV实时分配触发事件发生的频率很高，每次触发事件的发生都会触发一次ALV实时分配，进行ALV实时分配的频率也会很高，因此对处理ALV实时分配的时间要求也很高.每次触发ALV实时分配后，ALV的任务分配必须在短时间内完成并向ALV发送作业指令，这样才能使ALV实时分配方式的优势得到发挥.因此，需要一种对ALV进行任务分配的算法，以快速地对规模较大的ALV实时分配模型进行求解.

3.1 算法简介

3.1.1 A*搜索算法

A*搜索算法是静态路网中求解最短路最有效的方法.A*搜索算法通过最佳优先搜索来寻找一条从起始节点到一个目标节点或者多个可能的目标节点的代价最短的路径.作为启发式搜索的一种，A*搜索算法同样需要选取估价函数，以省略大量的无意义搜索，提高搜索效率.n是搜索图中的一个节点，A*搜索算法通过一个启发式代价函数

f（n）对节点n进行评价，由f（n）决定在搜索图中的搜索顺序.f（n）是从初始点经由节点n到目标点的估价函数.

式中：g（n）是在状态空间中从起始节点到节点n的实际代价；h（n）是从节点n到目标节点最佳路径的估计代价.h（n）是f（n）函数的一部分，是一个可采纳的启发式函数.对h（n）的估计不能超过节点n与目标节点之间的距离.如果应用在路径问题中，h（n）可以表示节点n与目标节点的距离，是两个节点之间可能的最短实际距离.h（n）是f（n）函数中最重要的一部分，h（n）设计的好坏，决定该算法是否能被称为A*搜索算法，也会影响搜索的效率[13].

3.1.2 A*搜索算法搜索过程

在A*算法执行的过程中用到OPEN表（用于存放搜索到的点但非最小代价节点的集合）和CLOSE表（用于存放已经搜索过的最小代价节点的集合），假设起点和终点分别用

S和V表示，Vi表示节点S与V间的任意一点，fi表示该节点的估价值.A*搜索算法搜索基本步骤如下.

在搜索过程中可以根据需要记录取得最短路径的行走轨迹.行走轨迹就是从起始点到达目标节点的路径最短的行走方案，也是大多数问题的解.

3.2 算法设计

应用A*搜索算法对大型集装箱码头ALV实时分配模型进行求解时，可以很容易将码头获取的ALV到达作业地点的距离dij按照第2节的模型规则转换成ALV到达作业地点的估计时间tij，以时间tij作为任务分配的代价值进行分配.用A*算法求解ALV实时分配问题，需要先将ALV分配问题转换成静态路网中的求解最短路问题，举例说明如下.

将ALV的任务分配问题转换成一个路网图（见图1），圆圈表示节点，其中节点S是起始点.根据ALV的数量或者任务的数量进行分层，本文是根据ALV的数量进行分层的.每一层为一辆ALV分配任务，下一层是在上一层的基础上进行的，根据第2节的模型，按照一辆

ALV最多只能被分配一个任务，一个任务最多只能分配一辆ALV的原则进行分配.例如第一层为ALV1分配任务，此时ALV1可以选择任务1，2，3三个任务，所以节点S下面有1，2，3三个节点.节点1，2，3分别表示将任务1，2，3分配给ALV1.第二层分配是在第一层分配的基础上进行的.第一层中节点1表示任务1分配给ALV1后，第二层ALV2只能分配任务2或3.因此，节点1下面有两个节点4，5，节点4表示将任务1分配给ALV1后，任务2分配给ALV2，节点5表示将任务1分配给ALV1后，将任务3分配给ALV2.同样，节点2和3下面也分别有两个节点.到第三层为ALV3分配任务时，ALV3只能选择上面两层没有选择的任务，因此节点4下面只有一个节点10，表示任务1分配给ALV1，任务2分配给ALV2后，任务3分配给ALV3.节点5下面只有一个节点11，表示任务1分配给ALV1，任务3分配给ALV2后，任务2分配给ALV3.其他节点也按照同样的规则进行分配，直到所有的ALV分配任务完成，得到图1所示的树状图.

根据图1所示的树状图进行搜索，对于搜索到的节点，需要求出它的h（n），g（n）和f（n）值.

g（n）是从起始节点S到达节点n所走的总路程，也就是搜索到达节点n时已经进行任务分配的总的

ALV到达作业地点的估计时间.h（n）是未分配的ALV到达每个作业地点的估计时间里最小的m个的总

如图2所示，在搜索到节点11时，f（n）小于OPEN表中所有点的f（n）值，结束搜索.根据推理可得， S1511路径为最优路径，总的ALV到达作业地点的估计时间为110 s，节点11代表的意义就是ALV的作业任务分配方案，也是问题的解，即任务1分给ALV1，任务3分给ALV2，任务2分给ALV3.

在上述案例中，若不考虑从节点n到目标节点最佳路径的估计代价h（n），只考虑目前从起始节点到节点n的实际代价g（n），也可以看作h（n）=0，此时f（n）=g（n），即贪婪算法.其搜索过程见图3.从图中可以看出，到达目标节点的最优路径为S1511，最短路程与用A*搜索算法得到的相同，都为110 s，但贪婪算法的搜索点数多于A*算法.从这个例子可以看出，A*算法中h（n）的作用是巨大的.

4 算例分析

4.1 A*搜索算法与贪婪算法对比实验设计

为验证A*搜索算法适用于大型集装箱码头ALV实时分配问题，设计几组实验.实验中使用几组实验数据（ALV任务分配的到达作业地点的估计时间），用贪婪算法和A*搜索算法对ALV实时分配问题进行求解，对比两种算法的求解结果，分析A*算法解决大型集装箱码头ALV实时分配问题的可行性，同时也验证A*算法的优越性.

对a辆ALV和q个任务进行任务实时分配，ALV到达作业地点的估计时间为a×q的矩阵.本文设计8组实验，分别是a辆ALV和q个任务（a=q=6，7，…，13）.实验数据是几组实验的ALV到达作业地点的估计时间矩阵，分别为a×q的时间矩阵，代表实验问题的规模，相应的实验组为a×q组，每组进行5次实验，分别对每组实验的5次实验结果取平均值.

用相同的软件分别编写利用A*搜索算法和贪婪算法求解ALV实时分配问题的程序，并在同一台笔记本电脑上运行.两种算法使用的实验数据相同，求解出来的最短路径的最优值也相同.在此问题中，这些分配方案是最优的，在第3节中已经证明.表3所示是两种算法每组实验在求解过程中的运行时间和总搜索点数的对比.通过对比可以看出，A*搜索算法的求解时间和总搜索点数明显少于贪婪算法.

如图4和5所示是求解运行时间和总搜索点数

的平均值变化趋势.从图4和5中可以看出，贪婪算法的运行时间和总搜索点数随求解问题规模的变大迅速增加，而A*搜索算法变化得比较慢.这说明，在遇到大规模的求解问题时，A*搜索算法运行时间和总搜索点数不会突然变大，求解速度所受的影响不大.

4.2 A*搜索算法性能测试

为进一步验证A*搜索算法的求解速度，在上述实验的基础上用A*搜索算法对14×14至17×17规模的ALV实时分配问题进行求解，实验运行时间和总的搜索点数的平均值见表4.

大型集装箱码头为一艘船最多配备6台QC，每台QC分配2辆ALV，即为同一艘船服务的ALV的最大数量为12台，因此ALV实时分配问题的最大规模为12×12，去掉部分正在运输集装箱的ALV，大多数情况实时分配的规模在10×10以内.从表3可以看出，10×10规模的问题用A*搜索算法求解的时间在0.3 s左右.从表3和4可以看出，如果问题的规模加大，A*搜索算法的计算时间不会出现急剧的增长.因此，在计算时间上，A*搜索算法完全可以满足解决大型集装箱码头ALV实时任务分配问题的需求.

5 结束语

本文在大型自动化集装箱码头的背景下，根据码头的新特点和FCFS分配的缺陷，设计了基于触发事件的ALV作业任务实时分配方式.设置了一组触发事件触发ALV实时分配，并以总的ALV到达任务作业地点估计时间最短为目标，建立了一个ALV实时分配模型.选用A*搜索算法对分配模型进行求解，通过与贪婪算法的对比验证A*搜索算法的优越性.对A*搜索算法求解大型集装箱码头的ALV实时分配问题的求解速度和稳定性进行实验测试，验证了选用A*搜索算法是可行的.

参考文献：

[1]

赵宁. 集装箱码头发箱任务的集卡指派模型[J]. 上海海事大学学报， 2011， 32（1）： 910.

[2]NGUYEN V D， KIM K H. A dispatching method for automated lifting vehicles in automated port container terminals[J]. Computers & Industrial Engineering， 2009， 56（3）： 10021020.

[3]ANGELOUDIS P， BELL M G H. An uncertaintyaware AGV assignment algorithm for automated container terminals[J]. Transportation Research Part E： Logistics and Transportation Review， 2010， 46（3）： 354366.

[4]LEE L H， CHEW E P， TAN K C， et al. Vehicle dispatching algorithms for container transshipment hubs[J]. OR Spectrum， 2010， 32（3）： 663685.

[5]RASHIDI H， TSANG E P K. A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals[J]. Computers & Mathematics with Applications， 2011， 61（3）： 630641.

[6]CAI Binghuang， HUANG Shoudong， LIU Dikai， et al. Optimisation model and exact algorithm for autonomous straddle carrier scheduling at automated container terminals[J]. Intelligent Robots and Systems （IROS）， 2011 IEEE/RSJ International Conference on. IEEE， 2011（4）： 36863693.

[7]轩华. 基于FCFS策略的带时间窗车队调度问题研究[J]. 交通运输系统工程与信息， 2013， 13（6）： 140157.

[8]SONG L Q， HUAGN S Y. A hybrid metaheuristic method for dispatching automated guided vehicles in container terminals[J]. Computational Intelligence in Scheduling （SCIS）， 2013（8）： 5259.

[9]ICHOUA S， GENDREAU M， POTVIN J. Vehicle dispatching with timedependent travel times[J]. European Journal of Operational Research， 2003， 144（2）： 379396.

[10]GUJJULA R， GUNTHER HO. The impact of storage block assignment for import containers on AGV dispatching in highly automated seaport container terminals[J]. Industrial Engineering and Engineering Management， 2008（8）： 17391743.

[11]LIU ChinI， LOANNOU P. A comparison of different AGV dispatching rules in an automated container terminal[J]. Intelligent Transportation Systems， 2002（6）：880885.

[12]张海涛， 程荫杭. 基于A*算法的全局路径搜索[J]. 微计算机信息， 2007（23）： 238240.

[13]李淑霞. 基于A*的路径规划算法研究[J]. 福建电脑， 2013（3）： 99100.

（编辑 贾裙平）