有限缓冲空间下岸桥和自动升降车的集成调度

余孟齐，韩晓龙

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



有限缓冲空间下岸桥和自动升降车的集成调度

余孟齐，韩晓龙

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

摘要：为了解决自动化集装箱码头中岸桥和自动升降车(ALV)的集成调度问题,考虑ALV自身能够从地面提升集装箱的特点,提出码头前沿的缓冲区约束,建立以最小化ALV总移动时间和岸桥作业总延迟为目标函数的混合整数规划模型并进行了求解；通过数值实验将调度模型与同一问题中的自动导引小车(AGV)相比较,并对ALV的数量和缓冲能力进行灵敏度分析,结果表明在有限缓冲空间情况下,使用ALV集成调度方案的作业总成本比使用AGV的调度方案减少了近28.72%,验证了ALV在有限缓冲情况下比AGV有更好的性能，有助于提高集装箱码头整体作业效率和港口竞争力。

关键词：自动化集装箱码头;ALV;岸桥;有限缓冲空间;集成调度

在过去十年中，全球贸易快速发展，世界集装箱码头吞吐量在2011年增长了5.9%，达到历史最高水平(5.728亿标准箱)[1]。如今超过60%的深海普通货物通过集装箱运输，尤其是在经济发达、关系稳定的国家之间[2]。集装箱装运数量的增加会导致集装箱码头之间的竞争变得越来越激烈。因此，对于港口运营商而言，开发不同的优化算法和决策工具提高其性能和竞争力是非常重要的。自动化集装箱码头(ACT)将有助于到降低运营成本，提高集装箱码头的吞吐量[3]。

目前，国内外学者对集装箱码头装卸设备的调度已经有了一定的研究。HASSAN等[4]将集装箱码头的AGV调度问题制定为最低费用流问题的一个特例，并为解决该问题提出了NSA+(network simplex algorithm+)算法和贪婪车辆搜索算法。HOMAYOUNI等[5]将岸桥和AGV的集成调度制定为一个混合整数线性规划模型，并将Lingo软件的求解结果与模拟退火算法的结果进行对比，结果表明模拟退火算法在实际调度问题中具有更好的性能。HOMAYOUNI等[6]还研究了自动化集装箱码头岸桥、AGV和存储平台这3种设备的集成调度，并提出了一种遗传算法，对存储平台3个不同停留点的策略进行了检验，并将所提出的遗传算法与已有算法进行比较，结果表明遗传算法在调度范围内的作业次数增加条件下优于已有算法。国内学者康志敏[7]研究了自动化码头AGV路径优化和调度，建立了以无效等待时间最少的小车调度优化模型，并利用遗传算法对建立的模型进行分析求解。梁承姬等[8]对集装箱港口岸桥、集卡、场桥3种装卸作业设备的集成调度问题进行建模，并设计了一种矩阵编码方式的遗传算法对问题进行求解。BAE等[9]通过仿真研究比较了AGV和ALV的运行效率，仿真实验表明，ALV到达与AGV相同的生产力水平，使用的车辆数量比AGV少。NGUYEN等[10]为ALV交付作业的最优分配提出了一种混合整数规划模型，将模型中的缓冲区约束转化为时间窗约束，然后提出了一个启发式算法来解决带有优先约束和时间窗约束的调度问题。

当前研究中涉及岸桥和ALV的集成调度问题较少，笔者将重点探讨考虑自动化集装箱码头在有限缓冲情况下岸桥和ALV的集成调度，提出了一个以ALV的总移动时间和岸桥作业的总延迟时间最小化为目标函数的岸桥和ALV集成调度问题，并应用CPLEX求解该混合整数规划模型。通过算例验证该模型和方案对自动化集装箱码头实际资源调度均衡性的效果。

1问题描述

岸桥和ALV的集成调度问题是指在已知条件下合理调配岸桥和ALV的装卸作业，完成集装箱船舶任务的优化问题。装卸活动分为两个部分，①由岸桥执行的装卸活动，称为海边作业；②由ALV和自动化场桥(AYC)执行的装卸活动，称为岸边作业。卸载作业中，岸桥捡取集装箱放在码头前沿岸桥下的缓冲空间中；然后ALV捡取集装箱并将其传送到编组堆场；在编组堆场，ALV释放集装箱到堆场中转运点的缓冲空间；AYC捡取集装箱并将其堆放在海湾中空的位置。装载作业以与卸载作业相反的顺序执行。

