研究背景与问题动机

近年来，UPS、亚马逊等大型物流企业纷纷启动无人机最后一英里配送项目，目标在于缩短配送时间、减少碳排放并提升客户满意度。学术界对此积极响应，Murray和Chu于2015年提出的飞行副驾旅行商问题（FSTSP）成为该领域的基准模型——一辆卡车搭载一架无人机共同服务一组客户，目标是使整体完成时间最小化。

然而，现有大多数研究共享一个与现实脱节的关键假设：无人机速度为常数，且续航能力与速度和载荷无关。这一假设暗示提升飞行速度只会带来正面效果，但实际中空气阻力造成的能耗是速度的非线性函数。改变飞行速度可能增加续航里程、服务更多客户，或通过更快的飞行缩短整体配送时间。

取自Fig.2。左：无人机巡航功率随速度的非线性变化；中：给定500kJ电池下的航程曲线；右：单位距离能耗函数EPM(v,w)，本研究的核心在于该函数的凸性分析。

问题定义：FSTSP-VDS建模

FSTSP-VDS是对经典FSTSP的扩展。一辆卡车配备一架无人机，无人机可在连续区间内为每条飞行弧段独立选择巡航速度。每架次飞行速度保持不变。无人机有固定的电池容量B=500kJ，续航时间取决于包裹重量和飞行速度的函数。无人机每次起飞需准备时间60秒，回收需30秒；卡车和无人机的包裹交付时间分别为30秒和60秒。

研究采用Liu等人（2017）的多旋翼小型无人机功率消耗模型，该模型区分了垂直起降、水平巡航和悬停三种飞行阶段的功率特征。无人机自重1.5kg，巡航高度50m，起飞和降落速度分别固定为10m/s和5m/s。模型系数来自Liu等人的实验标定（详见表1）。图2表明，无人机功率消耗是速度的非凸函数，但单位距离能耗EPM(v,w)在v>0时对每个载荷均为凸函数。

无人机能耗的凸性关键发现

作者证明了一个关键性质：当EPM(v,w)为凸函数时，对任意无人机航段(i,j,k)，其可行飞行时间集合也是凸的。这意味着可以预先计算每个无人机航段的最小和最大可行飞行时间，从而将无人机速度从决策变量中消除，将问题转化为MILP。

计算最小飞行时间时，目标是使航段总飞行时间最小化，同时满足电池约束。计算最大飞行时间时，将能耗表达为飞行时间的函数，利用EPM凸性推导出E_d的凸性，进而求解最大化飞行时间的凸优化问题。对于任意目标时间T，还可通过第三个凸优化问题确定最小化能耗的速度配置。所有预处理计算均使用NLopt库中的COBYLA算法完成。

紧凑MILP精确求解方法

基于上述凸性分析，FSTSP-VDS可被转化为一个紧凑的MILP模型（公式6a-6u）。模型的目标函数是最小化总配送完成时间makespan，包括卡车回库时间、所有无人机航段的起降准备时间、以及在连续操作之间完成的卡车配送时间。

取自Fig.3。一个五客户FSTSP-VDS实例的解：实线表示卡车弧，虚线表示无人机弧，双线表示联合弧。显示了卡车与无人机之间的同步关系和六种可能的makespan计算方式。

MILP模型包含五类核心决策变量：卡车弧变量、无人机弧变量、客户服务类型变量（卡车/无人机/联合客户）、无人机航段变量以及服务时序变量（在同步前/后服务）。约束条件涵盖流量守恒、消子环、无人机飞行时间上下界、服务时序兼容性等。引入有效不等式（约束7）可显著减少求解时间。

实验中使用CPLEX 22.1.1求解，时间限制1小时，单线程运行。在10客户实例上，所有实例均被求解至最优。当最大允许速度为40 m/s时，平均求解时间为64.04秒；当最大速度为10 m/s时，平均求解时间为160.27秒。平均整数间隙约为50%，不随最大速度变化而显著改变。

基于HGSADC的遗传算法设计

由于MILP无法扩展到更大规模实例，作者基于Vidal等人（2012）的混合遗传搜索与自适应多样性控制（HGSADC）框架设计了遗传算法GA。GA的种群规模为400，迭代2000代，每代生成20个后代，偏置适应度权衡参数λ=0.92。

取自Fig.4。染色体序列(0,1,2,0')编码的五种可能解，说明同一排列可对应多个解，需要split过程确定最优。

GA的关键创新在于split动态规划过程：给定一个客户排列，该过程计算出所有满足该排序约束的解中makespan最小的那个，时间复杂度O(n³)。对大规模实例，通过限制最大卡车路段长度至12个连续客户，可将复杂度降至可控范围。交叉过程中的缺失客户重插入也采用split评估每个候选位置，确保贪婪地选择最优插入点。

计算实验：固定与可变速度的对比

实验采用Raj和Murray（2020）的两组FSTSP-VDS实例：数据集A包含四个客户规模等级（10、25、50、100），每个等级10个实例，固定服务面积918 km²；数据集B包含50客户、四个服务面积等级（57.4至918 km²），每个等级10个实例。所有实例分别测试四种最大速度配置，共计320个实例。此外，还在Blufstein等人（2024）的750个FSTSP实例（9至99客户）上验证GA的通用性。

取自Fig.6。横轴为最大允许速度，蓝色线为固定速度设为最大速度的结果，红色线为允许速度在区间内变化的结果。固定速度在高速区导致makespan急剧增加。

固定与可变速度的对比结果极具启发性：当最大速度为10 m/s时，固定速度与可变速度的差距为0%；但当最大速度升至30 m/s和40 m/s时，固定速度分别带来22.82%和32.06%的额外makespan。最优固定速度为20 m/s，gap为5.07%。即使每次飞行都选择使航程最大化的速度，gap仍达7.79%，比统一采用20 m/s更差。

在FSTSP-VDS大规模实例上，GA在所有实例上均找到了优于RM的最佳已知解。在数据集A的160个实例上，GA的聚合平均gap为0.16%，而RM为7.78%。GA的计算时间从10客户实例的几秒到100客户实例的约10分钟，扩展性优于RM。在FSTSP实例（固定速度）上，GA在1253个已被精确求解的实例中取得了0.26%的平均gap，并找到了其中990个实例的最优解，包括部分99客户的大规模实例。

管理启示与研究局限

从物流管理角度，本研究的核心启示是明确的：无人机速度选择是最后一英里配送成本的关键杠杆。即便在一个仅有10个客户的小规模场景中，选择次优的固定速度策略就可导致5%至32%的额外配送时间。这提醒运营管理者，在规划无人机-卡车协同路径时，必须将速度决策与路径决策进行联合优化，而非先选速度再规划路径。

本研究也存在若干局限。MILP精确方法仅能求解10客户规模的实例，距离实际场景仍有差距。实验只研究了速度优化对makespan的影响，未涉及碳排放、能耗成本等多目标的权衡。此外，当客户数量超过100时，预处理阶段为所有可行无人机航段计算最小/最大飞行时间的计算负担将显著增加。

未来工作可从几个方向展开：扩展至多无人机场景，探索不同速度策略之间的交互效应；将凸性分析框架应用到其他真实能耗模型（如Stolaroff或Zhang模型）的配送问题上；设计针对超大规模实例（>1000客户）的高效启发式速度选择策略。