Navegando por Autor "Martins, Simone de Lima"
Agora exibindo 1 - 3 de 3
Resultados por página
Opções de Ordenação
Item Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads.(2018) Haddad, Matheus Nohra; Pinto, Rafael Martinelli; Vidal, Thibaut Victor Gaston; Martins, Simone de Lima; Ochi, Luiz Satoru; Souza, Marcone Jamilson Freitas; Hartl, RichardWe consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard problem linked with a variety of applications for bulk product transportation, bike-sharing systems and inventory re-balancing. This problem is notoriously difficult due to the interaction of two challenging vehicle routing attributes, “pickups and deliveries” and “split deliveries”. This possibly leads to optimal solutions of a size that grows exponentially with the instance size, containing multiple visits per customer pair, even in the same route. To solve this problem, we propose an iterated local search metaheuristic as well as a branch-and-price algorithm. The core of the metaheuristic consists of a new large neighborhood search, which reduces the problem of finding the best insertion combination of a pickup and delivery pair into a route (with possible splits) to a resource-constrained shortest path and knapsack problem. Similarly, the branch-and-price algorithm uses sophisticated labeling techniques, route relaxations, pre-processing and branching rules for an efficient resolution. Our computational experiments on classical single-vehicle instances demonstrate the excellent performance of the metaheuristic, which produces new best known solutions for 92 out of 93 test instances, and outperforms all previous algorithms. Experimental results on new multi-vehicle instances with distance constraints are also reported. The branch-and-price algorithm produces optimal solutions for instances with up to 20 pickup-and-delivery pairs, and very accurate solutions are found by the metaheuristic.Item Planejamento de ordens de manutenção preventiva por meio de simheurística.(2023) Coelho, Diego Gomes; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Martins, Simone de Lima; Fonseca, George Henrique Godim daEste trabalho aborda o problema de alocação de tarefas de manutenção preventiva em um planejamento de 52 semanas. Dado um conjunto de tarefas de manutenção a serem realizadas em um conjunto de máquinas, um conjunto de equipes e um horizonte de planejamento, o problema consiste em designar cada tarefa a uma equipe em um determinado instante do horizonte de planejamento visando a minimizar o numero de equipes necessárias e maximizar o número de tarefas não executadas. Para tratá-lo, inicialmente foi desenvolvido um algoritmo construtivo capaz de testar automaticamente 384 regras de construção e retornar a melhor regra para cada instância. Comparado com a literatura, esse algoritmo construtivo gerou soluções de boa qualidade em tempo computacional muito menor que os algoritmos meta-heurísticos existentes. Foi desenvolvido também o algoritmo meta-heurístico Iterated Local Search (ILS) para aprimorar as soluções geradas pelo método construtivo. O algoritmo ILS atingiu o melhor resultado em 97% das instancias avaliadas. No entanto, tanto o método ILS quanto os demais métodos da literatura para o problema são determinísticos e não levam em consideração as incertezas que podem ocorrer durante a execução de uma tarefa, o que pode resultar em um planejamento insuficiente com um tempo de execução total mais longo do que o previsto. Para contornar essa situação, foi proposto um algoritmo simheurístico, nomeado SIM-ILS. Embora ele apresente um custo levemente superior ao método ILS determinístico, o SIM-ILS e capaz de captar as incertezas da operação de manutenção, tornando suas soluções mais aderentes ao ambiente industrial.Item Revisitando o revenimento paralelo : computação de alto desempenho e aplicação em pesquisa operacional.(2024) Almeida, André Luis Barroso; Carvalho, Marco Antonio Moreira de; Lima, Joubert de Castro; Carvalho, Marco Antonio Moreira de; Lima, Joubert de Castro; Souza, Marcone Jamilson Freitas; Coelho, Igor Machado; Soares, Leonardo Cabral da Rocha; Martins, Simone de LimaNos últimos 35 anos, a computação paralela vem chamando a atenção da comuni- dade científica, especialmente para solucionar problemas complexos de otimização que necessitam de uma quantidade expressiva de poder computacional. A utilização de arquiteturas paralelas (multi-core e distribuídas) é uma alternativa natural e efetiva para acelerar as metaheurísticas e aumentar a qualidade das soluções geradas. Neste contexto, visando contribuir para a área de metaheurísticas paralelas, este estudo apresenta uma revisão sistemática de literatura ressaltando as particularida- des das publicações que adotam a computação de alto desempenho para projetar, implementar e experimentar metaheurísticas baseadas em trajetória. Ademais, essa revisão desempenhou um papel crucial para o desenvolvimento de uma nova me- taheurística paralela baseada no método conhecido como parallel tempering, pouco explorado na área de pesquisa operacional, que apresenta resultados expressivos na área de simulação e se integra de forma sinérgica com plataformas multiprocessadas modernas. Identificado durante a revisão, o parallel tempering revelou-se como uma metaheurística mais promissora para mitigar as lacunas identificadas na literatura. Assim, a nova metaheurística paralela desenvolvida foi minuciosamente avaliada em três estudos de caso envolvendo problemas difíceis de otimização abordados recentemente na literatura, tanto em termos de qualidade da solução quanto de tempo computacional. Além disso, uma API contendo a implementação do parallel tempering paralelo foi proposta e disponibilizada para facilitar futuras implementa- ções e popularizar sua utilização. Os resultados da avaliação ratificaram o potencial do parallel tempering, apresentando desempenho comparável ao estado da arte em um dos estudos de caso e superando-o nos outros dois, com redução de até 43,13% no valor das melhores soluções conhecidas. Quanto ao tempo computacional, os valores obtidos não se mostraram proibitivos em ambientes industriais reais, consolidando a eficácia da abordagem proposta.