Abstract
The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics. © 2006 IEEE.
Original language | English |
---|---|
Article number | 5352249 |
Pages (from-to) | 356-374 |
Number of pages | 19 |
Journal | IEEE Transactions on Evolutionary Computation |
Volume | 14 |
Issue number | 3 |
Early online date | 11 Dec 2009 |
DOIs | |
Publication status | Published - Jun 2010 |
Externally published | Yes |
Keywords
- Capacitated arc routing problem
- Combinatorial optimization
- Evolutionary algorithms
- Time-limited service