IRP问题多Agent模型调度策略研究*

孙斌锋 吕雄伟 李 军

(湖南大学应用经济博士后流动站1) 长沙 410079) (西南交通大学经济管理学院2) 成都 610031)

在实施供应商管理库存(vendorm anaged inventory,VM I)[1]策略下,零售商企业根据合同协议,将库存业务外包给供应商完成,进而专注于核心业务的开发,快速响应客户的需求,提高企业竞争优势;同时供应商整合多家企业的库存业务,综合考虑库存与运输相互影响,合理安排车辆进行商品配送从而获取规模效应,降低运作成本,实现供应链系统整体优化.

VMI的实施是个复杂的系统工程,具体运作需要多方面的考虑.存贮路径问题(inventory routing p rob lem,IRP)是VM I管理策略下的核心问题之一[2],在单个供应商对多个分散零售商库存进行统一管理的模式下,系统考虑库存控制与运输计划之间的协调,制定使得供应商运输成本与零售商库存成本总和极小的补货策略(包括车辆运输计划和零售商库存策略).

最终的补货策略可以认为是计划期内一组车辆路线的集合,它规定了不同补货期内车辆怎样和以什么顺序完成零售商补货任务;同时它也被认为是系统内各零售商库存策略的集合,规定了各客户补货的时间和补货的数量.因而,IRP问题需要解决的是补货任务(包括时间与数量)的生成和分配,即为补货任务在时间维度上安排合理的数量,以及空间维度上指定配送的顺序.

在单个供应商和多个零售商构成系统中,无论是作为客户的零售商,还是起着配送中心作用的供应商,它们在地理位置上分散,组织结构上分属于不同的自治成员企业,同时各个成员都具有自己核心的能力,因此为实现系统的总体目标,必须相互协作与协调.尽管IRP问题也已被诸多学者从不同角度提出了求解方案[3],有鉴于各方案大多采用集中式模型为主的优化技术[4],忽视系统成员决策的自治性和环境的动态性,本文设计了IRP问题的多Agent模型[5]整体框架,利用多Agent协商谈判实现补货策略的求解.该方法较之传统集中式、非自主数学模型更强调功能实体间的交互作用.

1 IRP问题多Agent模型整体框架

IRP问题系统中包含多种配送资源和多样的零售商需求,逻辑和控制关系十分复杂.基于多Agent的协商求解方法提供了一种动态灵活、快速响应市场的配送调度机制,通过对配送中心与零售商的联合,实现系统的集成.本文建立了IRP问题的多Agent模型[6],通过Agent之间的合作以及多Agent系统协调来完成补货策略的求解,并达到预先规定的系统目标.在多Agent模型中,包括四类Agent:配送中心 Agent、客户 Agent、补货任 务Agent和车辆Agent,如图 1所示.

图1 IRP问题多Agent模型调度框架

配送中心Agent根据客户Agent提供的需求信息和自身的能力约束,生成客户初始补货计划,并以时间顺序将计划细分,动态生成补货任务Agent.

客户Agent负责预测客户需求、实时监控自身库存水平;与车辆Agent交互,接收车辆补货数据,更新库存信息;记录周期内客户消耗情况,生成实际需求历史数据库,以及提交客户需求信息.

补货任务Agent作为客户每天补货任务的代理,在每个配送周期开始前由配送中心Agent根据需要动态生成;与车辆Agent通信,实现补货任务的分配;监控车辆Agent的运行情况,对任务的执行状况和车辆负载情况进行监控.

车辆Agent与实际配送设备相对应,通过知识推理能力,与其他车辆Agent相互竞争补货任务,主动争取任务安排.车辆Agent维持自己的下述属性:(1)可用性运输能力以及车载能力约束;(2)使用成本;(3)补货客户集合等.

2 基于多Agent协商谈判的调度研究

