The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Greedy Randomized Adaptive Search Procedures
Abstract
GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this chapter, we first describe the basic components of GRASP. Successful implementation techniques and parameter tuning strategies are discussed and illustrated by numerical results obtained for different applications. Enhanced or alternative solution construction mechanisms and techniques to speed up the search are also described: Reactive GRASP, cost perturbations, bias functions, memory and learning, local search on partially constructed solutions, hashing, and filtering. We also discuss in detail implementation strategies of memory-based intensification and post-optimization techniques using path-relinking. Hybridizations with other metaheuristics, paral lelization strategies, and applications are also reviewed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Genetic Algorithms in Search, Optimization and Machine Learning
Goldberg, D. E., & Robson, D. (1988) · Cited by 18,391
Bollobás, B. (1985) · Cited by 6,196
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Glover, F., & Laguna, M. (1997) · Cited by 5,679
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Mladenović, N., & Hansen, P. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(97)00031-2 · Cited by 4,254
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001
Greedy Randomized Adaptive Search Procedures
Feo, T. A., & Resende, M. G. C. (1995) · Journal of Global Optimization · doi:10.1007/bf01096763 · Cited by 2,778
Self-citationOR-Library: Distributing Test Problems by Electronic Mail
Beasley, J. E. (1990) · Journal of the Operational Research Society · doi:10.1057/jors.1990.166 · Cited by 1,899
Optimization by simulated annealing: Quantitative studies
Kirkpatrick, S. (1984) · Journal of Statistical Physics · doi:10.1007/bf01009452 · Cited by 1,805
The Traveling Salesman Problem
(2019) · Fundamentals of Supply Chain Theory · doi:10.1002/9781119584445.ch10 · Cited by 1,614
A new method for solving hard satisfiability problems
Selman, B., Levesque, H. J., & Mitchell, D. G. M. (1992) · Cited by 1,156
A probabilistic heuristic for a computationally difficult set covering problem
Feo, T. A., & Resende, M. G. C. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90002-3 · Cited by 1,065
Self-citationAn approximate solution for the Steiner problem in graphs
Takahashi, H., & Matsuyama, A. (1980) · Mathematica japonica · Cited by 878
Robust taboo search for the quadratic assignment problem
Taillard, É. D. (1991) · Parallel Computing · doi:10.1016/s0167-8191(05)80147-4 · Cited by 835
Noise strategies for improving local search
Selman, B., Kautz, H., & Cohen, B. (1994) · Cited by 757
The primal-dual method for approximation algorithms and its application to network design problems
Goemans, M. X., & Williamson, D. P. (1996) · PWS Publishing Co. eBooks · Cited by 365
GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
Laguna, M., & Martí, R. (1999) · INFORMS journal on computing · doi:10.1287/ijoc.11.1.44 · Cited by 339
QAPLIB-A quadratic assignment problem library
Burkard, R. E., Karisch, S., & Rendl, F. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90197-4 · Cited by 332
Avoiding local optima in thep-hub location problem using tabu search and GRASP
Klincewicz, J. G. (1992) · Annals of Operations Research · doi:10.1007/bf02060483 · Cited by 234
On maximum clique problems in very large graphs
Abello, J., Pardalos, P., & Resende, M. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/06 · Cited by 221
Self-citationFlight Scheduling and Maintenance Base Planning
Feo, T. A., & Bard, J. F. (1989) · Management Science · doi:10.1287/mnsc.35.12.1415 · Cited by 221
A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
Ribeiro, C. C., Uchoa, E., & Werneck, R. F. (2002) · INFORMS journal on computing · doi:10.1287/ijoc.14.3.228.116 · Cited by 187
Self-citationA Grasp for Aircraft Routing in Response to Groundings and Delays
Argüello, M. F., Bard, J. F., & Yu, G. (1997) · Journal of Combinatorial Optimization · doi:10.1023/a:1009772208981 · Cited by 171
A Grasp for Job Shop Scheduling
Binato, S., Hery, W. J., Loewenstern, D., & Resende, M. G. C. (2002) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-1507-4_3 · Cited by 169
Self-citationFleurent, C., & Glover, F. (1999) · INFORMS journal on computing · doi:10.1287/ijoc.11.2.198 · Cited by 163
The noising method: a new method for combinatorial optimization
Charon, I., & Hudry, O. (1993) · Operations Research Letters · doi:10.1016/0167-6377(93)90023-a · Cited by 160
Probability Distribution of Solution Time in GRASP: An Experimental Investigation
Aiex, R. M., Resende, M. G. C., & Ribeiro, C. C. (2002) · Journal of Heuristics · doi:10.1023/a:1015061802659 · Cited by 153
Self-citationHeuristic-biased stochastic sampling
Bresina, J. L. (1996) · National Conference on Artificial Intelligence · Cited by 139
Local search with perturbations for the prize‐collecting Steiner tree problem in graphs
Canuto, S. A., Resende, M. G. C., & Ribeiro, C. C. (2001) · Networks · doi:10.1002/net.1023 · Cited by 138
Self-citationHashing vectors for tabu search
Woodruff, D. L., & Zemel, E. (1993) · Annals of Operations Research · doi:10.1007/bf02022565 · Cited by 127
Strategies for the Parallel Implementation of Metaheuristics
Cung, V., Martins, S. L., Ribeiro, C. C., & Roucairol, C. (2002) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-1507-4_13 · Cited by 125
Self-citationDevelopments of Variable Neighborhood Search
Hansen, P., & Mladenović, N. (2002) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-1507-4_19 · Cited by 125
Fulkerson, D. R., Nemhauser, G. L., & Trotter, L. E. (1974) · Mathematical programming studies · doi:10.1007/bfb0120689 · Cited by 109
Multi-Start and Strategic Oscillation Methods — Principles to Exploit Adaptive Memory
Glover, F. (2000) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-4567-5_1 · Cited by 97
A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy
Martins, S. L., Resende, M. G. C., Ribeiro, C. C., & Pardalos, P. M. (2000) · Journal of Global Optimization · doi:10.1023/a:1026546708757 · Cited by 92
Self-citationFortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP
Resende, M. G. C., Pitsoulis, L., & Pardalos, P. M. (2000) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(99)00171-7 · Cited by 44
Self-citationOsborne, L. J., & Gillett, B. E. (1991) · INFORMS journal on computing · doi:10.1287/ijoc.3.3.213 · Cited by 43
Cited by
Mladenović, N., & Hansen, P. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(97)00031-2 · Cited by 4,254
Metaheuristics in Combinatorial Optimization
Gendreau, M., & Potvin, J.-Y. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3971-7 · Cited by 2,338
Variable neighborhood search: Principles and applications
Hansen, P., & Mladenović, N. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(00)00100-4 · Cited by 1,902
A survey on optimization metaheuristics
Boussaïd, I., Lepagnot, J., & Siarry, P. (2013) · Information Sciences · doi:10.1016/j.ins.2013.02.041 · Cited by 1,655
Hyper-heuristics: a survey of the state of the art
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013) · Journal of the Operational Research Society · doi:10.1057/jors.2013.71 · Cited by 1,263
Metadata
- Authors
- Resende, M. G. C., & Ribeiro, C. C.
- Venue
- International Series in Operations Research & Management Science
- Publisher
- Kluwer Academic Publishers
- Published
- 2006-02-02
- Pages
- 219-249
- OpenAlex
- W2090275183
- Cited by
- 2,310
- References
- 40
- FWCI
- 212.45
- Type
- book chapter
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.