Genetic local search algorithm for a new bi-objective arc routing problem with profit collection and dispersion of vehicles

We present a new bi-objective arc routing problem in which routes must be constructed in order to maximize collected profit and a non linear dispersion metric. A dispersion metric calculated based on instantaneous positions, suitable to capture routing characteristics found when vehicles have to travel in hostile environments, is a novelty in the routing literature. The inherent combinatorial nature of this problem makes it difficult to solve using exact methods. We propose a Multi-objective Genetic Local Search Algorithm to solve the problem and compare the results with those obtained by a well known multi-objective evolutionary algorithm. Computational experiments were performed on a new set of benchmark instances, and the results evidence that local search plays an important role in providing good approximation sets. The proposed method can be adapted to other multi-objective problems in which the exploitation provided by local search may improve the evolutionary procedures usually adopted.