A cutting plane method for the windy postman problem

In this paper the authors describe a cutting plane algorithm for the (NP-hard) windy postman problem. This algorithm can also be applied to the mixed, directed, and undirected postman problems. It is based on a partial linear description of the windy postman polyhedron and on the simplex method. The partial linear description (together with cutting plane recognition strategies) provides new cutting planes and hence generates better and better linear programming relaxations of the windy postman polyhedron, and the simplex method solves these linear programs. The authors have investigated the performance of the present algorithm with several test problems defined on graphs of up to 264 nodes. For most of these problems, they obtained optimal solutions in reasonable computation times.