Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/11246
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Paixão, José Manuel | - |
dc.contributor.author | Santos, José Luis | - |
dc.date.accessioned | 2009-08-28T13:37:19Z | - |
dc.date.available | 2009-08-28T13:37:19Z | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | Pré-Publicações DMUC. 08-27 (2008) | en_US |
dc.identifier.uri | https://hdl.handle.net/10316/11246 | - |
dc.description.abstract | In 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.sponsorship | FCT 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.language.iso | eng | en_US |
dc.publisher | Centro de Matemática da Universidade de Coimbra | en_US |
dc.rights | openAccess | eng |
dc.subject | Multiple objective programming | en_US |
dc.subject | Combinatorial optimization | en_US |
dc.subject | Shortest path problem | en_US |
dc.subject | Ranking algorithm | en_US |
dc.subject | Labelling algorithm | en_US |
dc.subject | Non-dominated path | en_US |
dc.title | A new ranking path algorithm for the multi-objective shortest path problem | en_US |
dc.type | preprint | en_US |
uc.controloAutoridade | Sim | - |
item.fulltext | Com Texto completo | - |
item.openairecristype | http://purl.org/coar/resource_type/c_816b | - |
item.languageiso639-1 | en | - |
item.openairetype | preprint | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
crisitem.author.dept | Faculty of Sciences and Technology | - |
crisitem.author.parentdept | University of Coimbra | - |
crisitem.author.researchunit | CMUC - Centre for Mathematics of the University of Coimbra | - |
crisitem.author.orcid | 0000-0002-2727-6774 | - |
Appears in Collections: | FCTUC Matemática - Vários |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A new ranking path algorithm for the multi-objective.pdf | 161.06 kB | Adobe PDF | View/Open |
Page view(s) 50
394
checked on Oct 15, 2024
Download(s)
89
checked on Oct 15, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.