PRODUÇÃO ACADÊMICA Repositório Acadêmico da Graduação (RAG) TCC Ciência da Computação
Use este identificador para citar ou linkar para este item: https://repositorio.pucgoias.edu.br/jspui/handle/123456789/3736
Tipo: Trabalho de Conclusão de Curso
Título: Heurísticas para o problema leasing k-median
Autor(es): dos Santos, Jorge
Primeiro Orientador: Riabeiro, Alexandre
metadata.dc.contributor.referee1: Centeno, Carmen
metadata.dc.contributor.referee2: Oliveira, Max Gontijo de
Resumo: Neste trabalho de conclusão de curso foi abordada uma generalização do problema k-median, chamada leasing k-median. Nessa generalização são dados um conjunto de instantes de tempo, um conjunto de clientes que precisam ser atendidos para cada instante de tempo, um conjunto de pontos onde podem ser abertas facilidades para atender os clientes, as possíveis durações para a abertura de uma facilidade e uma constante k. O objetivo do problema é determinar quais, quando e por quanto tempo as facilidades devem ser abertas para minimizar os custos de atender os clientes, respeitando uma restrição de que no máximo k facilidades podem estar abertas ao mesmo tempo. Ao longo do trabalho foram propostos uma formulação de programação linear inteira e dois algoritmos heurísticos baseados nas meta-heurísticas BRKGA e VNS. A formulação de programação linear foi utilizada junto a um resolvedor comercial como um benchmark para os experimentos computacionais. Os experimentos consistiram em executar cada uma das abordagens por 10 minutos e considerar a melhor solução obtida nesse prazo para um conjunto de instâncias pseudoaleatórias. O resolvedor mostrou-se bastante útil na resolução de instâncias pequenas, encontrando, durante os testes, soluções ótimas para todas as instâncias desse tipo em menos de 30 segundos. O BRKGA apresentou em média um gap de otimalidade de 7,08% entre um limite inferior do valor ótimo e o valor da solução incumbente encontrada pela heurística. O VNS mostrou-se, dentre as três abordagens, como a melhor opção para as instâncias de médio e de grande portes obtendo em média gaps de otimalidade, respectivamente, de 2,08% e 5,70% entre o valor da solução incumbente e um limite inferior do valor ótimo.
Abstract: In this term paper a generalization of the k-median problem, known as leasing k-median problem, was studied. For this generalization are given a set of time instants, sets of customers that need to be served at each time instant, a set of points where facilities can be opened to serve customers, the possible durations for a facility opening and a constant value k. The objective of the problem is to determine which, when and for how long the facilities should be opened to minimize the costs of serving the customers, while respecting a rescriction that at most k facilities may be open at the same time. Throughout the work, an integer linear programming formulation and two heuristics based on the BRKGA and VNS metaheuristics were proposed. The linear programming formulation was used with a commercial solver as a benchmark for the computational experiments. The experiments were performed by running each approach for 10 minutes and considering the best solution obtained within that timeframe for a set of random instances. The solver was very useful in resolving small instances, finding, during the test phase, an optimal solution for all instances of this type in less than 30 seconds. The BRKGA presented an average optimality gap of 7.08% between a lower bound of the optimal value and the value of the incumbent solution found by the heuristic. Among the three approaches, the VNS was the best option for medium and large-sized instances, obtaining, on average, optimal gaps, respectively, of 2.08% and 5.70% between the value of the incumbent solution and a lower bound of the optimal value.
Palavras-chave: Problema leasing k-median
Localização de facilidades
Heurísticas
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
Idioma: por
País: Brasil
Editor: Pontifícia Universidade Católica de Goiás
Sigla da Instituição: PUC Goiás
metadata.dc.publisher.department: Escola Politécnica
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.pucgoias.edu.br/jspui/handle/123456789/3736
Data do documento: 5-Dez-2019
Aparece nas coleções:TCC Ciência da Computação

Arquivos associados a este item:
Arquivo TamanhoFormato 
Heurísticas para o Problema Leasing k-Median.pdf2,34 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.

Ferramentas do administrador