Ranking multiobjective shortest paths

• Author(s): Martins, Ernesto Queirós ; Paixão, José Manuel ; Rosa, Mário Silva ; Santos, José Luis
• Date: 2007
• Persistent ID: http://hdl.handle.net/10316/11301
• Origin: Estudo Geral - Universidade de Coimbra
• Subject(s): Multiple objective programming; Combinatorial optimization; Ranking algorithm; Total order; Non-dominated path
• Document Type: Preprint
• Language: English

Description

This paper is concerned with the ranking of multi-objective shortest paths accordingly to an order relation verifying certain conditions such is the case, for instance, of the lexicographic order. We present a new labelling algorithm that makes use of shortest deviation paths for obtaining the set of Pareto solutions for the multi-objective shortest path problem. The computational experience reported at the end of the paper shows that the new algorithm clearly outperforms the previous approaches when one looks for the `-th shortest non-dominated paths. FCT, POCTI - Research Units Pluriannual Funding to Centro de Matemática da Universidade de Coimbra, CIO (Operations Research Center of the University of Lisbon); POCTI/MAT/139/2001 cofunded by the EU program FEDER.