强化学习求解CVRP：Python实现、训练避坑与扩展指南-平芜编程栈

简介：这是一套基于强化学习的带负载约束车辆路径规划问题求解Python源码，面向人工智能、运筹优化方向的在校生与开发者，适合用作毕业设计、课程设计或相关课题的入门实践。压缩包共七个文件，涵盖Python主程序、两个预训练模型权重、三个Markdown说明文档及Git忽略配置文件，整体约5.04MB，目录清晰，便于快速定位代码、说明与模型文件。目前已有九十一人学习下载，适合初步接触强化学习与组合优化相结合的读者。资源中的预训练模型文件可直接加载使用，省去重复训练成本；通过说明文档可快速了解项目结构、依赖与运行方式，并能在现有代码基础上修改扩展，尝试更多带负载约束的车辆路径变体。代码经测试可稳定运行，可作为算法对比、实验改进或毕设答辩的可靠基础。

1. 带负载约束的 VRP 用强化学习求解：这条路到底通不通

做物流调度或者路径规划的工程师，基本都撞过 CVRP：一个仓库、一批客户、每辆车有最大载重，目标是让总里程最短。传统解法跑 OR-Tools 或者商用求解器，中小规模很快，规模一上来就越来越吃力。强化学习这条路近几年反复被提起，核心思路是让一个神经网络反复“试跑”路径，跑得越短奖励越大，最后学出来的策略能一步一个动作地把一条可行路径解码出来。这个标题说的，就是怎么用 Python 把这套东西落成一个能自己训练、能出解、能跟传统方法对比的求解器。

如果你是刚接触强化学习的新手，下面内容能让你把一个最小可跑的 Python 求解器骨架搭起来；如果你已经在跑 OR-Tools，这篇重点讲强化学习求解器的模型结构、训练参数和最容易翻车的部分，方便你评估这套方案值不值得投入。

2. 把 CVRP 改写成强化学习问题：状态、动作、掩码与奖励怎么设计

要把路径规划问题交给强化学习，第一步不是写网络，而是把问题重新定义成一个“智能体一步步做决策”的过程。这个定义直接决定后面的模型好不好训，稍有不慎就会训出一个只会原地打转的网络。

2.1 为什么 CVRP 适合改写成序列决策问题

CVRP 的标准数学模型是一个整数规划：变量是“某辆车有没有从节点 i 开到节点 j”，约束包括每个客户的访问次数、每辆车的载重限制，目标是最小化总行驶距离。求解器在这个模型上做分支定界或者割平面。问题在于客户数量超过一两百之后，精确算法的搜索空间膨胀得非常快，启发式算法又需要大量人工调参。

强化学习换了个角度：不直接求解“整条路径”，而是让一个策略网络每次输出“下一步去哪”。每输出一个节点，就相当于在已有路径后面追加一段；当所有客户都访问完，一条完整路径就拼出来了。这个过程跟人开车送货的决策习惯很像，而且天然适合用策略梯度方法优化——网络的输出是离散动作，路径越长奖励越小，模型会慢慢学会先服务偏远节点、减少回头路。

这个改写最大的好处是：模型训练好之后，推理只是一串前向计算，不需要像 OR-Tools 那样每次重新做搜索。对大规模算例或者需要实时响应的场景，这是一个非常值得考虑的性质。需要说明的是，强化学习一般不会预先把车辆数固定死，而是让网络通过“是否回仓库”的决策自动决定用几辆车，车辆数本身成为策略的一部分。

2.2 状态与动作空间：编码器输入、掩码与容量约束的实现

强化学习里的“状态”在 CVRP 里由两部分构成：静态信息是整个实例的地图，包括仓库和所有客户的位置坐标，以及每个客户的需求量；动态信息是当前已经走过的路径、当前在哪一个节点、车辆还剩多少载重、还有哪些客户没访问。

这里的难点是让网络知道“哪些动作现在合法”。比如当前车辆剩余载重是 3，而某个客户需求是 5，这一步就不能选这个客户；又比如这一条路径已经把所有客户都访问完了，那下一步只能回仓库。把这种合法性直接写进掩码，比在损失函数里加惩罚项要可靠得多。惩罚项只能让网络“尽量少犯”，掩码能让它“根本犯不了”。

一个典型的环境初始化代码如下：

