Abstract
Capacitated Arc Routing Problem (CARP) has drawn much attention during the last few years. In addition to the goal of minimizing the total cost of all the routes, many real-world applications of CARP also need to balance these routes. The Multi-objective CARP (MO-CARP) commonly exists in practical applications. In order to solve MO-CARP efficiently and accurately, this paper presents a Multi-population Cooperative Coevolutionary Algorithm (MPCCA) for MO-CARP. Firstly, MPCCA applies the divide-and-conquer method to decompose the whole population into multiple subpopulations according to their different direction vectors. These subpopulations evolve separately in each generation and the adjacent subpopulations can share their individuals in the form of cooperative subpopulations. Secondly, multiple subpopulations are used to search different objective subregions simultaneously, so individuals in each subpopulation have a different fitness function, which can be modeled as a Single Objective CARP (SO-CARP). The advanced MAENS approach for single-objective CARP can be used to search each objective subregion. Thirdly, the internal elitism archive is used to construct evolutionary pool for each subregion, which greatly speeds up the convergence. Lastly, the fast nondominated ranking and crowding distance of NSGA-II are used for selecting the offspring and keeping the diversity. MPCCA is tested on 91 CARP benchmarks. The experimental results show that MPCCA obtains better generalization performance over the compared algorithms.
Original language | English |
---|---|
Pages (from-to) | 609-642 |
Number of pages | 34 |
Journal | Information Sciences |
Volume | 277 |
DOIs | |
Publication status | Published - 1 Sept 2014 |
Bibliographical note
Funding Information:We would like to express our sincere appreciation to the anonymous reviewers for their insightful and valuable comments, which have greatly helped us in improving the quality of the paper. This work was partially supported by the National Basic Research Program (973 Program) of China , under Grant 2013CB329402 , the National Natural Science Foundation of China , under Grants 61371201 , 61001202 , 61203303 and 61272279 , the Fundamental Research Funds for the Central Universities , under Grant K5051302028 , the Fund for Foreign Scholars in University Research and Teaching Programs (the 111 Project) under Grant B07048 , and the Program for Cheung Kong Scholars and Innovative Research Team in University under Grant IRT1170 .
Keywords
- Capacitated arc routing problem
- Coevolution
- Evolutionary algorithm
- Multi-objective optimization
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence