Rural postman problem data

This page contains data for the rural postman problem. The problem and data is described in the following article. An instance is simply a list of edges with a cost and a "required-flag" for each edge.

Any use of these problem data should be accompanied with a reference to the article above. You might also want to send me an email.

Instances in subdirectory "datagrid" are grid instances, generated by myself, reflecting a city-like structure. (I used Vineopt when making them.)
Instances in subdirectory "data-ac" were obtained from Ghiani, Lagana, Musmanno.
Instances in subdirectory "datagrplib" were obtained from the collection at, collected by Dirk Oliver Theis.
I have removed instances that were, from the rural postman perspective, uninteresting. I have also removed all data except the above mentioned edge list with costs and required-flags.
More information about the instances can be found in my article above, and at Theis' page (which however seems to be moved to

I made these versions only in order to simplify for my own code. However, there seems to be some demand for them, which is why I made them available here. If you use them, please make all the appropriate citations to the original authors.

By the way, if you are successful with the more difficult sets (groups 7, 8b and 9b) it would be interesting to hear about it.

Data format:

m n
For each edge: i j c r

In the file problems characteristics of each problem is given: Problem name, number of vertices, number of edges, number of required edges, number of connected parts (and the sum of all edge costs, which would be the cost of a Eularian tour, if there was one).

Download all problem data in a zip-file.

Kaj Holmberg, email:, homepage:
Division of Optimization, Department of Mathematics, Linköping Institute of Technology, SE-581 83 Linköping, SWEDEN.