@Article{HelHad00a, author = "S. Abdinnour-Helm and S.W. Hadley", title = "Tabu search based heuristics for multi-floor facility layout", journal = "International Journal of Production Research", volume = "38", pages = "365--383", year = "2000", annote = "Two two-stage heuristics are proposed for solving the multi-floor facility layout problem. {GRASP}/TS applies a {GRASP} to find the initial layout and tabu search to refine the initial layout, based on total inter/intra-floor costs. Computational tests indicate that {GRASP}/TS compares favorably with heuristics that do not rely on exact algorithms.", } @article{AhmOsm03a, author = {S. Ahmadi and I.H. Osman}, title = {Greedy random adaptive memory programming search for the capacitated clustering problem}, journal = {European Journal of Operational Research}, volume = {}, number = {}, year = {2003}, pages = {}, note = {To appear.}, annote = "Given a set $N$ of $n$ points, the capacitated clustering problem consists in finding a partition of $N$ in $p$ clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of $p$ centers that minimizes the total scatter of points allocated to these centers. In order to introduce some sort of memory into the pure {GRASP} framework, the authors propose a GRAMPS framework, which is an hybrid of {GRASP} and AMP (Adaptive Memory Programming). Local search procedure is descent based on a restricted $\lambda$-interchange neighborhood." } @Article{AhuOrlTiw00a, author = "R.K. Ahuja and J.B. Orlin and A. Tiwari", title = "A greedy genetic algorithm for the quadratic assignment problem", journal = "Computers and Operations Research", volume = "27", pages = "917--934", year = "2000", annote = "This report suggests a genetic algorithm for the QAP that incorporates the construction phase of the {GRASP} for QAP of Li, Pardalos, and Resende (1994) to generate the initial population.", } @Article{AieBinRes03a, author = "R.M. Aiex and S. Binato and M.G.C. Resende", title = "Parallel {GRASP} with path-relinking for job shop scheduling", journal = "Parallel Computing", volume = {29}, pages = {393--430}, year = "2003", annote = "In this paper, a parallel {GRASP} with path-relinking as intensification strategy for the job shop problem is described using some ideas proposed in the {GRASP} of Binato et al. (2002). During the construction phase, the restricted candidate list is made up of elements that among those that can be added to the current partial solution without causing any infeasibility have greedy function value above a specified threshold. While in Binato et al. (2002) the greedy function value of an operation $k$ is the makespan resulting from the inclusion of $k$ to the already scheduled operations, in this paper the authors propose the so called {\em time-remaining} function. It is a new greedy function to be used in conjunction with the makespan and that favors operations from jobs having long remaining processing times. The authors employ the two exchange local searches used in Binato et al. (2002). Two parallelization strategies are proposed: an independent and a cooperative strategy. The independent strategy shows a sub-linear speedup, while the cooperative one shows an approximate linear speedup, thus confirming that the extra time spent for processes communication is compensated by an increase in solution quality.", } @techreport{AieResParTor00a, author = "R.M. Aiex and M.G.C. Resende and P.M. Pardalos and G. Toraldo", title = "{GRASP} with path relinking for the three-index assignment problem", institution = "AT\&T Labs Research", address = "Florham Park, NJ 07733", year = "2000", note = {To appear in {\em INFORMS J. on Computing}.}, annote = "This paper describes variants of {GRASP} with path relinking for the three index assignment problem (AP3). Computational results show clearly that this {GRASP} for AP3 benefits from path relinking and that the variants considered in this paper compare well with previously proposed heuristics for this problem. The authors also show that the random variable time to target solution, for all proposed {GRASP} with path relinking variants, fits a two-parameter exponential distribution. To illustrate the consequence of this, one of the variants of {GRASP} with path relinking is shown to benefit from parallelization." } @Article{AktKil99a, author = {M.S. Akturk and K. Kili\c{c}}, title = {Generating short-term observations for space mission projects}, journal = {J. of Intelligent Manufacturing}, volume = {10}, pages = {387--404}, annote = {Generating short-term observations for space mission projects is basically a scheduling problem. It consists in generating short-term observation schedules of Hubble Space Telescope (HST) such that the scientific return is maximized. In this paper, a new dispatching rule and a set of local search based algorithms are proposed. The algorithms are based on the filtered beam search and include a {GRASP} and a Simulated Annealing to construct short-term observation schedules of space mission projects, mainly for NASA HST. The greedy function used in the proposed {GRASP} is based start time and completion time of scheduled observations The local search is based on a simple exchange neighborhood structure and is not performed at each {GRASP} iteration, but only if the schedule output from the construction phase seems to be promising.}, year = {1999} } @techreport{AlvGonDeA03a, author = {A.M. \'Alvarez and J. L. Gonz\'alez and K. De-Alba}, title = {Scatter search for a network design problem}, number = {PISIS-2003-02}, institution = {Universidad Aut\'onoma de Nuevo Le\'on, Facultad de Ingenier\'{\i}a Mec\'anica y El\'ectrica, Divisi\'on de Posgrado en Ingenier\'{\i}a de Sistemas, Mexico.}, annote = {The authors propose a Scatter Search (SS) algorithm for solving a fixed charge capacitated multicommodity network design problems on undirected networks. SS is an evolutionary method that constructs new solutions by combining others. It performs the following three basic steps: 1) generation of a population $P$; 2) extraction of a reference set $R$; 3) combination of elements from $R$ and updating of $R$. The different ways SS can be implemented consists in designing several different subroutines, including a Diversification Generation Method (DGM). The DGM proposed in this paper is a {GRASP} with some memory features incorpored. More in detail, in the {GRASP} DGM for each commodity a certain number $q$ of shortest paths between each origin-destination pair are kept as RCL elements. The local search consists basically in sorting the chosen paths and possibly exchange some of them in order to get a better distribution.}, year = {2003} } @Article{AlvParTam02a, author = "R. Alvarez-Vald\'es and A. Paraj\'on and J.M. Tamarit", title = "A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems", journal = "Computers \& Operations Research", volume = "29", pages = "925--947", year = "2002", annote = "This paper proposes several heuristics for the two-dimensional cutting problem, in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. One algorithm is a tabu search procedure, while two further heuristics are simple constructive procedures based on bounds obtained by solving one-dimensional knapsack problems. Those two constructive procedures have been then embedded in a {GRASP}, whose local search looks for an improving solution by merging two adjacent rectangles (i.e. two rectangles that have a common side) into a single rectangle and trying to cut it with a greater value. The authors have also implemented a path-relinking procedure as post-optimization phase for improving the final results of all above cited algorithms.", } @techreport{AndRas03a, author = "M. Andronescu and B. Rastegari", title = {{Motif-{GRASP} and {Motif-ILS}: {T}wo new stochastic local search algorithms for motif finding}}, institution = "Computer Science Department, University of British Columbia", address = "Vancouver, Canada", annote = {A motif is a conserved pattern thought to exist in several biosequences such as DNA, RNA, and proteins. Given $N$ biosequences $S_i$, $i=1,2,\ldots,N$ with length $n_i$ and a number $L$, the problem of motif finding consists in finding a sequence $M_i$ of length $L$ for each biosequence such that their similarity grade is maximized. A candidate solution is represented as a set $a_1,a_2,\ldots,a_N$, where $a_k\in [1,n_k-L+1]$, for each $k\in [1,N]$. All candidate solutions correspond to all possible combinations of $a_i$ assignment. Several greedy functions are proposed based on the a weight defined on the starting point of the motif. One of such greedy function is the ratio between the probability of generating a certain subsequence $x$ from the current motif and the probability of generating $x$ from the background. The neighborhood structure used in the local search procedure is a $1$-exchange.}, year = "2003" } @inproceedings{AreVan00a, author = {S. Areibi and A. Vannelli}, title = {Efficient Hybrid Search Techniques For Circuit Partitioning}, booktitle = {{IEEE 4th World Multiconference on Circuits, Systems, Communications \& Computers}}, city = {Athens, Greece}, month = {July}, year = {2000}, annote = "In this paper, for solving the problem the authors apply a simulated annealing, a tabu search, a {GRASP}, and a genetic algorithm. Two further search techniques are also proposed as hybrids, where a {GRASP} and a genetic algorithm are used for generating good initial partitions." } @Article{BarKonYu02a, author = "J.F. Bard and G. Kontoravdis and G. Yu", title = "A branch-and-cut procedure for the vehicle routing problem with time windows", journal = "Transportation Science", volume = "36", pages = "250--269", year = "2002", annote = "In this paper, the authors propose a branch-and-cut algorithm for finding the minimum number of homogeneous vehicles needed for visiting a set of costumers (nodes of the input graph) requiring the same type of service subject to time windows and capacity constraints. They obtain feasible solutions and/or upper bounds by applying a {GRASP}.", } @inproceedings{CanCorHerSan02a, author = "J.R. Cano and O. Cord\'on and F. Herrera and L. S\'anchez", title = "A {GRASP} Algorithm for clustering", editor = {F. J. Garijo and J.C.R. Santos and M. Toro}, booktitle = {Advances in Artificial Intelligence - IBERAMIA 2002, 8th Ibero-American Conference on AI, Seville, Spain, November 12-15, 2002, Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {2527}, pages = {214--223}, year = {2002}, isbn = {3-540-00131-X}, annote = "A {GRASP} for cluster analysis is described. Construction is done using a randomized greedy Kaufman procedure and local search uses the $K$-means algorithm. High quality solutions are found for benchmark problems. The best solutions are found with a hybid {GRASP}/$K$-means with Kaufman initialization." } @Article{CanResRib01a, author = "S.A. Canuto and M.G.C. Resende and C.C. Ribeiro", title = "Local search with perturbation for the prize-collecting {Steiner} tree problems in graphs", journal = "Networks", volume = "38", pages = "50--58", year = "2001", annote = "Several local search strategies have been investiged in this paper for solving the prize-collecting {Steiner} tree problems in graphs, including path relinking, VNS, and a {GRASP} that uses some cost perturbations. The greedy choice takes into account the input edge weights, while the local search routine defines as neighborhood of a solution $T(X)$ the set of all minimum spanning trees $T(X')$, where $X'$ differs from $X$ for exactly one node.", } @incollection{CarBak02a, author = "C. Carreto and B. Baker", title = "A {GRASP} interactive approach to the vehicle routing problem with backhauls", booktitle = "Essays and surveys in metaheuristics", editor = "C.C. Ribeiro and P. Hansen", publisher = "Kluwer Academic Publishers", pages = "185--200", year = "2002", annote = "The incorporation of interactive tools into heuristic algorithms is investigated. A {GRASP} is used in the route construction and improvement phase. The construction phase is implemented in a clustering heuristic that constructs the routes by clustering the remaining customers according to the vehicles defined by seeds while applying the $3$-opt heuristic to reduce the total distance traveled by each vehicle. The greedy function takes into account routes with smallest insertion cost and costumers with biggest difference between the smallest and the second smallest insertion costs and smallest number of routes they can traverse. As the local search phase, $3$-opt is used." } @mastersthesis{Chr02a, author = "L.M. Christofoletti", title = "M\'etodos de rein\'{\i}cio aplicados ao seq{\"u}enciamento em uma m\'aquina com tempos de prepara\c c\~ao e data de entrega", school = "Departamento de Engenharia de Sistemas, Universidade Estadual de Campinas", address = "Brazil", annote = "This thesis discusses about applications of {GRASP} and its variants to the problem of minimizing the total tardiness of jobs in a single machine with sequence dependent setup times. An innovative aspect of this thesis is the introduction in the multistart framework with some memory strategies for storing a population of high quality solutions. In Portuguese.", month = "April", year = "2002" } @Incollection{SouDuhRib03a, author = "M.C. de Souza and C. Duhamel and C.C. Ribeiro", title = "A {GRASP} heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy", booktitle = "Metaheuristics: Computer decision-making", editor = "M.G.C. Resende and J.P. de Sousa", publisher = {Kluwer Academic Publishers}, pages = "627--658", year = "2003", annote = "In this paper, the authors propose a novel local search that applies reduction techniques to speed up the search and uses a new path-based neighborhood structure, defined by path exchanges. Each edge $e$ having extremities into two different components of $T$ is considered a candidate for being inserted into the current tree, but immediately discarded (reduction strategy) if it does not respect some conditions that depend on three criteria and that, if verified, ensure that it is unlikely that the involved edge can be part of an improving move. One criterion is based on the relative cost $r(e)$ of the edge $e$, i.e. the difference between the weight of a minimum spanning tree and the weight of a constrained spanning tree in which the presence of $e$ is enforced. Another criterion is based on the decomposition of the cost of a move defined by the candidate edge $e$ for insertion and by a candidate path $(p--q)$ (from $p$ to $q$) for removal. The cost $\Delta$ of such a move can be written as $\Delta=\Delta_1+\Delta_2$, where $\Delta_1$ is associated with the edge exchanges that will generate the component containing $e$ in the new solution, while $\Delta_2$ is given by the reconnection of the remaining elements along the candidate path $(p--q)$. The third criterion does not compute $\Delta_2$ and uses a lower bound $\delta\leq \delta_1$: a candidate edge $e$ is discarded if $\delta\geq 0$ for each possible candidate path $(p--q)$ that can be used in conjunction with $e$. The authors also propose a {GRASP} that uses the same neighborhood structure as the previously described local search and some short term memory elements of tabu search and that implements a randomized version of a savings heuristic in the construction phase. A post-optimization phase is realized by applying a path-relinking procedure.", } @Article{DelDiaFerOrt99a, author = "H. Delmaire and J.A. D\'{\i}az and E. Fern\'andez and M. Ortega", title = "Reactive {GRASP} and tabu search based heuristics for the single source capacitated plant location problem", journal = "INFOR", volume = "37", pages = "194--225", year = "1999", annote = "The single source capacitated plant location problem is a discrete location problem that takes into account capacities in the plants to be opened and imposes that clients be served from a single open plant. The authors propose a hybrid heuristic that embeds reactive {GRASP} in a tabu search algorithm as a diversification method that provides elite i candidate sets. Intensification is also done.", } @Article{FesParResRib02a, author = "P. Festa and P.M. Pardalos and M.G.C. Resende and C.C. Ribeiro", title = "Randomized heuristics for the {MAX-CUT} problem", journal = "Optimization Methods and Software", volume = "7", pages = {1033--1058}, year = "2002", annote = {Given an undirected graph with edge weights, the max-cut problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. For solving this well-known NP-hard problem, the authors propose and test a {GRASP}, a variable neighborhood search (VNS), a path relinking intensification heuristic, and new hybrid heuristics that combine {GRASP}, VNS, and path relinking. The greedy function of the pure {GRASP} is related to the sum of the weights of the edges in each cut. Let $(S,\bar S)$ be the current cut solution and let $v\in V$ be a vertex, then the pure {GRASP} local search associates to $v$ either the neighbor $(S \setminus \{v\}, \bar S\cup \{v\})$ if $v \in S$, or the neighbor $(S \cup \{v\}, \bar S \setminus \{v\})$ otherwise. Computational results indicate that the proposed randomized heuristics find near-optimal solutions. On a set of standard test problems, new best known solutions were produced for many of the instances.}, } @Article{LagMar99a, author = "M. Laguna and R. Mart\'{\i}", title = "{GRASP} and path relinking for $2$-layer straight line crossing minimization", journal = "{INFORMS} Journal on Computing", volume = "11", pages = "44--52", year = "1999", annote = "This paper develops a {GRASP} for the problem of minimizing straight line crossings in a $2$-layer graph. The method proposed can be coupled with a path relinking strategy to search for improved outcomes. The greedy criterion of the construction phase is based on the degree of the vertices and a value based restricted candidate list is used. Each step of the improvement phase consists in selecting each vertex to be considered for a move. A probabilistic selection rule is used such that vertices with high degree are more likely to be selected first at each step of this process. This paper incorporates to {GRASP} a path relinking strategy to search for improved outcomes. Path relinking generates new solutions by exploring trajectories connecting high quality solutions. Starting from an {\em initiating solution}, path relinking generates a path in the neighborhood space that leads toward the other solutions, called {\em guiding solutions}. This is accomplished by selecting moves that introduce attributes contained in the guiding solutions.", } @techreport{MarMig03a, author = "Y. Marinakis and A. Migdalas", title = "Expading neighborhood {GRASP} for the {T}raveling {S}alesman {P}roblem", institution = "Technical University of Crete", address = "Chania 73100, Greece", annote = {For the traveling salesman problem the authors of this paper propose a {GRASP} that includes tour improvement methods. One among the simplest tour improvement method is the nearest neighbor in which at each step the salesman moves to the city nearest to the current one.}, year = "2003" } @Article{MarResRibPar00b, author = "S.L. Martins and M.G.C. Resende and C.C. Ribeiro and P.M. Pardalos", title = "A parallel {GRASP} for the {Steiner} tree problem in graphs using a hybrid local search strategy", journal = "Journal of Global Optimization", volume = "17", year = "2000", pages = "267--283", annote = "This paper presents a {GRASP} for the Steiner problem in graphs. The construction phase is based on the Mehlhorn distance network heuristic, which consists of computing the modified distance network graph and using Kruskal's algorithm to solve the minimum spanning tree problem for the resulting graph. The local search is done by using a combination of key-path based local search and node based local search.", } @inproceedings{OliParRes03a, author = {C.A. Oliveira and P.M. Pardalos and M.G.C. Resende}, title = {{{GRASP} with path-relinking for the {QAP}}}, booktitle = {{Proceedings of the Fifth Metaheuristics International Conference (MIC2003)}}, editor = {T. Ibaraki and Y. Yoshitomi}, city = {Kyoto, Japan}, pages = {57-1 -- 57-6}, annote = {In this paper, a {GRASP} using path relinking as intensification phase is proposed for the quadratic assignment problem. The {GRASP} has essentially the same implementation as in Li et al. (1994).}, year = {2003} } @article{PacVel03a, author = {J. Pacheco and O. Valencia}, title = {Design of hybrids for the minimum sum-of-squares clustering problem}, journal = {Computational Statistics and Data Analysis}, volume = {43}, pages = {235--248}, annote = {For the non-hierchical clustering problem under the criterion of minimum sum-of-squares clustering a set of heuristics are proposed that incorporate genetic operators, local search, and tabu search. The authors compare their algorithms with other heuristic approaches including a {GRASP} on a set of test problems.}, year = {2003} } @Article{PalTom02a, author = "G. Palubeckis and A. Tomkevicius", title = "{GRASP} implementations for the unconstrained binary quadratic optimization problem", journal = "Information Technology and Control", volume = "24", pages = "14--20", year = "2002", annote = "In this paper, the authors propose a classical {GRASP} framework and an enhanced {GRASP} that uses a simple tabu search as local search. Numerical results show that the enhancement introduced in the classical {GRASP} implementation produces higher quality solutions.", } @Article{ParRamResLi97a, author = "P.M. Pardalos and K.G. Ramakrishnan and M.G.C. Resende and Y. Li", title = "Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem", journal = "SIAM Journal on Optimization", volume = "7", pages = "280--294", year = "1997", annote = "This paper describes a branch \& bound algorithm for the quadratic assignment problem which uses a {GRASP} to compute upper bounds.", } @article{PinPlaCamMar04a, author = "E. Pi{\~n}ana and I. Plana and V. Campos and R. Mart\'{\i}", title = "{GRASP} and path relinking for the matrix bandwidth minimization", journal = "European J. of Operational Research", volume = "153", number = "1", pages = "200--210", year = "2004", annote = {Given matrix $A=\{a_{ij}\}_{n\times n}$, the matrix bandwidth minimization problem consists in finding a permutation of the rows and columns of $A$ that keeps the nonzero elements in a band lying as close as possible to the main diagonal of $A$. The problem can be easily stated in terms of graph optimization problem, considering a vertex for each row and a vertex for each column and connecting vertex $i$ to vertex $j$ through an edge either if $a_{ij}\not= 0$ or $a_{ji}\not= 0$. Then, the original problem is equivalent to the problem of finding a labeling $f$ of the vertices that minimizes the maximum difference between labels of adjacent vertices. The authors propose a {GRASP}, in which the greedy choice favors vertices having a maximum number of adjacent labeled vertices. The local search phase is based on swap moves that exchange labels of a pair of vertices.}, } @Article{PraRib00a, author = "M. Prais and C.C. Ribeiro", title = "Reactive {GRASP}: {A}n application to a matrix decomposition problem in {TDMA} traffic assignment", journal = "INFORMS Journal on Computing", volume = "12", pages = "164--176", year = "2000", annote = "This paper describes a {GRASP} for matrix decomposition problem arising in the context of traffic assignment in communication satellites. A geostationary communication satellite has a number of spot beam antennas covering geographically distributed areas. According to the slot switching configuration on the on-board switch, the uplink traffic received at the satellite has to be immediately sent to ground areas through a set of transponders. The slot switching configurations are determined through the solution of a time slot assignment problem, which is equivalent to the decomposition of a nonnegative traffic matrix into the sum of a family of switching mode matrices. A refinement of {GRASP}, called Reactive {GRASP}, is proposed. Instead of using a fixed value for the basic parameter that defines the restrictiveness of the candidate list during the construction phase, Reactive {GRASP} self-adjusts the parameter value according to the quality of the solutions previously found. The local search phase of the {GRASP} proposed is based on a new neighborhood, defined by constructive and destructive moves.", } @inproceedings{ResRib03b, author = {M.G.C. Resende and C.C. Ribeiro}, title = {{{GRASP} and path-relinking: Recent advances and applications}}, booktitle = {{Proceedings of the Fifth Metaheuristics International Conference (MIC2003)}}, editor = {T. Ibaraki and Y. Yoshitomi}, city = {Kyoto, Japan}, pages = {T6-1 -- T6-6}, annote = {In this paper, the basic components of {GRASP} and path relinking are described. Their successful implementations are described in detail and several real world problems application are reported.}, year = {2003} } @article{ResWer04a, author = {M.G.C. Resende and R.F. Werneck}, title = {A hybrid heuristic for the p-median problem}, journal = {Journal of Heuristics}, volume = {10}, pages = {59--88}, year = {2004}, annote = {Given a set of $m$ potential facilities and $n$ cosumers, the $p$-median problem consists in finding a subset of $p$ facilities ($p\leq m$) such that the cost of serving all costumers is minimized. The authors present in this paper a {GRASP} with path relinking as intensification and post-optimization phase. The greedy function chooses most profitable facilities, but several different constructive algorithms have been embedded into the {GRASP} framework: pure random, random plus greedy, randomized greedy, proportional greedy, proportional worst, and sample greedy. The methods are distinguishable much more by their computational time than the quality of the solutions they provide.} } @techreport{ResWer03c, author = {M.G.C. Resende and R.F. Werneck}, title = {{A hybrid multistart heuristic for the uncapacitated facility location problem}}, institution = {Internet and Network Systems Research Center, AT\&T Labs Research}, address = {Florham Park, NJ}, year = {2003}, annote = {In this paper, a multistart heuristic is proposed based on an idea already proposed by the authors in Resende and Werneck (2004). The algorithm consists in two phases. The first phase is a multistart procedure that builds a randomized solution from which to apply a local search routine and a path relinking. The second is a post-optimization phase realized by applying path relinking over the whole elite set.}, note = {Submitted to {\em European J. of Operational Research}.} } @Article{RibUchWer02a, author = "C.C. Ribeiro and E. Uchoa and R.F. Werneck", title = "A hybrid {GRASP} with perturbations for the {Steiner} problem in graphs", journal = "INFORMS Journal on Computing", volume = "14", pages = "228--246", year = "2002", annote = "In this hybrid {GRASP} here proposed for the {Steiner} problem in graphs, the {GRASP} construction phase is replaced by either one of several different construction procedures that apply weight perturbation strategies combining intensification and diversification elements. The local search phase circularly explores two different strategies. The first defines a simple node-based neighborhood structure. The second one uses a key-path-based neighborhood, where a key-node is a {Steiner} node with degree at least three and a key-path is a {Steiner} tree $T$ whose extremities are either terminals of key-node (if there are any, intermediate nodes are {Steiner} node with degree two in $T$). An adaptive path-relinking procedure is at the end used as a post-optimization strategy.", } @techreport{RibVia03a, author = "C.C. Ribeiro and D.S. Vianna", title = {A {GRASP}/{VND} heuristic for the phylogeny problem using a new neighborhood structure}, institution = {Department of Computer Science, Catholic U. of Rio de Janeiro}, address = "Rio de Janeiro, Brazil", annote = {The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps, where a phylogeny is a tree that relates taxonomic units based on their similarity over a set of characters. The authors propose a hybridization of {GRASP} and VND. The greedy criterion is based on insertions of new taxons into a branch of the current partial solution. The local search phase uses a VND strategy and a new neighborhood structure, called $2$-SPR and based on the iterative removing of branches on the cuurent solution.}, year = "2003" } @Incollection{SouMacOch03a, author = "M.J.F. Souza and N. Maculan and L.S. Ochi", title = "A {GRASP}-tabu search algorithm for school timetabling problems", booktitle = "Metaheuristics: Computer decision-making", editor = "M.G.C. Resende and J.P. de Sousa", publisher = {Kluwer Academic Publishers}, pages = "659--672", year = "2003", annote = "In this paper, a hybrid approach is proposed that uses a {GRASP} greedy randomized construction phase for obtaining a feasible solution to be hopefully improved applying a tabu search. The greedy choice takes into account first the number of available teachers and then the activity degree of each teacher. A timetable is represented as a $m\times q$ matrix $Q$ of integer values, such that each row $i$ represents the weekly schedule of teacher $i$ and $q_{ik}$ represents the activity of teacher $i$ in pariod $k$. A neighbor of a timetable $Q$ is a timetable $Q'$, obtained from $Q$ simply by changing two different and nonnegative values of a give row of $Q$.", } @techreport{AieRes03a, author = {R.M. Aiex and M.G.C. Resende}, title = {Parallel strategies for {GRASP} with path-relinking}, institution = {Internet and Network Systems Research Center, AT\&T Labs Research}, address = {Florham Park, NJ}, year = {2003}, annote = { This paper analyzes two parallel strategies for GRASP with path-relinking and proposes a criterion to predict parallel efficiency based on experiments with a sequential implementation of the algorithm. Independent and cooperative parallel strategies are described and implemented for the 3-index assignment problem and the job-shop scheduling problem. The computational results for independent parallel strategies are shown to qualitatively behave as predicted by the criterion. }, } @techreport{ResRib03c, author = {M.G.C. Resende and C.C. Ribeiro}, title = {{{GRASP} and path-relinking: Recent advances and applications}}, institution = {Internet and Network Systems Research Center, AT\&T Labs Research}, address = {Florham Park, NJ}, year = {2003}, annote = { This paper addresses recent advances and application of hybridizations of greedy randomized adaptive search procedures (GRASP) and path-relinking. A template for implementing path-relinking as an intensification procedure for GRASP is presented. Enhancements to the procedure, recently described in the literature, are reviewed. The effectiveness of the procedure is illustrated experimentally. }, }