Título
[en] HEURISTICS FOR THE CONNECTED P-MEDIAN PROBLEM
Título
[pt] HEURÍSTICAS PARA O PROBLEMA DAS P-MEDIANAS CONECTADAS
Autor
[pt] CARLOS EDUARDO COSTA VIEIRA
Vocabulário
[pt] OTIMIZACAO COMBINATORIA
Vocabulário
[pt] META-HEURISTICA
Vocabulário
[pt] HEURISTICA
Vocabulário
[en] COMBINATORIAL OPTIMIZATION
Vocabulário
[en] META-HEURISTICS
Vocabulário
[en] HEURISTICS
Resumo
[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.
Resumo
[en] In this work, the connected p-median and the connected
facility location problems are defined. Applications arise
in regional planning, design of telecommunications and
transportation networks. For the first problem,
two integer linear programming formulations are proposed.
Adaptations are made in one of these formulations and are
used to model the second problem. Approximation algorithms
to solve the connected p-median problem are developed. A
hybrid local search strategy is proposed. In order to speed
up the local search iterations, ideas as circularity, first-
improving strategy and discard neighbors are incorporated.
A GRASP algorithm and a VNS heuristic are also proposed. A
filter is used to reduce the computational time required
and a path-relinking is applied to improve the results
found. Computational experiments to compare the algorithms
are reported. To improve these results, it is applied a
post-optimization step to the GRASP and VNS heuristics.
Orientador(es)
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
SERGIO LIFSCHITZ
Banca
SIMONE LIMA MARTINS
Banca
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
LUIZ SATORU OCHI
Banca
MAURICIO CARDOSO DE SOUZA
Banca
PAULO OSWALDO BOAVENTURA NETTO
Catalogação
2007-03-28
Apresentação
2006-09-11
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9711@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9711@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.9711
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF