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 2021. You can find data for different types of Arc Routing Problems defined on undirected, directed, mixed, and windy graphs.

The results for the instances for each specific problem have been obtained in the following articles:

The Rural Postman Problem, the General Routing Problem and the Graphical Traveling Salesman Problem

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

The Maximum Benefit Chinese Postman Problem

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 Directed Rural Postman Problem, the Directed General Routing Problem and the Stacker Crane Problem

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

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

Close-Enough Arc Routing Problem (or Generalized Directed Rural Postman Problem)

Á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 Profitable Close-Enough Arc Routing Problem

Bianchessi, Corberán, Plana, Reula and Sanchis (The Profitable Close-Enough Arc Routing Problem, Submitted, 2021).

The Distance-Constrained Close-Enough Arc Routing Problem

Á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

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

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

ˇ        The Min-Max Close-Enough Arc Routing Problem 

    o   BianchessiCorberán, Plana, Reula and Sanchis(On the Min-Max Close-Enough Arc Routing Problem, Submitted, 2021).

The Orienteering Arc Routing Problem

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 Team Orienteering Arc Routing

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

 

The Windy Postman Problem and Windy Rural Postman Problem

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

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

The Min-Max K-vehicles WRPP

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

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.

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 Profitable Windy Rural Postman Problem

Á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.

 

Other contributions

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

Length-Constrained K-Drones RPP (LC K-DRPP)

LC K-DRPP instances

LC K-DRPP char

LC K-DRPP solutions

readme_ LC K-DRPP

Directed Graphs

Diected General Routing Problem (DGRP)

DGRP instances

DGRP char

DGRP solutions

readme_DGRP

Stacker Crane Problem (SCP)

SCP instances

SCP char

SCP solutions

readme_SCP

 Close Enough Arc Roting Problem (CEARP) or    Generalized Directed RPP (GDRPP)

CEARP instances

CEARP char

CEARP solutions

readme_CEARP

Profitable CEARP (PCEARP)

PCEARP instances

 PCEARP char

PCEARP solutions

readme_PCEARP

Distance-Constrained CEARP (DC-CEARP)

DC-CEARP instances

DC-CEARP char

DC-CEARP solutions

readme_DC-CEARP

Min-Max CEARP (MM-CEARP)

MM-CEARP instances

MM-CEARP char

MM-CEARP solutions

readme_MM-CEARP

Orienteering ARP (OARP)

OARP_instances

OARP_char

OARP_solutions

readme_OARP

Team Orienteering ARP (TOARP)

TOARP_instances

TOARP_char

TOARP_solutions

readme_TOARP

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