Geoscience Reference
In-Depth Information
Table 13.1
Problem instances
Name
Range
Reference
Comments
Nug
12-30
Nugent et al. (
1968
)
All optimal solutions found
Tai a
12-100
Taillard (
1991
)
Random weights & distances
Tai b
12-150
Taillard (
1991
)
Real-life like
Tai c
64-256
Taillard (
1995
)
Grey pattern problems
Tai e
27-343
Drezner et al. (
2005
)
Large airport configuration
Dre
30-90
Drezner et al. (
2005
)
Known optimum
Tho
30-150
Thonemann and Bölte (
1994
)
Sko
42-100
Skorin-Kapov (
1990
)
BL,CI
36-144
de Carvalho Jr and Rahmann (
2006
)
Non-symmetric weights
the weights as c
ij
D
c
ij
C
c
ji
and the problem becomes symmetric with double the
value of the objective function. Symmetric problems can be solved in about half the
time because most of the calculations are not replicated twice unnecessarily.
The best known solutions to some of the bigger problems are listed in Table
13.2
.
The results for the Sko and Tho problems are taken from Drezner (
2008a
)andthe
results for the other problems are taken from Drezner and Misevicius (
2013
).
The best known solution values for the grey pattern problems for n
D
256
and 3
m
128 are available in Drezner (
2006
,
2008b
), Misevicius (
2011
)
and reported in Table
13.3
.Form > 128 the solution is obtained by exchanging
between the locations of black and white points. The results for 3
m
8 are
proven optimal in Drezner (
2006
). The original Tai256c (Taillard
1995
)isdefined
for m
D
92.Misevicius (
2011
) also reports the best known solutions for various
value of m for the n
D
64 grey pattern problems and Misevicius et al. (
2013
)define
the largest QAP test problems using a grey pattern with n
D
1024 points and report
the best known solutions for these problems up to m
D
512.
Two pictorial solutions to the grey pattern problems reported in Drezner et al.
(
2014
) illustrate the grey pattern results. First we present in Fig.
13.1
the optimal
configuration of locating 20 black points in a square of dimensions 8
8 replicated
9 times. This problem was optimally solved in Drezner et al. (
2014
)inlessthan
six and a half hours. The configuration shows groups of 5 points in a “V” shape
alternating up and down. The other (heuristic, but probably optimal) solution found
in a few papers is for locating 64 black points in a 16
16 square. The pattern is
depicted in Fig.
13.2
. It is interesting that this pattern is very close to an hexagonal
pattern that is known to be the densest packing, see Coxeter (
1973
) and Hilbert
an
d
Cohn-Vossen (
1956
). The distance to the four points in a diagonal direction is
p
5
D
2:236 while the distance to the two points on the left and on the right is 2. In
a hexagonal pattern these six distances are the same and therefore this pattern can
be viewed as “hexagonal-like”. The hexagonal pattern is also preferred to a square
pattern for a large number of points in many location problems (Drezner and Suzuki
2010
; Drezner and Zemel
1992
; Okabe and Suzuki
1987
; Suzuki and Drezner
1996
;
Suzuki and Okabe
1995
; Szabo et al.
2007
).
