Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/9497
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Agra, Agostinho Miguel Mendes | pt |
dc.contributor.author | Almeida, Diana Xavier de | pt |
dc.date.accessioned | 2013-01-17T11:08:50Z | - |
dc.date.available | 2013-01-17T11:08:50Z | - |
dc.date.issued | 2008 | - |
dc.identifier.uri | http://hdl.handle.net/10773/9497 | - |
dc.description | Mestrado em Matemática e Aplicações | pt |
dc.description.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. | pt |
dc.description.abstract | 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. | pt |
dc.language.iso | por | pt |
dc.publisher | Universidade de Aveiro | pt |
dc.rights | openAccess | por |
dc.subject | Matemática aplicada | pt |
dc.subject | Problema do caixeiro viajante | pt |
dc.subject | Optimização combinatória | pt |
dc.title | O problema do caminho mais curto com restrições de capacidade | pt |
dc.type | masterThesis | pt |
thesis.degree.level | mestrado | pt |
thesis.degree.grantor | Universidade de Aveiro | pt |
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.