On Crossings, the Crossing Postman Problem, and the Rural Postman Problem

The Rural Postman Problem (RPP), on an undirected network, is a classic edge-routing problem. The Crossing Postman Problem is a generalization which is introduced here. Results are presented on the structure of optimal solutions to both problems. A new formulation for RPP, based on these results, is given. © 1999 John Wiley & Sons, Inc. Networks 34: 173-180, 1999