Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/11275
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Paixão, José Manuel | - |
dc.contributor.author | Santos, José Luis | - |
dc.date.accessioned | 2009-09-01T13:06:15Z | - |
dc.date.available | 2009-09-01T13:06:15Z | - |
dc.date.issued | 2007 | - |
dc.identifier.citation | Pré-Publicações DMUC. 07-42 (2007) | en_US |
dc.identifier.uri | https://hdl.handle.net/10316/11275 | - |
dc.description.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. | en_US |
dc.description.sponsorship | 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 | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Centro de Matemática da Universidade de Coimbra | en_US |
dc.rights | openAccess | eng |
dc.subject | Multiple objective programming | en_US |
dc.subject | Combinatorial optimization | en_US |
dc.subject | Shortest path problem | en_US |
dc.subject | Labelling algorithm | en_US |
dc.subject | Non-dominated path | en_US |
dc.title | Labelling methods for the general case of the multi-objective shortest path problem - a computational study | en_US |
dc.type | preprint | en_US |
uc.controloAutoridade | Sim | - |
item.openairecristype | http://purl.org/coar/resource_type/c_816b | - |
item.openairetype | preprint | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
item.fulltext | Com Texto completo | - |
item.languageiso639-1 | en | - |
crisitem.author.dept | Faculty of Sciences and Technology | - |
crisitem.author.parentdept | University of Coimbra | - |
crisitem.author.researchunit | CMUC - Centre for Mathematics of the University of Coimbra | - |
crisitem.author.orcid | 0000-0002-2727-6774 | - |
Appears in Collections: | FCTUC Matemática - Vários |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Labelling methods for the general case of the multi-objective.pdf | 200.87 kB | Adobe PDF | View/Open |
Page view(s) 50
396
checked on Apr 23, 2024
Download(s)
204
checked on Apr 23, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.