基于多智能体的网购生鲜无人车配送调度仿真

　　摘要：无人车配送可有效缓解目前末端配送效率低、人力成本高、安全隐患多等问题。本研究以城市社区网购生鲜无人车配送为研究对象，搭建了网购生鲜时空需求数据驱动的多智能体仿真平台，构建了基于实际路网的仿真环境及无人车、客户、配送站三类智能体，以运营成本最小及客户满意度最大为优化目标，设计并测试了动静态订单分配策略及距离最近或时间最紧配送路径规划策略。最后基于上海某生鲜电商实际订单数据，对不同策略展开情景模拟及敏感度分析，实现了运力资源的优化配置。

　　关键词：多智能体仿真;无人车配送;网购生鲜;订单分配;路径规划

　　引言近年来，即时物流订单量尤其是生鲜配送的规模逐年增加。调查数据显示，每周购买一次以上的生鲜网购用户达63.8%[1]。2019年的生鲜电商交易规模达1620亿元，相较于2018年增长29.2%[2]，2020年新冠肺炎疫情期间，相关生鲜电商平台的单日订单量同比增长200300%[3]，预计未来网购生鲜规模将进一步增大。据调查，我国居民网购生鲜产品时最注重的前两个因素分别是安全和品质，其比例分别占55.7%、49.3%。

　　人工智能论文： 基于5G的无人机智能组网的应急通信技术开发及应用

　　缩短配送时间可有效保证生鲜产品的品质[4]。由于网购生鲜配送时效性强、需求随机性高、规模逐年增大等特点，导致了人力配送难以精准效应网购生鲜配送需求，造成了配送效率低下、人力成本高昂、安全隐患多等问题。与此同时，我国在无人配送领域的政策不断完善，为无人配送的应用落地提供了政策支持。2017年月，国务院印发《新一代人工智能发展规划》，该规划指出行业需要不断完善无人配送车的技术标准。2019年月，中共中央、国务院印发《交通强国建设纲要》，明确提到要“积极发展无人机(车)物流递送”。

　　因此，许多电商企业、第三方物流和众多初创公司开始探索使用无人车、无人机、配送机器人代替人力进行配送，不仅可以缓解订单量暴涨导致的运力紧张，降低人力成本，也降低了疫情期间人际传播带来的潜在感染风险。无人车的加入，可代替难以管理的三轮车、电动车等车辆上路，减少安全隐患。电动无人车相比于燃油配送车辆，更利于保护环境。利用无人车进行城市社区网购生鲜配送，是生鲜配送服务链的最后一个环节，属于末端配送问题。针对末端配送的研究，主要由两个部分组成——订单分配和路径规划。由于针对无人配送的订单分配研究较少，因此在本研究中主要分析物流订单分配与网约车订单分配的相关研究。

　　邓娜和张建军(2018)基于聚类分析和TSP路径规划建立了O2O外卖订单指派模型，将一定时长内的订单进行聚类合并;刘鹏宇和陈淮莉(2018)对超售策略进行了研究，根据消费者对时隙价格的偏好建立Logit模型，采用强化学习的方法求解;戴大鹏(2018)以总体的物流成本最小、配送时间最短、配送质量最高为优化目标建立多目标规划模型，采用蚁群算法、遗传算法求解;Kuhnle等(2019)基于深度强化学习的方法对车间生产系统内的订单自组织调度进行了研究;Malus等(2020)采用多智能体强化学习的方法对生产系统内部的物料流动进行调度，通过自主移动机器人学习协同竞价的方式，实现更高效的订单分配目标。

