Study On Multiple Depot Capacitated Arc Routing Problem

For the wide applications of the Capacitated Arc Routing Problem (CARP) in our daily life, to resolve this problem successfully brings us the significant effects not only in the aspect of economic saving, but also in the work efficiency improvement. But in the application of our real life, the standard CARP usually is extended, for instance, the Multiple Vehicle Capacitated Arc Routing Problem (MVCARP) and the Multiple Depot Capacitated Arc Routing Problem (MDCARP). There are many researchers studing about standard CARP and MVCARP, but few about MDCARP. For the common sense, the MDCARP 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 if we use it to resolve the MDCARP, not only it has the global astringency, but also owns the perfect performance in the combination optimizing problems. This paper proposes two methods respectively to resolve two different kinds of MDCARP: transferring to single depot MVCARP to solve the closed MDCARP and all depots optimizing together to solve the open MDCARP. Moreover, an effective resolution is also proposed to solve a special MDCARP (CLARPIF) in the paper.This paper studies on the MDCARP (including closed MDCARP and open MDCARP) with multiple vehicles and a special MDCARP (CLARPIF). The main contributions of this paper are as follows:Firstly, it comfirms the mathematical models of closed MDCARP and provides the mathematical models of the open MDCARP based on the researches and the analysis of the mathematical models of the standard CARP and the MVCARP.Secondly, for the closed MDCARP, it transfers the MDCARP into multiple single- depot MVCARP by means of the merging of arcs to depots, which will be resolved by an existing HEGA algorithm for the MVCARP. And in the process of solving the problem, adjusting the bound arcs with the simulated annealing method, so a HGAC algorithm is formed for the closed MDCARP.Thirdly, for the open MDCARP, it adopts the method of all depots optimizing together, and improves the population structure and local search strategy, furthermore, it adds the measures of ensuring the continuity of the vehicles'service, so as to compose a HGAO algorithm for the open MDCARP. Forthly, it provides four data sets with different size, on which the HGAC algorithm for the closed MDCARP and the HGAO algorithm for the open MDCARP are tested and get perfect effects.At last, it studies a special MDCARP (CLARPIF), and designs a HGAIF algorithm for solving the CLARPIF based on the existing HEGA. Furthermore, this paper does the comparative testing with the existing algorithm such as VNS algorithm on the international standard testing data sets in common use to validate the effect of the HGAIF algorithm.The main purpose of this paper is to resolve the MDCARP, to which we are commonly facing in our real life. The MDCARP is based on the background of sprinklers routing optimization, also added the multiple vehicle and the complex traffic restrictive conditions, so it is of certain practical value. Moreover, for the special kind of MDCARP (CLARPIF), it is based on the background of refuse collection vehicles without real traffic conditions, so it has a little practical use.