Genetic Algorithms For Solving The Arc Routing Problem

Derived from the transportation service system in real life, arc routing problem have found its application in many fields, and is now becoming the focus of many relevant studies. Since it is a NP-hard problem, the time exact algotithm needs in solving it usually increases exponentially. Thus it is incapable of dealing with massive problems. In comparison with exact algotithm, the heuristic algorithm may takes less time, however, it is also deficient in terms of the efficiency and quality of the solution. With the development of Genetic Algorithms, it has already been applied to the solution of such a problem. Genetic Algorithms turned out to be an effective strategy with full consideration to both the efficiency of computation and the quality of solution. And there would be great prospect for Genetic Algorithms in giving solutions to arc routing problem.Based on extensive and thorough reading of the literature both at home and abroad, this thesis makes an in-depth theoretical study on the fundamental theories and methods of Genetic Algorithms and does an experimental analysis of the application of Genetic Algorithms in solving arc routing problem. The gist is as follows:1. A systematic and detailed introduction of the general procedure, fundamental theories and methods of Genetic Algorithms.2. A brief introduction of the origin and history of evolution of arc routing problem. A summarization of the solution of this problem will also be presented. Aiming at lowering the cost of car service, the thesis will then put forward a new Genetic Algorithms to tackle arc routing problem. The new algorithm not only adopted the improved local search technique, but made some adjustments to some other sections of the current algorithm. Finally, the computation of many examples will prove the effectiveness of this algorithm in solving most of the relevant problems...