The capacitated location routing problem

Location routing integrates the two classical optimization problems of facility location and vehicle routing, addressing both location and tour planning decisions in a single step. There is a large number of different versions of location routing problems, incorporating different sets of constraints arising in real-world applications, such as vehicle and depot capacities or time windows.

In the basic version considered here, we are given a graph whose vertex set consists of facilities and clients with given demands, metric edge costs, and a uniform vehicle capacity. The problem is to find a subset of facilities that have to be opened, and a set of tours originating from those facilities, serving all clients while not violating the vehicle capacity, and minimizing the incurred opening and connection costs.

For a more formal problem definition, see, e.g., Section 2 of Approximation Algorithms for Capacitated Location Routing.

CLR test sets

Given their considerable practical relevance, location routing problems have received great attentition by the operations research and combinatorial optimization community. An extensive number of heuristics has been designed for different variants of the problems and benchmarked in computational studies. Many researchers published not only their computational results but also their instance sets, so as to enable other researchers to perform studies on the same set. A very good resource, e.g., is the instance collection by Duhamel, Lacomme, Prins and Prodhon.

The instances found in the CLRlib test set were generated in order to test the performance of an approximation algorithm for CLR. While running this algorithm, it turned out that the cpu time of the algorithm used on the moderately sized classical CLR instances as found in the library mentioned above was barely measurable. Thus, we generated larger instances with up to 10,000 clients and 1,000 facilities (100 times the size of classical instances) to verify its performance.

Download

All instances of the CLRlib are available for download as a compressed zip-archive. The format of the files is identical to the one used in the collection of classical LRP instances by Carolin Prodhon. For information, see the file format description page (a text version of the explanation is also included in the archive).

Click here to download all instances of the CLRlib (Feb 02, 2012).

Submit new results

If you performed computational experiments on the instances of the CLRlib and published your results, please send us a mail to matuschke 'at' math.tu-berlin.de with a link to the corresponding publication, so we can update the table by adding your results and updating the best known solution and lower bound columns.

This website hosts the CLRlib, a libary of instances of the capacitated location routing problem (CLR) with a focus on large instance sizes. This test set can be used as a benchmark for algorithms for CLR. It is part of MultiTrans, a joint research project with 4flow AG, Berlin.

Authors of CLR algorithms are invited to download the test set and perform computations on its instances. Please inform us of your results via email, so we can keep the tables on this website up-to-date.

The instances of the CLRlib were generated in a similar fashion as facilitated by Tuzun and Burke. The instances are build on three base networks of different sizes: M (1000 clients, 100 facilities), L (5000, 500), and XL (10000, 1000). All clients and facilities are identified with points in the Euclidian plane, with x- and y-coordinates drawn uniformly at random. Facility opening costs were drawn uniformly at random from three different ranges: [0;100], [100;200], and [200;500] and vehicle capacities were set to either 9, 100, or 1000, while client demands were drawn uniformly at random from [0;10] in all cases. All possible combinations of the three input parameters yield 27 different instances, which are named by their size, indexed with their choice of facility opening cost and vehicle capacity. E.g., M_2,2 is an instance with 1000 clients, 100 facilities, facility opening costs in [100;200], and vehicle capacity 100.

This work is part of the MultiTrans project, a joint project with 4flow AG, Berlin, and supported by European Regional Development Fund (ERDF).