Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/48324
Title: | Efficient heuristics for determining node-disjoint path pairs visiting specified nodes | Authors: | Martins, Lúcia Gomes, Teresa Tipper, David |
Keywords: | resilient routing; visiting a given set of nodes; min-sum; heuristics; node-disjoint path pair; path-based formulation | Issue Date: | 2017 | Publisher: | Wiley | Citation: | L. Martins, T. Gomes, D. Tipper. ''Efficient heuristics for determining node-disjoint path pairs visiting specified nodes'', Networks, Volume 70, Issue 4, 2017, Pages 292-307. DOI: 10.1002/net.21778 | Project: | info:eu-repo/grantAgreement/FCT/5876/147388/PT | Serial title, monograph or event: | Networks | Volume: | 70 | Issue: | 4 | Abstract: | A new recursive heuristic is proposed to calculate a shortest simple path, from a source node to a destination node, that visits a specified set of nodes in a network. To provide survivability to failures along the path, the proposed heuristic is modified to ensure that the calculated path can be protected by a node-disjoint backup path. Additionally, the case when both paths in the disjoint path pair are required to visit specific sets of nodes is studied and effective heuristics are proposed. An evaluation of the solutions of the heuristics is conducted by comparing with results from an integer linear programming (ILP) formulation for each of the considered problems, and also with previous heuristics. The ILP solver may require a significant amount of time to obtain a solution, especially in large networks, which justifies the need for effective, computationally efficient heuristics for solving these problems. | Description: | Peer reviewed version of "Efficient heuristics for determining node-disjoint path pairs visiting specified nodes" | URI: | https://hdl.handle.net/10316/48324 | ISSN: | 0028-3045 1097-0037 |
DOI: | 10.1002/net.21778 | Rights: | embargoedAccess |
Appears in Collections: | I&D INESCC - Artigos em Revistas Internacionais FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Martins_Gomes_Tipper_Networks_2017_EstudoGeral.pdf | 1.25 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License