Arc Routing Problems: Data Instances
This webpage is maintained by Ángel Corberán, Isaac Plana, and José María Sanchis. Last updated on January 24^{th} 2019.
In this webpage you can find data for different types of Arc Routing Problems defined on undirected, directed, mixed, and windy graphs.
The results for the Orienteering Arc Routing Problem instances have been obtained with the algorithm described in Archetti, Corberán, Plana, Sanchis, and Speranza (A branchandcut algorithm for the Orienteering Arc Routing Problem, Computers and Operations Research Vol. 66, pp. 95104, 2016).
The results for the Profitable Windy Rural Postman Problem have been obtained with the algorithm described in Ávila, Corberán, Plana and Sanchis (A branchandcut algorithm for the Profitable Windy Rural Postman Problem, European Journal of Operational Research, Vol. 249(3), pp. 10921101, 2016).
The results for the DistanceConstrained Generalized Directed Rural Postman Problem instances have been obtained with the algorithm described in Ávila, Corberán, Plana and Sanchis (Formulations and exact algorithms for the DistanceConstrained Generalized Directed Rural Postman Problem, EURO Journal on Computational Optimization, Vol. 5(3), pp. 339365, 2017) and the matheuristic proposed in
The results for the Generalized Directed Rural Postman Problem instances have been obtained with the algorithm described in Ávila, Corberán, Plana and Sanchis (A new branchandcut algorithm for the Generalized Directed Rural Postman Problem, Transportation Science, 50(2):750761, 2016).
The results for the Directed General Routing Problem and the Stacker Crane Problem instances have been obtained with the algorithm described in Ávila, Corberán, Plana and Sanchis (The Stacker Crane Problem and the Directed General Routing Problem, Networks, Vol. 65, pp. 4355, 2015).
The results for the Team Orienteering Arc Routing Problem instances have been obtained with the algorithm described in Archetti, Corberán, Plana, Sanchis, and Speranza (The Team Orienteering Arc Routing Problem, Transportation Science, Vol. 48, pp. 442457, 2014).
The results for the MinMax Kvehicles WRPP instances have been obtained with the algorithms described in Benavent, Corberán, Plana and Sanchis (MinMax Kvehicles Wind Rural Postman Problem, Networks, Vol. 54(4), pp. 216226, 2009 and New Facets and an enhanced BranchandCut for the MinMax Kvehicles Windy Rural Postman Problem, Networks, Vol. 58, pp. 255272, 2011), and in Benavent, Corberán, Desaulniers, Lessard, Plana, and Sanchis (A branchpriceandcut algorithm for the minmax kvehicle windy rural postman problem, Networks, Vol. 63, pp. 3445, 2014).
The results for the MBCPP instances have been obtained with the algorithm described in Corberán, Plana. RodríguezChía and Sanchis (A New Approach to the Maximum Benefit Chinese Postman Problem, Mathematical Programming, Vol. 141, pp. 2148, 2013).
The results for all the other instances have been obtained with the Branch & Cut algorithms described in Corberán, Plana and Sanchis (A Branch & Cut Algorithm for the Windy General Routing Problem and special cases, Networks 49, pp. 245257, 2007) and in Corberán, Oswald, Plana, Reinelt and Sanchis (New results on the Windy Postman Problem, Mathematical Programming, Vol. 132, pp. 309332, 2012).
The optimal values for the MCPP instance MB1055, and the MGRP instance GD427, as well as the bestknown solutions for the MGRP instance GD525, and the WGRP instances GB322, and GB422 were provided by Michael Drexl (On the generalized directed rural postman problem, JORS, Vol. 65, pp. 11431154, 2015).
The upper bounds for the MCPP instance MB3065, the MGRP instances GD422 and GD425, WRPP instances D322, D421, and D422, and the WGRP instances GB321, GB322, GB421, and GB622 were provided by Keld Helsgaun (Solving the equality generalized traveling salesman problem using the LinKernighanHelsgaun algorithm, Mathematical Programming Computation, Vol. 7, pp. 269287, 2015).
All the results are reported in the files linked in column Solutions values. The characteristics of the instances can be found in column Instance characteristics.
For more details about the instances, read the file readme file of the corresponding problem.
Problem 
Instances 
Instance characteristics 
Solution values 
Readme files 

Undirected Graphs 
Graphical TSP 

Rural Postman Problem (RPP) 

General Routing Problem (GRP) 

Maximum Benefit CPP (MBCPP) 

Directed Graphs 
Directed General Routing Problem (DGRP) 

Stacker Crane Problem (SCP) 

Generalized Directed RPP (GDRPP) 

DistanceConstrained GDRPP (DCGDRPP) 

Team Orienteering ARP (TOARP) 

Orienteering ARP (OARP) 

Mixed Graphs 
Mixed Postman Problem (MCPP) 

Mixed Rural Postman Problem (MRPP) 

Mixed General Routing Problem (MGRP) 

Hierarchichal Mixerd Rural Postman Problem (HMRPP) 



Windy Graphs 
Windy Postman Problem (WPP) 

Windy Rural Postman Problem (WRPP) 

Windy General Routing Problem (WGRP) 

MinMax Kvehicles Windy RPP 

Profitable Windy RPP (PWRPP) 