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 Bianchessi, Corberá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 |
||||
|
Rural Postman Problem (RPP) |
|||||
|
General Routing Problem (GRP) |
|||||
|
Maximum Benefit CPP (MBCPP) |
|||||
|
Length-Constrained K-Drones RPP (LC K-DRPP) |
|||||
|
Directed Graphs |
Diected General Routing
Problem (DGRP) |
||||
|
Stacker Crane Problem (SCP) |
|||||
|
Close Enough Arc Roting Problem (CEARP)
or Generalized Directed RPP (GDRPP) |
|||||
|
Profitable CEARP (PCEARP) |
|||||
|
Distance-Constrained CEARP (DC-CEARP) |
|||||
|
Min-Max CEARP (MM-CEARP) |
|||||
|
Orienteering ARP (OARP) |
|||||
|
Team Orienteering ARP (TOARP) |
|||||
|
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) |
|||||
|
Min-Max K-vehicles Windy RPP |
|||||
|
Profitable Windy RPP (PWRPP) |