On Deep Reinforcement Learning Algorithms For Solving Routing Problems

The solution methods for combinatorial optimization problem have permeated to the fields of artificial intelligence,operations research,etc.With the scale of data increasing and the speed of problem updating being faster,the traditional method of solving combinatorial optimization problem is challenged in computational speed,precision and generalization ability.In recent years,deep reinforcement learning has been widely used in driverless,industrial automation,game intelligence and other fields,showing strong decision-making and learning ability.Thus,many researchers have strived to use deep reinforcement learning to solve combinatorial optimization problem,which provides a novel method for solving NP-hard problems.In view of this,from the perspective of deep reinforcement learning,this dissertation conducts the following studies on two classic NP-hard problems – traveling salesman problem and capacitated vehicle routing problem:Aiming at the problems of incomplete information expression and poor generalization ability of the existing learning models in solving the travel salesman problem,we apply graph neural network aggregate operation processing to transformer decoding stage for the first time,which effectively capture the topological structure of the graph and the potential relationships between points.Specifically,the behavioral network parameters are trained by an improved REINFORCE algorithm to effectively reduce the variance,prevent local optima,avoided premature convergence and loss of global optimizations.Positional Encoding is used to the encoding structure to make the multiple node satisfy translation invariance during the embedding process and enhance the stability of the model.The experimental results show that the optimization effect of the model on the 100-TSP problem surpasses the current DRL-based methods and some traditional algorithms.Traditional positional encoding method is not suitable for extracting location information for dynamic optimization problems,the state of an instance is changed according to the model at different construction steps,and the node features should be updated correspondingly.With the goal of minimizing the routing length,a dynamic graph transformer model and a dynamic positional encoding method are creatively proposed,and a double-loss REINFORCE algorithm is novelly used to train the dynamic graph transformer model.In addition,the combination of reinforcement learning,graph neural network and Transformer architecture improve the training efficiency of the model.And it enhances the information representation of the neural network for routing problems with constraints.The experimental results show that the optimization of the model on this problem surpasses current deep reinforcement learning methods and some traditional algorithms.The overall performance of the dynamic graph transformer model is better than that of the professional solver and has good generalization performance,which provides an effective method for solving combinatorial optimization problems on graphs.