集装箱堆场收发箱管理Multi－Agent系统研究

周鹏飞，方金灿

（大连理工大学 水利工程学院，辽宁 大连 116024）

0 引 言

随着经济全球化以及世界贸易的发展，集装箱运输持续快速增长.集装箱吞吐量的增加以及船舶的大型化、高速化给集装箱码头生产管理提出了更高的要求.集装箱堆场是码头生产运作组织的关键环节，其运作管理需着眼于码头整体生产协调与效率提高.传统的集中式管理系统缺乏适应性，很难适应资源和决策分散的堆场优化管理.Multi－Agent system（MAS）可通过一系列分布式Agent协商解决复杂问题，具有分布性、协同性、并行求解等优点，符合堆场管理要求.

目前集装箱码头MAS的相关研究报道主要有：Botti［1］提出了集装箱码头的Multi－Agent应用模型；Degano等［2］将Multi－Agent技术应用于多功能集装箱码头进出口装卸优化，利用Agent对作业干扰事件进行检测；Yin等［3］针对动态泊位计划问题设计了基于遗传算法的泊位优化Agent，建立了分布式Multi－Agent系统；于蒙等［4］建立了基于MAS的集装箱码头智能生产调度系统框架，该系统考虑了泊位、岸桥、集卡等设施和设备的资源利用；徐健等［5］提出了基于MAS的自动码头调度算法，通过搜索资源Agent形成时间代价矩阵来指导Agent间的协作.

堆场收箱时箱位优化研究主要有Kim 等［6］考虑箱重等级，运用动态规划模型求解最少翻箱的堆存方案，Zhang等［7］修正了其翻箱量求解公式；Kang等［8］运用模拟退火算法和仿真研究了箱重分布确定条件下的出口箱箱位分配问题.王斌［9］和周鹏飞［10］假设进出口箱统计规律，分别基于不确定规划探讨了不确定条件下的堆场箱位优选问题.堆场发箱时翻箱优化研究主要有Kim等［11］提出的基于分支定界和启发式的提箱翻倒箱位优选方法，在此基础上徐亚等［12］提出了改进的启发式方法.

从以上分析可以看出，针对集装箱码头的Multi－Agent系统研究大多集中在泊位、场桥等码头资源管理方面.堆场收发箱作业作为集装箱码头重要的生产活动，涉及闸口、堆场、龙门吊等多个生产环节，其效率关系到码头生产成本和服务水平.本文针对码头堆场管理问题，探讨堆场收发箱管理Multi－Agent系统，以实现堆场收发箱分布式动态优化管理.

1 堆场收发箱管理Multi－Agent系统架构

1.1 堆场收发箱业务流程

堆场收发箱作业主要在闸口和堆场作业区进行，涉及箱位和堆场龙门吊等管理问题.闸口相关业务有：（1）在收箱过程中，闸口首先收到客户交箱请求；然后根据箱、车信息和堆场状态，优化分配箱位；制定并下发外卡的港内行车路线指令.（2）在发箱过程中，闸口首先收到客户提箱请求，核对箱信息无误后根据箱位置制定并下发外卡的港内行车路线指令.堆场相关业务有：（1）在收箱过程中，堆场首先根据收箱请求结合堆场状态优化分配箱位，然后调派龙门吊进行堆箱操作.（2）在发箱过程中，堆场首先根据提箱请求，查询目标箱位；若需翻箱则优选翻箱落位，然后调派龙门吊进行翻、取箱操作.在堆场收发箱过程中箱位分配不仅决定着堆场翻箱率，而且影响龙门吊、集卡的调配效果，进而影响码头整体作业效率，是其重要管理瓶颈.

1.2 系统架构

在对堆场收发箱业务流程分析的基础上，提出了集装箱堆场收发箱管理Multi－Agent系统基本架构，如图1所示.其中：（1）信息Agent，主要功能是提交箱预约和计划信息的标准化处理，包括根据箱抵港时间、箱重、目的港等信息分配箱属性值，根据到港时间计划建立提交箱序列等.（2）闸口Agent，主要功能是接收客户收发箱请求，转发客户收发箱请求，实时查询堆场状态.（3）堆场Agent，负责监控堆场状态，包括进、出口箱区.收箱时负责优化请求及数据集成发送；收箱完成后负责更新箱区数据.提箱时负责获取并转发目标箱位、翻箱落位优化请求及数据集成发送；发箱完成后负责更新箱区数据.（4）优化Agent，主要功能是优化求解，包括收箱时根据交箱序列及箱属性优化分配箱位及发箱时根据贝状态和提箱序列优化翻箱落位.（5）用户Agent，主要功能是堆场收发箱过程监控和查询.（6）数据库，包括堆场状态、提交箱序列、调度方案等信息数据.（7）知识库，主要包括箱操作、数据更新以及消息处理方面的知识规则，以C＃类库体现，供Agent群使用.

