Arc
Routing Problems: Data Instances
|
Problem |
|
|
values |
files |
References |
|
|
Undirected Graphs |
Graphical TSP |
[1], [28] |
||||
|
Upgrading
Graphical TSP (U-GTSP) |
|
|
[27] |
|||
|
Rural Postman Problem (RPP) |
[1], [28] |
|||||
|
General Routing Problem (GRP) |
[1], [28] |
|||||
|
Maximum Benefit CPP (MBCPP) |
|
[5] |
||||
|
Directed Graphs |
Directed
General Routing Problem (DGRP) |
[1], [8] |
||||
|
Stacker Crane Problem (SCP) |
[1], [8] |
|||||
|
Close Enough Arc Routing Problem (CEARP)
or Generalized Directed RPP (GDRPP) |
[9] |
|||||
|
Profitable CEARP (PCEARP) |
[20] |
|||||
|
Distance-Constrained
CEARP (DC-CEARP) |
[14], [16], [18] |
|||||
|
Min-Max CEARP
(MM-CEARP) |
[21] |
|||||
|
Orienteering
ARP (OARP) |
[11] |
|||||
|
Team Orienteering
ARP (TOARP) |
[7] |
|||||
|
Directed Profitable Rural
Postman Problem with Incompatibility Constraints (DPRPP-IC) |
|
|
[15] |
|||
|
Mixed Graphs |
Mixed Postman Problem (MCPP) |
[1] |
||||
|
Mixed
Rural Postman Problem (MRPP) |
[1] |
|||||
|
Mixed
General Routing Problem (MGRP) |
[1] |
|||||
|
Hierarchical
Mixed Rural Postman Problem (HMRPP) |
|
[12], [13] |
||||
|
The Periodic
Rural Postman Problem with Irregular Services on Mixed
Graphs (PRPP-IS) |
[17], [22] |
|||||
|
Windy Graphs |
Windy Postman Problem (WPP) |
[1], [4] |
||||
|
Windy
Rural Postman Problem (WRPP) |
[1], [4] |
|||||
|
Windy
General Routing Problem (WGRP) |
[1] |
|||||
|
Min-Max
K-vehicles Windy RPP |
[2], [3], [6] |
|||||
|
Profitable Windy RPP (PWRPP) |
[10] |
|||||
|
Drone ARPs |
Length-Constrained K-Drones RPP (LC K-DRPP) |
[19], [23] |
||||
|
Multipurpose K-drones General Routing Problem (MP K-DGRP) |
|
[24] |
||||
|
Load-Dependent drone General Routing Problem (LDdGRP) |
[26] |
|||||
|
Multi-Depot drone General Routing Problem with duration and capacity constraints (MDdGRP) |
[25] |
[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. Networks, pp. 1–22, https://doi.org/10.1002/net.22176, 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. Computers &
Operations Research, Vol. 159,
https://doi.org/10.1016/j.cor.2023.106321, 2023.
[28] Corberán, Plana, Sanchis, Segura. Theoretical and computational analysis of a new formulation for the Rural Postman Problem and the General Routing Problem. Submitted, 2023.
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).