A memetic algorithm for the open capacitated arc routing problem

In this paper, an open capacitated arc routing problem (OCARP) is defined and considered. The OCARP seeks to find a set of minimum-cost open routes that can serve the tasks (i.e., required arcs) of a given graph, subject to the vehicle capacity and travel distance. A mathematical programming formulation and a lower bound are established. An effective memetic algorithm is developed for solving the OCARP. Computational experiments demonstrate that the proposed algorithm can produce high quality solutions within a reasonable computational time span, and the proposed memetic algorithm is superior to the classical genetic algorithm in solution quality.