Geoscience Reference
In-Depth Information
It is interesting to note that an important step toward the development of
discrete facility location problems was taken in the same year when Balinski (
1965
)
proposed the first mixed-integer linear programming (MILP) formulation for a
discrete problem which also became classical in Location Science: the uncapacitated
facility location problem (UFLP). Some inequalities proposed in this work were
later used by ReVelle and Swain (
1970
) who formulated the first MILP model for
the discrete p-median problem. One year later, Toregas et al. (
1971
) introduced the
first integer programming formulation for a covering-location problem.
By the early 1970s, the foundations were laid for what would soon become a
very active research field. The recent topic by Eiselt and Marianov (
2011
) describes
the works that can be considered to constitute the basis of Location Science.
In the past 40 years, significant advances have been made in several areas of
Location Science, which is attested by several review papers, such as those by
Brandeau and Chiu (
1989
), ReVelle and Laporte (
1996
), Avella et al. (
1998
), Hale
and Moberg (
2003
), ReVelle and Eiselt (
2005
), ReVelle et al. (
2008
), and Smith
et al. (
2009
).
Initially, the major concern of the researchers had to do with theoretical develop-
ments and properties of the problems and their solutions. Much work was developed
on continuous and network location problems as well as on fundamental discrete
facility location problems. Further links were created with other areas. For instance,
the developments in continuous location problems led to the important connection
between location analysis and computational geometry. This link remains quite
strong to this day. In fact, one of the most relevant structures in computational
geometry, the Voronoi diagram [after Georgy Feodosevich Voronoy (1868-1908)],
is of major importance in the resolution of many continuous location problems (see,
for instance, the review by Okabe and Suzuki
1997
).
Nowadays, location problems can still be categorized according to the location
space (continuous, network or discrete), but also according to their context, namely
the objectives, constraints or type of facilities involved. Eiselt and Marianov (
2011
)
highlight the three major forms of facility location problems according to the type
of objective function: minsum, covering and minmax. For some time, it was also
popular to distinguish between public, semi-public and private facility location.
Location Science is highly interconnected with other disciplines and has appli-
cation in many areas. The theoretical foundations of this area lie in mathematics,
economics, geography and computer science. The developments we have observed
touch each of these areas.
More recently, stimulated by real-world problems, many areas have emerged
where facility location has been applied with great success. Among these, we can
point out logistics (see, for instance, Melo et al.
2006
, for a problem in the context
of logistics network design), telecommunications (see, for instance, Gollowitzer and
Ljubic
2011
, for a telecommunications network design problem), routing (e.g., in
the truck and trailer routing problem introduced by Chao
2002
, the location of the
