基于无人机-配送车联合配送的优化算法研究

熊兴隆，刘 佳，李 猛，马愈昭

1.中国民航大学 天津市智能信号与图像处理重点实验室，天津 300300

2.中国民航大学 电子信息与自动化学院，天津 300300

3.中国民航大学 民航空管研究院，天津 300300

在物流配送领域，传统单配送车送货存在配送成本高、效率低、延误高、环境污染等问题。随着无人机在物流领域受到越来越多的关注，提出一种新型交付概念——无人机联合配送车协同配送包裹。目前亚马逊、德国邮政、谷歌等企业已经尝试将无人机应用在其业务中以降低配送成本缩短配送时间[1-2]。无人机由于其移动消耗能量少，不受道路网络交通拥堵影响，速度快等特性，相比传统配送车送货而言可降低交付成本缩短交付时间，但考虑其载荷及续航能力问题，配送车又显得更有优势[3-5]。由于二者的互补性，将无人机整合到现有的“最后一英里”交付模式中可能产生协同效益。因此引发了“无人机-旅行商”问题（Travelling Salesman Problem with Drone，TSP-D）[6]针对无人机与配送车联合路径的研究。

2015年，Murray等人[6]首次将无人机引入TSP研究，引入混合线性规划公式求解两类问题模型，提出了一种基于先分群再排路线的启发式算法解决了10个节点的案例，该算法目前只能解决小规模节点案例。Agatz 等人[7]引入一个整数规划公式，提出了基于局部搜索和动态规划的先排路线再分群的两种启发式算法，同样只适用于小于10个节点的案例。Bouman等人[8]基于动态规划提出了一种求解TSP-D 的精确方法，能更快找到10个节点问题示例的最优解决方案。Sacramento等人[9]研究了TSP-D 的一个新变体，其中有多辆配送车存在，并对Murray等人[6]的混合线性规划公式进行了调整，提出了自适应大邻域搜索算法。

综上，由于TSP-D 是TSP 一个新变体，目前较少文献研究。为进一步改进TSP-D 的数学模型[10-12]，本文提出了一种新型优化迭代算法对该问题进行求解，在均匀和聚集两类示例下随机生成10个和11个节点分析验证实验结果，并与传统TSP 解进行对比，对算法的有效性进行验证。

1 TSP-D模型构建

1.1 TSP-D问题描述

无人机联合配送车的交付方式具体过程为：配送开始前，工作人员为无人机和配送车装载好货物，无人机停靠在配送车车顶。配送开始，无人机从车顶发射，二者分别前往各自客户节点配送货物。由于无人机的装载能力与电池寿命有限，其每访问完一次客户后需与配送车汇合，装载下一个客户的包裹并刷新电池。因此，客户节点可分为三类：卡车节点、无人机节点以及汇合节点。

无人机和配送车是否能同时到达汇合节点取决于二者在各自路径上的耗时。三种情况，当配送车先到达汇合节点时，需在节点处等待无人机到来，等待时间为Wt；若无人机先到达汇合节点或者二者同时到达汇合节点，配送车只需沿其路径继续行驶无需等待即Wt为0。因此，整个交付时间可看作配送车配送时长Ttruck与配送车等待时长Wt之和。TSP-D问题要求无人机和配送车的路线必须在仓库开始和结束，目标是最小化交付时间。

如图1 说明了这种交付方式。直线代表配送车路径，虚线代表无人机路径。0 点代表仓库，节点2、5、3、4、1、10是配送车服务的客户节点，无人机服务的客户节点为7、8、9、6，节点5、4、10为二者汇合节点。其中配送车路径为0-2-5-3-4-1-10-0，无人机路径为0-7-5-8-4-9-10-6-0。如图2为传统单配送车交付方式的模型。

图1 TSP-D问题模型Fig.1 TSP-D problem model

图2 TSP问题模型Fig.2 TSP problem model

1.2 约束条件

（1）无人机载重有限。无人机每访问完一个客户节点后需返回配送车拿取下一件包裹并刷新电池，接着再访问下一个客户节点，即无人机配送完货物的下一个节点总是配送车节点。如图3所示，0点为仓库，圆形代表配送车，方形代表无人机。

