Tabu search heuristics for the arc routing problem with intermediate facilities under capacity and length restrictions. (English) Zbl 1058.90031

Summary: This paper deals with the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions (CLARPIF), a variant of the classical Capacitated Arc Routing Problem (CARP), in which vehicles may unload or replenish at intermediate facilities and the length of any route may not exceed a specified upper bound. Three heuristics are developed for the CLARPIF: the first is a constructive procedure based on a partitioning approach while the second and the third are tailored Tabu Search procedures. Computational results on a set of benchmark instances with up to 50 vertices and 92 required edges are presented and analyzed.


90B60 Marketing, advertising
90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
Full Text: DOI