Projects per year
Abstract
In this paper, a divide-and-conquer approach is proposed to solve the large-scale capacitated arc routing problem (LSCARP) more effectively. Instead of considering the problem as a whole, the proposed approach adopts the cooperative coevolution (CC) framework to decompose it into smaller ones and solve them separately. An effective decomposition scheme called the route distance grouping (RDG) is developed to decompose the problem. Its merit is twofold. First, it employs the route information of the best-so-far solution, so that the quality of the decomposition is upper bounded by that of the best-so-far solution. Thus, it can keep improving the decomposition by updating the best-so-far solution during the search. Second, it defines a distance between routes, based on which the potentially better decompositions can be identified. Therefore, RDG is able to obtain promising decompositions and focus the search on the promising regions of the vast solution space. Experimental studies verified the efficacy of RDG on the instances with a large number of tasks and tight capacity constraints, where it managed to obtain significantly better results than its counterpart without decomposition in a much shorter time. Furthermore, the best-known solutions of the EGL-G LSCARP instances are much improved.
Original language | English |
---|---|
Article number | 6595573 |
Pages (from-to) | 435-449 |
Number of pages | 15 |
Journal | IEEE Transactions on Evolutionary Computation |
Volume | 18 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2014 |
Keywords
- Capacitated are routing problem
- cooperative co-evolution
- memetic algorithm
- route distance grouping
- scalability
ASJC Scopus subject areas
- Software
- Computational Theory and Mathematics
- Theoretical Computer Science
Fingerprint
Dive into the research topics of 'Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis
Yao, X. (Principal Investigator)
Engineering & Physical Science Research Council
29/04/11 → 28/10/15
Project: Research Councils