The capacitated arc routing problem with intermediate facilities

This article introduces the Capacitated Are Routing with Intermediate Facil ities (CARPIF), a variant of the classical Capacitated Are Roofing Problem (CARP) in which the vehicle may unload or replenish at intermediate facilit ies. Two lower bounds are developed for the CARPIF: The first is based on t he Rural Postman Problem (RPP) and the second one uses a relaxation of an i nteger linear formulation of the problem. Two upper bounds are also develop ed, 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.