Arc
Routing Problems: Data Instances
Problem |
|
|
values |
files |
References | |
Undirected
Graphs |
Graphical TSP |
[1] | ||||
Upgrading
Graphical TSP (U-GTSP) |
|
|
[27] | |||
Rural Postman Problem (RPP) |
[1] | |||||
General Routing Problem (GRP) |
[1] | |||||
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] | |||
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. 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.
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).