Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Protected shortest path visiting specified nodes

Gomes, T and Marques, S and Martins, L and Pascoal, M and Tipper, D (2015) Protected shortest path visiting specified nodes. Proceedings of 2015 7th International Workshop on Reliable Networks Design and Modeling, RNDM 2015. 120 - 127.

[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)


In this paper heuristics are proposed for finding the shortest loopless path, from a source node to a target node, that visits a given set of nodes in a directed graph, such that it can be protected using a node-disjoint path. This type of problem may arise due to network management constraints. The problem of calculating the shortest path that visits a given set of nodes is at least as difficult as the traveling salesman problem, and it has not received much attention. Nevertheless an efficient integer linear programming (ILP) formulation has been recently proposed for this problem. Here, the ILP formulation is adapted to include the constraint that the obtained path will be able to be protected by a node-disjoint path. Computational experiments show that this approach, namely in large networks, may fail to obtain a solution in a reasonable amount of time. Therefore three versions of a heuristic are proposed, for which extensive computational results show that they are able to find a solution in most cases, and that the calculated solutions present an acceptable relative error regarding the cost of the optimal active path. Further the CPU time required by the heuristics is significantly smaller than the required by the used ILP solver.


Social Networking:
Share |


Item Type: Article
Status: Published
CreatorsEmailPitt UsernameORCID
Gomes, T
Marques, S
Martins, L
Pascoal, M
Tipper, Ddtipper@pitt.eduDTIPPER0000-0002-9429-6425
Date: 10 November 2015
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: Proceedings of 2015 7th International Workshop on Reliable Networks Design and Modeling, RNDM 2015
Page Range: 120 - 127
Event Type: Conference
DOI or Unique Handle: 10.1109/rndm.2015.7325218
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Telecommunications
Refereed: Yes
ISBN: 9781467380515
Date Deposited: 23 Nov 2015 15:12
Last Modified: 30 Mar 2021 13:56


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item