×

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.

MSC:

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