Doutorado em Modelagem Matemática e Computacional
URI Permanente para esta coleção
Navegar
Submissões Recentes
Item ECT: an offline metric to evaluate case-based explanations for recommender systems(Centro Federal de Educação Tecnológica de Minas Gerais, 2020-12-14) Costa, Lucas Gabriel Lage; Lacerda, Anísio Mendes; http://lattes.cnpq.br/2034607422210997; http://lattes.cnpq.br/3544005614853592; Lacerda, Anísio Mendes; Dalip, Daniel Hasan; Pereira, Adriano César Machado; Pádua, Flávio Luis CardealSistemas de recomendação sugerem itens que melhor atendem aos gostos e interesses dos usuários. Eles são sistemas complexos e, frequentemente, são baseados em modelos do tipo caixa preta. No entanto, sabe-se que entender as recomendações é essencial para ajudar a construir a confiança e o envolvimento do usuário nesses sistemas. Portanto, as explicações das recomendações são uma forma de atingir esse objetivo. Uma explicação é uma informação exibida aos usuários, detalhando as motivações de porque um determinado item foi recomendado. A explicação baseada em caso é um dos estilos de explicação mais comumente usados em sistemas de recomendação. Essa abordagem é focada em fornecer explicações na forma de itens que foram avaliados previamente, como, por exemplo, em: "Porque você gostou de A, recomendamos B". Para medir a qualidade dos métodos que geram explicações, podemos fazer avaliações online e offline. As avaliações online requerem interação direta com os usuários e as avaliações offline requerem apenas dados históricos, ou seja, extraídos anteriormente à recomendação e explicação. A avaliação online pode tratar mais aspectos das explicações e produzir resultados mais completos, por isso é incentivada, mas nem sempre os testes envolvendo usuários estão acessíveis. A avaliação offline é frequentemente adotada pois elimina riscos de apresentar explicações que podem afetar negativamente a experiência dos usuários, além de ser mais fácil de implementar. Poucos trabalhos na literatura abordam métricas offline para medir a qualidade dos métodos de explicação baseados em casos. Assim, este trabalho propõe cobrir esta demanda por meio de uma nova métrica offline – ECT (Ease-of-interpretation Coverage Triviality) – para avaliar aspectos mais complexos dos métodos de explicação baseados em casos. É composta por três submétricas, uma delas já existente (Coverage), e duas novas (Ease-of-interpretation e Triviality). Experimentos foram conduzidos em cenários offline e online para validar o poder discriminativo da métrica proposta ECT, e mostram que ela apresenta uma correlação de 0,67 com o que os usuários consideram boas explicações para suas recomendações.Item Geometria computacional aplicada à mecânica de materiais granulares(Centro Federal de Educação Tecnológica de Minas Gerais, 2020/08/06) Boaventura, Eduardo Célio; Faria, Allbens Atman Picardi; http://lattes.cnpq.br/4216801992845696; http://lattes.cnpq.br/2056632739639225; Faria, Allbens Atman Picardi; Morgado, Welles Martinez; Alves, Sidiney Geraldo; Magalhães, Arthur Rodrigo Bosco de; Mattos, Thiago Gomes deA geometria computacional é uma área de estudo intrinsecamente interdisciplinar, pois associa técnicas computacionais às propriedades geométricas de sistemas diversos. Neste trabalho aplicamos a tesselação de Voronoi, uma técnica de geometria computacional, para obtenção da pavimentação de sistemas granulares bidimensionais. Nosso objetivo é obter propriedades mecânicas a partir das propriedades geométricas da pavimentação do plano. Nesta tese aplicamos a metodologia em duas situações diferentes: 1) sistema dinâmico; 2) empilhamento quase estático de grãos. A partir da análise das propriedades da geometria dos polígonos obtidos realizamos uma comparação com as propriedades mecânicas do sistema em questão, buscando associar a evolução espácio-temporal da pavimentação à dinâmica do sistema granular. No sistema dinâmico, durante a penetração de um intruso em um material granular confinado, analisamos as mudanças nos polígonos da área da cavidade (espaço vazio atrás do intruso) e do número de lados do polígono gerado pelo intruso, obtendo indícios de uma transição de fase de engarrafamento. No empilhamento quase estático de grãos, utilizamos a tesselação de Voronoi para a obtenção da função resposta a tensões, a partir de um calibre, e fomos capazes de reproduzir os resultados mecânicos obtidos a partir das forças de contato, utilizando geometria computacional. O calibre é uma constante obtida na base da camada granular por meio da relação entre a função resposta a tensões e a função resposta à tesselação de Voronoi. Este protocolo nos permite calcular a função resposta a tensões em diferentes níveis da camada granular, sem a necessidade de se introduzir um sensor no bulk, ou seja, de uma forma não destrutiva e não invasiva.Item Design configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-06-24) Oliveira, Sabrina Moreira de; Souza, Sérgio Ricardo de; Wanner, Elizabeth Fialho; Bezerra, Leonardo César Teonácio; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/0664132257054306; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/9822253950704581; Souza, Sérgio Ricardo de; Wanner, Elizabeth Fialho; Bezerra, Leonardo César Teonácio; Marcelino, Carolina Gil; Stüzle, Thomas; Sá, Elisângela Martins de; Martins, Flávio Vinícius CruzeiroOs algoritmos Ant Colony Optimization (ACO) foram inicialmente desenvolvidos para problemas de otimização estática, em que os dados do problema são conhecidos a priori e não sofrem alterações durante a execução. No entanto, sua estrutura baseada em memória mostrou-se eficaz também em Problemas de Otimização Combinatória Dinâmicos (POCD), nos quais os dados podem mudar em tempo real, sem previsibilidade. A partir de uma revisão da literatura, identificaram-se adaptações para melhorar o desempenho do ACO em POCD, incluindo o algoritmo Population-Based ACO (P-ACO), projetado especificamente para essa classe de problemas. Embora o P-ACO tenha se destacado por seu processamento rápido, faltam estudos conclusivos sobre a eficácia dos métodos ACO em cenários dinâmicos. Neste trabalho, realiza-se uma extensiva campanha experimental para avaliar as principais versões do ACO aplicáveis a POCD: o MAX-MIN Ant System (MMAS) e o P-ACO. Utilizou-se como estudo de caso uma variação dinâmica do Problema do Caixeiro-Viajante (PCVDD), amplamente adotado na literatura. As principais contribuições incluem: (i) a proposta de um setup experimental pioneiro, com configuração automática de parâmetros para POCD; (ii) a introdução da métrica de hipervolume para avaliação de desempenho em horizontes temporais variáveis; e (iii) a comparação entre MMAS e P-ACO, demonstrando que o MMAS supera o P-ACO quando combinado com busca local, enquanto o inverso ocorre sem essa técnica. Os resultados também indicam que procedimentos adaptativos têm impacto significativo apenas quando a busca local é desativada.Item Tempos de primeira passagem para caminhadas aleatórias em redes complexas(Centro Federal de Educação Tecnológica de Minas Gerais, 2020/11/26) Chaves, Marcelo Sousa; Mattos, Thiago Gomes de; Faria, Allbens Atman Picardi; http://lattes.cnpq.br/4216801992845696; http://lattes.cnpq.br/9832733706852720; http://lattes.cnpq.br/3890234130921034; Mattos, Thiago Gomes de; Faria, Allbens Atman Picardi; Silva, Alcides Volpato Carneiro de Castro e; Oliveira, Marcelo Martins de; Fernandes, José Luiz AcebalA análise topológica de redes é um importante campo de estudo em Teoria das Redes, com aplicações em vários campos da Ciência. Neste estudo, nós alteramos a topologia de uma rede quadrada através de reconexões em suas arestas e obtivemos diferentes tipos de redes: aleatória conservativa, aleatória não conservativa e livre de escala. Sob determinadas condições, as redes aleatórias e livre de escala apresentaram propriedades de mundo pequeno. Aplicamos as ferramentas da análise de Primeira Passagem para investigar as propriedades e características das caminhadas aleatórias nessas redes. Nas topologias investigadas, analisamos o Tempo de Primeira Passagem (TPP) de um significativo número de caminhantes aleatórios não interagentes, variando-se os sítios de partida e de chegada. Para caracterizar estes processos, aplicamos o conceito da simultaneidade de Primeira Passagem, através do chamado Índice de Uniformidade (IU), que é uma medida da probabilidade de que dois caminhantes independentes cheguem juntos ao sítio alvo. O IU permite avaliar se o tempo médio de primeira passagem (TMPP) é uma boa medida para o processo, e permite identificar redes com características de mundo pequeno. A análise da ocupação dos sítios durante uma caminhada aleatória nos permitiu diferenciar os diferentes tipos de redes, em particular identificar as propriedades de mundo pequeno, um tema que ainda é controverso na literatura.Item Abordagem de sistemas complexos aplicada a problemas biologicamente motivados(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-05-13) Lima, Larissa Lopes; Faria, Allbens Atman Picardi; Guimarães, Andréia Rodrigues Marques; http://lattes.cnpq.br/4216801992845696; http://lattes.cnpq.br/9943818682025940; Faria, Allbens Atman Picardi; Guimarães, Andréia Rodrigues Marques; Morais, Maria Helena Franco; Andrade, Roberto Fernandes Silva; Mattos, Thiago Gomes; Wanner, Elizabeth FialhoO campo de estudo dos sistemas complexos está entrelaçado a muitas áreas da ciência e constitui uma abordagem promissora para a investigação de problemas biológicos. Neste trabalho, algumas ferramentas de sistemas complexos são usadas para estudar três problemas biológicos de grande preocupação atual: a pandemia de COVID-19, a ciclicidade dos surtos de dengue e o impacto das mudanças climáticas no banco de sementes de uma espécie invasora. No estudo de COVID-19, desenvolveu-se um modelo baseado em agentes para simular o espalhamento da doença e o efeito de indivíduos superespalhandores com diferentes cenários de mobilidade. Uma análise de redes foi aplicada para investigar o papel dos superespalhadores, mostrando que há indivíduos chave que interferem no processo de infecção. Ainda, foram feitas simulações para algumas capitais brasileiras usando redes, dados de mobilidade extraídos por telefones celulares e diferentes cenários de infecção. No caso do estudo de dengue, inicialmente foram aplicadas ferramentas de grafo de visibilidade e entropia para interpretar os dados de séries temporais da doença. Além disso, introduziu-se uma ferramenta denominada Histograma de Impacto-Frequência, gerada a partir dos grafos de visibilidade, a qual mostrou resultados melhores para o estudo da ciclicidade da dengue que a abordagem utilizando entropia. Em seguida, foi adaptado um modelo baseado em agentes para investigar a dinâmica de diferentes cenários de infecção por dengue. O resultado permitiu identificar humanos e mosquitos que possuem papel essencial nas redes. Por último, foi adaptado um modelo baseado em agentes para simular a dinâmica de um banco de sementes de uma espécie invasora sob diferentes cenários de mudanças climáticas. Os resultados dos três modelos podem auxiliar na tomada de decisão em diferentes âmbitos. No caso de COVID-19 e dengue, os modelos podem ser adaptados para diferentes cenários e doenças. O modelo de espécie invasora também pode ser adaptado para outras espécies e para auxiliar no manejo dessas espécies. Assim, a abordagem de sistemas complexos permitiu alcançar resultados inéditos no tratamento e análise de problemas biologicamente motivados, como a identificação de superespalhadores no espalhamento da COVID-19, ciclicidade em surtos epidêmicos da dengue e influência das mudanças climáticas no banco de sementes de espécies invasoras. Todos os estudos abordados neste trabalho são passíveis de continuidade, seja para os mesmos problemas ou para aplicações semelhantes.Item Modelagem matemática para o problema de elaboração de cardápios nutricionais(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-03-31) Moreira, Rafaela Priscila Cruz; Wanner, Elizabeth Fialho; Martins, Flávio Vinícius Cruzeiro; Sarubbi, João Fernando Machry; http://lattes.cnpq.br/3199420233273400; http://lattes.cnpq.br/2555714512247868; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/1207202817257723; Wanner, Elizabeth Fialho; Martins, Flávio Vinícius Cruzeiro; Cruz, André Rodrigues da; Vassimon, Helena Siqueira; Souza, Sérgio Ricardo de; Menezes, Gustavo CamposEsta tese aborda o Problema de Elaboração de Cardápios, apresentando dois modelos matemáticos para gerar cardápios escolares que atendam aos requisitos do Programa Nacional de Alimentação Escolar (PNAE). As duas modelagens têm como função objetivo minimizar o custo total do cardápio. Na primeira modelagem, deseja-se gerar cardápios para 5 dias e tem-se as seguintes restrições: composição; cor; consistência; variedade; limites mínimos e máximos de: carboidratos, lipídeos e proteínas e limites máximos de sódio e gordura saturada. Na segunda modelagem, deseja-se criar cardápios para 푛 dias e foram consideradas restrições relacionadas à: composição; variedade; limites nutricionais de nutrientes como: carboidratos, proteínas, lipídios, gordura saturada, sódio e açúcar adicionado; oferta mínima de: alimentos in natura ou minimamente processados, incluindo porções semanais de frutas, verduras e legumes; oferta mínima semanal de: vitamina A, alimentos com ferro heme e fontes de vitamina C quando há alimentos com ferro não-heme; limite máximo de: margarina, lácteos adoçados e produtos cárneos e por fim, combinação e rejeição de preparações. Os cardápios foram obtidos resolvendo os modelos matemáticos lineares propostos por meio de um pacote de software de programação matemática de alto desempenho (IBM CPLEX Optimizer). Os aspectos qualitativos dos cardápios obtidos foram avaliados por meio do IQ COSAN - Índice de Qualidade da Coordenação de Segurança Alimentar Nutricional. Os resultados mostraram que os cardápios, tanto da primeira modelagem, quanto da segunda estão adequados ao IQ COSAN e às recomendações do PNAE. Os custos foram adequados, tendo em conta o recurso financeiro disponibilizado para as escolas. Aspectos culturais do cardápio foram contabilizados por meio das comidas e preparações culinárias incluídas no programa. Os resultados mostraram que os cardápios gerados pelos modelos são viáveis e adequados quantitativa e qualitativamente para a elaboração de cardápio escolar. Esse estudo viabiliza e contribui para o cenário pandêmico de obesidade mundial, apresentando cardápios que introduzem hábitos alimentares saudáveis, bem como auxiliando o profissional responsável por elaborá-los.Item Redução de dimensionalidade online para problema de roteamento de veículos com transporte reativo a demanda(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-03-28) Mendes, Renan Santos; Wanner, Elizabeth Fialho; Martins, Flávio Vinícius Cruzeiro; Sarubbi, João Fernando Machry; http://lattes.cnpq.br/3199420233273400; http://lattes.cnpq.br/2555714512247868; http://lattes.cnpq.br/2243256075052322; http://lattes.cnpq.br/0567160950149386; Wanner, Elizabeth Fialho; Martins, Flávio Vinícius Cruzeiro; Sarubbi, João Fernando Machry; Meneghini, Ivan Reinaldo; Marcelino, Carolina Gil; Silva, Alisson Marques da; Menezes, Gustavo CamposNeste trabalho é abordada uma formulação com muitos objetivos para o Problema de Roteamento de Veículos com Transporte Reativo a Demanda (PRVTRD). O problema pode ser considerado como um modo de transporte aproximado ao dos serviços de transporte sob demanda com compartilhamento de corridas. Este trabalho propõe o uso da análise de cluster online baseada nos coeficientes de correlação de Pearson e τ de Kendall para realizar a redução de dimensionalidade a cada geração do algoritmo MOEA/D. Inicialmente, foram comparadas as seguintes abordagens: (i) offline usando o coeficiente de correlação de Pearson; (ii) offline usando τ de Kendall; (iii) online usando o coeficiente de correlação de Pearson; (iv) online usando τ de Kendall; e (v) uma versão de baseline, o MOEA/D. Os algoritmos foram testados usando um conjunto de dados para a cidade de Belo Horizonte. Para avaliar a dispersão das soluções obtidas pelos algoritmos, foi aplicado o indicador de hipervolume. Os resultados destes experimentos mostraram que (i) não há diferença na formulação obtida para as abordagens offline; (ii) os algoritmos online são estatisticamente melhores do que o algoritmo offline; (iii) não é possível afirmar que há diferença estatística entre os algoritmos online e o MOEA/D. Os diagramas de cordas foram aplicados sobre as soluções obtidas e indicaram que a diversidade das soluções é diferente. A segunda sequência de experimentos realizados compara as abordagens de redução de dimensionalidade baseada em agregação online e outra baseada em seleção de atributos, que usa duas técnicas: Taxa de Dispersão (DR) e Máxima Variância (MV), as quais são usadas para selecionar o representante do cluster. O impacto da frequência da redução da dimensionalidade no desempenho do algoritmo também foi analisado. As abordagens foram acopladas ao algoritmo MOEA/D. Três algoritmos foram testados (i) cluster online usando o coeficiente de correlação Pearson com MOEA/D (OnCLρg-MOEA/D); (ii) cluster online usando o coeficiente de correlação de Pearson e DR com MOEA/D (OnDRρg-MOEA/D); (iii) cluster online usando coeficiente de Pearson e MV com MOEA/D (OnMVρg-MOEA/D), sendo g = 1, 25, 50, 100. Os resultados mostraram que, independentemente da frequência da abordagem de redução de dimensionalidade, os algoritmos MOEA/D e OnCLρg-MOEA/D são estatisticamente superiores aos OnDRρg-MOEA/D e OnMVρg-MOEA/D. Não é possível afirmar que haja diferença estatística entre os resultados dos algoritmos baseados na seleção de atributos online. Os diagramas de cordas mostraram que há uma maior diversidade das soluções obtidas quando todas as funções objetivo são utilizadas na forma reduzida do problema e também quando os algoritmos permanecem por mais gerações em uma determinada formulação reduzida.Item Controle do mosquito Aedes aegypti utilizando modelos entomológico e epidemiológico dependentes de variáveis climáticas(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-03-24) Vasconcelos, Amália Soares Vieira de; Cardoso, Rodrigo Tomás Nogueira; Fernandes, José Luiz Acebal; http://lattes.cnpq.br/5174842920583671; http://lattes.cnpq.br/6761973511780975; Cardoso, Rodrigo Tomás Nogueira; Fernandes, José Luiz Acebal; Dias, Cláudia Mazza; Cunha, Maria da Consolação Magalhães; Faria, Allbens Atman Picardi; Wanner, Elizabeth FialhoAs arboviroses, doenças transmitidas por artrópodes, tornaram-se um grande desafio para os gestores de saúde pública. Dentre elas, a Organização Mundial da Saúde destaca a dengue como a responsável por centenas de milhares de infecções por ano em todo o mundo. Como não há um tratamento específico para a doença e nem vacina eficiente e sem restrições para uso em massa, a melhor opção são as medidas para combater o vetor, o mosquito Aedes aegypti. Por isso, este trabalho propõe o estudo da evolução das populações do vetor por meio de simulações computacionais com o objetivo de minimizar a quantidade de inseticidas, observando, ainda, o custo financeiro. Além disso, procura-se reduzir o custo social demandado para tratamento de doentes. Para isso, dois estudos de caso distintos foram feitos. Primeiramente, considerou-se um modelo entomológico com parâmetros dependentes da temperatura e da precipitação. Por meio de um ajuste pela raiz do erro quadrático médio, o modelo foi calibrado com dados reais de fêmeas do vetor capturadas em armadilhas no Município de Lavras, Minas Gerais. Em seguida, foram construídos três cenários de testes de aplicação de inseticidas utilizando a técnica de controle ótimo. Os cenários permitiram a aplicação do controle durante 91 dias, variando as estações do ano em que normalmente ocorre a maior quantidade de casos de dengue. Dessa forma, o cenário I consistiu na aplicação durante os primeiros dias do verão; o cenário II, na primavera; e, por fim, o cenário III foi uma combinação entre a primavera e o verão. Os resultados encontrados sugerem que, dentre os três cenários, a melhor opção a ser colocada em prática é o controle integrado realizado no cenário III. A segunda parte deste trabalho envolveu a proposta de um modelo epidemiológico dependente da temperatura, precipitação e umidade e que levasse em consideração as infecções sintomáticas e assintomáticas de dengue. Para calibração do modelo, foram usados os dados reais de humanos infectados sintomáticos nos anos mais epidêmicos do Município de Belo Horizonte, Minas Gerais. Os dados indicam que as ações de controle já realizadas no município não são suficientes para garantir que o limiar de infestação seja pequeno o bastante para evitar uma epidemia. Assim, foi apresentada uma proposta de controle adicional com o uso de larvicida, adulticida e bloqueio de transmissão. A principal contribuição do trabalho é o estudo do custo monetário real que as ações de combate ao vetor demandam versus o custo hospitalar por infectado confirmado. Dessa forma, via otimização mono-objetivo e multiobjetivo, os resultados foram discutidos, concluindo-se que quantidades discretas de controle adicional já são suficientes para reduzir o custo financeiro que seria necessário para tratamento hospitalar. Os dois estudos de caso demonstram que este trabalho é de grande valia para auxiliar os gestores de saúde a planejarem as ações de controle e combate ao Aedes aegypti.Item Classificação e reconhecimento de padrões: novos algoritmos e aplicações / Emmanuel Tavares Ferreira Affonso(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-02-28) Affonso, Emmanuel Tavares Ferreira; Silva, Alisson Marques da; Moita, Gray Farias; http://lattes.cnpq.br/2550201329788172; http://lattes.cnpq.br/3856358583630209; http://lattes.cnpq.br/3453401178017064Este trabalho visa o desenvolvimento de novos algoritmos para tarefas de classificação e reconhecimento de padrões. Inicialmente é proposto um método para seleção de atributos (FS, do inglês feature selection) para classificadores com treinamento offline. A abordagem de FS proposta, chamada de Mean Ratio for Feature Selection (MRFS), é baseada na razão das médias dos atributos em cada classe. MRFS possui baixo custo computacional pois utiliza apenas operações matemáticas básicas como adição, divisão e comparação e realiza apenas uma passagem nos dados para ranquear os atributos. O MRFS foi implementado e avaliado como método filter (MRFS-F) e como wrapper (MRFS-W). O desempenho dos métodos foram avaliados e comparados com o estado da arte. As comparações realizadas sugerem que os métodos propostos possuem um desempenho comparável ou superior aos métodos alternativos. Além dos métodos de FS foram propostos três classificadores evolutivos com treinamento online. O primeiro chamado de evolving Fuzzy Mean Classifier (eFMC) é baseado em um algoritmo de agrupamento fuzzy que realiza a classificação com base no grau de pertinência dos grupos. Novos grupos são criados sempre que uma nova classe é descoberta e a atualização do centro dos grupos é através das médias amostrais calculadas de forma incremental. O segundo classificador introduzido é o evolving Fuzzy Classifier (eFC) que de maneira análoga utiliza as médias amostrais para atualização dos centros dos grupos. Seu diferencial está na capacidade de gerar mais de um grupo associado a uma mesma classe para mapear diferentes regiões do espaço dos dados, criação de novos grupos aplicando o conceito de procrastinação, união de grupos redundantes e exclusão de grupos obsoletos. Por fim, foi proposto um classificador evolutivo com seleção de atributos denominado evolving Fuzzy Classifier with Feature Selection (eFCFS). Este classificador foi construído utilizando o mesmo algoritmo do eFC e incorporando o método MRFS de seleção de atributos. Os classificadores evolutivos propostos foram avaliados e comparados com três classificadores evolutivos alternativos. Os resultados experimentais e as comparações sugerem que os métodos baseados no MRFS para auxiliar modelos com treinamento offline e os 3 modelos evolutivos com treinamento online são promissores como alternativas para tarefas de classificação e reconhecimento de padrões, com boa acurácia e baixo custo computacional.Item Uma nova abordagem para a regularização implícita restrita no cálculo de integrais de Feynman divergentes(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-12-04) Felippe, Bruno Zanotelli; Scarpelli, Antônio Paulo Baêta; Vieira, Alexandre Rodrigues; http://lattes.cnpq.br/6655550725236919; http://lattes.cnpq.br/4164041157405626; http://lattes.cnpq.br/1738991384346781; Scarpelli, Antônio Paulo Baêta; Vieira, Alexandre Rodrigues; Fernandes, José Luiz Acebal; Maglhães, Arthur Rodrigo Bosco de; D'Afonseca, Luis Alberto; Sampaio, Marcos Donizeti RodriguesOs cálculos perturbativos em Teoria Quântica de Campos podem ser representados graficamente em termos dos diagramas de Feynman. Os cálculos das amplitudes representadas pelos diagramas de Feynman além do nível árvore envolvem, muitas vezes, integrais divergentes . Essas integrais necessitam um tratamento conhecido como regularização, a fim de que o conteúdo físico da amplitude seja dela extraído. Uma das mais poderosas técnicas, a Regularização Dimensional, envolve extensões dimensionais não inteiras do espaço-tempo. Contudo, há modelos que envolvem objetos matemáticos cuja extensão dimensional é ambígua ou mal definida. Uma técnica, chamada Regularização Implícita, mostrou-se apropriada para o tratamento de modelos cuja extensão dimensional não é bem definida. O método permite que os cálculos sejam realizados na própria dimensão da teoria e prescreve regras simples para a preservação das simetrias dos modelos. No entanto, no caso de altos graus de divergência, para uma única integral de Feynman, a expansão para separar as divergências pode gerar um grande conjunto de integrais finitas. Além disso, as expansões geram altas potências de momentos no numerador e denominador, o que resulta em cálculos longos e trabalhosos. Desenvolvemos, nesse trabalho, um novo procedimento para aplicação da Regularização Implícita Restrita que simplifica o cálculo de amplitudes, incluindo as partes finitas.Item Desenvolvimento de matrizes de distâncias para representar interações de proteínas combinadas com algoritmos de agrupamento(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-24) Monteiro, Otaviano Martins; Rodrigues, Thiago de Souza; Dias, Sandro Renato; http://lattes.cnpq.br/5300421458375793; http://lattes.cnpq.br/4182923743939851; http://lattes.cnpq.br/5378637011361467; Rodrigues, Thiago de Souza; Dias, Sandro Renato; Gomes, Rogério Martins; Cruz, André Rodrigues da; Menezes, Gustavo Campos; Silva, Alisson Marques daAs proteínas são macromoléculas formadas por aminoácidos e estão presentes em todos os seres vivos. Várias proteínas tiveram suas estruturas tridimensionais resolvidas experimentalmente e foram armazenadas através de arquivos de texto em bancos de dados biológicos como o Protein Data Bank (PDB). Essas informações proteicas podem ser utilizadas por softwares, como o LSQKAB, que verificam similaridades tridimensionais de proteínas através de sobreposições entre os átomos das estruturas comparadas. No entanto, a realização de sobreposições atômicas requer um alinhamento preciso entre os átomos de duas estruturas por meio de movimentos de rotação e translação. Esse procedimento é computacionalmente intensivo, sendo classificado como NP-Completo. Portanto, a realização de múltiplas sobreposições atômicas, algo frequente em softwares que propõem mutações em proteínas, acarreta em um elevado custo computacional. Assim sendo, o propósito deste estudo consiste em elaborar abordagens fundamentadas em matrizes de distâncias, combinadas com algoritmos agrupamento (clustering) com o intuito de criar conjuntos de interações de proteínas que compartilham conformações tridimensionais semelhantes. O objetivo principal é alcançar soluções de alta precisão e desempenho notável, com o propósito de minimizar a necessidade de realizar sobreposições atômicas. Com o intuito de cumprir esses objetivos, foram desenvolvidas matrizes de distâncias baseadas em diferentes abordagens. A Matriz de Ângulos (MA) foi desenvolvida a partir dos ângulos dos átomos. A Matriz de Distâncias Completa Mista (MDCM) foi desenvolvida através da fusão de diferentes técnicas. A Matriz de Distâncias Reduzida cujos Centroides são Carbonos Alfa (MDRCCA), a Matriz de Distâncias Reduzida a partir de um Ponto entre os Carbonos Alfa (MDRPCA), além da Matriz de Pontos Médios (MPM) foram desenvolvidas a partir da importância dos átomos de carbonos alfa (CA). A concepção da MPM também foi influenciada pela importância das distâncias entre todos os átomos na estrutura, uma vez que essas distâncias são cruciais para o enovelamento da mesma. Essas estratégias foram integradas a algoritmos de agrupamento e os resultados subsequentes foram comparados com o método de busca da ferramenta RID, por ser uma ferramenta especialista em trabalhar com interações de proteínas, além da atomic Cutoff Scanning Matrix (aCSM) por ser uma das versões da Cutoff Scanning Matrix (CSM), que é considerada o estado da arte na geração de assinaturas em grafos proteicos, e com a Matriz de Distâncias Completa (MDC), que apresentou resultados superiores ao método de busca da RID e aCSM, nos primeiros trabalhos deste projeto. Os resultados foram satisfatórios, principalmente os alcançados pela MPM, que superou as demais técnicas na maioria dos experimentos.Item Desenvolvimento de matrizes de distâncias para representar interações de proteínas combinadas com algoritmos de agrupamento(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-24) Monteiro, Otaviano Martins; Rodrigues, Thiago de Souza; Dias, Sandro Renato; http://lattes.cnpq.br/5300421458375793; http://lattes.cnpq.br/4182923743939851; http://lattes.cnpq.br/5378637011361467; Rodrigues, Thiago de Souza; Dias, Sandro Renato; Gomes, Rogério Martins; Cruz, André Rodrigues da; Menezes, Gustavo Campos; Silva, Alisson Marques daAs proteínas são macromoléculas formadas por aminoácidos e estão presentes em todos os seres vivos. Várias proteínas tiveram suas estruturas tridimensionais resolvidas experimentalmente e foram armazenadas através de arquivos de texto em bancos de dados biológicos como o Protein Data Bank (PDB). Essas informações proteicas podem ser utilizadas por softwares, como o LSQKAB, que verificam similaridades tridimensionais de proteínas através de sobreposições entre os átomos das estruturas comparadas. No entanto, a realização de sobreposições atômicas requer um alinhamento preciso entre os átomos de duas estruturas por meio de movimentos de rotação e translação. Esse procedimento é computacionalmente intensivo, sendo classificado como NP-Completo. Portanto, a realização de múltiplas sobreposições atômicas, algo frequente em softwares que propõem mutações em proteínas, acarreta em um elevado custo computacional. Assim sendo, o propósito deste estudo consiste em elaborar abordagens fundamentadas em matrizes de distâncias, combinadas com algoritmos agrupamento (clustering) com o intuito de criar conjuntos de interações de proteínas que compartilham conformações tridimensionais semelhantes. O objetivo principal é alcançar soluções de alta precisão e desempenho notável, com o propósito de minimizar a necessidade de realizar sobreposições atômicas. Com o intuito de cumprir esses objetivos, foram desenvolvidas matrizes de distâncias baseadas em diferentes abordagens. A Matriz de Ângulos (MA) foi desenvolvida a partir dos ângulos dos átomos. A Matriz de Distâncias Completa Mista (MDCM) foi desenvolvida através da fusão de diferentes técnicas. A Matriz de Distâncias Reduzida cujos Centroides são Carbonos Alfa (MDRCCA), a Matriz de Distâncias Reduzida a partir de um Ponto entre os Carbonos Alfa (MDRPCA), além da Matriz de Pontos Médios (MPM) foram desenvolvidas a partir da importância dos átomos de carbonos alfa (CA). A concepção da MPM também foi influenciada pela importância das distâncias entre todos os átomos na estrutura, uma vez que essas distâncias são cruciais para o enovelamento da mesma. Essas estratégias foram integradas a algoritmos de agrupamento e os resultados subsequentes foram comparados com o método de busca da ferramenta RID, por ser uma ferramenta especialista em trabalhar com interações de proteínas, além da atomic Cutoff Scanning Matrix (aCSM) por ser uma das versões da Cutoff Scanning Matrix (CSM), que é considerada o estado da arte na geração de assinaturas em grafos proteicos, e com a Matriz de Distâncias Completa (MDC), que apresentou resultados superiores ao método de busca da RID e aCSM, nos primeiros trabalhos deste projeto. Os resultados foram satisfatórios, principalmente os alcançados pela MPM, que superou as demais técnicas na maioria dos experimentos.Item Estratégias de solução baseadas em paralelismo CUDA para o problema de instalação de fibras em redes óticas(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-18) Reis, Daniel Morais dos; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; http://lattes.cnpq.br/8899693603008522; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/2020021419382172; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; Coleho, Igor Machado; Fernandes, Gustavo Alves; Menezes, Gustavo Campos; Souza, Marcone Jamilson FreitasEste trabalho otimiza métodos sequenciais e propõe métodos heurísticos paralelizados em GPUs Nvidia CUDA para a solucionar o Problema de Instalação de Fibras em Redes Óticas - PIFRO. O PIFRO consiste em alocar, em uma rede ótica que utiliza tecnologia Wavelength Division Multiplexing (WDM), um conjunto de requisições previamente conhecidas com múltiplas origens e destinos. O objetivo é minimizar o custo total dos dispositivos necessários para a operação da rede. Após provar que a versão de decisão do PIFRO é NP-Difícil, é realizada uma formulação matemática e implementadas duas metaheurísticas paralelizadas em formatos inéditos, buscando a melhoria dos resultados da literatura. Uma das heurísticas é baseada em Biased Random Key Genetic Algorithm (BRKGA) e a outra é baseada em Iterated Local Search (ILS) as quais foram selecionadas pelos bons resultados existentes para o problema. Os conceitos básicos de processamento paralelo são analisados e selecionados para execução de novas metaheurísticas em ambientes heterogêneos com GPUsItem Análise multiplex da rede brasileira de transporte aéreo(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-03-20) Oliveira, Izabela Marques de; Faria, Allbens Atman Picardi; Carpi, Laura Corina; http://lattes.cnpq.br/2779640920944038; http://lattes.cnpq.br/4216801992845696; http://lattes.cnpq.br/0119061678782077; Faria, Allbens Atman Picardi; Carpi, Laura Corina; Jesus, Tiago Alves Schlieber; Gonçalves, Bruna Amin; Scarpelli, Antônio Paulo Baeta; Magalhães, Arthur Rodrigo Bosco deO transporte aéreo continua sendo a melhor opção para conectar regiões distantes e apoiar o desenvolvimento social e econômico mundial, apesar dos desafios ambientais. O Brasil depende fortemente dessa modalidade de transporte devido às suas dimensões continentais. Neste trabalho realizamos um estudo utilizando a abordagem multiplex de redes complexas para analisar a rede brasileira de transporte aéreo de passageiros, BATMN. Nesse contexto, criamos o Índice de Eficiência Multiplex (MEI) e suas versões para redes direcionadas e/ou ponderadas, que permitem quantificar o nível de heterogeneidade de conexões de uma rede multiplex em uma escala de 0 a 1, considerando características de direção e grau de importância das arestas, sendo apropriados para pesquisas em redes de transporte. Utilizamos o MEI para avaliar a diversificação de rotas das empresas de transporte aéreo no Brasil entre 2010 e 2021, um período marcado pela ocorrência de grandes eventos no país. Analisamos a influência de alguns desses eventos sobre a eficiência da rede, como a Copa do Mundo FIFA em 2014 e as Olimpíadas do Rio em 2016, assim como de outras mudanças no setor, incluindo a fusão entre companhias aéreas, a privatização de aeroportos, o encerramento de operações de uma importante transportadora aérea e da pandemia de COVID-19. Além disso, investigamos se a diversificação de rotas afetou os preços das passagens aéreas praticados no Brasil. Adicionalmente, por meio de uma metodologia recém-introduzida na literatura, examinamos a capacidade de difusão da rede e observamos o ganho relativo ocorrido em relação à difusão do sistema de transporte aéreo quando são consideradas as conexões de voos entre diferentes companhias aéreas, delineando um cenário de possíveis parcerias entre as empresas aéreas. As avaliações realizadas neste trabalho fornecem novas e significativas informações sobre a rede de transporte aéreo de passageiros no Brasil, contribuindo para otimizar a oferta desse tipo de transporte no país e, consequentemente, reduzir os custos envolvidos. Além disso, a metodologia proposta permite não somente uma análise diferenciada das redes de transporte aéreo, mas também a quantificação da eficiência de redes multiplex em geral.Item Um estudo com abordagem heurística para problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-02-27) Bezerra, Sinaide Nunes; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; http://lattes.cnpq.br/5654731681042767; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz; Sá, Elisângela Martins de; Wanner, Elizabeth FialhoEste trabalho trata de alguns problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos. Nesse conjunto estão problemas com roteamento fechado e aberto que objetivam a redução na distância ou na quantidade de veículos. Esse conjunto de problemas é NP-difícil, pois eles têm como subproblema, o Problema de Roteamento de Veículos (PRV), onde os clientes são atendidos por uma frota de veículos de mesma capacidade homogênea, em que os custos são dados pela distância total percorrida ou quantidade total de veículos utilizados no atendimento aos clientes. Para resolver esses problemas, o Smart General Variable Neighborhood Search com Busca Local Adaptativa (SGVNSBLA) é apresentado. O algoritmo alterna o mecanismo de busca local entre duas estratégias diferentes. Na primeira estratégia, o método Randomized Variable Neighborhood Descent (RVND) realiza a busca local e, ao aplicar essa estratégia, as vizinhanças com os melhores vizinhos recebem uma pontuação maior. Na segunda estratégia, o método de busca local é aplicado apenas em uma única vizinhança, escolhida pelo método da roleta. Assim, a aplicação da primeira estratégia de busca local serve como método de aprendizagem para aplicação da segunda estratégia. Para testar esses algoritmos, usamos instâncias de benchmark do MDVRPTW envolvendo até 960 clientes, 12 depósitos e 120 veículos, num total de 48 instâncias teste. Para fins de comparação, outros algoritmos baseados em vizinhança também foram implementados. Os resultados encontrados permitiram avaliar a contribuição das estruturas de vizinhanças utilizadas nas soluções que buscam a redução na quantidade de veículos. Os resultados mostram que o desempenho do SGVNSBLA superou o dos outros algoritmos implementados visando a redução da frota. Houve uma redução da frota de veículos em 91,18% das instâncias avaliadas e o tamanho da frota alcançou uma redução média de até 23,32% em problemas com janelas de tempo e múltiplos depósitos. Ao se avaliar essas instâncias com roteamento aberto, houve redução na quantidade de veículos em 100% das instâncias, com baixa variabilidade.Item Modelo de difusão-reação dependente de variáveis climáticas para o controle do mosquito Aedes aegypti(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-02-27) Lima, Josenildo Silva de; Cardoso, Rodrigo Tomás Nogueira; http://lattes.cnpq.br/5174842920583671; http://lattes.cnpq.br/3951904798639045; Cardoso, Rodrigo Tomás Nogueira; Takahashi, Ricardo Hiroshi Caldeira; Wyse, Ana Paula Pintado; Magalhães, Arthur Rodrigo Bosco; Fernandes, José Luiz AcebalO Aedes aegypti é um mosquito de origem africana que transmite diversas doenças gerando crescente preocupação internacional nos últimos anos, com mais de um terço da população do mundo vivendo em regiões suscetíveis à infecção. Muitas das doenças transmitidas pelo mosquito ainda carecem de tratamento ou vacina. Diante disso, modelos matemáticos e computacionais tem sido desenvolvidos para eliminação do Aedes aegypti como, controle mecânico utilizando inseticidas, larvicidas, tratamento Ultra Baixo Volume e controle biológico por meio da Wolbachia. Este trabalho considera um modelo entomológico e um modelo epidemiológico com dois estudos de caso com dados reais. Primeiramente apresenta-se o modelo matemático entomológico de difusão-reação unidimensional que analisa a propagação do vetor nas fases aquática e adulta de fêmeas, com alguns parâmetros dependentes da precipitação e temperatura. Em seguida, formulou-se um problema de otimização mono-objetivo para minimizar as variáveis de controle e as populações na fase aquática e adulta de fêmeas utilizando dados reais da cidade de Lavras/Minas Gerais. No segundo estudo propõem-se um sistema de equações diferenciais parciais que descrevem a dispersão e interação do Aedes aegypti com humanos com parâmetros dependentes da temperatura e precipitação. Formulou-se um problema de otimização mono e multiobjetivo para minimizar as variáveis de controle e população de humanos infectados sintomáticos utilizando dados reais do município de Belo Horizonte/Minas Gerais. Obteve-se a solução numérica da equação diferencial parcial dos dois modelos pelo método da decomposição de operadores e utilizou-se os métodos de diferenças finitas, Runge-Kutta de quarta ordem, Algoritmo Genético Real Polarizado e o Non-Dominated Sorting Genetic Algorithm II para as demais simulações computacionais. Os resultados numéricos mostram que o controle permitem melhor eficiência no combate ao Aedes aegypti para os casos de Lavras e Belo Horizonte e também uma redução significativa no número de humanos infectados e nos custos envolvidos com a hospitalização de pessoas infectadas pelo vírus da dengue em Belo Horizonte.Item Análise de fatores que impactam no futebol baseada em ciência de dados(Centro Federal de Educação Tecnológica de Minas Gerais, 2022-02-27) Capanema, Daniel de Oliveira; Pereira, Adriano César Machado; http://lattes.cnpq.br/6813736989856243; http://lattes.cnpq.br/0779594261363903; Alves, Adriano César Machado; Alves, Adriano Lima; Claudino, João Gustavo de Oliveira; Santiago, Paulo Roberto Pereira; Wanner, Elizabeth Fialho; Pádua, Flávio Luis CardealEsportes profissionais e de alto desempenho estão cada vez mais utilizando novas tecnologias para obter melhores resultados em treinamentos e competições. Estudos para prevenir lesões e melhorar o desempenho têm sido aplicados e bons resultados já foram alcançados. Para atingir os objetivos, técnicas de inteligência artificial são aplicadas aos dados para encontrar padrões, prever tendências, melhorar resultados, táticas, equipamentos e outros. Este trabalho analisa dados reais de clubes da primeira divisão do futebol brasileiro, aplicando métodos de inteligência artificial para classificar jogadores, encontrar padrões, variáveis ou características que influenciam nos resultados, definindo características que influenciam na ocorrência de lesões e no desempenho dos atletas. Jogadores foram classificados e comparações foram feitas em grupos que possuíam ou não jogadores lesionados. Também foram realizadas análises comparativas em grupos de jogadores com melhores e piores médias de eficiência física, mostrando que jogadores com melhores médias tendem a apresentar características de treino mais parecidas com as do jogo, enquanto jogadores com piores médias apresentam números no treinamento inferiores aos dos jogos. Também foram estudadas as principais características que influenciam nos resultados dos jogos, sendo uma delas a diferença de performance entre o primeiro e o segundo tempo, considerando variáveis relacionadas à distância. O classificador XGBoost conseguiu bons resultados ao prever esta diferença de performance, além de apresentar como e quais variáveis influenciam nesta diferença. O trabalho também apresenta revisões sistemáticas de inteligência artificial em esportes em equipes e individuais, trazendo informações relevantes e métricas sobre o assunto.Item Técnicas de aprendizado de máquina para a previsão da resistência à compressão do concreto e da aderência aço-concreto(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-02-24) Silva, Priscila Flávia Souza da; Moita, Gray Farias; Carvalho, Eliene Pires de; http://lattes.cnpq.br/0426741711913176; http://lattes.cnpq.br/2550201329788172; http://lattes.cnpq.br/2665331153908857; Moita, Gray Farias; Carvalho, Eliene Pires de; Kripka, Moacir; Pitangueira, Roque Luiz da Silva; Silva, Alisson Marques da; Menezes, Gustavo CamposO concreto convencional é um dos materiais mais utilizados na construção civil e no mundo. Sua mistura é composta por cimento, água e diversos agregados. Seu comportamento é altamente não linear devido, principalmente, a suas características heterogêneas. A resistência à compressão é um dos parâmetros mais importantes para a determinação das características estruturais do concreto, sendo utilizada amplamente por calculistas para a realização de projetos estruturais. Já a aderência entre a barra de aço e a pasta de concreto, que são os principais componentes do concreto armado, pode ser vista como um dos principais fatores para que o concreto armado seja considerado uma solução estrutural viável para as mais diversas obras. Esses dois paramentos são usualmente determinados por meio de ensaios laboratoriais dispendiosos, ocasionando grande gasto com recursos, materiais e tempo para a sua execução. Esse gasto é aumentado, principalmente, se considerado que a resistência à compressão do concreto, para atendimentos de processos normativos, é medida aos 7, 14 e 28 dias. Portanto, a previsão de resistência do concreto e da tensão de aderência continua sendo uma área ativa de pesquisa com um número considerável de estudos realizados. Por outro lado, a inteligência artificial e suas diversas aplicações são exemplos de novas tecnologias emergentes que têm se mostrado bem-sucedidas nas mais diversas aplicações científicas. Geralmente, os métodos computacionais superam suas contrapartes tradicionais, como os ensaios experimentais, na resolução de tarefas não lineares. Neste trabalho, é proposta a implementação de algoritmos de inteligência computacional para determinar a resistência do concreto armado à compressão e a força de arrancamento a partir de bases de dados experimentais. Cinco modelos são projetados, implementados e testados: árvores de decisão, florestas aleatórias, máquinas vetoriais de suporte, redes neurais artificiais e regressor gradiente boosting. Também são utilizados métodos de pré processamento de dados e técnicas estatísticas para um melhor estudo das bases de dados utilizadas. O objetivo desse estudo é determinar a resistência à compressão do concreto e a força de arrancamento de barras de aço engastadas em corpos de prova de concreto sem destruir nenhuma amostra. Por fim, os resultados obtidos neste trabalho mostram eficiência na determinação da resistência à compressão e na força de arrancamento e são comparados com outros trabalhos, destrutivos e não destrutivos, que também obtiveram esses parâmetros.Item k-in-a-TREE: an integer programming approach(Centro Federal de Educação Tecnológica de Minas Gerais, 2024-10-16) Ferreira, Lucas Saldanha; Santos, Vinícius Fernandes dos; http://lattes.cnpq.br/6270626469557436; Santos, Vinícius Fernandes dos; Melo, Rafael Augusto de; Valle, Cristiano Arbex; Sá, Elisângela Martins de; Martins, Flávio Vinícius CruzeiroChudnovsky e Seymour (2010) propuseram o algoritmo THREE-IN-A-TREE, que resolve o seguinte problema em tempo polinomial: dado um grafo simples e finito e três vértices fixos, verificar se existe uma árvore induzida contendo esses vértices. Neste trabalho, lidamos com uma generalização natural desse problema, denominada k-IN-A-TREE. Este problema pergunta se um grafo contém uma árvore induzida que abrange k vértices predeterminados. Quando k faz parte da entrada, o problema é conhecido por ser NP-completo, se k ≥ 4 é um número fixo, sua complexidade está aberta. Entretanto existem algoritmos eficientes para casos restritos, como grafos livres de garras, grafos com circunferência pelo menos k e grafos cordais. Neste trabalho apresentamos formulações de programação inteira mista para o problema em questão e mostramos que instâncias com até 25.000 vértices podem ser resolvidas em tempo computacional razoável. Também agregamos mais de três anos de tempo computacional em experimentos projetados para explorar quais variáveis impactam o tempo de execução das várias instâncias geradas; essas análises fornecem um perfil para o problema k-IN-A-TREE em sua forma mais genérica. As contribuições deste trabalho incluem demonstrar que o k-IN-A-TREE pode ser eficientemente resolvido usando Programação Linear Inteira (ILP), permitindo a solução de instâncias de tamanhos relativamente grandes. Além disso, apresentamos análise detalhada que foi conduzida para identificar e caracterizar as principais variáveis que influenciam a dificuldade computacional do problema, fornecendo dados valiosos sobre como a estrutura do grafo, tamanho, conectividade dos vértices e a distribuição dos elementos obrigatórios, afetam a dificuldade. Outra contribuição significativa é a demonstração de que o problema pode ser resolvido de forma eficaz em intervalos de tempo que seriam insuficientes para resolver outros problemas combinatórios complexos, como o Problema do Caixeiro Viajante (TSP). Isso destaca a tratabilidade computacional do problema em ambientes com restrições de tempo, onde outros problemas de complexidade semelhante permanecem mais desafiadores. Essas contribuições avançam o entendimento do problema, estabelecendo um novo marco para a habilidade de resolver o problema e abrindo caminho para futuras explorações teóricas e práticas.Item Problemas de localização de concentradores com alocação simples e economia de escala dependente do fluxo: abordagens de minimização de custos e de maximização de lucro(Centro Federal de Educação Tecnológica de Minas Gerais, 2024-08-29) Freitas, Nayane Carvalho; Sá, Elisângela Martins de; Souza, Sérgio Ricardo de; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/4686246805500174; http://lattes.cnpq.br/3374333308607200; Martins, Alexandre Xavier; Camargo, Ricardo Saraiva de; Souza, Marcone Jamilson Freitas; Menezes, Gustavo CamposEsta tese aborda os problemas de localização de concentradores de alocação simples com economias de escala dependentes do fluxo, com foco em duas abordagens: a minimização de custos e a maximização de lucros. Estes problemas consistem em selecionar nós para estabelecer concentradores e determinar rotas para o roteamento dos fluxos de demanda através deles, a fim de minimizar o custo total (composto pelo custo de instalação dos concentradores e pelo custo de roteamento dos fluxos) ou maximizar o lucro total, assumindo que existe uma economia de escala que depende da quantidade de fluxo encaminhado em cada arco entre concentradores. O principal objetivo deste trabalho é desenvolver modelos matemáticos para os problemas abordados, bem como propor métodos heurísticos para resolvê-los. Para o Problema de Localização de Concentradores de alocação simples e economia de escala dependente do fluxo que minimiza o custo total, este estudo propõe um novo modelo de programação linear inteira e um algoritmo baseado na meta-heurística General Variable Neighborhood Search (GVNS) para lidar com instâncias de grandes dimensões do problema. Experimentos computacionais foram realizados utilizando instâncias da literatura com até 500 nós. Os resultados mostram que o algoritmo GVNS é eficaz para resolver as instâncias em termos de tempo de execução e qualidade da solução. Os resultados também mostram que a formulação proposta supera a formulação da literatura ao ativar o método de decomposição de Benders disponível no solver CPLEX. Para os Problemas de Localização de Concentradores de alocação simples e economia de escala dependente do fluxo que maximizam lucros, este estudo introduz os primeiros modelos de programação linear inteira para as versões do problema com e sem restrições de capacidade de fluxos nos concentradores, e desenvolve algoritmos heurísticos também baseados em GVNS para as duas versões do problema. Resultados de experimentos computacionais mostram que o melhor dos modelos apresentados permite obter a solução ótima, dentro de um tempo limite preestabelecido de 24 horas, para instâncias com até 50 nós utilizando o solver CPLEX. Os resultados também mostram a eficácia do método heurístico proposto, quando restrições de capacidade não são consideradas no problema.