Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey With...

Area of Science:

• Operations Research
• Artificial Intelligence
• Machine Learning

Background:

• Existing surveys on neural combinatorial optimization (NCO) solvers for vehicle routing problems (VRPs) lack coverage of recent state-of-the-art (SOTA) advancements.
• A comprehensive and up-to-date classification of NCO solvers is needed to understand the field's progress.

Purpose of the Study:

• To systematically review and categorize NCO solvers for VRPs.
• To identify and discuss the inadequacies of current SOTA NCO solvers.
• To propose future research directions for advancing NCO in VRPs.

Main Methods:

• Systematic literature review and classification of NCO solvers into four types: learning to construct (L2C), learning to improve (L2I), learning to predict-once (L2P-once), and learning to predict-multiplicity (L2P-M).
• Analysis of SOTA solver limitations, including generalization, scalability, variant handling, and comparison with operations research (OR) algorithms.
• Comparative performance analysis of NCO solvers across different learning paradigms (reinforcement, supervised, unsupervised) and VRP scales.

Main Results:

• The study categorizes NCO solvers into L2C, L2I, L2P-once, and L2P-M types.
• Identified key inadequacies of SOTA solvers: poor generalization, inability to solve large-scale VRPs, limited handling of VRP variants, and challenges in comparing with OR methods.
• Performance comparison revealed varying effectiveness of different learning paradigms across VRP scales.

Conclusions:

• Current NCO solver research often addresses only one or two limitations, with no unified approach tackling all concurrently.
• A proposed taxonomy and live repository aim to foster advancements in the NCO community.
• Further research is needed to overcome identified inadequacies and enable broader application of NCO for VRPs.