[CPCP] Instances

In order to perform computational experiments on the CPCP we considered five sets of instances: four are from previous literature, and the fifth is a set of large instances that we created to better evaluate our methods. Following the literature, in all the test sets each vertex is both a customer and a candidate location for a facility (i.e., C = F).

  • Set 1 (S1) - This set contains 160 instances proposed for the CPMP by Ceselli and Righini (2005) and derived from 40 different graphs containing either 50, 100, 150, or 200 vertices. This set includes and extends 20 instances from the OR-Library used in Scaparra et al. (2004). The demands and the coordinates of the vertices were randomly generated, and the distances were obtained by computing Euclidean values rounded down to the nearest integer. From each graph, four instances were produced by setting p equal to ⌊n/10⌋, ⌊n/4⌋, ⌊n/3⌋, or ⌊n/2.5⌋. The facility capacities are homogeneous and set to ⌈12n/p⌉. These instances are available here.
  • Set 2 (S2) - This set contains eight instances by Scaparra et al. (2004), derived from two different graphs containing either 100 or 150 vertices and with non-Euclidean integer distances. From each graph, four instances with homogeneous capacities and four with heterogeneous capacities were created by selecting p ∈ {5, 15}. These instances are available here.
  • Set 3 (S3) - Proposed by Lorena and Senne (2004) for the CPMP, this set contains six instances with n varying from 100 to 402 and p varying from 10 to 40, with homogeneous capacities equal to ⌈(∑j qj) / (τ p)⌉ and τ ∈ {0.8, 0.9}. The distances are Euclidean. Albareda-Sambola et al. (2010) considered floating-point values, while Quevedo-Orozco and Rķos-Mercado (2015) rounded down to the nearest integer. These instances are available here.
  • Set 4 (S4) - This set contains five instances by Lorena and Senne (2004), obtained by modifying the "Pcb3038" instance of the TSPLIB, varying p in {600, 700, 800, 900, 1000}. The facility capacities are homogeneous and set to ⌈(∑j qj) / (τ p)⌉, with τ ∈ {0.8, 0.9}. These instances are available here.
  • New set (KIV) - We generated 280 new instances that are similar to S1, but have either n ∈ {300, 500,1000, 2000, 3000} and integer distances, or n ∈ {50, 100, 150, 200, 300, 500, 1000, 2000, 3000} and floating-point distances. As in S1, the demand values were randomly generated within the interval [1, 20]. To obtain a customer density similar to that of Scaparra et al. (2004), we randomly generated the vertex coordinates in [1, √100n]. We created 20 instances for each value of n, dividing them into four groups of five instances each, with p equal to ⌊n/10⌋, ⌊n/7⌋, ⌊n/4⌋, or ⌊n/3⌋. These instances are available here.


References

Albareda-Sambola M, Dķaz J, Fernįndez E (2010) Lagrangean duals and exact solution to the capacitated p-center problem. European Journal of Operational Research 201(1):71–81. Available at https://doi.org/10.1016/j.ejor.2009.02.022.

Ceselli A, Righini G (2005) A branch-and-price algorithm for the capacitated p-median problem. Networks 45(3):125–142. Available at https://doi.org/10.1002/net.20059.

Lorena L, Senne E (2004) A column generation approach to capacitated p-median problems. Computers & Operations Research 31(6):863–876. Available at https://doi.org/10.1016/S0305-0548(03)00039-X.

Quevedo-Orozco D, Rķos-Mercado R (2015) Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent. Computers & Operations Research 62:133–144. Available at https://doi.org/10.1016/j.cor.2014.12.013.

Scaparra M, Pallottino S, Scutellą M (2004) Large-scale local search heuristics for the capacitated vertex p-center problem. Networks 43(4):241–255. Available at https://doi.org/10.1002/net.20000.