[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:9711 |
| Date | 28 March 2007 |
| Creators | CARLOS EDUARDO COSTA VIEIRA |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0033 seconds