Home > Research > Publications & Outputs > A cutting plane algorithm for the general routi...
View graph of relations

A cutting plane algorithm for the general routing problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>2001
<mark>Journal</mark>Mathematical Programming
Issue number2
Number of pages26
Pages (from-to)291-316
Publication StatusPublished
<mark>Original language</mark>English


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.