Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/97138
DC FieldValueLanguage
dc.contributor.authorPascoal, Marta-
dc.contributor.authorCraveirinha, José-
dc.contributor.authorClímaco, João-
dc.date.accessioned2022-01-14T17:04:27Z-
dc.date.available2022-01-14T17:04:27Z-
dc.date.issued2021-09-14-
dc.identifier.urihttp://hdl.handle.net/10316/97138-
dc.description.abstractThe 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.pt
dc.language.isoengpt
dc.publisherSpringerpt
dc.relationUID/Multi/00308/2019pt
dc.relationCENTRO-01-0145-FEDER-029312pt
dc.relationCMUC-UIDB/00324/2020pt
dc.rightsopenAccesspt
dc.subjectLexicographic shortest pathspt
dc.subjectRankingpt
dc.subjectPairs of pathspt
dc.subjectTelecommunication network designpt
dc.titleAn exact lexicographic approach for the maximally risk-disjoint/minimal cost path pair problem in telecommunication networkspt
dc.typearticle-
degois.publication.titleTOP: An Official Journal of the Spanish Society of Statistics and Operations Researchpt
dc.relation.publisherversionhttps://link.springer.com/article/10.1007/s11750-021-00619-9pt
dc.peerreviewedyespt
dc.identifier.doihttps://doi.org/10.1007/s11750-021-00619-9pt
dc.date.embargo2021-09-14*
uc.date.periodoEmbargo0pt
item.fulltextCom Texto completo-
item.languageiso639-1en-
item.grantfulltextopen-
Appears in Collections:I&D INESCC - Artigos em Revistas Internacionais
Files in This Item:
File Description SizeFormat
PascoalEtAlEGeral2021.pdf364.51 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.