Study On Multi-Vehicle Capacitated Arc Routing Problem (MVCARP)

For the wide applications of the Capacity Arc Routing Problem (CARP) in our daily lives, to resolve these problems successfully brings us the significant effects not only in the aspect of economic saving, but also in the work efficiency improvement. In the past years, the CARP inspired many researchers all around the world to focus on it. Although many great progresses have been made by their strenuous work, compared with the VRP with which we are very familiar, for a whole, we are now still struggling to improve the efficiency of the algorithms'performances. By the scrutiny of all the papers which are published, we believe that there are still some relative progresses we can achieve. Furthermore, as one of the sub-problems of the CARP, the Multi-type Vehicles CARP is just researched initially. The author hasn't found the mature methods to resolve it. Thus, as the fundamental research in the CARP and MV-CARP, this paper studies deeply in this area, and points out an effect solving to the CARP and the MV-CARP which as an extended problem of CARP.For the common sense, the CARP can be classified into the NP hard problem, which means that it is too hard for the precise algorithms to get the perfect results. Therefore, the heuristic methods are the better tools to resolve it. For the Genetic Algorithm (GA), there are many advantages that we use it to resolve the CARP, not only it has the global astringency, but also owns the perfect performance in the combination optimizing problems. The main contributions of this paper are follows:First, it provides the mathematics models of the MV-CARP based on the researches and the analysis of the traditional CARP.Second, with the careful study of the Memetic Algorithm (MA), which is one of the most popular methods to solve the CARP, and some other main algorithms'complexities and the efficiencies, this paper checks out the flaws of those algorisms to illustrate the main reasons why they can't successfully resolve the CARP.Third, with the combination of the Traditional GA (TGA) and the Parthenogenesis GA (PGA), after the conceiving of the population structures and the redesign of the evolutionary algorithms, this paper provides a new high performance GA, especially in the high speed of the calculation. Furthermore, the new GA can resolve both MV-CARP and the Traditional CARP.Fourth, by doing the research of CARP, this paper provides four different kinds of test data, and all of them are in different scales. Our research is based on these test data. All the algorithms are tested on these data, through which it is clearly to decide the level of the performance of the algorithms. At last, this paper also uses the data, which are provided by other papers and widely used in recent years, to test the algorithms. Furthermore, this paper also does the comparative test contrasting to the Memetic Algorithm based on the same test data. In this way, it is easy to validate the high effective algorithm of this paper.The main purpose of this paper is to resolve the MV-CARP, to which we are commonly facing in our real lives. Aiming at the providing of one more all-purpose and effective algorithm, this paper's contribution is to construct the algorithm based on the GA method to solve the CARP. It modifies some of the faults of other algorithms which cause many obstacles on the perfect performance.