A cutting plane algorithm for the General Routing Problem

[EN] 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.The authors would like to thank three anonymous referees for their helpful comments and suggestions that have greatly improved the contents and presentation of the paper. The contribution by A. Corberán & J.M. Sanchis has been partially supported by the Ministerio de Ciencia y Tecnología of Spain (Ref. TIC2000-1750-C06-01).Corberan, A.; Letchford, A.; Sanchís Llopis, JM. (2001). A cutting plane algorithm for the General Routing Problem. Mathematical Programming. 90(2):291-316. https://doi.org/10.1007/PL0001142629131690