Learning Improvement Heuristics for Solving Routing Problems.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Current deep learning (DL) methods for routing problems often rely on construction heuristics, yielding suboptimal solutions.
• Improvement heuristics offer a promising avenue for enhancing solution quality through iterative refinement.
• Traditional improvement heuristics are limited by handcrafted rules, hindering their performance potential.

Purpose of the Study:

• To develop a deep reinforcement learning (DRL) framework for learning effective improvement heuristics for routing problems.
• To address the limitations of handcrafted rules in traditional improvement heuristics.
• To enhance the performance of DL-based solutions for routing problems.

Main Methods:

• A DRL framework was proposed, utilizing a self-attention-based deep architecture as a policy network.
• The policy network guides the selection of solutions for iterative refinement.
• The framework was applied to the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).

Main Results:

• The proposed DRL method demonstrated superior performance compared to state-of-the-art DL-based approaches.
• Learned policies proved more effective than traditional handcrafted heuristics.
• The method showed good generalization across different problem sizes, initial solutions, and real-world datasets.
• Performance was further improved by incorporating simple diversifying strategies.

Conclusions:

• The DRL framework successfully learns effective improvement heuristics for routing problems.
• This approach overcomes the limitations of handcrafted rules and advances DL applications in combinatorial optimization.
• The learned policies offer a more robust and adaptable solution for TSP and CVRP, with potential for broader applications.