import torch class CVRPEnv: def __init__(self, num_customers, capacity, batch_size, seed=None): self.num_customers = num_customers self.capacity = capacity self.batch_size = batch_size if seed is not None: torch.manual_seed(seed) self.reset() def reset(self): # 节点 0 固定为仓库，其余为客户 # 坐标在 [0, 1] 正方形内均匀采样 self.nodes = torch.rand(self.batch_size, self.num_customers + 1, 2) # 客户需求取 1~9 的整数，保证每辆车能服务多个客户 self.demand = torch.randint(1, 10, (self.batch_size, self.num_customers + 1)).float() self.demand[:, 0] = 0 # 仓库没有需求 # 访问标记：仓库初始化就是已被访问状态 self.visited = torch.zeros(self.batch_size, self.num_customers + 1, dtype=torch.bool) self.visited[:, 0] = True # 所有车辆从仓库出发，剩余载重等于最大容量 self.remaining_capacity = torch.full((self.batch_size,), self.capacity, dtype=torch.float) self.cur_node = torch.zeros(self.batch_size, dtype=torch.long) self.total_dist = torch.zeros(self.batch_size, dtype=torch.float) return self._get_state() def _get_state(self): # 返回环境当前状态，供策略网络读取 return { "nodes": self.nodes, "demand": self.demand, "visited": self.visited, "remaining_capacity": self.remaining_capacity, "cur_node": self.cur_node, }

这个环境用 batch 并行处理多条独立路径，每条路径的车都从仓库出发。reset里关键是仓库的访问标记直接置 True，这样后续掩码逻辑里仓库永远走“访问仓库”的分支，不会出现重复访问客户的问题。

掩码函数需要同时考虑容量约束和终点约束：

def get_mask(self): # 客户节点掩码：未访问，且需求不超过当前剩余载重 customer_mask = (~self.visited[:, 1:]) & ( self.demand[:, 1:] <= self.remaining_capacity.unsqueeze(1) ) # 如果还有客户可以服务，则不应返回仓库； # 如果全部客户都已访问，则必须返回仓库 all_visited = self.visited[:, 1:].all(dim=1) any_serviceable = customer_mask.any(dim=1) depot_mask = all_visited | (~any_serviceable) mask = torch.cat([depot_mask.unsqueeze(1), customer_mask], dim=1) return mask

这段逻辑看着简单，其实是整个环境实现里最需要抠细节的地方。all_visited保证回路一定会回到仓库收尾；~any_serviceable保证当前载重装不下任何一个未服务客户时强制回仓库补货，不会卡死在死胡同。这两条缺一不可，漏掉任何一条训练出来的路径都会出现中途断开或者无限循环。

注意：这里用~visited[:, 1:]直接表达“客户还没被访问”，而不是把每个客户单独维护一个状态标记。批量操作写起来更短，也不容易在状态同步时出错。

2.3 奖励设计：稀疏距离奖励和多轨迹基线

CVRP 的奖励设计有两条路：稀疏奖励和步进奖励。稀疏奖励就是整条路径走完以后，把总里程的相反数当成奖励，路径越短奖励越大。步进奖励是每走一步就累加一段距离，再把当前累计距离的负值返回给智能体。

稀疏奖励的优点是目标跟实际问题完全一致，不会出现“每一步都变好，整体反而变差”的偏差；缺点是训练早期模型什么都学不到，因为所有路径的稀疏奖励相差不大，梯度信号非常弱。步进奖励能解决信号稀疏问题，但容易让模型偏向“前面少走两步、后面绕远路”的局部最优。

实践中比较稳妥的做法是把奖励设为整条路径的总距离负值，然后用一个额外的技巧来解决梯度弱的问题：多起点采样。也就是对同一个实例，让模型从不同客户作为第一个访问点分别生成多条路径，彼此共享一套网络参数，训练时用这多条路径的平均奖励作为基线，单条路径的奖励减去这个均值再当作梯度信号。

这个技巧在业界常被叫做“共享基线”，效果比单独用一个 critic 网络去预测奖励值更稳。原因很实在：同一份地图上，不同起点之间的路径差异恰好能反映策略网络当前的好坏，用它当基线等于在“同一场考试里比排名”，而不是跟一个绝对标准比。

