基于多Agent 的物流车辆调度系统研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于多Agent 的物流车辆调度系统研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：互联网和信息技术的高速发展推动物流行业的快速发展，物联网等新技术应用于物流调度将物流车辆调度系统与存储管理信息系统等进行数据交换，并协同完成车辆调度，使得物流的效率最大化。该文从物流车辆调度策略及优化算法，多Agent的物流车辆调度系统，物流车辆调度系统的实现等三个方面展开了研究， 综合C-W算法和启发式调度算法以及他们在物流调度策略的作用，提出了自己的物流调度策略。利用多Agent技术的成果，设计出基于多agent的物流调度系统的业务逻辑、应用逻辑、基础接口和智能四大部分，完成多Agent的物流调度系统的体系结构。

关键词：物流调度；多Agent；调度策略；C-W算法；启发式算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）32-7248-05

伴随物流行业的发展Agent技术[1]也在不断发展，在许多领域取得非常多的应用成果。在现代物流集约化和一体化的发展趋势中，车辆优化调度的效率已经影响到消费者，优化货运车辆的调度，科学管理货运组织对货运车辆调度理论与方法进行系统研究有着极为重要的意义，是建立智能交通运输系统，现代物流调度系统的基础。车辆优化调度的核心在于优化车辆线路，因此目前国内外大部分的研究在于优化车辆配送线路。Dantzig和Ramser于1959年首次提出车辆优化调度问题，许多学科专家运用不同的算法，运用不同的技术开始研究这个领域，比如运用人工智能，神经网络等技术对车辆优化调度问题开展了大量的实验模拟和理论研究，取得了大量的研究成果。该文运用现代物流理论以及信息技术等方面的研究成果，设计了物流车辆调度策略及优化算法，构建了基于多Agent的物流车辆调度系统，并以此为基础设计并实现了该物流车辆调度系统，结合C-W算法和启发式调度算法以及他们在物流调度策略的作用，提出了物流调度策略。

1 多Agent技术与物流车辆调度理论

1.1多Agent技术简介

Agent的概念起源于20世纪70年代的分布式人工智能，在计算机领域，Agent又称为软件智能体[2]。它一般具有自主性、交互性、反应性和主动性的特征。实际上，Agent的概念在分布式系统自身的管理应用已经非常广泛了。例如，在80年代Agent技术就开始应用于基于TCP/IP的互联网络管理技术的SNMP模型中。在该模型中，Agent是运行在被管理单元上的具有自我意识的程序段，它能够响应管理单元发来的管理命令，对被管理单元上的相关事件做出反应等。然而直到今天，人们才开始重视Agent技术在分布计算领域的应用，因为它对解决当今分布式应用的一些问题具有很好的效果[3-5]。

1.2物流车辆调度理论方法简介

国外车辆优化调度研究已广泛用于生产、生活的各个方面，如快递邮件投递、物流配送、车辆载货等等。在过去的几年里车辆优化调度取得不少成果，除在物流行业应用外，在工业管理、计算机应用等领域也广泛的应用，还用于各种行业计划安排、发货单的计划与控制等各个领域[6]。

1）启发式算法

启发式算法是计算机算法分析与设计中一种常用算法，主要用来计算最优值或者寻找出最佳方案，我们将这种算法运用于物流调度的多Agent系统中，主要是用来寻找出在车辆调度中的最佳运输路线方案。

2）C-W算法

C-W算法是一种非常常见的启发式算法，利用前人的经验来提升模型的精确度，通过跟踪校正过程逐步找出满意解[7]。

算法开始先设计由一个配送中心和N个零售商组成数学模型中，配送车辆的路线安排变得非常困难，这个数学模型适合采用启发式算法。节约量公式描述为：首先将配送中心用数学模型表示为[P0]，N个零售商用数学模型表示为[P1，P2，....，PN，]，已知任意节点PI和Pi的距离我们表示为公式[Pij（i，j=1，2，...，N）]，我们假设外对任意零售商Pi和Pj的分别取合并送货和分离送货两种方式，前者比后者节约的运输距离为：[Sij=d0i+d0j-dij]j。根据三点的位置关系可以计算出节约量[Sij≥0]。

1.3 一般运输调度问题的数学模型

