A multi-objective perspective on the cable-trench problem

Lara Löhken () and Michael Stiglmayr ()
Additional contact information
Lara Löhken: University of Wuppertal
Michael Stiglmayr: University of Wuppertal

Journal of Combinatorial Optimization, 2025, vol. 49, issue 4, No 2, 29 pages

Abstract: Abstract 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.

Keywords: Multi-objective optimization; Combinatorial optimization; Minimum spanning tree; Shortest paths; Network flow problem; 65K05; 90C29; 90C35; 90C27 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01289-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01289-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01289-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().