基于集群的卡车与无人机联合配送调度研究

曹英英，陈淮莉

上海海事大学 物流科学与工程研究院，上海 201306

近年来，随着互联网在农村的不断渗透，农村网购热潮不断兴起，在国家和企业的双重支持下，2020年中国农村电商市场规模为31 533亿元，同比增长37.7%，农村电商迅猛发展[1]。然而，除了国营企业邮政速递，大部分民营物流公司所构建的配送网络最多由县级下沉到人口聚集、交通相对便捷的乡镇，尚未往下延伸到各个村落，更不用说直接面向消费者，大部分快递仍需消费者自取，自行解决从村到站点的交通问题，导致物流时效性大大降低[2]。如何改变传统的物流配送方式以打通农村物流“最后一公里”，让消费者获得更高效的服务，是亟需解决的难点。随着无人机在物流领域受到越来越多的关注，多家企业和学者推出一种新的配送模式，即卡车与无人机联合配送，来取代传统的卡车运输。

目前Amazon、UPS、DHL等大公司开始将无人机应用于物流业务中[3]，国内企业以京东和顺丰等也紧跟其后，在全国各地着手布局无人机配送体系[4]。同时，关于在配送过程中使用无人机的研究受到学者们极大的关注。一些研究考虑通过搭建充电站网络使无人机直接从仓库交付货物[5]，或建立靠近客户的无人机站单独为无人机提供储存货物和充电服务[6]，以克服飞行距离限制。为了规避这些站点的投资成本，许多研究[7-17]又考虑将无人机加入到现有的卡车配送模式中协同配送。虽然无人机凭借着配送速率快、无视地形影响等优点，能有效节约时间和减少交付成本，但无人机载荷和续航能力有限，传统卡车可以弥补这一技术限制。在这些研究中，卡车携带无人机和所有订单从配送中心出发，需要在一些客户点处停留完成交付任务，同时无人机从客户点起飞对附近一定范围内的其他客户配送小型包裹。以此循环，直到所有订单配送完成。相比城市配送和其他应用场景[7-9]，农村地区由于禁飞政策相对宽松、安全性相对较好等因素能够很好地发挥出卡车与无人机联合配送新模式的作用。

关于卡车与无人机联合配送的研究主要集中于带无人机的旅行商问题（traveling salesman problem with drone，TSP-D）和多卡车多无人机路径问题（vehicle routing problem with drones，VRPD）。2015年，Murray等[10]首次提出卡车搭载无人机联合配送理论，开发混合整数线性规划模型和简单的启发式算法，可解决小规模案例。Agatz等[11]在Murray的研究基础上基于局部搜索和动态规划设计出两阶段启发式算法。Ha等[12]针对TSP-D问题，在最小化总运营成本中加入了等待时间所产生的罚金，提出贪婪随机化自适应搜索算法来求解更大规模实例。Ferrandez等[13]使用K-means算法将配送网络划分为集群，集群质心充当无人机调度的卡车停靠站，并使用遗传算法优化卡车路线。

以上研究均假设一辆卡车仅携带一架无人机，随着研究的深入，可考虑单辆或多辆卡车携带多架无人机[14-17]。其中，Kitjacharoenchai等[15]提出带无人机的两级车辆路径问题，设计无人机卡车路径构建算法和大邻域搜索算法来解决该问题。Chang等[16]在初始K-means聚类和TSP建模后通过增加移动权重将卡车停靠点向仓库靠近，以进一步缩短交货完成时间。Salama等[17]将无监督机器学习K-means算法分为三步得到修正后的最优卡车路径。

上述研究大多选择客户点来作为无人机的发射和回收位置，传统的K-means算法只是将聚类出的质心移动到离质心最近的客户位置处，该过程没有考虑卡车和无人机配送成本。对此，本文对K-means算法进行改进，考虑无人机续航和数量限制，通过修改聚类以适应本文所提出的特定客户点和普通客户点，来选出最佳卡车停靠点集合，并提出遗传模拟退火算法加快收敛速度，用以优化卡车与无人机联合配送路线，从而找出总运营成本最小的配送方案。同时，以上文献均未将时间窗纳入考虑范畴进行深入探索，而时间窗的设定可以提高消费者的服务体验。本文增加时间窗限制，若卡车或无人机配送未在规定时间内送达则会产生相应的惩罚成本。

综上，本文针对农村地区送货上门难的问题提出基于集群的卡车与无人机联合配送问题，以总运营成本最小为目标，结合无人机的特点，构建带有时间窗的混合整数规划模型，并通过改进后的K-means聚类算法和遗传模拟退火算法对模型求解，结果表明本文所采用的方法能有效降低配送成本，且算法效率较高。

1 模型构建

1.1 问题描述