图1 集装箱堆场收发箱管理Multi－Agent系统架构Fig.1 Multi－Agent system architecture of container reception and distribution management of container yard

2 Agent模型设计

2.1 Agent基本结构设计

根据系统特点，单Agent按混合型设计，其基本结构如图2所示.用户界面初始化模块负责用户操作界面的布局和功能初始化，用户操作界面提供Agent交互接口和计算参数设置或重置功能.对象定义模块负责对单Agent资源对象或计算参数变量进行定义，如消息队列对象、消息监听线程对象等.Agent交互接口及计算参数设置模块负责设置MAS中Agent交互接口信息，如计算机IP、端口等，并负责设置堆场收发箱优化涉及的优化参数，如箱区和贝规模参数等.消息监听模块、消息判断处理模块以及消息发送模块实现Agent交互通信管理功能.其中，消息监听模块负责监听Agent消息并接收；消息判断处理模块通过与数据库和知识库内的消息队列匹配逐条分析并处理；消息发送模块负责发送Agent响应消息.限于篇幅下文主要探讨系统关键技术实现：堆场Agent消息处理与优化Agent的箱位分配.

图2 单Agent结构示意图Fig.2 Structure of single Agent

2.2 堆场Agent的消息处理

堆场Agent是集装箱堆场收发箱管理系统的核心，其工作流程如图3所示.当接收到消息后，堆场Agent首先对消息来源进行判断.若消息来自信息Agent，可判定系统在根据交箱预约信息进行收箱箱位分配，堆场Agent将该消息集成转发给优化Agent进行滚动调度，形成收箱箱位分配初始方案；若消息来自闸口Agent，需判断消息请求类型，然后集成转发箱位优化请求给优化Agent 或指派提箱作业；若消息来自优化Agent，需判断优化结果消息类型，输出优化结果并将消息集成转发给用户Agent，若需进一步优化求解，堆场Agent将生成并发送优化请求给优化Agent.堆场Agent消息处理伪代码略.

2.3 优化Agent的箱位分配

2.3.1 收箱箱位分配 码头出口箱收箱基本过程是：（1）客户交箱预约；（2）根据预约交箱及相关信息制定箱位分配计划，交箱序列动态更新；（3）集装箱进场时，指定箱位，完成交箱.考虑码头出口箱收箱特点，将收箱箱位分配分为两阶段，形成两级调度：a.根据预约交箱预分配箱位；b.交箱时根据动态交箱序列调整预分配.两级调度流程如图4所示.基本流程是：在滚动调度的基础上，首先根据预约交箱信息，运用禁忌搜索算法得到初始箱位分配方案.当箱进场时，若当前进场箱序列和初始方案箱序列一致，则保持原调度方案不变；若不一致时，则进行实时调度，调整原调度方案，形成再调度方案，并作为下一进场箱的初始调度方案.滚动周期结束时进行下一阶段滚动调度.

图3 堆场Agent工作流程图Fig.3 Work flow chart of storage yard Agent

图4 两级调度流程图Fig.4 Flow chart of two－levels scheduling

2.3.2 发箱翻箱落位优化 考虑到集装箱堆场管理实际，本文假设：①翻箱在同贝内进行；②提箱时提箱序列和贝内箱分布已知；③提箱过程中贝内无新箱进场.首先按提箱序列，分别给箱编号为1，2，…，N（N为贝内箱数），提箱越早，编号越小.为表述方便，称当前翻倒箱所在栈为当前栈，称贝内其他栈为候选考察栈.本文考虑实际集装箱翻倒概率不同，改进了文献［12］的翻箱期望估计公式，在此基础上提出了基于翻箱期望最小的翻箱落位优化方法.改进后的考察栈翻箱期望E（e，n）估计可用式（1）递归求解：

式中：e为考察栈剩余空箱数，n为栈内箱最小编号，p（e，n，P）为箱P翻倒到考察栈可能性代表值，用近似式（2）求解，E（0，n）＝0.

其中a为候选栈最小箱序总和，b为考察栈箱序总和，其他符号解释同前.

翻箱前后只有当前栈和考察栈的预期翻箱量改变，因此可根据E（e，n）求解当前栈和考察栈在翻箱前后总翻箱增量，选取增加量最小的考察栈为翻倒最佳落箱位.求解过程伪代码略.

