自动化码头双ASC优先权规则及避让方案仿真

景贞文， 韩晓龙

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



自动化码头双ASC优先权规则及避让方案仿真

景贞文， 韩晓龙

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

摘要：为了减少自动化集装箱码头中，由于双自动堆垛起重机(双ASC)之间互相干扰造成的完工时间的延迟，提出9条优先权分配规则和两种避让方案——直接避让和动态暂存区。为了选择最合适的分配规则和避让方案，在回顾相关研究及反复实验的基础上，仿真实验将总任务数设置为100个，根据海侧任务比例(30%、40%、50%、60%、70%)将实验划分为5个等级。仿真结果表明，在80%的实验中，直接避让比动态暂存区的避让方案的最短完工时间少至少30 s；规则LonOri(选择在完成当前任务的前提下，距离下一任务的始发地具有最短运行时间的ASC赋予其优先权)或者规则LonFin(选择花费更多时间完成当前任务的ASC赋予其优先权)可以在至少60%的试验中取得最短完工时间。研究结果表明，规则LonOri和LonFin以及直接避让都可以有效减少完工时间。

关键词：双自动堆垛起重机(双ASC)； 仿真； 优先权分配； 动态暂存区

随着经济全球化的发展，集装箱码头的货运工作量持续增加，越来越多的集装箱码头急切地实施新型自动化技术提高效率来维持竞争力。其中，自动堆垛起重机(automated storage cranes，ASC)作为自动化集装箱码头的主要自动化设备，也越来越多地应用到码头中。

ASC是轨道吊的一种，一般放置在垂直于码头泊位的堆场箱区，并在堆场箱区顶端通过水平运输系统与岸边对接。ASC在箱区将集装箱吊起并沿箱区轨道搬运至目的地。每个箱区上通常运行有2个ASC：一个负责海侧作业，一个负责陆侧作业。2个相同型号的ASC运行在同一轨道上，由于不能互相穿套，作业时可能产生干扰。本文的研究重点就是双ASC产生干扰时的优先权分配以及避让规则问题。

对于堆场起重机设备的研究，国内外许多学者都集中在通过算法优化场桥的调度，例如Ng[1]利用基于动态规划的启发式算法研究了堆场内只有一条是双向车道的前提下，多台场桥设备操作优化的问题；Zhou等[2]在双场桥起重机调度研究中提出了交换点的概念，用优化算法最小化延迟时间和延迟的工作数量；文献[3-6]通过建立混合整数规划模型以及算法的应用解决场桥的调度问题；Chang等[7]提出新的动态滚动策略来优化场桥调度问题。也有学者从多种设备的集成调度来研究场桥调度，如Lau等[8]考虑多种港口设备资源的同步化问题，集成调度等；文献[9]以集卡等待时间为最小目标建立了单场桥动态调度的混合整数规划模型；Carlo等[10]重点研究了新型自动化存取系统(AS/RS)中两台设备的作业分配问题。与本文研究方向类似的有：Park等[11]对自动化码头中双RMG提出了基于启发式和局部搜索的实时调度方法，并提出了通过分配优先权给海侧ASC以及当前工作序列排名靠前的RMG来解决RMG之间的干扰的方法；Dorndorf等[12]提出了1个由3个ASC组成的ASC系统，其中有1个ASC是比较大的，另外2个ASC是比较小的且是相同大小的，这样，2个小的ASC就会从大的ASC下穿过。他们的研究的目标是最大化生产力，同时阻止延迟干扰的发生。

本文与以上研究的主要不同在于提出了9条优先权分配规则以及直接避让和动态暂存区(交换点)避让2种避让方案来实现双ASC的调度。

1系统和问题描述

本文研究的系统和问题都是在以下假设下进行的。

1)双ASC速度相同，且不因承重改变。

2)干扰产生之后系统才能识别干扰，而不能实现预见干扰。

3)堆场存贮能力足够。

4)ASC作业时间不变。

图1给出了本文研究的堆场双ASC布局模型。模型中有2辆ASC，C1和C2，位于堆场箱区的两侧，分别负责海侧和陆侧的作业。在箱区两端各有一个暂存区，负责暂存来自海陆两侧的任务集装箱。

图1　双ASC布局模型

图1中，双ASC在到达各自的任务地点前，可能会产生干扰。导致任务不能按时完成，造成整个系统完工时间的延迟。为了使系统快速地完成任务，要选择最佳的优先权分配以及非优先权ASC避让方案，减少干扰引起的延迟。因此，本文的研究重点是：1)在已知任务序列的情况下，确定两辆ASC的优先权分配规则；2)非优先权的ASC避让方案。

