货车联合无人机的农村电商物流运输路径规划

褚衍昌，王雪婷，张 娜

（1.中国民航大学 经济与管理学院，天津 300300；2.石河子大学 经济与管理学院，新疆 石河子 832000）

1 引言

随着信息技术日趋成熟，农村电商快速发展，带动物流业发生了翻天覆地的变化。2019年农村网络零售额达1.7万亿元，同比增长19.1%；全国快递企业业务量累计达到635.2 亿件，同比增长25.3%。“互联网+”背景下，电商与物流是协同发展、共生共荣的复杂关系，但目前物流发展速度与电商发展速度不匹配，特别是农村电商物流与农村电商市场的发展不适应。农村物流末端配送具有客户点分散、单位面积物流需求量小、交通道路条件差等特点，使农村电商末端物流陷入“长物流链+低消费密度”的困境，面临“最初一公里”揽件和“最后一公里”配送难题[1-2]。

无人机具有能耗小、飞行速度快、可直线飞行、不受地面交通条件和地形的限制等优点[3]。因此无人机配送可降低物流配送成本和运输时间，使其在物流配送中的应用越来越广泛。国内外大型电商物流企业如亚马逊、DHL、顺丰、京东纷纷开展了末端物流无人机的研究和应用[4]。2020 年初爆发的新冠肺炎由于具有强大传染性，使得无接触配送受到了人们的广泛关注，促进了前沿末端物流配送工具如无人机、无人机车和配送机器人等的推广应用。民航局也下发通知为通用航空提供政策支持，并进一步推动了无人机在物流配送中的应用。但是由于无人机具有载重小、续航能力短等缺点，使得无人机不适合运输载重大、航程远的包裹。因此将无人机与货车结合起来进行物流运输，可以用货车载重大、运距远的优点弥补无人机的缺点[5]。

无人机和货车合作的运行模式分为四种，分别为无人机辅助货车运行、货车辅助无人机运行、无人机和货车独立运行、无人机和货车同步运行[6]。目前关于货车辅助无人机运行模式以及无人机和货车同步运行模式的研究较多。Murray 等[7]提出的无人机旅行商问题（traveling salesman problem with drone,TSPD）是较早关于无人机与货车合作进行物流配送的研究，采用无人机和货车同步运行的模式，研究目标是使配送时间最短。Ha 等[8]也进行了无人机和货车同步运行模式的研究，其研究目标是配送总成本最小，其中包括无人机和货车的等待成本。Chang等[9]研究了以时间最短为目标的货车辅助无人机的运行模式。林驿等[10]针对我国农村实际情况，提出城乡客运班车辅助无人机的配送模式，并加入客运班车的时间窗约束。随着电商和物流的发展，客户退换货需求越来越多，形成逆向物流，同时取送货的车辆路径问题逐渐受到广大学者的关注。周永等[11]研究了冷链物流同时送取货车辆路径优化问题。Karak等[12]研究了货车和无人机合作的同时取送货的车辆路径问题。段凤华[13]研究了带碳费约束的同时取送货车辆路径问题。现代人对于时间的管控更加严格，往往希望包裹能在时间方便时送达，针对此问题，有关带时间窗约束的车辆路径研究不断发展[14-16]。

但是已有研究主要针对卡车的同时取送货和带时间窗的车辆路径问题，本文在前人研究的基础上提出货车联合无人机的同时取送货和带软时间窗的车辆路径问题（Drone-Vehicle Routing Problem with Simultaneous Pickup-Delivery and Soft Time Windows，DVRPSPDSTW）。以末端物流运作总成本最小为研究目标，建立数学约束模型，采用遗传算法求解，以期解决农村电商物流面临的“最初一公里”揽件和“最后一公里”配送难题。

2 问题描述

货车联合无人机的同时取送货和带软时间窗的车辆路径问题（DVRPSPDSTW）描述如下：一个配送中心有多辆同车型货车和一架无人机为所负责区域的客户提供送货和取货服务，本文研究的是货车和无人机独立运行的模式，货车负责配送或收取运距远、质量重的包裹，无人机负责配送或收取运距短、质量轻的包裹，如图1所示。客户对于服务时间区域有一定要求，如果客户在要求的时间区域内被服务，客户将会对服务时间很满意，如果早于或者晚于要求的服务时间，客户可以接受服务，但物流企业需要接受一定的经济惩罚。DVRPSPDSTW的研究目的是如何使物流企业在“最初一公里”和“最后一公里”的运作总成本最低，运作总成本包括货车司机的人工成本、货车和无人机的运输成本以及时间窗惩罚成本。

3 模型构建

3.1 模型的一般假设

本文对DVRPSPDSTW问题进行如下假设：

