Geoscience Reference
In-Depth Information
stated as to find a set of arcs S
E of cardinality at most q.q
j
E
j
/ and R of
cardinality at most p.p
j
N
j
/ such that f.S;R/is minimum, i.e.,
min
.S;R/U
f
f.S;R/
Wj
S
j
q;
j
R
j
p; N.S/
D
R
g
;
(12.2)
where N.S/
D f
i
2
N
W
.i;j/
2
S or .j;i/
2
S
g
is the set of nodes incident with
some edge in S. In order to deal only with feasible problems, we assume that p
d
2
e
.Whenp
min
fj
N
j
;2q
g
the maximum cardinality constraint on the number
of hub nodes becomes redundant. Similarly, if q
min
fj
E
j
;
2
g
the maximum
cardinality constraint on the number of hub arcs becomes redundant. A fundamental
property of f is that, for .S;R/
.T;Q/ and e
2
E
n
T , adding e to T will decrease
f by no more than by adding e to S. A real-valued set function with such property
is called
supermodular set function
.
Proposition 12.1
a.
h.S;R/
D
P
i;j2N
h
ij
.S;R/
is supermodular and nonincreasing.
b.
f.S;R/
D
c.S;R/
C
g.S;R/
C
h.S;R/
is supermodular.
Problem (
12.2
) can thus be stated as the minimization of a supermodular set
function, which is known to be in the class of NP-hard problems. We use SHLP to
describe any problem that can be formulated as (
12.2
). SHLPs are a quite general
class of HLPs and include several special cases which are of particular interest
such as p-hub median, uncapacitated hub location, and q-hub arc location. Other
classical facility location problems, such as the p-median or the uncapacitated
facility location problem, are also relevant special cases of SHLPs. However, we
note that not every HLP can be stated as problem (
12.2
). For instance, when a
single assignment pattern is imposed the flow cost associated with a given set of
hub arcs S is no longer h.S;R/, since all flow with the same origin (destination)
must be routed through the same collection (transfer) leg. That is, HLPs with single
assignments cannot be formulated as SHLPs. Moreover, even if multiple allocation
is allowed, the addition of capacity constraints also preclude the supermodularity
property when commodities cannot be splitted.
12.2.3
Objectives
Most of the hub location research has focused on HLPs that consider either a cost-
based or a service-based objective. Transportation applications tend to focus on the
flow transportation costs and travel times, whereas telecommunication applications
focus more on the set-up costs of the hub network. Analogously to facility location,
HLPs can be classified based on the type of objective they use.
