Reinforcement Learning With Multiple Relational Attention for Solving Vehicle Routing Problems.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Reinforcement learning (RL) models, particularly attention-based ones, show promise for vehicle routing problems (VRPs).
• Existing attention-based RL methods struggle with dynamic network structures, limiting their ability to model state transitions and action selection effectively.
• This limitation hinders performance in complex VRP scenarios.

Purpose of the Study:

• To develop an advanced attention-based RL model for VRPs that addresses the limitations of current approaches.
• To improve the modeling of dynamic network structures and enhance the effectiveness and efficiency of RL in solving VRPs.
• To evaluate the proposed model's performance across a diverse set of VRP benchmarks.

Main Methods:

• Developed a novel attention-based RL model incorporating batch normalization reordering and gate aggregation for enhanced node embeddings.
• Introduced a dynamic-aware context embedding mechanism using an attentive aggregation module on multiple relational structures.
• Experimented on five VRP variants: Traveling Salesman Problem (TSP), Capacitated VRP (CVRP), Split Delivery VRP (SDVRP), Orienteering Problem (OP), and Prize Collecting TSP (PCTSP).

Main Results:

• The proposed model significantly outperforms existing learning-based baselines in VRP solutions.
• The model demonstrates substantially faster problem-solving times compared to traditional VRP algorithms.
• Achieved improved generalizability on large-scale problems and datasets with varying data distributions.

Conclusions:

• The novel attention-based RL model offers superior performance and efficiency for various VRPs.
• The model's ability to capture dynamic network structures leads to enhanced generalizability.
• This research advances the application of RL in solving complex combinatorial optimization problems like VRPs.