Document details

Métodos aproximativos e exactos para o problema do caixeiro viajante múltiplo : um estudo computacional

Author(s): Mourão, Maria Cândida

Date: 1989

Persistent ID: http://hdl.handle.net/10400.5/13321

Origin: Repositório da UTL


Description

O problema do Caixeiro Viajante Múltiplo consiste na determinação das rotas óptimas a atribuir a dois ou mais caixeiros, que partindo todos de uma mesma cidade, a ela regressam no final da viagem. Todas as cidades, à excepção da inicial, são visitadas exactamente uma vez por um único caixeiro. Na presente tese são apresentados métcxios aproximativos e exactos para este problema. Após implementados, os diversos métodos foram analisados em termos das soluções que proporcionam. Com base nos resultados obtidos são tiradas algumas conclusões. Os valores das soluções óptimas de problemas Euclideanos, com um máximo de 30 vértices e 3 caixeiros, permitiram concluir que a heurística implementada revela interesse essencialmente teórico. Foi ainda possível observar, que o método de utilizado na determinação de minorantes proporcionou a obtenção de soluções de valores não muito afastados do valor óptimo do problema.

Mestrado em Estatística e Investigação Operacional

Document Type Master thesis
Language Portuguese
Advisor(s) Almeida, Maria Teresa Chaves de
Contributor(s) Mourão, Maria Cândida
facebook logo  linkedin logo  twitter logo 
mendeley logo

Related documents