Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/9497
Title: | O problema do caminho mais curto com restrições de capacidade |
Author: | Almeida, Diana Xavier de |
Advisor: | Agra, Agostinho Miguel Mendes |
Keywords: | Matemática aplicada Problema do caixeiro viajante Optimização combinatória |
Defense Date: | 2008 |
Publisher: | Universidade de Aveiro |
Abstract: | Neste trabalho estuda-se o problema do caminho mais curto com capacidades
(PCMCRC). O PCMCRC é uma variante do problema do caminho mais curto
onde existe uma restrição de capacidade associada aos arcos. Este problema
tem variadas aplicações, nomeadamente na área das telecomunicações e no
planeamento de rotas de veículos. Na sua forma geral o PCMCRC é NP-difícil.
É feita uma descrição do problema, uma breve referência às principais
técnicas de resolução e é proposto um novo algoritmo heurístico baseado na
relaxação da restrição de capacidade. É efectuado um estudo computacional
com o objectivo de identificar as instâncias mais difíceis do PCMCRC e,
também, de testar o novo algoritmo. This work studies the shortest path problem with capacities (SPPC). The SPPC is a variation of the shortest path problem, where there is a capacity constraint associated with the arcs. This problem has multiple applications in areas such as telecommunications and traffic routing planning. In it’s general form, it’s a NP-hard problem. It is made a description of the problem, a slight reference to the main resolution techniques, and it’s proposed a new heuristic algorithm, based on the relaxation of the capacity constraint. It is reported a computational study in order to identify the hard instances for the SPPC and in order to test the new algorithm. |
Description: | Mestrado em Matemática e Aplicações |
URI: | http://hdl.handle.net/10773/9497 |
Appears in Collections: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.