Study On Periodic Capacitated Arc Routing Problem

Nowadays, Periodic Capacitated Arc Routing Problem (PCARP) is a quite common problem in the routing optimization system, and it has the powerful application background, urban waste collection is the most typical example. PCARP is the extension of Capacitated Arc Routing Problem (CARP). For saving economic cost and improving social production efficiency, it's very meaningful to effectively solve PCARP and push it to the actual application. In the past twenty years, the CARP had inspired many researchers all around the world to focus on it, the researchers also proposed many effective solutions, but as a whole, compared with the VRP with which we are very familiar, the research of CARP is not enough. According to some existing published literatures, the method of solving CARP has large improving space. For the common PCARP in application, there are few international researchers work on it, while at home, the research of this field is nearly in blank. So it has very large improving prospect to research on PCARP. Therefore, this paper deeply studies on the basic PCARP and the extended PCARP (EPCARP), meanwhile, proposes the algorithms of solving the two problems.According to referred literature, most of them almost adopt heuristics or linear programming algorithm to solve PCARP. Because Genetic Algorithm (GA) has good property of global astringency, and owns the perfect performance in the combination optimizing problems, this paper will mainly use GA as the tool to solve PCARP, moreover, in order to avoid the shortages of early convergence and easy falling in the local minimization in the traditional genetic algorithm when solving some problems, the author proposes the second Partheno-Genetic Algorithm (SPGA) and Improved Memetic Algorithm (IMA), and validates the performance of the algorithms proposed in this paper by some experiments. The main contributions of this paper to PCARP show as follows:Firstly, it provides the mathematic models of the PCARP based on the researches and the analysis of CARP.Secondly, this paper proposes a kind of second Partheno-Genetic Algorithm (SPGA) to solve the basic PCARP. For the particular property of PCARP, this algorithm adopts the chromosome coding and initialization methods which are proper for PCARP; As for the chromosome recombination, the author learns from the ideas of Partheno-Genetic Algorithm (PGA), and adds a recombination operator; at last, the second genetic idea based on elite population is applied to PGA, effectively avoiding the shortages of early convergence and easy falling in the local minimization in the traditional genetic algorithm when solving routing optimization problems.Thirdly, this paper also proposes a kind of Improved Memetic Algorithm (IMA) to solve the extended PCARP (EPCARP). For the complexity of EPCARP, the algorithm adopts the PLOX crossover operator which is proper for EPCARP; in order to improve the running efficiency of this algorithm, the course of Local Search in MA is simplified; meanwhile, in order to get the better optimal results, this paper improves the population initialization, selection operator and fitness function of MA.Fourthly, this paper supplies several testing data sets with different scales for PCARP, on which the basic PCARP and EPCARP is respectively tested using SPGA and IMA, and finally get relatively excellent effect.The main purpose of this paper is to solve the common PCARP in practice, it's very valuable to study and research on this problem, not only can realize the rationality of routing partition, but also can improve the scientific management level of relevant department.