Almeida, Maria Teresa Chaves deMourão, Maria Cândida2017-03-162017-03-161989-06Mourão, Maria Cândida (1989). "Métodos aproximativos e exactos para o problema do caixeiro viajante múltiplo : um estudo computacional". Dissertação de Mestrado, Universidade de Lisboa. Faculdade de Ciências.http://hdl.handle.net/10400.5/13321Mestrado em Estatística e Investigação OperacionalO 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.pormaster thesis