An exact lexicographic approach for the maximally risk-disjoint/minimal cost path pair problem in telecommunication networks

Marta Pascoal (), José Craveirinha () and João Clímaco ()
Additional contact information
Marta Pascoal: University of Coimbra, CMUC
José Craveirinha: Universidade de Coimbra
João Clímaco: Universidade de Coimbra

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2022, vol. 30, issue 2, No 8, 405-425

Abstract: Abstract The paper addresses the lexicographically maximal risk-disjoint/minimal cost path pair problem that aims at finding a pair of paths between two given nodes, which is the shortest (in terms of cost) among those that have the fewest risks in common. This problem is of particular importance in telecommunication network design, namely concerning resilient routing models where both a primary and a backup path have to be calculated to minimize the risk of failure of a connection between origin and terminal nodes, in case of failure along the primary path and where bandwidth routing costs should also be minimized. An exact combinatorial algorithm is proposed for solving this problem which combines a path ranking method and a path labelling algorithm. Also an integer linear programming (ILP) formulation is shown for comparison purposes. After a theoretical justification of the algorithm foundations, this is described and tested, together with the ILP procedure, for a set of reference networks in telecommunications, considering randomly generated risks, associated with Shared Risk Link Groups (SRLGs) and arc costs. Both methods were capable of solving the problem instances in relatively short times and, in general, the proposed algorithm was clearly faster than the ILP formulation excepting for the networks with the greatest dimension and connectivity.

Keywords: Lexicographic shortest paths; Ranking; Pairs of paths; Telecommunication network design; Resilient routing models; 90C27; 90C35; 90C29 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-021-00619-9 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:topjnl:v:30:y:2022:i:2:d:10.1007_s11750-021-00619-9

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-021-00619-9

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().