Navegando por Autor "Martins, Alexandre Xavier"
Agora exibindo 1 - 20 de 31
Resultados por página
Opções de Ordenação
Item Um algoritmo híbrido para resolução de problemas binários.(2015) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Sérgio Ricardo deEste trabalho apresenta um método híbrido, denominado HGVPRLB, para resolver problemas lineares binários. O método combina os procedimentos Greedy Randomized Adaptive Search Procedures -- GRASP, Variable Neighborhood Descent -- VND, propagação de restrições, e cortes Local branching. Como em todo algoritmo GRASP, o método HGVPRLB apresenta duas fases, que interagem entre si até que o tempo limite seja atingido. A primeira fase visa a construção de uma solução inicial; a segunda, por sua vez, visa ao refinamento dessa solução construída. Na fase de construção, é utilizado o resolvedor CBC e um procedimento de propagação de restrições, de forma a gerar uma solução inicial para o problema. O resolvedor CBC relaxa as variáveis binárias, isto é, atribui o valor de cada variável no intervalo real [0,1]. O procedimento propagação de restrições possui a finalidade de verificar se existe solução viável ao se fixar uma determinada variável no valor 1. Se esta solução existir, ele poderá retornar, ainda, um conjunto de possíveis fixações das demais variáveis. Na fase de refinamento são utilizados cortes Local branching controlados pelo procedimento VND até que um tempo previamente definido seja atingido. Os cortes Local Branching utilizam um resolvedor de programação linear inteira como uma ferramenta caixa-preta para explorar eficientemente subespaços das soluções do problema. O método desenvolvido foi aplicado a um conjunto de problemas binários da biblioteca MIPLIB 2010 com o intuito de verificar sua capacidade de obter soluções viáveis de qualidade variando-se o tempo de processamento. Os experimentos computacionais realizados mostraram que, quando o tempo de processamento aumenta, o método consegue aumentar tanto o número de soluções viáveis quanto a qualidade delas. Além disso, o método desenvolvido se mostrou superior a outro método da literatura, bem como a dois outros resolvedores de código aberto nesses dois indicadores de avaliação.Item Algoritmos simulated annealing e GRASP para o planejamento de aulas de um departamento.(2009) Martins, Alexandre Xavier; Castro, Raphael Reis Mauro de; Souza, Marcone Jamilson FreitasEste trabalho trata do problema de programação de horários em escolas. Dada sua natureza combinatória, ele é resolvido por meio de dois algoritmos metaeurísticos, um baseado em Simulated Annealing e outro em GRASP. Ambos possuem parâmetros auto-adaptativos, dispensando, assim, a calibragem destes. Para testálos são utilizados dados reais do departamento de uma universidade. São apresentados resultados computacionais, comparando-se as soluções produzidas pelos algoritmos propostos com aquelas geradas manualmente pela instituição de ensino. Os resultados obtidos mostram a eficiência dos métodos desenvolvidos perante as soluções manuais e a superioridade do Simulated Annealing, em comparação com o GRASP para as instâncias tratadas.Item Análise de desempenho de um sistema de emergência médica via simulação e otimização : o caso do SAMU das cidades de Ouro Preto e Mariana – Minas Gerais.(2021) Morais, Thaise Regina Matos de; Gomes Júnior, Aloísio de Castro; Rodrigues, Lásara Fabrícia; Gomes Júnior, Aloísio de Castro; Rodrigues, Lásara Fabrícia; Martins, Alexandre Xavier; Pinto, Luiz RicardoO tempo de resposta de um Sistema Médico de Emergência (SME) é uma métrica preponderante de eficiência, visto que atender rapidamente as vítimas de urgência e emergência, prestando-lhes o atendimento pré-hospitalar, determina a minimização de sequelas permanentes ao mesmo tempo que maximiza a taxa de sobrevida do paciente. Este trabalho objetiva avaliar o desempenho do SAMU (Serviço de Atendimento Móvel de Urgência) das cidades de Ouro Preto e Mariana, através de seus indicadores de desempenho. Para tanto, foi desenvolvido um sistema computacional, em linguagem Python, e a partir deste, simulou-se diferentes cenários, que levavam em consideração diferentes políticas de despacho, aumento da demanda, realocação de unidades de resgate, entre outros, com objetivo de verificar o impacto no tempo de resposta do sistema. A esta estrutura, foi integrada a metaheurística Simulated Annealing, objetivando alcançar um resultado “otimizado”, que se apresentasse como o melhor dentre os cenários obtidos através da simulação, com o tempo de resposta médio do sistema reduzido. Considera-se este objetivo bastante relevante, em virtude da criticidade inerente às atividades do SME, onde sua eficiência determina a sobrevivência e/ou melhores condições de saúde do paciente. Ademais, um SME bem estruturado também resulta em uma melhor aplicabilidade de seus limitados recursos. Por se tratar de um sistema complexo, que envolve inúmeras variáveis de natureza estocástica, fazê-lo via simulação se mostra atraente e justificável. Os resultados obtidos demostraram que uma nova configuração, com estratégicas localizações de bases e respectivas alocações das ambulâncias, impactaria em uma redução de aproximadamente 10% no tempo de resposta de sistema. Demonstraram ainda, a importância de se analisar de forma conjunta ao número de habitantes, diferentes variáveis, como extensão territorial, complexidades geográficas e infraestruturas locais, ao se determinar o número necessário de ambulâncias para se atender as demandas de urgência no serviço pré-hospitalar.Item Branch-and-cut and GRASP with hybrid local search for the multi-level capacitated minimum spanning tree problem.(2009) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre XavierWe propose efficient algorithms to compute tight lower bounds and high quality upper bounds for the Multi-Level Capacitated Minimum Spanning Tree problem. We first develop a branch-and-cut algorithm for the problem. This algorithm is able to solve instances of medium size and to provide tight lower bounds for larger ones. We then use the branch-and-cut within GRASP to evaluate subproblems during the search. The computational experiments conducted have improved best known lower and upper bounds on benchmark instancesItem Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.(2012) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre Xavier; Fukasawa, RicardoWe propose algorithms to compute tight lower boundsand high quality upper bounds (UBs) for the multilevelcapacitated minimum spanning tree problem. We firstdevelop a branch-and-cut algorithm, introducing somenew features: (i) the exact separation of cuts correspond-ing to some master equality polyhedra found in theformulation; (ii) the separation of Fenchel cuts, solvingLPs considering all the possible solutions restricted tosmall portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solvingto optimality subproblems corresponding to partial solu-tions. The computational experiments were conductedon 450 benchmark instances from the literature. Numer-ical results show improved best known (UBs) for almostall instances that could not be solved to optimality.Item A computational study of a decomposition approach for the dynamic two-level uncapacitated facility location problem with single and multiple allocation.(2021) Oliveira, Paganini Barcellos de; Camargo, Ricardo Saraiva de; Miranda Junior, Gilberto de; Martins, Alexandre XavierThis work presents a computational study for two variants of a dynamic or multi-period two-level uncapacitated facility location problem. In this problem, first-level plants serve different demand patterns of scattered clients over a planning horizon via second-level facilities. In the first variant, second-level facilities can be supplied by only one of the plants (single assignment); whereas, in the second, they can be served by more than one of the first-level plants (multiple allocation). As the demands vary over time, the different operating settings for plants and facilities, and client assignments need to be sought in each period to serve demands at minimal installation and transportation costs. Since both problem variants arise naturally in the context of logistics systems, it is of interest to have solution methods at hand for practitioners and researchers. To provide such a tool, this work presents an efficient decomposition approach to solve the two problem variants. It relies on Benders decomposition reformulations combined with a greedy randomized adaptive search procedure and different Benders cut separation procedures. The devised solution framework outperformed CPLEX and its Benders built-in algorithm on solving two different challenging large-scale instance sets.Item Construção de um protótipo framework e seu uso na resolução do problema de roteamento de veículos com frotas heterogêneas e janelas de tempo.(2005) Neves, Tiago Araújo; Souza, Marcone Jamilson Freitas; Martins, Alexandre XavierItem Experiências com Ssimulated Annealing e Busca Tabu na resolução do problema de alocação de salas.(2002) Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Araújo, Cássio Roberto deEste trabalho trata do problema de alocação de salas. Uma vez que este problema é NP-difícil, muitos métodos heurísticos têm sido propostos para resolvê-lo. Simulated Annealing (SA) e Busca Tabu (BT) são exemplos de tais métodos que têm sido aplicados com sucesso na resolução deste problema. Esta classe de heurísticas encontra uma boa solução melhorando uma alocação inicial através de técnicas de pesquisa em vizinhança. Contrariamente às heurísticas convencionais, SA e BT permitem movimentos de piora como forma de escapar de ótimos locais. Neste artigo relata-se uma experiência com a utilização destas técnicas e propõe-se uma técnica híbrida SA+TS, a qual combina as características mais apropriadas de SA e BT de forma a obter um procedimento mais eficaz. A eficiência dessa combinação é avaliada comparando-a com as versões puras dos métodos envolvidos.Item Genils-TS-CL-PR : um algoritmo heurístico para resolução do problema de roteamento de veículos com coleta e entrega simultânea.(2012) Silva, Thaís Cotta Barbosa da; Cruz, Raphael Carlos; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Coelho, Vitor Nazário; Mine, Marcio TadayukiThis work addresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We propose the algorithm GENILS-TS-CL-PR for solving it. This algorithm combines the heuristic procedures Cheapest In- sertion, Cheapest Insertion with multiple routes, GENIUS, Iterated Local Search (ILS), Variable Neighborhood Descent (VND), Tabu Search (TS) and Path Relin king (PR). The first three procedures aim to obtain a good initial solution, and the VND and TS are used as local search methods for ILS. TS is applied after some iterations without any improvement through of the VND. The PR procedure is performed for each ILS iteration and it connects a local optimum with an elite solution generated during the search. The algorithm also uses a strategy to re- duce the number of solutions evaluated in the solution space. It was tested on benchmark instances taken from the literature and it was able to generate high quality solutions.Item GENVNS-TS-CL-PR: a heuristic approach for solving the vehicle routing problem with simultaneous pickup and delivery.(2012) Cruz, Raphael Carlos; Silva, Thaís Cotta Barbosa da; Souza, Marcone Jamilson Freitas; Coelho, Vitor Nazário; Mine, Marcio Tadayuki; Martins, Alexandre XavierThis work addresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). Due to its complexity, we propose a heuristic algorithm for solving it, so-called GENVNS-TS-CL-PR. This algorithm combines the heuristic procedures Cheapest Insertion, Cheapest Insertion with multiple routes, GENIUS, Variable Neighborhood Search (VNS), Variable Neighborhood Descent (VND), Tabu Search (TS) and Path Relinking (PR). The first three procedures aim to obtain an good initial solution, and the VND and TS are used as local search methods for VNS. TS is called after some iterations without any improvement through of the VND. The PR procedure is called after each VNS iteration and it connects a local optimum with an elite solution generated during the search. The algorithm uses an strategy based on Candidate List to reduce the number of solutions evaluated in the solution space. The algorithm was tested on benchmark instances taken from the literature and it was able to generate high quality solutions.Item Geração de colunas para o problema de roteamento e atribuição de comprimentos de onda.(2012) Martins, Alexandre Xavier; Duhamel, Christophe; Mahey, Philippe; Souza, Maurício Cardoso de; Saldanha, Rodney RezendeNeste trabalho, apresenta-se um estudo sobre o Problema de Roteamento e Atribuição de Comprimentos de Onda em redes ópticas WDM independentemente da topologia física subjacente. Por se tratar de um problema NP difícil muitos métodos exatos e heurísticos vem sendo estudados para a sua resolução. Apresentamos o estudo da versão do problema onde o objetivo é maximizar o número de requisições atendidas. Inicialmente é feita uma revisão da literatura apresentando alguns modelos matemáticos formulados para a resolução do problema. Depois apresentamos uma estratégia baseada em geração de colunas que combina métodos já existentes. Os resultados computacionais sobre instâncias consagradas da literatura comprovam a eficiencia do métodoItem Grasp com reconexão por caminhos para o problema eixo-raio com alocação simples.(2012) Martins, Alexandre Xavier; Costa, Yasmine de Melo; Camargo, Ricardo Saraiva deEste trabalho apresenta uma heurística eficiente desenvolvida para o projeto de redes eixo- raio com alocação simples. Este é um problema importante com muitas aplicações nos sistemas de transporte de carga e passageiros, e sistemas de telecomunicação. Um GRASP eficiente, combinado com três diferentes tipos de estruturas de vizinhança, é usado para resolver o problema. Além disso, um esquema baseado em reconexão por caminhos é apresentado a fim de aprimorar a qualidade das soluções do GRASP. O GRASP com reconexão por caminhos proposto claramente superou três conhecidas soluções heurísticas da literatura para as instâncias testadas. A abordagem por reconexão por caminhos desempenhou um papel importante na robustez do algoritmo proposto, tanto em termos de tempo computacional quanto na qualidade das soluções.Item Heuristique VND-ILS pour le problème de routage et d’affectation de longueur d’onde.(2011) Martins, Alexandre Xavier; Duhamel, Christophe; Mahey, Philippe; Souza, Maurício Cardoso de; Saldanha, Rodney RezendeItem HMS : a hybrid multi-start algorithm for solving binary linear programs.(2018) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Coelho, Vitor Nazário; Martins, Alexandre XavierThis work presents a hybrid multi-start algorithm for solving generic binary linear programs. This algorithm, called HMS, is based on a Multi-Start Metaheuristic and combines exact and heuristic strategies to address the problem. The initial solutions are generated by a strategy that applies linear programming and constraint propagation for defining an optimized set of fixed variables. In order to refine them, a local search, guided by a Variable Neighborhood Descent heuristic, is called, which, in turn, uses Local Branching cuts. The algorithm was tested in a set of binary LPs from the MIPLIB 2010 library and the results pointed out its competitive performance, resulting in a promising matheuristic.Item A hybrid VNS algorithm for solving the multi-level capacitated minimum spanning tree problem.(2018) Campos, Jean Carlos Tiburcio; Martins, Alexandre Xavier; Souza, Marcone Jamilson FreitasThis work addresses the multi-level capacitated minimum spanning tree (MLCMST) problem. It consists of finding a minimal cost spanning tree such that the flow to be transferred from a central node (root) to the other nodes is bounded by the edge capacities. In this paper, a hybrid algorithm, combining the Variable Neighborhood Search (VNS) metaheuristic and one mathematical programming formulation of the literature, is used for solving it. The formulation is used to give an initial solution to VNS. Five neighborhoods are used for exploring the solution space. Results show that the VNS is able to improve the initial solutions and to obtain small gap solutions for all instance sets.Item Método de decomposição de Benders generalizado para seleção estocástica de portfólios.(2023) Barcelos, Braulio Frances; Miranda Junior, Gilberto de; Silva, Thiago Augusto de Oliveira; Miranda Junior, Gilberto de; Silva, Thiago Augusto de Oliveira; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Camargo, Ricardo Saraiva deEste trabalho aborda o Problema de Seleção de Portfólios de Média-Variância. O problema contém um conjunto de ativos financeiros, no qual cada ativo possui um peso associado a sua escolha e um valor de retorno. O Retorno é obtido pela média dos retornos passados dos ativos ponderados pelos respectivos pesos. Outro parâmetro considerado no problema é o risco associado a cada ativo, obtido pela matriz variância-covariância. O objetivo é encon- trar a melhor combinação dos ativos ponderados pelos pesos associados, buscando reduzir o risco e aumentar o retorno. Para resolver o problema eficientemente, foram utilizados os algoritmos Conjunto Ativo e o Método de Projeção em Caixa. Além disso, foi utilizada uma técnica de pré-processamento para redução do tamanho da instância. Também, foi proposta uma reformulação do problema, utilizando-se a versão estocástica do Método de Decomposição de Benders Generalizado. Resultados computacionais mostraram a superio- ridade do Método de Projeção em Caixa em relação ao Algoritmo do Conjunto Ativo. Capaz de resolver instâncias com até 1.200 ativos, o Método de Projeção em Caixa superou o Algoritmo do Conjunto Ativo em tempo de solução e número de iterações, sendo 83 vezes mais rápido que o Algoritmo do Conjunto Ativo considerando o pior caso. Adicionalmente, as soluções derivadas do Método de Projeção em Caixa foram confrontadas com aquelas geradas pelo resolvedor de Programação Quadrática do Gurobi. Os resultados revelaram que o maior desvio observado pelo Método de Projeção em Caixa foi da ordem de 10−9 . Além disso, o código do Método de Projeção em Caixa, quando integrado ao Método de Decomposição de Benders Generalizado, foi testado e comparado com o software Gurobi considerando uma instância composta por 50 ativos e 500 cenários. O Método de Projeção em Caixa apresentou tempos de solução inferiores em comparação com aqueles obtidos pelo resolvedor de Programação Quadrática do Gurobi.Item Métodos meta-heurísticos para a resolução do problema de sequenciamento de ordens de manutenção preventiva de longo prazo.(2023) Santos, Arthur Almeida; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Oliveira, Paganini Barcellos de; Noronha, Thiago Ferreira deO sucesso de uma empresa requer o bom funcionamento e a confiabilidade de seus sistemas com máquinas e equipamentos em bom estado. Para isto, é essencial um bom plano de manutenção preventiva, que tende a ficar mais complexo conforme aumenta o número de equipamentos e o horizonte de planejamento. O presente trabalho tem como objetivo desenvolver algoritmos meta-heurísticos eficientes para tratar o Problema de Planejamento de Ordens de Manutenção Preventiva de Longo Prazo (PPOMPLP). O trabalho se inicia com o desenvolvimento de uma heurística construtiva e de alocação, seguido do desenvolvimento de heurísticas de busca local e de meta-heurísticas, bem como a avaliação do desempenho dos algoritmos propostos frente à outros trabalhos da literatura. Para a calibragem e validação das meta-heurísticas foram resolvidas instâncias fictícias pequenas. Após a calibragem, as meta-heurísticas foram aplicadas na resolução de instâncias maiores e a real. Como resultado, o Iterated Local Search (ILS) foi a meta-heurística de melhor performance e o resultado obtido para a instância real foi 40,5% melhor que o apresentado na literatura.Item Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem.(2016) Duhamel, Christophe; Mahey, Philippe; Martins, Alexandre Xavier; Saldanha, Rodney Rezende; Souza, Maurício Cardoso deThe routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.Item Um modelo de programação matemática para otimizar a composição de lotes de minério de ferro da mina Cauê da CVRD.(2006) Moraes, Edilaila Fernandes; Alves, José Maria do Carmo Bento; Souza, Marcone Jamilson Freitas; Cabral, Ivo Eyer; Martins, Alexandre XavierEsse trabalho tem seu enfoque no problema de blendagem de produtos de minério de ferro, estocados nos pátios da mina Cauê, da Companhia Vale do Rio Doce, em Itabira, Minas Gerais, para a composição de lotes. Pro-põe-se um modelo de programação linear por metas que visa a determinar os locais de retomada dos produtos estocados, de tal forma que a mistura atenda aos limites de especificações de qualidade e quantidade preestabelecidos pelo cliente e satisfaça as restrições operacionais dos pátios. O modelo de programação matemática desenvolvido foi implementado no modelador e otimiza-dor LINGO 9.0, interfaceando com planilhas do EXCEL 2000, possibilitando a utilização e exportação de dados em um ambiente familiar à empresa de mineração. O sistema desenvolvido foi validado comparando-se os resultados obtidos com os produzidos manualmente pela empresa. Os resultados computacionais apresentados comprovaram que é possível prover uma melhora na composição dos lotes através do modelo proposto.Item Modelo matemático para resolver o problema de alocação de turnos de funcionários : um caso real.(2017) Barrel, Mayara Alves; Moreira, Rafael Correia; Martins, Alexandre XavierO desafio de se escalar pessoas em turnos flexíveis em uma empresa consiste na elaboração de um cronograma para alocação de recursos necessários para executar uma atividade em um determinado período de tempo. Este trabalho tem o objetivo de propor uma otimização na programação de horários de turnos das faxineiras de um supermercado, através de um modelo matemático baseado no método de Programação Linear Inteira Mista, atendendo às restrições do Departamento de Recursos Humanos e às leis trabalhistas (CLT). O modelo foi desenvolvido no Lingo em interface com o MS Excel 2013. Os dados de entrada foram iterados no Lingo até que uma solução ótima fosse encontrada. A solução obtida pelo modelo apresentou um resultado satisfatório para o supermercado, pois minimizou a variação de horas trabalhadas durante a semana e distribuiu as funcionárias de maneira uniforme nas escalas de horário.