This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Corberán, A. Articles by Sanchis, J. M. Search for Related Content

New Results on the Mixed General Routing Problem

Departament d’Estadística i Investigació Operativa, Universitat de València, València, Spain
Departamento de Ciencias Básicas, Universidad EAFIT, Medellín, Colombia
Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, Valencia, Spain
angel.corberan{at}uv.es
gmejia{at}sigma.eafit.edu.co
jmsanchis{at}mat.upv.es

In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. Extensive computational experiments over different sets of instances are included.

Subject classifications: polyhedral combinatorics; rural postman problem; general routing problem; mixed rural postman problem.
History: Received May 2002; revision received November 2003; accepted November 2003.