智慧城市低空物流优化：基于TSP-DS模型的无人机-货车协同方案

一、研究背景与问题提出

电子商务的高速发展促进了城市末端配送需求的爆炸式增长。在传统车辆路径问题（VRP）或经典旅行商问题（TSP）中，配送车辆独自完成所有客户的服务。随着无人机技术的成熟，研究者尝试在“车—机协同”的框架下降低运营成本、减少行驶里程与碳排放。然而现有并行无人机旅行商问题（PDSTSP）大多假定无人机在货车上起降，这在实际中受限于货车空间和电池重量。本文关注的“旅行商问题‑无人机站”（TSP‑DS）允许无人机在独立的固定站点起降，货车通过联络路线补给站点，整个系统的目标是最小化从仓库出发到所有任务完成的完工时间。研究的关键问题包括：

• 场景描述：给定一个配送仓库、一个无人机站点以及若干客户，其中一部分客户只能由货车服务（称为货车客户），另一部分客户可由无人机或货车服务（称为无人机客户）。货车按顺时针顺序访问无人机站、客户并最终返回仓库；无人机可从站点出发执行多个往返任务，但每次起飞必须返回站点完成补给。
• 研究目的：在满足服务约束和飞行约束的前提下，通过优化无人机站位置、货车路径和无人机调度，寻求使系统完工时间最小的策略。
• 挑战与价值：TSP‑DS是PDSTSP的推广，既包括传统的车辆路径约束，又包含无人机的起降调度和站点容量约束，使得求解难度更高。论文通过提出两种强化的混合整数线性规划（MILP）模型及基于逻辑的Benders分解算法，实现对规模达152个客户实例的精确求解，并提供对无人机站位置、数量与速度等参数敏感性的洞察。

1.1 文献回顾与技术演进

• 并行无人机旅行商问题（PDSTSP）：该问题允许无人机搭载在货车上并伴随货车起降。尽管该模式减少了货车行驶距离，但无法避免无人机与货车同时占用货箱空间的问题。已有研究通过启发式算法与强化模型求解PDSTSP（如混合传输旅行商问题）；然而在规模较大的实例上仍难以获得精确解。
• 无人机站的引入：为解决车载起降的限制，TSP‑DS引入独立的无人机站点，允许无人机在站点独立操作，货车负责补给站点并配送其它客户。该模式提升了无人机的效率，但同时带来了新的决策变量：站点的起用时间与无人机数量。这使问题成为带有机器调度和路径规划的复杂组合优化问题。

二、模型与问题描述

2.1 基本符号与变量

设有有向完全图 。节点集合  包括仓库节点 、无人机站点 、货车客户集合  和可用无人机客户集合 。我们使用下列主要变量：

• 二元变量 ，当货车从节点  行驶到节点  时取值1，否则为0；
• 二元变量 ，当客户  由无人机服务时取值1，否则由货车服务；
• 连续变量 ，表示货车到达节点  的时间；
• 变量 ，表示整个系统的完工时间（货车和所有无人机任务都完成时的最大结束时间）。

无人机的起飞和返航时间由四元组  表征，意即从站点  起飞前往客户  后返回站点。无人机任务集合根据货车到达站点的时刻进行调度。假设无人机航行速度为  且最大航程不超过 。

2.2 原始模型

论文首先给出了紧凑型MILP模型来描述TSP‑DS。本节按照原文符号给出核心目标函数和约束，其中时间与二进制变量的耦合项被线性化，利用大M法处理服务时间关联。

目标函数：其中 (T) 为完成所有配送任务的最大时间。其值不小于货车完成路径的到达时间以及所有无人机任务完成时间。

主要约束（摘录）：