车辆优化调度问题的数学模型我们将做以下定义为：在物流调度模型中，我们随即设计一连串装货点和卸货点，然后在满足货物需求量、货物的发送量、客户要求交发货时间、车辆载重、车辆行驶里程限制、送货时间等约束条件，对各点之间构建行车线路，使车辆根据调度策略通过这些装卸点，完成既定目标（如降低费用等）[8]。

物流调度的核心问题就是车辆与运输调度问题，运输调度问题描述为是，假设某种货物有m个产地[A1，A2，.......，Am]。其中各个产地的货物产量值分别是[a1，a2，......，am]，再假设货物有n个销地[E1，E2，.....，En]，销地的销量分别是[b1，b2，....，bn]。假定从产地[Ai（i=1，2，...，m）]向销地[Ej（j=1，2，...，n）]运输货物单位物品的运价是F，那么我们建模的目的就是考虑在达到运输的要求的同时使得整个系统的总运费最少。

2 物流车辆调度策略与优化算法设计

2.1物流车辆调度策略设计

物流调度策略的设计主要是在限定一些条件下开始系统建模，然后利用一些较好的算法来实施物流车辆调度设计，因为建模方式和选定的限定条件不同，会得到完全不同的调度效果，同时会付出完全不同的调度代价[9]。

本文算法建立了一种基于多Agent技术的车辆竞标和合作协同完成任务的调度优化算法。整个系统由多Agent来构建，利用车辆调度的已有的算法研究成果，以及Agent在其他领域的应用成果，在兼顾平衡系统调度代价和目标优化等多种因素后提出一种混合调度策略。其核心思想在于，调度控制Agent统一安排大批量任务，车辆Agent自主决定执行小批量任务，，从而进一步提高调度系统效能 [10]。构建的物流车辆调度算法主要分为三个步骤：如下图。

2.2 物流车辆调度优化算法设计

2.2.1 规划型的任务优化算法

对于规划型任务，我们首先在建模的时候限定在特定车场，车辆采用的是特定车型，在这样的限定条件下进行发货单的分配。本算法利用启发式算法的基本规律，利用已有的成果对物流车辆的调度系统设计了一个行车路线优化的算法，通过分配、组合方式、反复的递归求解，对所有的任务进行分配联合，最终形成最优的行车路线，然后根据最优解来进行车辆的调度。具体算法说明如图2。

2.2.2 Agent竞标合作算法

Agent的竞标合作算法中车辆可以根据任务进行自主性调整，Agent能够在运输过程中对新任务进行动态安排，这种情况适合解决任务量少，车辆比较多的情况，也比较符合真实情况。此算法比较适合于已经进行初始安排的车辆动态调配新的发货单情况，是对前面一种情况的有利补充。若采用前面一章介绍的算法，这样新添加的发货单任务必须等待，等到一次新的初始化才能有效地插入到车辆的任务队列。针对这种经常发生的情况，提出了利用车辆Agent，车辆进行自主调整任务的调度算法，这种算法中车辆Agent根据调度Agent发送的任务清单，利用自身的状态参数来进行自主化的判断。算法具体实现见下图。

具体算法思想：系统出现新的货单任务时，系统首先到调度控制Agent上，再由调度控制Agent下发任务，来告知所有车辆Agent。我们这样的优化策略不再是静态的任务分配，算法将根据各种不同的现实环境，来进行系统的自主调整，这样的调整能够提高算法的自适应能力。系统将对不仅仅是进行初始化的任务分配，而且需要开始考虑未来的新增任务的情况，系统的动态考虑参数会很多，整个系统会根据各种状态的变化，自主的寻找动态的最优解，这样最优解不是针对整个系统，最优解可能是在一定时间，或者系统的某一个阶段的最优结果，在获取动态订单我们会将计算结果反馈给调度控制Agent，如果任务能够一次性完成，就由调度控制Agent告知对应车辆。如果发货单无法在任意一个车辆Agent完成，控制Agent将对发货单任务进行拆分，先将任务分解成能够由代价最小的车辆能够单独完成的量，然后将剩下任务给再由其他车辆Agent竞标，然后反复迭代，知道任务分配完毕。

3 基于多Agent的物流车辆调度系统设计

3.1系统体系结构

利用现有调度系统的模型，结合目前Agent技术取得的研究成果，提出了一种基于多Agent的物流车辆调度系统架构。将系统主要分为应用层、业务逻辑层、Agent层、物流实体层四层，系统通过接口来与仓库管理系统、GPS系统等外部系统实现信息的对接，具体的构架见下图。