关于ASC之间优先权分配规则，会在本文第3部分进行详细的介绍。关于非优先权的ASC的避让方式，本文提出了2个方案:一是直接回避，非优先权ASC退让到不影响优先权ASC作业而又能够最小化等待时间的地点等待；方案二是动态暂存区，即选择一个距离优先权ASC作业点最近的可行区作为动态暂存区，将非优先权ASC的任务暂时存放在动态暂存区，等待优先权ASC作业完毕后，运行到动态暂存区继续完成非优先权的ASC的作业任务。

本文借助图表识别ASC避让方案的运动轨迹:Fij和Gij分别代表C1和C2的运动轨迹，其中i=1,2,…,n代表ASC要执行的第i个作业任务，j=1，2，3，4，2+,4+代表ASC执行一个作业任务要完成的步骤，具体步骤如表1所示。例如F23代表C1正在执行第2个作业任务的第3步，即C1正在把第2个作业任务的目标集装箱运输到目标贝位。

表1　步骤描述

表2　双ASC作业任务顺序

基于表2给出的双ASC作业任务顺序，图2给出了2个大小不一的ASC在可穿套情况下的作业轨迹图。

图2　可穿套双ASC作业轨迹

通过分段函数图表可以简单地判断，在不可互相穿套的双ASC作业下，如果按照给定的作业顺序操作，C1和C2会在第5个贝位附近发生干扰。为了避免这种干扰，如果采用动态暂存区的避让方案，并赋予C1优先权，双ASC的作业轨迹图如图3所示。其中，在t=4附近时，C2由第6个贝位返回至第7个贝位，G14+代表C2将第1个作业任务暂时存放在第7个贝位(动态暂存区)，相应地，在t=6时，C1完成第1个作业任务，FG11代表C1正在向C2的第1个作业任务的暂存区(第7个贝位)运行，FG12+代表C1正在动态暂存区拾取C2的第1个作业任务，FG13代表C1正在将C2的第1个作业任务运输到其目标贝位(第4个贝位)，FG14+代表C1将C2的第1个作业任务集装箱释放到目标贝位的过程，则在t=11时，C2的第1个作业任务完成。通过图3可以得到在动态暂存区避让方案中各作业任务的实际完工时间。

图3　动态暂存区的双ASC作业轨迹

2规则

参照Carlo等[13]的观点，本文提出了9条双ASC优先权分配规则。

R1:(PricC1)C1一直有优先权。

R2:(PricC2)C2一直有优先权。

R3:(AdvFun)选择距离当前任务最近的ASC，赋予其优先权。

R4:(ShoOri)在完成当前任务的前提下，选择距离下一任务的始发地有最短运行时间的ASC，赋予其优先权。

R5:(LonOri)在完成当前任务的前提下，选择距离下一任务的始发地有最长运行时间的ASC，赋予其优先权。

R6:(ShoFin)选择花费较短时间完成当前任务的ASC，赋予其优先权。

R7:(LonFin)选择花费较长时间完成当前任务的ASC，赋予其优先权。

R8:(RemReq)选择剩余任务最多的ASC，并赋予其优先权。

R9:(Rand)随机赋予ASC优先权。例如，每个ASC有50%的可能拥有优先权。

以上9条规则以及第2部分中提到的直接避让和动态暂存区的避让方案都会通过仿真软件实现。要注意的是，本文提出这些优先权分配规则的目的是实现堆场双ASC作业的最短完工时间，但是每个规则适用的方案不同，并不是每条规则都能实现较短的完工时间。

3建模仿真

3.1仿真建模

eM-Plant是目前比较成熟的功能强大的作业系统仿真软件，它是面向对象的、图形化的、集成的建模、仿真工具[14]。集装箱码头作业系统是一个复杂的离散系统，在eM-Plant中，通过修改SingleProc、Entity、Transporter、Bay等对象的属性，可以将这些对象抽象成为岸桥、AGV、ASC、堆场、集装箱等港口设备，来实现集装箱码头作业的仿真。最重要的是，eM-Plant可以运用SimTalk语言为不同的对象编写Method。Method可以用来修改对象的属性，控制对象的运动，本文也是通过大量的Method在仿真中实现双ASC之间9条规则和2种避让方案的。

3.2仿真参数设置

