A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence

In the capacitated arc routing problem (CARP), a fleet of capacitated vehicles based at a depot must cover the streets of a network where the demand is located at the lowest possible total cost. Waste collection, street sweeping, winter gritting, and mail delivery are among its best-known applications. This work introduces the CARP with vehicle dependence (CARP-VD), an extension in which the cost of servicing an edge, and that of traversing it without service, are specific to each vehicle type and formulates it as a mixed-integer linear program. A two-stage matheuristic is proposed: the first stage distributes the required edges among the vehicles without exceeding their capacities, and the second builds the route of each vehicle. A bound is derived that limits the optimality loss of this decomposition by its own deadheading cost. Both approaches are evaluated on 47 benchmark instances adapted from the literature under a common one-hour budget, and their robustness is assessed over six scenarios that vary the parameters of the adaptation. The matheuristic returns good-quality solutions in a fraction of the time on the smaller instances, and on those in which almost every edge requires service it improves the best solutions found by a commercial solver applied to the complete model by up to 44%.