Benchmarks
Three sets of testing problems, organised by the size, were used to perform the computational study.
In all cases, customers are also considered to be possible facility locations, i.e. sets
I and
J are identical. As there are no standard test problems for facility location problem with lexicographic minimax objective we used problems originally proposed for the capacitated p-median problem while interpreting demands as multiplicities of customers. Twenty small instances
pmedcap1- pmedcap20 were taken from the OR-library[1]. To this set we also included the smallest testing problem
SJC1 used in the reference[2]. Three larger problems taken from the same source
SJC2,
SJC3 and
SJC4 together with two instances (
spain_737_1 and
spain_737_2) derived from the network of 737 Spanish cities[3] constitute the medium sized instances. The largest test problems include problem
p3038, originally proposed for the TSP[4] and later adjusted to the capacitated p-median problem [2]. Furthermore, considering population data, we created large-sized benchmarks from the road network of the
Slovak Republic[5] and the road network of six south-eastern
U.S. states[6].
Description of Files
When opening the directory with the benchmark data you will find two directories
Network and
Problem, each containing the following files:
Network
- matVzdialenosti.txt - file with the distance matrix. File contains |I|*|I| + 2 rows (I is the number of nodes representing aggregate customers and possible locations of facilities). In the first and in the second row is stored value of I parameter. In the consequent rows are stored the values of distances dij.
- zakazniciId.txt - file with indexes of active customers. In the first row is the number of active customers. If all customers in the benchmark are active (as we defined them in all benchmarks) then the file contains simple sequence of numbers 1, ..., I.
- zakazniciNazvy.txt - file with names of customer locations. Names can be used when reporting the results to identify customers.
- zakazniciPocObyv.txt - file with multiplicities (number of individual customers for every aggregate customer) for all active customers.
Problem
- maxP.txt - file with the values of parameter p (number of facilities to be located). In the first row is the number of values p for which the problem should be calculated. The values are listed in consequent rows.
- skladyId.txt - file with indexes of candidates for facility locations. In the first row is the number of active cadidate nodes. If all nodes are candidates for facility location (as we defined them in all benchmarks) then the file contains simple sequence of numbers 1, ..., I.
- skladyNazvy.txt - file with names of facility candidate locations. Names can be used when reporting the results to identify facility locations.
References
[1] J. E. Beasley, OR-Library: distributing test problems by electronic mail,
Journal of the Operational Research Society 41 (11) (1990) 1069-1072.
[2] L. A. Lorena, E. L. Senne, A column generation approach to capacitated
p-median problems, Computers & Operations Research 31 (6) (2004) 863-876.
[3] J. A. Diaz, E. Fernandez, Hybrid scatter search and path relinking for the capacitated p-median problem, European Journal of Operational Research 169 (2) (2006) 570-585.
[4] G. Reinelt, The traveling salesman: computational solutions for TSP applications, Springer-Verlag, Berlin, Heidelberg, 1994.
[5] Data describing the road network of the Slovak Republic were purchased from the publisher MAPA Slovakia Plus s.r.o.
http://www.mapaslovakia.sk (last accessed on 13/08/2013)
[6] United States Census Database 2000.
http://www.nationalatlas.gov/mld/ce2000t.html (last accessed
on 13/08/2013).