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

arXiv: https://arxiv.org/abs/2502.15777 · HTML: https://mlsanity.com/paper/2502.15777/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Builds on (most cited first, 8 of 8)

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Emergent Complexity via Multi-Agent Competition](https://mlsanity.com/paper/1710.03748/) (2017)
- [Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/1807.01672/) (2018)
- [Learning to Optimize Industry-Scale Dynamic Pickup and Delivery Problems](https://mlsanity.com/paper/2105.12899/) (2021)
- [Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning](https://mlsanity.com/paper/2006.07970/) (2020)
- [Adaptive Warm-Start MCTS in AlphaZero-like Deep Reinforcement Learning](https://mlsanity.com/paper/2105.06136/) (2021)
- [Policy-Based Self-Competition for Planning Problems](https://mlsanity.com/paper/2306.04403/) (2023)
- [SmartPathfinder: Pushing the Limits of Heuristic Solutions for Vehicle Routing Problem with Drones Using Reinforcement Learning](https://mlsanity.com/paper/2404.13068/) (2024)

## Abstract (arXiv)

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.