图3 无人机路径示例Fig.3 Drone path example

（2）无人机续航时间有限。无人机每次从起飞到降落至配送车这段路径耗时需在无人机的电池续航时间之内。如图3 中的各段无人机路径0-6-2，2-7-5……每段路径耗时都需小于等于无人机的最大续航时间才能完成配送任务。

（3）无人机与配送车汇合节点不能是上一个汇合节点之前的节点，即不能返回至配送车路过的节点。如图4 所示配送车路径为0-1-2-3-0，无人机路径的第一段为0-4-2，第二段为2-5-1，由于配送车与无人机是同步运动，二者在时间上也是同步的，显然无人机的第二段路径不成立，配送车此时已路过节点1，无人机若返回节点1则无法降落在配送车上。

图4 不满足条件的无人机路径示例Fig.4 Example of drone path that does not meet criteria

（4）无人机不允许重复访问客户。

（5）配送车不允许重复发射或接收无人机。

（6）总配送时间最短。

1.3 符号说明

（1）集合：

C表示客户节点集合；

R表示配送车路径集合（在第一阶段确定）；

D表示分配给无人机的客户节点集合（在第一阶段确定）；

P表示无人机路径集合（在第二阶段确定）。

（2）参数：

N表示客户节点个数；

T表示无人机与配送车联合配送总耗时；

EN表示无人机续航时间；

a、b、c表示节点位置；

r表示路径；

pk表示配送车路径中的节点k；

ti表示配送车到达i处的耗时；

di表示无人机到达i处的耗时。

（3）决策变量：

nar表示路径r中a节点若为无人机服务节点即为1，否则为0；

sar表示若路径r从节点a出发即为1，否则为0；

ecr表示若路径r在节点c结束即为1，否则为0；

xr表示若路径r为无人机路径即为1，否则为0；

yab若配送车从a行驶到b(a≠b)即为1，否则为0；

xabc表示若无人机路径从a发射，在c降落，途中访问b即为1，否则为0。

1.4 模型建立

针对TSP-D 问题建立以下数学模型：公式（1）为目标函数，表示无人机与配送车联合配送的总耗时最短；式（2）计算联合配送的总耗时，分为两部分：第一部分为配送车配送时长；第二部分为配送车等待时长。小括号中表达式表示配送车在发射和回收节点间的耗时，大括号中表达式表示发射和回收节点a、c间配送车与无人机的时间差，即配送车等待时长；式（3）表示无人机不能在返回配送车之前被重复发射，如无人机在a点被发射，在c点被回收，假设k点为a与c之间的点，那么无人机不允许在k点被再次发射或回收；式（4）表示若无人机从a点发射在c点被回收，则配送车在访问c之前需先访问a；式（5）表示若无人机从a点发射在c点被回收，则a与c为分配给配送车的客户点；式（6）表示若无人机从a发射在c被回收，则无人机耗时需在无人机续航时间内；式（7）表示每个客户节点只能被无人机访问一次；式（8）表示一个节点作为发射节点至多一次；式（9）表示一个节点作为回收节点至多一次；式（10）至式（15）表示二进制决策变量。

2 TSP-D求解方法

2.1 求解算法

TSP-D属于NP难题（Non-deterministic Polynomialhard，NP-hard），由于其非确定性，传统方法难以快速找到最优解，为缩小搜索范围，在合理时间内得到最优解[13-15]，故采用一种新型优化迭代方法求解问题。

本文将问题分为两阶段：第一阶段确定配送车路径；第二阶段确定无人机路径。由于配送车无需考虑重复装载货物等问题，首先确定配送车路径。不在配送车路径上的节点即为无人机配送节点，因此第一阶段解决了配送车路径和客户节点分配两个问题。第二阶段，固定第一阶段配送车路径和无人机配送节点，从配送车节点中确定满足约束的汇合节点，得到无人机配送路线。方法如图5、图6所示，具体如下：

图5 第一阶段固定配送车路线Fig.5 Fixed truck route in the first stage

图6 第二阶段确定无人机路线Fig.6 Determined drone route in the second stage