1. 车辆服务约束：每个货车客户只能由货车访问一次：
2. 无人机客户分配：每个无人机客户要么由货车服务，要么由无人机服务：
3. 货车流守恒：货车从仓库出发并必须访问无人机站点 (s)，因此 ，。
4. 时间与次序约束：若货车从  到 ，则满足其中  是货车在  上的行驶时间， 为足够大的常数。
5. 完工时间约束：货车完成路径及无人机任务结束时间均不能超过 。例如，对于货车，其中  为无人机在服务客户  的执行时间（往返行程）。

这些约束与变量的组合定义了基础模型，能够求解小规模实例。但随着客户数量增多，该模型因时间变量与二进制变量的耦合而出现松弛弱、求解时间长等问题。

2.3 模型改进与一般割集不等式

为了强化线性松弛，作者提出改进模型：引入决定客户是否由货车服务的二进制变量 ，并使用一般割集不等式（GCS）替代原有的子环消除约束。该不等式确保任何划分集  中至少有一条货车边离开集合：其中  取值1表示集合内包含货车客户或无人机站点。通过GCS约束，模型不需要显式引入时间变量即可排除小环，提升了模型在大规模实例上的求解效率。

三、解决方法与算法设计

3.1 挑战分析

TSP‑DS的难点主要体现在以下几点：

• 时间与路径耦合：无人机的起降时间依赖于货车到达站点的时刻；同时无人机和货车的完工时间共同决定目标函数，使得直接线性化复杂度高。
• 规模与维度增长：在多个无人机和客户的场景中，可能的无人机服务组合呈指数增长，传统的枚举或直接MILP求解难以处理。
• 无人机站选择：选取合适的无人机站点位置直接影响系统效率，但在不同站点之间切换存在路径重构和时间依赖，需协调货车与无人机调度。

为克服以上挑战，论文在改进模型的基础上提出了基于逻辑的Benders分解算法，将货车路径规划与无人机调度分离求解。该方法利用主问题生成货车路径，并在子问题中为给定路径计算无人机调度与相应完工时间，当子问题不可行或存在更优解时回传Benders割。

3.2 基于逻辑的Benders分解框架

下图展示了算法的整体流程。

• 主问题（Master Problem）：决定货车的行驶顺序  和无人机客户是否由货车服务的决策 。该主问题不包含无人机的时间变量，因此能够利用加速策略（如强有力的割集不等式）快速获得可行路径。
• 子问题（Subproblem）：在主问题给出的路径上，计算无人机调度的最小完工时间。此子问题等价于平行机器调度问题，通过求解可以得到无人机调度方案以及对应的完成时间 。若  或子问题不可行，则构造Benders割将该路径从主问题排除。

Benders割的形式可表示为：其中“cut”由子问题识别的违反时间约束的子环或服务模式确定。通过迭代添加割集，算法逐步缩小主问题可行域，直至获得整体最优解。其伪代码如下：

1. 初始化割集为空；求解主问题，得到货车路径。
2. 根据该路径构建并求解无人机调度子问题，计算最小完工时间 (\Theta)。
3. 若 (\Theta \le T)，则更新最优解；否则根据无人机调度或不可行原因生成Benders割并添加至主问题。
4. 返回第1步，直至主问题无更优解。

3.3 算法细节与改进策略

• 预处理与剪枝：在生成主问题的候选边时，利用三角不等式和时间窗排除明显不可能的链接，如货车在站点附近到达时间过晚的边，从而减少变量数量。
• 割集强化：针对无人机任务的串行调度和并行调度两种情况，算法分别构造不同的割，保证主问题的松弛尽可能紧。
• 分支‑Benders‑割框架：对于二进制变量较多的实例，作者在求解主问题时使用分支‑Benders‑割策略，将Benders割与经典分支定界算法结合，在分支节点上动态添加割以提高求解速度。

四、算例说明与比较

4.1 小规模示例

为直观展示TSP‑DS与PDSTSP的区别，论文给出了一个包含7个客户的示例。下图展示了五种配送方案：

