New Results on the Mixed General Routing Problem

Angel Corberán (), Gustavo Mejía () and José M. Sanchis ()
Additional contact information
Angel Corberán: Departament d’Estadística i Investigació Operativa, Universitat de València, València, Spain
Gustavo Mejía: Departamento de Ciencias Básicas, Universidad EAFIT, Medellín, Colombia
José M. Sanchis: Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, Valencia, Spain

Operations Research, 2005, vol. 53, issue 2, 363-376

Abstract: 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.

Keywords: polyhedral combinatorics; rural postman problem; general routing problem; mixed rural postman problem (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0168 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:2:p:363-376

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().