想象你是一个上门回收旧衣物的司机。每收一件衣服，你的车就重一分，油耗高一分，速度慢一分。你的任务是在一天内跑遍所有客户，尽可能多收有价值的衣物，同时又不能让油费和时间成本吃掉你的利润。这时候，如果你有一架无人机可以帮你飞去那些绕路才能到的偏远客户家取货，你会怎么安排这架无人机的起飞和降落时间，才能让整趟旅程既快又省？

这不是一个假设性的思想实验。它精确描述了印度尼尔玛大学和印度管理学院班加罗尔分校两位研究者最近提出的一个新问题，他们管它叫“带无人机的旅行小偷问题”（Travelling Thief Problem with Drone，简称 TTP-D）。这个名字听起来有点古怪，“小偷”从哪冒出来的？其实这里藏着一段有意思的学术渊源，我们后面会讲到。

先说说这篇论文到底在解决什么麻烦事。

一个被忽略了十年的矛盾

无人机送货这件事，这几年已经从科幻场景变成了现实生意。亚马逊的 Prime Air 让无人机送货进入了公众视野，卢旺达的医疗无人机会给偏远诊所送血液和药品，快递公司也在试验卡车搭载无人机的组合配送模式。

但你注意到没有，几乎所有这些应用讲的都是“送出去”，也就是配送。很少有人认真研究“收回来”这件事，也就是收集。

收集类任务其实到处都是：快递员去乡村诊所取样本，环卫车去各个垃圾回收点收垃圾，救援车队在受损道路网络里抢运物资。这些场景有两个共同点，而且恰恰是经典路径规划模型经常忽略的。

第一，车辆是越装越重的，重量会拖慢速度。你可以想象一辆垃圾车，刚出发时空车能跑得飞快，可每收一个点的垃圾就重一分，跑到最后几乎变成了老牛拉车。这意味着你在路线的最前面做的每一个“多收一件东西”的决定，都会拖慢后面所有的路程，这个惩罚是累积的、不可逆的。

第二，无人机确实能帮上大忙，专门去够那些开车绕路成本很高的偏远点，但前提是它的起飞和降落必须和卡车的行程严丝合缝地对上。无人机飞得再快，如果卡车没在正确的时间出现在正确的地点接应，那这趟飞行就是白费。

现有研究恰好把这两件事分开处理了。

一支研究脉络叫“旅行小偷问题”

引用块：旅行小偷问题（Travelling Thief Problem，TTP）：由 Bonyadi 等人在 2013 年提出，把经典的旅行商问题（走遍所有城市找最短路径）和背包问题（选择哪些物品装包获利最大）捆在一起，核心机制是车辆速度会随着装载重量下降而变慢。

这个模型抓住了“重量拖慢速度”这个关键点，但它假设只有一辆车，完全没考虑多辆车协同的情况。

另一支研究脉络是“卡车与无人机协同配送”，这类研究把无人机和卡车的同步飞行搞得很精细，但几乎清一色地只研究配送，也就是把货物送出去，而不是收回来，自然也就不涉及“选哪些物品收”这种背包式的取舍决策。

TTP-D 要做的，就是把这两条线拧到一起：既要处理车辆越装越重导致的减速惩罚，又要安排无人机和卡车的精密协同，而且这一切都是关于“收集”而不是“配送”。

**这个问题被证明是 NP 困难的，因为它同时包含了旅行商问题和 0-1 背包问题这两个已知的难题。**

更麻烦的是，这两个子问题被死死焊在了一起：你多收一件东西，会让卡车变重变慢，这会推迟后面所有站点的到达时间，而这些时间又可能让某个原本计划好的无人机会合点变得不可行。改一个决定，后面一连串安排全部要重新核算。这种耦合正是这个问题真正难啃的地方。

一张图看懂这套系统怎么运转

论文里有一张图特别直观，画的是一个十个客户的实例里，卡车速度随任务时间变化的曲线。

看这张图你会发现，卡车速度呈阶梯状下降：刚出发时是满速的，每收一件货物，速度台阶式往下掉一截，收到第六七件货物的时候，速度已经不到出发时的一半了。图里还标出了两段无人机飞行任务的时间窗口，其中有一段特别有意思：无人机先飞到会合点，结果卡车还没到，无人机就得在那儿干等着；另一段情况反过来，卡车先到了，得停在原地等无人机降落。

