In this paper, a new location analysis method is
presented. Given a connected graph $G=(V,E)$ with nonnegative
edge cost $c_e$ for each edge $e\in E$, $d_{ij}$ is the cost of
the shortest path between vertices $i$ and $j$ in the graph. The
{\em Connected p-facility Location Problem} (CpLP) is to choose
$p$ vertices from $V$ so as to minimize the total cost of shortest
path of pair-wise of these $p$ vertices. This problem is proved to
be NP-hard and non-linear integer programming is formulated. Then,
two algorithms are designed for solving the CpLP. One is a
heuristic algorithm based on classical maximum clique approach,
while the second one is genetic algorithm.
Finally, computational results show the comparison between these two algorithms.