3. 用 Python 写出可跑的 CVRP 环境：数据生成、状态步进与可行性校验

环境类写好之后，下一步是让它能真正跑起来：每一步执行动作、更新载重和访问状态、累计距离、判断是否结束。这个环节的代码不需要多高深，但状态更新的顺序一旦写错，后面所有训练结果都会是错的。

3.1 CVRP 环境的最小 Python 实现：step 与 done 判断

step 函数要同时完成三件事：算这一步的行驶距离、更新当前节点、更新剩余载重和访问标记。

def step(self, action): batch_idx = torch.arange(self.batch_size) # 当前节点坐标和目标节点坐标 cur_pos = self.nodes[batch_idx, self.cur_node] nxt_pos = self.nodes[batch_idx, action] # 欧氏距离作为两个节点间的行驶距离 step_dist = torch.norm(cur_pos - nxt_pos, dim=-1) self.total_dist += step_dist # 判断动作是否回仓库 is_depot = (action == 0) # 剩余载重：回仓库则补满，否则扣减客户需求 self.remaining_capacity = torch.where( is_depot, torch.full_like(self.remaining_capacity, self.capacity), self.remaining_capacity - self.demand[batch_idx, action] ) # 标记该节点已访问；仓库本来就是 True,重复访问不影响 self.visited[batch_idx, action] = True self.cur_node = action # 全部客户访问完即结束 done = self.visited[:, 1:].all(dim=1) return self._get_state(), step_dist, done

这里必须注意的是remaining_capacity的更新不能写到visited更新之后再去读，因为torch.where的两个分支都会先计算出来，如果 action 是仓库，demand[:, 0]正好是 0，减去 0 不会出问题，但不小心把仓库需求设成非零数就会导致回仓库后载重变负。所以宁愿分开写清楚分支逻辑，也不要在一个表达式里塞太多隐式依赖。

done判断用的是“所有客户都访问过”，而不是“当前节点回到仓库”，这是因为允许车辆中途回仓库补货，如果以“到仓库”为结束条件，模型完全可能在服务一半客户时就宣布结束。

3.2 实例生成与批处理：batch 维度怎么组织才算对

训练强化学习模型，一次只跑一条路径效率太低。常见做法是让环境同时维护多条路径，每条路径对应 batch 里的一个样本。问题在于这些样本可能来自同一个实例，也可能来自不同实例。

如果想让模型对同一个实例生成多条轨迹来做基线，就要把同一个实例复制 group_size 份，堆叠在 batch 维度上；如果只是想增加样本多样性，那就每个 batch 位置放一个全新实例。我的经验是两者要搭配：训练阶段每个 batch 生成一批新的随机实例，坐标分布保持一致，保证网络学到的是“求解方法”而不是“背下某张地图”。

def generate_batch(num_customers, capacity, batch_size, seed=None): env = CVRPEnv(num_customers, capacity, batch_size, seed=seed) return env

看起来这只是一行创建环境的代码，实际上它决定了训练数据的分布策略。如果永远用同一个 seed，模型会把 50 个客户的坐标背下来，换一张图立刻崩；如果每个 batch 都重新随机，坐标的覆盖范围要跟应用场景保持一致。比如实际业务的仓库和客户可能集中在某个城市区域，训练时却用全局均匀分布，这样学出来的路径在实际场景上会有明显的偏差。

批量训练还有一个显存相关的坑：batch_size 直接决定了一个 step 里面要展开多少条轨迹。CVRP 的展开长度上限大概是2 * num_customers + 1，所以显存占用跟 batch_size 和客户数的乘积成正比。显存不够时优先压 batch_size，不要压网络宽度，否则模型表达能力不够，训练半天还是学不会。

3.3 可行性校验：怎么确保障生成的输出不是一个“看似合理”的非法解

强化学习训练过程中，我们经常需要随时抽查模型生成的路径。人眼很难在 200 个节点的图上快速判断有没有超载，因此算法层面一定要有自动校验函数。这个函数不参与梯度计算，只用来打印日志或者画路径图。