3 Agent的通信机制与协作机制

3.1 Agent的通信机制

该系统采用点对点方式进行通信，为确保Agent群间通信的完整性与实时性，选择基于TCP／IP协议的Socket进行通信，通信机制如图5所示.Socket监听模块负责监听并接收字节流消息，经消息转换模块将其转换为消息对象，并将其加入消息对象队列，基于FIFO 原则处理消息对象队列.消息识别－处理模块用于识别消息来源，并根据消息内容执行响应操作；根据响应操作执行结果，消息生成模块生成响应消息并转发；知识库包含消息转换、识别与处理、生成等的规则和知识.

图5 Agent通信机制Fig.5 Communication mechanism between agents

模型中，Agent群间通信的消息形式采用C＃自定义消息类AgentMessage，其部分字段及其意义见表1.该消息类包含两类字段：（1）标志消息发送者、箱型等功能字段；（2）承载求解所需的数据字段，如标记进口箱目标箱号、堆场区段号的字段等.Agent群通信时，发送端生成消息对象并赋值，经XML 序列化后发出；接收端接收到消息后，反序列化数据得到消息对象，根据消息类型和字段值执行响应操作.为解决Tcp消息无边界问题，采取消息内容与长度同步发送机制.

表1 AgentMessage字段表Tab.1 Field chart of AgentMessage

3.2 Agent的协作机制

Agent间的协作是指Agent相互合作，协调工作，共同完成系统的目标和任务.系统中信息Agent、闸口Agent、堆场Agent、用户Agent、优化Agent须相互协作，完成各自预定的功能，才能实现堆场收发箱作业优化与管理，其协作过程如图6所示.

图6 Agent群协作过程Fig.6 Collaboration process of Agent group

4 系统实现与仿真算例分析

4.1 系统实现

本系统采用Visual C＃进行开发.以栈数×栈高为7×5时发箱为例，假设客户要求提取1号箱，则该系统各Agent协作完成该任务的过程为（为叙述简便起见，以下省略了各Agent与用户Agent交互过程）闸口Agent接收1号箱提箱请求，转发给堆场Agent；堆场Agent查询得到1号箱位置，转发给闸口Agent（制定行车指南），并判定是否需翻箱及优化，若需要，发送优化请求给优化Agent进行箱位优化（可有多个优化Agent实现并行），交互实现1号箱管理作业.闸口Agent与堆场Agent运行效果如图7所示.堆场收发箱管理MAS通过将收发箱管理任务分解并分配给闸口Agent、堆场Agent、优化Agent 等多个Agent，实现了堆场收发箱的分布式并行管理，并可分担计算时间成本；同时Agent间的实时动态交互实现了收发箱动态管理.

4.2 收箱管理算例仿真与分析

这里选取10和30个贝的堆场区段作为算例进行分析，区段内设1台龙门吊，最大堆存系数取90%.滚动调度长度和周期分别取3d和1d.仿真不同r×T（即栈数×额定堆存高度）和交箱动态变化度组合（交箱时间动态变化程度）的M＝50个算例，选取实际中常用的基于压箱最小与最近规则的启发式分配方法进行对比分析.

图7 闸口Agent、堆场Agent运行效果图Fig.7 Operation effect chart of gate Agent and storage yard Agent

表2给出了50组算例两种方法的平均对比结果，可以看出，10 和30 贝堆场区段不同条件下，两级调度算法效果均优于启发式分配算法，分别在10%和67%以上.这主要得益于两级调度算法综合利用了交箱预约信息和实时动态信息，所得解更趋近于全局最优.区段规模越大，两级调度算法优势越明显.通过对比不同交箱时间动态变化度的总成本变化趋势可看出，动态交箱时间变化度越小，即实时序列与预约序列相差越小，两级调度算法效果越好.表3给出了不同成本比例下2种算法调度效果对比，可以看出不同成本比例下两级调度算法调度效果均更好.

表2 不同区段规模4×3、6×4、7×5分布时两级调度算法与启发式分配算法调度效果对比Tab.2 Scheduling effect contrast between two－levels scheduling algorithm and heuristic allocation algorithm of 4×3，6×4and 7×5distribution of different yard section scales

表3 不同区段规模4×3分布时不同成本比例下两级调度算法与启发式分配算法调度效果对比Tab.3 Scheduling effect contrast between two－levels scheduling algorithm and heuristic allocation algorithm under different cost ratios of 4×3distribution of different yard section scales