　　滴滴出行[1在2018年提出了在线调度模型，基于实际订单数据，通过强化学习构建状态动作值函数，采用KM算法求解全局最优匹配;而在2019年，滴滴出行[1将时间因素加入状态动作值函数中，并进一步采用深度神经网络(CVNet)进行更好地未来订单匹配价值学习。在路径规划研究中，不仅包括无人车，还包括无人车与卡车、无人机与卡车的协同配送研究。

　　Zhang[1(2016)等人设定车辆有三个状态：在车站等候、服务客户、再平衡调度到另一个车站，建立混合整数规划模型进行求解;张嘉琦[1(2017)通过子目标点与无人车的连线将平面划分为自由扇区，并设计局部层和全局层进行路径规划;郭蓬[1(2019)等人基于Frenet坐标系理论，采用一元三次方程拟合局部层路径，并选取代价函数最小的最优路径;胡觉亮[1(2020)等以配送成本最小为目标，采用遗传算法与模拟退火算法相结合的方法求解电动无人车的路径规划模型。

　　Rabta[1(2018)以灾难援助为背景，以载重、能耗为约束，以成本最小为目标建立无人机末端调度模型;Agatz[1、Paul18(2018)采用means算法对客户群进行分类，采用动态规划方法求解;Chang19(2018)在运用means进行订单分类及建立旅行商模型后，对无人机向卡车的移动路径进行优化，以最小化配送时间;Yurek[2(2018)采用两阶段法，对客户和任务进行分配后，建立混合整数规划模型。

　　彭勇[2(2020)定义了三种客户类型：只能由无人机服务、只能由卡车服务和既可以由无人机服务，也可以由卡车服务，以服务时间最小为目标，采用混合邻域搜索算法进行无人机-卡车协同配送问题求解。在针对末端配送调度现有研究中，很少有研究将订单分配与路径规划组合在一起考虑;且现有研究方法主要分为分支定界法等精确算法和遗传算法等近似算法。随着问题规模的扩大，精确算法的计算时间将不断增加，因此模型运用范围受限。单纯地采用精确算法或启发式算法，不能够很好的描述无人车配送系统，并且难以应对大规模动态的无人调度决策[2,2。

　　由于智能体具有个体异质、自主行动、环境感知、信息交互等特点，基于智能体的仿真能够更加自然、连续的描述无人车、客户等实体之间的动态供需交互行为，并且在仿真过程中可以灵活的改变智能体的数量、属性、行为规则等。多智能体仿真从个体级别开始建模，模拟现实系统中的个体行为决策、个体之间的交互合作，系统的变化由单个智能体行为变化而涌现[2。

　　因此为了理解无人车生鲜配送系统在不同订单分配策略和路径规划策略下的表现，本文采用多智能体仿真的方法[2，并在此方法中嵌入贪婪算法，以辅助无人车智能体的行为决策。利用地理信息强化，将实际路网、配送站等环境信息纳入到仿真框架中。通过实际需求数据驱动微观个体仿真，以“自下而上”的建模思路，通过各智能体间的互动决策，群智涌现无人车配送调度系统整体优化效果。

　　1基于多智能体仿真的无人车配送调度方法

　　1.1多智能体仿真模型概述

　　基于网购生鲜需求时空变化特征，本研究搭建了基于多智能体仿真的无人车生鲜配送模型，由基于实际路网仿真环境及若干辆无人车智能体、若干个已知地理位置的客户智能体和一个配送站智能体组成;基于智能体间的互动，设计不同的订单分配策略和配送路径规划策略，以实现客户满意度最大和无人车运营成本最小的优化目标。本研究建模主要基于以下假设：(1)所有无人车均从配送站出发并最终返回配送站;(2)每辆无人车型号、最大容量均一致;(3)每位客户的需求量为非负值且小于等于每辆无人车的最大容量;(4)在配送过程中每位客户只能由一辆无人车服务;(5)无人车每次的装载量均不超过其最大容量;(6)无人车匀速行驶，不考虑行驶过程中出现交通拥堵、交通事故等突发情况;(7)配送站拥有全品类的生鲜产品，能够满足当日所有客户的需求;(8)只考虑单纯送货任务，不考虑客户取货情况。

　　1.2智能体定义

　　1.2.1智能体类型及属性

　　①客户智能体客户智能体的属性主要包括所在位置、下单时间及可接受最大延误时间。客户智能体的行为主要包括向配送站发送订单和计算自身满意度。客户智能体的状态随着配送过程推进依次变化：客户下单后由普通客户转变为待配送客户;该客户订单分配给某一辆无人车后，状态由待配送客户转变为目标客户，但状态仍为false，待无人车在配送站取完该客户的货物后，其目标客户状态变为rue;无人车决定优先配送该客户的货物时，状态由目标客户转变为当前客户;无人车完成该客户的货物配送后，状态又由当前客户转变为普通客户。

　　②无人车智能体无人车智能体的属性主要包括数量、位置、运行速度、最大容量、目标客户列表等。无人车智能体的行为主要包括返回仓库取货、优化目标客户配送的先后次序、记录运行公里数及运行轨迹。本研究探讨的无人车具有同样的容量和成本等参数。③配送站智能体配送站智能体的属性主要是待配送客户列表。配送站智能体的行为主要是分配待配送客户订单给无人车以及更新待配送客户列表。

　　1.2.2智能体行为规则①客户智能体向配送站发送订单：待系统时间到客户的下单时间时，客户智能体会向配送站发送订单。配送站每五分钟更新一次客户新订单。

　　1.3环境定义仿真环境包括配送站、实际路网、居民区建筑等实物信息及节假日、疫情实时状态等环境信息。仿真环境中有且仅有一个配送站。由国外的管理经验可知，目前国外无人车行驶的道路主要有两种：人行道与机动车道，不允许在高速公路上行驶。因此无人车行驶的实际路网不包含高速公路。

　　1.4仿真系统运行流程本项目无人车生鲜配送仿真流程如图所示，主要体现了无人车、客户、配送站三类智能体间的交互，通过不断调整无人车配送路径规划策略和配送站订单分配策略，涌现无人车自主配送智能调度效果，实现客户满意度最大和运营成本最小的优化目标。

　　2城市社区无人车配送案例研究

　　2.1仿真数据输入

　　本研究以上海市嘉定区某生鲜电商的配送区域为研究对象，拟使用无人车进行网购生鲜配送服务。配送区域面积为8km×5km，有个生鲜配送站。共有42个住宅小区，3400多个住宅建筑，总人口为260多户，基于该生鲜电商实际订单数据，新冠肺炎疫情期间，该配送区域工作日的日均订单量为800多单。本研究以该配送区域某个工作日生鲜配送需求为例，共有858名客户智能体参与仿真。

　　客户智能体属性参数均来源于网购生鲜客户调查数据，其中包括客户下单时间、可接受的最大延误时间及家庭月收入水平。无人车智能体属性参数来源于现有文献，包括车辆速度、租赁成本、行驶成本、最大容量等。目前无人车技术可实现30秒弹夹式智能换电，100公里续航[2，因此本研究假设无人车在一天的配送过程中不需要中途充电。

　　2.2仿真场景构建

　　在仿真场景的模拟中，共考虑了静态、动态订单分配和距离最近、时间最紧配送路径规划两两组合的四种策略组合场景。静态订单分配与动态订单分配两种场景的区别在于无人车是否中途取货。距离最近配送与时间最紧配送两种场景主要体现在无人车取完所有目标客户的货物后，如何进行配送路径规划。在上述四种策略组合场景中，通过改变无人车的数量及最大容量，来达到客户满意度最大(即延时惩罚成本最小)和运营成本最小的优化目标。同时延时惩罚成本和运营成本共同组成了系统总成本，因此可将多目标优化问题转化为单目标优化问题进行讨论，从而选择最优的策略组合。

　　2.3结果分析

　　本文以运营成本最小及客户满意度最大为优化目标，设计并测试了动静态订单分配策略及基于贪婪算法的距离最近或时间最紧配送路径规划策略。为了更好地对仿真结果进行分析，在上述仿真结果中选取了四种策略下的最小延时成本、最小运营成本、最小系统总成本、最小平均行驶公里数以及对应的无人车数量和最大容量，如表所示。当无人车数量较大，容量较小时，延时惩罚成本最小;当无人车数量最小，容量最大，运营成本最小;当无人车数量较大，容量最小时，系统总成本最小;当无人车数量最大，容量最大时，平均行驶公里数最小。当订单分配策略为静态分配，配送路径规划策略为最近优先配送时，系统总成本最小为15579元，此时无人车数量为28辆，无人车最大容量为。

　　2.4敏感度分析

　　通过2.3节不同策略组合下的仿真结果对比分析，静态订单分配与最近配送路径规划是最优的策略组合。因此基于该策略组合，本节对无人车数量及无人车最大容量对系统总成本影响进行了敏感度分析。

　　3结论

　　随着网购生鲜规模逐年增加，传统的依靠人力的配送模式已难以满足配送需求。交通强国等政策的支持及新冠肺炎疫情的影响加速了无人车配送在城市末端配送的应用落地。本研究基于网购生鲜需求时空变化特征，搭建多智能体仿真平台，评估无人车配送模型的运营成本以及客户满意度。基于上海市某生鲜电商的某配送区域的实际订单数据和网购生鲜客户调查数据，对网购生鲜无人车配送展开实例仿真分析。通过仿真结果的对比分析，发现当组合策略为静态订单分配，路径规划策略为距离最近优先配送时，延时惩罚成本和运营成本皆最小，从而系统总成本最小。

　　并在此策略下，对无人车数量和无人车的最大容量对系统总成本影响进行了敏感度分析，发现为满足该配送区域的网购生鲜订单配送服务无人车日均数量应不少于18辆。本研究中的无人车配送路径规划采取了贪婪算法，无人车总是选取距离最近或时间最紧的目标客户进行优先配送，所得结果易陷入局部最优。未来的研究将融合深度强化学习从全局优化的角度进行无人车配送的智能调度。本项目研究中的无人车行驶路网已基于现有地理信息筛选优化，但还需更精细的地理信息识别，以提升方案结论的落地性。

　　参考文献：

　　[1]艾瑞咨询.2019年中国生鲜电商行业研究报告[EB/OL].[202018].http://report.iresearch.cn/wx/report.aspx?id=3400.Iresearch.2019ChineseFreshEcommerceIndustryResearchReport[EB/OL].[202018]. http://report.iresearch.cn/wx/report.aspx?id=3400. 

　　[2]艾媒咨询.2019年中国生鲜电商行业商业模式与用户画像分析报告[EB/OL].[202018].http://report.iresearch.cn/wx/report.aspx?id=3400.Iresearch.2019ChineseFreshEcommerceIndustryBusinessModelandUserPortraitAnalysisReport[EB/OL].[202018]. http://report.iresearch.cn/wx/report.aspx?id=3400. 

　　[3]张珉.新冠肺炎疫情下的无人配送[J].企业观察家,2020,(3):4647.ZhangMin.AutonomousDeliveryintheContextofCOVID19[J].CorporateObserver,2020,(3):4647.

　　[4]史映红.生鲜产品物流配送中存在的问题及对策[J]..现代商业,2020,(2):6061.

　　作者：陆淼嘉，黄承媛，滕靖

转载请注明来自发表学术论文网：http://www.fbxslw.com/dzlw/27881.html