IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v55y2004i9d10.1057_palgrave.jors.2601758.html
   My bibliography  Save this article

An overview of heuristic solution methods

Author

Listed:
  • E A Silver

    (Haskayne School of Business, The University of Calgary)

Abstract

Besides those analysts who are already familiar with a number of heuristic methods, this paper should also be of interest to those analysts and managers who, although not yet aware of specific heuristic approaches, are quite comfortable with the use of mathematical modelling as an aid to decision making. It is concerned with obtaining usable solutions to well-defined mathematical representations of real-world problem situations. Heuristic procedures are defined and reasons for their importance are listed. A wide variety of heuristic methods, including several metaheuristics, are described. In each case, references for further details, including applications, are provided. There is also considerable discussion related to performance evaluation.

Suggested Citation

  • E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    • Handle: RePEc:pal:jorsoc:v:55:y:2004:i:9:d:10.1057_palgrave.jors.2601758
    DOI: 10.1057/palgrave.jors.2601758
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601758
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601758?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Taillard, Eric D. & Gambardella, Luca M. & Gendreau, Michel & Potvin, Jean-Yves, 2001. "Adaptive memory programming: A unified view of metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 1-16, November.
    2. Nonobe, Koji & Ibaraki, Toshihide, 1998. "A tabu search approach to the constraint satisfaction problem as a general problem solver," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 599-623, April.
    3. Klein, Robert, 1999. "Computing lower bounds by destructive improvement - an application to resource-constrained project scheduling," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 10913, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    4. Kolisch, Rainer, 1999. "Resource allocation capabilities of commercial project management software packages," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 7938, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. Rosing, K. E. & ReVelle, C. S. & Rolland, E. & Schilling, D. A. & Current, J. R., 1998. "Heuristic concentration and Tabu search: A head to head comparison," European Journal of Operational Research, Elsevier, vol. 104(1), pages 93-99, January.
    6. Rainer Kolisch, 1999. "Resource Allocation Capabilities of Commercial Project Management Software Packages," Interfaces, INFORMS, vol. 29(4), pages 19-31, August.
    7. van Houtum, G. J. & Zijm, W. H. M., 1991. "Computational procedures for stochastic multi-echelon production systems," International Journal of Production Economics, Elsevier, vol. 23(1-3), pages 223-237, October.
    8. Keith L. McRoberts, 1971. "A Search Model for Evaluating Combinatorially Explosive Problems," Operations Research, INFORMS, vol. 19(6), pages 1331-1349, October.
    9. Tsubakitani, Shigeru & Evans, James R., 1998. "An empirical study of a new metaheuristic for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 104(1), pages 113-128, January.
    10. Gordon C. Armour & Elwood S. Buffa, 1963. "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science, INFORMS, vol. 9(2), pages 294-309, January.
    11. Charles Fleurent & Fred Glover, 1999. "Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 198-204, May.
    12. Dimitris Bertsimas & Ramazan Demir, 2002. "An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems," Management Science, INFORMS, vol. 48(4), pages 550-565, April.
    13. Bright, J. G. & Johnston, K. J., 1991. "Whither VIM? -- A developer's view," European Journal of Operational Research, Elsevier, vol. 54(3), pages 357-362, October.
    14. Jatinder N. D. Gupta & Randall S. Sexton & Enar A. Tunc, 2000. "Selecting Scheduling Heuristics Using Neural Networks," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 150-162, May.
    15. L M Gambardella & É D Taillard & M Dorigo, 1999. "Ant colonies for the quadratic assignment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(2), pages 167-176, February.
    16. Richard M. Karp, 1977. "Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 209-224, August.
    17. Jeffrey I. McGill & Garrett J. van Ryzin, 1999. "Revenue Management: Research Overview and Prospects," Transportation Science, INFORMS, vol. 33(2), pages 233-256, May.
    18. Marin, Angel & Salmeron, Javier, 1996. "Tactical design of rail freight networks. Part II: Local search methods with statistical analysis," European Journal of Operational Research, Elsevier, vol. 94(1), pages 43-53, October.
    19. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    20. Yagiura, Mutsunori & Ibaraki, Toshihide, 1996. "The use of dynamic programming in genetic algorithms for permutation problems," European Journal of Operational Research, Elsevier, vol. 92(2), pages 387-401, July.
    21. Shore, Haim, 1999. "Optimal solutions for stochastic inventory models when the lead-time demand distribution is partially specified," International Journal of Production Economics, Elsevier, vol. 59(1-3), pages 477-485, March.
    22. Gabriel R. Bitran & Horacio H. Yanasse, 1984. "Deterministic Approximations to Stochastic Production Problems," Operations Research, INFORMS, vol. 32(5), pages 999-1018, October.
    23. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    24. Hillier, Mark S., 2002. "The costs and benefits of commonality in assemble-to-order systems with a (Q,r)-policy for component replenishment," European Journal of Operational Research, Elsevier, vol. 141(3), pages 570-586, September.
    25. CORNUEJOLS, Gérard & FISHER, Marshall L. & NEMHAUSER, George L., 1977. "Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms," LIDAM Reprints CORE 292, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    26. Edward A. Silver, 1976. "A Simple Method of Determining Order Quantities in Joint Replenishments Under Deterministic Demand," Management Science, INFORMS, vol. 22(12), pages 1351-1361, August.
    27. B. Golden & L. Bodin & T. Doyle & W. Stewart, 1980. "Approximate Traveling Salesman Algorithms," Operations Research, INFORMS, vol. 28(3-part-ii), pages 694-711, June.
    28. Hertz, Alain & Widmer, Marino, 2003. "Guidelines for the use of meta-heuristics in combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 151(2), pages 247-252, December.
    29. Silver, Edward A. & Victor, R. & Vidal, V. & de Werra, Dominique, 1980. "A tutorial on heuristic methods," European Journal of Operational Research, Elsevier, vol. 5(3), pages 153-162, September.
    30. Hasegawa, Mikio & Ikeguchi, Tohru & Aihara, Kazuyuki & Itoh, Kohji, 2002. "A novel chaotic search for quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 139(3), pages 543-556, June.
    31. Zanakis, Stelios H. & Evans, James R. & Vazacopoulos, Alkis A., 1989. "Heuristic methods and applications: A categorized survey," European Journal of Operational Research, Elsevier, vol. 43(1), pages 88-110, November.
    32. F Della Croce & V T'kindt, 2002. "A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(11), pages 1275-1280, November.
    33. Grossman, Thomas Jr. & Rohleder, Thomas R. & A. Silver, Edward, 2000. "A negotiation aid for fixed-quantity contracts with stochastic demand and production," International Journal of Production Economics, Elsevier, vol. 66(1), pages 67-76, June.
    34. C. West Churchman, 1970. "Operations Research as a Profession," Management Science, INFORMS, vol. 17(2), pages 37-53, October.
    35. Jonsson, Henrik & Silver, Edward A., 1996. "Some insights regarding selecting sets of scenarios in combinatorial stochastic problems," International Journal of Production Economics, Elsevier, vol. 45(1-3), pages 463-472, August.
    36. Craig A. Tovey, 2002. "Tutorial on Computational Complexity," Interfaces, INFORMS, vol. 32(3), pages 30-61, June.
    37. Marshall L. Fisher, 1980. "Worst-Case Analysis of Heuristic Algorithms," Management Science, INFORMS, vol. 26(1), pages 1-17, January.
    38. Stelios H. Zanakis & James R. Evans, 1981. "Heuristic “Optimization”: Why, When, and How to Use It," Interfaces, INFORMS, vol. 11(5), pages 84-91, October.
    39. Candace Arai Yano & Hau L. Lee, 1995. "Lot Sizing with Random Yields: A Review," Operations Research, INFORMS, vol. 43(2), pages 311-334, April.
    40. Voudouris, Christos & Tsang, Edward, 1999. "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 469-499, March.
    41. Marshall L. Fisher, 1985. "An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, INFORMS, vol. 15(2), pages 10-21, April.
    42. Richard Ehrhardt, 1979. "The Power Approximation for Computing (s, S) Inventory Policies," Management Science, INFORMS, vol. 25(8), pages 777-786, August.
    43. Klein, Robert & Scholl, Armin, 1999. "Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 112(2), pages 322-346, January.
    44. Bell, Peter C., 1991. "Visual interactive modelling: The past, the present, and the prospects," European Journal of Operational Research, Elsevier, vol. 54(3), pages 274-286, October.
    45. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    46. Baum, Sanford & Carlson, Robert, 1979. "On solutions that are better than most," Omega, Elsevier, vol. 7(3), pages 249-255.
    47. Srinivas Bollapragada & Thomas E. Morton, 1999. "Myopic Heuristics for the Random Yield Problem," Operations Research, INFORMS, vol. 47(5), pages 713-722, October.
    48. B Dominguez-Ballesteros & G Mitra & C Lucas & N-S Koutsoukis, 2002. "Modelling and solving environments for mathematical programming (MP): a status review and new directions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(10), pages 1072-1092, October.
    49. Jonsson, Henrik & Silver, Edward A., 1989. "Common component inventory problems with a budget constraint: Heuristics and upper bounds," Engineering Costs and Production Economics, Elsevier, vol. 18(1), pages 71-81, October.
    50. Chelouah, Rachid & Siarry, Patrick, 2000. "Tabu Search applied to global optimization," European Journal of Operational Research, Elsevier, vol. 123(2), pages 256-270, June.
    51. L. G. Mitten, 1970. "Branch-and-Bound Methods: General Formulation and Properties," Operations Research, INFORMS, vol. 18(1), pages 24-34, February.
    52. John J. Bartholdi, III & Loren K. Platzman, 1988. "Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space," Management Science, INFORMS, vol. 34(3), pages 291-305, March.
    53. Andrew J. Mason & David M. Ryan & David M. Panton, 1998. "Integrated Simulation, Heuristic and Optimisation Approaches to Staff Scheduling," Operations Research, INFORMS, vol. 46(2), pages 161-175, April.
    54. J-F Cordeau & M Gendreau & G Laporte & J-Y Potvin & F Semet, 2002. "A guide to vehicle routing heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 512-522, May.
    55. L R Weatherford & P P Belobaba, 2002. "Revenue impacts of fare input and demand forecast accuracy in airline yield management," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(8), pages 811-821, August.
    56. S. Rajagopalan, 2002. "Make to Order or Make to Stock: Model and Application," Management Science, INFORMS, vol. 48(2), pages 241-256, February.
    57. H. Shore, 1999. "A general solution of the preventive maintenanceproblem when data are right‐censored," Annals of Operations Research, Springer, vol. 91(0), pages 251-261, January.
    58. Robert W. Haessler, 1983. "Developing an Industrial-Grade Heuristic Problem-Solving Procedure," Interfaces, INFORMS, vol. 13(3), pages 62-71, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Martí, Rafael & Sevaux, Marc & Sörensen, Kenneth, 2025. "Fifty years of metaheuristics," European Journal of Operational Research, Elsevier, vol. 321(2), pages 345-362.
    2. Daniel Martins & Gabriel M. Vianna & Isabel Rosseti & Simone L. Martins & Alexandre Plastino, 2018. "Making a state-of-the-art heuristic faster with data mining," Annals of Operations Research, Springer, vol. 263(1), pages 141-162, April.
    3. Michel Gendreau & Jean-Yves Potvin, 2005. "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 189-213, November.
    4. Michael Brusco & Hans-Friedrich Köhn, 2009. "Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer;The Psychometric Society, vol. 74(3), pages 457-475, September.
    5. Jamal Ouenniche & Prasanna K. Ramaswamy & Michel Gendreau, 2017. "A dual local search framework for combinatorial optimization problems with TSP application," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1377-1398, November.
    6. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    7. Daniels, Richard L. & Rummel, Jeffrey L. & Schantz, Robert, 1998. "A model for warehouse order picking," European Journal of Operational Research, Elsevier, vol. 105(1), pages 1-17, February.
    8. Rolland, Erik & Schilling, David A. & Current, John R., 1997. "An efficient tabu search procedure for the p-Median Problem," European Journal of Operational Research, Elsevier, vol. 96(2), pages 329-342, January.
    9. Hauser, John R. & Urban, Glen L. & Weinberg, Bruce D., 1992. "Time flies when you're having fun : how consumers allocate their time when evaluating products," Working papers 3439-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    10. Sharma, R.R.K. & Berry, V., 2007. "Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort," European Journal of Operational Research, Elsevier, vol. 177(2), pages 803-812, March.
    11. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    12. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    13. Awi Federgruen & Nan Yang, 2008. "Selecting a Portfolio of Suppliers Under Demand and Supply Risks," Operations Research, INFORMS, vol. 56(4), pages 916-936, August.
    14. Marshall L. Fisher, 2004. "Comments on ÜThe Lagrangian Relaxation Method for Solving Integer Programming ProblemsÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1872-1874, December.
    15. El-Ghazali Talbi, 2016. "Combining metaheuristics with mathematical programming, constraint programming and machine learning," Annals of Operations Research, Springer, vol. 240(1), pages 171-215, May.
    16. Rosing, K. E. & ReVelle, C. S. & Schilling, D. A., 1999. "A gamma heuristic for the p-median problem," European Journal of Operational Research, Elsevier, vol. 117(3), pages 522-532, September.
    17. Michael Brusco & Hans-Friedrich Köhn, 2008. "Optimal Partitioning of a Data Set Based on the p-Median Model," Psychometrika, Springer;The Psychometric Society, vol. 73(1), pages 89-105, March.
    18. Voelkel, Michael A. & Sachs, Anna-Lena & Thonemann, Ulrich W., 2020. "An aggregation-based approximate dynamic programming approach for the periodic review model with random yield," European Journal of Operational Research, Elsevier, vol. 281(2), pages 286-298.
    19. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    20. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:55:y:2004:i:9:d:10.1057_palgrave.jors.2601758. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.