A genetic algorithm for a bi-objective capacitated arc routing problem

The capacitated arc routing problem (CARP) is a very hard vehicle routing problem for which the objective—in its classical form—is the minimization of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip.In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated sorted genetic algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files.Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.