这两种等待都在烧钱，因为计费的时钟是连续跑的，不会因为谁在等谁就暂停。

这就引出一个很实际的问题：无人机和卡车谁先到、要不要等、等多久，全都取决于前面的“收货计划”是怎么安排的。改变一件物品要不要收，就可能让整个会合时间表往后错位。

打个比方，这就像两个人约好在地铁站换乘接头，一个人从家里出发，一个人骑车。如果骑车的人半路上又多绕去买了杯咖啡，接头时间就得往后推，而后面所有的行程安排都要跟着调整。如果不去精确计算这种连锁反应，你要么让人白等浪费时间，要么错过接头彻底打乱计划。TTP-D 干的事，就是精确算清楚这种连锁反应该怎么安排才最划算。

数学模型：把这个乱麻问题写成公式

要解决问题，先得把它讲清楚规则。论文给 TTP-D 设定了几条基本假设。

问题是静态且确定的，也就是说所有的距离、利润、重量在任务开始前就已知，且过程中不会变化。一辆卡车和一架无人机都从同一个仓库出发，最后也要回到仓库。每个客户点只有一件可收的物品，且只能被到访该客户的那辆车收走。

无人机每次只能带一件包裹飞行，速度恒定，不受载重影响，但载重不能超过它的载重上限。一次飞行任务包含恰好两段：一段出发去目标客户，一段返回和卡车会合，会合点必须是卡车路线上稍后经过的一个节点。

卡车的速度是载重的线性函数，空载时最快，满载时最慢，而且计算某一段行程耗时时用的是这段行程出发时的载重，而不是到达时的载重。

基于这些规则，论文构建了一个混合整数线性规划模型（MILP）。

引用块：混合整数线性规划（Mixed-Integer Linear Program，MILP）：一种数学优化建模方式，变量里既有连续的（比如时间、重量），也有 0/1 二元的（比如“这个客户是不是被无人机收货”），目标是在满足一堆线性约束条件下求出让目标函数最大或最小的解。

这个模型里唯一麻烦的地方是卡车速度和行驶时间之间的关系，因为速度随重量线性下降，行驶时间等于距离除以速度，这个关系是非线性的（凸函数）。论文用了一种叫 SOS2 分段线性化的技巧，把这条曲线拆成若干段折线来近似，这样就能塞进线性规划的框架里求解。

**这个近似带来的误差是有严格数学证明的上界的，也就是说求出来的解和真实最优解之间的差距是可控可估计的，不是拍脑袋近似。**

论文还专门设计了三条“有效不等式”，用来给最优时间（也就是决定租金成本的关键变量）设一个更紧的下界，实验中这些不等式能把线性松弛的下界收紧多达五倍，是让 N=15 的实例能够被精确求解到最优的关键推手。

目标函数：这不是让路程最短，而是让钱赚得最多

TTP-D 要最大化的目标是净利润，公式很直白：

G = 收集到的所有物品利润总和 – 租金比率 × 完成任务所需的总时间

这里藏着一个很关键的设定：租金是按时间计费的，时间越长，成本越高。

引用块：租金比率（Renting Ratio，R）：每单位任务时间要付出的成本，这是把“时间”直接换算成金钱的汇率，决定了整个任务在经济上是不是划算。

这意味着，方案好不好不能只看收了多少东西，还得看跑得快不快。论文的实验里，租金比率被设得很高（比如 a280 基准里 R=72.70），高到超过了车队能收集到的最大利润，所以在这些实验设置下，目标函数值几乎全是负数，越接近零（越不负）就说明方案越好。

这个设计其实很贴近现实，你想想物流公司雇一辆车一天的成本，可能远远超过一趟路上能多捡回来的那点零星货物价值。这时候，省时间比多收货更重要。

三套解法：从精确求解到学出来的策略

论文的求解方案分了三个梯队，越往后越能应付大规模问题，但也越依赖近似和取舍。