（1）只有一个配送中心；

（2）有多个货车和一架无人机；

（3）货车采用同一车型；

（4）同一客户点，要先执行送货任务，再执行取货任务；

图1 货车联合无人机的运行模式

（5）送货和取货任务提前获知，不发生变更；

（6）不考虑货物体积因素；

（7）货车和无人机均匀速运行；

（8）配送货物和收取货物可以混装；

（9）采用更换锂电池方法解决无人机锂电池储能小的问题，所以充电时间忽略不计。

3.2 模型的参数设置

首先定义如下符号：

N={1,2,...,n}表示所有的客户节点；

N0={0,1,...,n}表示所有的出发节点；

N+={1,2,...,n+1}表示所有的到达节点；

V表示配送车辆集合，V=1,2,...,m；

D表示无人机航次集合，D=1,2,...,k；

dij表示客户i到客户j的路线距离；

lij表示客户i到客户j的飞行距离；

Qv表示车辆的最大载重；

Qd表示无人机的最大载重；

Dv表示车辆的最大行驶里程；

Dd表示无人机的最大航程；

Vv表示车辆的平均行驶速度；

Vd表示无人机的平均飞行速度；

ch表示单位时间人工成本；

bij表示车辆由客户i行驶至客j每公里产生的费用；

cij表示无人机由客户i飞行至客户j每公里产生的费用；

qi表示客户i的送货量；

pi表示客户i的取货量；

ai表示客户i约定的最早服务时间；

bi表示客户i约定的最晚服务时间；

qij表示运输工具从客户i到客户j时还需要配送的货物重量；

pij表示运输工具从客户i到客户j时已经收取的货物重量；

α1表示运输工具在ai之前到达客户i处开始服务的惩罚系数；

α2表示运输工具在bi之后到达客户i处开始服务的惩罚系数；

3.3 模型建立

根据以上符号和变量，货车联合无人机的农村电商物流运输路径规划问题可表示为如下模型：

式（1）是目标函数，表示最小化成本；式（2）表示货车从配送站出发并回到配送站；式（3）表示无人机从配送站出发并回到配送站；式（4）表示客户仅被访问一次；式（5）表示货车的装货总量不超过货车最大载重；式（6）表示无人机的装货总量不超过无人机的最大载重；式（7）表示送货量等于客户需要收货量的总和；式（8）表示取货量等于客户需要寄货量的总和；式（9）表示第v 辆货车行驶距离小于货车最大行驶里程；式（10）表示无人机飞行距离小于无人机最大航程；式（11）-式（14）表示货车和无人机的服务时间窗；式（15）-式（16）表示决策变量的取值范围。

4 算法设计

本文研究的DVRPSPDSTW 问题是传统VRP 问题的变体，对于这类NP-hard 问题，一般方法较难求解，由于遗传算法具有高效、鲁棒性强、不容易陷入局部最优等优点，所以本文采用遗传算法求解。遗传算法运算流程如图2所示。

4.1 染色体编码

图2 遗传算法流程图

遗传算法不能直接对问题参数进行处理，需要将这些参数转换成遗传算法可以识别的个体或者是染色体，这一过程称为编码。常用的编码方法包括二进制编码、浮点编码、自然数编码等。本文使用自然数编码，配送中心的编号是“0”，顾客编号是1-n的自然数，如染色体“05304210”表明有两条配送路线，分别是配送中心-客户5-客户3-配送中心；配送中心-客户4-客户2-客户1-配送中心。

4.2 初始化种群

初始化种群在遗传算法求解过程中扮演着重要的角色，种群规模大小会对遗传算法最终的运行结果以及运行效率产生重大影响。在种群规模较小时，会影响遗传算法的优化性能，一般情况下不太好，种群规模较大时可以降低算法陷入局部最优的概率，但是计算复杂程度和运行时间会增加。染色体长度不是很大时，种群规模的大小在10～200之间，对于比较复杂的问题，可根据具体情况适当增加种群规模。

4.3 适应度计算

适应度即种群中个体适应环境的能力，适应度值越大代表个体适应环境的能力越强，适应度函数的评价是选择操作的依据，它的设计会对遗传算法性能产生影响。本文的目标函数是成本最小，故适应度函数为目标函数的倒数。

4.4 选择操作

选择的目的是淘汰劣质个体，选择优质个体，本文采用轮盘赌选择法，其表达式为：

式中：fi为单个个体的适应度，NP 为种群规模。个体适应度值越大，被选择的概率越大，优质个体基因遗传到下一代的机会越大。

4.5 交叉操作

