Problem

Arc Routing Problems: Data Instances

This webpage is maintained by Ángel Corberán, Isaac Plana, Miguel Reula and José María Sanchis. Last updated on May 2023. You can find data for different types of Arc Routing Problems defined on undirected, directed, mixed, and windy graphs, as well as Drone Arc Routing Problems. 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	References
Undirected Graphs	Graphical TSP	GTSP instances	GTSP char	GTSP solutions	readme	[1]
	Upgrading Graphical TSP (U-GTSP)	UGTSP_instances		UGTSP solutions		[27]
	Rural Postman Problem (RPP)	RPP instances	RPP char	RPP solutions	readme	[1]
	General Routing Problem (GRP)	GRP instances	GRP char	GRP solutions	readme	[1]
	Maximum Benefit CPP (MBCPP)	MBCPP instances	MBCPP char	MBCPP solutions	readme	[5]
Directed Graphs	Directed General Routing Problem (DGRP)	DGRP instances	DGRP char	DGRP solutions	readme_DGRP	[1], [8]
	Stacker Crane Problem (SCP)	SCP instances	SCP char	SCP solutions	readme_SCP	[1], [8]
	Close Enough Arc Routing Problem (CEARP) or Generalized Directed RPP (GDRPP)	CEARP instances	CEARP char	CEARP solutions	readme_CEARP	[9]
	Profitable CEARP (PCEARP)	PCEARP instances	PCEARP char	PCEARP solutions	readme_PCEARP	[20]
	Distance-Constrained CEARP (DC-CEARP)	DC-CEARP instances	DC-CEARP char	DC-CEARP solutions	readme_DC-CEARP	[14], [16], [18]
	Min-Max CEARP (MM-CEARP)	MM-CEARP instances	MM-CEARP char	MM-CEARP solutions	readme_MM-CEARP	[21]
	Orienteering ARP (OARP)	OARP_instances	OARP_char	OARP_solutions	readme_OARP	[11]
	Team Orienteering ARP (TOARP)	TOARP_instances	TOARP_char	TOARP_solutions	readme_TOARP	[7]
	Directed Profitable Rural Postman Problem with Incompatibility Constraints (DPRPP-IC)	DPRPP-IC instances			readme_DPRPP-IC	[15]
Mixed Graphs	Mixed Postman Problem (MCPP)	MCPP instances	MCPP char	MCPP solutions	readme	[1]
	Mixed Rural Postman Problem (MRPP)	MRPP instances	MRPP char	MRPP solutions	readme	[1]
	Mixed General Routing Problem (MGRP)	MGRP instances	MGRP char	MGRP solutions	readme	[1]
	Hierarchical Mixed Rural Postman Problem (HMRPP)	HMRPP instances		HMRPP solutions		[12], [13]
	The Periodic Rural Postman Problem with Irregular Services on Mixed Graphs (PRPP-IS)	PRPP-IS instances	PRPP-IS char	PRPP-IS solutions	readme	[17], [22]
Windy Graphs	Windy Postman Problem (WPP)	WPP instances	WPP char	WPP solutions	readme	[1], [4]
	Windy Rural Postman Problem (WRPP)	WRPP instances	WRPP char	WRPP solutions	readme	[1], [4]
	Windy General Routing Problem (WGRP)	WGRP instances	WGRP char	WGRP solutions	readme	[1]
	Min-Max K-vehicles Windy RPP	MM K-WRPP	MM K-WRPP char	MM K-WRPP	readme	[2], [3], [6]
	Profitable Windy RPP (PWRPP)	PWRPP instances	PWRPP char	PWRPP solutions	readme_PWRPP	[10]
Drone ARPs	Length-Constrained K-Drones RPP (LC K-DRPP)	LC K-DRPP instances	LC K-DRPP char	LC K-DRPP solutions	readme_ LC K-DRPP	[19], [23]
	Multipurpose K-drones General Routing Problem (MP K-DGRP)	MP K-DGRP instances		MP K-DGRP solutions	readme_ MP K-DGRP	[24]
	Load-Dependent drone General Routing Problem (LDdGRP)	LDdGRP instances		LDdGRP solutions	readme_LDdGRP	[26]
	Multi-Depot drone General Routing Problem with duration and capacity constraints (MDdGRP)	MDdGRP instances		MDdGRP solutions	readme_MDdGRP	[25]
	Min-Max Multi-Trip drone Location Arc Routing Problem (MM-MT-dLARP)	MM-MT-dLARP instances		MM-MT-dLARP solutions	readme_MM-MT-dLARP	[28]

