Solving various classes of arc routing problems with a memetic algorithm-based framework

Full abstract

Read the full abstract

Arc routeing problems are combinatorial optimisation problems with many real-world applications, such as mail delivery, snow ploughing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. We develop a unified memetic algorithmic framework that integrates genetic operators, a dynamic-programming-based route splitting procedure, and problem-specific local search methods in a modular and reusable way. Unlike existing memetic algorithms designed for individual problem variants, our approach formalises the interaction among these components so that the same structure can be adapted to different classes of arc routeing problems—directed, undirected, or windy, with objectives ranging from cost minimisation to profit maximisation. This general formulation establishes a systematic foundation for designing problem-specific heuristics while maintaining consistency across ARP families. The framework is applicable to single- or at-most-once-service problems but not multi-service or close-enough variants. We select two problems to test the effectiveness of our proposed framework: the Min–Max k-Vehicle Windy Rural Postman Problem (MM K–WRPP) and the Undirected Capacitated Arc Routeing Problem with Profits (UCARPP). We implement our framework and compare it with existing algorithms using an established benchmark set for each problem. We demonstrate that our proposed framework can outperform custom-built algorithms.