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.