pytorch-drl4vrp

实现：Nazari, Mohammadreza 等人。“用于求解车辆路径问题的深度强化学习”。arXiv 预印本 arXiv:1802.04240 (2018)。

目前支持旅行商问题和车辆路径问题。详情请参阅 tasks/ 文件夹。

要求：

• Python 3.6
• pytorch=0.4.1
• matplotlib

运行方法

通过调用 python trainer.py 来运行。

可以通过 “task” 和 “nodes” 标志来更改任务和复杂度：

python trainer.py --task=vrp --nodes=10

要恢复检查点，必须指定包含 “actor.pt” 和 “critic.pt” 检查点的文件夹路径。示例权重可在 这里 找到。

python trainer.py --task=vrp --nodes=10 --checkpoint=vrp10

与论文的不同之处：

• 解码器网络使用 GRU 而不是 LSTM
• 评论家直接接收原始的静态和动态输入状态，并预测奖励
• 使用需求缩放（MAX_DEMAND / MAX_VEHICLE_CAPACITY），并为 VRP 的配送中心赋予一个与剩余运力成比例的负值（不确定是否实际使用）

TSP 示例路线：

左: 20 个城市 TSP

右: 50 个城市 TSP

VRP 示例路线：

左: 10 个城市 + 载重 20 的 VRP

右: 20 个城市 + 载重 30 的 VRP

TSP

TSP 使用以下掩码方案：

1. 如果销售员已经访问过某个城市，则不允许再次访问。

VRP

VRP 处理动态元素（载重 ‘L’、需求 ‘D’），这些元素在车辆/销售员每次访问城市时都会发生变化。每个城市的需求随机生成，范围为 [1, 9]。销售员的初始运力会根据问题的复杂度（例如节点数量）而变化。

VRP 使用以下 掩码方案：

1. 如果任何城市的需求已耗尽，则结束行程。这意味着车辆必须返回配送中心才能完成。
2. 只要车辆能够完全满足需求，就可以访问任何城市（如果需要，可以轻松修改为部分运输）。
3. 车辆不能连续两次访问配送中心（以加快训练速度）。
4. 只有当车辆已完成其路线并等待其他车辆完成时，才允许连续两次或多次访问配送中心（例如在小批量训练中）。

在该项目中，使用了以下动态更新：

1. 如果车辆访问某个城市，其载重将根据公式 Load = Load - Demand_i 进行调整，该城市的需求也将根据公式 Demand_i = (Demand_i - load)+ 进行更新。
2. 返回配送中心时，车辆的载重会被重新装满。配送中心被赋予一个“负”需求，该需求会随着车辆剩余载重量的增加而增大。

结果：

行程准确性

此仓库仅在测试时实现了“贪心”方法，即选择概率最高的城市。将本项目与相应论文相比，行程长度如下所示。行程长度的差异很可能可以通过超参数搜索进一步优化，但此处并未进行此类搜索。

	论文（“贪心”）	本项目
TSP20	3.97	4.032
TSP50	6.08	6.226
TSP100	8.44
VRP10 容量 20	4.84	5.082
VRP20 容量 30	6.59	6.904
VRP50 容量 40	11.39
VRP100 容量 50	17.23

训练时间

在 Tesla P-100 GPU 上，观察到以下训练时间。结果是通过统计前 100 次训练迭代的总时间（使用相应的批次大小），并将其转换为相应的时间单位得出的。请注意，对于 VRP 特别是，在这段时间内模型尚未充分训练，因此这些结果可能略有不准确，具体情况因人而异。

任务	批次大小	每 100 次更新所需时间（秒）	每轮所需时间（分钟）	每轮所需时间（小时）	20 轮
TSP20	128	8.23	10.71	0.18	3.57
TSP20	256	11.90	7.75	0.13	2.58
TSP20	512	19.10	6.22	0.10	2.07
TSP50	128	21.64	28.17	0.47	9.39
TSP50	256	31.33	20.40	0.34	6.80
TSP50	512	51.70	16.83	0.28	5.61
TSP100	128	48.27	62.85	1.05	20.95
TSP100	256	73.51	47.85	0.80	15.95

任务	批次大小	每 100 次更新所需时间（秒）	每轮所需时间（分钟）	每轮所需时间（小时）	20 轮
VRP10	128	12.15	15.82	0.26	5.27
VRP10	256	15.75	10.25	0.17	3.42
VRP10	512	23.30	7.58	0.13	2.53
VRP20	128	21.45	27.93	0.47	9.31
VRP20	256	28.29	18.42	0.31	6.14
VRP20	512	43.20	14.06	0.23	4.69
VRP50	128	53.59	69.77	1.16	23.26
VRP50	256	77.25	50.29	0.84	16.76
VRP50	512	127.73	41.58	0.69	13.86
VRP100	128	130.06	169.35	2.82	56.45
VRP100	64	95.03	247.48	4.12	82.49

致谢：

感谢 https://github.com/pemami4911/neural-combinatorial-rl-pytorch 提供关于 GPU 上随机数生成器错误的见解。

pytorch-drl4vrp 快速上手指南

本指南基于 Nazari 等人关于“利用深度强化学习解决车辆路径问题（VRP）”的论文实现，支持旅行商问题（TSP）和车辆路径问题（VRP）。

环境准备

在开始之前，请确保您的系统满足以下要求：

• 操作系统：Linux / macOS / Windows
• Python 版本：3.6
• 核心依赖：
  • PyTorch == 0.4.1
  • matplotlib

注意：由于该项目依赖较旧版本的 PyTorch (0.4.1)，建议创建独立的虚拟环境以避免版本冲突。国内用户可使用清华源或阿里源加速依赖安装。

安装步骤

1. 克隆项目代码

   git clone https://github.com/your-repo/pytorch-drl4vrp.git
   cd pytorch-drl4vrp
   

2. 创建并激活虚拟环境

   python -m venv venv
   source venv/bin/activate  # Windows 用户使用: venv\Scripts\activate
   

3. 安装依赖 国内用户推荐使用清华镜像源安装 PyTorch 特定版本及其他依赖：

   pip install torch==0.4.1 -i https://pypi.tuna.tsinghua.edu.cn/simple
   pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple
   

   (注：如果 pip 无法直接找到 torch 0.4.1，可能需要前往 PyTorch 官网历史版本页面下载对应的 .whl 文件进行本地安装)

基本使用

1. 启动训练

最简单的运行方式是直接调用 trainer.py。默认情况下，您可以指定任务类型（task）和城市节点数量（nodes）。

示例：训练一个包含 10 个节点的 VRP 模型

python trainer.py --task=vrp --nodes=10

示例：训练一个包含 20 个城市的 TSP 模型

python trainer.py --task=tsp --nodes=20

2. 加载预训练权重（断点续训）

如果您希望从已有的检查点继续训练或测试，需指定包含 actor.pt 和 critic.pt 文件的文件夹路径。

您可以从 Google Drive 下载示例权重，解压后执行：

python trainer.py --task=vrp --nodes=10 --checkpoint=vrp10

3. 结果说明

• 测试策略：本项目在测试阶段仅实现了“贪心（Greedy）”策略，即每一步选择概率最高的城市。
• 性能参考：在 Tesla P-100 GPU 上，TSP20 任务的贪心解长度约为 4.032（论文基准为 3.97）。通过进一步的超参数搜索，性能仍有优化空间。