O problema do caminho mais curto com restrições de capacidade

• Author(s): Almeida, Diana Xavier de
• Date: 2008
• Persistent ID: http://hdl.handle.net/10773/9497
• Origin: RIA - Repositório Institucional da Universidade de Aveiro
• Subject(s): Matemática aplicada; Problema do caixeiro viajante; Optimização combinatória
• Document Type: Master Thesis
• Language: Portuguese
• Advisor(s): Agra, Agostinho Miguel Mendes

Description

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. Mestrado em Matemática e Aplicações