Geoscience Reference
In-Depth Information
in which the backbone network is complete instead of a star, i.e., each pair of
concentrators is connected by a direct link.
20.3
The Connected Facility Location Problem
As stated in the introduction of this chapter, telecommunications companies are
currently trying to bring rapid and high-capacity fiber-optic technologies closer
to the customers (FFTx networks). Outdated copper twisted cable connections are
progressively replaced by fiber optic connections. The
Connected Facility Location
Problem
(ConFL) aims at optimizing the building cost for networks mixing the
two technologies by modeling them as
tree-star
networks: the core network, made
of fiber optic connections, has a tree topology and interconnects multiplexers that
switch traffic between fiber optic and copper connections. Each multiplexer is the
center of a star-network of copper connections to the customers.
20.3.1
Uncapacitated Model
ConFL is a generalization of both the facility location problem and the Steiner tree
problem. Formally, an undirected graph G
D
.V;E/ is given, with a set of potential
locations for the facilities I
V and a set of customer nodes J
V . An opening
cost f
i
0 is incurred for opening facility i
2
I, each edge e
2
E has a cost
c
e
0, and each customer j
2
J has a demand d
j
. The edge cost c
e
, for an edge
e linking a customer j to a facility i, represents the assignment cost for sending
the demand of customer j to facility i. We assume the amount of demand d
j
is
implicitly accounted for in the assignment costs. Nodes in S
WD
V
n
J are Steiner
nodes (i.e., optional nodes that can be used to reduce the cost of the solution but
do not necessarily have a facility open). This set includes the set of facilities (i.e.,
I
S). The cost c
e
of an edge between two Steiner nodes represents its installation
cost in the Steiner tree. When a facility node is used as pure Steiner node, no opening
cost is paid for it. Optionally, a root node r
2
I can be given (together with its fixed
location) that represents the connection to a higher order (e.g., backbone) network.
That root node corresponds to an open facility that is always included in the network.
A solution .F;T/ of ConFL is composed of a set of open facilities F
I,
such that each customer j
2
J is assigned to an open facility i.j/
2
F and the
open facilities are connected by a Steiner Tree T . An example of such a solution
is illustrated in Fig.
20.2
. Plain rounded nodes represent the customers, dashed
rounded nodes are the Steiner nodes, where no facility is opened, and losanges
are the opened facilities. The plain black node in the middle is the root node. The
objective is to minimize the sum of assignment, facility opening and Steiner tree
costs.
