考虑末端配送方式感染风险及消费者满意度的车辆路径问题研究.pdf

计算机时代 2023年 第9期0 引言后疫情时代，居民使用生鲜电商app频次增加，但配送成本过高一直都是亟需解决的问题，末端配送路径优化是降低成本的重要手段1。除成本问题外，满意度也是十分重要的问题，它影响着客户重复购买的意愿2。客户满意度大多体现在时间窗上3，运输时间过长也会影响生鲜食品的货损程度。在时间满意度、食品货损程度等约束条件下，适当的规划行车路线，实现成本控制，这是车辆路径问题的重要研究内容。在生鲜配送的路径问题研究中，余海燕等以配送距离最小为目标，构建生鲜外卖即时配送路径优化模型4。物流成本最小化也是生鲜配送的重要问题5。在生鲜配送的多目标问题中，詹红鑫等人以配送成本最小，路径风险最小为目标构建路径优化模型6。由于感染风险是疫情背景下所特有的，因此本文在考虑末端配送方式满足客户满意度前提下，以最小化物流成本和最小化感染风险为目标构建模型，运用改进的 NSGA-算法求解该问题，通过算例实验来验证算法的有效性与可行性。1 问题描述及模型构建1.1 问题描述本文研究后疫情时代生鲜配送车辆路径优化问题，定义G=(V,E)为一个完备的无向图，配送中心用 0 DOI:10.16644/33-1094/tp.2023.09.013考虑末端配送方式感染风险及消费者满意度的车辆路径问题研究陆心航1，徐宗露1，刘文2(1.江南大学商学院，江苏 无锡 214122；2.南京理工大学机械工程学院)摘要：在商品供应链中，生鲜配送成本过高是亟需解决的问题。本文考虑疫情的感染风险对生鲜配送路径优化问题展开研究，以最小化物流成本和最小化感染风险为目标构建模型，设计优先级三层编码方法，使用NSGA-求解问题。在此基础上，增加逆序邻域策略改进NSGA-，提高算法的收敛性。最后进行数值实验，验证了模型的可行性以及改进算法的优越性。关键词：后疫情时代；生鲜电商；车辆路径问题；NSGA-；客户满意度中图分类号：C93;TP18文献标识码：A文章编号：1006-8228(2023)09-59-05Research on vehicle routing problem considering the infection risk ofterminal distribution mode and consumer satisfactionLu Xinhang1,Xu Zonglu1,Liu Wen2（1.Business School,Jiangnan University,Wuxi,Jiangsu 214122,China;2.School of Mechanical Engineering,Nanjing University of Science and Technology）Abstract：In the commodity supply chain,the high cost of fresh food distribution is an urgent problem.In this paper,consideringthe infection risk of the epidemic,the optimization of fresh food distribution route is studied.A model with the objectives ofminimizing logistics cost and infection risk is constructed.A priority three-layer coding method is designed and NSGA-is used tosolve the problem.On this basis,the inversion neighborhood strategy is added to improve the convergence of NSGA-.Thefeasibility of the model and the superiority of the improved algorithm are verified by numerical experiments.Key words：post-epidemic era;fresh e-commerce;vehicle routing problem;NSGA-;customer satisfaction收稿日期：2023-03-29作者简介：陆心航（1998-），男，江苏常熟人，物流工程与管理硕士，主要研究方向：物流与供应链管理。59Computer Era No.9 2023表示，客户集合用N=1,2,n 表示，V=N 0 表示图中节点集合，配送员与配送车辆集合用K=1,2,m 表示，E=()i,j,i,j V,i j 表示各节点间的弧集合。具体描述为：一个配送中心有k个配送员和k辆车执行送货任务，将货物送往n个客户点。每个客户点都有三种交付方式可以选择：快递柜、物业和送货上门。1.2 参数设置N=1,2,n：表示客户集合；K=1,2,m：表示车辆与配送员的集合；Ck：表示第k辆车及第k个配送员的固定成本；Cl：表示使用第l种交付方式所需要的单位时间成本；Cl:表示使用第l种交付方式所需要的固定成本；Cg1：表示使用快递柜的固定成本；dij：表示从点i到j之间的距离；A：表示配送过程中单位距离重量成本；qj：表示第j个客户的货物需求量；tj：表示到达第j个客户点的时间；V：表示车辆行驶速度；tjl：表示配送员配送生鲜的服务时间，包括交付时间及等待时间；t1,t2：表示客户的期望时间窗；T1,t1)，(t2,T2：表示客户可接受时间窗；：表示商品提前送达时客户对时间的敏感系数；：表示商品延迟送达时客户对时间的敏感系数；：表示客户满意度的最低要求水平；yj：表示客户可容忍的最高货损率；Sj()l：表示客户j对第l种末端配送方式的满意度；Y：表示单位时间货损系数；Q：表示配送车辆的最大装载量；N+：表示区域内的感染人数；N：表示区域内的总人数；l：第l种末端配送方式下，客户受到配送者感染风险的概率系数；l：第l种末端配送方式下，配送者受到客户感染风险的概率系数；l：表示末端配送方式，当l=g1时，表示将货物放在快递柜作为末端配送方式；当l=g2时，表示将货物放在物业作为末端配送方式；当l=g3时，表示将送货上门作为末端配送方式；xijk：xijk=1表示从点i到j由第k个配送员配送，xijk=0表示从点i到j不由第k个配送员配送。1.3 模型构建物流成本模型物流成本模型：由配送车辆及配送员人力的固定成本CA、配送车辆的配送成本CB、以及末端配送方式的交付成本和交付过程中配送员的等待成本CC构成。具体公式如下所示：CA=k=1mCkCB=i=0nj=1nk=1mdijxijkAqjCC=j=1n(Cl+Cltjl)其中,Cl=Cg1,l g10,l g2,g3tjl=1,l g1,g212exp()-()x-222,l g3末端配送方式感染风险模型：本文假设城市总人数为N，城市中尚未采取隔离措施的新冠疫情肺炎病毒携带者人数为N+，人们在城市中的感染概率为P。客户与配送员的感染概率如下所示：Pkstart=N+NPjstart=N+NPjend=Pjstart+lPki()1-PjstartxijkPkj=Pki+lPjstart()1-PkixijkP*=k=1mPk0+j=1nPjend其中，Pkstart表示配送员初始感染概率，Pjstart表示客户初始感染概率，Pk0表示配送员回到配送中心感染概率，Pjend表示客户j拿到货物后的感染概率，Pki表示配送员在点i的感染概率，Pkj表示配送员在点j感染概率。客户满意度模型客户满意度模型：客户的满意度会收到收货方式的影响。具体交付方式满意度和时间满意度设置表示如下：Sj()l=b,l g1b-c,l g2a,l g360计算机时代 2023年 第9期Sj(tj)=()tj-T1t1-T1,tj)T1,t11,tjt1,t2()T2-tjT2-t2,tj(t2,T20,elseVRPTWVRPTW模型模型：根据物流成本模型、感染风险模型和客户满意度模型，以客户满意度作为约束条件，以最小化物流成本和最小化感染风险为目标构建模型如下：F1=Min()CA+CB+CCF2=Min(k=1mPk0+j=1nPjendm+n)s.t.：S=j=1nSj(tj)+j=1nSj()l2n j=1nxijk.qj Q,k 1,2,myj=Y()tj-t0 yjj=1nx0jk=i=1nxi0k=1,k 1,2,mj=1nxijk=i=1nxijk=1,k 1,2,mi=1nxihk-j=1nxhjk=0,h n,k 1,2,m式表示物流成本最小化；式表示感染风险最小化；式是客户满意度约束；式是车载容量约束；式是生鲜货损率约束；式表示配送车辆始于配送中心，终于配送中心；式表示每个消费者仅被一个配送员服务；式是保证路线的连贯性。2 基于优先级三层编码改进的NSGA-算法目前，遗传算法已经有了较为成熟的研究。NSGA-与NSGA相比，复杂度更低，求解速度更快，收敛性越好。因为本文使用了NSGA-求解感染风险和成本最小化的双目标问题，图1为NSGA-改进算法流程。2.1 基于优先级编码方法简介基于优先级编码方法相较于传统编码方式有如下优点：相对传统的编码方式，该方法降低了决策变量维度，提高了求解效率；通过解码获得的路径均为从起点到终点的完整路径。具体编码过程如表1所示。图1增加局部搜索的NSGA-改进算法流程图表1基于优先级编码方法算法算法1 1：基于优先级编码方法输入输入：具备n个节点和a条边的多重图G=(V,E)输出输出：一条由起点到终点的完整路径1234567891011将多重图的起点和终点分别记为v1和vn生成一组优先级序列号作为决策变量，序列号为1-，且不重复基于多重图邻接关系生成每个节点的候选节点初始化当前节点:vs v1初始化路径:R=vs,whilewhilevs vndodo在节点vs的候选节点中，选择优先级最大的节点vc作为路径的下一个节点更新路径:R R vc将节点vs的优先级设为0更新当前节点vs:vs vcvi vcreturnreturnR61Computer Era No.9 20232.2 三重编码方法简介本文具体案例：某个配送员将物资以某种配送方式送给某个客户。为此设计了三层实数编码。第一层，客户点优先级编码，第二层，车辆路径选择编码，第三层，末端配送方式选择编码。第一层编码：1,3,2,4,6,5,7,10,8,9；第二层编码：(0-1-5-9-0)(0-2-4-7-0)(0-3-6-8-10-0)；第三层编码：1.0,1.0,1.0,3.0,2.0,2.0,2.0,1.0,1.0,2.0。2.3 局部寻优策略逆序策略逆序策略：在染色体的基因中，随机选择两个不同的位置生成n1、n2两个点，对n1、n2两点之间的基因（包括基因的优先级、配送车辆和顺序、交付方式）进行逆序排列，形成新的编码序列。如图2所示，n1、n2分别为客户点3与客户点10，采用逆序策略后，路径3为0108630。客户点处的基因全部逆序。图2路径逆序策略示意图3 算例实验假设平台接到 20个订单，配送中心有 10辆配送车辆，配送车辆速度为 300m/min，最大车载重量为30kg，每辆车和每个配送员固定成本为50元。单位距离重量成本为0.001元/m*kg；快递柜的固定成本为0.5元/次，交付的单位时间成本为1元；单位时间货损系数为 0.005货损，客户对送达时间的敏感系数为 0.2。配送过程中生鲜货损率小于0.6，客户满意度阈值为0.6，直接接触的感染风险概率系数为0.31，间接接触的感染风险概率系数为0.20。算例实验数据如表2所示。直接接触的感染风险概率系数为 0.31，间接接触的感染风险概率系数为0.20。表2客户位置及需求数据序号01234567891011121314151617181920 x2000365137714762903960357439423382799190713663386171324211658392334737471333614y20003446322634143575422346227273124310236452707270225983168363120031008348629901329qj069712479516254228313T18:04:008:55:008:40:008:36:008:25:008:56:008:15:008:10:008:24:008:35:008:10:008:40:008:19:008:23:008:22:008:57:008:15:008:55:008:47:008:06:00t18:10:009:01:008:46:008:42:008:31:009:02:008:21:008:16:008:30:008:41:008:16:008:46:008:25:008:29:008:28:009:03:008:21:009:01:008:53:008:12:00t28:14:009:05:008:50:008:46:008:35:009:06:008:25:008:20:008:34:008:45:008:20:008:50:008:29:008:33:008:32:009:07:008:25:009:05:008:57:008:16:00T28:20:009:11:008:56:008:52:008:41:009:12:008:31:008:26:008:40:008:51:008:26:008:56:008:35:008:39:008:38:009:13:008:31:009:11:009:03:008:22:00根据以上数据，在python中运用基于优先级三层编码的NSGA-原始算法和NSGA-改进算法进行数值实验，如图 3所示，一个点即代表了一个配送方案，F1为物流成本目标，F2为感染风险目标。帕累托点所代表的具体方案如表3所示。图3帕累托最优解集图表3中交付方式1.0对应送货到快递柜的末端配送方式，2.0对应送货到物业的配送方式，交付方式3.0对应送货上门的配送方式。其中送货上门和送货到快递的末端配送方式较为常用，送货上门为末端配送方式次数最少。可视化车辆路径选择图如图4所示。62计算机时代 2023年 第9期研究结果发现，NSGA-改进算法与 NSGA-原始算法在感染风险均为0.1449时，成本从580.50降到了500.74，降低了13.6%；NSGA-改进算法得到的方案3与方案4在和NSGA-原始算法的方案相比，改进算法的方案能得到更小的物流成本和更低的感染风险。4 结束语在后疫情时代，送货上门和送货到快递柜应为生鲜电商平台较为常用的末端配送方式，送货上门既增加成本又增加感染风险并不提倡。生鲜电商平台必须根据实际情况平衡配送过程中物流成本、客户满意度和感染风险。此外，算例实验证明了模型及算法的有效性，也证明了改进算法的优越性。参考文献(References):1 蒋俊,申贵成,王诗佳,等.基于强化学习的物流配送路径优化J.统计与决策,2021,37(18):185-188.2 Wu J,Li YY,Zhang W.ReRec:A Divide-and-ConquerApproachtoRecommendationBasedonRepeatPurchaseBehaviorsofUsersinCommunityE-CommerceJ.Mathematics,2022,10(2):208.3WangDQ,YangYT,WangYH.OptimizationofDistributionPathconsideringCostandCustomerSatisfactionunderNewRetailModesJ.Journalof表3具体方案结果方案12345交付方式选择1.0,1.0,2.0,2.0,1.0,2.0,2.0,2.0,2.0,2.0,1.0,2.0,1.0,2.0,1.0,1.0,2.0,2.0,2.0,1.01.0,1.0,2.0,2.0,1.0,2.0,2.0,2.0,2.0,2.0,1.0,2.0,1.0,2.0,1.0,1.0,2.0,2.0,2.0,1.02.0,1.0,1.0,2.0,2.0,2.0,2.0,2.0,2.0,2.0,1.0,2.0,1.0,2.0,1.0,1.0,2.0,2.0,3.0,1.02.0,1.0,1.0,2.0,2.0,2.0,2.0,2.0,2.0,2.0,1.0,2.0,1.0,2.0,1.0,1.0,2.0,2.0,2.0,1.01.0,1.0,2.0,2.0,1.0,2.0,2.0,2.0,2.0,2.0,1.0,1.0,1.0,2.0,1.0,1.0,2.0,2.0,2.0,1.0物流成本（F1）500.74510.78529.96535.54603.69感染风险（F2）0.14490.14490.14200.13990.1399图4可视化路径图(下转第68页)63Computer Era No.9 2023对于每个子链中的相应工厂中的库存水平，逐步达成一致。此外，我们分析了整个系统就库存达成一致所需的时间。对于上述相同的供应链系统，初始库存水平从0-10随机抽样，而其他参数保持不变。通过重复该实验100次，工厂1和工厂2达成一致所需的时间相似，而工厂3达成一致的时间相对较长。显然，这是因为工厂3与市场直接相连，市场波动会影响其收敛时间。图8子链xi2库存水平图9子链xi3库存水平5 结束语在本文中，我们提出了一种在多智能体系统中仅通过增量状态实现一致性的新方法。该方法在通信拓扑满足一般连接性要求的条件下，引入每个智能体及其邻居的控制变量信息，作为更新其自身状态的控制输入。理论分析和数值模拟表明了该方法的有效性。同时，在供应链系统中采用所提出的方法来达成库存一致。另外，对于平衡的拓扑结构，也可以实现平均一致。但仍有一些问题尚未解决，首先，实际场景中的拓扑通常是动态的，这是未来应该考虑的问题。其次，能否放宽对初始条件的限制可能是一个新的研究方向。参考文献(References):1 DeGroot M H.Reaching a consensusJ.Journal of theAmerican Statistical association,1974,69(345):118-121.2 Jadbabaie A,Lin J,Morse A S.Coordination of groups ofmobile autonomous agents using nearestneighbor rulesJ.IEEETransactionsonautomaticcontrol,2003,48(6):988-1001.3 侯健,郑荣濠.随机分组策略下的分布式多智能体一致性J.控制理论与应用,2018,35(4):517-522.4 覃茜.基于多智能体的供应链系统在切换拓扑下的H一致性D.山西:山西大学,2017.5 高杉杉,刘永泽,王冰,等.基于切换拓扑的供应链系统库存H一致性C/中国自动化学会控制理论专业委员会（TechnicalCommitteeonControlTheory,ChineseAssociation of Automation）,中 国 自 动 化 学 会（ChineseAssociation of Automation）,中国系统工程学会（SystemsEngineering Society of China).第40届中国控制会议论文集（15）,2021:6.6 Farivar M,Zho X,Chen L.Local voltage control indistribution systems:An incremental control algorithmC/2015 IEEE international conference on smart gridcommunications(SmartGridComm).IEEE,2015:732-737.7 Carli R,Fagnani F,Frasca P,et al.Average consensus onnetworks with transmission noise or quantizationC/2007 European Control Conference(ECC).IEEE,2007:1852-1857.8 俞辉,蹇继贵,王永骥.多智能体有向网络的加权平均一致性J.微计算机信息,2007,192(5):239-241.Advanced Transportation,2021:9426659.4 Su JF,Zhang FT,Chen S.Path Optimization of FreshProducts Logistics Distribution under New Retail ModeJ.International Journal of Innovative Computing Informa-tion and Control,2022,18(2):511-523.5 詹红鑫,王旭坪,孙自来,等.基于邻域搜索的成品油多舱多目标配送路径优化算法研究J.系统工程理论与实践,2019,39(10):2660-2675.6 赖志柱,王铮,戈冬梅,等.多目标应急物流中心选址的鲁棒优化模型J.运筹与管理,2020,29(5):74-83.(上接第63页)CECE68