Instances for the Capacitated m-Ring-Star Problem

1. How to Cite This Page

2. Problem Definition

3. Instance Files

4. Optimal Solution Files

5. Bibliography

6. Acknowledgements

How to Cite This Page

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 d_ij

for each edge (i,j):

'e' i j c_ij

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

Click here to download an archive file with all instances.

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:

• instances in the group CEIL_2D

• instances in the group BDS

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 “-”.

All optimum solution files are available to download here.

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 x_ij

total of connection arcs at the solution

for each connection arc ij:

i j x_ij

value of the solution

where, x_ij 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].

Optimal solutions for instances in the group BDS

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

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.