Information Technology Reference
In-Depth Information
The investigation of the properties of late acceptance strategies (LAS) is
still in an early stage. Consequently, only few contributions in literature deal
with LAS for heuristics and metaheuristics. Abuhamdah [1] proposed LAHC
and a randomized version for solving course timetabling problems. In that case
the randomized version performed better than the originally presented LAHC
of [5]. Ozcan et al. [14] presented a set of hyper-heuristics utilising different
heuristic selection methods combined with LAS for examination timetabling.
Verstichel and Berghe [20] applied LAS to a lock scheduling problem. Their
experiments showed that the application of the late acceptance criterion within
their local search heuristic led to an improvement of the solution quality in every
instance.
The remainder of this paper is organized as follows. In Section 2 we describe
the TPP in more detail. In Section 3 we explain LAHC and show how to possibly
apply it while using different neighborhoods. Finally, examples of computational
experiments are reported.
2 The Traveling Purchaser Problem
Consider a set
V
=
{
1
,
2
,...,m
}
of
m
markets, a set
K
=
{
1
,
2
,...,n
}
of
n
products and a domicile (or home-market)
s
V
)denote
the cost of travel from market
i
to market
j
. In the symmetric TPP it is assumed
that
c
ij
=
c
ji
∀
∈
V
.Let
c
ij
(with
i,j
∈
i,j
. Every product
k
(
k
∈
K
) is available in a subset of markets
V
k
⊆
) and if a product
k
is available at market
i
,
p
ik
presents the cost of
k
at
i
.Otherwise,
p
ik
is set to a prohibitively large number
M
.
It is implicitly assumed that if a product
k
is available at market
i
, its available
quantity
q
ki
is sucient to satisfy the demand
d
k
[15]. This model formulation
represents a symmetric uncapacitated version of the TPP. The overall idea of
the TPP is to generate a tour through a subset of the
m
markets starting and
ending at
s
, such that all
n
products are purchased while minimizing the sum of
travel and purchasing costs.
V
s
(with
V
s
:=
V
−{
s
}
Fig. 1.
Example of the TPP (cf. [21])
