  The cable-trench problem is defined as a linear combination of the shortest
path and the minimum spanning tree problem. In particular, the goal is to find
a spanning tree that simultaneously minimizes its total length and the total
path length from a pre-defined root to all other vertices. Both, the minimum
spanning tree and the shortest path problem are known to be efficiently
solvable. However, a linear combination of these two objectives results in a
highly complex problem.
  In this article we consider bi-objective cable-trench problem which
separating the two cost functions. We show that in general the bi-objective
formulation has additional compromise solutions compared to the cable-trench
problem in its original formulation. In order to determine the set of
non-dominated points and efficient solutions, we use epsilon-constraint
scalarizations in combination with a problem specific cutting plane. Moreover,
we present numerical results on different types of graphs analyzing the impact
of density and cost structure on the cardinality of the non-dominated set and
the solution time.
