PPGCC - Mestrado (Dissertações)
URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/597
Navegar
18 resultados
Resultados da Pesquisa
Item Exact and heuristic approaches for traveling salesman problems with drones.(2021) Freitas, Júlia Cária de; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Souza, Marcone Jamilson Freitas; Subramanian, AnandThe technological advances concerning drones have encouraged the market to consider drone applications in different areas including last mile delivery. However, limitations due to battery capacity, maximum weight, and legal regulations restrict the effective operational range of drones in many practical applications. To overcome the battery issue, hybrid operations involving one or more drones launching from a larger vehicle have emerged, in which the larger vehicle operates as a mobile depot and a recharging platform. In this dissertation, we describe a routing model that leverage the drone and truck working as a synchronized unit. The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return to the truck to recharge batteries, pick up another package, and launch again to a new customer location. This work proposes two novel Mixed Integer Programming (MIP) formulations and a heuristic approach to address the problem. The proposed MIP formulations yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature. We developed a hybrid heuristic based on the General Variable Neighborhood Search metaheuristic to tackle a generalization of the FSTSP called Multiple Traveling Salesman Problem with Drones, in which multiple trucks and drones are considered as part of the delivery system. The heuristic obtained high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 410 benchmark instances from the literature, and over 80% of the best known solutions were improved.Item Uma nova formulação para otimização multi-objetivo em redes de filas finitas gerais e com único servidor.(2020) Souza, Gabriel Lima de; Moreira, Gladston Juliano Prates; Duarte, Anderson Ribeiro; Moreira, Gladston Juliano Prates; Duarte, Anderson Ribeiro; Cruz, Frederico Rodrigues Borges da; Silva, Ivair RamosUma nova formulação de programação matemática é proposta para um problema de otimização em redes de filas. A soma das probabilidades de bloqueio de uma rede de filas acíclicas finitas de servidor único e tempo de serviço geral é minimizada juntamente com o tamanho total da área de espera e as taxas gerais de serviço. Um algoritmo genético multiobjetivo (MOGA) e um algoritmo multiobjetivo de otimização por enxame de partículas (MOPSO) é adaptado para resolver esse difícil problema estocástico. O algoritmo resultante produz um conjunto de soluções eficientes para mais de um objetivo. A implementação dos algoritmos de otimização depende do método de expansão generalizado (GEM), uma ferramenta clássica usada para avaliar o desempenho de redes de filas finitas. Um conjunto de experimentos computacionais é apresentado para evidenciar a eficácia e eficiência da abordagem proposta. As informações obtidas a partir da análise de uma rede complexa podem ajudar no planejamento desses tipos de redes de filas.Item Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.(2018) Campos, Jean Carlos Tiburcio; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Souza, Maurício Cardoso deEste trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN). Ele consiste em encontrar uma árvore geradora de custo mínimo, tal que o fluxo a ser transferido de um nó central aos demais nós seja limitado pela capacidade das arestas. Para resolvê-lo, propomos neste trabalho uma formulação reforçada de programação matemática e um algoritmo híbrido, combinando as heurísticas relax-and-fix e Variable Neighborhood Search (VNS), juntamente com um modelo matemático. A formulação matemática proposta, chamada \Modelo Baseado na Capacidade das Facilidades 2" (MBC2), consiste em adicionar dois novos conjuntos de restrições à formulação considerada a mais e ciente da literatura. A motivação para a utilização do modelo MBC2 está em ele fornecer um limite inferior de qualidade, esperando assim convergir mais rapidamente à solução ótima. Experimentos computacionais mostraram que a formulação reforçada proposta, quando comparada ao modelo da literatura, melhora a qualidade da relaxação linear, fornecendo um limite inferior melhor e justificando a sua utilização. Para o desenvolvimento do algoritmo híbrido, foi utilizado o modelo MBC2 proposto neste trabalho, em razão de ele ser capaz de proporcionar um limite inferior de qualidade. Essa formulação reforçada é usada com a heurística relax-and-fix para fornecer uma solução inicial para o VNS. Resultados mostram que o VNS melhora a solução inicial e gera soluções com gaps relativamente pequenos nas instâncias usadas para teste.Item Propostas para solução do problema de movimentação de tripper.(2018) Caldas, Felipe Novaes; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Carvalho, Marco Antonio Moreira de; Camargo, Ricardo Saraiva deO tripper é um equipamento frequentemente encontrado em uma planta de beneficiamento mineral. Sua função é distribuir o minério proveniente de uma correia transportadora sobre um silo de estocagem. A movimentação de tripper é um problema de sequenciamento definido pela determinação do posicionamento do equipamento sobre um silo ao longo do tempo. A escassez de referências na literatura científica que descrevam detalhadamente o tema em questão releva a importância deste trabalho em propor soluções a um problema que, apesar de receber pouca atenção do meio acadêmico, possui grande importância em muitas instalações de tratamento de minério ao redor do mundo. O primeiro passo é propor a modelagem do sistema silo-tripper na forma de um programa linear inteiro misto, de modo que seja possível determinar uma trajetória ótima de movimentação para o equipamento. Dois paradigmas foram utilizados para obter soluções exatas para este modelo: programação linear inteira mista e programação dinâmica. Embora tenham sido efetivas em solucionar instâncias pequenas, estas duas abordagens se mostraram ineficientes ao lidar com instâncias de dimensões mais elevadas, já que o tempo necessário para se alcançar a solução exata é muito alto, inviabilizando-se aplicações reais em silos com muitos compartimentos. Buscando-se alcançar soluções relativamente boas em relação ao ótimo, mas levando muito menos tempo, as meta-heurísticas GRASP e Simulated Annealing (SA) foram adaptadas como alternativa aos métodos exatos, representando esses algoritmos a segunda contribuição deste trabalho. O desempenho do GRASP se mostrou muito superior aos resultados obtidos pelo SA, tanto em relação ao tempo despendido quanto à assertividade em atingir soluções exatas. Os resultados importantes alcançados pela programação dinâmica e pelo GRASP os tornam fortes candidatos à implantação em aplicações reais, em situações que tanto precisão quanto tempo de resposta sejam pré-requisitos necessários.Item Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo : um estudo de caso industrial de larga escala.(2018) Aquino, Roberto Dias; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Carvalho, Marco Antonio Moreira de; Souza, Sérgio Ricardo deEste trabalho propõe uma modelagem de programação linear inteira mista e algoritmos meta-heurísticos para um problema real de planejamento de manutenção de longo prazo para uma planta de beneficiamento de minério de ferro no Brasil. Este é um problema complexo de programação de ordens de manutenção preventiva, para o qual é necessário atribuir ordens de manutenção preventiva para as equipes de trabalho disponíveis em um horizonte de 52 semanas. Foi desenvolvido um modelo de programação inteira mista e os resultados foram utilizados como um benchmark. Como o modelo não foi capaz de resolver a instância real, foram propostos algoritmos meta-heurísticos para resolvê-la. Esses algoritmos foram baseados nos métodos Simulated Annealing, Variable Neighborhood Search, Multi-Start, Biased Random-Key Genetic Algorithm e algoritmos meméticos. Os algoritmos heurísticos desenvolvidos foram capazes de resolver a instância real, assim como melhorar a maioria dos resultados das instâncias de dimensões menores, levando a novos benchmarks.Item Operador de pesquisa local baseada em aproximação quadrática para problemas de otimização contínua.(2018) Mota, Felipe de Oliveira; Moreira, Gladston Juliano Prates; Moreira, Gladston Juliano Prates; Cruz, André Rodrigues; Wanner, Elizabeth Fialho; Santos, Thiago FontesEste documento traz o estudo de um operador de busca local que uti- liza aproxima¸c˜oes quadr´aticas para formar um algoritmo hibrido e resolver problemas multiobjetivo ou mono objetivo com restri¸c˜oes de igualdade. Mui- tas vezes, algoritmos evolutivos como o PSO (Eberhart & Kennedy,1995) conseguem encontrar boas bacias de atra¸c˜ao em problemas de otimiza¸c˜ao, mas explor´a-las pode ser complicado. Por isso uma hibridiza¸c˜ao com poten- cial para encontrar rapidamente m´ınimos locais ´e uma op¸c˜ao amplamente utilizada para acelerar a convergˆencia e melhorar a precis˜ao do processo. Ao longo da sua execu¸c˜ao, os algoritmos evolutivos movem seus pon- tos de maneira que eles avancem a`s regi˜oes com as melhores solu¸c˜oes. Os operadores utilizados, chamados aqui de Full-Matrix Quadratic Approxima- tion (FMQA) e Diagonal Quadratic Approximation (DQA), utilizar˜ao pontos das boas regi˜oes encontradas no espa¸co para gerar fun¸c˜oes quadr´aticas que aproximam as fun¸c˜oes originais do problema. Eles diferem apenas em como as matrizes s˜ao constru´ıdas. Este modelo aproximado pode ser facilmente resolvido, obtendo uma solu¸c˜ao que atender´a o problema original e ´e prova- velmente melhor do que os pontos utilizados para fazer tal constru¸c˜ao. O objetivo do trabalho ´e testar a uni˜ao destes operadores com o algoritmo evolutivo Particle Swarm Optimization (PSO), melhorando seus indiv´ıduos separadamente para resolver problemas com restri¸c˜oes de igualdade. N´os queremos observar suas vantagens e desvantagens quanto a tempo compu- tacional e precis˜ao, quando aplicada aos problemas propostos. Nestes pro- blemas, a dimens˜ao reduzida do espa¸co de busca torna dif´ıcil o trabalho do algoritmo evolutivo puro, e esse operador se mostrou eficiente para auxiliar na busca. Tamb´em ser´a estudado como os operadores performam em problemas multiobjetivo.Item Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.(2018) Santos, Vinícius Gandra Martins; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Lima, Joubert de CastroO problema de Minimização da Largura de Corte em Grafos (ou CMP, do inglês Cutwidth Minimization Problem) consiste em determinar um leiaute linear para um grafo de forma a minimizar a quantidade máxima de arestas que cruzam cada par de vértices consecutivos. Esse problema pode ser encontrado no projeto de circuitos integrados de larga escala, no desenho de diagramas de grafos e no projeto de compiladores, entre outros. O CMP é um problema NP-Difícil e se apresenta como um desafio para métodos exatos e heurísticas. Neste trabalho, é reportada pela primeira vez na literatura a aplicação do método metaheurístico Busca Adaptativa em Grandes Vizinhanças (Adaptive Large Neighborhood Search) para solução do CMP. Os experimentos computacionais envolvem 11.786 instâncias de quatro conjuntos da literatura e os resultados encontrados são comparados com o atual estado da arte. O método proposto se mostra competitivo, sendo capaz de igualar a maioria dos resultados comprovadamente ótimos e melhores resultados conhecidos, além de melhorar alguns resultados que não foram provados ótimos e encontrar pela primeira vez limitantes superiores para instâncias não resolvidas.Item Segmentação de núcleos de células cervicais em exame de Papanicolau.(2018) Oliveira, Paulo Henrique Calaes; Bianchi, Andrea Gomes Campos; Bianchi, Andrea Gomes Campos; Moreira, Gladston Juliano Prates; Ushizima, Daniela Mayumi; Medeiros, Fátima Nelsizeuma Sombra deA utilização de algoritmos que possam auxiliar no diagnostico do exame de Papanicolau vem sendo estudada ao longo das ultimas décadas devido ao aumento dos casos de Câncer cervical na população e respectivos dados coletados. Uma das etapas dessa automatização do diagnóstico é a segmentação automática das imagens. Alguns dos maiores problemas quando se realiza a segmentação deste tipo de imagens são a sobreposição celular, o dobramento das células e os artefatos que se confundem aos núcleos. Então é apresentada uma nova abordagem de segmentação nuclear utilizando uma heurística associada a um algoritmo genético multi-objetivo. O processo envolve três etapas principais, que são o pré-processamento, a calibração da heurística e a segmentação dos núcleos. Experimentos realizados com bases de dados sintéticas disponibilizadas no Overlapping Cervical Cytology Image Segmentation Challenge - ISBI2014 e uma nova base de imagens reais sugerem uma melhoria na detecção dos núcleos em comparação com os resultados obtidos pelos vencedores do desafio. Desse modo, esse trabalho apresenta uma interface web colaborativa criada para a geração de uma base de dados com imagens reais e um método para segmentação de núcleos que utiliza uma heurística associada a um algoritmo evolutivo multi-objetivo.Item Algoritmos exatos e heurísticos para a resolução do problema da descoberta de cliques de peso máximo.(2015) Vilas Boas, Matheus Guedes; Santos, Haroldo GambiniO presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heurísticos, sequenciais e paralelos, para a resolução do problema da enumeração de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vértices ponderados, onde o objetivo é encontrar todos os cliques maximais com peso acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separação de cortes no contexto de Programação Inteira. Encontrar todos os cliques acima de um dado peso é equivalente ao problema de encontrar todas as desigualdades violadas de clique. Foram desenvolvidas adaptações em algoritmos conhecidos na literatura para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adaptação foi realizada para resolver o PECPL. Além disso, várias melhorias foram propostas a fim de melhorar a eficiência na resolução das instâncias do problema. Foram propostas uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O algoritmo de Ostergard e a heurística busca tabu com multi-vizinhanças também foram implementados e modificados para refletir o problema abordado no presente trabalho. Porém, a metaheurística Simulated Annealing foi proposta e desenvolvida utilizando-se as mesmas estruturas de vizinhança utilizadas na heurística busca tabu com multivizinhanças. A diferença das duas técnicas está na estratégia de resolução do problema: enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292 instâncias, oriundas de quatro conjuntos referentes à separação de cortes em problemas formulados por meio do uso de programação inteira. Os experimentos foram conduzidos em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolução do PECPL. Posteriormente, o foco foi a resolução do problema do clique de peso máximo (PCPM). Quanto à resolução do PECPL, os resultados obtidos comprovam a eficiência do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar a solução ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras técnicas. Quando a análise dos resultados foi direcionada à resolução do PCPM, todas as técnicas implementadas obtiveram bons resultados, com destaque para a heurística busca tabu com multi-vizinhanças, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em relação às demais abordagens. Como trabalhos futuros, são sugeridos a adoção de operadores lógicos para a representação do grafo no algoritmo de Bron-Kerbosch, a melhoria da versão paralela do algoritmo e o estudo do projeto das metaheurísticas Simulated Annealing e busca tabu.Item Análise e otimização do problema de roteamento de veículos com muitos objetivos e janelas de tempo flexíveis.(2015) Matsueda, Lucas Carvalho Oliveira; Freitas, Alan Robert Resende de; Guimarães, Frederico GadelhaPara explorar a interseção entre problemas de roteamento de veículos propostos na literatura, esta dissertação propõe um problema de roteamento de veículos com muitos objetivos e janelas de tempo flexíveis (MOPRV). É proposta uma abordagem baseada em dois algoritmos evolucionários multiobjetivo (NSGA-II e NSGA-III) e um método para a redução e visualização de objetivos (Árvores de Agregação) é proposta. Através de um estudo sobre a harmonia e conflito entre os objetivos do problema, foi observada a possibilidade de agregação entre os mesmos, reduzindo o problema de seis para três objetivos. Os experimentos demonstram que as soluções para o problema reduzido possuem bons valores para todos os objetivos quando comparado com as soluções do problema completo. Mais ainda, os resultados demonstram que é mais vantajoso visualizar a relação entre os objetivos do MOPRV e em seguida otimizar o problema com menos objetivos do que tentar otimizar diretamente o problema considerando todos os objetivos do MOPRV.