在一个农村地区的乡镇级配送网点中，需要该网点的运输工具在规定时间内向周边相邻的多个客户点投递包裹。传统卡车单独配送如图1（a）所示，卡车与无人机联合配送模式如图1（b）所示。一辆卡车搭载着多架无人机和总需求前往每个集群内依次进行配送。将卡车配送点统称为卡车停靠点，集群是指以卡车停靠点为中心并包含作业半径限制内客户节点的集合。卡车需要在每个停靠点停留一段时间，首先对该客户点服务，然后让无人机从停靠点起飞对集群内的普通客户点配送，最后返回到停靠点处的卡车上完成装货和更换电池操作为下一次停靠做准备。以此循环完成所有配送，最后一同回到配送网点。由于部分货物的重量或体积超过无人机载荷限制，或需客户当面签名验收等原因，这些货物无法由无人机配送只能特别指定卡车来服务。本文称这些客户点为特定客户点，其他客户点为普通客户点，可随机由卡车或无人机来完成服务。为方便统计，本文简单地考虑货物重量来区分客户种类。

图1 配送模式对比Fig.1 Comparison of distribution modes

为方便进行定量化研究，对问题进行简化，做出如下假设：

（1）所有客户点位置、需求、服务时间及时间窗已知。

（2）无人机有容量和最大飞行半径限制，卡车一次出行有足够的容量和燃料供应。

（3）无人机装货和更换电池时间较短忽略不计。

（4）无人机一次只能配送一个包裹，完成任务后只能返回卡车停靠点，在每个集群内只进行一次飞行。

（5）每个客户点只能由一辆卡车或一架无人机一次配送完成。

（6）卡车和无人机均匀速行驶和飞行。

1.2 符号说明

1.3 建立模型

根据问题描述和参数定义，可构建以下模型：

其中，目标函数（1）为总运营成本最小化，总运营成本由无人机的固定成本、总行驶成本和时间惩罚成本构成；约束（2）表示每个客户节点只能被卡车或无人机访问一次；约束（3）确保卡车恰好离开和返回配送网点一次；约束（4）表示卡车对每一客户点进出度相同；约束（5）表示无人机对每一客户点进出度相同；约束（6）表示每架无人机对卡车停靠点进出度相同且只访问一次；约束（7）表示集群作业半径限制；约束（8）表示每个集群内需要无人机服务的客户点数不超过所携带的无人机数量；约束（9）表示无人机在集群内的配送时间为它的飞行时间加上在客户点的服务时间；约束（10）表示卡车的等待时间为无人机在集群内配送的最长时间；约束（11）表示当卡车到达j点时，其消耗的时间包括卡车到达i点的总时间，加上i处的服务时间和等待时间以及卡车从i到j所花费的行驶时间；约束（12）表示无人机配送满足客户时间约束；约束（13）为消除卡车路径子回路；约束（14）至（17）为变量取值范围。

2 算法设计

本文的问题属于NP-Hard问题，传统优化方法很难求解，因此本研究设计一个两阶段优化算法。首先利用带约束的改进K-means算法对普通客户点进行聚类，选出卡车停靠点；然后利用遗传模拟退火算法求得卡车与无人机联合配送最佳路线，从而求得卡车与无人机联合配送最小总运营成本。

2.1 获取卡车停靠点集合

K-means算法是一种基于划分的聚类算法，它以k为参数把数据对象分成k个簇，将相似度高的对象聚为一类，而簇间对象彼此相似度尽量低。传统的K-means算法事先给定聚类数k，该点为各簇中样本点的平均值。在本研究中，将对普通客户进行聚类，k的最大值高达N F，最小值为N F/(g+1)，即每(g+1)个点就会形成一个集群和一个卡车停靠点，是最理想的状态。需要对聚类算法进行改进，修改聚类来满足所有类型客户的配送需求。本文将k值设为N F/(g+1)，初始卡车停靠点集合中含有配送网点和特定客户点。具体实现过程如下：

步骤1对普通点进行K-means聚类，得到k个聚类中心。

步骤2将每个聚类中心移至最近的节点处作为卡车停靠点，首先考虑约束（7）进行筛选，超过里程限制的普通点加入停靠点集合。若簇内的普通点满足约束（8），转步骤4，不满足转步骤3。

步骤3超过无人机数量限制时选择客户遵循优先满足离配送网点最远距离原则，未被选上的普通点加入停靠点集合。

步骤4将每个集群内的卡车停靠点移至最近的配送网点或特定点处，同时考虑约束（7）和（8）。集群内的普通点没有减少，则将该集群的停靠点转移到配送网点或特定点处，不满足则不转移保持现状。

