Arc
Routing Problems: Data Instances
This
webpage is maintained by Ángel Corberán, Isaac Plana,
and José María Sanchis.
Last updated on November 20th 2015.
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, doi: 10.1016/J.ejor.2015.10.016,2015).
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, doi: 10.1007/s13675-015-0053-8, 2015).
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, doi: 10.1287/TRSC.2015.0588, 2015).
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 |
||||
|
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) |
|||||
|
Distance-Constrained GDRPP (DC-GDRPP) |
|||||
|
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) |
|||||
|
Min-Max K-vehicles Windy RPP |
|||||
|
Profitable Windy RPP (PWRPP) |