本文研究的仿真模型主要包括港口作业的几个过程：岸桥移动过程、装载过程、卸载过程;AGV装载过程、搬运过程、卸载过程;ASC装载过程、搬运过程、卸载过程[15]。不管在实际操作还是仿真实验中，由于资源调配不均或者突发状况等，在每个过程中都可能存在等待时间。为了便于仿真模型的运行以及数据分析工作，本文将仿真模型中各装卸设备的作业时间进行了简化，具体如表3所示。

表3　仿真实验参数设置

在不考虑其他因素的情况下，任务量是对完工时间影响最大的因素，是仿真实验中重要的输入参数。考虑到仿真模型中堆场的存储能力以及仿真结果的准确性，本文将仿真实验的任务量设为100个。此次仿真实验中，堆场任务包括海侧进口任务和陆侧进口任务，为了说明9条优先规则和2种避让方案的适用情况，仿真实验根据海侧任务比例划分为5个等级，具体如表4所示。同时，完工时间作为主要的衡量数据，也是该仿真系统的主要输出参数。

表4　仿真实验等级设置

3.3仿真结果分析

从直接避让的仿真结果(表5)可以看出，在5个等级实验下，每个等级最优的2个优先权分配规则分别是：LonOri，LonFin；LonFin，RemReq；PriC1，LonFin；PriC1，LonOri；LonOri，RemReq。而且规则LonOri和LonFin都在3个等级的试验下取得较短完工时间，所以，在直接避让的方案中，最佳的优先权分配规则应该是LonOri(在完成当前任务的前提下，选择距离下一任务的始发地有最长运行时间的ASC，赋予其优先权)和LonFin(选择花费较长时间完成当前任务的ASC，赋予其优先权)。

仿真实验也给出了直接避让方案下的延迟时间，结果如表6所示。从结果可以看出，AdvFun有最小的延迟时间，这与表5得到的最小完工时间是冲突的，经过分析，原因可能有以下几点：1)在不同等级的实验下，产生的干扰次数是不一样的；2)延迟时间与产生干扰时双ASC所处的位置有关。

表5　直接避让方案的完工时间仿真结果

表6　直接避让延迟时间

动态暂存区避让方案的仿真结果如表7所示。由于动态暂存区的避让方案比直接避让更加复杂，也面临着更多的可能性。所以，各优先权分配规则的优势并不明显，不同等级试验下的完工时间差别比较大。经过对比可以发现，在动态暂存区避让方案下，有4个等级的最短完工时间比直接避让的最短完工时间长，所以综合稳定性以及最短完工时间可以看出，直接避让的避让方案比动态暂存区更有优势。此外，即使动态暂存区在避让方案中并不是最优选择，但规则LonOri和LonFin仍是这个方案中相对具有优势的分配规则。

表7动态暂存区避让方案的完工时间仿真结果

Tab.7Makespan simulation results of the dynamic exchange area

从图4来看，等级Ⅲ的仿真结果较为平缓而且明显优于其他等级的试验结果。相比之下，海陆两侧的任务数差别越大，其完工时间越长，而且波动越大。因此，在堆场双ASC的实际操作中，当海陆两侧任务数差别不大时，可以选择LonFin；当海侧任务明显大于陆侧任务数时，选择RemReq；当海侧任务明显小于陆侧任务时，选择LonOri。此外，在避让方案的选择上，直接避让比动态暂存区更加优化可行。

图4　仿真结果折线图

综上所述，由于并不存在对于每个等级实验都是最优的分配规则，所以就整体而言，LonOri和LonFin是最具优势的优先权分配规则。直接避让的避让方案比动态暂存区的避让方案有明显的优势，所以本文推荐直接避让的避让方案。

4结论

本文重点研究了双ASC作业工艺下，双ASC之间优先权分配规则的问题，提出了9条优先权分配规则以及直接避让和动态暂存区两种非优先ASC避让方案。以最小化完工时间为目标，并以其为衡量标准，通过5个等级的仿真实验，对9条规则和2种避让方案进行了评估。结果证明，在80%的实验中，直接避让比动态暂存区的避让方案的最短完工时间少至少30 s，规则LonOri 和 LonFin可以在至少60%的实验中取得最短完工时间。因此，本文得到整体而言最具优势的优先规则LonOri 和 LonFin，而动态暂存区的避让方案从仿真结果以及现实的堆场管理来讲都不是一个较好的选择。虽然本文的研究得到了较为理想的结果，但是也存在许多不足，比如，由于技术不足，不能在仿真过程中放入集装箱出口过程；缺乏对固定暂存区的思考；仿真实验中的等级设置考虑不足可能会影响到仿真结果，等等。这些问题都会在以后的研究中一一解决。

参考文献：

[1]NG W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research, 2005, 164(1):64-78.

