Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/11246
Title: A new ranking path algorithm for the multi-objective shortest path problem
Authors: Paixão, José Manuel 
Santos, José Luis 
Keywords: Multiple objective programming; Combinatorial optimization; Shortest path problem; Ranking algorithm; Labelling algorithm; Non-dominated path
Issue Date: 2008
Publisher: Centro de Matemática da Universidade de Coimbra
Citation: Pré-Publicações DMUC. 08-27 (2008)
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.
URI: http://hdl.handle.net/10316/11246
Rights: openAccess
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 full item record

Page view(s) 50

218
checked on May 22, 2019

Download(s)

22
checked on May 22, 2019

Google ScholarTM

Check


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