摘 要:针对集装箱装卸设备作业相互耦合的特点,设计了基于多智能体的协同调度优化模型。首先应用带有阻塞限制的混合流水车间模型构建了调度模型,随后应用蚁群算法得到初始方案,最后应用多智能体的合同网机制对方案进行调整。仿真结果显示,该调度方法具有较好的可行性。
关键词:集装箱码头;装卸设备;集成调度;智能体
集装箱码头在有限的作业空间上布置了多种装卸设备,如岸桥、场桥、集卡和自动导引运输车(AGV)等,通过这些设备间的协调作业完成码头的物流任务。在日常运作中管理者需要对装卸设备进行调度以提高作业效率,而这些决策又常常相互影响、相互制约,因此针对集装箱码头装卸设备的调度和协调是一个比较复杂、困难的问题。
1 研究现状
近年来,国内外很多学者针对集装箱码头装卸设备调度及优化问题展开了研究。Lee[1]研究了集装箱港口中岸桥的作业顺序分配问题,建立了考虑桥吊互不干涉约束的混合整数规划模型,并提出了模型的启发式遗传算法。计明军和靳志宏[2]研究了基于时间最短的集卡线路优化模型,并应用进化算法求解模型,但未讨论集卡配置问题。这些研究取得了丰硕的成果,但也存在有待改进和提高的方面。现有研究中构建的模型大多针对码头单个设备(或单类设备)的模型,而忽略了作业设备的关联性,因此调度结果的可行性相对较差。
近年来,基于多Agent的复杂系统建模的最新发展,使得开展基于多Agent的码头装卸设备集成优化成为可能,如李斌和李文锋[3]应用多Agent方法对集装箱码头的协同生产调度问题进行了探讨,提出了集装箱码头集成服务系统的思想。杨鹏等[4]将Agent方法应用于场桥间的作业协调,但研究对象仅限于堆场的场桥作业环节。Agent系统属于分布式自治系统,具有高度的灵活性,但在决策实时性方面则往往难以满足系统要求。本文应用集中式决策和多Agent融合的方法,对码头装卸设备的协同调度问题开展研究。
2 装卸设备调度集成建模
本文将装卸设备集成调度问题分解为存在关联性的三个问题:(1)装卸设备的集成调度建模问题;(2)集成调度模型的求解问题;(3)基于多智能体的调度方案柔性调整问题。其中问题(1)的建模过程中可以忽略装卸设备初始位置及其作业过程中的相互影响等因素;而问题(2)得到的调度结果只是初始方案(或称为粗方案);在问题(3)中需要设计设备Agent的避让规则以及作业任务调整规则,经过仿真、调整得到最终的细化调度方案。
2.1 问题描述
集装箱码头存在岸桥作业、水平运输和场桥作业三类操作,对应设备分别为岸桥、集卡、场桥。集装箱作业需要在三类设备中依次选择完成任务,但不存在环节间的缓冲区。基于码头作业流程的特点,应用带有阻塞限制的混合流水车间模型(NWHFS)对其描述。
本文基于以下假设构建了集成调度模型:(1)由于自动导引车(AGV)在国内使用较少,因此假设装卸设备仅包括岸桥、场桥和内部集卡(如无特殊注明,以下集卡均表示内部集卡);(2)模型中仅考虑船舶的卸载作业(装船作业与此类似,仅顺序相反);(3)忽略装卸设备作业细节,同类设备能力相同,完成相同任务的耗时与设备所处位置无关。
2.2 基于MAS的柔性调度方案
考虑将装卸设备映射为Agent,根据设备的特点和作业规则为Agent设置冲突避让规则,应用合同网机制为设备设计作业任务调整规则。模型中共设置岸桥、场桥和集卡三类Agent,下面将对各类Agent的冲突消解机制和任务调整机制进行介绍。
2.2.1 冲突消解机制
场桥Agent的冲突消解机制:在仿真模型中,为场桥Agent设置圆形冲突探测区,一旦出现探测区的重叠,则重叠的场桥Agent各自提出修改路径的代价函数——修改路径的移动成本。最终成本最小的Agent调整路径,若成本相同,则随机选择Agent调整路径。
岸桥Agent的冲突消解机制:岸桥仅能够在岸边做一维移动,岸桥Agent也具备冲突探测区,当岸桥Agent发生移动冲突,则选择外侧岸桥Agent向外侧移动等待。
在天津地区集装箱码头的调研过程中了解到,由于验放闸口的入场集卡数量控制功能,国内码头集卡作业中极少出现冲突或死锁,因此模型中假设集卡Agent不存在冲突问题。
2.2.2 装卸任务调整机制
在模型中为装卸设备Agent设置:忙碌、空闲和冲突等待状态。当Agent正在固定位置执行装卸任务或向目标工位移动,其状态为忙碌;当Agent完成其全部装卸任务序列,其状态为空闲;当Agent被其他Agent阻挡,其状态为冲突等待。
当系统中出现处于空闲或冲突等待状态的Agent,则忙碌状态的设备Agent将对尚未完成的任务进行招标。由空闲和冲突等待状态Agent及其自身竞标,竞标的报价函数为完成该装卸任务的移动时间。最终任务分配给报价最低的Agent,该Agent将其状态置为忙碌,原有Agent从其任务序列中删除该任务。
3 仿真结果
为了检验本文的调度方法,本文参考天津某码头布局方式、管制习惯和参考文献[5]提供的装卸设备参数进行仿真实验,仿真采用的软件为NetLogo。应用Agent方法进行调度方案修正的记为A试验;未采用MAS方法修正调度方案的记为B试验。为了确保B试验能够完成全部装卸任务,为其设置了简单的冲突处理机制。仿真结果如图1、图2所示。
图1中由于装卸设备之间缺乏有效的协调机制,B的总任务完成时间随任务量的增长而显著增加;由于A中采用了协商机制,具备冲突消解措施,任务完成时间并未显著增长。图2中卸载的集装箱数量为60。在A实验中,采用了基于Agent的冲突条件和任务再分配机制,因此,装卸设备间存在协作和协调关系,能够有效发挥装卸设备的潜力;而由于设备移动路径冲突的存在,并且缺乏任务分配平衡机制,因此B实验中,总完工时间并未随装卸设备数量的增加而显著降低。
在本文的研究中,MAS模型仅用于最初调度方案的调整和优化,如果初始方案不可行度较高,则最终调整方案的结果也较差。今后将考虑根据Agent仿真结果构建禁忌表,在Agent仿真结果的基础上应用算法再优化,并且还要考虑装卸设备作业时间不确定性等方面的因素,使得模型更加真实地反映集装箱码头的操作进程。
参考文献
[1] LEE D H, Wang Huiqiu, Miao Lixin. Quay crane scheduling with non-interference constraints in port container terminals[J]. Transportation Research part E, 2008, 44:124- 135
[2] 计明军,靳志宏.集装箱码头集卡与岸桥协调调度优化[J].复旦学报,2007(8):476-480.
[3] 李斌,李文锋.基于MAS的集装箱码头物流系统协同生产调度体系[J].计算机集成制造系统,2011,11(17):2502-2513.
[4] 杨鹏,柴小燕,孙俊清.集装箱码头场桥协同调度研究[J].计算机工程与应用,2011,47(1):231-234
[5] 张煌,王少梅.基于遗传算法的泊位连续化动态调度研究[J].系统仿真学报,2007,19(10):2161-2164.