第一梯队是精确求解器，也就是直接把 MILP 模型扔给商业求解器 Gurobi 去算。这种方法能给出带证明的最优解，但只能应付很小规模的问题。实验结果显示，N=5 和 N=10（客户数量为 5 或 10）的实例能在几十秒到几分钟内被精确求解；N=15 时，五个实例里只有两个能在 24 小时内证明最优，剩下三个跑满 24 小时后还留有 5.94% 的差距；到了 N=20，24 小时跑完后差距还有 40.05%，几乎宣告精确求解器在这个规模上已经力不从心。

这就好比你想用手算的方式规划一个 20 个包裹的取件路线，理论上可以，但排列组合的数量爆炸式增长，你算到天荒地老也未必能确认自己找到了最好的那条路。

第二梯队是元启发式算法（metaheuristics），论文用了两种：模拟退火（Simulated Annealing，SA）和变邻域搜索（Variable Neighbourhood Search，VNS）。

引用块：模拟退火：一种借鉴金属冷却过程的搜索算法，允许在搜索早期接受一些“变差”的调整（就像金属在高温下原子还能到处乱跑），随着“温度”逐渐降低，接受变差方案的概率也逐渐降低，最终收敛到一个较好的解。

引用块：变邻域搜索：一种在搜索过程中不断切换“邻域结构”（也就是尝试不同类型的微调方式）的算法，交替进行随机扰动（跳出局部最优）和确定性局部下降（精细打磨当前方案）。

这两种算法都从一个“最近邻”的粗糙初始方案开始，配合一套共享的“移动操作库”，里面有十种不同的调整手法，比如交换两个客户的访问顺序、把一段路径倒过来走、把某个客户从卡车改派给无人机等等。

实验数据很能说明问题：在 N=5 到 N=20 的实例上，SA 几乎每次都能达到已知最优解（也就是所有方法里跑出来的最好结果），而 VNS 在小规模上表现相当，但一旦规模扩大到 N=40、N=50，VNS 的差距从 5.14% 一路飙升到 27.07%，明显撑不住了。相比之下 SA 全程保持在 0.04% 的平均差距，几乎逼近完美。

这个现象背后的道理其实挺朴素的：VNS 靠一条单一的搜索轨迹去覆盖越来越大的解空间，就像一个人想独自巡视一座越建越大的城市，规模一旦超过某个临界点，靠一个人的脚步再怎么勤快也顾不过来了。

第三梯队是深度强化学习（Deep Reinforcement Learning，DRL）构造的策略，这是整篇论文里技术含量最高，也最值得展开讲的部分。

让神经网络自己学会怎么规划路线

传统元启发式算法有个天生的局限：每来一个新问题实例，都得从头搜索一遍，之前解决过的经验一点都用不上。

DRL 的思路完全不同，它想训练一个神经网络策略，让这个策略见过足够多的问题实例之后，能对一个从未见过的新实例，只需一次前向计算（不需要反复试错搜索）就给出一个相当不错的方案。

论文把 TTP-D 建模成一个马尔可夫决策过程（Markov Decision Process，MDP）。

引用块：马尔可夫决策过程：一种描述“在每个时刻做决定，决定会影响后续状态和收益”的数学框架，核心假设是当前状态已经包含了做出最优决策所需的全部信息，不需要回顾更早的历史。

具体来说，每次卡车到达一个新节点，就触发一次决策，这个决策打包了五件事：要不要让飞在半空中的无人机降落、要不要收下无人机带回来的物品、要不要收下当前节点的物品、要不要派无人机去下一个目标、卡车接下来该开去哪个节点。

这五个子决策的顺序是精心设计过的，无人机的派遣决定必须排在卡车移动决定之前，如果反过来，就没法处理“无人机去收最后一个客户的货，卡车径直开去仓库等着”这种合理的场景。

神经网络的结构采用了编码器-解码器架构，编码器用的是一种叫图注意力（Graph Attention，GAT）的机制。

引用块：图注意力网络：一种让每个节点（这里是每个客户点）在计算自己的特征表示时，能够“关注”并综合其他所有节点信息的神经网络结构，本质上是让每个点都能看到全局，而不是只顾自己。

