Scholarlink

<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1289_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A multi-objective perspective on the cable-trench problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年4月26日

查看全文
  • Lara Löhken,
  • Michael Stiglmayr

摘要

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 \(\varepsilon \) ε -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.