  This paper introduces a new deep learning approach to approximately solve the
Covering Salesman Problem (CSP). In this approach, given the city locations of
a CSP as input, a deep neural network model is designed to directly output the
solution. It is trained using the deep reinforcement learning without
supervision. Specifically, in the model, we apply the Multi-head Attention to
capture the structural patterns, and design a dynamic embedding to handle the
dynamic patterns of the problem. Once the model is trained, it can generalize
to various types of CSP tasks (different sizes and topologies) with no need of
re-training. Through controlled experiments, the proposed approach shows
desirable time complexity: it runs more than 20 times faster than the
traditional heuristic solvers with a tiny gap of optimality. Moreover, it
significantly outperforms the current state-of-the-art deep learning approaches
for combinatorial optimization in the aspect of both training and inference. In
comparison with traditional solvers, this approach is highly desirable for most
of the challenging tasks in practice that are usually large-scale and require
quick decisions.
