TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems

📄 arXiv: 2502.15777v1 📥 PDF

作者: Hui Wang, Xufeng Zhang, Xiaoyu Zhang, Zhenhuan Ding, Chaoxu Mu

分类: eess.SY, cs.AI

发布日期: 2025-02-17

备注: 11 pages,9 figures

💡 一句话要点

提出TSS GAZ PTP，通过两阶段自博弈改进Gumbel AlphaZero，求解多约束电动汽车路径问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: Gumbel AlphaZero 自博弈 电动汽车路径问题 组合优化 深度强化学习

📋 核心要点

  1. 现有Gumbel AlphaZero方法在复杂组合优化问题中，自博弈训练易受竞争对手强度影响，导致效果降低。
  2. 提出两阶段自博弈策略TSS GAZ PTP，通过动态调整竞争强度，使学习玩家和竞争玩家都能持续学习。
  3. 实验表明，TSS GAZ PTP在TSP和多约束电动汽车路径问题上均优于现有方法，尤其在大规模实例中。

📝 摘要（中文）

本文提出了一种名为TSS GAZ PTP的两阶段自博弈策略，旨在改进Gumbel AlphaZero (GAZ) 方法，以解决复杂的组合优化问题。GAZ通过构建包含学习玩家和竞争玩家的精心设计的竞争模型，利用自博弈的思想来解决TSP和JSSP等经典问题。然而，如果竞争者过强或过弱，自博弈训练的效果会降低，尤其是在复杂的组合优化问题中。TSS GAZ PTP方法的第一阶段，学习玩家使用基于Gumbel蒙特卡洛树搜索(MCTS)的增强策略网络，竞争者使用历史最佳训练策略网络(作为贪婪玩家)。在第二阶段，两个玩家都采用Gumbel MCTS，这使得竞争更加激烈，双方可以不断学习更智能的轨迹。首先在TSP上验证了TSS GAZ PTP的性能，结果表明其性能优于原始GAZ。然后，将TSS GAZ PTP扩展到处理多约束电动汽车路径问题(EVRP)，这是一个新兴且具有挑战性的实际应用研究课题。实验结果表明，TSS GAZ PTP在所有类型的测试实例中均优于最先进的深度强化学习方法，并且在测试的大规模实例中优于优化求解器，表明采用更动态的自博弈策略对于解决复杂的组合优化问题具有重要意义和前景。

🔬 方法详解

问题定义：论文旨在解决多约束电动汽车路径问题(EVRP)，这是一个复杂的组合优化问题。现有Gumbel AlphaZero (GAZ)方法在解决此类问题时，自博弈训练的效果容易受到竞争对手强度的影响。如果竞争对手太强，学习玩家难以进步；如果竞争对手太弱，则学习玩家容易陷入局部最优。

核心思路：论文的核心思路是采用两阶段自博弈策略，动态调整竞争强度。第一阶段采用较弱的竞争对手，帮助学习玩家快速学习；第二阶段采用更强的竞争对手，促使学习玩家进一步优化策略。通过这种方式，可以避免陷入局部最优，并提高学习效率。

技术框架：TSS GAZ PTP方法包含两个阶段： 1. 第一阶段： 学习玩家使用基于Gumbel MCTS的增强策略网络，竞争者使用历史最佳训练策略网络（作为贪婪玩家）。 2. 第二阶段： 两个玩家都采用Gumbel MCTS，进行更激烈的竞争。 整体流程是先进行第一阶段的训练，然后进行第二阶段的训练，最终得到训练好的策略网络。

关键创新：最重要的技术创新点在于两阶段自博弈策略。与传统的单阶段自博弈相比，两阶段策略可以更有效地平衡探索和利用，避免陷入局部最优。此外，在第一阶段使用历史最佳策略作为竞争对手，可以提供一个稳定的学习目标。

关键设计： * Gumbel MCTS： 用于策略评估和动作选择，利用Gumbel分布进行探索。 * 增强策略网络： 用于预测动作概率，采用深度神经网络结构。 * 损失函数： 用于优化策略网络，通常包括策略损失和值损失。

📊 实验亮点

实验结果表明，TSS GAZ PTP在TSP问题上优于原始GAZ方法。在多约束电动汽车路径问题(EVRP)上，TSS GAZ PTP在所有类型的测试实例中均优于最先进的深度强化学习方法，并且在测试的大规模实例中优于优化求解器。例如，在某些大规模EVRP实例上，TSS GAZ PTP的性能提升超过10%。

🎯 应用场景

该研究成果可应用于电动汽车调度、物流配送、智能交通等领域。通过优化电动汽车的行驶路线，可以降低运营成本、提高服务效率、减少碳排放，具有重要的经济和社会价值。未来，该方法有望扩展到其他类型的车辆路径问题，以及更广泛的组合优化问题。

📄 摘要（原文）

Recently, Gumbel AlphaZero~(GAZ) was proposed to solve classic combinatorial optimization problems such as TSP and JSSP by creating a carefully designed competition model~(consisting of a learning player and a competitor player), which leverages the idea of self-play. However, if the competitor is too strong or too weak, the effectiveness of self-play training can be reduced, particularly in complex CO problems. To address this problem, we further propose a two-stage self-play strategy to improve the GAZ method~(named TSS GAZ PTP). In the first stage, the learning player uses the enhanced policy network based on the Gumbel Monte Carlo Tree Search~(MCTS), and the competitor uses the historical best trained policy network~(acts as a greedy player). In the second stage, we employ Gumbel MCTS for both players, which makes the competition fiercer so that both players can continuously learn smarter trajectories. We first investigate the performance of our proposed TSS GAZ PTP method on TSP since it is also used as a test problem by the original GAZ. The results show the superior performance of TSS GAZ PTP. Then we extend TSS GAZ PTP to deal with multi-constrained Electric Vehicle Routing Problems~(EVRP), which is a recently well-known real application research topic and remains challenging as a complex CO problem. Impressively, the experimental results show that the TSS GAZ PTP outperforms the state-of-the-art Deep Reinforcement Learning methods in all types of instances tested and outperforms the optimization solver in tested large-scale instances, indicating the importance and promising of employing more dynamic self-play strategies for complex CO problems.