3.2物理实体层

物理层的物理外部系统和设备可以看作一个实体，甚至可以将地图都作为一个实体，这些实体可以为层服务，它能够和外部系统通过接口连接起来，甚至将外部的系统信息转换为系统的内部信息，通过物理层的系统对外部系统的控制，物理物理层实体详情如下：

1）全球定位实体。主要用于获取车辆的地理信息，经度和纬度坐标，它主要是用来存储当前车辆地理信息，为上层提供实时的路线优化信息。

2）短信通信实体。 SMS通信系统主要是用于与实体的车辆的信息通信，车辆可实时返回的信息中心，同时要求也可以解码短信，SMS可以处理不同类型的服务，以满足各种车辆需求。

3）车辆终端。该终端主要实现两个类型的功能，一个是可以实时查询车辆状态，包含车辆的位置，速度等车辆营运车辆状态参数和地理信息，另外一个是对车辆进行控制，如断油、速度设定、部署设置。它还有一个车辆调度信息系统，使驾驶员可以按照系统安排工作的操作。

4）地理信息实体。与地理信息系统进行交互，提供必要的数据，为优化实体提供基本的地理信息，一些性能良好的地理信息实体要能够做到实时交通信。

5）仓库管理的实体。对应仓库系统，主要指仓库的货物数量以及货物存储信息，企业的货物存放信息，以及该实体能够获取的货物情况，将能够完成货物的运输路线、地理信息的商品、货物的数量、货物的重量和其他安排的关键数据，并且可以动态更新的仓储信息。

3.3 Agent层

根据底层业务逻辑的分析，为上层Agent服务，Agent将根据实施相应的逻辑层的业务需求。在层中，调度和控制Agent是所有Agent的核心，它负责协调各种Agent之间的决策关系。详细组织关系的设计如下图所示：

对本层中各种Agent的功能进行简单的描述如下：

1）发货单Agent功能描述

发货单Agent主要是在接收客户发货单以后进行简单处理，然后将简单处理结果反馈给调度Agent。本Agent的核心功能包括：发货单输入、发货单分解、发货单合并、任务分配这几个模块。发货单输入模块主要是接受各类输入的发货单任务，并将其存入数据库，并记录发货单执行情况；发货单分解模块主要确定发货单中各类商品的地点，将发货单转化为有明确起终点、明确任务量的任务单；发货单合并模块主要功能是拆分任务单，然后在满足车辆容量和仓库商品数量限制条件下将起点和终点相同的任务尽量合并起来。任务分配模块主要功能是将任务下发到执行Agent并将任务的执行记录和执行情况记录进数据库。

2）车辆Agent

其实每一个车辆Agent都代表现实的一台车，他具有车辆的行为状态，能够通过他查看车辆目前的信息，同时他还能够在调度系统起到参与竞争、协作。一个车辆调度系统中有一个到多个车辆Agent，车辆Agent由调度控制Agent进行调度和任务的分配，同时本Agent能够根据系统调度Agent分布的任务信息，来进行计算考虑是否参与任务的竞标；同时能够评估任务能否胜任工作并在获得竞标成功的消息后将任务放入执行队列，在接收任务以后负责执行完，并能够将车辆状况信息及时通报给调度控制Agent，便于调度控制Agent的调度。

3）调度控制Agent

Agent系统的核心功能就是能够信息交换，其包含仓库管理系统、发货单任务的详细信息、地理信息系统的信息中新等多个模块的信息交互。同时，它将复杂任务下发给车辆Agent。其具体职能如下：将任务数和系统的车辆数来确定系统属于什么类型，任何根据类型来决定是否采取招标方式还是任务直接分配方式；在确定任务的优化调度类型的情况下，系统将采取前文所介绍的算法来进行任务的分配，通过递归迭代计算，找出分配的最优方案，任何将任务分配给不同的车辆，完成调度结果。如果使用招标，将公布的汽车，通过竞争性招标，以提供车辆任务完成任务确定车辆的成本信息的任务。信息交与车辆，车辆由完成最后的任务。接受有关车辆的当前状态以及地理信息，如车辆容量测试、车辆状态信息监控。在执行任务的仓库管理信息进行更新，以保持一致性情况下的资源更新。

4）仓储管理Agent

