[en] HEURISTICS FOR THE CONNECTED P-MEDIAN PROBLEM

• Ano de defesa: 2007
• Autor(a) principal: CARLOS EDUARDO COSTA VIEIRA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] OTIMIZACAO COMBINATORIA; [pt] META-HEURISTICA; [pt] HEURISTICA; [en] COMBINATORIAL OPTIMIZATION; [en] META-HEURISTICS; [en] HEURISTICS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9711&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9711&idi=2; http://doi.org/10.17771/PUCRio.acad.9711

[pt] Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas.