The capacitated arc routing problem with intermediate facilities

This article introduces the Capacitated Arc Routing with Intermediate Facilities (CARPIF), a variant of the classical Capacitated Arc Routing Problem (CARP) in which the vehicle may unload or replenish at intermediate facilities. Two lower bounds are developed for the CARPIF: The first is based on the Rural Postman Problem (RPP) and the second one uses a relaxation of an integer linear formulation of the problem. Two upper bounds are also developed, based on the solution of an RPP and of a CARP. Computational results on a set of benchmark instances confirm the quality of the proposed bounds.