Arc Routing

Computers & Operations Research 30 (2003) 705 – 728

www.elsevier.com/locate/dsw

A cutting plane algorithm for the capacitated arc routing problem

Josà M. Belenguer, Enrique Benavent ∗ e

Departamento de EstadÃstica e Investigacià n Operativa, Universitat de Val ncia, Dr. Moliner 50, 46100 Burjassot, o e Valencia, Spain Received 1 October 2000; received in revised form 1 November 2001

Abstract The Capacitated Arc Routing Problem (CARP) consists of ÿnding a set of minimum cost routes that service all the positive-demand edges of a given graph, subject to capacity restrictions. In this paper, we introduce some new valid inequalities for the CARP. We have designed and implemented a cutting plane algorithm for this problem based on these new inequalities and some other which were already known. Several identiÿcation algorithms have been developed for all these valid inequalities. This cutting plane algorithm has been applied to three sets of instances taken from the literature as well as to a new set of instances with real data, and the resulting lower bound was optimal in 47 out of the 87 instances tested. Furthermore, for all the instances tested, our algorithm outperformed all the existing lower bounding procedures for the CARP. Scope and Purpose In this paper, we present new developments in the Capacitated Arc Routing Problem (CARP), which has many real-world applications. Examples include the routing of refuse collection vehicles, street sweepers, snow removal vehicles and many others. Due to the complexity of the CARP, it cannot be solved optimally except for very small size instances and a number of heuristic procedures have been proposed to solve the CARP approximately. Unfortunately, it is di cult to estimate the quality of a given heuristic solution for a CARP instance unless we know a tight lower bound on its optimal cost. In this paper, we develop a cutting plane algorithm to compute a lower bound for the CARP that outperforms all the existing lower...