Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems.

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• The Covering Salesman Problem (CSP) is a complex combinatorial optimization challenge.
• Existing heuristic and deep learning methods face limitations in speed, scalability, or optimality.

Purpose of the Study:

• To introduce a new deep learning approach for approximately solving the CSP.
• To develop a model that directly outputs CSP solutions from city location data.
• To achieve faster computation times and maintain high solution quality.

Main Methods:

• A deep neural network model trained using unsupervised deep reinforcement learning.
• Integration of multihead attention (MHA) for capturing structural patterns.
• Implementation of dynamic embeddings to address problem dynamics.

Main Results:

• The model demonstrates over 20x speed improvement compared to traditional heuristic solvers with minimal optimality loss.
• Achieves superior performance in both training and inference over state-of-the-art deep learning methods.
• Exhibits generalization capabilities across various CSP instances without retraining.

Conclusions:

• The proposed deep learning approach offers a highly efficient and scalable solution for the CSP.
• This method is particularly valuable for large-scale, time-sensitive practical applications.
• It represents a significant advancement in applying deep learning to combinatorial optimization problems.