A cutting plane algorithm for the general routing problem

A cutting plane algorithm for the general routing problem

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: travelling salesman
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.

Reviews

Required fields are marked *. Your email address will not be published.