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.

► A new and complex open capacitated arc routing problem is introduced and studied.
► A mathematical formulation and a lower bound are established for the OCARP.
► An effective memetic algorithm (MA) is developed for solving the OCARP.
► Computational results show that MA performs well for random and benchmark instances.