A cutting plane algorithm for the General Routing Problem

Citation
A. Corberan et al., A cutting plane algorithm for the General Routing Problem, MATH PROGR, 90(2), 2001, pp. 291-316
Citations number
29
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
2
Year of publication
2001
Pages
291 - 316
Database
ISI
SICI code
0025-5610(200104)90:2<291:ACPAFT>2.0.ZU;2-4
Abstract
The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visit s certain vertices and edges of a network. It contains the Rural Postman Pr oblem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very s trong lower bounds and, in most cases, optimal solutions.