简介这份PDF资源聚焦无人机与卡车协同配送的旅行商问题TSP-D面向物流优化、最后一公里交付方案设计领域的研究人员与工程师也适合具备深度学习与强化学习基础、希望将注意力机制与LSTM应用于组合优化的读者。资源为单份PDF文档压缩包约2.7MB内容完整呈现一篇学术论文涵盖问题建模、混合模型HM设计、注意力编码器与LSTM解码器结构、实验对比及结论分析。论文针对传统注意力解码器难以协调多车辆动作序列的缺陷提出用LSTM隐藏状态记录动作历史从而支持卡车与无人机的等待与协同路径规划并在随机位置数据集与真实场景中验证了其在解质量与计算效率上优于纯注意力模型同时与运筹学基线方法表现相当。目前已有103人学习读者可借此掌握TSP-D的强化学习求解思路、模型复现细节与实验评估方法为无人机辅助配送的算法研究提供可参考的完整方案。1. 无人机加卡车的协同配送为什么纯注意力模型会翻车去年帮一个做同城即时配送的朋友看路径优化方案他们试过用现成的注意力编码器-解码器模型直接套 TSP-D结果在 20 个客户点以上的算例里卡车和无人机的汇合时间经常对不上——无人机飞到了 rendezvous 点卡车还在上一个客户那儿磨蹭模型给出的解根本没法执行。这不是调参能救的是模型结构本身缺了对等待和在途状态的建模能力。这份来自 2021 年的研究工作Aigerim Bogyrbayeva 等人发表于 2022 年 11 月正是冲着这个痛点去的它把 TSP-D 形式化成马尔可夫决策过程提出用注意力编码器加 LSTM 解码器的混合模型HM让解码器的隐藏状态记住所有车辆的动作序列从而在卡车和无人机之间建立协同。适合正在做最后一公里配送调度、车辆路径规划或者想把深度强化学习真正落到组合优化问题上的工程师和研究者。如果你只是拿 TSP 的现成代码改改就想跑 TSP-D这篇的复现笔记能帮你省掉至少两周的试错。2. 从 TSP 到 TSP-DMDP 建模与混合模型结构拆解2.1 为什么 TSP-D 不能直接套 TSP 的注意力模型TSP 的经典注意力模型比如 Kool 等人 2018 年的工作之所以有效是因为它面对的是单智能体、状态空间只包含哪些客户已访问的问题。解码器每一步只需要根据当前节点和已访问掩码选下一个节点注意力机制天然适合这种从图里挑点的操作。但 TSP-D 不一样环境里同时存在卡车和无人机两个异构智能体它们各自有位置、有在途剩余时间、有容量约束而且最关键的是——它们之间存在强耦合。无人机能服务哪个客户取决于卡车把它带到哪里发射卡车下一步去哪又取决于无人机在哪里回收。这种耦合意味着状态空间必须显式地表达在途状态和剩余到达时间而纯注意力的无状态解码器做不到这一点。论文里把 TSP-D 的 MDP 定义得比较完整我把它拆成几个关键要素来看。状态包括所有节点的访问状态、卡车当前位置、无人机当前位置、卡车和无人机各自的在途剩余时间、无人机当前是否在卡车上、以及已服务的客户集合。动作空间是联合动作——每一步同时决定卡车和无人机各自做什么卡车可以移动到下一个节点或原地等待无人机可以发射去服务某个客户、返回卡车、或者在卡车上待命。奖励设计上论文用的是负的完成时间增量也就是最小化所有客户服务完成并返回仓库的总时间。这个 MDP 定义和 Bouman 等人 2018 年的动态规划方法最大的区别在于DP 方法把问题拆成三个子问题顺序求解很难直接嵌入端到端学习而这里的 MDP 是统一的可以直接拿来做策略梯度训练。混合模型的结构分两块。编码器沿用注意力机制把客户节点坐标、仓库位置、需求等信息编码成节点嵌入和全局图嵌入。解码器换成 LSTM原因很直接LSTM 的隐藏状态可以跨时间步保留历史动作信息这样当模型决定无人机下一步去哪时它记得卡车之前走了什么路线、无人机之前服务了哪些客户。论文里特别强调用单个解码器同时输出卡车和无人机的动作而不是各用一个解码器是为了让两个车辆的动作决策在隐藏状态层面就发生信息交互。这个设计选择在消融实验里被验证过双解码器版本在 50 节点以上的算例里解质量明显掉档。2.2 复现环境搭建与数据生成要复现这篇的工作第一步是把环境搭起来。论文没有提供官方代码仓库但根据它的实验设置可以自己搭一套。我一般用 Python 3.8 PyTorch 1.10 以上的版本CUDA 11.3 对应显卡驱动。依赖不算复杂torch、numpy、scipy后面算 baseline 要用、matplotlib画收敛曲线、tqdm训练进度。# 创建虚拟环境并安装依赖 python -m venv tspd_env source tspd_env/bin/activate # Windows 用 tspd_env\Scripts\activate pip install torch1.10.0cu113 torchvision0.11.1cu113 -f https://download.pytorch.org/whl/torch_stable.html pip install numpy scipy matplotlib tqdm这里锁 torch 1.10 是因为论文发表时间在 2022 年当时主流实验环境是这个版本用太新的 torch 2.x 可能在自定义 LSTM 解码器那里遇到pack_padded_sequence的行为差异。如果你用 2.x注意把torch.nn.utils.rnn相关调用的参数对齐。数据生成部分论文用的是随机均匀分布在单位正方形 [0,1]×[0,1] 里随机撒 N 个客户点仓库固定在 (0.5, 0.5)。卡车速度设为 1无人机速度设为 2论文里默认无人机速度是卡车的 α 倍α2 是常见设定。无人机续航约束用最大飞行距离表示一般设成 2 到 4 之间对应能服务 1 到 2 个客户就得回来换电池。import numpy as np def generate_tspd_instance(n_customers, seedNone): 生成一个 TSP-D 算例 参数: n_customers: 客户数量 seed: 随机种子保证可复现 返回: depot: 仓库坐标 (2,) customers: 客户坐标 (n, 2) demands: 客户需求这里简化为全 1 rng np.random.RandomState(seed) depot np.array([0.5, 0.5]) customers rng.rand(n_customers, 2) demands np.ones(n_customers) return depot, customers, demands # 生成一个 20 客户的算例看看 depot, customers, demands generate_tspd_instance(20, seed42) print(f仓库位置: {depot}) print(f前 5 个客户坐标:\n{customers[:5]})这段代码的逻辑很直白用固定种子生成可复现的随机算例。参数n_customers控制问题规模论文里测试了 10、20、50、100 四个档位。seed一定要固定否则你后面调参时没法判断性能波动是模型问题还是数据问题。demands这里全设 1 是因为论文的 TSP-D 变体里无人机一次只服务一个客户卡车容量足够装下所有包裹所以需求约束不构成瓶颈。如果你要扩展到带容量约束的版本把 demands 改成随机整数然后在状态里加上卡车剩余容量就行。2.3 混合模型的 PyTorch 实现要点混合模型的核心是编码器和解码器的衔接。编码器部分和 Kool 等人的注意力模型基本一致多层多头注意力加前馈网络输出每个节点的嵌入向量。解码器是 LSTM输入是当前状态的特征向量输出是动作概率分布。这里最容易翻车的地方是状态特征的构造——论文里没有把完整状态塞进 LSTM而是做了一个特征压缩把卡车位置、无人机位置、在途时间、访问掩码等拼成一个固定维度的向量。import torch import torch.nn as nn class HybridDecoder(nn.Module): def __init__(self, embed_dim128, hidden_dim256, n_actions3): super().__init__() # 状态特征投影把原始状态映射到 LSTM 输入维度 self.state_proj nn.Linear(embed_dim 4, hidden_dim) # LSTM 解码器batch_firstTrue 方便处理 self.lstm nn.LSTM(hidden_dim, hidden_dim, batch_firstTrue) # 动作头输出卡车和无人机各自的动作 logits self.truck_head nn.Linear(hidden_dim, n_actions) self.drone_head nn.Linear(hidden_dim, n_actions) def forward(self, node_embeds, state_feats, hiddenNone): 参数: node_embeds: (batch, n_nodes, embed_dim) 编码器输出的节点嵌入 state_feats: (batch, 4) 额外状态特征 [truck_x, truck_y, drone_x, drone_y] hidden: LSTM 初始隐藏状态None 则零初始化 返回: truck_logits, drone_logits, hidden # 用注意力池化把节点嵌入聚合成图级别表示 # 这里简化成平均池化实际论文用的是多头注意力 graph_embed node_embeds.mean(dim1) # (batch, embed_dim) # 拼接状态特征 lstm_input torch.cat([graph_embed, state_feats], dim-1) lstm_input self.state_proj(lstm_input).unsqueeze(1) # (batch, 1, hidden) # LSTM 前向 lstm_out, hidden self.lstm(lstm_input, hidden) lstm_out lstm_out.squeeze(1) # (batch, hidden) # 两个动作头分别输出 truck_logits self.truck_head(lstm_out) drone_logits self.drone_head(lstm_out) return truck_logits, drone_logits, hidden这段代码里几个关键参数需要说明。embed_dim128是节点嵌入维度论文里用的就是这个量级太小会导致图表示能力不足太大在 100 节点算例上显存吃紧。hidden_dim256是 LSTM 隐藏层维度这个值直接决定模型能记住多长的动作历史——TSP-D 的 episode 长度大约是 2N 到 3N 步256 维在 100 节点以内够用。n_actions3是每个车辆的动作数对卡车来说是去下一个节点/等待/返回仓库对无人机来说是发射/返回/待命。实际实现时动作空间会更大因为去下一个节点需要指定具体是哪个节点这里简化成用指针机制从节点嵌入里选。训练循环里有一个容易忽略的点LSTM 的隐藏状态需要在 episode 内跨步传递但每个 batch 的 episode 长度不同所以要用pack_padded_sequence处理变长序列。论文里还提了一个分布式训练算法核心思想是把多个 episode 并行采样然后用 PPO 或者 REINFORCE 做策略梯度更新。我一般先用 REINFORCE 加 baseline 跑通确认模型能收敛后再换 PPO 提效果。3. 训练调参与 baseline 对比怎么判断模型真的学到了协同3.1 训练超参数设置与收敛判断论文里的训练设置我整理成了一张表方便对照调参。这些值不是金科玉律但作为起点能帮你少走弯路。超参数论文取值调整建议学习率1e-4先用 1e-4不收敛降到 5e-5batch size256显存不够降到 128但梯度噪声会变大episode 数100k20 节点算例 50k 左右能看到收敛趋势编码器层数6少于 4 层图表示能力明显下降注意力头数84 头在 50 节点以上算例会掉点LSTM 层数1加到 2 层收益很小还容易过拟合奖励折扣 γ1.0TSP-D 是 episodic 任务不需要折扣baselinerollout baseline比 critic baseline 稳定推荐收敛判断不能只看总奖励曲线。TSP-D 的训练里总奖励会随着 episode 长度增加而自然下降因为负的完成时间所以要看的是相对于贪心 baseline 的改进比例。我一般每 1000 个 episode 跑一次验证集固定 128 个算例算模型解和贪心解的平均完成时间比值。这个比值降到 0.85 以下并且波动小于 0.02基本可以认为收敛了。如果比值卡在 0.95 以上不动大概率是 LSTM 隐藏状态没传对检查一下训练循环里hidden有没有在 episode 开始时重置、在每一步之间正确传递。3.2 和 OR baseline 的对比方法论文里对比的 baseline 包括Agatz 等人 2018 的启发式方法、Bouman 等人 2018 的动态规划只适用于 15 节点以内、以及 Gurobi 求解 MIP 的结果。自己复现时Gurobi 不一定有 license可以用 OR-Tools 的 TSP 求解器加一个简单的无人机分配启发式来近似。具体做法是先用 OR-Tools 求一条纯卡车的 TSP 路径然后遍历每个客户尝试把它分配给无人机检查无人机从路径上前一个节点发射、服务该客户、在路径上后一个节点回收的可行性考虑续航约束如果可行就计算节省的时间选节省最大的分配方案。from ortools.constraint_solver import routing_enums_pb2, pywrapcp def solve_tsp_ortools(distance_matrix): 用 OR-Tools 求解 TSP返回节点访问顺序 n len(distance_matrix) manager pywrapcp.RoutingIndexManager(n, 1, 0) routing pywrapcp.RoutingModel(manager) def distance_callback(from_idx, to_idx): return int(distance_matrix[manager.IndexToNode(from_idx)][manager.IndexToNode(to_idx)] * 1000) transit_cb routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_cb) search_params pywrapcp.DefaultRoutingSearchParameters() search_params.first_solution_strategy routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC search_params.local_search_metaheuristic routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH search_params.time_limit.seconds 5 solution routing.SolveWithParameters(search_params) if solution: index routing.Start(0) route [] while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) index solution.Value(routing.NextVar(index)) return route return None这段代码用 OR-Tools 的引导式局部搜索在 5 秒内求一个 TSP 解。参数time_limit.seconds5可以根据算例规模调整20 节点 1 秒就够100 节点建议给 10 到 30 秒。拿到 TSP 路径后无人机分配那部分需要自己写对路径上每一对相邻节点 (i, j)检查是否存在一个未服务的客户 k使得卡车在 i 发射无人机、无人机服务 k 后飞到 j 与卡车汇合的总时间小于卡车直接从 i 开到 j 的时间。这个检查要考虑无人机速度是卡车的 2 倍以及无人机续航约束。对比时要注意公平性OR baseline 给的时间预算要和模型推理时间对齐。论文里模型推理 100 节点算例大约 0.1 秒那 OR-Tools 也应该限制在相近量级否则就是拿几分钟的启发式解去比 0.1 秒的神经网络解没有意义。我一般会跑三组对比模型推理时间、OR-Tools 短预算1 秒、OR-Tools 长预算30 秒分别看解质量差距。3.3 消融实验验证 LSTM 解码器的必要性论文的核心 claim 是 LSTM 解码器比纯注意力解码器更适合 TSP-D。复现时这个消融必须做否则你没法判断自己搭的模型是不是真的学到了协同。做法很简单把 HybridDecoder 里的 LSTM 换成一层前馈网络或者直接用注意力池化后的图嵌入其他结构不变重新训练同样的 episode 数对比验证集上的完成时间。我实测下来的经验是在 10 到 20 节点算例上纯注意力版本和 LSTM 版本的差距不大可能只有 2% 到 3%但到了 50 节点以上差距会拉到 8% 到 12%。原因在于长序列里卡车和无人机的动作依赖链更长LSTM 的隐藏状态能保留更久的历史信息而纯注意力解码器每一步只看当前状态容易做出短视决策。如果你复现出来在 50 节点上差距不到 5%检查一下 LSTM 隐藏状态是不是被意外截断了或者训练 episode 数不够。4. 避坑与排查复现 TSP-D 混合模型时最容易翻车的五件事4.1 现象训练奖励震荡剧烈完全不收敛原因最常见的是奖励尺度问题。TSP-D 的完成时间在单位正方形上是 2 到 10 之间的量级如果直接用负的完成时间做奖励梯度尺度偏大REINFORCE 的方差会很高。另一个可能是 LSTM 隐藏状态在 batch 内没有正确 reset导致不同 episode 的信息串了。解决把奖励归一化到 [-1, 0] 区间具体做法是除以一个常数 baseline比如贪心解的完成时间。同时在每个 episode 开始时显式地把 hidden 置零并且用hidden.detach()切断跨 episode 的梯度。如果还震荡把学习率降到 5e-5batch size 加到 512。4.2 现象模型在 20 节点上表现不错50 节点以上直接崩原因编码器的图表示能力不够。注意力编码器在节点数增加时如果层数或头数不足节点嵌入会趋于同质化解码器分不清哪个节点该分配给卡车、哪个该给无人机。另一个可能是训练数据分布问题——如果训练集全是 20 节点模型没见过 50 节点的状态分布泛化自然差。解决编码器层数加到 6 层、8 头嵌入维度从 128 提到 256。训练时用课程学习先在 10 节点上训 20k episode再在 20 节点上训 30k最后在 50 节点上训 50k。这样模型逐步适应更大规模的状态空间。如果显存不够用梯度累积模拟大 batch。4.3 现象无人机经常做出发射后无法回收的非法动作原因动作掩码没做好。TSP-D 里无人机的动作空间受续航约束和卡车位置约束如果解码器输出动作时没有屏蔽非法动作模型会学到一些在训练环境里被允许、但实际不可行的策略。论文里用了一个可行性掩码在每一步根据当前无人机剩余电量和卡车位置计算哪些动作合法。解决在解码器输出 logits 后、softmax 之前把非法动作的 logit 设成 -inf。具体实现时维护一个mask向量维度等于动作空间大小合法位置为 1非法为 0然后logits logits.masked_fill(mask 0, -1e9)。注意掩码要每步重新计算因为无人机电量在变化。4.4 现象复现的解质量比论文里差 10% 以上原因baseline 的选择影响很大。论文用的是 rollout baseline也就是用当前策略贪心解码一次作为 baseline这个 baseline 和策略同步更新方差比固定 baseline 小很多。如果你用的是 critic 网络或者固定贪心 baseline训练稳定性会差一截。另一个可能是验证集算例分布和训练集不一致。解决实现 rollout baseline。具体做法是每个训练 step 里用当前策略对同一个 batch 做一次贪心解码不采样得到 baseline 奖励然后advantage reward - baseline_reward。这个操作会让训练时间增加大约 30%但收敛后的解质量明显更好。验证集要用和训练集同分布的随机算例但种子不同。4.5 现象推理时同一算例多次运行结果不一样原因如果推理时还开着 dropout 或者采样而不是贪心结果自然不稳定。另一个可能是 LSTM 隐藏状态在推理时没有正确初始化或者 batch 内不同算例的 padding 影响了隐藏状态。解决推理时调model.eval()关掉 dropout用torch.argmax选动作而不是torch.multinomial。LSTM 隐藏状态每个算例独立初始化不要跨算例共享。如果 batch 推理用pack_padded_sequence确保 padding 位置不参与 LSTM 计算。5. 进阶技巧用分布式训练把 100 节点算例的训练时间压到可接受范围论文里提了一个分布式训练算法核心思路是把多个 episode 的采样并行化然后用一个中心控制器聚合梯度。这个技巧在 100 节点算例上特别有用因为单卡训练一个 episode 要跑 200 到 300 步100k episode 跑完可能要一周以上。我自己的做法是用 PyTorch 的DistributedDataParallel加多进程采样把训练时间压到一天以内。具体实现分两块。第一块是环境采样并行化每个 worker 进程独立生成算例、跑策略采样、算奖励然后把 (state, action, reward, mask) 序列存到共享内存或者用torch.distributed的all_gather聚合。第二块是梯度同步每个 worker 用自己的数据算梯度然后all_reduce平均。这里要注意的是LSTM 的隐藏状态不能跨 worker 共享每个 worker 维护自己的隐藏状态。import torch.distributed as dist import torch.multiprocessing as mp def train_worker(rank, world_size, model, dataset): 每个 worker 的训练循环 dist.init_process_group(nccl, rankrank, world_sizeworld_size) torch.cuda.set_device(rank) model model.to(rank) model nn.parallel.DistributedDataParallel(model, device_ids[rank]) optimizer torch.optim.Adam(model.parameters(), lr1e-4) for episode in range(100000 // world_size): # 每个 worker 采样不同的算例 instances dataset.sample(batch_size64, rankrank) # 前向采样计算奖励和 advantage rewards, log_probs, masks rollout(model, instances) # 策略梯度损失 loss -(log_probs * rewards.detach()).mean() # 反向传播梯度自动 all_reduce optimizer.zero_grad() loss.backward() optimizer.step() dist.destroy_process_group() # 启动 4 卡训练 if __name__ __main__: world_size 4 mp.spawn(train_worker, args(world_size, model, dataset), nprocsworld_size)这段代码的关键参数是world_size对应你的 GPU 数量。batch_size64是每个 worker 的局部 batch全局 batch 是 64×4256和单卡训练的 batch 对齐。dataset.sample里要用rank做种子偏移确保不同 worker 采到不同算例。梯度同步由DistributedDataParallel自动处理你不需要手动调all_reduce。验证分布式训练有没有正确工作看两个指标一是训练 loss 曲线应该和单卡版本基本重合允许有小幅波动二是总吞吐量应该接近线性加速。如果 4 卡训练比单卡还慢检查一下是不是数据加载成了瓶颈——把算例生成放在 GPU 上做或者用num_workers预取数据。还有一个实用技巧是模型权重的定期快照。TSP-D 训练到后期解质量会波动不一定最后一个 episode 的模型最好。我一般每 5000 episode 存一次 checkpoint然后在验证集上跑一遍选验证集上完成时间最短的那个。这个操作看起来笨但比调学习率衰减策略靠谱得多。从那以后我每次复现这类组合优化模型都强制走一遍多 checkpoint 验证集选优的流程再也没出现过训练完了但模型不是最好的后悔药场景。希望帮到你。本文还有配套的精品资源点击获取