Author(s): Mourão, Maria Cândida
Date: 1989
Persistent ID: http://hdl.handle.net/10400.5/13321
Origin: Repositório da UTL
Author(s): Mourão, Maria Cândida
Date: 1989
Persistent ID: http://hdl.handle.net/10400.5/13321
Origin: Repositório da UTL
Mestrado em Estatística e Investigação Operacional
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.