Title:
|
UMA ABORDAGEM EXATA E META-HEURÍSTICAS
PARA O P-CABLE TRENCH PROBLEM WITH COVERING |
Author(s):
|
Ítalo Fernandes Gonçalves e Alexandre Ribeiro |
ISBN:
|
978-989-8704-25-2 |
Editors:
|
Paula Miranda, Cristiano Costa, Pedro Isaías e Flávia Maria Santoro |
Year:
|
2020 |
Edition:
|
Single |
Keywords:
|
Meta-heurísticas, Otimização combinatória, Programação linear inteira, Posicionamento de Servidores com Cobertura |
Type:
|
Full |
First Page:
|
55 |
Last Page:
|
62 |
Cover:
|
|
Full Contents:
|
click to dowload
|
Paper Abstract:
|
Neste trabalho é abordado o p-cable trench problem with covering (pCTPC), um problema de otimização combinatória
NP-completo, recentemente introduzido na literatura. Seu objetivo é minimizar o custo total da instalação de servidores
primários e servidores secundários a fim de satisfazer toda demanda de usuários de uma região. Os lugares onde,
exclusivamente, podem ser instalados os servidores são os nós da rede, que coincidem com as localidades dos usuários.
Tanto servidores primários quanto secundários distribuem os dados dentro de seu raio de cobertura, porém somente os
primários são fornecedores de dados. Dessa forma é necessário que cada servidor secundário seja conectado através de uma
conexão dedicada a um primário, evitando o compartilhamento da capacidade de transmissão de dados pelos cabos. Neste
trabalho é apresentado uma adaptação da formulação linear inteira do pCTPC, baseada em trabalhos da literatura
e propostas três abordagens, sendo a primeira uma abordagem heurística baseada no Biased random-key genetic algorithm
(BRKGA) e a segunda baseada no Variable neighborhood search (VNS) e a terceira uma solução exata com o resolvedor
de programação linear inteira GUROBI. O resolvedor encontrou o ótimo para todas instâncias e foi utilizado para
comparação e validação das abordagens heurísticas. As propostas demonstram ser competitivas e promissoras. |
|
|
|
|