Please use this identifier to cite or link to this item:
Title: On a relaxed maximally disjoint path pair problem: A bicriteria approach
Authors: Pascoal, Marta 
Clímaco, João 
Keywords: Bicriteria problems; pairs of paths; maximally disjoint labels; cost
Issue Date: 2020
Publisher: Wiley
Project: UID/MAT/00324/2019 
Serial title, monograph or event: International Transactions in Operational Research
Issue: 27
Abstract: In some application areas in telecommunication and transportation networks, there are problems requiring the determination of pairs of paths, aiming at minimizing the number of links, or link groups that they share, and their total cost. In this paper, a new bicriteria algorithm is proposed to deal with this problem. The algorithm is based on ranking pairs of paths by order of the total cost, using an adaptation of a path-ranking algorithm, after a suitable modification of the network topology. Nondominated solutions are then filtered by means of a dominance test. First, computational experiments are reported in order to assess the efficiency of the algorithm to calculate the whole set of nondominated pairs of paths. Second, we present computational results focused on the nondominated solutions close to the maximal disjoint pair (i.e., quasi-disjoint pairs only, for a predefined admissible relaxation value) because in some application problems, such as shared risk link group pairs of paths, only those solutions have practical relevance.
DOI: 10.1111/itor.12624
Rights: embargoedAccess
Appears in Collections:I&D INESCC - Artigos em Revistas Internacionais
I&D CMUC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
PascoalClimacoDec2018.pdf415.11 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Jun 10, 2021


checked on Jun 10, 2021

Google ScholarTM




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