船舶制造具有小批量、大结构、严格按照订单等生产的特点,需要较大容量的仓储系统以满足对项目生产过程中的物资冗余度要求[1]。船企仓储类型有多种,对于露天堆场的仓储管理问题的研究主要集中在堆场内结构件的排布优化上[2];对于室内仓储问题的研究,主要集中在出入库、利库(剩余物料跨项目再利用)的流程上,对复杂出入库情况进行优化计算[3](包括推-拉生产方式)。船企中,不同仓储作业间存在竞争和冲突,需要与物资管理系统进行有效结合以协调仓储点活动,避免仓储和物流能力浪费。
国内外在仓储调度管理方面已有较多研究成果,如仓储动态实时化管理[4]、使用算法进行仓储调度优化[5]、供需结合的仓储管理[6]、仓储活动决策系统的建立[7]、面向料单的仓储配送[8]以及多仓储和多生产点条件下的仓储选择等。但对厂内物流能力等资源冲突情况下的仓储运作缺乏考量。
由于仓储在船企内的地理分布特性,船舶制造项目仓储问题是一个分布式问题,从提高自动化程度和仓储效率的角度来看,分布式人工智能(distributed artificial intelligence,DAI)技术匹配了该类问题求解的大部分特征,具有较好的预期[9];而多智能体系统(multi-agent system,MAS)是DAI领域所应用的比较成熟的技术之一。数字软件上的智能体Agent,是指驻留在某一环境下能够自主﹑灵活地执行动作以满足设计目标的行为实体;由多个Agent彼此互相通信并为完成共同目标协同工作组成的系统被称为多智能体系统(multi-agent system,MAS)[10]。文献[11]中即使用Agent用于仓储系统虚拟化设计,对仓储进程中各因素影响进行评估。在仓储管理方面,国外在2004年即开始利用智能Agent技术设计或改进仓储管理系统[12];国内也进行了MAS技术在仓储管理上的应用研究[13-14]并取得了一些研究成果。
为此,本文利用多智能体技术构建具备一定智能程度的、适用于船舶制造企业的仓储管理系统,以期提高船企仓储管理系统的鲁棒性,并能兼容船企已有的项目管理系统,实现业务集成和数据共享,提高生产自动化程度。
1 船舶项目仓储问题模型 1.1 船舶项目仓储活动概述船舶制造企业中,一般设立多个仓储点以满足生产需要,其中部分库房为特定种类物料所设置,多数仓储场所之间物料可以相互流通。根据船舶仓储活动的特点,船企仓储系统的问题主要集中在仓储任务的选择与调度上。主要的仓储活动问题有:1) 根据仓储系统需要入库的物料量,进行仓储任务调度;2) 根据物料特性(部分物料指定仓库)进行仓储任务调度;3) 根据库容量安排仓储任务;4) 根据物流路径的承运能力安排仓储任务。
1.2 仓储管理角色根据船舶或海洋工程装备项目的生产特点,将船企内部各个仓储场地简化成具有多个出入口和一定容量的仓储单元以建立模型。仓储单元包括:
1) 仓储群:指船企内部包括库房及堆场等所有具有仓储功能的场地集群;2) 仓储点:指船企内部具有仓储能力的场所单元,如单个库房或堆场为一个仓储点;3) 路径:连接各个仓储点之间的物流路径。单位时间内路径上的物料运输量称为路径通量;路径通量和路径长度是路径的评价指标。
1.3 仓储问题模型单元从船企效益的角度出发,库存优化是以实现最小成本进行体现的;在具体执行上则以减少物流成本和缩短物流时间为优化目标。物资在仓储环节流转中,主要受仓储点容量以及配送路径通量的限制,不可无视物流承载力和库容任意存取物料。由此,仓储问题优化的目标应为:结合实际需要,以尽量短的物料路径尽快完成仓储任务,从而提高仓储周转效率。为具体描述仓储任务,将仓储问题模型(warehouse problem model,WPM)形式化表示为集合
WPM={WTU,WAU}
式中:WTU为仓储任务单元(warehouse task unit);WAU为仓储动作单元(warehouse action unit)。WTU和WAU各为一组属性的集合。多个WAU共同解决同一个WTU组成了仓储问题的解决模型。WPM模型内的详细内容如图 1和表 1所示。
![]() |
图1 仓储问题模型(WPM) Figure 1 Warehouse problem model (WPM) |
单元 | 属性 | 含义 | 内容类型 |
WTU | Sp | 仓储任务单元定义 | 集合 |
WTU | Tc | 本任务包单位运输成本 | 数值 |
WTU | Rc | 本任务包所需库容 | 数值 |
WTU | Sa | 包内物料对应仓储点类型 | 集合 |
WTU | Tf | 本任务包物料运输通量限制 | 数值 |
WAU | Su | 仓储动作单元定义 | 集合 |
WAU | Lr | 对应仓储点物流路径 | 矩阵 |
WAU | Ac | 对应仓储点可提供库容 | 数值 |
WAU | Mc | 对应仓储点可存储物料类型 | 集合 |
WAU | Cr | 仓储动作路径的通量 | 矩阵 |
WPM模型中系统工作可描述为:1) 制定WAU以完成WTU;2) 布置WAU以提高仓储资源利用率。
1.4 仓储群模型仓储群模型定义了WTU和WAU的逻辑关系。首先定义模型内参数,见表 2。
参数 | 含义 | 备注 |
路径l | 完成仓储动作所需的配送路径长度 | WAU内Lr属性的元素 |
路径通量e | 各仓储路径上单位时间的物料运输量 | WAU内Cr属性的元素 |
仓储点数量n | 仓储模型中物流节点的数量 | 包括物料出入口和仓储点 |
WAU数量m | 仓储动作单元(WAU)的数量 | 对单个WTU求解的WAU数量 |
根据产品生产特性,在船企仓储动作中,WTU可分为入库、出库和移库三类;其中入库指物资从外部进入仓储点;出库指外部从仓储点获取物资的过程;移库指物资根据需要在不同仓储点之间的移动过程。仓储活动是WTU和WAU动态平衡的结果。一组仓储动作的示意如图 2所示。
![]() |
图2 船舶项目中的仓储动作示意 Figure 2 Sketch of warehouse movement in shipbuilding project |
在仓储群模型中,各个WAU中的路径Lr和通量Cr两项属性通过从群模型中简化后的仓储路径模型得到。一个仓储路径模型如图 3所示。
![]() |
图3 仓储路径模型 Figure 3 Model of warehouse movement |
该仓储路径包括5个节点,每个节点代表一个仓储点或物料进出口。以元素eij表示各节点间路径的通量,得到路径方阵为
$\mathit{\boldsymbol{E}} = \left[ {\begin{array}{*{20}{l}} {{e_{11}}}&{{e_{12}}}& \cdots &{{e_{15}}}\\ {{e_{21}}}&{{e_{22}}}& \cdots &{{e_{25}}}\\ \vdots & \vdots & \vdots & \vdots \\ {{e_{51}}}&{{e_{52}}}& \cdots &{{e_{55}}} \end{array}} \right]$ |
WAU的Cr属性即为E矩阵。在实际的物料装车配送过程中,路径的通量与车运方向有关,所以eij≠ eji。WAU内的Lr属性与之类似,方阵内各元素为各段路径的长度,lij=lji。
在完成仓储任务的过程中,各仓储点因共用路径和物流能力等常产生资源冲突。因此,通过设置仓储问题模型,将问题简化为如何设置WAU以解决WTU;建立智能船舶制造仓储管理系统(intelligent shipbuilding warehouse management system,ISWMS),增强信息管理和数据反应能力,以提高船舶生产中的仓储管理效率,缩减仓储成本。
2 船舶项目仓储系统模型仓储活动时效性较强,当吞吐量冲突发生时,需尽快完成各仓储点之间的冲突协商,以避免物流材料在仓储阶段的滞留。由此,ISWMS基于MAS技术构建,各仓储点的库存活动使用Agent代理,运用MAS的协商机制来实现仓储问题模型中多WAU对WTU的求解。
2.1 系统组成ISWMS由多个Agent和通信网络共同组成。网络中的Agent使用规范的语言进行通讯。
2.1.1 Agent设计典型的Agent结构由传感器、知识库、处理器和动作器几部分组成;针对其属性和智能程度又分反应型、慎思型和混合型等;根据响应速度和协调效率的要求,结合Agent的信念愿望意图(belief desire intention, BDI)模型架构,ISWMS中的Agent被设计为复合型Agent;结构如图 4所示。
![]() |
图4 ISWMS中Agent结构 Figure 4 Structure of agents in ISWMS |
MAS系统中,Agent间通信方式包括黑板系统和消息对话方式两种,根据通信特点及使用需求,应构建两种通信方式兼具的通信网络。其中黑板系统方式用以实现单个Agent获取全局MAS信息;而消息对话方式用来实现多个Agent的协商。ISWMS中通信架构设计在2.2节中得到体现。
2.2 系统架构从当前船舶企业仓储的特点来看,船舶制造所需的仓储点位置及数量固定,各仓储点之间关系对等,没有较复杂的内部级联关系,问题求解集中在各仓库吞吐量的协调上。因此,ISWMS被设计为由控制层和动作层两层结构组成的双层MAS系统。图 5及表 3展示了在ISWMS内各Agent组成及信息交互示意。
![]() |
图5 ISWMS通信及架构 Figure 5 Communication and construction of ISWMS |
Agent名称 | 职能描述 |
仓储控制 | 对全局仓储活动进行控制,发布WTU,评估动作层Agent计划任务 |
仓储点 | 代理仓储点物料活动,接收WTU并提出WAU,和其他Agent交换WAU协商 |
物流 | 监控物流任务并反馈信息 |
传统的船企生产流程中,一般自顶向下,将仓储任务分配到各个仓储点执行。这种库存管理方式增加了管理层的工作量,且各子库存信息更新不及时。因此,结合MAS使用“库存竞投标”这一概念,控制Agent接收到仓储群的库存任务WTU后(写入MAS黑板),各仓储点Agent为完成任务提出WAU,相互协商形成协作团队方案进行竞投标。仓储控制中心对各协作方案进行评估,选择中标方案执行任务,完成WTU。在ISWMS中,协作模型以如下方式进行表述
Cooperation=<M,G,P,T,S>,其中
M:协作管理员(cooperation manager),协作管理员在协作过程中提出协作任务,监控任务完成情况。ISWMS中这一角色由控制中心Agent承担。
G:协作目标(cooperation goal),协作目标由协作管理员(M)提出,包括协作目标本身和达成目标的评估标准。ISWMS中协作目标即为WTU,以WTU是否完成作为协作目标完成的标识。
T:协作团队(cooperation team),协作团队成员由Agent根据任务自愿加入。在ISWMS中,各Agent根据WTU定义决定是否参与,从而组成T。
P:协作计划(cooperation plan),对协作目标G进行任务分解,指定协作团队角色间联系。ISWMS系统中,仓储点Agent根据对WTU的分析,提出WAU,与其他Agent协商获得协作计划。
S:协作结果(cooperation solution),协作结果是协作计划的结果。ISWMS中为各Agent确定协作方案,将仓储动作汇总得到的总WAU执行序列。
ISWMS系统中各个Agent的协作流程和序列为:1) 控制中心Agent根据WTU制定仓储群任务计划作为MAS的协同目标G;2) 制定协同方案和协同体结构,确定协同角色的组成及WTU发标范围;3) 发表WTU,各功能Agent协商后形成协作团队;5) 选择中标团队,得到团队的协作结果S;6) 按选择团队组织相关Agent动作达成协作目标。根据协作模型,ISWMS内运行序列如图 6所示。
![]() |
图6 ISWMS协同运行序列 Figure 6 Sequence diagram of agent cooperation in ISWMS |
通过1.4节提出的仓储问题模型,参考文献[15]中提出的物流优化方法,设计算例对系统运行流程和协商过程进行说明如下:
1) 仓储控制Agent获得仓储动作指令,将相似属性仓储任务归类生成WTU,在MAS通信黑板上发布仓储任务单元WTU={Sp,Tc,Rc,Sa,Tf};
2) 仓储点Agent获取WTU内的任务定义Sp、库容Rc和仓储点类型Sa属性,判定合适时制定本仓储点的初始WAU并发布。WAU内的Cr和Lr属性通过通信网络实时获取。仓储点Agent发布各自的初始WAU,并在MAS系统内根据规则寻找其他参与协商的其他仓储点Agent。
3) 各Agent寻找并组成具有m个WAU的协作团队,形成初始协作团队T0,及其协商得到的WAU执行序列WAUnegotiation={WAU1,WAU2,…,WAUm}。
完成条件:当以下规则同时满足时,完成协作团队的构建工作。
① 仓储点可以存储对应任务包的物料类型:
$\{ {M_c}|{\rm{WA}}{{\rm{U}}_i}\} \supseteq \{ {S_a}|{\rm{WTU}}\} ,i \le m$ | (1) |
② 仓储任务需要的库容得到满足,即
$\sum\limits_{i = 1}^m {{A_c}} |{\rm{WA}}{{\rm{U}}_i} \ge {R_c}|{\rm{WTU}}$ | (2) |
③ 路径通量可满足仓储任务的运输通量需求,即对协商结果总WAUT的Cr属性,有
${\mathit{\boldsymbol{C}}_\mathit{\boldsymbol{r}}}|{\rm{WA}}{{\rm{U}}_{\rm{T}}} = {\left( {{e_{pq}}} \right)_{n \times n}},\forall {e_{pq}} \ge {T_f}|{\rm{WTU}}$ | (3) |
协商过程:
仓储点Agent对其它Agent所持的WAU进行协作收益的计算。包括:
① 通过WAU内的属性判定是否协作。若双方Agent所持WAU的Su属性的交集为空集时,说明任务物料种类不符,拒绝协作。
② 从双方WAU的Lr属性出发,计算目标Agent的协作影响。当不同WAU之间在路径上发生冲突时,协作收益因子u按下式计算:
$u = 1 - (L_{{\rm{sum}}}^{ - 1} \cdot \sum {l_{clash}})$ | (4) |
式中:Lsum为协商各方所持的路径Lr|WAU矩阵内的所有元素和,表征参与者WAU的物流路径总长度;∑lclash为各方Lr|WAU矩阵内重合元素值之和,表征各方仓储动作的冲突路径总长度。u=1说明各方WAU无冲突。
③ Agent优先选择与自身WAU具有高协作数值的其他WAU组成团队,在达到完成条件时,完成初始协作团队T的组建工作。
4) 控制Agent收到初始团队T后,获取T的协商WAUT,参考文献[16]中提出的多指标绩效评估模型进行评估。评估指标包括:完成WTU的时间成本,完成WTU的物流成本,Agent知识库内基于过往经验或预先定义的各项成本评估权重,自外集成系统或人工发出的干预指令。
5) 根据评估结果选择协作团队后,询问对应的团队成员Agent确定是否接收任务。
6) 各团队成员接受评估结果并开始调动物流Agent执行物流作业,一次MAS协作过程结束。
7) 控制Agent对全局仓储动态进行监控。当某一路径活动通量为0时,控制Agent将对该路径及两端仓储点Agent活动数据进行收集,寻找合适的WTU并向MAS发布执行协作作业。
4 系统开发验证 4.1 运行平台系统开发与工信部《工信部高技术船舶科研项目》已有研究成果相结合,针对集成系统特性选取基于Java语言的多智能体开发框架平台(Java agent development framework,JADE),结合JADE框架自带的FIPA-ACL智能体通信语言进行ISWMS的开发。ISWMS系统以浏览器/服务器架构(Browser/Server,B/S)在船企局域网上实现,并与物流系统及进度管理系统实现集成兼容。系统主要功能界面如图 7所示。
![]() |
图7 ISWMS主要功能界面 Figure 7 Main function interface of ISWMS |
从系统集成生产管理模块中导入某船舶企业的24 h内采购到货及生产计划数据,对ISWMS原型系统进行多组测试模拟仓储任务规划问题。系统合并生成了4个WTU,测试过程与结果如表 4-6所示,从结果可见,本文提出方法在多仓储点冲突环境的运行下具有较好的优化效率。测试过程详述如下。
团队编号 | WTU完成时间/min | 总路径×通量/(件数·km) | 路径协作收益因数 |
#2-1 | 126 | 732 | 0.79 |
#3-1 | 153 | 758 | 0.88 |
#4-1 | 170 | 596 | 0.76 |
#5-1 | 117 | 654 | 0.82 |
编号 | 时间成本 | 物流成本 | 成本权重时间/物流 | 综合成本 | 顺序 |
#2-1 | 5 040 | 5 124 | 1 | 10 164 | 2 |
#3-1 | 6 120 | 5 306 | 1 | 11 426 | 4 |
#4-1 | 6 800 | 4 172 | 1 | 10 972 | 3 |
#5-1 | 4 680 | 4 578 | 1 | 9 258 | 1 |
WTU序号 | WTU类型 | 协作方案数 | 参与协作的仓储点数量 | 成本权重时间/物流 | 协作路径收益因子 | 使用MAS协商方案综合成本 | 顺序分配任务综合成本 | 优化效 |
1 | 入库 | 4 | 4 | 1 | 0.93 | 22 250 | 23 958 | 7.1 |
2 | 入库 | 4 | 4 | 1 | 0.82 | 9 258 | 10 376 | 20.4 |
3 | 出库 | 3 | 3 | 4 | 0.67 | 10 972 | 14 770 | 25.7 |
4 | 移库 | 1 | 2 | 0.2 | 1.00 | 650 | 650 | 0.0 |
1) 发布WTU。根据到货计划,控制中心将数个从节点#1入库的仓储作业集合为1个WTU并发布。测试仓储群中有5个物流节点,起点为#1的仓储路径矩阵(单位为km)为
$\mathit{\boldsymbol{L}} = \left[ {\begin{array}{*{20}{c}} 0 & {0.23} & 0 & {0.08} & {0.20}\\ {0.23} & 0 & {0.11} & 0 & 0\\ 0 & {0.11} & 0 & {0.12} & 0\\ {0.08} & 0 & {0.12} & 0 & 0\\ {0.20} & 0 & 0 & 0 & 0 \end{array}} \right]$ |
实时通量(单位为件/h)为
${\mathit{\boldsymbol{E}}_0} = \left[ {\begin{array}{*{20}{c}} 0 & {400} & 0 & {305} & {600}\\ {400} & 0 & {260} & 0 & 0\\ 0 & {240} & 0 & {150} & 0\\ {310} & 0 & {160} & 0 & 0\\ {450} & 0 & 0 & 0 & 0 \end{array}} \right]$ |
2) 根据WTU属性,仓储点Agent开始协商,组建协作团队。本轮测试过程中,4个仓储点Agent均在协商后提出协作团队。协作计划如表 4所示。
3) 控制中心对各协作团队进行评估,结果如表 5所示。表 5展示了示例的评估结果。最终选择#5仓储Agent主导的任务协作团队执行示例WTU。
系统运行实现了研究提出的主要功能,包括:1) Java web网络框架与Jade框架相整合,从web端调用Agent数据并以FIPA-ACL格式通信;2) 在服务器端建立控制中心Agent,与数据库中专门设计用于Agent黑板通信的表空间实现了双向连接;3) 使用多仓储点Agent协商实现物流能力协调,并和解决物流问题的算法库实现了共用;4) MAS部分系统人机交互界面和登陆权限的设计;5) 原型系统和外部系统的对接集成及兼容性测试。
5 结论1) 与其他研究中采用的船舶建造仓储集中管理模式不同,ISWMS系统使用多智能体中的各个agent对企业仓储活动中的各分布节点进行业务代理,运用多智能体协调机制,为多个分布式仓储点协同完成仓储物流任务提供了较快的动作方案,并兼容针对仓储配送等已有问题的解决算法和其他用于船舶制造项目管理的数字系统。
2) 经运行测试证明,在多智能体系统框架上构建的ISWMS系统增加了仓储管理的信息化和智能化程度,可用于辅助船舶制造企业进行仓储管理,具有较好实用意义。
对于分布式仓储管理过程中的多代理协商及物流调度算法库补充、对生产现场更复杂仓储问题及更大数据量的测试及相关优化工作,有待进一步深入研究。
[1] |
李敬花, 吕慧超, 胡载萍, 等. 基于MAS的海洋工程装备项目钢板可追溯系统[J].
计算机集成制造系统, 2013, 19(5): 1041–1050.
LI Jinghua, LV Huichao, HU Zaiping, et al. Plate traceable system based on MAS in oceaneering equipment projects[J]. Computer integrated manufacturing systems, 2013, 19(5): 1041–1050. |
[2] |
李敬花, 樊付见, 余峰. 求解船体分段堆场调度问题的改进遗传算法[J].
计算机集成制造系统, 2012, 18(12): 2674–2682.
LI Jinghua, FAN Fujian, YU Feng. Improved genetic algorithm for ship block yard scheduling problem[J]. Computer integrated manufacturing systems, 2012, 18(12): 2674–2682. |
[3] | PAN J C, SHIH P, WU M. Order batching in a pick-and-pass warehousing system with group genetic algorithm[J]. Omega, 2015, 57: 238–248. DOI:10.1016/j.omega.2015.05.004 |
[4] | DONG W S, CHANG Y S, KIM W R. Design of warehouse control system for real time management[J]. IFAC-Papers On Line, 2015, 48(3): 1434–1438. DOI:10.1016/j.ifacol.2015.06.288 |
[5] | MA H, SU S, DAN S, et al. Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling[J]. Engineering applications of artificial intelligence, 2015, 44: 79–90. DOI:10.1016/j.engappai.2015.05.009 |
[6] | PAN J C, SHIH P, WU M, et al. A warehouse assignment heuristic method based on genetic algorithm for a pick-and-pass warehousing system[J]. Computers & industrial engineering, 2015, 81(C): 1–13. |
[7] | ACCORSI R, MANZINI R, MARANESI F. A decision-support system for the design and management of warehousing systems[J]. Computers in industry, 2014, 65(1): 175–186. DOI:10.1016/j.compind.2013.08.007 |
[8] | LU W, MCFARLANE D, GIANNIKAS V, et al. An algorithm for dynamic order-picking in warehouse operations[J]. European journal of operational research, 2016, 248(1): 107–122. DOI:10.1016/j.ejor.2015.06.074 |
[9] |
黄晶. 基于多Agent分布式约束优化问题求解方法研究[D]. 长春: 吉林大学, 2008: 15-17.
HUANG Jing. Multi-Agent based approaches to solving distributed constraint optimization problems[D]. Changchun: Jilin University, 2008: 15-17. |
[10] |
张青, 李萍, 杨正全, 等. 带有未知参数和通讯时延的多智能体蜂拥控制[J].
哈尔滨工程大学学报, 2016, 37(5): 696–700.
ZHANG Qing, LI Ping, YANG Zhengquan, et al. Flocking control of a multi-agent system with unknown parameters and communication delays[J]. Journal of Harbin Engineering University, 2016, 37(5): 696–700. |
[11] | HUANG S, WANG Q, BATTA R, et al. An integrated model for site selection and space determination of warehouses[J]. Computers & operations research, 2015, 62: 169–176. |
[12] | KIM B I, HERAGU S S, GRAVES R J, et al. Intelligent agent based framework for warehouse control[C]//200437th Hawaii International Conference on System Sciences. IEEE Computer Society, Washington, USA, 2004: 1-10. |
[13] |
胡志苹, 林国顺. 基于Agent的物流仓储工作流建模[J].
大连海事大学学报, 2006, 32(4): 28–30.
HU Zhiping, LIN Guoshun. Research on modeling of warehouse workflow based on agent[J]. Journal of Dalian Maritime University, 2006, 32(4): 28–30. |
[14] |
贾红雨, 陈燕, 胡松筠, 等. 库存管理模拟Multi-Agent建模方法研究[J].
系统仿真学报, 2006, 18(z2): 73–76.
JIA Hongyu, CHEN Yan, HU Songjun, et al. Study on the multi-agent-based modeling methodology for inventory management simulation[J]. Journal of system simulation, 2006, 18(z2): 73–76. DOI:10.3969/j.issn.1004-731X.2006.z2.021 |
[15] | WANG Y, MA X, XU M, et al. Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm[J]. Expert systems with applications, 2015, 42(12): 5019–5031. DOI:10.1016/j.eswa.2015.02.058 |
[16] |
杨春周, 战希臣, 郑海平, 等. 船舶仓储管理绩效的评估模型[J].
舰船科学技术, 2011, 33(11): 131–134.
YANG Chunzhou, ZHAN Xichen, ZHENG Haiping, et al. Research on management performance evaluation model of ship warehouse[J]. Ship science & technology, 2011, 33(11): 131–134. DOI:10.3404/j.issn.1672-7649.2011.11.031 |