Geoscience Reference
In-Depth Information
and is also consistent with practice. In air transportation, for example, it ensures
that a passenger will never have to change flights more than twice. In ground
transportation, it is convenient to restrict the number of hub facilities that each route
has to pass through so as to reduce handling and congestion at hubs and to provide
a form of performance guarantee. O/D paths are once more of the form .i;k;m;j/,
and thus, defining their flow cost as F ijkm .
Figure 12.1 b shows an example of a solution network of a HALP in which
different structures on O/D paths arise (dashed lines represent bridge arcs). The
path .5;8;2;3/is a four-hub path formed by the bridge arcs .5;8/, .2;3/ and the
hub arc .8;2/. The path .5;8;9;10/is a three-hub path containing the bridge arc
.5;8/, the hub arc .8;9/ and the access arc .9;10/.
12.2.2
Supermodular Properties
We next show how a general class of HLPs can be stated as the minimization of
a real-valued supermodular set function. This fundamental property, which is also
known for other types of classical facility location problems (p-median, uncapac-
itated and capacitated facility location), can be exploited to develop mathematical
formulations and solution algorithms with worst case bounds.
This class of HLPs, referred to as Supermodular Hub Location Problems
(SHLPs), considers Assumptions 1-4 and the additional assumption that limits O/D
paths to contain at most one hub arc. SHLPs consist of locating a set of at most
q hub arcs (q 1), that induce a set of at most p hub nodes (p 2), and of
determining the routing of commodity flows through the hub network, with the
objective of minimizing the total set-up and flow cost. We can state SHLPs as the
following combinatorial problem. Let U D N [ E be a finite set containing both the
set of nodes N and the set of edges E of G. For each non-empty subset .S;R/ U ,
where S E and R N,define
c.S;R/ D X
i
c i I g.S;R/ D X
e
g e I h.S;R/ D X
i;j
h ij .S/ D X
i;j
min
.k;m/
F ijkm ;
2
S
2
R
2
S
2
N
2
N
and
f.S;R/ D c.S;R/ C g.S;R/ C h.S;R/ D X
i2R
c i C X
e2S
g e C X
i;j2N
min
.k;m/2S
F ijkm ;
(12.1)
and f. ; / D 0. For nonempty sets of hub nodes R N and hub arcs S E,
c.S;R/ is the total set-up costs for setting hub nodes, g.S;R/ is the total set-up
cost of the hub arcs, and h.S;R/ is the total cost for routing the flows when the set
of hub arcs S is chosen. Thus, f.S;R/ is the objective function value associated
with the set of hub nodes R and the set of hub arcs S. Therefore, SHLPs can be
Search WWH ::




Custom Search