第一阶段，生成所有可能的配送车路径。为确定配送车路径，首先需要确定可能的配送车节点。从所有节点中去除可能与配送车组合的最多个无人机节点，剩余节点即为最少的配送车节点。从最少的配送车节点开始直至遍历C-1 个节点（只有一个无人机的情况），生成所有可能的配送车路径。由于无人机每配送完一次货物需返回配送车拿取下件货物。例如有10个配送节点，为满足以上条件，无人机节点最多5 个最少1 个，则配送车对应路径即为5个节点至9个节点的任意排列组合；若有11 个配送节点，无人机节点最多6 个最少1 个才能保证每个无人机节点都有“返回点”，则配送车路径为5到10个节点的随机组合。在开始求解前，首先计算得到N个节点由“传统单货车配送”的最优路径解即TSP 解，为得到可行的配送车路径并缩小搜索范围，只保留路径距离小于TSP解的配送车路径，将配送车路径按其耗时升序存储在集合R中。算法流程图如图7所示。

图7 第一阶段算法流程图Fig.7 Flow chart of first-stage algorithm

第二阶段，固定第一阶段确定的配送车路径及无人机节点确定无人机路线。算法开始，将TSP解作为全局上界ub，对于固定的配送车路径将相应剩余的无人机节点在满足“每个无人机都有返回节点”的条件下，随机插空进配送车路径中，得到所有可能的无人机路径；然后考虑无人机续航时间的约束，计算各段无人机起飞至降落到配送车的路径耗时，保留满足无人机续航时间的无人机路径；接着结合对应的配送车路径，针对其相应的无人机路径计算联合配送情况下配送车的等待时间Wt，得到联合配送时间T为配送车耗时Truck与Wt之和；最后，若T小于TSP 解则保留该条联合配送路径，并将T作为新的全局上界否则不保留，以此方式更新改进ub。由于T为Ttruck与Wt的总和，而在第一阶段配送车路径按Ttruck升序排列，因此当迭代至第p条配送车路径时，Ttruck若大于最新的ub，则程序直接终止，此时的ub即为最优解，其对应的路径即为最优联合路径。算法流程图如图8所示。

图8 第二阶段算法流程图Fig.8 Flow chart of second-stage algorithm

2.2 算法示例

为理解算法，现以4 个节点为例说明算法流程，其中仓库坐标（15.18，15.76），配送节点坐标分别为（6.21，16.42）、（19.76，10.86）、（26.56，15.82），单位为km。算法开始前求得4 节点的TSP 解为65.16 min。4 节点情况下，配送车节点个数至少为1，至多为2才能使得无人机有返回点。因此第一阶段生成满足以下两个条件的配送车路径：（1）路径耗时小于TSP解；（2）避免重复路径，要求最后一个客户节点序号大于第一个客户节点序号。例如，路径0-2-3-0 与0-3-2-0 是相反方向的同一条路径，为缩小搜索范围，只保留第一条。最后按照路径耗时由小到大排列存储。第一阶段确定的配送车路径如表1所示。

表1 配送车路径举例Table 1 Example of delivery vehicle routes

第二阶段，固定第一阶段确定的配送车路径，将剩余节点合理插入配送车路径中生成满足约束条件的无人机路径，具体迭代过程如表2所示。

表2 无人机路径及算法迭代过程举例Table 2 Example of drone path and algorithm iteration process

表2中第2、3、6次迭代的联合路径总耗时都大于全局上界，因此ub未更新。第4 次迭代的路径耗时小于ub，因此ub更新为39.76 min。针对表1 中第4 条配送车路径0-2-3-0，对应有3条可能的无人机路径如表2中的4 至6 次迭代所示。其中无人机路径0-1-3-0 耗时29.35 min，超出了无人机自身续航时间25 min，因此不再后续计算同时删除该条路径。由于配送车路径耗时已经按由小到大排序，而第7 次迭代配送车路径耗时45.52 min 大于最新的全局上界39.76 min，因此算法停止，得到最优解为39.76 min。

3 实验结果分析

3.1 示例数据

由于TSP-D被引入文献不久，目前没有被广泛接受的基准数据，因此为研究评估本文算法的性能，本节通过随机生成的两类测试示例来求解TSP-D问题模型，并从运行时间、节点个数等方面分析了算法在两种示例上的结果。最后，从求解质量和求解时间等方面对该算法的性能进行了评价。

