Problema multi-período da Árvore de Steiner com coleta de prêmios e com restrições de orçamento

Este trabalho apresenta um modelo de otimização cujo objetivo é identificar a expansão ótima da rede de gás para cidades atualmente não atendidas, mas que pertencem à área de operação de uma determinada companhia de distribuição local. O modelo maximiza o aumento potencial do lucro de uma empresa em um horizonte especificado pelo usuário, buscando vincular cidades vizinhas. O problema é definido como um problema multi-período da Árvore de Steiner com coleta de prêmios e com restrições de orçamento, uma vez que existem ganhos por vértice vinculado, custos nas arestas inseridas e limites para o orçamento da empresa por período. A formulação é de um programa linear inteiro em um modelo de grafo direcionado. Ela inclui a transformação de instâncias não-direcionadas em direcionadas e a criação de uma raiz artificial para a instância, se necessários. A técnica Branch-e-Cut é usada com cortes com base na separação de conjuntos de desigualdades violadas por um algoritmo de fluxo máximo. Instâncias de até 250 cidades são avaliadas de forma satisfatória com o modelo.