METAHEURISTICS: COMPUTER DECISION-MAKING

EDITED BY Mauricio G. C. Resende and Jorge Pinho de Sousa
with assistance from Ana Viana.
Copyright © 2004 by Kluwer Academic Publishers.
Published by Kluwer Academic Publishers. 
P.O. Box 17, 3300 AA Dordrecht, The Netherlands.







Table of contents
List of contributors
List of referees

PREFACE

Combinatorial optimization is the process of finding the best, or optimal, solution for problems with a discrete set of feasible solutions. Applications arise in numerous settings involving operations management and logistics, such as routing, scheduling, packing, inventory and production management, location, logic, and assignment of resources. The economic impact of combinatorial optimization is profound, affecting sectors as diverse as transportation (airlines, trucking, rail, and shipping), forestry, manufacturing, logistics, aerospace, energy (electrical power, petroleum, and natural gas), telecommunications, biotechnology, financial services, and agriculture.

While much progress has been made in finding exact (provably optimal) solutions to some combinatorial optimization problems, using techniques such as dynamic programming, cutting planes, and branch and cut methods, many hard combinatorial problems are still not solved exactly and require good heuristic methods. Moreover, reaching "optimal solutions" is in many cases meaningless, as in practice we are often dealing with models that are rough simplifications of reality. The aim of heuristic methods for combinatorial optimization is to quickly produce good-quality solutions, without necessarily providing any guarantee of solution quality. Metaheuristics are high level procedures that coordinate simple heuristics, such as local search, to find solutions that are of better quality than those found by the simple heuristics alone. Modern metaheuristics include simulated annealing, genetic algorithms, tabu search, GRASP, scatter search, ant colony optimization, variable neighborhood search, and their hybrids. In many practical problems they have proved to be effective and efficient approaches, being flexible to accommodate variations in problem structure and in the objectives considered for the evaluation of solutions. For all these reasons, metaheuristics have probably been one of the most stimulating research topics in optimization for the last two decades.

Metaheuristics: Computer Decision-Making grew out of the 4th Metaheuristics International Conference (MIC2001), held in Porto, Portugal, on July 16-20, 2001, and chaired by Jorge Pinho de Sousa. Kluwer Academic Publishers published three books developed from previous editions of the Metaheuristic International Conference (MIC'95: I.H. Osman and J.P. Kelly (eds.), Meta-heuristics: Theory and Applications, Kluwer, 1996, held in Breckenridge, United States, in 1995; MIC'97:  S. Voss, S. Martello, I.H. Osman, and C. Roucairol (eds.), Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, 1999,  held in Sophia-Antipolis, France, in 1997; and MIC'99:  C.C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics, Kluwer, 2002, held in Angra dos Reis, Brazil, in 1999). Though this book is not a conference proceedings, it does characterize the type of research presented at MIC2001.
                                                                               
Metaheuristics: Computer Decision-Making exemplifies how much the field has matured in the last few years. The volume has 33 papers, covering a broad range of metaheuristics and related topics, as well as applications.

Metaheuristics and related topics include:

Applications and problems types include:

assignment and partitioning problems:
scheduling:
tree and graph problems:
statistics:
cutting problems:
mathematical programming:
vehicle routing: Chapters 5 and 33;

single source capacitated location: Chapter 9;

industrial applications:
heuristic search software framework: Chapter 11.


The editors would like to thank the authors for their contributions, the over 70 referees for their tireless effort and helpful suggestions, Kluwer Academic Publishers for publishing the book, and Alec Resende and Geraldo Veiga for assistance in producing the final camera-ready manuscript.
                                                                               
Last, but not least, we are specially grateful to Ana Viana, for her valuable support and tireless collaboration in the editorial work involving the publication of this book.
                                                                               

Florham Park and Porto, April 2003

Mauricio G. C. Resende and Jorge Pinho de Sousa

Table of contents
List of contributors
List of referees