Geoscience Reference
In-Depth Information
a reasonable limit, it has been impossible to address all relevant variants and
extensions of the problem. As a consequence, we have selected some topics which,
in our opinion, cover most of the major issues related to fixed-charge facility
location. Diversity among the selected topics has been a major guideline as well.
The material presented in this chapter is the result of the research carried out
by many authors in this area over the last 60 years. Most of it has been published
but occasionally we present and prove some unpublished results which are either
adaptations of well-known results for other cases, or simple results that can be easily
derived from the existing state of knowledge.
The remainder of this chapter is structured as follows. In Sect.
3.2
we introduce
our notation and we provide an overview of the problems we study. Section
3.2
also discusses modeling issues leading to standard formulations or to alternative Set
Partitioning formulations and properties of the domains. A sample of possible solu-
tion methods, namely Lagrangean relaxation and column generation is presented
in Sect.
3.3
. Some of the major difficulties of FLPs that will offer service to users
derive from the assumption that individual facilities do not have enough capacity to
satisfy the demand of all customers. Releasing this assumption yields a particular
FLP known as the Uncapacitated Facility Location Problem (UFLP), which is
studied in Sects.
3.4
and
3.5
. The UFLP satisfies some specific properties that do
not hold for general FLPs. These properties can be exploited for modeling purposes
or for deriving specific solution techniques. In particular, Sect.
3.4.1
studies some
properties derived from Linear Programming duality, whereas Sect.
3.4.2
presents a
formulation for the UFLP based on its supermodular property and relates it with the
so-called radius based formulations. Finally, Sect.
3.5
gives some polyhedral results
related to the UFLP. The chapter closes in Sect.
3.6
with some comments.
3.2
Overview and Modeling Issues
In this chapter we will use indistinctively the term service center when referring
to a facility, and customer or demand point when referring to a user. Let I
D
f
1;:::;i;:::;m
g
denote the index set for the potential locations for the facilities
and J
Df
1;:::;j;:::;n
g
the index set for the users. We will refer to potential
locations by their indices, so we will say that a facility is open at location i,or
simply that facility i is open, if the decision to establish a service center at the
potential location i is made. We will also denote users by their indices and simply
refer to user j. Associated with each i
2
I, q
i
denotes the maximum capacity of
facility i, if it is opened. The service demand of user j
2
J is denoted by d
j
.As
mentioned, there are two types of costs. The decision to establish a facility at i
2
I
incurs a fixed-charge (setup) cost f
i
.Fori
2
I and j
2
J, c
ij
is the cost for serving
all the demand of customer j from facility i.