Geoscience Reference
In-Depth Information
Nowadays, Multi-Objective Combinatorial Optimization (MOCO) (see Ehrgott
and Gandibleux
2000
; Ulungu and Teghem
1994
) provides an adequate framework
to tackle various types of discrete multicriteria problems as, for instance, the
p-Median Problem (p-MP). Within this emergent research area, several methods
are known to handle different problems. It is worth noting that most of MOCO
problems are NP-hard and intractable (see Ehrgott and Gandibleux
2000
,for
further details). Even in most of the cases where the single objective problem
is polynomially solvable the multiobjective version becomes NP-hard. This is
the case of spanning tree problems and min-cost flow problems, among others.
In the case of the p-MP, the single objective version is already NP-hard. This
ensures that the multiobjective formulation is not solvable in polynomial time unless
P=NP. In this context, when time and efficiency become a real issue, different
alternatives can be used to approximate the Pareto-optimal set. One of them is
the use of general-purpose MOCO heuristics (Gandibleux et al.
2000
). Another
possibility is the design of “ad hoc” methods based on one of the following
strategies: (1) computing supported non-dominated solutions; and (2) performing
partial enumerations of the solutions space. Obviously, the second strategy does not
guarantee the non-dominated character of all the generated solutions although the
reduction in computation time can be remarkable.
The aim of this section is to present methods to obtain the Pareto-optimal set for
the multiobjective p-median problem (p-MP). In all cases, our approach to solve the
multicriteria p-MP takes advantage of the problem's structure. The first method is
exact and it determines the whole set of Pareto-optimal solutions based on new tools
borrowed from the theory of short rational generating functions. The second method
is an “ad hoc” approximate method that generates supported Pareto locations.
9.4.1
Model and Notation
Let I
Df
1;:::;M
g
and J
Df
1;:::;N
g
respectively denote the sets of indices
for demand points and for plants, and
Df
1;:::;Q
g
denote the set of indices
for the considered criteria. For each criterion q
2
Q
,let.c
ij
/
i2I;j2J
2
MN
be
the allocation costs of demand points to plants. The multicriteria p-median location
problem is:
Q
Q
0
1
X
M
X
N
X
M
X
N
@
c
ij
x
ij
A
c
ij
x
ij
;:::;
v-Minimize
(9.6)
iD1
jD1
iD1
jD1
N
X
subject to
x
ij
D
1; i
2
I;
(9.7)
jD1
x
ij
y
j
; i
2
I; j
2
J;
(9.8)
