The capacitated arc routing problem with intermediate facilities

This article introduces the Capacitated Are Routing with Intermediate Facilities (CARPIF), a variant of the classical Capacitated Are Roofing 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. (C) 2001 John Wiley & Sons, Inc.