基于Agent的物流配送最优路线决策系统研究
2020-12-15孙勇喻飞根徐昊汪余意
孙勇 喻飞根 徐昊 汪余意
【摘要】近年来随着电商平台与直播带货的火热发展，直接地带动了中国物流行业的快速发展以及促进行业资源的整合，提高了现在的物流速度。但是，现在的物流配送路线是由各个公司根据自己的效益所决定的，并不是最优路线。为了解决配送的最优路线问题，本文利用Agent的移动性、主动反应性以及实时性等特点，构建了基于Agent的物流配送决策系统，在系统的最优路线决策模型中利用Dijkstra算法来求解发货地与目的地之间的最优路线，从而实现物流配送最优路线的决策问题。
【关键词】物流配送 最优路线 决策系统 Agent建模 Dijkstra算法
一、引言
物流配送是现代物流管理的一个重要环节，是实现电商、直播带货的关键一环和基本保证。近年来，随着互联网的大力发展，电子商务得到了空前的发展。在今年疫情下，直播带货又将电子商务推上了一个新的高度。因此，也直接的带动了物流行业的迅猛发展。在今年一、二季度因疫情原因使得市场经济低迷的情况下，物流行业的经济指标依然有很好的增长。
现在的各种物流配送系统中，需要采取一些配送的策略来降低货运费用和行驶路程，提高物流配送速度和服务水平，物流配送策略其中车辆路线安排问题（VRP）是物流领域中一个研究的热点问题。VRP属于多约束条件的组合优化问题，是由Dantzig和Ramser于1959年首次提出，是运筹学、管理学、计算机应用、组合数学、图论等学科的组合优化问题。当前的物流配送路线决策涉及客户信息管理、订单信息管理、配送点管理、地理位置信息管理等许多方面，体系复杂庞大。因此需要建立一个物流配送决策系统，管理物流系统中的各种数据信息，选择配送的最优路线。
智能体（Agent）是人工智能领域中一个很重要的概念，出现于20世纪70年代，80年代后发展起来。智能体具有自治性、反应性、交互性、主动性以及社会性等特征。它自身拥有行为控制机制，可根据自身状态以及外部环境的感知，做出决策和相应的行为;因为具有社会性，所以它可以与其他的智能体进行交流合作;同时可以感知所处环境信息，可以实时的做出适当的反应。智能体的概念和方法不仅是计算机领域和人工智能领域研究的热点，而且引起了军事、教育、交通、物流等许多领域的关注和相关的应有研究。
本文利用Agent的移动性、主动反应性以及实时性等特点，构建了基于Agent的物流配送決策系统。在系统的最优路线决策模型中采用Dijkstra算法选择最优路线。
二、利用Dijkstra算法求解最优路线
（一）Dijkstra算法概述
在物流配送过程中最重要的一环是选择车辆最优配送路线问题即VRP问题，在车辆配送过程中，耗费的油量、花费的时间以及高速路费等支出与两点之间的路程是具有正相关性的。故而本文选择车辆配送最优路线以配送点与客户两点之间的最短路径为标准，即最短路线为最优路线。决策系统利用图论知识中的Dijkstra算法来求解两点之间的最短路线即为物流配送最优路线。
迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
（二）Dijkstra算法应用原理
物流配送点根据服务端发来的订单数据，解析数据得到客户的地理位置信息，利用地图可将配送点与客户看作地图上两点，其余点都是各个城市所设立的快递中转站。将配送点作为起点、客户作为终点，所以有物流配送网络图模型表示为G=
G=
其中，V={v1，v2，v3，v4，v5，v6}，E={dij|1≤i，j≤6}
Dijkstra算法求解流程包含以下方面：①初始时S只包含起点v1;U包含除v1外的其他顶点，且U中顶点的距离为起点v1到该顶点的距离;② 从U中选出距离最短的顶点k，并将顶点k加入到S中;同时，从U中移除顶点k;③更新U中各个顶点到起点v1的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离;④重复步骤②和③，直到遍历完所有顶点。通过以上四步即可求出v1到v6之间的最短路径即为物流网络配送过程的最优路线。
三、构建基于Agent的物流配送决策系统
为了对构建基于Agent的物流配送决策系统，我们需要知道现在的网络物流配送决策过程，然后从现有的决策系统中判断哪些模块是可以具有智能体的特性，以此构建基于Agent的物流决策系统。
（一）典型的网络配送决策结构
典型的网络配送决策过程主要分四部分：客户端、服务端、配送点以及运输。
（1）客户端的主要任务是与客户进行交互，客户在客户端上进行订单的填写以及订单的提交，并根据客户的应决定是否进行订单的修改。在客户端用一个客户Agent来完成，用来响应客户请求以及向客户反馈处理结果。
（2）服务端的主要任务是分析客户的需求信息、提取关键信息并广播给各个配送点，然后对配送点反馈的结果进行分析，寻找合适的配送点。如果没有找到合适的配送点，则向客户返回拒绝信息及拒绝的原因，客户可以根据提示原因修改订单信息继续提交。否则向客户返回订单接受信息。在服务端可以使用订单Agent和订单分配Agent来处理，订单Agent分析处理订单信息分析、向配送点广播、向客户反馈结果以及分析配送点反馈的结果。订单分配Agent主要承担寻找最优配送点任务。
（3）配送点的任务是可以根据GPS与GIS系统信息寻找配送点与客户之间的最优路线，同时对各个订单的信息进行跟踪，了解配送车辆的位置并将位置反馈给客户，客户可以实时查看訂单的状态，这部分需要决策系统来完成，且决策过程依赖模型库、合作库、知识库等等。
（4）运输主要是根据GPS导航将订单物品通过公路、高速或空运运抵客户所在城市，这部分可以使用车辆Agent来完成。典型的网络配送决策过程如下图所示：
（二）基于Agent的物流配送决策系统
通过上一节的分析，我们了解物流配送决策过程，其中许多的功能都是可以通过Agent来完成，依据图2的决策过程以及物流配送系统中各个部分的职责，得到相应的基于Agent的物流配送决策系统如图3所示。
系统中每个部分都是独立一个功能模块，包含了以下几个方面：
（1）用户单元：包含用户与下单界面，用户在下单界面下单，服务端通过网络将接受与否富人结果反馈到下单界面。
（2）Agent实体单元：包含各个功能Agent实体以及Agent总控部分。具体有①Agent总控：主要负责管理系统中的各个功能Agent以及监听系统各个事件，若发生某种事件则可以是对应的功能Agent活跃。②客户Agent：响应客户请求以及向客户反馈处理结果。③订单Agent：分析处理订单信息分析、向配送点广播、向客户反馈结果以及分析配送点反馈的结果。④订单分配Agent：寻找最优配送点。⑤车辆Agent：根据GPS与GIS将产品运到客户手中。
（3）信息提取及分析：提取客户订单信息的关键信息如家庭住址、联系电话、联系人等等。分析提取的关键信息以及系统其他功能模块反馈的日志信息。
（4）决策系统及决策库：决策系统根据模型库推演的最优路线以及其他的数据库、知识库中提供的历史数据来进行决策，选择出最适合的最优路线。在模型库中主要模型是基于Dijkstra算法求解最短路线的模型。
四、结语
本文研究的基于Agent的物流配送最优路线决策系统利用Dijkstra算法求解物流配送的最短路线，较为快速的为客户以及配送点给出合适的配送路线。利用Agent的主动性，移动性等特点构建了基于Agent的物流配送结构，整合了物流配送的各节点，使物流配送具有系统性，整体性。本系统可以为物流配送行业提高配送效率，降低了物流配送过程的费用，促进了物流行业的发展，具有很广泛的应用价值。
参考文献：
[1]申静.基于多Agent协商的物流配送最优路径选择问题研究[J].物流技术，2014，33（11）：95-98.
[2]陈宇.基于物流配送路径优化问题的最优化方法研究[J].今日南国（理论创新版），2008（12）：8-9.
[3]周宏，廖雪珍.基于Agent的网络物流配送决策系统研究[J].系统工程与电子技术，2004（10）：1421-1425.
[4]刘小玲，李辉，郭治国.基于狄克斯特拉算法的车间动态生产能力评估与实现[J].微计算机信息，2006（12）：96-98
[5]王华.基于Dijkstra算法的物流配送最短路径算法研究[J].计算机与数字工程，2011，39（03）：48-50.
作者简介：孙勇（1994-），男，汉族，湖北襄阳人，中国科学院科技战略咨询研究院2019级博士在读，武汉市中城事大数据有限责任公司，高级算法工程师，研究方向：机器学习与自然语言处理;喻飞根（1999-），男，汉族，湖南岳阳人，中南民族大学 计算机科学学院2018级本科生在读，研究方向：智能科学与技术;徐昊（1999-），男，汉族，湖北孝感人，中南民族大学 计算机科学学院2018级本科生在读，研究方向：自动化;汪余意（2000-），女，汉族，湖北大冶人，中南民族大学，计算机科学学院2018级本科在读，武汉市中城事大数据有限责任公司，工程师，研究方向：文本分析与语义挖掘。
