12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

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

« Back

A cutting plane algorithm for the general routing problem

Research output: Contribution to journalJournal article

Published

Journal publication date2001
JournalMathematical Programming
Journal number2
Volume90
Number of pages26
Pages291-316
Original languageEnglish

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