A cutting plane algorithm for the General Routing Problem |
| |
| Authors: | Angel Corberáan Adam N Letchford José María Sanchis |
| |
| Institution: | (1) DEIO, Faculty of Mathematics, University of Valencia, Spain, ES;(2) Dept. of Management Science, Lancaster University, England, GB;(3) Dept. of Applied Mathematics, University Polytechnic of Valencia, Spain, ES |
| |
| 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.
Received: November 1998 / Accepted: September 2000?Published online March 22, 2001 |
| |
| Keywords: | : valid inequalities – cutting planes – General Routing Problem – Rural Postman Problem – Graphical Travelling Salesman Problem |
| 本文献已被 SpringerLink 等数据库收录！ |
|
