孟 聪,初良勇,2
(1.集美大学 航海学院,福建 厦门 361021;2.集美大学 现代物流研究中心,福建 厦门 361021)
基于多Agent的物流车辆调度系统构建及协作机理
孟聪1,初良勇1,2
(1.集美大学航海学院,福建厦门361021;2.集美大学现代物流研究中心,福建厦门361021)
在传统物流车辆调度过程的基础上,结合Agent在物流车辆调度和物资调度方面的应用,设计了基于多Agent协作的车辆调度系统模型的框架,进一步分析了各Agent之间共同协作完成任务的过程。同时建立了基于黑板系统的通信机制,深入分析Agent之间的协作机理。
多Agent;物流车辆;车辆调度;协作机理;通信机制
随着市场经济的发展,物流成为企业最重要的竞争领域之一,未来一段时间,企业之间的竞争一定程度上取决于其物流能力的发展。眼下我国物流行业的总体水平仍落后于发达国家,最显著的问题是物流成本较高和物流运作手段落后。作为物流最重要的环节之一,配送的费用在整个物流运作中占据了很大比重,因为目前相当一部分物流企业还是通过人工经验来判断和进行配送,如配送车辆的调度以及路径选择。在欧美、日本等一些国家,在20世纪80年代末就已然出现了专供物流调度所使用的计算机软件,摆脱了陈旧的人工经验调度的方法,开启了车辆调度操作智能化、自动化的新时代,这些技术中智能Agent技术越来越引起人们的关注。
智能体(Agent)是一个具有自主性、主动性、持续性、交互性和自适应性的智能实体,可以在没有外界直接操纵的情况下,通过自身的传感器感知外部环境的变化,并通过效应器自主地对环境做出反应。而由多个智能体组成的多智能体系统(Multi-AgentSystem,MAS)具有敏捷、灵活、实时的优点,采用分布式体系结构,其每个智能体皆有一定的独立功能,且智能体之间的结构关系是动态可调整的,不同功能Agent组成紧耦合的运输调度管理体系结构,具有适应性、自组织和良好的协调性能,可以通过协调方式完成繁杂的整体运作[1]。因此,多智能体技术非常适用于解决物流配送中的车辆调度问题。
近年来,国内外的学者对基于Agent的复杂系统建模问题进行了研究,如许多学者开展了基于MAS的故障诊断系统理论和模型研究,提出了基于MAS的智能故障诊断原型系统的基本框架[2-3]。随着研究的深入,有学者设计了一套基于合同网机制、拥有混合多Agent系统架构的裁判模型,将其应用于生产调度以及再调度的相关领域[4]。Tamagawa等将多智能体系统应用到城市商业运输模拟中,构建了两个模型,分别是学习模型和带时间窗的车辆路线规划和运输调度问题的模型。另外,还有学者将多Agent技术拓展应用于解决机场的应急资源动态调度和军用物资的车辆调度方面[5]。
本文针对传统配送车辆调度过程中存在的问题,提出了一种基于多Agent的配送车辆调度系统模型,通过将传统配送模式下的过程分解成几个模块,每个模块用一个智能Agent来代替,各Agent之间通过特定的通信语言进行协调合作,以实现整个配送过程的合理化、智能化。
2.1系统模型中各Agent的设定及分析
传统电子商务下的配送是指客户填写订单,配送中心接受订单并组织车辆进行配送的整个过程。该过程主要由人工操作,信息沟通不够及时,造成效率低下,同时,在组织车辆进行配送时,通常由人工经验进行车辆调度,存在很大的不合理性。为了克服传统人工经验可能带来的不合理性,物流车辆智能调度系统将配送过程分解成几个模块,即订单的处理过程、车辆调度的求解过程、车场的调度过程以及车辆执行任务的过程,每个模块利用一个智能Agent代替,即订单处理Agent、车辆调度Agent、车场Agent、车辆Agent,同时需要仓库管理Agent和路网信息Agent的配合,并增加一个协调控制Agent来解决一些全局性问题。本文将这些Agent模块分为四种类型,即管理型、任务型、计算型和资源型[6]。
(1)任务型:订单Agent。任务型Agent会选择合适的资源完成对自己的处理,是动态生成的,同时要监控任务的顺利执行。在实际物流配送系统中,映射为订单Agent。订单Agent负责接收和处理客户订单,包括手动输入、文件导入等方式,并对订单进行分析,形成任务。并向客户反馈和监控订单的处理状态。同时,它可以提取客户相关信息,用来分析该网点的客户类型和客户群。
(2)管理型:协调控制Agent。管理型Agent协调处理和监控一些全局性信息。映射为智能车辆调度系统中的协调控制Agent,负责整个系统的管理、监督与控制,尤其当系统出现紧急或者突发状况,如出现紧急订单,协调控制Agent会根据计划编制知识库中的规则,给紧急订单一个较高的优先级。
(3)计算型:车辆调度Agent。计算型Agent是指写入具体算法,并拥有判断能力的智能体。在物流配送智能车辆调度系统中,映射为车辆调度Agent,是整个系统的核心部分,即智能车辆调度的算法库,如遗传算法,模拟退火算法、神经网络算法等,判断自己是否有能力解决该订单,并且基于一定的目标形成车辆调度方案。
(4)资源型:仓库管理Agent、车场Agent,车辆Agent,路网信息Agent。资源型Agent即资源的一个功能单元或者管理资源的单元组合。映射为实际物流配送中,一般包括物资设备、运输工具、操作人员等。
2.2系统模型的构建
本文设计的车辆调度系统模型由多个Agent共同协作完成配送任务(如图1所示),任务完成过程中各Agent之间的配合如下:
(1)客户首先通过Internet端输入订单信息,订单Agent被激活,负责提取订单的各方面信息,如配送地点、时间要求、货物种类及数量等,形成具体的配送任务,任务消息将传送给车辆调度Agent,订单Agent转为等待状态。
图1 基于多Agent的车辆调度系统框架
(2)读取到任务的车辆调度Agent被激活,通过其他Agent的配合对任务进行求解,即需要激活车场Agent、仓库管理Agent以及路网信息Agent,通过调取仓库货物信息、车场的车辆信息、道路状态信息等,根据其内部封装的调度算法以及自身的数据库、知识库、合作库等对任务进行求解,形成的配送及车辆调度方案发送给车场Agent,同时将任务的处理进程反馈给订单Agent,车辆调度Agent转为空闲状态。
(3)车场Agent在接收到调度方案后,激活各车辆Agent,寻找合适的车辆Agent并进行任务分派。
(4)各车辆Agent根据接收到的调度指令,完成配送任务。
此外,协调控制Agent在整个任务完成过程中起到统筹全局的作用,如全程跟踪监控订单的处理状态,若出现紧急订单,协调控制Agent将给该订单一个优先级;当Agent之间合作或者通信出现问题,协调控制Agent将进行协调;或当任务的完成出现问题,协调控制Agent可以帮助追溯问题环节。
3.1Agent的物理结构
智能体(Agent)是一个可以在没有外界直接操纵的情况下,通过自身的传感器感知外部环境的变化,并通过效应器自主地对环境做出反应的智能实体。单个智能体的应用只能解决简单的现实问题,即接收外部环境的问题,通过内部封装的算法或程序对问题进行求解,再反馈给外部环境的简单过程。
图2 Agent的物理结构
如图2,在多个Agent组成的系统中,Agent之间需要互相共享协作共同完成任务,一个通用的Agent一般具有用户接口、通讯接口和自模型三部分。用户接口用来与外部环境进行交互,即接收问题或者反馈求解结果。自模型是其核心部分,负责对问题进行求解,一般包括求解模块和合作模块,求解模块内部有与该智能体对应的数据库、知识库及封装的算法库,推理机负责将问题进行分解并利用现有的知识进行推理求解;合作模块内部有合作库,负责该Agent与其他Agent之间的信息交互及交流协作,共同完成任务。
3.2Agent之间的通信机制
Agent之间的通信语言主要有三种[7],第一种是知识查询与操纵语言—KQML(Knowledge Query and Manipulation Language),它规定了消息的格式及传送系统,为Agent之间的通信和协作提供了一种通用的框架,尤其提供了一组识别、连接建立和消息交换的协议;第二种是知识交换格式—KIF(Knowledge Interact Format),用来表达某一集域的性质以及集域中实体与实体之间关系的公共语言,严格基于一阶谓语逻辑演算;第三种是FIPA定义的ACL语言,用于表示Agent的行为特征,其消息往往表示一个通信动作。
Agent之间的通信方式主要有两种,一种是同步信息传递,即黑板系统,就是把消息放在可以广泛存取的黑板上,每个Agent可以向黑板发送消息,也可以从黑板上读取消息;另一种是异步消息传递,即点对点的方式,一个Agent可以向一个或多个Agent发送消息,这种通信方式需要Agent之间有更多了解,要求消息的发送者事先了解消息接收者的有关信息。
本文设计的智能车辆调度系统的通讯方式是黑板系统,通讯语言是美国ARPA知识共享项目提出的KQML语言定义协调规则,KQML包括以下要素:述行语、角色、语言、论域、内容等,一个KQML的例子如下[8]:
各Agent的状态由协调规则进行定义,以订单Agent为例,从订单的开始状态向获得状态转移时的协调规则定义如下[9]:
3.3车辆调度系统中的协作机理
本文设计的黑板系统中包括两个黑板,一个主要应用于车辆调度Agent对车辆调度方案进行求解的过程,另一个应用于车场Agent对于车辆Agent的管理过程,整个系统的信息传递如下:
(1)用户通过通讯接口将订单信息输入,订单Agent将提取的订单信息写入黑板系统中。
(2)车场Agent、仓库管理Agent以及路网信息Agent查看到黑板中的订单信息后,将相应的车辆信息、仓库货物信息以及路网信息写入黑板1中。其中,车辆信息需要黑板2进行配合,每个车辆Agent将该车辆的状态信息写入黑板2中,车场Agent根据黑板2中的信息将车辆信息汇总至黑板1中。
(3)车辆调度Agent读取黑板中的信息后,激活内部封装的算法库,开始求解,并将形成的调度方案写入黑板中。
(4)车场Agent读取到黑板中的车辆调度方案后,将调度方案信息写入黑板2中,寻求合适的车辆,完成配送任务。
图3 多Agent之间的协作机理
此外,如图3协调控制Agent作为一个中心控制节点,可以从黑板系统中读取到整个调度过程的各种信息,如订单信息及其处理状态、仓库信息、路网信息等,当任务处理过程出现任何突发问题需要其协调解决时,只需将协调方法和机制写入黑板1中,相应的Agent会读取到黑板1中的消息,并按照规定执行。
该系统模型将Agent的学习机制考虑进去,即群体学习机制。每个Agent通过记忆和遗忘来保存那些对共同任务求解有利的知识和经验,如车辆调度Agent,每个订单的调度方案形成之后,通过学习机对车辆调度方案的各个方面信息进行分析整合以及选择性的遗忘和记忆,形成有利于完成共同任务的实际经验的知识集合,记录于车辆调度Agent的知识库中,使知识库不断更新。协调控制Agent作为“负责人”的身份协调各Agent之间的通信和协作,除掌握各Agent的学习知识和经验,还要通过对群体执行共同任务进行分析,记忆整个群体在执行任务过程中有利于共同任务求解的模式以及相对最优的求解结构和协作方法,为类似的任务解决奠定基础。
本文利用多智能体系统敏捷、灵活、实时的优点,结合目前Agent技术取得的研究成果,设计了基于多Agent的物流车辆智能调度的系统模型,并对其内部的协调运作过程和通信机制进行分析,以实现车辆调度过程的智能化、合理化。展望未来,物流配送的整个过程正在朝着更加智能化的方向发展,Agent技术在物流的配送决策、车辆的智能调度方面的应用更值得深入研究。
[1]席钌姿.基于Multi-Agent技术的物流企业运输调度系统优化研究[D].衡阳:南华大学,2014.
[2]Wooldridge M,Jennings N R.Intelligent Agents:Theory and Practice[J].TheKnowledgeEngineeringReview,1995,10(2):115-152.
[3]Willimason.Distributed Intelligent Agent[J].IEEE Expert,1996,12(1):36-45.
[4]Shen W,Norrie D H.An Agent-based Approach for Dynamic Manufacturing Scheduling[C].Workshop Notes of the Agent-Based Manufacturing Workshop at Autonomous Agents'98[A].1998.
[5]崔国山.机场应急救援系统中资源动态调配研究[D].南京:南京航空航天大学,2009.
[6]李义华.基于多智能体的物流配送车辆调度决策方法研究[D].长沙:中南大学,2012.
[7]贾利民,刘刚,秦勇.基于智能Agent的动态协作任务求解[M].北京:科学出版社,2007.
[8]朱欣娟,薛惠锋.基于本体的MAS黑板模型研究[J].计算机工程与设计,2004,(1):26-28,141.
[9]周宏,廖雪珍.基于Agent的网络物流配送决策系统研究[J].系统工程与电子技术,2004,(10):1 421-1 425.
Establishment and Collaboration of Logistics Vehicle Dispatching System Based on Multi-agent System
Meng Cong1,Chu Liangyong1,2
(1. Navigation College, Jimei University, Xiamen 361021; 2. Modern Logistics Research Center, Jimei University, Xiamen 361021, China)
In this paper, on the basis of the traditional logistics vehicle dispatching process and in connection with the application of theAgent technology in logistics vehicle dispatching and material dispatching, we designed the framework of the vehicle dispatching systemmodel based on multi- agent collaboration and then further analyzed the collaborative process among the Agents. At the meantime, weestablished the blackboard-based telecommunication mechanism and analyzed in-depth the collaborative mechanism among the Agents.
multi-Agent; logistics vehicle; vehicle dispatching; collaborative mechanism; telecommunication mechanism
U116;F253.9
A
1005-152X(2016)08-0092-05
10.3969/j.issn.1005-152X.2016.08.024
2016-07-05
福建省自然科学基金(2012J01302);厦门市科技项目(3502Z20143022);福建省教育厅中青年教师教育科研项目(JA15288)
孟聪(1992-),女,硕士生,研究方向:交通运输规划与管理。