Please use this identifier to cite or link to this item:
Title: Labelling methods for the general case of the multi-objective shortest path problem - a computational study
Authors: Paixão, José Manuel 
Santos, José Luis 
Keywords: Multiple objective programming; Combinatorial optimization; Shortest path problem; Labelling algorithm; Non-dominated path
Issue Date: 2007
Publisher: Centro de Matemática da Universidade de Coimbra
Citation: Pré-Publicações DMUC. 07-42 (2007)
Abstract: 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.
Rights: openAccess
Appears in Collections:FCTUC Matemática - Vários

Files in This Item:
Show full item record

Page view(s) 50

checked on Mar 27, 2023


checked on Mar 27, 2023

Google ScholarTM


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