Geoscience Reference
In-Depth Information
i and j and has a per unit flow cost of Ǜd
ij
. The parameter Ǜ.0
Ǜ
1/ is
used as a discount factor to provide reduced unit flow costs on hub arcs to reflect
economies of scale resulting from consolidation of flows between hubs. The per unit
flow cost between O/D pairs is given by the length of the path between the origin
and destination nodes in the solution network. Each O/D path has a
collection
leg
from the origin node to the first hub, possibly a
transfer
leg between the first and the
last hubs, and a
distribution
leg from the last hub to the destination node. A generic
hub location problem consists of locating a set of hub facilities and a set of hub arcs,
and of determining the routing of flows through the hub network, with the objective
of minimizing the total set-up and flow cost.
Most of the hub location literature has focused on
Hub Node Location Problems
(HNLPs), which consider the location of a set of hub facilities and the assignment
of O/D nodes to these facilities. Arc selection and routing decisions are usually
determined by the assumptions made on the cost structure and the assignment
pattern. The network induced by the solution of a HNLP consists of three types
of arcs:
(i) hub arcs
connecting two hubs,
(ii) access arcs
connecting non-hub
nodes and hubs, and
(iii) direct arcs
connecting two non-hub nodes. A more general
class of hub location models, known as
HubArcLocationProblems
(HALPs), have
received less attention in the literature. HALPs consider the location of a set of hub
arcs, that induce a set of hub nodes, and the assignment of O/D nodes to these hub
arcs. In HALPs, the possibility of connecting two hub nodes with a fourth type of
arc arises. A
bridge arc
is an arc that connects two different hub nodes, without
benefiting from the reduced unit flow cost of a hub arc. HNLPs can be seen as
particular cases of HALPs in which additional conditions are imposed.
There are four common assumptions underlying most HLPs:
1. Flows have to be routed via a set of hubs.
2. Access arcs and bridge arcs have no set-up cost.
3. The discount factor Ǜ is the same for all hub arcs and does not depend on the
amount of flow that is actually routed on each hub arc.
4. Distances d
ij
satisfy the triangle inequality.
A consequence of Assumption 1 is that direct connections between O/D nodes
which are not hubs are not allowed and thus, O/D paths must include at least one
hub node. In most HNLPs an additional fifth assumption stating that the set-up cost
of hub arcs is equal to zero (i.e., g
e
D
0 for each e
2
E) is also considered. This
allows hubs to be interconnected at no extra cost and, together with Assumptions 3
and 4, an important resulting property in solution networks of HNLPs is that the set
of hub arcs define a complete subgraph on the set of hub nodes (i.e. hubs are fully
interconnected). As a consequence, hub arc selection decisions become trivial once
the location of hub nodes is known. Another important property, obtained when
combining all assumptions, is that paths between O/D pairs will contain at least one
and at most two hubs. However, it is important to note that whenever Assumption 4
is not satisfied, paths may contain more than two hubs and more than one hub arc.
The above properties simplify the network design decisions and characterize
the structure of O/D paths. In HNLPs, all O/D paths include either a single hub
