深度强化学习求解无人机旅行商问题：从建模到实战

研究生时期接到一个课题：用深度强化学习求解无人机旅行商问题。我当时盯着"旅行商问题"四个字想了好几天——一个被研究了几十年的组合优化经典问题，套上"无人机"还能玩出什么花？真把建模、训练、部署全套跑下来才意识到，无人机TSP和教科书里的TSP完全是两个物种。这个方向后来成了我毕业论文的核心章节，也在企业里拿真实订单数据做了端到端验证。今天把整套实战思路从头拆一遍，从建模、选网络、写训练循环到两边落地的差异，一次讲清楚。

1. 无人机TSP建模：从"走最短路径"到"活着走完"

1.1 经典TSP与无人机TSP的本质区别

教科书TSP的定义很干净：给定N个城市的坐标，找一条从起点出发、遍历所有城市恰好一次再返回的最短闭合路径。问题形式化之后只依赖一个距离矩阵，其余什么都不用管。经典的动态规划、分支定界、割平面法，以及LKH这类启发式求解器，都是在这个设定下工作的。

把问题换到无人机上，约束一下子变得不干净了。最核心的是续航限制——一架小型多旋翼的留空时间往往只有几十分钟到一小时，能覆盖的配送点数量是有限的。假设一张地图上有100个配送点，但无人机飞35个点就到电量红线了，这时候问题就变成"飞完哪些点、在哪里充电、怎么规划航程"的组合决策。这已经超出了标准TSP的范畴，更像绿色车辆路径问题（GVRP）或带充电站的路径规划。

除此之外还有一堆实际约束：三维空间要处理高度变化和地形遮挡，气压、风速会影响能耗模型；关键区域不能飞；起降点可能不是唯一的；货物重量影响了续航曲线。这些约束叠加在一起，标准TSP的距离矩阵求最短路的思路就失效了——因为"代价"不再是单纯的距离，而是随着环境动态变化的能耗、风险和时间的加权和。

1.2 为什么深度强化学习更贴合这个场景

传统解法放在无人机场景里各有各的难受。精确算法（分支定界、动态规划）能算出最优解，但计算复杂度随节点数指数增长，20个节点还能硬算，50个往上就直接无解了。启发式算法（LKH、模拟退火、遗传算法）处理静态问题效果不错，但每次问题环境变化——比如来了新订单、某个区域被临时管控、风速突变——就需要人工设计新的特征和规则去适配，工程成本很高。

深度强化学习的思路完全不同：把路径决策建模成一个序贯决策过程，让策略网络根据当前状态直接输出下一个要访问的节点。网络通过大量实例训练学会"看到什么样的节点分布，就走什么样的顺序"，推理时一次前向传播就能得到一个完整路径。这个特性天然适合无人机的在线规划需求——地图变了，输入变一下，重新推理一次就有新路径。

对我来说还有一个很现实的原因：这个题目非常适合做毕设。深度强化学习覆盖了马尔可夫决策过程、策略梯度、Transformer架构、图表示学习好几块硬核知识，论文的理论深度好写；同时又有清晰的可视化和对比实验可以做，工作量好展示。企业端则看重它从输入到输出的端到端能力，省掉了传统方案里大量特征工程的维护成本。

2. 方案选型：MDP建模、网络架构与训练算法

2.1 MDP建模：状态、动作、奖励怎么设计才不掉坑

深度强化学习解决TSP，第一步是把组合优化问题描述成马尔可夫决策过程（MDP）。这一步直接决定后面网络怎么设计、训练能不能收敛，很多人上来就写模型，结果折腾半天发现问题出在建模上。

状态s_t需要包含三类信息：所有节点的坐标（这是静态特征，编码器一次处理完）、当前无人机所在的节点（每步变化）、以及已访问节点集合（决定下一步能选谁）。已访问集合在实现里通常用一个mask向量表示，每个维度对应一个节点，访问过就置为1，解码时把对应概率强制设成0。

动作a_t简单直白：从当前未访问的节点集合里选一个作为下一个目标点。这里有个细节，模型输出的是所有未访问节点的概率分布，训练时按概率采样，评估时取最大概率。采样的随机性让策略能探索不同的路径组合，这是强化学习能够跳出局部最优的关键。

奖励设计我一开始踩了坑。最自然的做法是每走一步给负的距离奖励，但直接把原始距离当奖励，20节点和50节点的奖励量级差了好几倍，换规模就得重新调学习率。我的做法是每个step的奖励用当前两节点距离除以实例节点的平均间距做归一化，走完所有节点后再给一个完成奖励。这样不同规模下的奖励都在同一个量级，训练超参可以直接迁移。至于禁飞区、电池余量这类硬约束，直接在mask里处理，比在奖励里加惩罚项稳定得多。