主要用于对应仓库管理系统这个外部系统的接口，它能够和调度Agent进行信息交换，根据调度Agent指派的任务将仓库的货物信息及时反馈给调度系统，并且根据车辆Agent的运行情况及时更新库存。

5）地理信息Agent

主要是和地理信息系统打交道，向调度控制Agent提供车辆Agent以及一些仓库地图地点的经纬度坐标信息，能够通过地理信息系统获取目前的线路的路考，为调度系统提供调度决策的基础信息。

3.4业务逻辑层

业务逻辑层主要是系统的一些基本的业务单位，许多业务单位组织成一些宏观业务逻辑。这些业务逻辑是一种上层应用的接口，为应用层提供技术的封装。其主要有以下一些业务需求：子发货单业务逻辑负责发出发货单任务分配调度控制单元，并反馈执行的任务；发货单分解业务逻辑负责对任务按照顺序进行分解，但同时参考交货时间，车辆的能力；库存信息查询业务逻辑负责查询当前库存的商品。车辆信息查询业务逻辑负责车辆能力状态的查询分析和决策的能力。发货单合并业务逻辑就是能够把将打破后的项目再次组合成一个可执行车辆的发货单执行的任务；库存信息更改业务逻辑负责库存的商品库存的变化信息在更改信息或其他情况下，实时改变库存信息。

3.5应用层

应用层主要包括物流计划、发货单处理和调度系统资源管理三大模块，三大模块详细描述如下：物流计划就是根据发货单等信息，确定系统的总的物流调度计划，这个是为调度系统提供安排的基础数据，他能够集中初始化任务和车辆数量，是系统的基础。发货单处理系统能够外接外部的发货单信息的录入，并且能够将发货单进行合并，归类处理，为后期的调度系统的顺利调度提供数据基础。调度系统资源管理主要是负责对数据进行处理，能够将发货单按照计划，开始动用系统初始化的车辆和仓库，能够很好的调度车辆，完成物流运输任务，同时保证消耗的资源最少，他能够管理各种资源的使用（库存、交通等）的信息，并且能够向调度Agent提供信息检索，动态刷新的基本功能。

4 结论

本文利用现有调度系统的模型，结合目前Agent技术取得的研究成果，提出了一种基于多Agent的物流车辆调度系统架构。利用多Agent技术的成果，设计出基于多Agent的物流调度系统的业务逻辑、应用逻辑、基础接口和智能四大部分，完成多Agent的物流调度系统的体系结构。根据物流调度的现状，完成了物流系统额原型化，并且给出系统的中结构架图，并且分别给出算法的具体实现。

展望未来，我们在设计基于多Agent技术的物流调度系统中，还有以下几个方面值得深入研究：物流调度领域的其它辅助Agent的详细结构，研究多车场多车型的运输问题。研究基于Agent的调度算法的动态集成方法，发货单的评估技术的方法。

参考文献：

[1] 鲍晓鸣.基于Agent的分布式GIS在物流配送系统中的应用[J].宁波职业技术学院学报，2011（5）：24-27.

[2] 孙学琴.基于GPS的第三方综合物流管理信息系统分许与规划[D].青岛：山东科技大学，2004.

[3] Kroeger R.Performance and scalability measurement of COTS EJB technology[J].Computer Architecture and High Performance Computing， 2002（10）：212-219.

[4] Qing Caoa，Marc J.Schniederjans. Agent-mediated architecture for reputation-based electronic tourism systems： A neural network approach[J].IEEE TRANSACTIONS ON INFORMATION THEORY，2008，54（6）： 2818-2826.

[5] Hyun G M.An Effective Method to Design CBD Components in Enterprise JavaBeans[J].Software Engineering Research，2006，9：49-56.

[6] 邵建利.物流管理信息系统[M].上海：上海财经大学出版社，2005.

[7] 兰宜生.电子商务物流管理[M].北京：中国财政经济出版社，2001（8）：35-37.

[8] 王红卫.基于WEB的物流信息管理系统的分析与研究[D].西安：西安理工大学，2004.

[9] Zeadally S，Lu J，Nanduri S.Design and implementation of a Jini-J2EE bridge to enable access to enterprise services [J]. Consumer Communications and Networking Conference， 2004（1）： 370-375.

[10] 刘向，李延晖. 电子商务配送的跨区域VRP模型及其启发式算法[J]. 清华大学学报：自然科学版， 2006， 46：76-81.