配送车与无人机的农村物流配送路径优化仿真

许文鑫，张 敏，2，熊国文

(1. 西南交通大学机械工程学院，四川 成都 610031；2. 轨道交通运维技术与装备四川省重点实验室，四川 成都 610031)

1 引言

随着经济的快速发展，物流需求加快，农村物流市场不断扩大，据中国物流与采购联合会发布数据显示，从2015年到2019年农村业务量指数上升了589.54。许多物流企业已开始布局农村市场，但因我国农村物流配送区域分散、投放难度大和配送成本较高，导致大多数的农村物流配送仅局限于乡镇甚至是县城，处于一级配送状态并没有直接面向农村客户，因此农村物流总体体验较差。近年来，随着我国农村物流需求量的不断上升，农村物流配送末端的“最后一公里”配送问题得到越来越多的关注，探索农村物流配送模式成为降低农村物流配送延误率和物流成本的关键方向。

随着无人机技术的不断发展，国内外企业纷纷将无人机投入物流领域，其中包括亚马逊的“空中仓库”、顺丰公司的“三段式”空运以及UPS的无人机+卡车模式。他们认为通过“运输工具+无人机”协同配送，能够较好解决“最后一公里”配送的难题，以达到降低配送延误率和成本的目的。近年来，许多国内外专家对物流无人机的运用进行了一系列研究，他们分别针对各个行业对无人机的配送前景和配送系统进行了讨论并设计出相关优化调度方案与路径规划模型，同时也对无人机物流配送的成本进行了系统的分析。尽管物流无人机具有速度快、成本低和环保节能等优点，但是其存在电池容量有限的不足，进而导致物流无人机不能长期飞行，限制了物流无人机的配送范围。为此，相关学者提出了一种新型配送模式即“配送车+无人机模式”，如周浪提出在农村地区利用无人机和配送车联合进行物流配送，物流无人机对各个需求点进行多点配送后返回配送中心或配送车进行充电和补货操作，配送车只需服务距配送中心较近的配送点，极大程度的缩短了农村物流配送的时间和距离。但由于农村各地区地形不同以及需求量的差异，并不是所有农村地区都能找出合适配送车停放点，其势必会影响整个运输过程的路径以成本。

路径优化问题一直是国内外学者研究的热点，许多学者对其进行了深入研究，栾兆亮、Xing、Cailei等分别对地铁路线、公共交通、船舶路线等不同交通方式建立模型，并应用相关算法进行了求解。Xu等提出了一种改进的多目标粒子群优化算法对无人机的路径进行优化。杨珺等设计出禁忌搜索-改进Clarke-Wright节省的两阶段启发式算法来求解电动汽车物流配送系统的换电站选址与配送路径优化问题。Ying等为了控制温泉旅游的时间和运输成本，提出了一种天然温泉旅游的沿海路线规划模型，对关键路线进行规划。虽然许多学者已经对无人机配送进行了一系列研究，也将路径优化模型运用到基础建设、物流运输等方面并解决了相关行业的路径规划问题，但针对农村物流的无人机快递配送的研究相对较少。

本文将结合农村的物流特征设计了一种拥有配送车暂时停放点的“配送车+无人机”路径规划模型以及相关物流配送策略，通过k-means算法对配送系统中的配送中心以及配送车暂时停放点的位置进行确定，利用改进遗传算法实现无人机和配送车的路径优化，最后通过实例验证整个物流配送模式的可行性。物流企业可以根据实际情况来确定配送中心和配送车暂时停放点的位置以及配送车和无人机的路径，使整个配送系统的成本最低。

2 问题描述

基于拥有配送车暂时停放点的“配送车+无人机”配送模型，假设配送中心拥有一架载重为30kg、续航30km的物流无人机与一辆载重500kg、续航50km的配送车，对某县城农村区域内需求量不同的L个村落进行快递配送。整个系统包含两种配送模式，第一种是物流无人机单独进行配送，物流无人机从镇级配送中心A出发为各个村落固定接收点L进行多点配送，配送完成后返回配送中心A补货或充电(如图1(a)所示)。但由于无人机载重能力以及续航能力的限制，并不能一次性完成所有村落的配送。因此提出第二种配送方式——配送车携带物流无人机进行配送，首先配送车从镇级配送中心A出发，按照规划好的线路到达配送车暂时停放点T，然后无人机从配送车暂时停放点T出发按照规划好的路线为各个村落固定接收点L进行配送，配送完成后返回配送车暂时停放点T补货或充电，“配送车+无人机”配送流程如图1(b)所示。本文将针对农村物流配送环境，对“配送车+无人机”配送系统进行构建，并设计拥有配送车暂时停放点的“配送车+无人机”路径优化模型，实现配送车和无人机的路径优化。