2.2 网络架构：Attention Model是更省心的选择

确定了MDP，接下来是策略网络的结构。早期研究多用Pointer Network，它基于Seq2Seq架构，编码器把节点序列编码成隐状态，解码器每步用注意力机制输出一个指向输入序列位置的指针。Pointer Network能解决小规模TSP，但有两个问题：一是循环结构串行计算，训练慢；二是它本质上假设节点顺序有意义，而TSP的节点集合是无序的。

后来Attention Model这套思路成了主流：编码器直接用Transformer的多头自注意力结构，对每个节点坐标做线性嵌入后，通过N层自注意力编码节点间的关系。自注意力让每个节点在生成表示时能看到所有其他节点，相当于让网络自己学习"哪些节点之间存在强相关性"——距离近的点会被编码成相似的表示，这在图数据上是一种很自然的归纳偏置。

解码器部分维护一个上下文向量，由三部分拼接而成：全局图嵌入（所有节点编码的均值）、当前节点编码、以及一个表示已走步数的嵌入。用上下文向量作为query，和所有未访问节点的key做点积，得到注意力分数，softmax后就是下一个节点的选择概率。已访问节点在算分数前就把logits置为负无穷，softmax之后概率自然归零，这是保证路径合法性的关键机制。

我实际体验下来，Attention Model比Pointer Network省心很多：PyTorch的TransformerEncoder可以直接复用，不用手写循环，训练速度快一大截；而且它对输入节点顺序完全不敏感，这在处理真实地图数据时是个很大的优势。

2.3 训练算法：REINFORCE + Rollout Baseline 是毕设稳妥路线

训练策略网络有两大流派：基于策略梯度的REINFORCE，和基于Actor-Critic的PPO。对我这个场景，我推荐REINFORCE + rollout baseline，理由有三个：实现简单（整个训练循环50行代码搞定）、显存占用低（不需要额外的critic网络）、训练稳定（不需要调PPO那一堆超参）。

REINFORCE的核心公式是策略梯度：∇J(θ) = E[(L - b) ∇log π_θ]，其中L是采样路径的总长度，b是baseline。这里的直觉是：如果一条路径比"平均水平的路径"更短，就把产生这条路径的决策概率调高；如果比平均水平长，就降低它的概率。baseline的作用是减小梯度方差，没有它训练会非常不稳定。

rollout baseline的实现很有意思：冻结一份旧策略网络，每隔固定epoch用它贪婪解码一批验证集实例得到路径长度，作为当前采样的baseline。只有当新模型在验证集上明显优于旧模型时，才更新这份冻结的baseline。相比训练一个critic网络，这个方法不需要额外维护一个回归模型，也不容易因critic拟合不好引入偏差。我实践中发现它的收敛曲线比带critic的版本平滑得多。

如果后面想扩展做连续控制——比如同时决策飞行速度和方向——再考虑PPO也不迟。纯路径规划的离散决策场景，REINFORCE + rollout baseline是性价比最高的选择。

3. 实操过程：从零到一搭出一套可复现的求解流程

3.1 环境准备与训练数据构造

环境方面，Python 3.8+、PyTorch 2.0+、CUDA 11.x就够用。数据集不用去找现成的，自己生成反而更灵活。训练数据采用随机生成的方式：每个实例从中抽取N个节点的二维坐标，归一化到[0,1]区间。注意要在实例里加一个索引为0的节点作为起点（可以理解为无人机机库或配送中心的坐标），起点也要参与编码，但mask的规则略有不同——起点在第一步之后就不可再选，直到最后一步返回才算闭合。

验证和测试数据我建议另抽一批固定的随机实例，固定随机种子，保证实验可复现。我在项目中准备了1000个20节点、1000个50节点、200个100节点的测试实例。20节点的最优解可以用穷举或精确求解器算出来，用来算精确gap；50和100节点的参考解用LKH这类强启发式求解器长时间运行得到。评估标准就是gap = (模型平均路径 - 参考最优路径) / 参考最优路径。

import torch from torch.utils.data import Dataset class TSPDataset(Dataset): """随机生成TSP实例，坐标归一化到[0,1]。 所有实例第一个节点作为起点/终点，其余为待访问节点。 """ def __init__(self, num_samples, num_nodes): super().__init__() # shape: (num_samples, num_nodes + 1, 2) self.data = torch.rand(num_samples, num_nodes + 1, 2) def __len__(self): return self.data.shape[0] def __getitem__(self, idx): return self.data[idx]

