HANDBOOK OF METAHEURISTICS
INTERNATIONAL SERIES IN
OPERATIONS RESEARCH & MANAGEMENT SCIENCE
Frederick S. Hillier, Series Editor
Stanford University
Weyant, J. / ENERGY AND ENVIRONMENTAL POLICY MODELING
Shanthikumar, J.G. & Sumita, U. / APPLIED PROBABILITY AND STOCHASTIC PROCESSES
Liu, B. & Esogbue, A.O. / DECISION CRITERIA AND OPTIMAL INVENTORY PROCESSES
Gal, T., Stewart, T.J., Hanne, T. / MULTICRITERIA DECISION MAKING: Advances in MCDM
Models, Algorithms, Theory, and Applications
Fox, B.L. / STRATEGIES FOR QUASI-MONTE CARLO
Hall, R.W. / HANDBOOK OF TRANSPORTATION SCIENCE
Grassman, W.K. / COMPUTATIONAL PROBABILITY
Pomerol, J.-C. & Barba-Romero, S. / MULTICRITERION DECISION IN MANAGEMENT
Axsäter, S. / INVENTORY CONTROL
Wolkowicz, H., Saigal, R., & Vandenberghe, L. / HANDBOOK OF SEMI-DEFINITE
PROGRAMMING: Theory, Algorithms, and Applications
Hobbs, B.F. & Meier, P. / ENERGY DECISIONS AND THE ENVIRONMENT: A Guide to the Use of
Multicriteria Methods
Dar-El, E. / HUMAN LEARNING: From Learning Curves to Learning Organizations
Armstrong, J.S. / PRINCIPLES OF FORECASTING: A Handbook for Researchers and Practitioners
Balsamo, S., Personé, V., & Onvural, R. / ANALYSIS OF QUEUEING NETWORKS WITH
Bouyssou, D. et al. / EVALUATION AND DECISION MODELS: A Critical Perspective
Hanne, T. / INTELLIGENT STRATEGIES FOR META MULTIPLE CRITERIA DECISION MAKING
Saaty, T. & Vargas, L. / MODELS, METHODS, CONCEPTS and APPLICATIONS OF THE
ANALYTIC HIERARCHY PROCESS
Chatterjee, K. & Samuelson, W. / GAME THEORY AND BUSINESS APPLICATIONS
Hobbs, B. et al. / THE NEXT GENERATION OF ELECTRIC POWER UNIT COMMITMENT
BLOCKING
MODELS
Vanderbei, R.J. / LINEAR PROGRAMMING: Foundations and Extensions, 2nd Ed.
Kimms, A. / MATHEMATICAL PROGRAMMING AND FINANCIAL OBJECTIVES FOR
SCHEDULING PROJECTS
Baptiste, P., Le Pape, C. & Nuijten, W. / CONSTRAINT-BASED SCHEDULING
Feinberg, E. & Shwartz, A. / HANDBOOK OF MARKOV DECISION PROCESSES: Methods and
Ramík, J. & Vlach, M. / GENERALIZED CONCAVITY IN FUZZY OPTIMIZATION AND
Applications
DECISION ANALYSIS
Bernard Roy
Song, J. & Yao, D. / SUPPLY CHAIN STRUCTURES: Coordination, Information and Optimization
Kozan, E. & Ohuchi, A. / OPERATIONS RESEARCH/MANAGEMENT SCIENCE AT WORK
Bouyssou et al. / AIDING DECISIONS WITH MULTIPLE CRITERIA: Essays in Honor of
Cox, Louis Anthony, Jr. / RISK ANALYSIS: Foundations, Models and Methods
Dror, M., L’Ecuyer, P. & Szidarovszky, F. / MODELING UNCERTAINTY: An Examination of
Stochastic Theory, Methods, and Applications
Dokuchaev, N. / DYNAMIC PORTFOLIO STRATEGIES: Quantitative Methods and Empirical Rules
for Incomplete Information
Sarker, R., Mohammadian, M. & Yao, X. / EVOLUTIONARY OPTIMIZATION
Demeulemeester, R. & Herroelen, W. / PROJECT SCHEDULING: A Research Handbook
Gazis, D.C. / TRAFFIC THEORY
Zhu, J. / QUANTITATIVE MODELS FOR PERFORMANCE EVALUATION AND BENCHMARKING
Ehrgott, M. & Gandibleux, X. / MULTIPLE CRITERIA OPTIMIZATION: State of the Art Annotated
Bienstock, D. / Potential Function Methods for Approx. Solving Linear Programming Problems
Matsatsinis, N.F. & Siskos, Y. / INTELLIGENT SUPPORT SYSTEMS FOR MARKETING
Bibliographical Surveys
DECISIONS
Alpern, S. & Gal, S. / THE THEORY OF SEARCH GAMES AND RENDEZVOUS
Hall, R.W. / HANDBOOK OF TRANSPORTATION SCIENCE—2nd Ed.
HANDBOOK OF METAHEURISTICS
edited by
Fred Glover
Leeds School of Business
University of Colorado at Boulder
Gary A. Kochenberger
College of Business
University of Colorado at Denver
KLUWER ACADEMIC PUBLISHERS
NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: 0-306-48056-5
Print ISBN:
1-4020-7263-5
©2003 Kluwer Academic Publishers
New York, Boston, Dordrecht, London, Moscow
Print ©2003 Kluwer Academic Publishers
Dordrecht
All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,
mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Visit Kluwer Online at:
and Kluwer's eBookstore at:
http://kluweronline.com
http://ebooks.kluweronline.com
To our wives, Diane and Ann, whose meta-patience and meta-support have
sustained us through this effort!
This page intentionally left blank
CONTENTS
List of Contributors
Preface
1
Scatter Search and Path Relinking: Advances and Applications
Fred Glover, Manuel Laguna and Rafael Marti
2 An Introduction to Tabu Search
Michel Gendreau
3 Genetic Algorithms
Colin Reeves
4 Genetic Programming: Automatic Synthesis of Topologies and
Numerical Parameters
John R. Koza
5 A Gentle Introduction to Memetic Algorithms
Pablo Moscato and Carlos Cotta
6 Variable Neighborhood Search
Pierre Hansen and Nenad
7 Guided Local Search
Christos Voudouris and Edward P.K. Tsang
8 Greedy Randomized Adaptive Search Procedures
Mauricio G.C. Resende and Celso C. Ribeiro
9
The Ant Colony Optimization Metaheuristic: Algorithms,
Applications, and Advances
Marco Dorigo and Thomas Stützle
ix
xi
1
37
55
83
105
145
185
219
251