# Instances for the Capacitated m-Ring-Star Problem

Please use the BibTex entry bellow:

@Misc{cmrsp-instance-page,

author = {E. A. Hoshino and C. C. de Souza},

title = {Instances for the Capacitated m-Ring-Star Problem},

howpublished = {{\tt www.ic.unicamp.br/\raisebox{-0.6ex}{\~{}}cid/Problem-instances/CmRSP/}},

}

# Problem Definition

Let G=(V,E A) a mixed graph, where E is a set of edges in V and A is a set of directed arcs (called connections). Each edge has a routing cost and each arc has a connection cost, those costs are non-negative integers. We consider V partitioned in three parts: a special vertex 0, denoting a central depot, a set of customers U and a set of Steiner points W.

A ring-star is a pair (R,S) where R is a subset of edges in E defining a cycle that includes the central depot, and S is a subset of arcs in {ij in A : i is a customer and j is a endpoint of some edge in R}. We say that it is Q-capacitated if the total of customers at the ring-star is at most Q. A ring-star (R,S) covers a customer v if v is a endpoint of some edge in R or S contains a connection from v to a endpoint of some edge in R.

The capacitated m-ring-star problem (CmRSP) asks for m ring-stars Q-capacitated covering all customers and minimizing the sum of routing and connection costs. This problem was first studied in [1] and is NP-hard since it generalizes the Traveling Salesman Problem.

# Instance Files

All instances are generated from TSPLIB and are separated in two groups: BDS and CEIL_2D. First group refers to instances used in [1] and obtained using the EUC_2D metric distance and applying a post-processing. The second one contains instances generated using the CEIL_2D metric distance and was used to analyze the branch-and-price[3] and branch-and-cut-and-price[4] approaches. See [5] for more details about those metrics and [4] for explanations about the instances.

There are three classes of instances: class A, class B and class C.

We named each instance file by eil<n>.tsp.<m>.<|U|>.<Q>.<class>.<group>.cmrsp, where

<class> : A or B or C

<group> : BDS or CEIL_2D.

The format of these files is:

n |U| |W| Q m

for each connection ij:

'a' i j dij

for each edge (i,j):

'e' i j cij

where cij is the routing cost of the edge (i,j) and dij is the connection cost of the arc ij.

All instance files can be viewed here.

# Optimal Solution Files

The following tables report the value of the optimum solution (when it is available) for:

We list the value of the optimum solution in each instance class and at parenthesis which code produced it. When it is not available we mark it with “-”.

First lines of those files contain some comments about the instance. After comments lines, the output format is:

total of routing edges at the solution

for each routing edge (i,j):

i j xij

total of connection arcs at the solution

for each connection arc ij:

i j xij

value of the solution

where, xij is the number of times the edge or arc occurs in the solution.

### Optimal solutions for instances in the group CEIL_2D

The bc and bcp codes refer to implementations of the branch-and-cut and branch-and-cut-and-price algorithms, respectively, for the CmRSP described in [2]. We limited the running time for both codes to 1800 seconds.

