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 branch-and-cut algorithm for the Orienteering Arc Routing Problem, Computers and Operations Research Vol. 66, pp. 95-104, 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 branch-and-cut algorithm for the Profitable Windy Rural Postman Problem, European Journal of Operational Research, Vol. 249(3), pp. 1092-1101, 2016).

The results for the Distance-Constrained 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 Distance-Constrained Generalized Directed Rural Postman Problem, EURO Journal on Computational Optimization, Vol. 5(3), pp. 339-365, 2017) and the matheuristic proposed in Corberán, Plana, Reula and Sanchis (A Matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem, Submitted to TOP, 2019). 

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 branch-and-cut algorithm for the Generalized Directed Rural Postman Problem, Transportation Science, 50(2):750-761, 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. 43-55, 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. 442-457, 2014).

The results for the Min-Max K-vehicles WRPP instances have been obtained with the algorithms described in Benavent, Corberán, Plana and Sanchis (Min-Max K-vehicles Wind Rural Postman Problem, Networks, Vol. 54(4), pp. 216-226, 2009 and New Facets and an enhanced Branch-and-Cut for the Min-Max K-vehicles Windy Rural Postman Problem, Networks, Vol. 58, pp. 255-272, 2011), and in Benavent, Corberán, Desaulniers, Lessard, Plana, and Sanchis (A branch-price-and-cut algorithm for the min-max k-vehicle windy rural postman problem, Networks, Vol. 63, pp. 34-45, 2014).

The results for the MBCPP instances have been obtained with the algorithm described in Corberán, Plana. Rodríguez-Chía and Sanchis (A New Approach to the Maximum Benefit Chinese Postman Problem, Mathematical Programming, Vol. 141, pp. 21-48, 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. 245-257, 2007) and in Corberán, Oswald, Plana, Reinelt and Sanchis (New results on the Windy Postman Problem, Mathematical Programming, Vol. 132, pp. 309-332, 2012).

The optimal values for the MCPP instance MB1055, and the MGRP instance GD427, as well as the best-known 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. 1143-1154, 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 Lin-Kernighan-Helsgaun algorithm, Mathematical Programming Computation, Vol. 7, pp. 269-287, 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	GTSP instances	GTSP char	GTSP solutions	readme
	Rural Postman Problem (RPP)	RPP instances	RPP char	RPP solutions	readme
	General Routing Problem (GRP)	GRP instances	GRP char	GRP solutions	readme
	Maximum Benefit CPP (MBCPP)	MBCPP instances	MBCPP char	MBCPP solutions	readme
Directed Graphs	Directed General Routing Problem (DGRP)	DGRP instances	DGRP char	DGRP solutions	readme_DGRP
	Stacker Crane Problem (SCP)	SCP instances	SCP char	SCP solutions	readme_SCP
	Generalized Directed RPP (GDRPP)	GDRPP instances	GDRPP char	GDRPP solutions	readme_GDRPP
	Distance-Constrained GDRPP (DC-GDRPP)	DCGDRPP instances	DCGDRPP char	DCGDRPP solutions	readme_GDRPP
	Team Orienteering ARP (TOARP)	TOARP_instances	TOARP_char	TOARP_solutions	readme_TOARP
	Orienteering ARP (OARP)	OARP_instances	OARP_char	OARP_solutions	readme_OARP
Mixed Graphs	Mixed Postman Problem (MCPP)	MCPP instances	MCPP char	MCPP solutions	readme
	Mixed Rural Postman Problem (MRPP)	MRPP instances	MRPP char	MRPP solutions	readme
	Mixed General Routing Problem (MGRP)	MGRP instances	MGRP char	MGRP solutions	readme
	Hierarchichal Mixerd Rural Postman Problem (HMRPP)	HMRPP instances		HMRPP solutions
Windy Graphs	Windy Postman Problem (WPP)	WPP instances	WPP char	WPP solutions	readme
	Windy Rural Postman Problem (WRPP)	WRPP instances	WRPP char	WRPP solutions	readme
	Windy General Routing Problem (WGRP)	WGRP instances	WGRP char	WGRP solutions	readme
	Min-Max K-vehicles Windy RPP	MM K-WRPP	MM K-WRPP char	MM K-WRPP	readme
	Profitable Windy RPP (PWRPP)	PWRPP instances	PWRPP char	PWRPP solutions	readme_PWRPP