图1 “配送车+无人机”配送模式

问题假设如下：

1)配送中心只有一辆配送车和一架无人机，整个乡镇级配送系统只有1个配送中心，多个配送车暂时停放点，多个村落固定接收点；

2) 每一个村落固定接收点只能进行一次配送；

3)物流无人机可以为多个的村落固定接收点进行配送，物流无人机只能返回其出发的配送车暂时停放点或者配送中心；

4)物流无人机可以从配送中心出发为村落固定接收点配送，也能在配送车达到某配送车暂时停放点后再为村落固定接收点配送；

5)配送车和无人机运输成本主要由配送距离相关的费用构成。

3 模型构建

在“配送车+无人机”配送模式下，将配送系统的运输成本最低、配送的路径总距离最短、完成所有配送任务的时间最短作为整个路径优化问题的目标。配送车运输产生的相关费用为燃料消耗成本、折旧费用、维修费用。无人机配送产生的相关费用为无人机能耗费用、电池维护费用、折旧费用、维修费用，具体项目及计算方式均采用单位距离费用*路线长度。模型参数分别代表的含义如表1所示。

表1 参数定义

针对农村的特殊地形与村落分布情况，本文将分别对物流无人机单独配送和配送车携带无人机配送两种方式进行建模和分析。在进行建模计算时，首先通过运输方式决策变量l将配送点分为由配送车辆携带物流无人机进行配送的村落固定接收点集合E和由物流无人机单独进行配送的村落固定接收点集合F。在整个配送过程，配送车只能从配送中心出发并且只能在配送车暂时停放点暂时停留，而物流无人机的出发点既能是配送中心也能是配送车暂时停放点。

E

={

i

│

l

=1，

i

∈

L

}

(1)

F

={

i

│

l

=0，

i

∈

L

}

(2)

集合H′ 表示的是通过配送车携带物流无人机进行配送的物流无人机的集合：

(3)

H是从配送车暂时停点T出发的物流无人机集合

(4)

根据上述分析，建立拥有暂时停放点的“配送车+无人机”模型如下所示

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

x

=0，

i

∈

L

，∀

j

，

(16)

l

=0或1，∀

i

，

(17)

x

=0或1，

i

∈(

A

∪

T

)，

j

∈(

A

∪

T

)

(18)

y

=0或1，∀

i

，∀

j

，∀

h

，

(19)

上述模型中，式(5)表示的是整个模型配送成本最小化的目标函数。式(6)、(7)表示每个村落固定接收点只能由物流无人机进行一次配送。式(8)、(9)是为了确保物流无人机配送路径的连贯性。式(10)是为了确保配送车从配送中心出发，经若干配送车暂时停放点后回到最初的配送中心。式(11)表示在物流无人机单独进行配送的情况下，物流无人机从配送中心站出发，经若干村落固定接收点后回到出发的配送中心。式(12)表示在配送车携带物流无人机进行配送时，物流无人机从配送车暂时停放点出发，经若干村落固定接收点后回到出发的配送车暂时停放点。式(13)表示物流无人机的实际载重小于物流无人机的最大载重。式(14)表示配送车的实际载重小于配送车的最大载重。式(15)表示物流无人机配送路线的长度小于物流无人机的续航能力的约束。式(16)、(17)、(18)、(19)表示本模型中所有变量的取值范围。

4 路径优化方法设计

基于拥有配送车暂时停放点的“配送车+无人机”配送模型，首先需要通过

k

-

means

算法将村落固定接收点分为无人机单独配送和配送车携带无人机进行配送两种类型并对配送中心和配送车暂时停放点的位置进行确定。其次，通过遗传算法分别对配送车和无人机的配送路线进行规划，模型的具体流程如下图2所示。

图2 “配送车+无人机”路径规划模型步骤

由于

k

-

means

算法在解决聚类问题上简单、快捷，处理大型数据集具有可收缩性和高效性，因此将用其确定配送中心和配送车暂时停放点的位置以及对村落固定接收点进行分类。其中在计算对象之间的距离时选取欧式距离，

d

(，)越小二者越相似，计算公式如(20)所示。

(20)

在聚类结束后将运用平方误差准则函数对聚类后的性能进行评估，E表示所有对象的平方误差和。计算公式如(21)所示。

(21)

其中簇中心的计算公式如(22)所示。

(22)

关于农村“配送车+无人机”路径规划问题，本文将运用遗传算法对配送车与无人机的路径进行求解。它的具体步骤有交叉、变异、进化、分裂一系列操作。其中变异操作是随机选取两点对换其位置，通过产生随机的两个数，如m=4，m=7，将其对换，具体过程如下图3所示。