[2]ZHOU W, WU X. An efficient optimal solution of a two-crane scheduling problem[J]. General Information, 2009, 26(1):31-58.

[3]KIM K H, PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research, 2004, 156(3):752-768.

[4]乐美龙, 林艳艳, 范志强. 基于两阶段启发式算法的多场桥作业调度研究[J]. 武汉理工大学学报, 2012, 34(1):60-65.

LE Meilong, LIN Yanyan, FAN Zhiqiang. Research on multi-yard-crane scheduling problem based on two-phase heuristic algorithm[J]. Journal of Wuhan University of Technology, 2012, 34(1):60-65.

[5]赵磊, 胡志华, 李淑琴. 基于作业均衡的集装箱堆场箱区场桥作业调度[J]. 武汉理工大学学报, 2013, 35(1):69-74.

ZHAO Lei, HU Zhihua, LI Shuqin. Container yard crane scheduling for operations balance between yard cranes[J]. Journal of Wuhan University of Technology,2013, 35(1):69-74.

[6]何军良, 宓为建, 严伟. 基于爬山算法的集装箱堆场场桥调度[J]. 上海海事大学学报, 2007, 28(4):11-15.

HE Junliang, MI Weijian, YAN Wei. Container yard crane scheduling based on hill-climbing algorithm[J].Journal of Shanghai Maritime University, 2007, 28(4):11-15.

[7]CHANG D, JIANG Z, YAN W, et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics, 2011, 25(3):485-494.

[8]LAU H Y K, ZHAO Y. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research, 2008, 159(1):665-682.

[9]GUO X, HUANG S Y, WEN J H, et al. Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information[J]. Advanced Engineering Informatics, 2011, 25(3):472-484.

[10]CARLO H J, VIS I F A. Sequencing dynamic storage systems with multiple lifts and shuttles[J]. International Journal of Production Economics, 2012, 140(2):844-853.

[11]PARK T, CHOE R, OK S M, et al. Real-time scheduling for twin RMGs in an automated container yard[J]. Or Spectrum, 2010, 32(3):593-615.

[12]DORNDORF U, SCHNEIDER F. Scheduling automated triple cross-over stacking cranes in a container yard[J]. Or Spectrum, 2010, 32(3):617-632.

[13]CARLO H J. Priority rules for twin automated stacking cranes that collaborate [J]. Computers & Industrial Engineering, 2015, 6(1):5-20.

[14]施於人,邓易元. EM- Plant 仿真技术教程[M]. 北京:科学出版社,2009.

[15]张少凯, 韩晓龙, 胡少龙. 新旧工艺下集装箱港口装卸设备配置仿真研究[J]. 广西大学学报(自然科学版), 2013, 38(2):368-373.

ZHANG Shaokai，HAN Xiaolong，HU Shaolong. Simulation of equipment allocation under two different handling technologies[J]. Journal of Guangxi University(Nature Science Ed, 2013, 38(2):368-373.

Twin ASCs Priority Rules and Avoidance Plans Simulation in Automated Container Terminal

JING Zhenwen， HAN Xiaolong

(Logistic Research Center, Shanghai Maritime University, Shanghai 201306, China)

Abstract：In order to reduce the delay of makespan caused by the interference between the twin ASCs in automated container terminal, nine priority rules and two avoidance plans are proposed: direct avoidance and dynamic exchange area. To choose the best priority rules and avoidance plans, on the basis of relevant research review and repeated experiments, the total number of tasks is set to 100, and the experiments will be divided into five levels according to the proportion of seaside tasks (30%, 40%, 50%, 60%, and 70%). The simulation results show that the shortest makespan in direct avoidance will be at least 30 seconds shorter than that for dynamic exchange area in 80% of the experiments; rules LonOri (giving priority to the ASC with the longest travel time to the origin of the next request, upon completion of the current request) and LonFin (giving priority to the ASC with the longest time to finish the current request) can get the shortest makespan in at least 60% of the experiments. The results show that the rules LonOri and LonFin and direct avoidance can effectively reduce the makespan.

Key words：twin automated storage cranes(twin ASCs); simulation; priority assignment; dynamic exchange area

收稿日期：2015- 07- 15

基金项目：上海市科委能力提升资助项目(14DZ2280200)

作者简介：景贞文(1991-)，女，河南省人，硕士研究生，主要研究方向为自动化码头仿真.

doi:10.3969/j.issn.1007- 7375.2016.02.019

中图分类号：TP391.9

文献标志码：A

文章编号：1007-7375(2016)02- 0128- 06