论文特意做了一个对照实验，把 GAT 换成一个只看自己四个特征、完全不和其他节点交换信息的简单感知机（MLP），结果发现在完全相同的解码器、掩码机制、训练流程下，GAT 的解质量明显更好，而且推理速度完全一样。这说明让节点之间“互通有无”确实是有价值的，不是白费功夫的花架子。

训练方法上，论文用了近端策略优化（Proximal Policy Optimisation，PPO）配合一种叫 POMO 的多起点基线方法。

引用块：POMO（Policy Optimisation with Multiple Optima）：利用路径规划问题里“同一个好方案可以有多种不同起点”这个特性，让同一个策略从多个强制不同的初始动作出发，各自跑出一整条方案，再用这一组方案的平均得分作为参照基准，用来判断某条具体方案是“好于平均”还是“差于平均”。这样就不需要额外训练一个专门用来估计基准值的网络，省了参数，也避免了估计偏差。

不过这套 DRL 策略的表现说实话没那么惊艳。

在 a280 这个改造自经典 TSP 基准库的数据集上，GAT 策略在小规模上还凑合，但随着规模变大，差距逐渐拉开到 8.42% 到 19.92% 不等；在专门为无人机续航设计的 ttd300 新基准上，情况更糟，GAT 在 N=10 时差距是 2.37%，但到了 N=100，差距飙到了 51.05%，几乎是把最优解砍掉了一半。

这暴露了一个纯构造式神经网络策略的软肋：它只能一次性做出决定，没有机会像元启发式算法那样反复修正、试错、回头看。

LISA：把学出来的策略和搜索缝合起来

正是因为看到了 DRL 又快又不够精、元启发式又精又不够快这个矛盾，论文提出了一个叫 LISA 的混合方案。

引用块：LISA（Learner-Initialised Simulated Annealing，学习者初始化模拟退火）：先用完整预算跑一遍 SA 算法，把得到的优质解转换成一系列“状态-动作”的训练样本，再用行为克隆的方式训练一个神经网络策略去模仿这些高质量决策；实际使用时，让这个训练好的策略先快速生成一个初始方案，然后只用一小部分的搜索预算去做局部修补。

这个设计思路可以打个比方：假设你要临摹一幅名画，你可以让一个刚学画画的新手从空白画布开始一笔一笔琢磨，也可以先找一个熟练的临摹者快速勾出大致轮廓，再由你自己花一点点时间去补细节。前者慢而且未必画得好，后者省了大部分时间，最后的画作质量却不会差太多。如果没有这个“先勾轮廓再补细节”的分工，你要么得花大把时间从零开始搜索，要么就只能忍受神经网络单独生成的粗糙结果。

LISA 有一个参数 β，代表分配给退火修补阶段的预算比例。β 趋近于 0 时，LISA 退化成纯粹的克隆策略；β 等于 1 时，LISA 就是完整预算的 SA。

实验结果相当亮眼。在 a280 基准上，LISA 在 β=50% 时（也就是只用一半的退火预算）能把差距压到 1.6% 的平均水平；在更难的 ttd300 基准上，同样的预算比例能把平均差距控制在 5.1%。

具体到某个规模来看会更有感觉。在 N=10 时，LISA 用 β=50% 只需 15 秒就能达到 0.02% 的差距，比跑满预算的 SA 和 VNS 都要快一半时间，效果却几乎一样好。在更大的 N=100 实例上，LISA 依然能把差距控制在两位数以内，而单独的 DRL 策略已经差了超过一半。

论文还专门测试了 LISA 在预算极端压缩情况下的表现，哪怕只给 5% 的预算，也能把克隆策略原本高达 64% 的平均差距一举压到 10.71%。这说明哪怕是极短的一段“热身式”搜索，配合一个学过的靠谱起点，也能带来立竿见影的改善。

两套基准测试：从经典城市到自制无人机续航实验室

论文用了两套测试数据。

第一套叫 a280，源自经典的旅行商问题城市数据库，客户位置和物品都是从这个数据库里抽样的，而且假设无人机续航无限，能飞多远飞多远。

第二套叫 ttd300，是这篇论文自己创建的合成数据集，专门用来控制无人机续航这一个变量。

引用块：无人机续航（Endurance，ED）：一次飞行任务的最大往返距离限制，也就是无人机电池能支撑飞出去再飞回来的总里程上限，这是这套系统里限制无人机能不能派上用场的关键物理约束。

