Answers are grounded in this paper and cite their sources.
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 introduce the bi-objective cable-trench problem which separates 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. To determine the set of non-dominated points and efficient solutions, we use ε ε -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.
No takes yet. Share an insight, caveat, or question.
Löhken et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: