Please use this identifier to cite or link to this item:
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"
ISSN: 0028-3045
DOI: 10.1002/net.21778
Rights: embargoedAccess
Appears in Collections:FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais
I&D INESCC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
Martins_Gomes_Tipper_Networks_2017_EstudoGeral.pdf1.25 MBAdobe PDFView/Open
Show full item record


checked on May 29, 2020

Citations 10

checked on Apr 2, 2021

Page view(s) 50

checked on Jun 10, 2021

Download(s) 50

checked on Jun 10, 2021

Google ScholarTM




This item is licensed under a Creative Commons License Creative Commons