ttd300 设计了四档相对续航系数（0.25、0.5、0.75、1.0，对应实例里最大两点距离的不同比例），横跨七种规模（10 到 100 个客户），每种组合有五个不同的随机布局，一共形成了 140 个测试实例。

结果里最能说明问题的一组数据出现在续航系数变化的实验里：把续航系数从 0.25 提到 0.50，几乎每个规模、每个布局的目标值都变好了，在 N=10 时改善了 8.3%，在 N=50 时改善幅度高达 34.7%。但继续往上加到 0.75 和 1.0，改善就明显放缓了。

这里面有个特别直白的现象：在 N=10、续航系数只有 0.25 时，五个布局里有四个压根一次无人机飞行都没派出去，因为飞行半径实在太窄，够不到任何有价值的目标。这就好比你养了一条特别短的狗绳去遛狗，狗根本没法自己跑去够任何有意思的东西，等于养了条狗却没法发挥它的作用。

一件事贵不贵，还是先看时租

论文最后做了一轮敏感性分析，专门看不同参数变化对最终利润的影响有多大。

结论相当清楚：租金比率 R 是压倒性的决定因素，物理参数（车辆容量、速度）的影响相比之下小得多。

具体数字很有说服力。在 N=100、续航系数为 1.00 的设置下，把 R 从 1 调到 200，目标值从 +81,408 一路跌到 –382,171，跨度极大。而只需把 R 从 50 降到 25，在 N≥40 且续航条件较宽松时，整个任务就能从亏损变成盈利，不需要升级任何硬件。

反过来，如果把 R 固定不动，只调物理参数，能撬动的空间就小得多。车辆容量的影响是从 –82,931 提升到 –17,648，无人机速度是从 –57,656 到 –23,416，卡车最低速度是从 –41,311 到 –18,705，这些变化都远远不如调整 R 那么剧烈。

而且续航限制会掐死无人机速度带来的好处。在最紧张的续航条件下（N=10），不管无人机开多快，目标值始终卡在 –45,243 不动，因为飞行半径太小，压根没法派出任何一趟无人机飞行任务。也就是说，就算你给无人机装上火箭引擎，如果它的续航够不着目标客户，速度再快也是白搭。

这给了一个很实际的启示：**如果你是负责这类车队的运营方，比起追求更快的无人机，更值得优先投资的是延长无人机的续航能力。**

论文还测试了一个很有意思的变体：如果每个客户点不止一件物品，而是有五件可选物品呢？结果发现，放开这个“单物品”的限制，在每个规模和每个续航条件下都带来了实实在在的收益改进。在 N=10 时改善了 1,626 到 4,004 不等，到了 N=100 时改善幅度飙升到 40,058 到 53,945，这个规模的改进大到足以让原本亏本的任务变成实打实的盈利，是论文里唯一出现正数目标值的场景。

这说明**在这套系统里，允许多件物品收集，等同于给整个车队打开了一个原本被人为锁死的利润空间。**

Q&A

**Q1：TTP-D 到底是什么问题？**

A：TTP-D 全称是“带无人机的旅行小偷问题”，指的是一辆会越装越重、越装越慢的卡车配合一架无人机去收集分散在各地客户点的物品，目标是让收集到的总利润减去按时间计费的租金成本达到最大。它把经典的旅行商问题、背包问题和无人机协同调度捏合到了一起。

**Q2：为什么无人机速度提升的效果有限？**

A：因为无人机的续航（也就是一次飞行能往返的最大距离）是硬性约束。实验发现，如果续航半径太窄，无人机压根没机会飞出去执行任务，这时候不管把无人机速度调多快，最终结果都不会变化，续航不够，速度再快也没用。

**Q3：LISA 方法比单独用模拟退火或深度学习哪个更好？**

A：LISA 是把两者结合起来的混合方案，先用训练好的神经网络策略快速生成一个初始方案，再用一小部分预算做退火式的局部修补。实验显示只用一半计算预算就能达到接近完整退火算法的质量，比单独用神经网络策略（差距可能高达 50%）或单独跑退火算法（需要完整时间预算）都要划算。