Geoscience Reference
In-Depth Information
11.2
Continuous Problems
One of the best-known facility location problems is the Weber problem: given a
set of weighted nodes in the Euclidean plane, where to locate a single facility
minimizing the weighted sum of the distances to the points? A multi-period
extension of this problem was first proposed by Wesolowsky (
1973
). A finite
planning horizon T , divided into several time periods, is assumed. In each period
t
2
T , a set of weighted nodes J
t
is considered. The goal is to find the optimal
location for the single facility in each period. When the facility changes from one
location to another (in consecutive periods), a relocation cost is paid. The conceptual
model proposed by Wesolowsky (
1973
) is the following:
c
tj
.x
t
;y
t
/
C
jT
X
tD2
Minimize
X
t2T
X
f
t
z
t
(11.1)
j2J
t
subject to
z
t
D
0 if d
t1;t
D
0; t
2
T
nf
1
g
(11.2)
z
t
2f
0;1
g
; t
2
T:
(11.3)
In this model, c
tj
.x
t
;y
t
/ represents the present value of the cost for shipping from a
facility located at .x
t
;y
t
/ to demand point j
2
J
t
in period t
2
T ; f
t
denotes the
cost for relocating the facility at the beginning of period t
2
T ; d
t1;t
is the distance
by which the facility is moved at the beginning of period t
2
T
nf
1
g
. All the costs are
assumed to be forecasted in advance and therefore known to the model. For tackling
this problem, Wesolowsky (
1973
) proposed an incomplete dynamic programming
algorithm. The stages are associated with the time periods, the states correspond to a
set of possible locations for the facility and the decisions correspond to the possible
changes in the location of the facility. The relevance of this work arises from the
fact that it represents the first attempt to extend the Weber problem to a multi-period
setting. Nevertheless, the first work addressing the location and relocation of a single
facility in the plane over a multi-period finite planning horizon is due to Ballou
(
1968
). The goal is to maximize the total profit generated by a distribution system
involving factories, markets and the single warehouse to be located and relocated.
In that paper, a restricted set of potential locations for the warehouse was defined
considering the optimal location for the facility in the different periods. This set then
defined the states for all periods, and (incomplete) dynamic programming was then
applied. The method was later converted into an exact one by Sweeney and Tatham
(
1976
) who extended the restricted set just mentioned. In fact, a set of potential
locations for the warehouse can be found in each time period, thus ensuring that the
optimal solution of the problem is not lost when dynamic programming is applied.
It is worth noting that the methodologies proposed by Ballou (
1968
) and Sweeney
and Tatham (
1976
) can be applied to problems defined in a discrete setting.
