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

• ID-MAENS is proposed in this paper.
• The replacement accelerates the convergence speed.
• The implemented elitism maintains the diversity of the solutions.
• The experimental results show the effectiveness of the proposed algorithm.

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 D-MAENS 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.

The original Multi-Objective Capacitated Arc Routing Problem is firstly decomposed into N scalar sub-problems with a set of uniformly distributed weight vectors λ1, …, λN. Each region represents one sub-population, and individuals are classified into different sub-populations according to their own direction vectors. When solving each problem respectively, two improvements of the new algorithm are as follows: (1) the replacement of the solutions is immediately done once an offspring solution is generated so as to accelerate the convergence; (2) elitism is implemented by using an archive to maintain the optimal solution in its decomposition direction during the search and these elite solutions can provide helpful information for solving their neighbor sub-problems by cooperation.Figure optionsDownload as PowerPoint slide