Learning Feature Embedding Refiner for Solving Vehicle Routing Problems.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Encoder-decoder models are common for Vehicle Routing Problems (VRPs) but struggle with solution search due to deterministic embeddings and distributions.
• Existing deep learning methods for VRPs lack flexibility and struggle to explore diverse solutions effectively.

Purpose of the Study:

• To introduce a novel Feature Embedding Refiner (FER) to enhance existing encoder-decoder deep models for VRPs.
• To improve the search capabilities of neural construction methods by refining feature embeddings and probability distributions.

Main Methods:

• Proposed a generic encoder-refiner-decoder structure, where the refiner network combines Gated Recurrent Units (GRU) with Accumulated Graph Attention (AGA) and Gated Nonlinear (GNL) layers.
• The AGA layer extracts topological information from historical solutions, while the GNL layer refines encoder embeddings using pool embeddings.
• Applied FER to Attention Model (AM) and Policy Optimization with Multiple Optima (POMO) for Traveling Salesman Problem (TSP) and Capacitated VRP (CVRP).

Main Results:

• FER enables iterative refinement of feature embeddings for a broader search range and dynamic updates of probability distributions for more diverse exploration.
• Experiments demonstrated that FER-enhanced methods achieved lower gaps and better generalization compared to original models.
• FER-based approaches showed competitive performance against state-of-the-art neural improvement methods for TSP and CVRP.

Conclusions:

• The proposed FER significantly boosts the performance of existing neural construction methods for VRPs by enhancing solution search.
• FER offers a model-agnostic approach, improving both the search range and diversity of solutions for complex routing problems.
• This method provides a valuable advancement for deep learning applications in combinatorial optimization problems like VRP and TSP.