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

陆心航 徐宗露 刘文

摘  要： 在商品供应链中，生鲜配送成本过高是亟需解决的问题。本文考虑疫情的感染风险对生鲜配送路径优化问题展开研究，以最小化物流成本和最小化感染风险为目标构建模型，设计优先级三层编码方法，使用NSGA-Ⅱ求解问题。在此基础上，增加逆序邻域策略改进NSGA-Ⅱ，提高算法的收敛性。最后进行数值实验，验证了模型的可行性以及改进算法的优越性。

关键词： 后疫情时代； 生鲜电商； 车辆路径问题； NSGA-Ⅱ； 客户满意度

中图分类号：C93;TP18          文献标识码：A     文章编号：1006-8228（2023）09-59-05

Research on vehicle routing problem considering the infection risk of

terminal distribution mode and consumer satisfaction

Lu 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， considering the infection risk of the epidemic， the optimization of fresh food distribution route is studied. A model with the objectives of minimizing logistics cost and infection risk is constructed. A priority three-layer coding method is designed and NSGA-Ⅱ is used to solve the problem. On this basis， the inversion neighborhood strategy is added to improve the convergence of NSGA-Ⅱ. The feasibility 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

0 引言

后疫情時代，居民使用生鲜电商app频次增加，但配送成本过高一直都是亟需解决的问题，末端配送路径优化是降低成本的重要手段[1]。除成本问题外，满意度也是十分重要的问题，它影响着客户重复购买的意愿[2]。客户满意度大多体现在时间窗上[3]，运输时间过长也会影响生鲜食品的货损程度。在时间满意度、食品货损程度等约束条件下，适当的规划行车路线，实现成本控制，这是车辆路径问题的重要研究内容。

在生鲜配送的路径问题研究中，余海燕等以配送距离最小为目标，构建生鲜外卖即时配送路径优化模型[4]。物流成本最小化也是生鲜配送的重要问题[5]。在生鲜配送的多目标问题中，詹红鑫等人以配送成本最小，路径风险最小为目标构建路径优化模型[6]。

由于感染风险是疫情背景下所特有的，因此本文在考虑末端配送方式满足客户满意度前提下，以最小化物流成本和最小化感染风险为目标构建模型，运用改进的NSGA-Ⅱ算法求解该问题，通过算例实验来验证算法的有效性与可行性。

1 问题描述及模型构建

1.1 问题描述

本文研究后疫情时代生鲜配送车辆路径优化问题，定义[G=（V，E）]为一个完备的无向图，配送中心用[{0}]表示，客户集合用[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]种交付方式所需要的单位时间成本；

