Solving Capacitated Arc Rqutinjg Problems With Immune Coevolutionary Theory

The Capacitated Arc Routing Problem (CARP) is a classical combinatorialoptimization problem. It has a wide application in the real world, such as: garbagecleaning, mail delivery, salting route optimization, sprinkling salt route optimizationand school bus scheduling. For the above reasons, CARP has drawn much attentionduring the last few years. Due to the presence of multiple constraints, the solutionspace of CARP consists of separated feasible regions. Since CARP is NP-hard, existingmethods are unable to find the global optimal solution in a polynomial time. The clonalselection algorithm and the coevolutionary algorithm are highly evolved, parallelevolutionary algorithms. The successes of immune and coevolutionary theory havebeen revealed on a wide variety of real-world problems, including numericaloptimization and combinational optimization. So in this thesis, we investigate CARPwithin the theory of immune and coevolutionary in order to obtain the near-optimalsolutions. The main contribution can be listed as follows:1) In existing metaheuristics for CARP, the offspring are often randomly selectedand a traversal local search is used to go through all the neighbors of the currentoffspring. This mechanism is beneficial to find new lower bound, while takingnumerous function evaluations. In order to solve dynamic CARP, there is a need tofurther enhance the efficiency of these algorithms. The motivation of this work is todevelop a high-efficiency algorithm which can solve CARP instances within a limitedcomputational budget. In this thesis, a novel algorithm for CARP—immune clonalselection algorithm for CARP (ICSA-CARP) is proposed. First, a robust constructiveheuristic is used to initialize the antibody population. The initial antibodies generatedby heuristic can accelerate the algorithm’s convergence. Second, we investigate CARPwithin the framework of immune clonal selection algorithm (ICSA), and ICSA canfocus on these high quality antibodies. By taking different strategies on different clonalantibodies of the same antibody, it not only promotes the cooperation and informationexchanging among antibodies but also increases the diversity and speeds up theconvergence. Third, two different antibody repair operations which make the infeasiblesolutions approach to the global optimal are introduced for repairing differentinfeasible solutions. The numerical experiments show that the result obtained by thenew algorithm is very competitive.2) Next, we focus on a more complicated extension of CARP calledmulti-objective CARP (MO-CARP). MO-CARP is a quite challenging problem since it has the difficulties caused by both multi-objective problems and combinatorialoptimization problems. In2012, a new Memetic Algorithm (MA) calledDecomposition-Based MA with Extended Neighborhood Search (D-MAENS) wasproposed by Yi Mei et al. D-MAENS adopts a decomposition-based framework whichis similar to that of MOEA/D, and D-MAENS adopts the MAENS approach forSO-CARP. Through following the advanced features of evolution strategy which isNSGA-II, D-MAENS shows a superior performance than other MO-CARP algorithms.However, the replacement mechanism and the assignment mechanism of the offspringin D-MAENS remain to be improved. In response to these issues, this thesis presentsan improved Decomposition-Based Memetic Algorithm for Multi-objectiveCapacitated Arc Routing Problem (ID-MAENS). ID-MAENS makes twoimprovements over the existing D-MAENS and the comparative tests demonstrate thesuperiority of the new algorithm.3) For the MO-CARP, we present a Multi-population Cooperative CoevolutionaryAlgorithm (MPCCA) for MO-CARP. Firstly, MPCCA applies the divide-and-conquermethod to decompose the whole population into multiple subpopulations according totheir different direction vectors. These subpopulations evolve separately in eachgeneration and the adjacent subpopulations can share their individuals in the form ofcooperative subpopulations. Secondly, individuals in each subpopulation have adifferent fitness function, which can be modeled as a SO-CARP and the advancedMAENS approach for single-objective CARP can be used to search each objectivesubregion. Thirdly, the internal elitism archive is used to construct evolutionary poolfor each subregion, which greatly speeds up the convergence. Lastly, the fastnondominated ranking and crowding distance of NSGA-II are used for selecting theoffspring and keeping the diversity. MPCCA is tested on91CARP benchmarks and theexperimental results show that MPCCA obtains better generalization performance overthe compared algorithms.This research is supported by the National Natural Science Foundation of China(No.61001202), the National Research Foundation for the Doctoral Program of HigherEducation of China (No.20100203120008) and the Fundamental Research Funds forthe Central Universities, under Grant K5051302028.