def check_feasibility(nodes, demand, capacity, route): # route 是节点索引序列，例如 [0, 3, 5, 0, 2, 7, 0] total_dist = 0.0 load = 0.0 visited = set() for i in range(len(route)): # 当前载重不能超过容量 if load > capacity: return False, load, total_dist node = route[i] if node != 0: if node in visited: return False, load, total_dist visited.add(node) load += demand[node] else: load = 0.0 if i > 0: total_dist += torch.norm(nodes[route[i-1]] - nodes[node]) # 所有客户都必须被服务，且最后一步必须回到仓库 if len(visited) != demand.shape[0] - 1: return False, load, total_dist if route[-1] != 0: return False, load, total_dist return True, load, total_dist

这个函数是训练过程中的“后悔药”。它能直接告诉你模型当前生成的路径在业务上能不能用，而不是只看 loss 曲线。很多新手的误区是只看平均路径长度下降就以为模型学好了，结果一校验发现 30% 的路径超载或者漏客户，之前的下降全是虚假繁荣。我在训练代码里每 100 步就会抽一批路径做校验，并把非法率打到日志里，比看 loss 管用得多。

4. 策略网络和训练循环：REINFORCE 基线让模型自己学会少绕路

环境准备好以后，核心工作就是策略网络和训练循环。网络结构决定模型有没有能力表达“当前地图上哪些客户值得优先访问”，训练循环决定这个表达能力能不能稳定地转化为更短的路径。

4.1 编码器：用注意力层替换全连接网络

CVRP 的网络输入是一堆无序节点，每个节点带坐标和需求两个特征。全连接网络对这种输入的处理方式很弱，因为它把节点顺序当成了有意义的先验，打乱输入顺序得到的特征完全不一样。注意力机制没有这个毛病：它对所有节点做聚合，任意两个节点之间的关系权重由模型自己学，天然适合“集合输入”的问题。

import torch.nn as nn import torch.nn.functional as F class EncoderLayer(nn.Module): def __init__(self, embed_dim, n_heads): super().__init__() self.mha = nn.MultiheadAttention(embed_dim, n_heads, batch_first=True) self.ff = nn.Sequential( nn.Linear(embed_dim, 2 * embed_dim), nn.ReLU(), nn.Linear(2 * embed_dim, embed_dim), ) self.norm1 = nn.LayerNorm(embed_dim) self.norm2 = nn.LayerNorm(embed_dim) def forward(self, x): h, _ = self.mha(x, x, x) x = self.norm1(x + h) h = self.ff(x) x = self.norm2(x + h) return x class Encoder(nn.Module): def __init__(self, embed_dim=128, n_heads=8, n_layers=3, input_dim=3): super().__init__() self.embed = nn.Linear(input_dim, embed_dim) self.layers = nn.ModuleList( [EncoderLayer(embed_dim, n_heads) for _ in range(n_layers)] ) def forward(self, nodes, demand): # 输入特征：横坐标、纵坐标、需求量 x = torch.cat([nodes, demand.unsqueeze(-1)], dim=-1) h = self.embed(x) for layer in self.layers: h = layer(h) return h

embed_dim=128是兼顾表达能力和训练速度的起点，太小学不好节点之间的关系，太大在小规模算例上容易过拟合。层数n_layers=3是这类任务里比较稳妥的选择，再深收益有限，训练时间和显存占用却线性增加。这里的残差连接和 LayerNorm 也很关键，没有它们，几十层堆叠的注意力特征会越传越扭曲，梯度也更容易爆炸。

4.2 解码器：上下文、查询与动作 logits

编码器把整个实例变成一组节点特征向量，解码器则在每一步决定下一步去哪个节点。解码器需要三类信息：全图特征、当前节点特征、剩余载重。这三者的组合形成一个查询向量，和所有节点的特征向量做点积，得到每个候选节点的分数。

class Decoder(nn.Module): def __init__(self, embed_dim): super().__init__() self.cap_proj = nn.Linear(1, embed_dim) self.Wq = nn.Linear(embed_dim * 3, embed_dim) self.Wk = nn.Linear(embed_dim, embed_dim) self.scale = embed_dim ** 0.5 def forward(self, h, cur_node, remaining_capacity, mask): # h: [batch, num_nodes, embed_dim] graph_feat = h.mean(dim=1) # 全图特征 cur_feat = h.gather(1, cur_node[:, None, None].expand(-1, -1, h.size(-1))).squeeze(1) # 剩余载重是标量，先映射到 embed_dim cap_feat = F.relu(self.cap_proj(remaining_capacity.unsqueeze(-1))) context = torch.cat([graph_feat, cur_feat, cap_feat], dim=-1) query = self.Wq(context) keys = self.Wk(h) logits = torch.matmul(query.unsqueeze(1), keys.transpose(1, 2)).squeeze(1) logits = logits / self.scale logits = logits.masked_fill(~mask, -1e9) return logits