[C'l]：表示使用第[l]种交付方式所需要的固定成本；

[Cg1]：表示使用快递柜的固定成本；

[dij]：表示从点[i]到[j]之间的距离；

[A]：表示配送过程中单位距离重量成本；

[qj]：表示第[j]个客户的货物需求量；

[tj]：表示到达第[j]个客户点的时间；

[V]：表示车辆行驶速度；

[∆tjl]：表示配送员配送生鲜的服务时间，包括交付时间及等待时间；

[t1，t2]：表示客户的期望时间窗；

[T1，t1）]，[t2，T2]：表示客户可接受时间窗；

[α]：表示商品提前送达时客户对时间的敏感系数；

[β]：表示商品延迟送达时客户对时间的敏感系数；

[μ]：表示客户满意度的最低要求水平；

[yj']：表示客户可容忍的最高货损率；

[Sjl]：表示客戶[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=1mCk]  ⑴

[CB=i=0nj=1nk=1mdij∙xijk∙A∙qj] ⑵

[CC=j=1n（C'l+Cl∙∆tjl）]  ⑶

其中，

[C'l=Cg1 ，  l∈g1  0，     l∈g2，g3]  ⑷

[∆tjl=1，                                               l∈g1，g212π∙σ∙exp-x-μ22σ2 ，l∈g3]  ⑸

末端配送方式感染风险模型：本文假设城市总人数为[N]，城市中尚未采取隔离措施的新冠疫情肺炎病毒携带者人数为[N+]，人们在城市中的感染概率为[P]。客户与配送员的感染概率如下所示：

[Pkstart=N+N]  ⑹

[Pjstart=N+N]  ⑺

[Pjend=Pjstart+φl∙Pki∙1-Pjstart∙xijk]  ⑻

[Pkj=Pki+ωl∙Pjstart∙1-Pki∙xijk]  ⑼

[P*=k=1mPk0+j=1nPjend]  ⑽

其中，[Pkstart]表示配送员初始感染概率，[Pjstart]表示客户初始感染概率，[Pk0]表示配送员回到配送中心感染概率，[Pjend]表示客户[j]拿到货物后的感染概率，[Pki]表示配送员在点[i]的感染概率，[Pkj]表示配送员在点[j]感染概率。

客户满意度模型：客户的满意度会收到收货方式的影响。具体交付方式满意度和时间满意度设置表示如下：

[Sjl=b，              l∈g1b-δc，    l∈g2a ，              l∈g3]  ⑾

[Sj（tj）=tj-T1t1-T1α， tj∈T1，t11，                  tj∈t1，t2T2-tjT2-t2β， tj∈t2，T20，                 else]  ⑿

VRPTW模型：根据物流成本模型、感染风险模型和客户满意度模型，以客户满意度作为约束条件，以最小化物流成本和最小化感染风险为目标构建模型如下：

[F1=MinCA+CB+CC]  ⒀

[F2=Min（k=1mPk0+j=1nPjendm+n）]  ⒁

s.t.：

[S=j=1nSj（tj）+j=1nSjl2n>μ]  ⒂

[j=1nxijk.qj≤Q ，∀k∈1，2，…，m]  ⒃

[yj=Y∙tj-t0<yj']  ⒄

[j=1nx0jk=i=1nxi0k=1，  ∀k∈1，2，…，m]  ⒅

[j=1nxijk=i=1nxijk=1，  ∀k∈1，2，…，m]  ⒆

[i=1nxihk-j=1nxhjk=0，  h∈n，  ∀k∈1，2，…，m]  ⒇

式⒀表示物流成本最小化；式⒁表示感染风险最小化；式⒂是客户满意度约束；式⒃是车载容量约束；式⒄是生鲜货损率约束；式⒅表示配送车辆始于配送中心，终于配送中心；式⒆表示每个消费者仅被一个配送员服务；式⒇是保证路线的连贯性。

2 基于优先级三层编码改进的NSGA-Ⅱ算法

目前，遗传算法已经有了较为成熟的研究。NSGA-Ⅱ与NSGA相比，复杂度更低，求解速度更快，收敛性越好。因为本文使用了NSGA-Ⅱ求解感染风险和成本最小化的双目标问题，图1为NSGA-Ⅱ改进算法流程。

2.1 基于優先级编码方法简介

基于优先级编码方法相较于传统编码方式有如下优点：①相对传统的编码方式，该方法降低了决策变量维度，提高了求解效率；②通过解码获得的路径均为从起点到终点的完整路径。具体编码过程如表1所示。

2.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为[0→10→8→6→3→0]。客户点处的基因全部逆序。

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。

根据以上数据，在python中运用基于优先级三层编码的NSGA-Ⅱ原始算法和NSGA-Ⅱ改进算法进行数值实验，如图3所示，一个点即代表了一个配送方案，F1为物流成本目标，F2为感染风险目标。帕累托点所代表的具体方案如表3所示。

表3中交付方式1.0对应送货到快递柜的末端配送方式，2.0对应送货到物业的配送方式，交付方式3.0对应送货上门的配送方式。其中送货上门和送货到快递的末端配送方式较为常用，送货上门为末端配送方式次数最少。可视化车辆路径选择图如图4所示。

研究结果发现，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-ConquerApproach to Recommendation Based on Repeat Purchase Behaviors of Users in Community E-Commerce[J]. Mathematics，2022，10（2）：208.

[3] Wang DQ， Yang YT， Wang YH. Optimization of Distribution Path considering Cost and Customer Satisfaction under New Retail Modes[J]. Journal of Advanced Transportation，2021：9426659.

[4] Su JF， Zhang FT， Chen S. Path Optimization of Fresh Products Logistics Distribution under New Retail Mode[J].International Journal of Innovative Computing Information and Control，2022，18（2）：511-523.

[5] 詹红鑫，王旭坪，孙自来，等.基于邻域搜索的成品油多舱多目标配送路径优化算法研究[J].系统工程理论与实践，2019，39（10）：2660-2675.

[6] 赖志柱，王铮，戈冬梅，等.多目标应急物流中心选址的鲁棒优化模型[J].运筹与管理，2020，29（5）：74-83.