# Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem arXiv: https://arxiv.org/abs/2507.21386 ยท HTML: https://mlsanity.com/paper/2507.21386/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Builds on 33 of its 57 references that are in the map. - First posted on arXiv 28 Jul 2025. ## Builds on (most cited first, 30 of 33) - [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021) - [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015) - [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018) - [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020) - [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024) - [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018) - [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019) - [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023) - [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022) - [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021) - [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020) - [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023) - [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023) - [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024) - [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024) - [Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2110.02629/) (2021) - [CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention](https://mlsanity.com/paper/2412.00346/) (2024) - [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024) - [Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed](https://mlsanity.com/paper/2312.12469/) (2023) - [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024) - [Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context](https://mlsanity.com/paper/2306.02689/) (2023) - [Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2505.12627/) (2025) - [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024) - [Destroy and Repair Using Hyper Graphs for Routing](https://mlsanity.com/paper/2502.16170/) (2025) - [RRNCO: Towards Real-World Routing with Neural Combinatorial Optimization](https://mlsanity.com/paper/2503.16159/) (2025) - [An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem](https://mlsanity.com/paper/2501.13767/) (2025) - [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022) - [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023) - [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024) - [Incorporating Surprisingly Popular Algorithm and Euclidean Distance-based Adaptive Topology into PSO](https://mlsanity.com/paper/2108.11173/) (2021) ## Built on by (most cited first, 3 of 3) - [Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba](https://mlsanity.com/paper/2602.20730/) (2026) - [Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem](https://mlsanity.com/paper/2604.05195/) (2026) - [WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problems](https://mlsanity.com/paper/2605.22876/) (2026) ## Abstract (arXiv) Numerous Neural Combinatorial Optimization (NCO) solvers have been proposed to address Vehicle Routing Problems (VRPs). However, most of these solvers focus exclusively on single-vehicle VRP variants, overlooking the more realistic min-max Heterogeneous Capacitated Vehicle Routing Problem (MMHCVRP), which involves multiple vehicles. Existing MMHCVRP solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP, including local topological relationships, vehicle permutation invariance, and node symmetry, resulting in suboptimal performance. To better address these limitations, we propose ECHO, an efficient NCO solver. First, ECHO exploits the proposed dual-modality node encoder to capture local topological relationships among nodes. Subsequently, to mitigate myopic decisions, ECHO employs the proposed Parameter-Free Cross-Attention mechanism to prioritize the vehicle selected in the preceding decoding step. Finally, leveraging vehicle permutation invariance and node symmetry, we introduce a tailored data augment strategy for MMHCVRP to stabilize the Reinforcement Learning training process. To assess the performance of ECHO, we conduct extensive experiments. The experimental results demonstrate that ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns. Finally, ablation studies validate the effectiveness of all proposed methods.