库代码注意masked_fill的地位：把非法动作用-1e9掩盖后经过 softmax 概率会变成 0，梯度也不会从这些非法位置往回传。有些实现会用float('-inf')，理论上可以，但在某些数值精度设置下容易造成 NaN，经验上-1e9更稳。

解码器里graph_feat用的是所有节点特征的均值池化，简单且有效。也可以换成在编码器后加一个专门的图嵌入 token，但均值池化在中小规模算例上跟它的差距很小，没必要一上来就做得复杂。

4.3 训练循环：策略梯度、组内基线与梯度裁剪

训练循环用最基本的 REINFORCE。因为策略网络的输出是离散动作，我们不能直接对动作做梯度下降，只能通过采样动作、用奖励加权 log 概率的方式来近似梯度。为了让梯度不那么摇摆，一个实用做法是取同一个 batch 内所有轨迹奖励的均值作为基线：

import torch.optim as optim def train(env, encoder, decoder, optimizer, group_size, max_steps): encoder.train() decoder.train() # 每个实例重复 group_size 份，用于组内基线 max_steps = 2 * env.num_customers + 2 for step in range(max_steps): env.reset() # 编码一次，整条路径共享 h = encoder(env.nodes, env.demand) log_probs = [] for t in range(max_steps): mask = env.get_mask() logits = decoder(h, env.cur_node, env.remaining_capacity, mask) logp = F.log_softmax(logits, dim=-1) probs = logp.exp() action = probs.multinomial(1).squeeze(1) log_probs.append(logp.gather(1, action.unsqueeze(1)).squeeze(1)) env.step(action) rewards = -env.total_dist # 总距离越短越好 # 利用 batch 内均值做经验基线，减少梯度方差 baseline = rewards.mean().detach() advantage = rewards - baseline loss = -(torch.stack(log_probs).sum(dim=0) * advantage).mean() optimizer.zero_grad() loss.backward() torch.nn.utils.clip_grad_norm_( list(encoder.parameters()) + list(decoder.parameters()), max_norm=2.0 ) optimizer.step() if step % 500 == 0: print(f"step {step}, reward={rewards.mean().item():.4f}")

这里用固定长度2 * num_customers + 2展开，路径已经完成的样本会被掩码强制选择仓库，后续步的距离为 0，不影响奖励。如果你想做得更精细，可以在同一实例上重复采样 group_size 条轨迹，然后对每条奖励按组取平均作为基线，这就是所谓的共享基线，方差会比全局均值更小。上面的代码为保持清晰用了最简单的全局均值，你可以在读到 5.5 节后回到这里改成组内基线。

梯度裁剪的max_norm是这里最容易忽略的参数。REINFORCE 的梯度方差本身就大，不裁剪的话偶尔一条“奇短”的路径会产生超大梯度，直接把网络参数推到 NaN。我用 2.0 这个值在 50~200 个客户的算例上都比较稳妥。

5. 避坑：训练强化学习 VRP 求解器时最常踩的五个坑

这部分是我自己反复折进去、又反复爬出来的地方，每条基本都是血泪教训换来的。

5.1 训练 loss 发散成 NaN：奖励尺度不一致

现象：训练跑到几百步，loss 突然变成 NaN，之后所有参数全废，只能重新开始。原因：REINFORCE 的梯度由reward * log_prob组成。当奖励的绝对数值很大，比如 500 个客户总距离几百个单位，advantage的尺度也跟着大，乘上 log_prob 后梯度数值很容易过界。再加上同一个 batch 里出现一条特别短的路径，这个 outlier 会让梯度直接爆炸。解决：先把 reward 按问题规模归一化，比如除以该实例的客户数；再做梯度裁剪，把max_norm压到 1.0~2.0 之间。我一般两个都做，单独靠梯度裁剪还是会在奖励尺度突然变化时露出破绽。

5.2 模型学会了“抄近路”：输出全是回仓库

