Information Technology Reference
In-Depth Information
Figure 1 visualizes the TPP. In this example we have a cycle through a subset
of the three markets, starting at the domicile and visiting markets 1 and 3.
Product 1 is purchased at market 1 and products 2 and 3 at market 3, shown
in boldface.
We assume that each product is available in at least one market and that the
purchaser may pass through a market any number of times without purchasing.
Or, he may purchase as many products as there are available at each market. A
capacitated version of the TPP assumes that the available quantities
q
ki
might be
insucient to satisfy the demand, i.e. it is assumed for each
k
∈
K
that
q
ki
and
V
k
)and
j∈V
i
q
kj
≥
d
k
satisfy 0
<q
ki
≤
d
k
[16]. Other modifications
of the TPP with additional capacity constraints, like a limit on the maximum
number of markets to be visited and a limit on the number of items bought per
market are also important [9].
The TPP is known to be NP-hard, since it reduces to the NP-hard TSP if each
product is only available at one market and each market carries only one product.
This complexity indicates that only problems of moderate size can be solved by
an exact method, a suggestion that is strengthened by the scarce number of
literature dealing with exact methods for the TPP. Exact algorithms proposed
in the literature include a branch-and-bound algorithm calculating a lower bound
by solving a relaxation similar to a simple plant location problem [18]. Branch-
and-cut procedures can be found in [12,17] being able to solve instances up to
200 markets and 200 products. An approach based on constraint programming
and Lagrangean relaxation is presented in [6] improving some of the earlier
approaches. Despite these contributions, the literature on the TPP is mostly
directed towards the development of heuristics and metaheuristics; see, e.g.,
[8,13,19,2]. This includes extensions of methods known from the TSP like the
famous nearest neighbor method (NN) [3]aswellasclassicaladdanddrop
procedures [21]. First metaheuristics for the TPP were proposed in [21] showing
that simulated annealing was outperformed by different dynamic tabu search
strategies. Other approaches also include tabu search [4], a local search algorithm
with two neighborhoods [16] and a transgenetic algorithm inspired by horizontal
gene transfer and endosymbiosis [7].
d
k
(
∀
i
∈
3 Late Acceptance Strategy
LAHC is based on a simple hill-climbing algorithm. The procedure starts from a
single initial solution and iteratively modifies it to produce candidate solutions.
The simple hill-climbing algorithm is a greedy procedure that is regarded to
be very fast but with poor results as it tends to get stuck in a local optimum
very quickly. To overcome this problem, the basic idea of LAHC is to delay the
comparison of solutions by “memorizing” previous current solutions in a list of a
particular length, called fitness array
F
a
of length
L
fa
(
F
a
=
f
0
,f
1
,...,f
L
fa−
1
}
with
f
a
denoting the cost function value of solution
a
. Contrary to pure hill-
climbing (note that LAHC with
L
fa
= 1 degenerates into pure hill-climbing)
LAHC compares a candidate not to its direct previous current solution but to
{
