无人机配送场景：基于分支定界的旅行商问题深入解析

论文题目：A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone

第一作者：Stefan Poikonen, Professor (Assistant) at University of Colorad. 研究核心聚焦组合优化与路径规划，重点围绕旅行商问题（TSP）、车辆路径问题（VRP）及无人机相关路径规划展开。

E-mail：stefan.poikonen@ucdenver.edu

大牛作者：Bruce L. Golden, Editor-in-Chief of the INFORMS Journal on Computing. 聚焦组合优化、网络模型与应用运筹学，深耕车辆路径、旅行商等问题的算法研究，跨医疗、物流等场景落地应用，且推动技术转化为实用软件并为多家企业提供咨询。

E-mail：bgolden@rhsmith.umd.edu

无人机配送场景：基于分支定界的旅行商问题深入解析

论文摘要

近年来，物流企业尝试利用无人机辅助卡车完成末端配送。论文针对单辆卡车搭载单架无人机的配送模型，即旅行商问题与无人机联合配送（TSP‑D）。该模型要求司机驾车从仓库出发，在配送途中释放无人机到某些节点去送包裹，并在电量限制内与卡车再次会合。为降低总体送货时间，研究者提出一种基于分支定界的求解框架。首先将配送序列建成树状结构，每个节点代表一个送货顺序；利用动态规划在每个节点上进行精确划分，确定哪些包裹由卡车送、哪些由无人机送，并计算这一序列的完成时间作为假定下界。算法按照最小下界扩展子序列，并用“树探索比”终止准则控制计算量。为了提高效率，论文提出线性和二次提升下界的启发式，并引入分治式策略将大规模问题拆分为小子问题。实验表明，基础分支定界法能获得接近最优的结果，但计算时间较长；提升下界与分治法能显著加速运算，在多数实例中优于现有的TSP‑ep方法。该研究为混合车–无人机配送提供了完整的算法框架和多种启发式优化策略。

一、研究背景与问题定义

1.1 背景概述

• 无人机配送需求增加：亚马逊、UPS等企业正在测试无人机用于包裹投递；电池寿命提升、成本降低使其应用越来越可行。
• 混合模型：论文关注的混合模式中，卡车携带无人机出行，在某些节点释放无人机去送单个包裹；卡车可在无人机飞行期间继续前进，之后在下一个节点与无人机会合。
• TSP‑D问题：与传统的旅行商问题不同，TSP‑D需决策“包裹由卡车还是无人机送达”的划分，并考虑无人机续航时间、发射/回收地点限制等因素。

1.2 模型与符号

• 节点集合：配送点及仓库组成集合 ，其中  和  为起讫仓库， 表示必须由卡车送达的点， 是可由无人机送达的点。

• 距离矩阵： 代表卡车从点  到  所需时间， 为无人机飞行时间，并假设满足三角不等式。

• 电池约束：无人机每次最多持续飞行  时间单位，必须在  时间内完成投递并在某个节点与卡车汇合。

• 决策变量：确定拜访顺序  并划分为卡车子序列  和无人机子序列 ；目标最小化完成时间 。

1.3 核心难点

• 组合复杂性高：既要确定访问顺序，又要决定每个包裹由卡车还是无人机送达，决策空间比传统TSP更大。
• 动态特性：无人机发射与回收的时机影响卡车行驶路径，插入新的停靠节点反而可能降低总时间。
• 电池与速度约束：需要确保无人机在电池寿命内完成任务，并考虑卡车速度与无人机速度差异，这对求解策略产生重要影响。

二、算法方法与关键技术

2.1 TSP-ep 动态规划划分

Agatz 等人提出的 TSP-ep 方法先求得卡车的 TSP 路线，再用动态规划将该路线划分为卡车与无人机子序列。定义 为无人机从卡车在点  发射，到经过中间点  送货后与卡车在点  会合的时间；若不可能在电池寿命内完成则 。进一步定义。动态规划递推式如下：

其中  表示在固定 TSP 顺序下完成从起点到节点  的最小完成时间，最终  就是按照固定 TSP 顺序划分后得到的 TSP-D 完成时间。这种方法保证子问题最优，但限制了卡车与无人机访问顺序必须是 TSP 子序列，无法探索更优的交叉访问顺序。

2.2 分支定界框架（BAB）

论文提出的核心算法是在分支定界框架下全局搜索访问顺序：

• 节点结构：树的每个节点对应一个访问序列。从根节点开始，每次选取距离父节点序列中已访问点最远的点插入不同位置生成子节点。
• 下界计算：利用改进的动态规划函数，允许卡车在无人机飞行期间等待，从而获得序列的最佳分割，并将其作为该节点的假定下界。
• 搜索策略：假设插入更多包裹通常会增加完成时间，即。算法始终扩展当前下界最小的叶节点，当某个节点序列包含所有包裹时，将其视为上界。
• 终止准则：设为所有叶节点的最小下界，若则停止搜索；是用户设定的树探索比，越大表示可接受更大误差以减少搜索树。