步骤5含有α个普通点的集群尝试与最近的集群合并，见公式（18）。以满足两个约束条件为前提，停靠点为普通点的集群并入停靠点为特定点或配送网点的集群，停靠点到配送网点较远的集群并入停靠点到配送网点近的集群中。

步骤6输出优化后的卡车停靠点集合。

带约束的改进K-means聚类算法既满足了无人机续航和数量限制，还能不断调整卡车停靠点移动到合适的客户点处。与传统的K-means聚类算法相比，不需要考虑初始值的选取对聚类结果的影响。

2.2 优化联合配送路线

遗传算法的基本思想是借鉴自然界中“物竞天择、适者生存”的法则，应用适应度对个体进行评估筛选来寻找问题的满意解，是具有自适应能力的、全局性的概率搜索算法。因其寻优能力强，可靠性较高，已被用于求解许多车辆路径问题。同时遗传算法容易出现过早收敛的问题，在进化后期搜索效率较低，不易得到最优解。模拟退火算法是以单个个体为对象，基于上一代个体进行迭代，局部收敛特性良好，但全局搜索能力不太强。因此，本文将这两种算法相结合可以优势互补，设计遗传模拟退火算法来优化卡车与无人机联合配送路径问题，提高求解效率。遗传模拟退火算法具体操作步骤如下。

（1）设置初始化参数：种群规模N、最大迭代次数M、交叉概率pc、变异概率pm、初始温度T、温度冷却系数λ。

（2）生成初始种群：卡车停靠点编号为顺序对N条染色体编码，随机生成N条长度为k的染色体（k为卡车停靠点数）。

（3）计算个体适应度：适应度函数是用来度量群体中染色体的优良程度，适配值越大则个体越优。本文的目标函数是求成本最小化，所以根据公式（1）计算出每种卡车与无人机联合配送方案的总运营成本，以其倒数作为适应度f i。

（4）遗传算子：为选择算子、交叉算子和变异算子。本文采用轮盘赌的方法选择出当前种群中适应度高的个体，以pc的概率利用单点交叉方式生成子代。为了维持种群的多样性，本文按pm概率对个体进行变异。经过选择、交叉和变异操作后生成新种群，并计算新种群中个体的适应度f i+1。

（5）模拟退火操作：根据模拟退火中Metropolis接受准则，对新种群中的个体进行退火操作来实现新旧种群的替换，若f i+1＞f i，新个体将替换旧个体，否则的话就以p=exp((f i-f i+1)/T)的概率接受新个体。

（6）判断终止条件：若迭代次数达到M，则停止循环输出最优解，否则按照T i+1=λTi降温转（3）。根据上述步骤，遗传模拟退火算法流程图如图2所示。

图2 遗传模拟退火算法流程图Fig.2 Genetic simulated annealing algorithm flow chart

3 数值实验

算法采用Python编程来实现，在一台CPU型号为AMD Ryzen 5、12 GB内存、Windows 10操作系统的计算机上运行。遗传模拟退火算法中种群规模设为50，最大迭代次数设为200，交叉概率为0.9，变异概率为0.1，初始温度为100，降温系数为0.98。

假设有四架无人机，无人机的固定成本为10元/架，载重为10 kg，平均飞行速度为80 km/h，最大飞行距离为12 km，卡车平均行驶速度为60 km/h。另一方面，将卡车单位行驶成本设为1.5元/km，无人机单位飞行成本设为0.18元/km，早到的时间惩罚成本为0.4元/min，晚到的时间惩罚成本为0.8元/min，每个客户的平均服务时间为1.5 min。为方便计算，各点之间的卡车行驶距离采用曼哈顿距离，各点之间的无人机飞行距离采用直线距离。

3.1 模型与算法的验证分析

目前，没有针对该问题的标准测试数据，本文以Solomon算例集中的C和R为基础数据，在10 km、20 km和30 km的地图范围内从两个算例中分别选择前10、20和30个顾客节点构成小规模算例，并对数据做适当调整，来适应地图的大小。其中，确保有δ=10%的客户需求超过无人机的载重，剩余客户均可由无人机服务。在此对时间窗放宽限制，避免最终结果受时间惩罚成本影响较大。

为了评估本文模型的准确性和两阶段算法的有效性，选用文献[17]中的方法进行对比。首先将聚类数定为N F/(g+1)，采用传统的K-means算法求出各集群的质心，然后将质心移动至最近的卡车服务点，从而得到卡车停靠点集合，同时考虑无人机数量和里程限制，超过限制的点由卡车配送。最后使用CPLEX求解标准的TSP模型。将结果与本文所提出的两阶段算法的计算结果进行比较，测试结果如表1所示。

通过表1可知，两阶段算法求出的结果均小于文献[17]所采用的方法。对K-means算法进行改进加入选择客户优先满足离中心最远距离原则和合并操作可得到优化后的卡车停靠点集合，有效减少总运营成本。