Some solutions (marked with *) have one ring-star (R,S) in which S is empty and R is a cycle passing only through the central depot and one Steiner point. This implies that a better solution could be found using fewer ring-stars in those instances. Nevertheless, we prefer not to reduce the number of ring-stars in order to strictly follow the procedure to generate instances described in [1].

 instance m U Q class A class B class C eil26.tsp 3 6 3 178(bcp,bc) 1246(bcp,bc) 159(bcp,bc) eil26.tsp 4 6 2 198*(bcp,bc) 1386*(bcp,bc) 177(bcp,bc) eil26.tsp 5 6 2 215*(bcp,bc) 1505*(bcp,bc) 193(bcp,bc) eil26.tsp 3 12 5 254(bcp,bc) 1778(bcp,bc) 226(bcp,bc) eil26.tsp 4 12 4 271(bcp,bc) 1897(bcp,bc) 243(bcp,bc) eil26.tsp 5 12 3 304(bcp,bc) 2128(bcp,bc) 270(bcp,bc) eil26.tsp 7 12 2 373(bcp,bc) 2611(bcp,bc) 324(bcp,bc) eil26.tsp 10 12 2 429*(bcp,bc) 3003*(bcp,bc) 406*(bcp,bc) eil26.tsp 3 18 7 312(bcp,bc) 2184(bcp,bc) 289(bcp,bc) eil26.tsp 4 18 5 349(bcp,bc) 2443(bcp,bc) 324(bcp,bc) eil26.tsp 5 18 4 387(bcp,bc) 2709(bcp,bc) 353(bcp,bc) eil26.tsp 7 18 3 462(bcp,bc) 3234(bcp,bc) 414(bcp,bc) eil26.tsp 10 18 2 590*(bcp,bc) 4130*(bcp,bc) 500(bcp,bc) eil26.tsp 14 18 2 680*(bcp,bc) 4760*(bcp,bc) 625*(bcp,bc) eil26.tsp 3 25 10 346(bcp,bc) 2422(bcp,bc) 327(bcp,bc) eil26.tsp 4 25 7 379(bcp,bc) 2653(bcp,bc) 362(bcp,bc) eil26.tsp 5 25 6 398(bcp,bc) 2786(bcp,bc) 385(bcp,bc) eil26.tsp 7 25 4 490(bcp,bc) 3430(bcp,bc) 460(bcp,bc) eil26.tsp 10 25 3 601(bcp,bc) 4207(bcp,bc) 547(bcp,bc) eil26.tsp 14 25 2 771(bcp,bc) 5397(bcp,bc) 683(bcp,bc) eil51.tsp 3 12 5 254(bcp,bc) 1778(bcp,bc) 226(bcp,bc) eil51.tsp 4 12 4 271(bcp,bc) 1897(bcp,bc) 241(bcp,bc) eil51.tsp 5 12 3 303*(bcp,bc) 2121*(bcp,bc) 270(bcp,bc) eil51.tsp 7 12 2 373(bcp,bc) 2611(bcp,bc) 319(bcp,bc) eil51.tsp 10 12 2 420*(bcp,bc) 2940*(bcp,bc) 373*(bcp,bc) eil51.tsp 3 25 10 343(bcp,bc) 2354(bcp,bc) 325(bcp,bc) eil51.tsp 4 25 7 378(bcp,bc) 2606(bcp,bc) 359(bcp,bc) eil51.tsp 5 25 6 395(bcp,bc) 2718(bcp,bc) 383(bcp,bc) eil51.tsp 7 25 4 489(bcp,bc) 3400(bcp,bc) 457(bcp,bc) eil51.tsp 10 25 3 595*(bcp,bc) 4111*(bcp,bc) 539(bcp,bc) eil51.tsp 14 25 2 769*(bcp,bc) 5353*(bcp,bc) 669*(bcp,bc) eil51.tsp 3 37 14 406(bcp,bc) 2795(bcp,bc) 397(bcp,bc) eil51.tsp 4 37 11 437(bcp,bc) 3022(bcp,bc) 427(bc) eil51.tsp 5 37 9 467(bcp) 3236(bcp,bc) 446(bcp,bc) eil51.tsp 7 37 6 547(bcp) 3775(bcp) 530(bcp) eil51.tsp 10 37 5 626(bcp) 4335(bcp) 598(bcp) eil51.tsp 14 37 3 829(bcp,bc) 5759(bcp,bc) 765(bcp,bc) eil51.tsp 3 50 19 496(bc) 3393(bc) - eil51.tsp 4 50 14 530(bcp,bc) 3624(bcp,bc) 505(bcp) eil51.tsp 5 50 12 560(bcp) 3853(bcp) - eil51.tsp 7 50 8 648(bcp) 4474(bcp) - eil51.tsp 10 50 6 754(bcp) 5216(bcp) 721(bcp) eil51.tsp 14 50 4 954(bcp) 6612(bcp) 905(bcp) eil76.tsp 3 18 7 338(bcp) 2319(bcp) - eil76.tsp 4 18 5 399(bcp) 2729(bcp) 385(bcp) eil76.tsp 5 18 4 460(bcp) 3172(bcp) 439(bcp) eil76.tsp 7 18 3 558*(bcp) 3824*(bcp) 527*(bcp) eil76.tsp 10 18 2 746*(bcp) 5137*(bcp) 676*(bcp,bc) eil76.tsp 14 18 2 814*(bcp) 5613*(bcp) 745*(bcp,bc) eil76.tsp 3 37 14 - - - eil76.tsp 4 37 11 - - - eil76.tsp 5 37 9 501(bcp) 3495(bcp) 491(bcp) eil76.tsp 7 37 6 641(bcp) 4451(bcp) 626(bcp) eil76.tsp 10 37 5 748*(bcp) 5177*(bcp) 723*(bcp) eil76.tsp 14 37 3 1045*(bcp) 7235(bcp) 969*(bcp) eil76.tsp 3 56 21 - - 488(bc) eil76.tsp 4 56 16 - - - eil76.tsp 5 56 13 584(bcp) - 566(bcp) eil76.tsp 7 56 9 - - - eil76.tsp 10 56 7 824(bcp) 5541(bcp) - eil76.tsp 14 56 5 1030(bcp) - - eil76.tsp 3 75 28 - - - eil76.tsp 4 75 21 - - - eil76.tsp 5 75 17 - - - eil76.tsp 7 75 12 - - - eil76.tsp 10 75 9 - - - eil76.tsp 14 75 6 1180(bcp) - - eil101.tsp 3 25 10 381(bcp) 2629(bcp) - eil101.tsp 4 25 7 433(bcp) 2972(bcp) - eil101.tsp 5 25 6 469(bcp) 3237(bcp) - eil101.tsp 7 25 4 576(bcp) 3986(bcp) - eil101.tsp 10 25 3 693*(bcp) 4803*(bcp) 631*(bcp) eil101.tsp 14 25 2 905*(bcp) 6244*(bcp) 789*(bcp,bc) eil101.tsp 3 50 19 - - - eil101.tsp 4 50 14 - - - eil101.tsp 5 50 12 - - - eil101.tsp 7 50 8 - - - eil101.tsp 10 50 6 819*(bcp) - - eil101.tsp 14 50 4 - - 993(bcp) eil101.tsp 3 75 28 648(bc) - - eil101.tsp 4 75 21 - - - eil101.tsp 5 75 17 - - - eil101.tsp 7 75 12 - - - eil101.tsp 10 75 9 - - - eil101.tsp 14 75 6 - - - eil101.tsp 3 100 38 - - - eil101.tsp 4 100 28 - - - eil101.tsp 5 100 23 - - - eil101.tsp 7 100 16 - - - eil101.tsp 10 100 12 - - - eil101.tsp 14 100 8 - - -

