HEURÍSTICAS PARA O PROBLEMA DAS P-MEDIANAS CONECTADAS / HEURISTICS FOR THE CONNECTED P-MEDIAN PROBLEM

AUTOR(ES)

CARLOS EDUARDO COSTA VIEIRA

DATA DE PUBLICAÇÃO

2006

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.

ASSUNTO(S)

meta-heuristics otimizacao combinatoria meta-heuristicas heuristics heuristica combinatorial optimization

Documentos Relacionados

• ALGORITMOS PRIMAIS E DUAIS PARA O PROBLEMA DAS P-MEDIANAS
• Um algoritmo exato para problemas das P-medianas
• Resolução do problema das p-medianas não capacitado: comparação de algumas técnicas heurísticas
• Abordagens complementares para problemas de p-medianas
• A branch-and-price method for p-median location problems