Reinforcement Learning for Solving the Vehicle Routing Problem
计 算 机 与 大 数 据 学 院 Fuzhou University Reinforcement Learning for Solving the Vehicle Routing Problem 论 文 出 处 ： 32nd Conference on Neural Information Processing Systems 发 表 时 间 ： 2018 作 者 ： 汇 报 人 ： 邱 添 立 日 期 ： 2023-11-10 基 于 强 化 学 习 的 车 辆 路 径 问 题 求 解
1.摘要
1. 摘 要 本 文 使 用 强 化 学 习 解 决 车 辆 路 径 问 题 （ VRP ） 。 训 练 一 个 单 一 的 策 略 模 型 ， 该 模 型 仅 通 过 观 察 奖 励 信 号 和 遵 循 可 行 性 规 则 来 为 类 似 大 小 的 各 种 问 题 实 例 找 到 接 近 最 优 的 解 决 方 案 。 训 练 好 的 模 型 产 生 一 系 列 连 续 动 作 的 解 决 方 案 ， 而 不 需 要 为 每 个 新 的 问 题 实 例 重 新 训 练 。 在 容 量 受 限 的 VRP 上 ， 本 文 的 方 法 在 中 等 规 模 的 实 例 上 的 解 决 方 案 质 量 优 于 经 典 的 算 法 和 Google 的 OR 工 具 ， 并 且 计 算 时 间 相 当 。
2.引言
2. 引 言 车 辆 路 径 问 题 （ VRP ） 是 一 个 组 合 优 化 问 题 ， 在 VRP 的 最 简 单 形 式 中 ， 单 个 容 量 受 限 的 车 辆 负 责 将 物 品 运 送 到 多 个 客 户 节 点 ; 车 辆 用 完 时 必 须 返 回 仓 库 拾 取 额 外 的 物 品 。 其 目 标 是 优 化 一 组 路 线 ， 所 有 的 起 点 和 终 点 都 在 一 个 给 定 的 节 点 ， 以 获 得 最 大 可 能 的 回 报 。 本 文 开 发 了 一 个 框 架 ， 能 够 使 用 强 化 学 习 解 决 各 种 组 合 优 化 问 题 ， 并 展 示 了 如 何 将 其 应 用 于 解 决 VRP 。 其 中 的 最 佳 解 决 方 案 可 以 被 视 为 一 个 序 列 的 决 定 。 这 允 许 我 们 使 用 RL 通 过 解 码 “ 期 望 ” 序 列 的 概 率 来 产 生 接 近 最 优 的 解 决 方 案 。
2.引言
2. 引 言 本 文 的 方 法 受 到 Bello 等 人 工 作 的 启 发 。 他 们 用 了 Pointer Network 来 解 码 得 到 解 。 这 种 方 法 不 能 直 接 应 用 到 VRP 的 一 个 最 重 要 原 因 ， 是 他 们 假 定 系 统 是 静 态 的 。 但 是 在 VRP 问 题 中 ， 节 点 的 需 求 是 动 态 变 化 的 ， 一 旦 节 点 的 需 求 被 满 足 了 ， 就 会 变 为 0 。 为 了 克 服 这 个 问 题 ， 本 文 的 模 型 由 RNN 解 码 器 和 注 意 力 机 制 组 成 。 在 每 个 时 间 步 ， 静 态 元 素 的 embedding 会 输 入 给 RNN 解 码 器 ， RNN 解 码 器 的 输 出 和 动 态 元 素 的 embedding 会 输 入 给 注 意 力 机 制 ， 然 后 形 成 下 一 个 可 行 决 策 点 的 概 率 分 布 。
3.模型概述
3. 模 型 概 述  
3.模型概述
3. 模 型 概 述 RNN 只 有 当 输 入 传 递 了 有 序 信 息 时 才 有 必 要 ， 例 如 ， 在 文 本 翻 译 场 景 ， 单 词 之 间 的 相 对 关 系 必 须 要 学 到 。 但 在 组 合 优 化 问 题 中 ， 输 入 集 合 中 的 元 素 之 间 的 顺 序 并 没 有 任 何 意 义 。 因 此 ， 去 掉 了 RNN 编 码 器 ， 只 用 输 入 的 embedding 代 替 了 RNN 的 隐 状 态 。 指 针 网 络 很 好 地 解 决 了 只 有 静 态 信 息 的 问 题 ， 但 是 不 适 用 于 更 复 杂 的 组 合 优 化 问 题 ， 尤 其 是 系 统 表 示 随 时 间 变 化 的 问 题 ， 例 如 VRP 。
3.模型概述
3. 模 型 概 述 a t 描 述 了 每 个 输 入 在 下 一 个 decoding 步 t 中 多 大 程 度 上 是 相 关 的 。 RNN decoder 上 下 文 向 量
3.模型概述
3. 模 型 概 述    
3.模型概述
3. 模 型 概 述 训 练 方 法 ： AC 算 法 （ i ） actor 网 络 在 每 个 决 策 步 骤 预 测 出 next 动 作 的 概 率 分 布 。 （ ii ） critic 网 络 来 估 计 任 意 问 题 实 力 中 给 定 状 态 的 reward 。
4.实验
4. 实 验 实 验 设 置 ： 假 设 节 点 位 置 位 置 分 布 在 [0,1]*[0,1] 的 方 格 内 。 每 个 节 点 的 需 求 是 {1,…,9} 的 整 数 。 假 设 时 间 0 时 ， 车 辆 在 仓 库 位 置 ， decoder 的 第 一 个 输 入 是 仓 库 位 置 的 embedding 。 在 每 个 decoder 步 ， 车 辆 从 客 户 节 点 或 者 仓 库 作 为 下 一 个 遍 历 点 。 两 种 不 同 的 解 码 方 式 ： （ i ） greedy ： 每 次 解 码 时 选 概 率 最 高 的 （ ii ） Beam Search （ BS ） ： 会 维 护 最 有 可 能 的 几 条 路 径 ， 然 后 选 择 长 度 最 小 的 一 条 路 径
4.实验
4. 实 验
5.结论
5. 结 论 与 许 多 经 典 的 算 法 不 同 ， 本 文 提 出 的 方 法 随 着 问 题 规 模 的 增 加 而 扩 展 ， 并 且 具 有 更 好 的 性 能 。 它 不 需 要 计 算 繁 琐 距 离 矩 阵 ， 特 别 是 在 动 态 变 化 的 VRP 。 并 且 所 提 出 的 算 法 不 仅 限 于 VRP ， 还 可 以 将 其 应 用 到 其 他 组 合 优 化 问 题 。 这 种 方 法 非 常 有 吸 引 力 ， 只 需 要 知 道 奖 励 和 可 行 性 的 规 则 ， 一 旦 经 过 训 练 的 策 略 可 用 ， 它 就 可 以 多 次 使 用 ， 而 不 需 要 重 新 训 练 新 问 题 。
谢谢！
计 算 机 与 大 数 据 学 院 Fuzhou University 谢 谢 ！