TLDR: POMO+ is an improved version of the reinforcement learning model POMO, designed to solve the Capacitated Vehicle Routing Problem (CVRP). It enhances POMO by adding a lightweight auxiliary agent that learns to select optimal starting nodes for vehicle routes. This modification leads to faster convergence and better solutions, particularly for CVRP instances with up to 100 customers, demonstrating improved performance and scalability compared to the original POMO model.
The world of logistics and transportation constantly seeks efficiency, and at its heart lies a complex challenge known as the Vehicle Routing Problem (VRP). This problem, which generalizes the Traveling Salesman Problem, aims to find the most cost-effective routes for a fleet of vehicles starting and ending at a central depot, all while meeting customer demands. Even minor improvements in route optimization can lead to significant savings, with industrial studies reporting 5–30% lower transport costs.
Because VRP is computationally very difficult (NP-hard), traditional exact algorithms struggle with more than a few dozen customers. This has led researchers to rely on heuristic methods, from classical savings algorithms to modern genetic algorithms and large-neighborhood search techniques. Among the many variants of VRP, the Capacitated VRP (CVRP), where each vehicle has a limited capacity, is one of the most studied and widely applied in practice.
In recent years, Machine Learning (ML), particularly Reinforcement Learning (RL), has emerged as a powerful alternative to traditional heuristics. Attention-based policies trained with RL can now match specialized solvers on instances with 100 nodes, offering much faster inference. Models like the Attention Model (AM) and POMO have set new benchmarks for neural VRP heuristics.
A new research paper, titled “POMO+: Leveraging starting nodes in POMO for solving Capacitated Vehicle Routing Problem,” introduces an enhancement to the state-of-the-art POMO model. Authored by Szymon Jakubicz, Karol Kuźniak, and Jan Wawszczak from the University of Warsaw, Poland, along with Paweł Gora from Fundacja Quantum AI, this work addresses a specific area for improvement in POMO for VRP variants.
The original POMO model, which stands for Policy Optimisation with Multiple Optima, generates multiple trajectories simultaneously by launching one rollout from every customer node and averaging their costs. While effective, the authors of POMO noted that for VRP problems, there was potential for improvement by strategically choosing which nodes to start the rollouts from. Unlike the Traveling Salesman Problem where the starting node doesn’t affect the optimal cycle, in VRP, the initial customer directly influences the entire trajectory of a vehicle, making the choice of starting nodes crucial.
This is where POMO+ comes in. The researchers developed a lightweight auxiliary agent that learns to select the best starting nodes for VRP variants. This agent is trained alongside the main POMO model and leverages the hidden representations produced by POMO’s Attention Model Encoder. This approach is highly efficient as it avoids training a separate encoder, thus not significantly increasing training time.
The auxiliary agent’s architecture is simple, consisting of a Multi-Head Attention layer and a feed-forward network. It processes the node representations from the encoder and computes a score for each node, generating a probability distribution over them. During training, it uses Gumbel–Softmax to sample K starting nodes, repeating each N/K times to match the total number of trajectories with the number of clients (N).
Experiments were conducted on CVRP instances with 20, 50, and 100 customers using both synthetic datasets and the CVRPLIB benchmark. The results are promising: POMO+ consistently showed faster convergence and achieved better solutions compared to the vanilla POMO model. The performance gap was most significant for instances with 20 customers and gradually narrowed for larger instances, but POMO+ maintained its superior performance. On the CVRPLIB benchmark, POMO+ demonstrated a lower optimality gap for N=20 and N=50, with more ambiguous but still competitive results for N=100, suggesting potential for further optimization with more training epochs or different parameter choices.
Also Read:
- AI-Powered Route Planning: A New Approach to Vehicle Routing Challenges
- Understanding Key Features for Better Vehicle Routing Solutions
In conclusion, POMO+ offers a valuable and lightweight enhancement to existing POMO-based models for solving VRP problems. The research highlights the importance of informed starting node selection in VRP and provides a method that converges faster and achieves better results, particularly for problem instances with up to 100 customers. This work paves the way for further advancements in reinforcement learning methods for combinatorial optimization problems like VRP. You can read the full research paper here.
