Metaheuristics: Heuristic Techniques for Combinatorial Optimization Problems

Metaheuristics: Heuristic Techniques for Combinatorial Optimization Problems

Stephan Scheuerer (Fraunhofer Center for Applied Research on Technologies for the Logistics Service Industries ATL, Germany)
DOI: 10.4018/978-1-59904-843-7.ch067
OnDemand PDF Download:


Decision support systems (DSSs) provide modern solution techniques that help the decision maker to find the best solution to a problem. These embedded solution techniques include and combine, but are not limited to, simulation, exact optimization methods, and heuristics. Especially in the field of heuristics, recent advances in metaheuristic methods have proved to be remarkably effective so that metaheuristics are nowadays the preferred way for solving many types of complex problems, particularly those of combinatorial nature. Some of these problems are, for example, the well-known “traveling salesman” problem, the generalized assignment problem, the set-covering problem, and vehicle and network routing applications. Most of all, metaheuristics allow us to solve real-world problems with a notably high level of complexity. This is where exact methods are often incapable of finding solutions whose qualities are close to that obtained by the leading metaheuristics. Metaheuristic applications with world-class performance can be found in all kinds of areas such as economics, engineering, and natural sciences.

Key Terms in this Chapter

Constructive Methods: Constructive methods are heuristics that build up a complete solution from scratch by sequentially adding components to a partial solution until the solution is complete.

Diversification: Diversification is a strategy that encourages a search process to examine unvisited regions of the search space.

Intensification: Intensification is a strategy that encourages a thorough examination of attractive-looking regions in the search space.

Population-Based Metaheuristics: These are metaheuristics that consider a set of solutions rather than a single solution.

Single-Solution Metaheuristics: These are metaheuristics that basically work on a single solution at a time.

Metaheuristics: These are strategies that guide a heuristic search process to efficiently explore the search space in order to find a (close to) optimal solution.

Improvement Methods: These are methods that attempt to improve a given solution either in cost or in structure.

Complete Chapter List

Search this Book: