基于多Agent协商的物流配送最优路径选择研究_因子分析论文

基于多Agent协商的物流配送最优路径选择问题研究，本文主要内容关键词为：最优论文,路径论文,物流配送论文,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：地理信息系统。负责实时路况信息的传递和分析，为动态加权因子的选择提供依据。

      (5)U：效益函数。根据当前情形，分析不同配送路线的效益值，经过排序比较产生最大效益方案。

      (6)L：根据实时的路况信息和综合效益分析，系统最终所产生的最优配送路线。

      3 最优路径选择算法

      依据一般的配送原则，货物配送的重点就是综合考虑车辆的有效利用，使得在规定的配送时间内以最小的代价把物品送到客户手中，要达到这一目的，关键在于配送过程中最优路径的选择。根据物流配送网络本身所具有的连通性、节点性、有向性等特点，把配送站点抽象为点，配送线路抽象为线，配送网络就可以转化为一个由站点和线段组成的有向连通图，如图2所示，记为G(V，E，W)，其中V、E分别为G的配送点集合和各点之间所构成的线段集合，W是任意可通的道路间的权集，从而可以利用图论理论对物流配送中的路线选择问题进行分析[1，9-10]。

      

      图2 物流配送模拟图

      3.1 系统假设

      结合实际运行情况和模型的构建，系统作以下假设：

      (1)客户的货物需求已知且均小于配送车辆的载重量；

      (2)车辆配送路径的总长度不能超出最大行驶距离；

      (3)每辆车都从配送中心出发，完成若干客户的运送任务后再回到配送中心；

      (4)车辆出发时间确定；

      (5)规定一个客户的货物需求只能由一辆配送车一次运送完成；

      (6)车辆以平均车速v(km/h)作匀速行驶。

      3.2 算法思想设计

      

      

      算法描述：

      输入：各服务点客户对物品的需求量和初始的路况信息；

      输出：最优路线。

      Step1：经人机交互界面输入客户对货物的需求，初始化各参数；

      Step2：依据每个客户的需求

(i=1，2，…，n)和车的载重量

(r=1，…，m)，由黑板系统提交决策库D运算，依据运算结果进行车辆运输任务的合理分配，即在不超过配送车辆

载重量的情况下，尽可能地由接近配送任务载重量的车去执行配送任务；

      Step3：确定每辆车的配送出发时间

(r=1，…，m)；

      Step4：依据Step2和Step3，按式(2)计算最大效益U，即配送车辆

可由点i行驶到点j，当y(

)=1时，考虑其配送过程中的综合费用

确定每辆车的初始最优配送路线，转Step5；

      Step5：依据地理信息系统G实时反馈的路况信息，若路况情况良好，按既定的最优配送路线前进，否则转Step6；

      Step6：查询交通信息管理Agent所提供的路况信息，分析路况拥塞情况，并通过总控Agent和其余Agent之间的实时信息交流进行协商，通过协商结果选择出合适的加权因子f(a，b)的值，重新计算不同配送路线的最大效益U并排序；

      Step7：输出效益最大者，

时的配送路线L即为最优路线。

      4 仿真实验

      综合以上所述，采用面向对象的C#为开发工具，以较好的图形化界面为接口，对系统中的各Agent实体进行编程实现。C#中的Class可以对属性和方法进行封装，并可以进行动态生成和调整，所以在实际的设计过程中，把各Agent实体作为一个对象来开发，以SQL Server2005为后台数据库，保障了数据的存储和更新，友好的人机界面接口能给出相应的操作提示和系统信息的反馈。

      系统以图2为配送示意图进行仿真实现，为了便于和真实的地理位置相吻合，给出了配送中心和每个客户点的逻辑平面坐标，且其配送中心的选择有别于文献[1]、[11]、[12]中的把配送中心定在逻辑坐标点(0，0)的方式，避免了和地理信息衔接存在的困难，能更加真实地反映配送位置的任意性。其中配送中心

(17.5，14.5)，14个客户需求点表示为

，客户需求的货物计量单位为吨(t)，每辆配送车的载重量最大值为1t，即

≤1(r=1，…，m)，车辆的行驶距离的计量单位为千米(km)，图2所对应的客户点详细信息及货运需求量见表1。考虑到系统的可行性，将路况的拥塞情况映射到加权因子上，根据实时情况分析得出a，b的取值范围，见表2。通过人机交互界面对系统所用到的数据进行初始化，分别对没有采用加权因子的最优路径选择算法和采用加权因子不同取值的最优路径选择算法进行仿真实验。

      

      经仿真实验，其路线选择结果见表3，考虑加权因子的时间耗费和未考虑加权因子的时间耗费对比如图3所示。针对同样的客户配送点，在不含加权因子的算法的路径选择中，所走的路程不仅长，而且没有考虑路况拥塞和时间延迟，这就使得配送成本明显增加；而加权因子的引入不仅考虑了各站点之间的实际距离，更重要的是将路况拥塞情况换算成对时间的耗费上，且算法能根据随时获取的动态路况信息进行因子大小的调整，结果显示，加权因子的运用不仅缩短了配送的总里程，确保了最优路线的选择，而且节约了时间、降低了运输成本，为物流配送的最优路径选择问题提供了新思路和更有效的解决方法，从而为电子商务系统的信息化发展提供一定的技术支持。

      

      

      图3 是否考虑加权因子动态选择路径时间耗费对比图

      5 结束语

      本文利用Agent所具有的动态反应性和实时性，提出了基于多Agent的物流配送最优路径选择算法，通过多Agent之间相互合作，并及时地获取路况信息，不断调整动态加权因子值，以综合效益最大为驱动目标，实现了配送过程中最优路径的选择。实验结果表明，算法能在有效的时间内进行路径的全局搜索和寻优，保证了能快速高效地获得最优解，为物流配送路径的最优选择问题提供了新思路和方法，从而可以提高配送效率、降低配送中心的运作成本。

标签：因子分析论文;  物流配送论文;  路线论文;