ALV卸载作业的功能和职责是把集装箱从码头前沿传送到堆场，装载作业则是把集装箱从堆场传送到码头前沿。在卸载作业期间，岸桥从船头捡取集装箱并将其传送到缓冲区。考虑码头前沿和堆场有一定的缓冲空间，其中岸桥、AYC、ALV均可释放集装箱。岸桥或AYC可以直接从ALV上捡取集装箱或者把集装箱放在ALV上。然而，由于ALV自身有能力从地面上提升集装箱，如果缓冲空间是可用的岸桥可以将集装箱放在缓冲空间，但缓冲空间已满时岸桥和ALV必须等待。为了提高作业效率，降低船舶操作延迟，笔者以最小化的岸桥延迟时间和ALV移动时间为目标。

2模型假设

结合实际情况，对问题进行了合理简化，提出如下假设：①所有ALV的能力和形状都是相同的，且一次传送一个集装箱。②对于一个ALV共享策略被应用到调度过程，既不分配给特定类型的集装箱，也不分配给特定的起重机。这意味着没有ALV是专用于一个岸桥的。③不考虑ALV在导引路径中的拥塞。④ALV或岸桥拾取和释放集装箱的作业时间足够小，可以忽略不计。⑤ALV的移动时间、岸桥在码头和船只区域(TQ)的移动时间及其作业时间是预先确定的。⑥在双循环中，缓冲区中岸桥(或ALV)释放一个集装箱之后到缓冲区中ALV(或岸桥)捡取另一个集装箱之前的时间可以忽略不计。

3模型建立

(3)数学模型。其中目标函数为：

(2)

(3)

l∈K,i=1,2，…,mk,j=1,2,…,m

(4)

(5)

(6)

i=1,2…,mk-1

(7)

(8)

(9)

(10)

(11)

(13)

(14)

(15)

(16)

i=1,2,…,mk,j=1,2,…,ml

(17)

4算例实验

通过一组测试算例将具有有限缓冲空间的ALV调度所提出的模型与带有AGV的同样问题进行比较。表1显示了QC1应用于船舶作业的一个序列表例子，其以双周期的方式执行船舶作业。表2显示了QC1船舶作业中的事件及其符号。在表1最后一列中的最早事件时间是指岸桥作业在没有任何中断和延迟的假设下，岸桥传送集装箱到ALV或从ALV传送集装箱的时间。

表1　QC1船舶作业的序列表

注：QC1缓冲容量为2；船舶位置编号分别表示船舶的贝编号/行编号/列编号；堆场位置编号分别表示堆场箱区的编号/堆场贝的编号/行编号/列编号

4.1ALV与AGV 的目标值分析

10个测试算例来自于一个堆场具有6个转运点和码头前沿有6台岸桥的典型自动化集装箱码头。表3所示为算例中ALV和AGV的目标值对比情况。所有ALV和AGV的测试由CPLEX软件编程解决。表3中，CPLEX求出ALV与AGV目标值的比值范围为0.642 43～0.806 95。从数值结果可以观察到，在所有的测试算例中，具有有限缓冲空间的ALV比AGV的结果更好，通过增加ALV的数量，可以得到更好的结果和更早的完工时间。在有限缓冲空间情况下，使用ALV的集成调度方案的作业总成本比使用AGV的调度方案减少了近28.72%。

表2　QC1船舶作业的事件

表3　算例结果比较

4.2ALV的数量和缓冲能力的灵敏度分析

图1所示为ALV的数量对岸桥总延迟时间的影响折线图，可见岸桥的延迟时间随着ALV数量的增加而迅速减小。当ALV的数量超过一定的水平条件下，减少量可以忽略不计。对于缓冲空间容量的变化，岸桥的延迟时间随着缓冲空间容量的增加而减少。然而，当ALV的数量达到4时(如图2中所示)，缓冲区容量的变化不影响岸桥的延迟时间。

图1　ALV的数量对岸桥总延迟时间的影响折线图