在计算时间方面，两级调度算法中实时调度求解耗费时间不超过0.01s，满足实时性要求，这里主要分析滚动调度时耗.表4给出了两种区段规模的滚动调度求解耗时统计结果，可以看出，一般较大规模问题算法求解时间小于2 min，当问题规模非常大（区段规模为30贝，贝规模为7×5，集装箱约为900 个）时滚动调度耗时平均为249s.由于滚动调度针对预约交箱过程不要求实时求解，并且多个优化Agent求解是分布并行的，可满足实际应用要求.

表4 不同区段规模下滚动调度耗费时间Tab.4 Rolling scheduling time－consuming under different yard section scales

4.3 发箱管理算例仿真与分析

本文对不同r×T组合的M＝50个算例分别利用IH 算法［12］及提出的MAS 进行求解，结果见表5，其中N＝（r－1）×T＋1，为集装箱数.可以看出，MAS求解的平均翻箱量小，统计不同规模的贝分布，较IH 算法平均改进均在11%以上，最大相对改进在42%以上，且随着贝规模的增大，启发式分配算法较IH 算法改进有增大的趋势.

表5 翻箱优化算法的平均翻箱量、平均相对改进及最大相对改进Tab.5 Average number of relocation，average relative improvement and maximum relative improvement of container relocation optimization algorithm

5 结 论

堆场收发箱管理是集装箱码头的动态分布式问题.本文在对集装箱堆场收发箱作业流程分析的基础上，建立了堆场收发箱管理Multi－Agent系统模型，分析了Agent的基本结构和功能，提出了堆场收发箱作业优化Agent模型和算法，探讨了系统的通信和协作机制.系统算例仿真分析表明系统能够有效发挥Multi－Agent的分布并行动态性优势，提高收发箱管理效果，验证了系统的有效性和可行性.

［1］ Botti V J.Multi－Agent system technology in a port container terminal automation［J］.ERCIM News，2004（56）：37－39.

［2］ Degano C F，Pellegrinno A.Multi－Agent coordination and collaboration for control and optimization strategies in an intermodal container terminal ［C］／／IEEE International Engineering Management Conference.Cambridge：IEEE，2002：590－595.

［3］ Yin X F，Khoo L P，Chen C H.A distributed agent system for port planning and scheduling ［J］.Advanced Engineering Informatics，2011，25：403－412.

［4］ 于 蒙，王少梅.基于多Agent的集装箱码头生产调度系统建模研究［J］.武汉理工大学学报，2007，31（3）：494－497.YU Meng，WANG Shao－mei.Research on modeling of Multi－Agent－based scheduling system for container terminal ［J］.Journal of Wuhan University of Technology，2007，31（3）：494－497.（in Chinese）

［5］ 徐 健，陈启军.基于MAS的集装箱自动化码头调度算法［J］.系统仿真学报，2009，21（15）：4888－4991.XU Jian，CHEN Qi－jun.Multi－Agent system for scheduling of automated container terminal ［J］.Journal of System Simulation，2009，21（15）：4888－4991.（in Chinese）

［6］ Kim K H，Park Y M，Ryu K R.Deriving decision rules to locate export containers in container yards［J］.European Journal of Operational Research，2000，124：89－101.

［7］ ZHANG Can－rong，CHEN Wei－wei，SHI Le－yuan，et al.A note on deriving decision rules to locate export containers in container yards［J］.European Journal of Operational Research，2010，205（2）：483－485.

［8］ Kang J，Ryu K R，Kim K H.Deriving stacking strategies for export containers with uncertain weight information ［J］.Journal of Intelligent Manufacturing，2006，17（4）：399－410.

［9］ 王 斌.集装箱码头堆场的一种动态随机堆存方法［J］.系统工程理论与实践，2007（4）：147－154.WANG Bin.Dynamic and stochastic storage model in a container yard［J］.Systems Engineering－Theory＆Practice，2007（4）：147－154.（in Chinese）.

［10］ 周鹏飞.面向不确定环境的集装箱码头优化调度研究［D］.大连：大连理工大学，2005.ZHOU Peng－fei.Study on resource allocation under uncertainty environments in container terminal［D］.Dalian：Dalian University of Technology，2005.（in Chinese）.

［11］ Kim K H，Hong G P.A heuristic rule for relocating blocks ［J］.Computers and Operations Research，2006，33（4）：940－954.

［12］ 徐 亚，陈秋双，龙 磊，等.集装箱倒箱问题的启发式算法研究［J］.系统仿真学报，2008，20（14）：3666－3669，3674 XU Ya，CHEN Qiu－shuang，LONG Lei，et al.Heuristics for container relocation problem ［J］.Journal of System Simulation，2008，20（14）：3666－3669，3674.（in Chinese）.