Rethinking Light Decoder-based Solvers for Vehicle Routing Problems

Light decoder-based solvers have gained popularity for solving vehicle routing problems (VRPs) due to their efficiency and ease of integration with reinforcement learning algorithms. This paper revisits light decoder-based approaches, analyzing the implications of their reliance on static embeddings and the inherent challenges that arise. Specifically, we demonstrate that in the light decoder paradigm, the encoder is implicitly tasked with capturing information for all potential decision scenarios during solution construction within a single set of embeddings, resulting in high information density. Furthermore, our empirical analysis reveals that the overly simplistic decoder struggles to effectively utilize this dense information, particularly as task complexity increases, which limits generalization to out-of-distribution (OOD) settings. Building on these insights, we show that enhancing the decoder capacity, with a simple addition of identity mapping and a feed-forward layer, can considerably alleviate the generalization issue. Experimentally, our method significantly enhances the OOD generalization of light decoder-based approaches on large-scale instances and complex VRP variants, narrowing the gap with the heavy decoder paradigm. Our code is available at: https://github.com/ V ehicle Routing Problems (VRPs) are a fundamental class of NP-hard combinatorial optimization problems (COPs) with wide-ranging applications in logistics (Konstantakopoulos et al., 2022), transportation (Garaix et al., 2010), and supply chain management (Dondo et al., 2011). Efficiently solving VRPs is critical for reducing operational costs and enhancing service quality in practice. Traditionally, VRPs have been tackled either using exact solvers (e.g., Gurobi) or heuristic solvers (e.g., LKH-3 (Helsgaun, 2017)). While these methods can yield high-quality (or even optimal) solutions for small to moderate-sized instances, they often face challenges in scaling to larger problem sizes or adapting to different problem variants without extensive domain expertise or manual tuning. Neural solvers have emerged as a promising alternative by leveraging advanced deep learning techniques to learn solution strategies directly from data (Bengio et al., 2021). Numerous neural solvers have been proposed for solving VRPs (Bogyrbayeva et al., 2024), with autoregressive construction solvers gaining particular popularity. These solvers sequentially build solutions by adding one feasible node at a time and are valued for their conceptual simplicity and flexibility across different VRP variants. Among them, (heavy encoder) light decoder-based solvers (Vinyals et al., 2015; Kool et al., 2019; Kwon et al., 2020; Kim et al., 2022; Gao et al., 2024; Liu et al., 2024) stand out for their computational efficiency and ease of integration with reinforcement learning (RL) algorithms.