Labelling methods for the general case of the multi-objective shortest path pro...

• Author(s): Paixão, José Manuel ; Santos, José Luis
• Date: 2007
• Persistent ID: http://hdl.handle.net/10316/11275
• Origin: Estudo Geral - Universidade de Coimbra
• Subject(s): Multiple objective programming; Combinatorial optimization; Shortest path problem; Labelling algorithm; Non-dominated path
• Document Type: Preprint
• Language: English

Description

This paper is devoted to the study of labelling techniques for solving the multi-objective shortest path problem (MSPP) which is an extension of the shortest path problem (SPP) resulting from considering simultaneously more than one cost function (criteria) for the arcs. The generalization of the well known SPP labelling algorithm for the multiobjective situation is studied in detail and several different versions are considered combining two labelling techniques (setting and correcting), with different data structures and ordering operators. The computational experience was carried out making use of a large and representative set of test problems, consisting of around 9000 instances, involving three types of network (random, complete and grid) and a reasonable range for the number of criteria. The computational results show that the labelling algorithm is able to solve large size instances of the MSPP, in a reasonable computing time. The computational experience reported in this paper is complemented by the results presented in a twin paper [22] showing that the label correcting technique proves to be the fastest procedure when the computation of the full set of non-dominated paths is required. FCT through POCTI - Research Units Pluriannual Funding to CMUC and CIO (Operations Research Center of the University of Lisbon), and grant POCTI/MAT/139/2001 cofunded by the EU program FEDER