Deep reinforcement learning algorithm based on multi-start and Mask strategy for solving the covering salesman problem
The covering salesman problem(CSP)is a variant of the traveling salesman problem,which is widely used in disaster planning and emergency management.Since the traditional solvers are time-consuming for solving problem instances,deep neural networks have been proposed for solving this type of combinatorial optimization problem in recent years,which have obvious advantages in terms of solving speed and generalization.However,existing methods based on deep neural networks for solving CSP problems have low solution quality,especially in large-scale instances,compared with traditional heuristics.Therefore,we propose a new method based on deep reinforcement learning to solve the CSP problem,in which the encoder encodes the input features,propose a new Mask strategy to constrain the decoder to construct a solution using the self-attention mechanism,and propose a multi-start strategy to improve the training process and the solution quality.Experimental results show that the proposed method further reduces the optimality gap compared with existing deep neural network-based solution methods,has higher sample efficiency,shows stronger generalization ability in CSP tasks of different sizes and coverage types,and has a 10-40 times improvement in solution speed compared with heuristic algorithms.
NETL
NSTL
万方数据
