Título: | HEURISTICS FOR THE CONNECTED P-MEDIAN PROBLEM | ||||||||||||||||||||||||||||||||||||||||||||
Autor: |
CARLOS EDUARDO COSTA VIEIRA |
||||||||||||||||||||||||||||||||||||||||||||
Colaborador(es): |
CELSO DA CRUZ CARNEIRO RIBEIRO - Orientador |
||||||||||||||||||||||||||||||||||||||||||||
Catalogação: | 28/MAR/2007 | Língua(s): | PORTUGUESE - BRAZIL |
||||||||||||||||||||||||||||||||||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||||||||||||||||||||||||||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||||||||||||||||||||||||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=9711&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=9711&idi=2 |
||||||||||||||||||||||||||||||||||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.9711 | ||||||||||||||||||||||||||||||||||||||||||||
Resumo: | |||||||||||||||||||||||||||||||||||||||||||||
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.
|
|||||||||||||||||||||||||||||||||||||||||||||
|