The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm

Tools

Ferone, Daniele, Festa, Paola, Fugaro, Serena and Pastore, Tommaso (2023) The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm. Networks, 81 (2). pp. 204-219. ISSN 0028-3045

[thumbnail of Networks - 2022 - Ferone - The resource constrained clustered shortest path tree problem Mathematical formulation and]
Preview
 PDF (Networks - 2022 - Ferone - The resource constrained clustered shortest path tree problem Mathematical formulation and) - Published Version
Available under License Creative Commons Attribution Non-commercial.
Download (1MB) | Preview

Abstract

In this article, the Resource Constrained Clustered Shortest Path Tree Problem is defined. It generalizes the classic Resource Constrained Shortest Path Tree Problem since it is defined on an undirected, complete and weighted graph whose set of nodes is partitioned into clusters. The aim is then to find a shortest path tree respecting some resource consumption constraints and inducing a connected subgraph within each cluster. The main support and motivation for studying this problem are related, among the others, to the design of telecommunication networks, and to Disaster Operations Management. In this work, we present a path-based formulation for the problem, addressing the case of local resource constraints, that is, resource constraints on single paths. For its resolution, a Branch&Price algorithm featuring a Column Generation approach with Multiple Pricing Scheme is devised. A comprehensive computational study is conducted, comparing the proposed method with the results achieved by the CPLEX solver, adopted to solve the mathematical model. The numerical results underline that the Branch&Price algorithm outperforms CPLEX, both in terms of solution cost and time.

Item Type: Article
Additional Information: Publisher Copyright: © 2022 The Authors. Networks published by Wiley Periodicals LLC.
Uncontrolled Keywords: branch&price,clustered graph,column generation,danzig wolfe,resource constrained paths,information systems,computer networks and communications ,/dk/atira/pure/subjectarea/asjc/1700/1710
Faculty \ School: Faculty of Social Sciences > Norwich Business School
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 12 May 2026 14:49
Last Modified: 12 May 2026 14:50
URI: https://ueaeprints.uea.ac.uk/id/eprint/102968
DOI: 10.1002/net.22124

Downloads

Downloads per month over past year

Actions (login required)

View Item View Item