[1] Corberán, Plana and Sanchis. A Branch & Cut Algorithm for the Windy General Routing Problem and special cases, Networks 49, pp. 245-257, 2007.

[2] Benavent, Corberán, Plana and Sanchis. Min-Max K-vehicles Wind Rural Postman Problem, Networks, Vol. 54(4), pp. 216-226, 2009

[3] Benavent, Corberán, Plana and Sanchis. 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.

[4] Corberán, Oswald, Plana, Reinelt and Sanchis. New results on the Windy Postman Problem, Mathematical Programming, Vol. 132, pp. 309-332, 2012.

[5] 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.

[6] 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.

[7] Archetti, Corberán, Plana, Sanchis, and Speranza. The Team Orienteering Arc Routing Problem, Transportation Science, Vol. 48, pp. 442-457, 2014.

[8] Ávila, Corberán, Plana and Sanchis. The Stacker Crane Problem and the Directed General Routing Problem, Networks, Vol. 65, pp. 43-55, 2015.

[9] Á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.

[10] Á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.

[11] 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.

[12] Colombi, Corberán, Mansini, Plana and Sanchis. The Hierarchical Mixed Rural Postman Problem. Transportation Science, Vol. 51(2), pp. 755-770, 2016.

[13] Colombi, Corberán, Mansini, Plana and Sanchis. The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm. EJOR, Vol. 257(1), pp. 1-12, 2017.

[14] Ávila, Corberán, Plana and Sanchis. Formulations and exact algorithms for the Distance-Constrained Generalized Directed RuralPostman Problem, EURO Journal on Computational Optimization, Vol. 5 (3), pp. 339-365, 2017.

[15] Colombi, Corberán, Mansini, Plana and Sanchis. The directed profitable rural postman problem with incompatibility constraints. EJOR, Vol. 261(2), pp. 549-562, 2017.

[16] Corberán, Plana, Reula and Sanchis. A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem. TOP, Vol. 27, pp. 312-326, 2019.

[17] Benavent, Corberán, Laganà and Vocaturo. The Periodic Rural Postman Problem with Irregular Services on Mixed Graphs, European Journal of Operational Research, Vol. 276, pp. 826-839, 2019.

[18] Corberán, Plana, Reula and Sanchis. On the Distance-Constrained Close-Enough Arc Routing Problem. EJOR, Vol 291 (1), pp 32-51, 2021.

[19] Campbell, Corberán, Plana, Sanchis and Segura. Solving the length constrained K-drones rural postman problem. EJOR, Vol. 292(1), pp. 60-72, 2021.

[20] Bianchessi, Corberán, Plana, Reula and Sanchis. The Profitable Close Enough Arc Routing Problem. Computers & Operations Research, 140: 105663, 2022.

[21] Bianchessi, Corberán, Plana, Reula and Sanchis. The Min-Max Close-Enough Arc Routing Problem. EJOR, Vol. 300, pp.837-851, 2022.

[22] Benavent, Corberán, Laganà and Vocaturo. A two-phase hybrid algorithm for the periodic rural postman problem with irregular services on mixed graphs. EJOR, Vol. 307 (1), pp. 64-81, 2022.

[23] Campbell, Corberán, Plana, Sanchis and Segura. Polyhedral analysis and a new algorithm for the length constrained K-drones rural postman problem. Computational Optimization and Applications, Vol. 83(1), pp. 67-109, 2022.

[24] Campbell, Corberán, Plana, Sanchis and Segura. The multi-purpose K-drones general routing problem. Submitted, 2023.

[25] T. Corberán, Plana, Sanchis, Segura. The Multi-Depot drone General Routing Problem with duration and capacity constraints. Submitted, 2023.

[26] Plana, Sanchis, Segura. The Load-Dependent drone General Routing Problem. In preparation, 2023.

[27] Landete, Plana, Sainz-Pardo, Sanchis. Upgrading edges in the Graphical TSP. Submitted, 2023.

[28] T. Corberán, Plana, Sanchis. The min max multi-trip drone location arc routing problem. In preparation, 2024.

Other contributions

The optimal values for the MCPP instance MB1055, and the MGRP instance GD427, as well as the best-knownsolutions 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, WRPPinstances 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).