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.
	Go Back