# How Good Is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2022.

## Built on by (most cited first, 27 of 27)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024)
- [It's Morphing Time: Unleashing the Potential of Multiple LLMs via Multi-objective Optimization](https://mlsanity.com/paper/2407.00487/) (2024)
- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)
- [Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design](https://mlsanity.com/paper/2509.24509/) (2025)
- [Survey on Neural Routing Solvers](https://mlsanity.com/paper/2602.21761/) (2026)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2503.10421/) (2025)
- [LiBOG: Lifelong Learning for Black-Box Optimizer Generation](https://mlsanity.com/paper/2505.13025/) (2025)
- [GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2405.12475/) (2024)
- [Hardware-Aware DNN Compression for Homogeneous Edge Devices](https://mlsanity.com/paper/2501.15240/) (2025)
- [Lifelong Learning with Behavior Consolidation for Vehicle Routing](https://mlsanity.com/paper/2509.21765/) (2025)
- [Neural QAOA2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization](https://mlsanity.com/paper/2605.13072/) (2026)
- [Memory efficient location recommendation through proximity-aware representation](https://mlsanity.com/paper/2310.06484/) (2023)
- [Attention is All You Need to Optimize Wind Farm Operations and Maintenance](https://mlsanity.com/paper/2410.24052/) (2024)
- [Multi-Dimensional AGV Path Planning in 3D Warehouses Using Ant Colony Optimization and Advanced Neural Networks](https://mlsanity.com/paper/2504.01985/) (2025)
- [Scalable Structure Learning of Bayesian Networks by Learning Algorithm Ensembles](https://mlsanity.com/paper/2506.22848/) (2025)
- [Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Unified Tool](https://mlsanity.com/paper/2507.22440/) (2025)
- [Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem](https://mlsanity.com/paper/2508.08718/) (2025)
- [CogMCTS: A Novel Cognitive-Guided Monte Carlo Tree Search Framework for Iterative Heuristic Evolution with Large Language Models](https://mlsanity.com/paper/2512.08609/) (2025)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)
- [Keep Rehearsing and Refining: Lifelong Learning Vehicle Routing under Continually Drifting Tasks](https://mlsanity.com/paper/2601.22509/) (2026)
- [Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization](https://mlsanity.com/paper/2608.13087/) (2026)

## Abstract (arXiv)

Traditional solvers for tackling combinatorial optimization (CO) problems are usually designed by human experts. Recently, there has been a surge of interest in utilizing deep learning, especially deep reinforcement learning, to automatically learn effective solvers for CO. The resultant new paradigm is termed neural combinatorial optimization (NCO). However, the advantages and disadvantages of NCO relative to other approaches have not been empirically or theoretically well studied. This work presents a comprehensive comparative study of NCO solvers and alternative solvers. Specifically, taking the traveling salesman problem as the testbed problem, the performance of the solvers is assessed in five aspects, i.e., effectiveness, efficiency, stability, scalability, and generalization ability. Our results show that the solvers learned by NCO approaches, in general, still fall short of traditional solvers in nearly all these aspects. A potential benefit of NCO solvers would be their superior time and energy efficiency for small-size problem instances when sufficient training instances are available. Hopefully, this work would help with a better understanding of the strengths and weaknesses of NCO and provide a comprehensive evaluation protocol for further benchmarking NCO approaches in comparison to other approaches.