现象：训练日志里 reward 不降，打印路径发现模型每次选完一两个客户就回仓库，整条路径又短又无意义。原因：仓库始终在动作空间里，如果模型发现“早回仓库”能快速结束 episode 并获得“不算太差”的奖励，它就会陷进这个局部最优。问题的根源是掩码给的自由度太大：在还有可服务客户时也放行了仓库。解决：把掩码逻辑收紧——只要还有任意一个客户能满足剩余载重，仓库就不出现在可选动作里。这个修改让模型被迫服务客户，回仓库只能发生在“当前载重装不下任何客户”或者“全部服务完”两种场合。改完之后绝大多数训练都能顺利前进。

5.3 mask 写错导致非法解被当成合法样本

现象：训练曲线正常下降，模型跑测试时却经常出现超载路径，而且超载量还挺大。原因：训练过程中模型只在“合法动作”里采样，按理不会出现超载。问题通常出在 mask 跟 step 的状态更新不同步：比如上一轮已经更新了remaining_capacity，但 mask 还在用旧的容量计算可访问节点；或者 batch 里某条路径已经服务完所有客户，但 mask 还允许它继续访问客户。解决：写环境的时候把 mask 的计算放在 step 之后、下一次决策之前，并且每次都从self.visited、self.remaining_capacity等状态变量现算，不要缓存上一轮的 mask 结果。再就是每训练 100 步调用一次 3.3 节的可行性校验函数，成本很低，但能及早发现问题。

5.4 训练集和验证集分布不一致，换了数据就崩

现象：训练集上平均路径长度收敛得不错，一换到新生成的实例上就比 OR-Tools 差 40% 以上，而且曲线波动剧烈。原因：随机种子固定得太死，训练循环每次都在同一批实例上反复跑，模型把坐标背下来了。这是深度学习里典型的过拟合到数据分布，而不是学到了“泛化求解”。解决：训练时每个 epoch 都重新生成随机实例，不要把数据集固定成一个静态列表；同时让训练数据里的客户数在一个区间内变化，比如训练 50~100，测试 100~200，泛化能力会有明显提升。如果要更严格，可以在训练集中留一部分种子永远不变，作为固定验证集，每次评估都用这一批。

5.5 batch 太小导致梯度方差大，训练像过山车

现象：loss 曲线不是平滑下降，而是上下横跳，reward 也时好时坏，甚至训练 5000 步跟 1000 步时的表现差不多。原因：REINFORCE 的本质是蒙特卡洛采样，梯度是采出来的，样本越少方差越大。batch=16 时，每个 step 的梯度几乎被噪声主导，模型根本找不到正确的优化方向。解决：把 batch_size 提到 512 以上，同时把 group_size 从 1 提升到 8 或者 16。同样的显存开销下，group_size 增大对方差的影响更明显，因为它让每一条轨迹都能跟同一实例的其他轨迹对比，而不是跟一批随机实例的均值对比。如果显存不够，优先减小客户数或者网络维度，而不是减 group_size。

6. 进阶：从能跑通到能交付，验证、参数与扩展方向

模型能收敛只是第一步，真正决定这套强化学习方案是否值得投产的，是它跟传统求解器在同等条件下谁更稳、谁更快、谁更容易调。

6.1 用 OR-Tools 做交叉验证

我常做的验证方式是固定 100 个随机实例，分别用 OR-Tools 的路径求解和强化学习模型跑，记录两者的总里程和运行时间，计算 gap：gap = (rl_total - or_tools_total) / or_tools_total。强化学习在 20 个客户的小实例上通常比不过精确算法，但在 200 客户规模下，训练好的模型往往能跟 OR-Tools 的启发式打平甚至略优，而推理时间只有后者的几十分之一。这个对比的结论比任何单点训练曲线都有说服力。

6.2 上线前要盯的参数化问题

部署前重点看三件事：客户规模是否超出训练分布，容量是否和需求分布匹配，以及坐标分布是否跟训练数据同源。很多模型在均匀分布上表现好，落地到实际城市路网就明显变差，原因是实际客户坐标往往有聚类特征。应对办法是在训练数据里混入聚类坐标，比如用高斯混合模型生成位置，这样模型才能学到“先扫一片区域再换下一个区域”的高层策略。