Information Technology Reference
In-Depth Information
algorithms on the instances of Class 1 (http://webpages.ull.es/users/jriera/
TPP.htm) defined by Singh and van Oudheusden [18]. This class contains 33-
market symmetric instances and the product prices are generated according to a
uniform distribution in an interval of [1,500]. The routing costs are taken of the
33-vertex TSP described in Karg and Thompson [11] and the first vertex corre-
sponds to the depot. All markets sell all products and the quantity of products
varies between 50 and 500. The algorithms runs were aborted after a number of
15000 iterations for every instance.
25 instances with 50 to 250 products have been solved to optimality (note
that the optimal values for these instances are also provided at the webpage
mentioned above). Table 1 compares the results of the sLAHC and the LAHC
algorithm to these optimal values. Optimal values for the instances with 300 to
500 products have not yet been presented. In Table 2 we provide the objective
function values for 25 instances out of this range with a number of products from
300 up to 500. The results show, that both algorithms achieve optimal results
or small optimality gaps for almost all tested instances and outperform known
results from literature (see Table 3). Especially for small instances the sLAHC
algorithm seems to perform better than the LAHC algorithm. The LAHC tends
to get stuck in a local optimum quickly for those instances. The sLAHC, in
contrast, has a lower risk to stay early at a local optimum but seems to be
weaker for larger instances. For small instances the LAHC fitness array seems
to guide the LAHC algorithm to local optima while the sLAHC can come closer
to the global optimum without the guidance of a LAHC fitness array. For large
instances this disadvantage seems to turn into an advantage and the LAHC seems
benefit from the LAHC mechanism. The sLAHC achieves optimal solutions for
all five instances with 50 products and performs more homogenously over all
instances without any spikes. Note that the results in Table 1 were created with
a single batch run. For small instances the LAHC results highly depend on the
initial feasible solution, which were generated randomly. Thus exceptionally large
optimality gaps might occur. The average gaps are usually much lower like, e.g.,
for instance 3 another run led to a 0% instead of a 14% optimality gap.
The column headings in the tables are described as follows:
sLAHC
:
simplified Late Acceptance Hill Climbing;
LAHC
5000
:
Late Acceptance Hill Climbing with
L
fa
= 5000;
LAHC
10000
:
Late Acceptance Hill Climbing with
L
fa
= 10000;
V
:
um r f m ;
K
:
number of products;
V
∗
:
number of markets involved in the best solution;
V
LA
:
number of markets involved the best solution of the LAHC;
%
gap
:
quality of the LAHC over an optimal solution;
Furthermore, we compare different list lengths of the LAHC fitness array. No
variation of the list length is presented for the sLAHC algorithm as it could
be seen throughout the experiments that a variation of the list length has no