图2显示了总延迟时间在有缓冲和没有缓冲情况的不同。当ALV的数量为2时，改进比率的范围为5.5%～18%。当ALV的数量为4时，差异由1.5%到2%。可以看出，随着ALV数量的增加，改进比率的差异减小。

图2　有缓冲区和无缓冲区改进比率对比图

5结论

笔者针对岸桥和ALV在有限缓冲空间下集成调度问题的一些特性和约束，建立了集成调度问题的模型；通过算例分析得知，ALV集成调度方案的作业总成本比AGV调度方案可减少28.72%，验证了ALV在有限缓冲情况下比AGV有更好的性能；在其他条件相同的情况下，ALV比AGV能更有效地提高港口作业效率，增加港口的经济效益。此外，ALV数量和缓冲能力的敏感性分析实验结果证明，增加ALV的数量可以减少岸桥作业的延迟；当ALV的数量较少时，缓冲空间的大小对岸桥作业的延迟时间影响很大，然而随着ALV数量的增加，影响也随之减小。

参考文献：

[1]NARGES K,NATHAN H.Integrated quay crane and yard truck scheduling for unloading inbound containers[J].International Journal of Production Economics,2015,159(1):168-177.

[2]HOAI M L,ADNAN Y,RIADH M.DCA for solving the scheduling of lifting vehicle in an automated port container terminal[J].Computational Management Science,2012(9):273-286.

[3]XIN J B,RUDY R N,GABRIEL L.Energy-aware control for automated container terminals using integrated flow shop scheduling and optimal control[J].Transportation Research Part C:2014,44(2):214-230.

[4]HASSAN R,EDWARD PKT.A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals[J].Computers and Mathematics with Applications,2011,61(3):630-641.

[5]HOMAYOUNI S M,TANG S H，NAPSIAH I.Using simulated annealing algorithm for optimization of quay cranes and automated guided vehicles scheduling[J].International Journal of the Physical Sciences,2011,6(27):6286-6294.

[6]HOMAYOUNI S M,TANG S H,MOTLAGH O.A genetic algorithm for optimization of integrated scheduling of cranes,vehicles,and storage platforms at automated container terminals[J].Journal of Computational and Applied Mathematics,2014,270(1):545-556.

[7]康志敏.集装箱自动化码头AGV路径优化和调度研究[D].武汉:武汉理工大学,2011.

[8]梁承姬，张松波.集装箱港口装卸作业设备集成调度[J].辽宁工程技术大学学报(自然科学版),2015,34(2):262-266.

[9]BAE H Y,CHOE R,PARK T,et al.Comparison of operations of AGVs and ALVs in an automated container terminal[J].Journal of Intelligent Manufacturing,2011,22(1):413-426.

[10]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):1002-1020.

YU Mengqi:Postgraduate; Logistics Research Center,Shanghai Martine University,Shanghai 201306,China.

[编辑：王志全]

文章编号：2095-3852(2016)01-0101-05

文献标志码:A

收稿日期：2015-07-14.

作者简介：余孟齐(1992-)，女，安徽安庆人，上海海事大学物流研究中心硕士研究生．

基金项目：上海市科学技术委员会工程中心能力建设项目基金资助项目(14DZ2280200)．

中图分类号：U691;U169.63;N945.12

DOI：10.3963/j.issn.2095-3852.2016.01.022

Integrated Scheduling of Quay Cranes and Automated Lifting Vehicles with Limited Buffer Space

YU Mengqi,HAN Xiaolong

Abstract：In order to solve the integrated scheduling of quay cranes and ALVs in automated container terminal,considering that an ALV are capable of lifting a container from the ground by itself,buffer constraints in an apron were suggested,a mixed integer programming model was set up,aiming to minimize the total travel time of ALVs and the total delays in QC operations.Then,CPLEX was used to solve this model.Finally,comparing the scheduling results between the proposed model for dispatching of ALVs and the same problem with AGV,and analyzing the sensitivity of the number of ALVs and buffer capacity.The results showed that the total cost in scheduling of ALV almost reduced by 28.72% compared with AGV,which confirmed that ALV with limited buffer space has better performance than AGV.The sensitivity analysis can help to improve the operation efficiency of container terminals and increase the competitive strength of the port.

Key words：automated container terminal; ALV; quay crane; limited buffer space; integrated scheduling