计算机技术的迅速发展为设计功能足够强大的Agent提供了重要的技术支持,运用多Agent系统理论研究IRP问题,可以运用多个Agent通过协商谈判共同完成补货策略的制定,将IRP问题分解为许多个子过程分散处理,大大简化了IRP问题的复杂性,提供系统的可维护性,降低生成客户库存策略和车辆调度计划成本.

基于多A gent的IRP模型是个典型的合作性多Agent系统,Agent协商谈判的目的是动态生成补货任务,并为补货任务制定补货顺序、分配给适合的车辆完成配送,实现系统性能指标的最大化.在多Agent系统中,谈判是任务分配的一种有效机制,参与谈判的每一方都根据自身的利益做出决策,最终的补货策略是多方共同的意向.本文采用合同网[7]进行管理与协调Agent,并在此基础上实现Agent间的协商谈判.

在IRP问题调度模型中,客户Agent与配送中心Agent负责补货计划的生成与分解,并动态生成补货任务Agent;车辆Agent负责补货任务的调度.在这个过程Agent是相互协作的,他们必须要具有相应的调度流程及冲突消解策略.

2.1 多Agent调度流程

在基于多Agent的IRP问题模型中,其基本流程见图2.从需求信息的发送,到补货任务的生成,以及车辆竞标分配,各Agent协同工作,实现补货策略决策.对于补货策略的规划,基本流程描述如下.

步骤1 配送中心Agent根据客户提供客户的需求信息,以及配送中心仓储能力等约束,为系统内各客户生成补货计划.补货计划是客户在计划期内接受配送中心配送的数量与时间集.

步骤2 配送中心A gent与客户Agent进行协商谈判,根据配送中心能力约束及客户需求限制,将补货计划分解成当前补货期内的补货任务,动态生成补货任务Agent,组成待调度的任务集合.

步骤3 触发集合中优先级最高的、且与其他正在招标的补货任务Agent没有资源冲突的补货任务Agent,向系统内车辆Agent发出招标信息.

步骤4 车辆Agent评价配送该任务的可行性,为其在本车服务客户集合中指定合适的顺序,并将车辆能力预定给该补货Agent,确保不被其他Agent使用;然后将增加的相关成本,以及当前空闲的运载能力作为标书返回给招标的补货任务Agent.

步骤5 在收到所有可行车辆Agent投标信息后,补货任务给予启发式原则(如总成本最低等)从竞标对象中选择合适的车辆Agent,发送确认信息;同时发送失败信息给其余车辆Agent.

步骤6 收到确认信息的车辆Agent将预定能力和顺序标记为占用;其他则将该预定信息消除位.所有的Agent继续为下一次竞标做准备.

步骤7 谈判反复进行,直至当前补货期内补货任务都被指定给车辆.车辆实体执行配送计划.

步骤8 重复上述活动,直至计划期的结束.

图2 基于Agent协商谈判的IRP问题调度流程

从整体上看,图2所表达的是Agent相互关系和调度工作的先后顺序,但在实际的运作过程中,各相关A gent又是相互独立并行工作的.

2.2 补货任务Agent优先级

在前文阐述的补货策略决策流程中,配送中心Agent和客户Agent负责补货任务Agent的生成,并为之设定优先级.A gent的自治、自主等特性,使得Agent具备的信息具有不完全性,难以从整体上把握问题的目标,因而其局部目标和系统整体目标存在着差异.IRP问题是以整体成本极小为主要目标的,可以通过在补货任务优先级的确定上体现出全局的目标约束.本文以表达式(1)的数值降序标识补货任务的优先级,数值越大优先级越高.

描述缺货概率越高的补货任务优先完成.

2.3 车辆Agent投标书的制作

在IRP问题的多Agent模型中,补货任务是由车辆Agent自主竞标决定起执行的方式,因此投标书的制作是车辆获取补货任务的关键.如果考虑每个任务由单车负责配送,显然会造成成本的极大浪费,也会限制车辆竞争任务的能力.这里车辆Agent决策能力采用节约/插入算法[8],为招标的补货任务在已有的车辆服务客户集合中选择最适合的配送顺序.

