驾驶、装载、飞行：The Travelling Thief Problem with Drone
在收集作业中，不断增加的载荷会逐渐降低车辆速度，给路径规划效率带来累积惩罚。机载无人机可通过取回外围物品来抵消这一惩罚，从而缩短完工时间、提升运营利润。然而，旅行时间仍依赖载荷，并且地面车辆每收集一件物品都会改变控制无人机发射与汇合点的到达时间。 本文提出 Travelling Thief Problem with Drone (TTP-D) 问题，通过联合优化物品选择、车辆路径和飞行同步，最大化扣除按时租赁成本后的收集利润。我们构建了一个 mixed-integer linear program 模型，可对小规模实例求解最优；同时开发了 metaheuristics 和基于注意力的 Deep Reinforcement Learning (DRL) 策略以应对更大实例。进一步，我们提出了一种 learner-initialised hybrid solver，由 DRL 策略构建初始解，再用短时模拟退火（annealing）进行精炼。 在两个基准集上，该混合方法能以极低的计算预算恢复大多数元启发式基线的质量；但最大实例仍需基线使用完整预算。敏感性分析表明，rental ratio（租赁比率） 是盈利能力的主要驱动因素，而车队参数仅对利润产生边际影响。
论文精读
TL;DR 本文定义带无人机的旅行小偷问题（TTP-D），联合优化物品选择、车辆路径与飞行同步以最大化利润，并提出注意力 DRL 初始化的混合求解器，在少量计算预算下恢复元启发式基线的大部分质量。
问题
问题背景
在集合作业路由领域，车辆随收集物品增重而逐步减速，造成负载依赖的累积行驶时间惩罚，直接影响 makespan 与运营利润。当前研究热点是将无人机作为移动副车，通过空中取回外围物品来抵消地面车辆的负载劣势。
现有方法局限
传统 Travelling Thief Problem (TTP) 只考虑地面车辆，忽略无人机协同路由的可行性；已有的卡车-无人机路径规划方法通常假设行驶速度与负载无关，且将无人机调度视为独立的访问序列优化，并未联合优化物品选择、地面路由与飞行同步。在实际负载依赖场景下，地面车辆每拾取一件物品都会改变后续到达时间，进而改变无人机可发射与回收的时空窗口。若沿用解耦或负载无关假设，得到的方案会违反同步约束，或大幅偏离真实最优利润。
为什么这个问题难/重要
难度来自两个层面：
- 耦合动态性：负载变化导致地面车辆到达时间不断漂移，无人机发射/会合点必须随之重新规划，搜索空间呈指数级增长。
- 多目标权衡：利润 = 收集收益 − 时间租金成本，需要同时决定选哪些物品、按什么顺序取、何时放无人机，三者互相牵制。
精确 MILP 只能处理小规模实例，对于数百节点的大规模问题，必须依赖元启发式或深度强化学习。业界关注最后一公里物流、仓储自动化等场景，其中负载敏感车辆与无人机的协同已成为降本增效的关键技术路径。
行业类比
类似强化学习控制多机器人仓库拣选系统：移动机器人载重变化影响速度与路径时间，调度策略需同时优化任务分配与动态路径，才能保证全局吞吐与能耗平衡。
核心洞察
- 负载依赖的行驶时间使地面路径、物品选择与无人机同步构成强耦合的联合优化问题，不同于传统 truck-and-drone 路由通常假设恒定速度或负载独立。在 TTP-D 中，每个地面拾取物品都会改变后续到达时间，进而影响无人机的发射和会合点，因此必须同时决策物品取舍、路径和飞行同步，避免次优解。这种建模更接近实际物流采集场景，对工程人员意味着需要整体求解而非分阶段近似。
- DRL 策略作为初始解生成器配合短模拟退火精炼（LISA）展示了学习与元启发式互补的优势。DRL 能快速捕获问题结构并产出高质量初始解，而退火在极小预算下完成局部改进，在计算受限时达到元启发式基线大部分质量。这种混合模式为实际部署提供了灵活的算力-质量权衡，最大实例仍可用完整元启发式兜底。
方法
TTP-D 的求解方法分为四类：MILP 精确求解、元启发式、深度强化学习及混合求解器。
输入与输出
- 输入：问题实例包含节点坐标、物品价值与重量、无人机续航与速度、单位时间租用成本等。
- 输出：最大化利润（收集物品总价值 − 时间租金）对应的物品选择、地面车辆路径与无人机同步调度。
关键模块
- MILP：针对小规模实例建立混合整数线性规划，包含路径、物品选择、载荷与重量跟踪、旅行时间与同步约束，并加入有效不等式加速求解。
- 元启发式：定义
move库（邻域操作），采用模拟退火和变邻域搜索两种搜索策略迭代改进解。 - DRL 策略：将问题建模为 MDP，
state包含当前路径、载荷、已选物品、时间等；策略网络由注意力编码器与多个action heads组成，输出合成动作（选择下一个地面节点 / 发射或回收无人机 / 选择物品）。训练使用 PPO，引入group baseline、start strata分层课程、pinned heads与数据增强提升稳定性与泛化。 - LISA（Learner-Initialised Simulated Annealing）：先由 DRL 策略构造初始解，再用短时模拟退火精炼。
与同类方法的差异：纯 DRL 或纯元启发式往往在解质量与计算预算之间失衡，而 LISA 通过“先学习后微调”的混合范式，用少量计算预算恢复大部分元启发式基线质量，仅在最大规模实例上才需要完整预算的元启发式。
实验
实验设计
论文在 a280 与 ttd300 两个基准集上评估。小规模实例采用 MILP 求最优；中大规模以 Simulated Annealing (SA) 和 Variable Neighbourhood Search (VNS) 作为元启发式基线；提出基于注意力机制的 Deep Reinforcement Learning (DRL) 策略；以及 LISA (Learner-Initialised Simulated Annealing) 混合求解器，由 DRL 构造初始解，再用短时间退火精炼。评估指标为扣除时间租金后的利润。
关键发现
- LISA 在多数实例上以远低于元启发式的计算预算恢复了大部分解质量。
- 最大实例上，元启发式全预算仍优于 LISA。
- 敏感性分析 显示租金比率是利润的主要驱动因素，车队参数（如无人机速度）影响有限。
- MILP 能求解小规模最优，但扩展性受限。
基线对比
DRL 单独性能未明确量化，但 LISA 作为初始化解生成器结合短退火，展现了 learning-to-optimise 与经典元启发式的互补。相比纯 DRL，混合方法提高了可靠性和解质量；相比纯元启发式，大幅降低计算成本。该结果与神经组合优化中“学习初始化 + 局部搜索”的范式一致，表明 DRL 在复杂约束问题中作为 warm-start 的实用价值。
行业影响
落地场景
该求解框架适用于电商仓储自动化与最后一公里配送场景：地面车辆携带无人机，在收集多件包裹时，负载增加会降低车速，无人机可同时取回偏远货架或室外取件点的物品。另一个典型场景是工业巡检与资产盘点，地面机器人搭配无人机在厂区收集传感器数据，负载影响能耗与速度，需联合优化路径、物品选择与无人机起降同步。
商业价值
核心收益在降本增效：通过联合优化减少地面车辆绕行距离与在途时间，降低燃油/电耗；同时精确控制无人机起降点避免等待，缩短任务 makespan。增收角度，模型支持选择高利润物品并扣除时间租金成本，能直接提升单次任务的净利润。对巡检类业务，更快完成数据采集可提高资产利用率和响应速度，间接改善服务水平。
与现有产品/工作流接口
该模型可作为调度系统的路线规划插件：输入订单/巡检点坐标、物品重量、车辆与无人机参数，输出地面路径、物品选择、无人机发射与回收时间点。小规模实例可直接调用 MILP 精确求解，大规模场景用 DRL 策略生成初始解后接模拟退火微调，适合集成到 WMS/TMS 或机器人调度平台。开源代码 TTP-D 提供可复现基准，便于在现有 stack 中做 A/B 测试与参数校准。
局限
- **DRL 策略的泛化与预算敏感**：论文提出的 attention-based DRL 策略仅在固定规模基准集上训练和评估，当实例规模增大时，混合求解器（LISA）需要更长的退火时间才能接近元启发式基线，说明 DRL 初始解在复杂约束下质量有限。此外，DRL 训练需要大量样本和调参，对新问题规模或参数分布可能需要重新训练，实际部署的计算成本和维护成本未被充分讨论。
- **问题假设的简化与工程差距**：TTP-D 模型假设无人机仅用于取回边缘物品、不承担载荷累积，且飞行速度恒定、续航无限（或仅受时间窗约束），未考虑无人机容量、能耗、充电/换电、与卡车的通信延迟及碰撞规避等现实约束。这些简化可能导致求解结果在实际物流场景中不可行或偏差较大，限制了模型的直接工程应用价值。
- **方法创新有限，与已有神经组合优化工作区分度不足**：论文所采用的 MILP、模拟退火、变邻域搜索和 attention-based DRL 均为成熟技术，混合求解器（DRL 初始化 + 短退火）的思路在已有研究中已有类似体现（如神经引导的局部搜索）。虽然首次将无人机引入 TTP，但算法层面没有提出针对 TTP-D 特性的新算子或网络结构，其贡献更多在于问题定义和基准集，而非方法突破。