An Improved Decomposition-Based Memetic Algorithm for Multi-Objective Capacitated Arc Routing Problem

摘要

Capacitated Arc Routing Problem (CARP) has attracted the attention of many researchers during the last few years, because it has a wide application in the real world. Recently, a Decomposition-Based Memetic Algorithm for Multi-Objective CARP (D-MAENS) has been demonstrated to be a competitive approach. However, the replacement mechanism and the assignment mechanism of the offspring in DMAENS remain to be improved. First, the replacement after all the offspring are generated decreases the convergence speed of D-MAENS. Second, the representatives of these sub-problems are reassigned at each generation by only considering one objective function. In response to these issues, this paper presents an improved D-MAENS for Multi-Objective CARP (ID-MAENS). The two improvements of the proposed algorithm are as follows: (1) the replacement of the solutions is immediately done once an offspring is generated, which references to the steady-state evolutionary algorithm. The new offspring will accelerate the convergence speed; (2) elitism is implemented by using an archive to maintain the current best solution in its decomposition direction during the search, and these elite solutions can provide helpful information for solving their neighbor sub-problems by cooperation. Compared with the Multi-Objective CARP algorithm, experimental results on large-scale benchmark instances egl show that the proposed algorithm has performed significantly better than D-MAENS on 23 out of the total 24 instances. Moreover, ID-MAENS find all the best nondominated solutions on 13 egl instances. In the last section of this paper, the ID-MAENS also proves to be competitive to some state-of-art single-objective CARP algorithms in terms of quality of solutions and computational efficiency.