A multi-start local search matheuristic for the capacitated arc routing problem with irregular services

This paper investigates the periodic capacitated arc routing problem with irregular services, a challenging combinatorial optimization problem that arises in various real-world scenarios, such as waste collection and road maintenance. This problem is defined over a mixed graph and asks for scheduling a fleet of capacitated vehicles to meet the demands associated with a set of required links, while minimizing the routing costs over a given planning horizon. Each required link has its own service plan, indicating the frequency with which its demand must be met over the planning horizon. To solve this problem, we propose a novel matheuristic approach that combines a route-based mathematical formulation with a multi-start local search framework. The matheuristic incorporates two distinct local search strategies, which are crucial for improving solution quality, as revealed by the computational experiments. Additional experiments further confirm the effectiveness of the proposed matheuristic, comparing its performance against an exact method and a heuristic algorithm from the literature, solving the uncapacitated version of the problem. Finally, we analyze the impact of introducing the capacity constraint by comparing the solutions obtained in the two cases.