下面通过图例帮助理解。下图(a)给出了一个四节点示例，当时需要完整展开树；若则可剪枝。

图1展示在电池寿命为10分钟时，插入一个新的停靠点可以让无人机成功完成送货并缩短总时间：在图(a)中无人机无法从节点0直接飞往节点1而返回，必须由卡车送达；在图(b)中插入节点3后，无人机可在节点3起飞、节点1送货、在节点2与卡车会合，完成时间从34分钟降至21分钟。

2.3 强化下界的启发式

为减少搜索节点，作者提出在下界上加入惩罚项：

• 线性提升（BAB+L）：，意为还未插入的每个包裹至少增加时间。
• 二次提升（BAB+Q）：，假设短序列插入包裹的代价较大，序列越长越容易插入。

通过调整参数可以在精度与计算时间之间取得平衡。当时退化为原始BAB；越大，算法越倾向快速剪枝，但可能错过最佳解。

2.4 分治启发式（DCH）

当问题规模大时，单纯分支定界计算量极大。作者提出将节点分组，分别求解子问题再连接的方法：

1. TSP初始化：先根据卡车度量求解标准TSP，并重新编号节点。
2. 分组处理：将个配送点划分为个连续子组，每组大小约 或 ，每组形成一个子问题。对于第组，序列起点为上一组终点，终点为本组最后一个节点。
3. 子问题求解：对每个子组应用BAB或其变体求解，然后将子序列连接即可。

图2给出的例子，不同颜色区域可独立优化后拼接。

2.5 完整探索示例与剪枝策略

下面的图是一个含四个配送点的完整树，当必须搜索所有节点；若则可提前终止，因为部分节点的下界乘以1.15已经超过了当前最优解。

三、实验分析与结果讨论

3.1 树探索比对结果影响

• 对规模的100个随机实例进行测试，当从1增大到1.25时，BAB算法的平均目标值逐渐逼近最优解，而计算时间增长明显。
• 在的实例中，时需要穷举全树，计算时间非常长；当时，BAB的目标值始终不劣于TSP‑ep方法。
• 综合来看，适当提高可以在保证结果质量的同时大幅减少搜索节点，是分支定界算法的有效调节参数。

3.2 启发式的速度–质量权衡

作者将原始BAB与线性提升、二次提升和分治法进行比较：

• 线性/二次提升：通过设置，可以显著缩短运行时间，但目标值略有上升。当时回到原算法，越大剪枝越激进。
• 分治法：将大问题拆成若干子问题可实现线性增长的计算时间，且在大多数实例中比TSP‑ep获得更好的目标值。
• TSP‑ep比较：TSP‑ep方法基于固定TSP路径的划分，其速度最快但无法探索新的卡车顺序。在某些实例中，BAB的解明显优于TSP‑ep，图5展示了一个四点实例中TSP‑ep错过最优解而BAB找到最优解的场景。

3.3 综合评价

总体而言，BAB能够在小规模实例上获得接近最优的解；线性/二次提升通过增加下界改善剪枝效率；分治法适用于大规模实例，兼顾质量和效率。TSP‑ep作为对比基准，在速度上具备优势，但在很多情况下目标值明显偏高。

四、创新点与未来展望

4.1 主要创新

• 全局搜索与精确划分结合：将分支定界的全局顺序搜索与动态规划的精确划分相结合，突破传统TSP‑ep必须按TSP子序列划分的限制。
• 假定下界与树探索比：引入假定下界和树探索比，使搜索过程既能优先探索潜在好解，又能通过调节控制计算时间。
• 启发式提升函数：设计线性与二次提升下界，实现对分支定界的启发式加速，在误差可接受的情况下显著减少节点数量。
• 分治策略：提出将大规模问题分割成若干子问题的策略，可与分支定界结合，保证局部最优时整体效果良好，并显著降低复杂度。

4.2 未来研究方向

文章最后提出了几条值得探索的方向：

• 多无人机协同：当前模型限制卡车携带单架无人机，未来可研究多无人机协同发射、回收的调度问题。
• 沿边发射/降落：扩展无人机可在边上任意点起降，而不仅限于节点，提高灵活性。
• 考虑起降开销：模型未包含无人机发射、降落和电池更换耗时，未来可以将这些因素引入成本函数。
• 多车多无人机车队：将TSP‑D嵌入到车辆路径规划中，考虑多辆卡车与多个无人机协同的复杂情形。
• 客户分布影响：实验发现算法在“一中心”实例上效果更好，未来可进一步分析客户分布对算法表现的影响。

4.3 学术与实践意义

该研究为混合车–无人机配送提供了系统性的算法框架，并在算例中验证其效果。对于学术界，这为TSP‑D等组合优化问题提供了可推广的分支定界技术和启发式加速思路；对于行业实践，分治策略和提升下界方法可指导在有限计算资源下快速生成高质量配送方案。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。