数据加载用PyTorch的DataLoader，batch size设256到512。这里有个经验：batch内所有实例的节点数一致，所以不需要padding，数据shape是规则的（B, N+1, 2），丢进模型直接算。

3.2 核心代码实现：Encoder、Decoder与训练循环

Encoder部分直接复用PyTorch的TransformerEncoder层。先把节点坐标通过一个线性层映射到128维的embedding空间，加上可学习的位置编码或不加都行（因为自注意力本身不依赖顺序），然后过3层TransformerEncoder，每层8个注意力头。输出是每个节点的128维编码向量，同时把它们的均值作为全局图嵌入。

import torch.nn as nn class TSPEncoder(nn.Module): def __init__(self, embed_dim=128, num_layers=3, num_heads=8): super().__init__() self.embed_dim = embed_dim # 坐标 -> 嵌入向量 self.init_proj = nn.Linear(2, embed_dim) # Transformer 编码层 encoder_layer = nn.TransformerEncoderLayer( d_model=embed_dim, nhead=num_heads, dim_feedforward=512, batch_first=True ) self.encoder = nn.TransformerEncoder(encoder_layer, num_layers=num_layers) def forward(self, coords): # coords: (batch, num_nodes+1, 2) x = self.init_proj(coords) # (batch, num_nodes+1, embed_dim) x = self.encoder(x) # 自注意力编码节点关系 graph_embed = x.mean(dim=1) # 全局图嵌入 return x, graph_embed

Decoder部分需要自己写一个循环。每一步的输入是当前节点编号、所有节点的编码向量和全局图嵌入。把当前节点编码和全局图嵌入拼起来作为query，与所有节点编码做注意力打分。打分时，已经访问过的节点logits要mask掉，最后softmax得到选择概率。

class TSPDecoder(nn.Module): def __init__(self, embed_dim=128, num_heads=8): super().__init__() # 将上下文（当前节点编码 + 全局图嵌入）映射为query self.project_query = nn.Linear(2 * embed_dim, embed_dim) def compute_logits(self, node_embeds, graph_embed, current_idx, mask): batch, num_nodes, embed_dim = node_embeds.shape cur = node_embeds[torch.arange(batch), current_idx] context = torch.cat([cur, graph_embed], dim=-1) # (batch, 2*embed_dim) query = self.project_query(context).unsqueeze(1) # (batch, 1, embed_dim) # 注意力打分：query 与所有节点编码做点积 logits = torch.bmm(query, node_embeds.transpose(1, 2)).squeeze(1) # 已访问节点 mask 掉：logits 置为 -inf logits = logits.masked_fill(mask == 1, float('-inf')) return logits

训练循环是整套流程的灵魂。每个batch走一遍完整路径生成，用负路径总长作为奖励，然后套REINFORCE梯度公式更新参数。

def train_step(model, baseline_model, batch, optimizer): batch_size, num_nodes, _ = batch.shape coords = batch.to(device) node_embeds, graph_embed = model.encode(coords) # 路径生成循环 mask = torch.zeros(batch_size, num_nodes, dtype=torch.bool, device=device) mask[:, 0] = True # 起点已访问 current_idx = torch.zeros(batch_size, dtype=torch.long, device=device) log_probs = [] actions = [current_idx.clone()] total_distance = torch.zeros(batch_size, device=device) for _ in range(num_nodes - 1): logits = model.decode(node_embeds, graph_embed, current_idx, mask) probs = torch.softmax(logits, dim=-1) dist = torch.distributions.Categorical(probs) action = dist.sample() log_probs.append(dist.log_prob(action)) actions.append(action.clone()) # 累加距离 prev = coords[torch.arange(batch_size), current_idx] nxt = coords[torch.arange(batch_size), action] total_distance += torch.norm(nxt - prev, dim=-1) # 更新mask和当前节点 mask[torch.arange(batch_size), action] = True current_idx = action # 最后返回起点，闭合路径 prev = coords[torch.arange(batch_size), current_idx] start = coords[:, 0] total_distance += torch.norm(start - prev, dim=-1) # baseline 用冻结的旧模型对同batch做贪婪解码 with torch.no_grad(): baseline = baseline_model.greedy_length(coords) # 贪心解码路径长度 # REINFORCE loss log_probs = torch.stack(log_probs, dim=1).sum(dim=1) advantage = total_distance - baseline # 路径越短，advantage越小 # 注意：reward应取负距离，所以 loss = advantage * log_probs 对应的梯度方向相反 loss = (advantage.detach() * log_probs).mean() optimizer.zero_grad() loss.backward() torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0) optimizer.step() return loss.item(), total_distance.mean().item()

