Article ID: | iaor2002924 |
Country: | Germany |
Volume: | 90 |
Issue: | 2 |
Start Page Number: | 291 |
End Page Number: | 316 |
Publication Date: | Jan 2001 |
Journal: | Mathematical Programming |
Authors: | Corbern A., Sanchis J.M., Letchford A.N. |
Keywords: | programming: travelling salesman |
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 visits certain vertices and edges of a network. It contains the Rural Postman Problem, 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 strong lower bounds and, in most cases, optimal solutions.