Research Of Deep Neural Network Algorithms For Capacitated Arc Routing Problems

The capacitated arc routing problem(CARP)is a challenging combinatorial op-timization problem with complex formulation and constraints.It has extensive appli-cations in real world,such as municipal services,logistics transportation,urban waste collection,power line inspection,and automated guided vehicle path planning.Heuris-tic algorithms were commonly used to solve CARP in the research over the past decades.However,for a given CARP instance,most heuristic algorithms need to search itera-tively to find the solution from scratch,which is extremely time-consuming.Therefore,it is hard to apply existing heuristic algorithms to some problem scenarios that require real-time solutions.Inspired by research on deep learning that has developed rapidly in recent years,a novel paradigm for solving CARP is proposed in this thesis.The deep neural network model that treated as a solver is trained by a large number of problem instances.Then for each new instance to be solved,the solving process is considered as a rapid testing process of the neural solver.Compared with heuristic algorithms,the goal of the neural solver is to accelerate the solving process greatly with minor loss of quality of solutions.This thesis focuses on this goal and proposes the following two different methods.Firstly,this thesis proposes a neural solver that based on a sequence-to-sequence(seq2seq)model and trained by supervised learning.The problem instance and the corresponding solution given by a heuristic algorithm are treated as the input and the label of a training sample.By a graph embedding technique and a presorting,the input and the label of a sample are constructed as two sequences.Then,the solving of a CARP instance is equivalent to a sequence-to-sequence prediction process.The proposed method uses an encoder-decoder model trained by supervised learning as the neural solver to map the input sequence to the output sequence.Actually,the knowl-edge that the heuristic algorithm used for solving history instances is transferring into the neural solver by supervised learning,which guarantees the quality of solutions gen-erated by the neural solver to some extent.In view of the difficulty in collecting labeled data in some scenarios,this thesis proposes a neural solver that based on a set-to-sequence model and trained by reinforce-ment learning.Reinforce learning trains model by maximizing the cumulative rewards,which requires no labeled data.The proposed method introduces a graph convolutional network(GCN)and two endocer-decoder models to convert the solving of a CARP in-stance into a set-to-sequence prediction process.The entire model is parameterized as a solution generating policy.By regard the cost function values of solutions generated by conducting the policy as rewards and by optimizing parameters of the policy with REINFORCE algorithm,the neural solver can learn an effective solving method.Empirical results show the two proposed methods can achieve remarkable speedup while they are not significantly worse than the heuristic algorithm in terms of the quality of solutions.