基于多Agent协商的物流配送最优路径选择问题研究

      doi：10.3969/j.issn.1005-152X.2014.06.030

      1 引言

      物流活动是电子商务过程的基本要素，物流配送是现代物流管理中的一个重要环节，是实现电子商务的基本保证和关键环节。随着市场经济的发展和物流技术专业化水平的提高，我国的物流配送业得到了迅猛发展。在许多配送系统中，需要采取有效的配送策略以提高服务水平、降低货运费用。其中车辆路线安排问题(Vehicle Routing Problem，简称VRP)是亟待解决的一个重要问题，因此物流配送车辆路径优化也成为了物流领域的一个研究热点。车辆路径问题属于组合优化领域带多个约束条件的一类问题，由Dantzig和Ramser于1959年首次提出，因其应用广泛，国内外学者对其进行深入的理论研究与实验分析，综合运用运筹学、管理科学、经济学、组合数学、计算机科学、图论等理论知识，通过类比、演绎、推理和综合等方法，取得了一定的成果[1-6]。研究VRP可以合理使用调运工具、优化运输路线、降低企业物流成本。

      近年来，国内外学者对VRP算法进行了大量研究，研究者使用启发式算法和智能算法来求解VRP[1，12]已取得了一定的成果，但对物流环境信息的实时更新和路线调整、高效的时效性要求等问题都没有很好的解决，往往是路线一旦生成，几乎不能变动，并没有考虑具体路线的拥塞情况，从而无法真正地使最终选择的路线符合实际情况，也就无法保证最终运行的路线是最优路径，脱离了应用实际。本文针对上述路径选择中所存在的不足，充分利用Agent所具有的自主性、社会性、反应性、能动性、动态实时性等特性[7-10]，提出了基于多Agent协商的物流配送最优路径选择算法，即在确定的需求下，通过各Agent之间的协商，以综合效益最大为驱动目标实现配送过程中的路径选择，引入加权因子更好地解决了路况拥塞和费用问题，不仅能动态调整配送路线，而且保证了在不延迟配送时间的同时对路径的全局搜索和寻优能力，提高了配送效率，降低了配送中心运作成本，为电子商务中物流配送的信息化推进提供了一定的技术支持。

      2 基于多Agent的物流配送系统结构

      依据物流配送系统的职责，相应的系统结构如图1所示。系统中负责完成各功能的模块均由担任不同角色的Agent进行控制和处理，通过人机交互界面向黑板系统提交相应的需求信息，黑板系统对这些信息进行分析并把提取的关键信息交由决策支持库进行数据处理，再把决策支持库所反馈的结果传递给总控Agent模块，进而再确定配送任务，并通过调用最优路径算法，在各Agent模块协商合作下选择出最优的配送路线。

      

      图1 物流配送系统结构图

      系统中的每个Agent均构建成功能不同的独立模块，系统模型M可以用一个六元组来表示，即M=｛Ag，D，B，G，U，L｝，其中各参数的含义如下：

      (1)Ag：Ag=｛Agt1，Agt2，...，Agtn｝是配送系统中各Agent的模块集合。每个进入物流配送系统的Agent都有唯一的ID号作为自己的身份标识，以便于任务的分配和信息管理，主要包含以下Agent实体：

      ①总控Agent模块：对不同的Agent模块进行管理和任务分配，以广播的形式通知各不同的Agent完成各自相应的任务，协调各Agent间的协商合作问题，以最终达到最优路线选择下货物配送的目的；

      ②客户信息管理Agent：对客户信息的管理和更新，对客户的层次和级别以及货物的需求跟踪等相应信息的管理；

      ③员工信息管理Agent：对员工的任务分配和级别的更新管理；

      ④订单信息管理Agent：订单信息的填写和提交，并根据反馈的信息决定是否对订单信息进行修改，响应客户的请求并及时给予反馈；

      ⑤车辆调度管理Agent：结合交通信息管理Agent和车辆调度算法完成对车辆的有效调度，从而生成最优的配送方案；

      ⑥交通信息管理Agent：借助于实时的导航信息系统获取路况信息，为最优路径的选择提供有效依据；

      ⑦配送信息管理Agent：对各订单信息及时进行跟踪，寻求合适的配送点，选择合理的配送方案，并反馈配送结果；

      ⑧仓库与库存管理Agent：协调配送中心各仓库的库存和货物存放问题，提升货物的空间利用率，负责物品的周转和配送。

      (2)D：决策支持库。主要由知识库、数据库、案例库、模型库和规则库组成，负责完成相应的决策算法和提供领域知识的支持。决策支持是物流配送中的核心，不仅可以实现日常运营方案的自动化管理，而且对订单信息的跟踪和结果反馈以及最优路线的选择和调整都起到了很好的支持作用；决策支持库中的信息可以及时的更新，以保证系统的开放性。

      (3)B：黑板系统。主要负责总控Agent和决策库中信息的交流和分析，为问题的求解提供了一个公共和交流的平台。

      (4)G：地理信息系统。负责实时路况信息的传递和分析，为动态加权因子的选择提供依据。