图3 变异操作

交叉操作采用部分映射的方式来进行，将父代分成A、B两组，每一组重复以下过程：产生两个随机数m=4，m=7，对两个位置中间的部分进行交叉，交叉后有冲突的位置采用部分映射的方式进行消除，其过程如下图4所示。

图4 交叉操作

分裂操作是为了使无人机与配送车的路径更贴合现实，通过分裂无人机和配送车能够从固定点出发返回固定点并在货物配送完后返回对应的地点进行补给，如在m=4，m=7时进行补给，具体步骤如下：首先从初始种群提取路径数据，然后通过计算确定代插入的村落固定接收点插入返回点形成新的种群。过程如下图所示，图5中1为返回点。

图5 分裂操作

5 实际算例分析

以四川省某乡镇为例，对农村“配送车+无人机”配送问题的实际情况进行分析，并在收集的数据基础上进行路径规划的应用。本文选取的乡镇共有12个村落，地形多为山地丘陵地带，将其作为研究对象具有一定的代表性。为了方便计算，下面将以北纬32°10′26

.

89″，东经106°18′34

.

93″ 的碾子梁作为坐标原点，碾子梁以北为

Y

轴以东为

X

坐标建立坐标系，以下各个坐标图均以此为参照。为了确定配送中心和配送车暂时停放点的位置，分别在

k

=1、

k

=2、

k

=3、

k

=4时运行

K

-

means

算法，求解出

k

=1时配送中心的坐标为(7

.

3463，8

.

2584)如图6所示，以及在

k

=4时配送车暂时停放点的坐标分别为(10

.

7892，9

.

2454)、(4

.

4560，3

.

8244)、(6

.

3156，7

.

8939)、(7

.

8243，12

.

0698)如图7所示。

图6 配送中心求解

图7 配送车暂时停放点求解

通过

Google

地图，本文将求解出的结果与实际路线相结合，并对配送车暂时停放点和配送中心的位置进行整合，将(6

.

9273，8

.

8970)确定为配送中心并取消暂时停放点4。配送车暂时停放点的分类如下表2所示。此外还计算出各个点之间的距离，暂时停放点之间配送车的公路距离如表3所示，村落固定接收点之间无人机的航线距离如表4所示。

表2 配送车暂时停放点分类

表3 配送车公路距离

表4 无人机航线距离

在整个“配送车+无人机”配送系统，配送车的作用是将货物与无人机运输到配送车暂时停放点，无人机的作用是对分布在暂时停放点周围的小货件物品进行配送。下面将通过遗传算法对配送车和无人机的路径进行求解。在整个过程中，假设各个配送车暂时停放点货物重量分别为300kg、200kg、150kg，假设各个村落固定接收点货物重量如表5所示，计算出配送车和无人机的路径如图8、9所示。

图8 配送车路径图

从图8可以看出配送车的路线为：1—>3—>4—>1—>2—>1，即配送中心—>配送车暂时停放点3—>配送车暂时停放点2—>配送中心—>配送车暂时停放点1—>配送中心，总路程为28.78km，配送总成本为22.4484元。从图9可以看出，在整个配送过程，无人机分别从1、5、9、13这些点出发(其中5为配送中心其余点均为配送车暂时停放点)，根据聚类的结果与求解的路径进行配送，最后返回对应的配送车暂时停放点，具体计算结果如表6所示，无人机飞行总路程33.9623km，总成本15.9623元。

图9 无人机路径图

表5 假设各村落需求量表(单位：kg)

表6 无人机路径求解

6 结论

农村物流配送一直是物流企业面临的一大难题。本文通过对农村现有的物流配送模式进行分析，在传统配送网络的基础上考虑了物流无人机的载重能力和续航能力，将无人机与配送车有效结合，提出了拥有配送车暂时停放点的“配送车+无人机”农村物流配送模式，并设计出无人机单独配送和配送车携带无人机进行配送两种模式，能够有效解决农村“最后一公里”配送难题。在整个路径规划模型中，首先通过k-means算法分别对配送车暂时停放点和配送中心的位置进行确定并将村落固定接收点进行分类处理；然后通过遗传算法分别对配送车的路径以及物流无人机的路径进行规划，使整个系统的成本最低；最后通过实际算例验证了本模型的可行性。本文的物流模型并没有考虑无人机在飞行过程中的风速影响，以及恶劣天气的应急处理方式，为使整个配送模式在应用中更加具有实际意义，在今后的研究中会考虑风速等自然条件的影响，设计出更加符合实际的配送模式。