local search

GRASP and path-relinking: Recent advances and applications

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , ,

    This paper addresses recent advances and application of hybridizations of greedy randomized adaptive search procedures (GRASP) and path-relinking. We present a template for implementing path-relinking as an intensification procedure for GRASP. Enhancements to the procedure, recently described in the literature, are reviewed. The effectiveness of the procedure is illustrated experimentally. Citation AT&T Labs Research Technical … Read more

    A fast swap-based local search procedure for location problems

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Global Optimization Applications Tags , ,

    We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though its worst-case complexity is similar, it can be significantly faster in practice: speedups of … Read more

    A hybrid improvement heuristic for the one-dimensional bin packing problem

  • Dario J. Aloise
  • Adriana C. Alvim
  • Fred Glover
  • Celso C. Ribeiro
    • Categories Combinatorial Optimization, Meta Heuristics Tags , , ,

    We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process … Read more

    A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy

  • Christophe Duhamel
  • Celso C. Ribeiro
  • Mauricio C. Souza
    • Categories Combinatorial Optimization, Graphs and Matroids, Meta Heuristics Tags , , ,

    We describe a new neighborhood structure for the capacitated minimum spanning tree problem. This neighborhood structure is used by a local search strategy, leading to good trade-offs between solution quality and computation time. We also propose a GRASP with path-relinking heuristic. It uses a randomized version of a savings heuristic in the construction phase and … Read more

    Parallel GRASP with path-relinking for job shop scheduling

  • Renata M. Aiex
  • S. Binato
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , , , ,

    In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … Read more