Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Greedy Randomized Adaptive Search Procedure <s> We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP + PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies. The first uses anode-based neighborhood for local search, while the second uses a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as apost-optimization strategy. Computational results on a broad set of benchmark problems illustrate the effectiveness and the robustness of our heuristic, which is very competitive when compared to other approximate algorithms. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Greedy Randomized Adaptive Search Procedure <s> Today, a variety of heuristic approaches are available to the operations research practitioner. One methodology that has a strong intuitive appeal, a prominent empirical track record, and is trivial to efficiently implement on parallel processors is GRASP (Greedy Randomized Adaptive Search Procedures). GRASP is an iterative randomized sampling technique in which each iteration provides a solution to the problem at hand. The incumbent solution over all GRASP iterations is kept as the final result. There are two phases within each GRASP iteration: the first intelligently constructs an initial solution via an adaptive randomized greedy function; the second applies a local search procedure to the constructed solution in hope of finding an improvement. In this paper, we define the various components comprising a GRASP and demonstrate, step by step, how to develop such heuristics for combinatorial optimization problems. Intuitive justifications for the observed empirical behavior of the methodology are discussed. The paper concludes with a brief literature review of GRASP implementations and mentions two industrial applications. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Greedy Randomized Adaptive Search Procedure <s> This work treats a more constrained School Timetabling Problem (STP). It consists of scheduling a set of lectures and teachers in a prefixed period of time, satisfying a set of operational requirements. We applied a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic, combined with a path-relinking improvement. During execution of the GRASP heuristic, the local search procedure interleaves two types of movements. In addition, the path-relinking strategy was itself enhanced by a local search procedure. The algorithms were tested with real instances and proved to be good approaches to solve this problem. Although some restrictions are specific to Brazilian educational institutions, the same ideas can inspire similar approaches for solving the STP in other situations. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Greedy Randomized Adaptive Search Procedure <s> Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used. <s> BIB004
Greedy randomized adaptive search procedure (GRASP) was introduced by Resende in 1995. GRASP BIB002 is a multi start or iterative procedure consisting of 2 phases. One is Construction phase and another is a local search phase. The construction phase creates a feasible solution by applying a greedy randomized criterion which is then improved until a local minimum is found during the local search phase the best overall solution is returned as the result. Construction phase can be illustrated by 2 basic types. One is Dynamic constructive heuristic and other one is Randomization. In constructive heuristic the elements that are not included in the partial solution are estimated with a greedy function and the list of best elements are kept in a so called restricted candidate list (RCL). Through randomization any element is randomly chosen and included in the partial solution thus resulting in a diversity of solutions. GRASP is memory less algorithm. proposed a hybrid GRASP to solve steiner problems in graphs using weight perturbation and adaptive path relinking heuristic (HGP-PR) BIB001 .  introduced continuous GRASP (C-GRASP) by extending GRASP from discrete optimization to continuous global optimization  .  proposed GRASP with an evolutionary path relinking to solve the network migration problem. The authors proposed a metaheuristic resulting from the hybridization of GRASP, path relinking, evolutionary path relinking  . Arnaldo and Rafael (2010) applied GRASP heuristic, merged with a path relinking for solving school timetabling problem BIB003 . Yannis (2012) proposed an enhanced version of GRASP called Multiple Phase Neighborhood Search GRASP (MPNS-GRASP) for solving vehicle routing problem. In this method, a stopping criterion based on Lagrangean relaxation and sub gradient optimization is applied. Also, another strategy known as the Circle Restricted Local Search Moves strategy was used for expanding the neighborhood search BIB004 .