代码里最容易被忽略的是advantage.detach()——优势值不能回传到生成路径的网络去，否则就变成了端到端的注意力监督学习，策略梯度的含义就没了。另外梯度裁剪是必需品，Transformer结构偶尔会有数值不稳定，不裁剪的话loss曲线会突然飞掉。

3.3 训练配置与调参实战

超参配置直接给一套能跑的方案，20节点训练是最佳起步规模，pipeline验证通了再往上加：

学习率用Adam默认的beta参数就行，但初始学习率要压住。我用1e-3试过，loss曲线前几个batch就在剧烈震荡，降到1e-4之后平滑很多。50节点以上建议把embed_dim提到256，但显存不够时先保证batch size，embed_dim降到128也能跑。

训练过程的判断标准看两个曲线：每个batch的平均路径长度（应该稳步下降），以及每10个epoch在验证集上的gap（评估用贪心解码）。我一般盯gap而不是loss，因为loss包含了baseline的影响，数值上参考意义不大。收敛的迹象是验证集gap连续10个epoch几乎没有下降，这时候就可以停了。20节点我的实验能达到gap小于3%，50节点gap约5%，100节点gap约8%——在动态场景中这已经足够实用，对比LKH在实时性上的劣势，这个精度完全可以接受。

4. 常见问题与调试实录

4.1 训练不收敛、损失曲线震荡

这是我被问得最多的问题。90%的情况出在奖励没有归一化，或者学习率太大。先检查奖励的量级：如果路径总长的期望是15，优势值的量级也是15，那么学习率1e-4对应的梯度更新幅度对128维的embedding来说偏大了，容易震荡。解决方向不是降学习率而是先归一化奖励，再回头调学习率。

另一个隐蔽问题是mask没有生效。如果训练中出现了重复访问同一节点的路径，那就要检查logits的mask是不是在softmax之前作用的，而不是在采样之后过滤。之后过滤等价于告诉模型"这个动作本来合法但不让你选"，梯度方向就错了。

4.2 模型过早收敛到固定模式

一个典型的失败现象：模型总是输出几乎相同的路径顺序，无论输入什么节点分布。这说明策略的熵太低，陷入局部最优。原因通常是baseline太弱，导致早期所有采样路径相对baseline的优势值都很大，模型被某一个方向"推过头"。

我的排查思路：训练开始阶段打印每个batch的平均熵值。如果第一个epoch熵降得过快（比如从log(20)左右迅速降到1以下），就要介入干预。两个手段：一是训练前几步增加熵正则项，让策略保持一定的探索性；二是检查rollout baseline的更新频率——如果baseline太差，优势值方差大，也会让策略快速坍缩。把baseline的替换阈值设得严格一些，让旧模型多"陪跑"一段时间，反而有利于探索。

4.3 换一个节点规模就性能骤降

在20节点上训练好的模型直接去跑50节点，效果通常惨不忍睹。这不算bug，是组合优化问题的固有性质——20节点的问题结构和50节点的问题结构在分布上差异很大，网络的泛化能力赶不上分布的变化。

通用的解法是混合规模训练：在同一个batch里混入20到50个节点的实例，让网络同时见到不同规模的问题分布。这个方案我实验下来很有效，模型在40节点上的表现只比单独训练的模型差3%左右。另外一个技巧是输入时做坐标缩放增强——每个批次对坐标做随机缩放和旋转，相当于数据增广，能提升模型的几何泛化性。要说明的是，这套方案也有边界：50节点训练出的模型直接挪到200节点基本不可用，真要做大规模场景，只能按规模分段训练模型，上线时按问题规模路由到对应模型。

4.4 显存不够、训练速度太慢

Attention Model的显存消耗主要在自注意力层的注意力矩阵上，batch里所有实例拼一个大张量，序列越长越吃显容。我遇到过20节点能跑，100节点直接OOM的情况。几个实用对策：减小batch size的同时增加梯度累积步数；embed_dim从128降到96；训练时用混合精度autocast。这三个组合起来通常能把显存占用砍掉一半。

