DECEA - Departamento de Ciências Exatas e Aplicadas

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/551

Navegar

Filtros

2002 - 200932010 - 20125

Configurações

Autor: search.filters.author.Martins, Alexandre Xavier

Resultados da Pesquisa

Agora exibindo 1 - 8 de 8
  • Nenhuma Miniatura Disponível
    Item
    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 de
    Este 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.
  • Nenhuma Miniatura Disponível
    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 Tadayuki
    This 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.
  • Nenhuma Miniatura Disponível
    Item
    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 de
    Este 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.
  • Nenhuma Miniatura Disponível
    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 Rezende
    Neste 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étodo
  • Nenhuma Miniatura Disponível
    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 Rezende
  • Nenhuma Miniatura Disponível
    Item
    Novas formulações para o problema da árvore geradora mínima capacitada em níveis.
    (2005) Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Souza, Maurício Cardoso de
  • Nenhuma Miniatura Disponível
    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 Xavier
    We 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 instances
  • Nenhuma Miniatura Disponível
    Item
    Variable neighborhood descent with iterated local search for routing and wavelength assignment.
    (2012) Martins, Alexandre Xavier; Duhamel, Christophe; Mahey, Philippe; Saldanha, Rodney Rezende; Souza, Maurício Cardoso de
    In this work we treat the Routing and Wavelength Assignment (RWA) with focus on minimizing the number of wavelengths to route demand requests. Lightpaths are used to carry the traffic optically between origin-destination pairs. The RWA is subjected to wavelength continuity constraints, and a particular wavelength cannot be assigned to two different lightpaths sharing a common physical link. We develop a Variable Neighborhood Descent (VND) with Iterated Local Search (ILS) for the problem. In a VND phase we try to rearrange requests between subgraphs associated to subsets of a partition of the set of lightpath requests. In a feasible solution, lightpaths belonging to a subset can be routed with the same wavelength. Thus, the purpose is to eliminate one subset of the partition. When VND fails, we perform a ILS phase to disturb the requests distribution among the subsets of the partition. An iteration of the algorithm alternates between a VND phase and a ILS phase. We report computational experiments that show VND-ILS was able to improve results upon powerful methods proposed in the literature.