表1 传统K-means+CPLEX与两阶段算法结果对比Table 1 Comparison of results between traditional K-means+CPLEX and two-stage algorithm

3.2 案例分析

综上分析，本文所提出的两阶段算法对卡车与无人机联合配送优化问题具有较好的求解性能，接下来，选取江苏省宿迁某农村地区来对卡车与无人机联合配送模式进行仿真模拟。本区域有一辆卡车和四架无人机，为30个客户提供送货服务，具体位置分布如图3所示。

图3 客户点分布Fig.3 Customer points distribution

每个客户点的需求和时间窗随机生成，如表2所示，其中1、3、4这3位客户的需求超过无人机载重限制，为特定客户点，其他客户点均为普通客户点。

表2 客户点信息Table 2 Customer points information

遗传模拟退火算法迭代到52次时算法收敛。经过多次程序的运行，最终方案如图4所示，最低总运营成本为263.35元，其中运输成本为218.75元，时间惩罚成本为4.6元，大部分服务时间都在客户要求的时间窗范围内，极大地提升了客户服务水平。以上结果表明卡车与无人机联合配送模式能够在农村地区有效完成配送任务。

图4 卡车与无人机联合配送结果Fig.4 Results of joint distribution of trucks and drones

为了验证遗传模拟退火算法的优劣，采用传统的遗传算法对模型求解，参数设置不变，结果对比如图5所示。从图5可知传统遗传算法相较于遗传模拟退火算法有着更多的平均迭代次数，这意味着遗传模拟退火算法在每个生成解的范围内有着更好的搜索精度，搜索效率更佳。而且遗传模拟退火算法求出的解优于传统遗传算法，这表明遗传模拟退火算法收敛到全局最优，没有陷入局部最优解中，因此遗传模拟退火算法较传统的遗传算法有着更好的求解性能，寻优能力更强，稳定性更好。

图5 收敛性能对比图Fig.5 Convergence performance comparison chart

为了体现卡车与无人机联合配送的优越性，本文对单独使用卡车运输的方式进行求解，结果如表3所示，最低总成本为309.4元。联合配送模式的最终结果与仅卡车配送模式的最终结果相比降低了14.89%，这表明无人机在物流运输方面还是有一定的优势，卡车与无人机联合配送的运输方式可有效降低物流运输成本。

表3 卡车单独配送结果Table 3 Individual truck delivery results

与此同时，研究特定客户占比因子和携带的无人机数量对最终结果的影响，分别在有时间窗和没有时间窗约束的情况下运行，最优值变化如图6、图7所示。

通过图6和图7可知，特定客户占比因子和携带的无人机数量均会对配送路径目标产生影响。图6和图7中的（a）显示，所有货物都可以由无人机服务时成本最少。当δ为10%以上时成本急速上升，因此理想的做法是将特定客户占比限制为较小的值，尽量将货物交予无人机配送。在现实配送中，物流公司应选择能承载更重货物的无人机来进行末端配送，减少卡车配送的几率。

图6 不考虑时间窗时的最优值变化Fig.6 Optimal value change without considering time window

图7 考虑时间窗时的最优值变化Fig.7 Optimal value change when considering time window

图6和图7中的（b）显示，不考虑时间窗时，UAV数量为2架时总运营成本最小，相较于纯卡车配送成本降低11.07%；而总运营成本加入时间惩罚成本时，UAV数量为3架时最小，相较于纯卡车配送总成本降低17.41%。因此，物流公司在配送规划时应根据不同农村地区对时间窗的容忍度来考虑是否将时间罚金纳入总运营成本中。同时，物流公司还需要根据客户分布情况来选择携带的UAV架数，而不是携带得越多越好，这会增加无人机成本，导致总运营成本的上升。

4 结束语

本文基于集群提出卡车与无人机联合配送模式来解决农村电商物流末端配送难题，并对问题进行定义，建立带时间窗的混合整数规划模型，目标是尽可能降低总运营成本。根据问题特性，提出两阶段算法，首先对K-means算法改进求出最佳卡车停靠点，然后采用遗传模拟退火算法优化卡车与无人机联合配送路线，将其与传统K-means算法加CPLEX结果对比，验证了模型的可行性和两阶段算法的有效性。仿真结果表明，遗传模拟退火算法相比传统的遗传算法有着更好的求解性能。同时，卡车与无人机联合配送模式与传统的纯卡车运输模式相比可有效降低总运营成本，这为解决农村地区的配送难题提供了指导性建议。本文只是考虑了将卡车停靠点限制在客户位置上，未来可以放松这一限制扩大搜索范围找到更合适的停靠点位置，还可以考虑卡车与无人机的其他合作模式来灵活应对不同的场景。