direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Capacitated Location Routing Instance Library (CLRlib)

Lupe

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.

Instances

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., M2,2 is an instance with 1000 clients, 100 facilities, facility opening costs in [100;200], and vehicle capacity 100.

Result overview
name
lower bound
bks
gap
M1,1
8800.8
13478.9
0.532
M1,2
41249.5
3499.05
0.669
M1,3
2096.3
2478.9
0.183
M2,1
12166.6
17997
0.479
M2,2
2288.8
4468.74
0.952
M2,3
2151.6
2620.84
0.218
M3,1
15432.2
22926.8
0.486
M3,2
2938.7
5345.92
0.819
M3,3
2203.4
2779.25
0.261
L1,1
17502
32325.9
0.847
L1,2
4607
8106.1
0.76
L1,3
4607
5463.71
0.186
L2,1
29519.6
50229.7
0.702
L2,2
5946.5
12059.5
1.028
L2,3
4659.4
6624.78
0.422
L3,1
38728.3
63905.1
0.65
L3,2
7515.9
14372.4
0.912
L3,3
4709.4
6966.54
0.479
XL1,1
25449.7
48677.1
0.913
XL1,2
6494.6
11872
0.828
XL1,3
6494.6
7754.66
0.194
XL2,1
46601.8
77580.6
0.665
XL2,2
9253.7
18159.1
0.962
XL2,3
6550.3
9296.1
0.419
XL3,1
60461.3
101454
0.678
XL3,2
11838.1
21341.5
0.803
XL3,3
6600.5
10389.9
0.574
average
14328.43
21562
0.616
Lupe

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

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions