Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.authorPaixão, José Manuel-
dc.contributor.authorSantos, José Luis-
dc.identifier.citationPré-Publicações DMUC. 08-27 (2008)en_US
dc.description.abstractIn this paper, we present a new algorithm for solving the multi-objective shortest path problem (MSPP) which consists of finding all the non-dominated paths between two nodes s and t (ND s-t paths), on a network where a multiple criteria function is defined over the set of arcs. The main feature of the algorithm is that, contrarily to the previous most efficient approaches for the MSPP, not all of the ND sub-paths on the network need to be found. Additionally, the algorithm fully exploits the fact that ND s-t paths are generated at a very early stage of the ranking procedure. The computational experience reported in the paper shows that, for large size general type networks, the new algorithm clearly outperforms the labelling approach.en_US
dc.description.sponsorshipFCT POCTI - Research Units Pluriannual Funding to CMUC (Centro de Matemática da Universidade de Coimbra) and CIO (Operations Research Center of the University of Lisbon), and grant POCTI/MAT/139/2001 cofunded by the EU program FEDER.en_US
dc.publisherCentro de Matemática da Universidade de Coimbraen_US
dc.subjectMultiple objective programmingen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectShortest path problemen_US
dc.subjectRanking algorithmen_US
dc.subjectLabelling algorithmen_US
dc.subjectNon-dominated pathen_US
dc.titleA new ranking path algorithm for the multi-objective shortest path problemen_US
item.fulltextCom Texto completo-
item.languageiso639-1en- of Sciences and Technology- of Coimbra- - Centre for Mathematics of the University of Coimbra-
Appears in Collections:FCTUC Matemática - Vários
Files in This Item:
File Description SizeFormat
A new ranking path algorithm for the multi-objective.pdf161.06 kBAdobe PDFView/Open
Show simple item record

Page view(s) 50

checked on Sep 16, 2022


checked on Sep 16, 2022

Google ScholarTM


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