• 图(a)：PDSTSP方案，由货车搭载无人机起降；
• 图(b)：在PDSTSP路径基础上将所有无人机客户交由站点无人机服务；
• 图(c)：允许无人机进行部分服务但过度依赖无人机，导致完工时间增加；
• 图(d)：适当分配无人机服务，提高效率；
• 图(e)：TSP‑DS的最优调度方案，货车与无人机协同完成配送。

从示例可见，过度依赖无人机或将所有服务交由货车都会影响完工时间，合理的任务分配和无人机站激活时机是提高效率的关键。

4.2 算法性能评估

论文利用多个公开数据集（如Murray等数据集）对提出的MILP模型和Benders算法进行比较。主要结论包括：

• 改进模型比原始紧凑模型在求解规模和速度上有明显优势，尤其是在客户数量超过30个时，GCS割能够显著缩小线性松弛差距。
• 基于逻辑的Benders算法能够在合理时间内求解包含152个客户的实例，且在多数测试数据集上优于商业求解器直接求解MILP的结果。
• 算法在无宽松度的极端情况下，即无人机数量有限且站点位置不利的场景下，也能保证求得最优解或提供很好的界。

五、敏感性分析与管理启示

在获得精确求解的基础上，论文进一步讨论了无人机数量、站点位置、飞行速度与航程对系统性能的影响。

5.1 无人机站位置与数量的影响

下图展示了不同站点位置（最佳覆盖站、最远邻站、随机站）以及无人机数量（1–5架）对性能的影响。

• 最佳覆盖站即使在多架无人机时依然表现优异；随机站或最远邻站在无人机数量增加时会显著降低系统效率，说明站点选址对多机系统尤为重要。
• 无人机数量增加能降低完工时间，但存在明显的递减效应。2到3架无人机通常能大幅提升效率，超过3架增益有限，并可能增加成本和调度复杂度。

5.2 无人机速度与航程的影响

另一组图展示了在不同速度比（无人机速度 / 货车速度）和航程长度下，系统平均目标值的变化。

• 速度提升对降低完工时间的效果大于单纯延长航程；当速度比从0.5提升至1或2时，目标值明显下降。
• 航程延长虽能增加无人机的可服务范围，但收益小于速度提升。由于长航程导致无人机电池重量上升，使用较快但较轻的无人机更为划算。
• 管理启示：企业在部署无人机配送时应优先选用速度较快、载重量适中的无人机；同时，无需配备过多无人机，合理的站点位置和2‑3架机队即可满足大部分需求。

六、研究结论与展望

本文全面分析了具备无人机站的旅行商问题（TSP‑DS），并提出两种强化的数学模型和基于逻辑的Benders分解算法。主要贡献包括：

• 模型创新：通过引入无人机站、一般割集不等式以及时间消除技巧，构建了适用于中大规模实例的MILP模型，并通过改进的变量和约束有效地提高了求解效率。
• 算法贡献：开发了逻辑Benders算法，将货车路径规划与无人机调度分离求解，显著降低了问题维度，并在测试集上取得比商业求解器更优的结果。
• 实证分析：使用多个实际场景数据集验证算法可解决规模达152个客户甚至264个客户的实例，且对无人机站位置、数量、速度与航程进行了系统的敏感性分析，为决策者在实际部署时提供了切实的建议。

未来研究方向：

• 多站点与多仓库场景：考虑多个无人机站和仓库并存时的路径规划与调度问题，以及站点的建设成本。
• 动态需求与不确定性：将动态到达订单、天气和能源消耗等不确定因素纳入模型，实现更具鲁棒性的调度。
• 绿色与可持续性目标：在最小化完工时间的基础上，引入碳排放、能源成本等环保指标，优化绿色供应链的综合效益。

总之，TSP‑DS的研究不仅为最后一公里配送提供了新的解决方案，也为混合交通工具协同调度提供了理论基础和实践指南，为智慧城市物流的可持续发展带来了重要启示。