Learning-Aided Neighborhood Search for Vehicle Routing Problems.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• The Vehicle Routing Problem (VRP) is a critical optimization challenge with widespread practical applications.
• Neighborhood search is a proven technique for VRP, but traditional methods suffer from inefficient, pre-determined neighborhood exploration.
• Existing learning-guided approaches often lack optimal strategy selection mechanisms.

Purpose of the Study:

• To develop an efficient and adaptive neighborhood search algorithm for the Vehicle Routing Problem.
• To introduce a novel multi-agent reinforcement learning framework for dynamic operator/neighborhood selection.
• To enhance the learning capability of agents through an informative, image-like state representation.

Main Methods:

• Proposed the Learning-aided Neighborhood Search (LaNS) algorithm, integrating multi-agent reinforcement learning.
• Implemented a collaborative guidance mechanism where two high-level agents select low-level heuristics.
• Developed a novel state representation converting route structures into image-like tensors for convolutional neural network analysis.

Main Results:

• LaNS demonstrated superior performance compared to state-of-the-art neighborhood search methods.
• The algorithm outperformed existing learning-guided neighborhood search techniques on diverse VRP benchmarks.
• Evaluations included capacitated VRP (CVRP), multi-depot VRP (MDVRP), and energy-constrained VRP variants.

Conclusions:

• LaNS offers a more efficient and effective approach to solving the Vehicle Routing Problem.
• The adaptive operator selection driven by multi-agent reinforcement learning significantly improves routing solutions.
• The novel state representation and learning framework provide a robust foundation for future VRP research.