Ranking multiobjective shortest paths

• Autor(es): Martins, Ernesto Queirós ; Paixão, José Manuel ; Rosa, Mário Silva ; Santos, José Luis
• Data: 2007
• Identificador Persistente: http://hdl.handle.net/10316/11301
• Origem: Estudo Geral - Universidade de Coimbra
• Assunto(s): Multiple objective programming; Combinatorial optimization; Ranking algorithm; Total order; Non-dominated path
• Tipo de Documento: Preprint
• Idioma: Inglês

Descrição

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.