驾驶、装载、飞行：带无人机的旅行窃贼问题 Drive, Pack, Fly: The Travelling Thief Problem with Drone
联合优化取货选择、卡车路径与无人机飞行同步，最大化扣除时间租金后的净收益
前置知识
旅行窃贼问题（TTP）
TTP 将旅行商问题（TSP）与背包问题（KP）耦合：小偷沿回路访问城市并选择性拾取物品，每件物品增加载重，而车速随载重线性下降（空载 $v_{max}$、满载 $v_{min}$），因此“装什么”与“怎么走”不可分割——装箱方案的价值取决于承载它的路线，路线的成本又取决于所选物品。Bonyadi 等 2013 年提出该问题，Polyakovskiy 等 2014 年基于 TSPLIB 建立 9720 个实例的基准套件，本文的 a280 即源于此。
TTP-D 是 TTP 的直接扩展：本文完整保留载重-速度耦合与容量约束，再叠加无人机协同，理解 TTP 的耦合机制是理解新问题难点的第一步。
卡车-无人机协同路由（Flying Sidekick TSP）
Murray 与 Chu 2015 年开创的协作路由模型：卡车搭载无人机并行服务客户，无人机从卡车所在节点起飞，飞往目标地点后沿路线在前方的汇合节点降落归队。计算核心是时空同步——两车路线不同却必须在汇合点协调，任何一侧到达时间的变化都会传播到另一侧，使路由决策紧耦合。
TTP-D 借用这种“起飞节点-目标客户-汇合节点”的单件出动结构，但把它嵌入收集场景的载重动态中；读懂同步约束才能理解模型的耦合来源。
MILP 与 SOS2 分段线性化
混合整数线性规划（MILP）用整数与连续变量加线性约束建模组合优化，可由 Gurobi 等求解器证明最优性。卡车行驶时间与速度倒数 $\psi(W)=1/v(W)$ 成正比，它是载重的凸函数，必须线性化：SOS2（Special Ordered Set type 2）约束强制插值权重 $\mu_{i,b}$ 只能落在相邻两个断点上，用弦从上方逼近凸曲线。
论文的精确模型正是用 $K=10$ 个断点的 SOS2 弦逼近处理非线性速度，并推导出目标误差上界 $\epsilon_G$，这是理解其最优性证书与小实例结果的关键。
模拟退火（SA）与变邻域搜索（VNS）
SA 是单轨迹元启发式，以温度控制的概率 $\exp(\Delta G/T)$ 接受劣化移动来逃离局部最优，温度按几何规律（本文 $\alpha=0.97$）冷却并可重热；VNS 则交替执行随机扰动（shaking）与确定性局部下降（VND），通过系统改变邻域结构探索空间。本文两者共享同一套十算子移动库与可行性保持评估器。
两者既是本文的解质量基线（SA 建立了几乎全部 BKS），又分别是 LISA 的蒸馏专家与修复引擎，不看懂它们就无法理解实验协议与混合框架。
PPO 与 POMO 训练范式
PPO 用裁剪代理目标限制策略更新幅度，可安全复用 rollout 批次跨多个梯度轮次；POMO 利用路由问题解的等价性，从多个强制不同的起点 rollout，以组均值回报作为逐实例基线，从而免去 critic 网络。本文用 $P=32$ 个 rollout，把起点按首次卡车移动与首次起飞目标分层，辅以 8 个二面角数据增强。
论文的 DRL 构造策略基于 PPO+POMO 训练，并针对五头分解动作空间改造了基线、裁剪更新与强制多样起点三个组件，这是复现其神经方法的必要背景。
行为克隆（Behaviour Cloning）
一种监督模仿学习：把专家（此处为全预算模拟退火）产生的状态-动作对作为训练数据，用最大似然拟合策略网络的五个动作头，使神经网络复现专家的搜索行为，从而把昂贵的在线搜索成本蒸馏为廉价的离线训练与单次前向推理。本文要求专家解经逆映射转为动作序列并在模拟器重放认证后才入库。
LISA 的核心机制就是行为克隆：SA 专家被蒸馏进构造策略，在线阶段克隆策略只负责生成热启动解，短退火负责修复，理解克隆才能理解 LISA。
研究动机
本文瞄准的是被经典路由模型忽视的“收集”场景：快递员赴偏远诊所取样、回收车清空分散的收集点、救援车辆在受损路网回收物资。这类运营有两个关键特征常被建模遗漏。其一，车辆边行驶边装载，累积载重带来真实的运营惩罚——油耗上升、车速下降，早取一件重物会拖慢之后每一段路程，形成累积性时间税。其二，机载无人机可以高效取回公路难以企及的轻量高价值物品，但其飞行必须与卡车行程严格同步，而机队每多部署一分钟都在产生成本。现有文献恰好把这两个特征割裂处理：TTP（Bonyadi 等，2013）只建模载重依赖的速度与装箱，没有第二台车；而 2015 年 Flying Sidekick TSP 以来的卡车-无人机路由文献处理同步出动，却几乎全部面向“配送”且不带背包约束。换言之，一边有“越拉越慢”却没有无人机，一边有无人机却没有载重惩罚，两者的交集正是收集型无人机物流的现实，却没有现成模型。
本文的目标是论文的目标是定义并求解带无人机的旅行窃贼问题（TTP-D）：一辆容量为 $W$ 的卡车与一架单件载荷为 $W^D$ 的无人机共同驻扎于仓库，必须访问全部 $N$ 个客户，但只收集其中一个子集的物品。无人机可从卡车所在节点起飞，飞往偏远客户取一件物品，再在卡车路线前方的汇合节点交付。目标函数为最大化净收益 $G=\sum_{i\in\mathcal{N}} p_i z_i - R\cdot\tau_{0'}$，即收集利润减去与任务总时长（makespan）成正比的租金，这要求联合决策每位客户的访问模式（卡车/无人机/汇合点）、装箱配置以及时空合法的起飞-汇合配对。为此论文交付四件事：可为小实例提供最优性证书的 MILP；SA 与 VNS 两个元启发式；基于图注意力的 DRL 构造策略；以及 LISA 混合求解器；并在 a280 派生集与自建的 ttd300 基准上完成计算研究与参数敏感性分析。
与已有工作不同的是，独特切入角度有三层。问题层面，TTP-D 首次把“载重依赖速度 + 背包装箱”与“时间同步的无人机单件出动”焊接在一起，证明其 NP-难（同时泛化 TSP 与 0-1 背包），并点明根本难点：多收一件物品会平移之后所有到达时刻，可能令下游已计划的无人机汇合失效——收集场景下装箱决策与同步调度互相改写。算法层面，本文重排了学习与搜索的角色：既有神经混合方法多让学习服务于搜索（学分支、学算子选择），LISA 则让元启发式担任“训练者”，把全预算 SA 的解经行为克隆蒸馏进构造策略，推理时只分配 5%–50% 的退火预算修复克隆解，单一参数 $\beta\in(0,1]$ 使其成为可在“纯策略”与“纯退火”之间连续插值的 anytime 求解器。基准层面，作者构造了 ttd300——以无人机续航 $E_D=f\cdot d_{max}$ 为唯一受控变量的合成测试床（140 个实例），专门用于隔离“电池半径”这一运营瓶颈。
核心方法
直觉上，卡车每收一件货就更慢、租金按总时长计费，因此最优计划会把尽可能多的客户“卸载”给无人机、只在卡车上保留低时间代价的物品，并尽量缩短 makespan。技术路线分四层。第一层是精确 MILP：对凸的速度倒数 $\psi(W)=1/v(W)$ 用 $K=10$ 个断点做 SOS2 分段线性化，用 McCormick 包络线性化双线性项 $\lambda_{kj}=z_k x^D_{kj}$ 以追踪无人机交付的载重，并添加三条收紧 makespan 下界的有效不等式，小实例上由 Gurobi 给出最优性证书。第二层是元启发式：SA 与 VNS 共享十个算子的移动库（收集翻转、路线算子、sortie 重排/重锚、卡车-无人机转移算子）和可行性保持评估器，在固定预算 $B(N)$ 内搜索联合的“路线-装箱-出动”空间。第三层是 DRL：把 TTP-D 建成有限期确定性 MDP，注意力编码器一次嵌入实例，解码器按 $a_t=(\rho_t,z^D_t,z^T_t,k_t,j_t)$ 自回归出五个动作头，PPO+POMO 训练，推理用宽 256 的束搜索加 8 个二面角视图。第四层是 LISA：离线用行为克隆蒸馏 SA 专家，在线以束解码热启动预算为 $\beta B(N)$ 的短退火。所有方法在同一 CPU 主机上、按精确载重-速度律统一计分。
核心创新是“问题定义 + 学习-搜索角色重排”的组合。问题层面，与搬运型卡车-无人机文献（无背包、无载重减速）和经典 TTP（无双车协同）都不同，TTP-D 中“多收一件货”同时改变装箱可行性、卡车后续速度曲线和无人机汇合时刻，三类决策被时间轴强耦合；论文用出发载重而非到达载重计算行驶时间、用 SOS2 弦从上方保守逼近 $\psi$（保证 $G^*_{\text{MILP}}\le G^*_{\text{exact}}$ 并给出误差上界式 (18)），这是精确侧的实质贡献。算法层面，LISA 与 NeuroLKH 等先验混合方法的本质区别在于角色安排：SA 既是老师也是修复器。专家解先经逆映射转成 MDP 复合动作序列，并在模拟器中重放、确认能复现专家目标值（“认证”）后才进入克隆数据集；推理时克隆策略提供高质量起点，短退火负责打磨。一个预算参数 $\beta$ 统一两端：$\beta\to 0$ 退化为克隆策略，$\beta=1$ 恢复全预算 SA。MDP 侧的双向可行性掩码（每个可行动作都有可行补全、每个可行 MILP 解都对应合法动作序列）免除了回溯与事后修复，同样是关键设计。
方法步骤详情
流程分四步。第一步精确建模：变量含两车弧 $x^T_{ij},x^D_{ij}$、模式变量 $y^T_i,y^D_i,y^C_i$、收集指示 $z_i$、出发载重 $W_i$、时刻 $\tau_i$ 与 SOS2 权重 $\mu_{i,b}$；约束 (2) 强制每客户恰选一种访问模式，(3)–(9) 给出两车流守恒与“锚定”条件、禁止无人机在客户间跳飞，(10) 限制无人机载重 $w_i z_i\le W^D$，(11)–(13) 用 McCormick 变量 $\lambda_{kj}$ 把无人机交付质量线性传播进卡车载重递推，(14)–(15) SOS2 插值逼近速度倒数，(16)–(17) 用大 M 约束同步两车时刻；有效不等式 (19)–(21) 直接下压 makespan（$N=20$ 时根 LP 界收紧至多五倍，是 $N=15$ 关到最优的功臣）。第二步元启发式：解为三元组 $x=(r,S,z)$，十算子覆盖收集翻转、交换/2-opt/Or-opt、DP 精确重排 sortie 锚点、单 sortie 重锚与四种卡车-无人机转移；SA 初始温度 $T_0=-|\overline{\Delta G^-}|/\ln 0.8$（开局接受约 80% 劣化移动）、几何冷却 $\alpha=0.97$ 并重热；VNS 扰动强度 $\eta$ 在 1–8 间循环。第三步 DRL：每个节点四维归一化特征，GAT 编码器每 episode 只算一次；解码上下文拼接载重比、时间比、无人机等待/在飞等 7–9 个量；两个指针头选 $k_t,j_t$、三个 MLP 头出二元决策；PPO 组基线取 $P=32$ 个 rollout 均值，推理束宽 256×8 视图。第四步 LISA：全预算 SA 跑训练语料、逆映射为动作序列、重放认证、按规模行为克隆，在线束宽 128 解码后以 $\beta B(N)$ 预算的 SA 修复。
技术新颖性
技术新颖性可从四方面评估。其一，建模严谨性：多数载重依赖路由的处理停留在启发式评估，本文给出可证明的线性化方案——SOS2 弦逼近保守（$\hat\psi_i\ge 1/v_i$），误差上界 $\epsilon_G\le R\,d_{max}(N+1)w_{tot}^2(\Delta v)^2/(4K^2v_{min}^3W^2)$ 明确可控，且以模拟器重放 MILP 最优解验证 MDP 的正确性，理论与工程双向闭环。其二，模式感知有效不等式 (21) 把“每客户至少往返仓库一次”的下界按访问模式分别用 $v_{max}$ 或 $v_D$ 计入，使 $N=15$ 全部关到最优、$N=20$ 根界收紧五倍，属精确侧实打实的推进。其三，学习侧的五头自回归复合动作把路由、装箱、起飞与移动决策压进单一策略，配合双向掩码实现免回溯构造；相比 Santiyuda 等（2024）处理双目标 TTP 时所需的编码-解码间接表示，这里原生输出耦合的“路线+装箱+出动”。其四，LISA 的“认证克隆”流程（重放复现专家目标才入库）与单一预算参数接口，是对模仿学习+搜索混合范式的干净工程化；GAT 与逐节点 MLP 的对照实验还干净隔离了图注意力编码器的贡献——同解码器、同训练管线、同推理速度，GAT 全面占优。
实验结果
a280 派生集（$R=72.70$，租金超过最大可收利润，$G$ 恒为负、实质比拼时间）：MILP 在 $N=5$ 平均 0.5 秒、$N=10$ 平均 49.1 秒证明最优；$N=15$ 仅 2/5 认证、平均间隙 5.94%；$N=20$ 全部触及 24 小时限制、间隙 40.05%，此时五分钟 SA 反而更优。最优解大量把客户卸载给无人机（$N=5/10/15/20$ 分别为 3/5、4/10、7/15、10/20）以保持卡车轻载。方法对比（相对 BKS 平均间隙）：SA 0.04% 最强；VNS 7.17%，且 $N\ge30$ 后由 5.14% 恶化至 27.07%；GAT 8.42%；MLP 9.95%。LISA 半预算（$\beta=50\%$）平均 1.59%，$N=10$ 时 15 秒做到 0.02%，$\beta\ge33.3\%$ 时 $N=15/20$ 达 0.11%/1.38%。ttd300（含续航约束，参考为全预算 SA）：GAT 从 2.37%（$N=10$）恶化到 51.05%（$N=100$）；克隆策略无修复基线平均 64% 间隙，$\beta=5\%$ 降至 10.71%，$\beta=50\%$ 为 5.06%，$N\le40$ 用不超过三分之一预算进入 4% 内。续航轴：$f$ 由 0.25 放宽到 0.50 在所有规模改善目标（$N=10$ 为 $|G|$ 的 8.3%，$N=50$ 为 34.7%）；$N=50$ 第一步值 16,622、其中 14,728 来自租金项（makespan 1,740→1,445）；$f=0.25$、$N=10$ 时五个布局中四个不派 sortie。利润/租金比由 0.10（$N=10$）升至 0.74（$N=100$），净亏损 $-38{,}444\to-29{,}890$。敏感性：$R$ 主导，$N=100$、$f=1.0$ 时 $R=1$ 得 $+81{,}408$、$R=200$ 得 $-382{,}171$，$R=25$ 即令 $N\ge40$、$f\ge0.5$ 转亏为盈；多件收集在 $N=100$ 增益 40,058–53,945，$f=1.0$ 时 $+13{,}342$ 转正；物理参数居次：容量 $-82{,}931\to-17{,}648$、无人机速度 $-57{,}656\to-23{,}416$、最低卡车速度 $-41{,}311\to-18{,}705$；续航钳制速度价值（$N=100$ 纯卡车$\to\varphi=3$：$f=0.25$ 仅增益 33,617，$f=0.5$ 达 61,863）。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| a280 派生实例解质量（N=5–50，每规模 5 实例 × 10 种子） | 相对 BKS 的平均间隙 (%) | SA 0.04%（建立全部 N≥30 的 BKS）；LISA β=50% 平均 1.59% | VNS 7.17%；GAT 8.42%；MLP 9.95% | SA 总体最优；LISA 以 5–50% 预算把纯策略 8–10% 量级的间隙压缩到 1.6–5.1% |
| ttd300 端到端策略对比（N=10–100，共 140 实例） | 相对全预算 SA 参考的平均间隙 (%) | LISA β=50% 平均 5.06%（N≤40 时以 ≤1/3 预算进入 4% 内） | GAT 端到端策略 28.34%（N=100 达 51.05%） | 同等推理预算下质量差距 20 个百分点以上 |
| 无人机续航放宽（f=0.25→0.50） | 目标 G 改善幅度（%|G|）与 makespan | 所有规模改善：N=10 为 8.3%，N=50 为 34.7%；N=50 的 makespan 由 1,740 降至 1,445 | f=0.25 紧凑 sortie 半径（N=10 时五个布局中四个零出动） | f≥0.5 后收益饱和（N≥30 时其余设置相差不超过 9.8 点） |
| 多件收集（每城 5 件物品，L1 布局） | 净收益 G 与容量利用率 | N=100 增益 40,058–53,945；f=1.0 时 +13,342 转正；容量利用率 44%→84–100% | 单件协议（每城至多收 1 件，容量约束从不绑定） | 全部实验中唯一的盈利操作点，直接改变运营可行性结论 |
| 租金比扫描（N=100，f=1.0） | 净收益 G 范围 | R=25 时即可盈利（N≥40 且 f≥0.5，无需硬件升级） | R=50 基准下所有规模净亏损（利润/租金比 0.10–0.74） | 商业条款比硬件升级更有效：R 主导盈利性，物理参数仅边际影响 |
局限与改进
作者承认的局限：精确方法止步于 $N=20$，且 $K=10$ 段线性化使 $N=15$ 的 0.36% 间隙部分来自代理模型与精确载重-速度律之间的偏差；学习策略按规模分别训练（ttd300 上超参还是为 a280 调的），跨规模、跨分布迁移不稳健；LISA 在最大实例上即便半预算仍留 10–15% 间隙，$N=75/100$ 仍需全预算退火；束搜索在 CPU 上超线性扩展，$N>50$ 后推理时间反超退火预算；ttd300 的 SA 参考在 $N\ge75$ 时最后改进出现在预算的 88% 之后，说明参考本身未收敛，$f\ge0.5$ 处出现 450–2,096 的目标值回退。我的补充观察：模型假设较强——单无人机、每 sortie 单件、零装卸/交接时间（被“预吸收”进距离）、无人机恒速、静态确定性环境与欧氏对称距离；$R$ 的标定（a280 上 72.70）使所有基准 $G$ 恒为负，“利润最大化”实际退化为时间最小化，部分结论依赖该参数区；ttd300 上 SA 种子间标准差达 1.9%–5.5%，而敏感性分析每配置仅单种子，多件收集在 $N=100$ 不同 $f$ 间约 ±14,000 的无规律波动提示部分结论可能被启发式方差污染。
独立分析的弱点
独立分析的弱点与改进方向。一、规模天花板：MILP 止步 $N=20$，LISA 在 $N\ge50$ 仍需接近全预算；可引入分解类方法（列生成、Benders）、更强的基于 sortie 结构的割平面，或测试时自适应（test-time adaptation）让策略在大实例上自我改进。二、策略泛化差：每规模一个检查点、跨分布（a280→ttd300）严重退化（GAT 在 $N=100$ 差 51%）；可用尺寸条件化网络（把 $N$、$R$、$E_D$ 作为全局条件输入）、相对坐标表示或多分布混合训练实现“一次训练、处处推理”。三、运营假设偏理想：单机、单件 sortie、零交接时间、无人机恒速、确定性静态环境均与现实有差距；可扩展为多机队与一次取多件的批量 sortie、显式交接时间常数，以及带随机行驶时间的鲁棒/随机规划版本。四、评估协议：ttd300 以未收敛的 SA 为参考，方法间真实差异可能被低估；单种子敏感性分析受方差影响（作者自己也观察到 $f$ 轴上的小幅回退）；应加长参考预算、建立跨方法共享的解池并报告多种子方差。五、经济参数标定：$G$ 恒为负的参数区让“利润”语义弱化，宜用真实运营数据标定 $R$、$p_i$、$w_i$ 后重新评估盈利边界。
未来方向
作者点名的方向包括：多无人机编队、一次 sortie 服务多个客户、显式交接时间、随机环境下的 TTP-D，以及把最优性认证推进到 $N=20$ 以上、实现跨尺寸的稳健策略迁移。基于本文成果还可延伸：其一，既然续航（而非速度）钳制无人机价值，电池热插拔/充电站选址与路径的联合优化是直接落点；其二，把租金比 $R$ 从参数变为决策变量，研究租赁-采购权衡与机队规模设计的经济学；其三，多件收集使 $N=100$ 转亏为盈，值得研究带容量交互的在线/分批收集版本；其四，LISA 的“专家蒸馏+短搜索修复”框架天然可移植到弧路由+无人机（Sobhanan 等 2025）等其他耦合路由问题；其五，对 $R$、$\varphi$、$E_D$ 三轴做 Pareto 前沿分析，为运营方量化决策与机队采购提供支持；其六，用学习算子选择的自适应大邻域搜索替代固定十算子库，有望进一步压缩修复预算。
复现评估
复现条件总体友好。代码、数据集与训练好的策略检查点公开于 github.com/corbit-lab/ttpd。硬件门槛低：全部 CPU 实验（MILP、元启发式、LISA 推理与评估）在 8 vCPU Xeon Platinum 8581C、62 GB 内存上完成；策略训练仅需单张 RTX 4000 Ada（20 GB 显存）。基准生成规则完整公开：ttd300 用 $[0,300]^2$ 均匀整数坐标、向上取整欧氏距离、$w\sim U[1000,1009]$、$p\sim U[1,1000]$、$W=\lfloor 2275.0357N\rceil$、$R=50$、$E_D=f\cdot d_{max}$，a280 派生参数见表 3，超参数见补充材料表 S2。两个摩擦点：MILP 需要 Gurobi 13.0（商业求解器，学术免费但需许可），且复现 $N=15/20$ 的精确结果需 24 小时级运行；DRL 按规模分别训练，从头训练全部检查点仍需可观 GPU 时间——不过仓库附带检查点，可跳过训练直接复现推理与 LISA。总体难度：元启发式与 LISA 推理为中等偏低，DRL 全管线复现为中等。
论文图表
以任务时间为横轴展示 10 客户实例中卡车速度曲线：载重从 0% 一路累积到 67%，速度随之从 $v_{max}$ 降至不足一半；两个阴影窗口为无人机 sortie 时段，灰色段为等待——第一次无人机先到汇合点悬停，第二次卡车先到原地等待，而租金时钟在等待期间照常计时。
一图胜千言地展示 TTP-D 的核心耦合：装箱决策改变卡车速度曲线，速度曲线改变到达时刻，到达时刻又决定合法的起飞-汇合配对，是理解问题动机的最佳入口。