训练速度方面，单卡消费级GPU训练20节点、100个epoch大约需要2到5个小时，50节点可能要一天。如果时间紧，先把epoch减少到原计划的1/3，看看曲线趋势能不能收敛，确认思路没问题再开长跑。评估阶段不要每个epoch都跑全部验证集，每10个epoch跑一次就够了，这里能省不少时间。

5. 毕设与企业双适配：同一套方案两边都加分

5.1 毕设版：理论、实验、可视化怎么让答辩老师挑不出毛病

毕设和论文的评审逻辑，和企业完全不同，他们看重的是你能不能说清楚"为什么选这条路""和已有工作相比好在哪"。所以毕设版要把三块补齐。

第一块是理论推导。策略梯度的推导、log-derivative trick、baseline为什么能降低方差，这些公式必须自己能推一遍，论文里写清楚。不光是抄公式，要结合自己的网络结构讲清楚梯度是怎么回传到Encoder和Decoder的。这一块是拉开档次的地方。

第二块是对比实验设计。光有自己模型的训练曲线不够，要设计几个维度的实验：不同节点规模下的准确率对比（vs 精确求解器、vs LKH、vs OR-Tools）；消融实验（去掉rollout baseline、减少Encoder层数、去掉mask各自的影响）；推理时间对比。对比实验的意义不是"证明自己最好"——在静态问题上DRL本来就很难超过LKH——而是证明在动态环境下，微小的性能差距换来的是几十倍的推理速度和在线重规划能力。

第三块是可视化。路径可视化（matplotlib画出求解结果）、训练曲线、注意力权重可视化。当你能把attention权重画出来，展示模型在决策时关注哪些节点，答辩效果会好很多。

5.2 企业版：从离线TSP到在线调度还缺的工程化改造

企业场景完全不关心你用什么算法框架，他们要的是稳定、快、能接进现有系统。我第一次把模型部署到实际调度系统时，发现了两边巨大的认知差。

第一个是数据分布差异。合成的均匀分布节点，和真实的配送地址分布完全不同——真实地址天然聚簇（写字楼、园区、小区），坐标归一化之后是明显成团的。直接拿合成数据训练的模型在真实数据上效果会打折。解决方案是拿历史订单数据做微调，微调时不需要重新训，在已有权重上小学习率跑几十个epoch就够。

第二个是推理性能。PyTorch模型直接部署在服务器上通常够用，但调度系统需要在几百毫秒内对几十个订单完成规划。两个优化手段：一是模型导出ONNX，再用TensorRT做FP16量化，推理延迟能压到个位数毫秒；二是批处理——系统同时来几百个订单时，把多个实例拼成一个batch推理，比循环单条推理快一个数量级。批处理还有额外收益：多次采样取最优路径的策略变得几乎零成本。

第三个是动态重规划。真实场景会有新订单接入、顾客取消、无人机临时故障。结合DRL的天然优势，热启动重规划方案是：把已经访问过的节点在mask里置为True，把当前无人机位置作为新的起点，重新推理一次就得到新路径。这个能力传统求解器很难优雅实现，但DRL模型天然支持。

5.3 扩展方向与实际落地判断

如果研究时间充裕，有几个方向值得投入。禁飞区约束可以用mask实现，几乎零成本地兼容现有框架；带时间窗的TSP只需要在状态里加上时间信息，奖励函数加延迟惩罚；多无人机协同则可以先做任务聚类分配，每个无人机单独求解，再统一协调时间窗；更进一步就是端到端的多智能体强化学习，但训练难度会明显上一个台阶。

判断扩展方向值不值得做，我的经验是看复用度：能不能复用现有的Encoder-Decoder骨架，需不需要改动MDP建模，reward函数改动的复杂度有多高。像禁飞区这种mask级别的改动，成本很低，毕设和企业都认可；而多智能体协同这种大改，适合有充足时间的研究场景，企业落地通常先用"聚类+单机求解"的方案过渡。落地时把握一个原则——先用最简单的方案满足需求，再根据实际效果决定是否上更大的模型。

整套方案跑下来，我最深的体会是：深度强化学习解决无人机TSP的核心难点从来不在算法本身，而在对问题的建模——把物理世界的约束翻译成MDP里的mask和reward，想清楚这一步，后面的网络和训练就是标准流水线的活。论文写完那一刻你可能觉得自己解决了TSP，等到企业里跑真实数据才发现只是开始：数据分布、部署延迟、动态事件，每一个都是新的坑。但这个方向最迷人的地方也在这里，它从理论到工程给你留了一整条路去走，每一步都能学到东西。