设R={1,2,…,n}为车辆Agent的服务客户集,0表示配送中心,cij表示车辆从点i行使到点j的费用,则在进行投标之前,车辆Agent配送路线为 .由节约/插入算法,得到招标补货任务k插入到配送路线中点i和点j的之间的费用节约值

在R∪{0}集合中选择s(i,j)极小值,将该位置预留给补货任务k,并做好标识.同时将将s(i,j)作为车辆Agent投标值和车辆空闲能力提交给招标Agent.

2.4 冲突消解机制分析

由单个供应商和多个零售商构成系统中,由于知识不完备、不同的局部目标及有限的资源约束,成员企业间的冲突发生往往不可避免,如补货任务的生成、车辆配送相同优先级的补货任务等.这时需要构建相应的策略规避与消解冲突,提高IRP问题决策的求解效率.

冲突一般可以采用数学的方法和人工智能的方法进行消解[9].在构建的IRP问题多Agent模型中,各Agent本身具有推理机,因此采用知识推理和协商的方法进行模型冲突的消解.

3 算例分析

设有8个客户接受单个配送中心的补货,某作业期内生成的补货任务A gent特征及通过表达式(1)得到各任务Agent的优先级见表1.这些补货或人物Agent由配送中心发出的容量为8 t的车辆Agent竞争完成,配送中心与各客户的距离(单位:km)见文献[8].

表1 补货任务 Agent特征

算例的多Agent调度流程见表2.需要注意的是,第3轮中车辆1在竞争任务7时载重约束受限,只能给出最大投标值M(M表示极大整数值);在第4轮中补货任务Agent1,Agent5处于相同优先级,则此两任务同时触发招投标过程.

若不考虑库存成本影响,仅就客户任务进行补货,问题简化成为车辆路径问题(VRP),此时对应的运输方案为[8]:0-8-5-7-0,0-6-4-0,0-3-1-2-0.二者比较,后者对应的运输成本更低,而前者为平衡库存成本的影响,选择了运输成本略高的配送方案,进而实现系统总成本的优化目标.

表2 调度结果

4 结 束 语

本文在分析VM I管理模式下的IRP问题研究内容及特点的基础上,运用分布式人工智能中的多 Agent方法构建问题求解框架,通过多Agent之间的协商谈判实现IRP问题补货策略的制定,并对调度流程中的优先级确定、标书的制作及冲突的消解作了简要的阐述;与IRP问题其他集中式模型求解策略相比,本文侧重于通过功能实体间交互作用研究问题求解,这也是集中式方法忽略的内容.然而模型中的A gent间的通信、冲突消解的具体实现等的深入分析,将有助于IRP问题的进一步研究.

[1]马士华,林 勇,陈志祥.供应链管理[M],北京:机械工业出版社,2000.

[2]K leyw egt A J,Nori V S.The stochastic inventory routing problem with direct deliveries[J].Transportation Science,2002,36(1):94-118.

[3]李 军,刘建新.第三方存贮-路径问题研究综述[J],科学技术与工程,2004,4(4):325-328.

[4]王红卫.建模与仿真[M].北京:科学出版社,2002.

[5]W ooldridge M J,Jennings N R.Agent theories,architectures and languages[C]//First International Conference on M u lti-Agent Systems.San Francisco,June 12-14,1995.

[6]孙斌锋,吕雄伟,李 军.基于MAS方法的存贮路径问题研究[J].计算机应用,2006,26(2):276-278.

[7]Sm ith R G,Davis R.Frameworks for cooperation in distributed p rob lem solving[J].IEEE Transactions Engineering Management,1981,11(1):61-69.

[8]李 军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.

[9]黄必清.虚拟企业系统的理论与技术[M].北京:机械工业出版社,2004.