如图9所示均匀示例，所有客户节点坐标均匀地分布在0～30 km，形成一个900 km2的配送网络。如图10所示聚集示例，所有客户节点集中分布在以仓库为中心的配送网络中。表3和表4分别列出了均匀与聚集示例下，10、11节点的详细实验数据。

图9 均匀分布坐标Fig.9 Uniformly distributed coordinates

图10 聚集类坐标Fig.10 Aggregation class coordinates

实验假设配送车速度为40 km/h，无人机速度60 km/h，无人机电池续航25 km/h。实验使用Matlab语言编程，使用设备处理器为Intel®Core™i7-8700k CPU，内存为32 GB。

3.2 结果分析

由于无人机速度大于配送车速度，因此考虑是否分配越多的无人机节点越能得到最优解。为考察无人机节点个数与求解质量间的关系，观察表3 和表4 最后一列发现，最优解的无人机节点个数始终小于可能的最多无人机节点个数。如10 节点情况下，最大可能的无人机节点个数为5（11 节点时为6），无论在均匀还是聚集示例下，最优解的无人机节点个数始终小于5。这表明得到最优路径并不等同分配更多无人机节点。由于无人机与配送车的“同步性”，将大部分客户分配给无人机会导致配送车等待时间提升，配送效率反而下降。

表3 均匀示例Table 3 Uniform samples

表4 聚集示例Tablel 4 Aggregation samples

运行时间上分析，如表3和表4第5列所示，总体运行时间大约控制在半小时以内。由于该过程需要枚举，每增加一个节点，配送车路径和无人机路径的排列组合呈指数增加，因此11 节点相比10 节点同条件下运行时间明显提高。

表5根据表3和表4第2、3列数据，计算TSP-D交付方式较传统TSP 节省效率，结果显示10 节点情况下平均配送时间可节省30%左右，而11 节点情况下平均可节省17%以上，表明将无人机整合入传统配送车运送模式的有效性以及在聚集示例下算法优势更大。

表5 TSP-D解提高百分比Tablel 5 Percentage increases in TSP-D solution

图11～13 为聚集示例相同坐标下TSP 与TSP-D 两种配送模式的仿真结果，图14～16为均匀示例相同坐标下两种配送模式的仿真结果。其中图12、15为TSP-D配送模式求解过程中的两个随机解。图11得到单配送车耗时110.93 min，图13相同坐标下配送车联合无人机最优解耗时83.61 min，配送时间节省24.63%；图14单配送车耗时181.16 min，图16相同坐标下配送车联合无人机最优解耗时124.37 min，配送时间节省31.35%。

图11 单配送车配送路径（聚集）Fig.11 Single distribution vehicle distribution path（aggregation）

图12 无人机-配送车联合配送随机路径（聚集）Fig.12 Random path of drone-delivery vehicle joint delivery（aggregation）

图13 无人机-配送车联合配送最优路径（聚集）Fig.13 Optimal path of drone-delivery vehicle joint delivery（aggregation）

图14 单配送车配送路径（均匀）Fig.14 Single distribution vehicle distribution path（uniform）

图15 无人机-配送车联合配送随机路径（均匀）Fig.15 Random path of drone-delivery vehicle joint delivery（uniform）

图16 无人机-配送车联合配送最优路径（均匀）Fig.16 Optimal path of drone-delivery vehicle joint delivery（uniform）

4 结论

无人机联合配送车送货是一种新型的物流配送模式，TSP-D 主要解决配送车与无人机的路由问题，目标减少“最后一英里”的运输时间，是对传统TSP问题的改进。为优化路由决策，本文建立联合配送模型并提出一种新型优化迭代算法对该问题进行求解，结果表明无人机联合配送车这种新型交货方式与传统单配送车交货相比在时间效率上有所提高，该算法能在合理时间内得到11节点内的最优解。

就实际应用而言，由于复杂的道路状况、法规等的约束以及问题的NP-hard性质，使得解决问题的复杂度提升，因此在实际约束条件的限制以及问题规模的大小等方面有待进一步拓展研究。