### Optimal solutions for instances in the group BDS

In this table, the results for the bc code refer to those published in [1].

 instance m U Q class A class B eil26.tsp 3 12 5 242(bcp,bc) 1684(bcp,bc) eil26.tsp 4 12 4 261(bcp,bc) 1827(bcp,bc) eil26.tsp 5 12 3 292(bcp,bc) 2041(bcp,bc) eil26.tsp 3 18 7 301(bcp,bc) 2104(bcp,bc) eil26.tsp 4 18 5 339(bcp,bc) 2370(bcp,bc) eil26.tsp 5 18 4 375(bcp,bc) 2615(bcp,bc) eil26.tsp 3 25 10 325(bcp,bc) 2251(bcp,bc) eil26.tsp 4 25 7 362(bcp,bc) 2510(bcp,bc) eil26.tsp 5 25 6 382(bcp,bc) 2674(bcp,bc) eil51.tsp 3 12 5 242(bcp,bc) 1681(bcp,bc) eil51.tsp 4 12 4 261(bcp,bc) 1821(bcp,bc) eil51.tsp 5 12 3 286(bcp,bc) 1972(bcp,bc) eil51.tsp 3 25 10 322(bcp,bc) 2176(bcp,bc) eil51.tsp 4 25 7 360(bcp,bc) 2470(bcp,bc) eil51.tsp 5 25 6 379(bcp,bc) 2579(bcp,bc) eil51.tsp 3 37 14 373(bcp,bc) 2490(bcp,bc) eil51.tsp 4 37 11 405(bcp,bc) 2721(bcp,bc) eil51.tsp 5 37 9 432(bcp,bc) 2908(bcp,bc) eil51.tsp 3 50 19 458(bcp,bc) 3015(bcp,bc) eil51.tsp 4 50 14 490(bcp,bc) 3260(bcp,bc) eil51.tsp 5 50 12 520(bcp,bc) 3404(bcp,bc) eil76.tsp 3 18 7 330(bcp,bc) 2253(bcp,bc) eil76.tsp 4 18 5 385(bcp,bc) 2620(bcp,bc) eil76.tsp 5 18 4 448(bcp,bc) 3059(bcp,bc) eil76.tsp 3 37 14 402(bcp,bc) 2720(bcp,bc) eil76.tsp 4 37 11 * * eil76.tsp 5 37 9 479(bcp,bc) 3284(bcp) eil76.tsp 3 56 21 471(bc) * eil76.tsp 4 56 16 * * eil76.tsp 5 56 13 545(bcp,bc) * eil76.tsp 3 75 28 564(bc) * eil76.tsp 4 75 21 * * eil76.tsp 5 75 17 * * eil101.tsp 3 25 10 363(bcp,bc) 2434(bcp,bc) eil101.tsp 4 25 7 415(bcp,bc) 2782(bcp,bc) eil101.tsp 5 25 6 448(bcp,bc) 3009(bcp,bc) eil101.tsp 3 50 19 * * eil101.tsp 4 50 14 * * eil101.tsp 5 50 12 * * eil101.tsp 3 75 28 595(bc) * eil101.tsp 4 75 21 * * eil101.tsp 5 75 17 * * eil101.tsp 3 100 38 646(bc) * eil101.tsp 4 100 28 * * eil101.tsp 5 100 23 700(bc) *

# Bibliography

[1] Baldacci, R., M. Dell'Amico, and J. Salazar Gonzalez. The Capacitated m-Ring-Star Problem. Operations Research, 55(6):1147-1162, 2007.

[2] Hoshino, E. A. Column Generation Algorithms for the Capacitated m-Ring-Star Problem. Institute of Computing, University of Campinas, PHD' thesis. (in preparation)

[3] Hoshino, E. A., C. C. de Souza. Column Generation Algorithms for the Capacitated m-Ring-Star Problem, in: 14th Annual International Computing and Combinatorics Conference (COCOON 2008), LNCS 5092 (2008), pp. 631–641.

[4] Hoshino, E. A., C. C. de Souza. A Branch-and-Cut-and-Price Approach for the Capacitated m-Ring-Star Problem (submitted).

[5] Reinelt, G. A Traveling Salesman Problem Library. ORSA Journal on Computing, 3:376-384, 1991.

# Acknowledgements

We are grateful to Prof. Roberto Baldacci from the University of Bologna (Italy) who made available to us the instances tested in [1].

Last update: Wed, May 26, 2010 by Edna A. Hoshino.