本文采用两点交叉法，从父代选择两个染色体，从每条染色体中选择两个点作为交叉点，将两条染色体对应位置交叉点的字符串交换，便可得到两个子代染色体。

4.6 变异操作

变异操作是模仿生物进化中基因突变的现象，从种群中选择若干个体，改变个体中的某些基因值，变异的概率一般很小，取值范围为0.001～0.1，如果变异率太大，会破环优质个体。

5 算例分析

5.1 算例数据

目前，无人机的优势在偏远农村地区能够得到更好体现，因此选择贵州省某农村地区作为本文货车联合无人机运输模式的研究地区，本区域有2辆货车和一架无人机，为20 个客户提供送货或者取货服务。具体模型参数见表1。

表1 模型参数

通过百度地图测得货车行驶距离以及无人机飞行距离，无人机飞行距离采用两点之间的直线距离，各个客户点的取货量、送货量以及时间窗随机生成，配送时间设置为早上九点至下午五点，以min 计算，早上九点设为0min,下午五点设为480min。货车行驶距离见表2，无人机飞行距离见表3，取送货信息见表4。

5.2 MATLAB求解

本文采用MATLAB R2019b软件进行编程，其中种群规模设为200，最大迭代次数设为300，交叉概率为0.9，变异概率为0.1。迭代55次时算法收敛，遗传算法的迭代情况如图3所示。

经过多次程序运行，货车联合无人机的运输路径规划结果见表5，求得最低总成本为1 995.73 元，无人机服务对象为载重和航程在其承受范围之内的客户，剩余客户由货车负责服务。大部分服务时间都在客户要求的时间窗范围内，极大地提升了客户服务水平，并在配送过程中完成取货任务。以上结果表明DVRPSPDSTW 模式能够在物流运输中应用并有效完成运输任务。

表2 配送站与各客户点以及各客户点之间的货车行驶距离

表3 配送站与各客户点以及各客户点之间的无人机飞行距离

表4 顾客取送货信息

图3 目标函数迭代次数

表5 DVRPSPDSTW运输路径规划结果

为了表明DVRPSPDSTW 运输方式的优越性，本文对单独使用货车运输的方式进行求解，货车运输路径规划结果见表6。

表6 VRPSPDSTW运输路径规划结果

通过对比表5和表6的求解结果，可知仅使用货车运输的最低总成本为2 614.05元，而DVRPSPDSTW模式最低总成本为1 995.73 元，相比只使用货车运输成本降低了23.65%。这表明无人机在物流运输方面有很大的优越性，“货车+无人机”的运输方式可有效降低物流运输成本。

不同区域的客户对于物流服务品质的要求会有一些差别，经济发达地区的客户对配送时间的敏感程度较高，经济较差地区的客户对配送时间窗的容忍程度较大。本文针对客户对配送时间敏感程度的不同，从农村电商物流利润最大化的角度出发，对时间敏感程度较低地区的客户，可以将提供时间窗约束的服务去掉，降低物流企业成本。不考虑时间窗约束的“货车+无人机”运输路径规划结果见表7。

表7 DVRPSPD运输路径规划结果

时间窗约束在运输路径规划中会产生很大影响，通过对比表5 和表7 的求解结果可知，不考虑时间窗约束的成本为1 677.57元，无人机飞行航次减少为3 次，成本降低了15.94%。故从利润最大化角度考虑，针对不同地区的客户，可采用不同的运输模式。

为了研究不同无人机载重对本文所提出运输模式成本的影响，对3-13kg 不同无人机载重的运输模型进行求解，模型运行结果见表8，结果表明无人机载重为9kg 时运输总成本最小。这启示物流企业在购买或者租赁末端物流无人机时，可根据用户需求量选择合适载重的无人机型号，有效降低末端物流运作总成本。

表8 不同无人机载重的运输规划结果

6 结语

本文分析了农村电商物流面临“最初一公里”揽件和“最后一公里”配送成本高的难题，并针对该问题提出了一种新的末端物流运输模式，即货车联合无人机的同时取送货和带软时间窗问题（DVRPSPDSTW）的运输模式。以末端物流运作总成本最小为目标建立数学模型，采用遗传算法求解，结果表明DVRPSPDSTW 模式可以有效完成物流运输任务，和传统的货车运输模式相比，该模式能够有效降低物流运作总成本。末端物流成本高一直是困扰物流企业向下延伸服务的难题，本文提出的运输模式显著降低了末端物流成本，为物流企业进一步拓展农村市场提供了解决方案。虽然本文对农村电商物流面临的难题提出了一种新的解决方案，但是只考虑了在时间窗约束和同时取送货情况下货车和无人机独立运行的一种模式，未来可考虑货车和无人机合作的其他模式，应对多种末端物流运输情境。