Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/11246
Título: | A new ranking path algorithm for the multi-objective shortest path problem | Autor: | Paixão, José Manuel Santos, José Luis |
Palavras-chave: | Multiple objective programming; Combinatorial optimization; Shortest path problem; Ranking algorithm; Labelling algorithm; Non-dominated path | Data: | 2008 | Editora: | Centro de Matemática da Universidade de Coimbra | Citação: | Pré-Publicações DMUC. 08-27 (2008) | Resumo: | 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. | URI: | https://hdl.handle.net/10316/11246 | Direitos: | openAccess |
Aparece nas coleções: | FCTUC Matemática - Vários |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
A new ranking path algorithm for the multi-objective.pdf | 161.06 kB | Adobe PDF | Ver/Abrir |
Visualizações de página 50
377
Visto em 23/abr/2024
Downloads
74
Visto em 23/abr/2024
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.