Skip to main content

Über dieses Buch

Finding exact solutions to many combinatorial optimization problems in busi­ ness, engineering, and science still poses a real challenge, despite the impact of recent advances in mathematical programming and computer technology. New fields of applications, such as computational biology, electronic commerce, and supply chain management, bring new challenges and needs for algorithms and optimization techniques. Metaheuristics are master procedures that guide and modify the operations of subordinate heuristics, to produce improved approx­ imate solutions to hard optimization problems with respect to more simple algorithms. They also provide fast and robust tools, producing high-quality solutions in reasonable computation times. The field of metaheuristics has been fast evolving in recent years. Tech­ niques such as simulated annealing, tabu search, genetic algorithms, scatter search, greedy randomized adaptive search, variable neighborhood search, ant systems, and their hybrids are currently among the most efficient and robust optimization strategies to find high-quality solutions to many real-life optimiza­ tion problems. A very large nmnber of successful applications of metaheuristics are reported in the literature and spread throughout many books, journals, and conference proceedings. A series of international conferences entirely devoted to the theory, applications, and computational developments in metaheuristics has been attracting an increasing number of participants, from universities and the industry.



1. Selected Topics in Simulated Annealing

We review a number of selected topics that were published in the simulated annealing literature during the past decade. The emphasis of the presentation is on theoretical and general results. The presentation of the novel features include generalized convergence results, new performance properties, improved variants, genetic hybrids, and approaches to general mathematical programming models.
Emile Aarts, Jan Korst

2. Reactive Tabu Search with Path-Relinking for the Steiner Problem in Graphs

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists in finding a minimum weight subgraph spanning a given subset of nodes (terminals) of the original graph. We describe a reactive tabu search with path-relinking algorithm for the Steiner problem in graphs, based on the extension of a previously developed tabu search algorithm using a neighborhood defined by insertions and eliminations of Steiner nodes. Computational experiments on benchmark problems are reported, comparing the reactive tabu search with other metaheuristic implementations. The reactive tabu search algorithm outperforms other algorithms, obtaining better or comparably good solutions. We also describe a robust parallel implementation based on an independent-thread multiple-walk strategy and report improved computational results on a 32-processor cluster running under Linux.
Marcelo P. Bastos, Celso C. Ribeiro

3. A Grasp for Job Shop Scheduling

In this paper, we describe a greedy randomized adaptive search procedure (GRASP) for the job shop scheduling problem (JSP). We incorporate to the conventional GRASP two new concepts: an intensification strategy and POP (Proximate Optimality Principle) in the construction phase. These two concepts were first proposed by Fleurent and Glover (1999) in the context of the quadratic assignment problem. Computational experience on a large set of standard test problems indicates that GRASP is a competitive algorithm for finding approximate solutions of the job shop scheduling problem.
S. Binato, W. J. Hery, D. M. Loewenstern, M. G. C. Resende

4. A Reactive Grasp for Transmission Network Expansion Planning

In this paper we describe an enhanced GRASP (Greedy Randomized Adaptive Search Procedure) applied to power transmission network expansion planning problems. GRASP is a metaheuristic that has been shown to be powerful in solving combinatorial problems. It is composed of two phases: the construction phase where a feasible solution is iteratively built, and a local search phase that seeks improvements within a given neighborhood of the solution found by the construction phase. The best solution over all GRASP iterations is chosen as the result. The enhancements analyzed in this paper are two: instead of using a random function in the construction phase, we use a linear bias function to guide the construction. We also applied a reactive procedure to self adjust GRASP parameters. Two real-world power transmission network expansion planning problems of the Brazilian power system are used to verify the performance of these improvements.
Silvio Binato, Gerson Couto Oliveira

5. Tabu Search for Two-Dimensional Irregular Cutting

The two-dimensional irregular cutting problem consists of cutting figures of various shapes from a rectangular area to minimize the area required. We adapt the tabu search metaheuristic to the problem, defining a specific neighborhood and various types of moves and search strategies. A standard type of tabu search, with simple and combined evaluating functions as well as a probabilistic tabu search variants are considered. In the paper, the behavior of different probabilistic approaches and the advantage of a newly proposed random candidate list version over a simple ranking approach are demonstrated. An exact algorithm for finding a placement of the polygon has been used in order to enhance the quality of solutions. Preview of wide range of experiments performed gives an idea about the efficiency of different approaches proposed.
Jacek Btażewicz, Adrian Moret Salvador, Rafat Walkowiak

6. A Study of Global Convexity for a Multiple Objective Travelling Salesman Problem

Global convexity, or heuristic concentration, has been mentioned in the literature as a reason for the success of many single objective metaheuristics. Global convexity is not an intrinsic characteristic of a combinatorial problem, but rather a property of the topology induced in a solution space by, for example, a neighborhood operator. This paper presents a study of global convexity for a multiple objective travelling salesman problem using the 2-OPT operator. The analysis is based on local search and includes extensive experimentation with the weighted sums program and augmented Tchebycheff program. We study the concentration of local optima for instances of scalarizing programs, the differences observed between solutions and points generated with different weights, and the stability of the best local optima for small weight variations. The exact global optima for weighted sums programs are also generated and exhibit concentration characteristics. The results are promising in that they confirm the existence of global convexity and might be used as a basis for understanding and building new metaheuristics for multiple objective optimization problems.
Pedro Castro Borges, Michael Pilegaard Hansen

7. A Lower Bound Based Meta-Heuristic for the Vehicle Routing Problem

In this paper is described a tabu search algorithm for the vehicle routing problem, considering a fleet of K vehicles. The most interesting and innovative feature of this algorithm is that the starting solution, instead of being obtained from scratch or from some kind of well known heuristic method, as is the usual pattern, is given by a lower bound for this problem. This lower bound is a minimum cost K-tree with two K edges incident on the depot, and with two types of additional constraints representing the facts that each customer must be visited just once and that the capacity of the vehicles must not be exceeded.
José Brandão

8. A Simulated Annealing Approach for Minimum Cost Isolated Failure Immune Networks

Isolated failure immune networks are communication networks having an interesting immunity structure. An application of Simulated Annealing algorithm to the minimum cost failure immune networks problem is presented. Computational experiments show that the metaheuristic approach outperforms previous simple heuristics. The dependency on starting solution and neighborhood scheme is also analyzed.
Alfredo Candia, Hugo Bravo

9. A Grasp Interactive Approach to the Vehicle Routing Problem with Backhauls

Interactive methods for vehicle routing axe appealing because they integrate the insight and experience of the user and the power and precision of heuristics in an interactive environment. Although best known results for benchmark problems are attributed to tabu search, interactive methods give results within about 3% of these solutions, whilst retaining the advantage of user control. A new interactive construction method using GRASP will be presented. The method allows vehicles to make all their deliveries, and then make pick-ups before returning to the depot. A Windows implementation allows the user to control the solution process by selecting initial outline routes of one or more deliveries followed by pick-ups. The user can also try to improve the solution, especially if it is infeasible, using interactive tools. Results will be shown for benchmark problems.
Carlos Carreto, Barrie Baker

10. Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem

In this paper we consider the labor constrained scheduling problem (LCSP), in which a set of jobs to be processed is subject to precedence and labor requirement constraints. Each job has a specified processing time and a labor requirements profile, which typically varies as the job is processed. Given the amount of labor available at each period, the problem consists in determining starting times so as to minimize the overall makespan, subject to the precedence and labor constraints. We propose two parallel cooperative algorithms for LCSP: an asynchronous team and a parallel tabu search strategy. Both algorithms make use of cooperative processes that asynchronously exchange information gathered along their execution. Computational experiments on benchmark instances show that these parallel algorithms produce significantly better solutions than all sequential algorithms previously proposed in the literature.
Cristina C. B. Cavalcante, Victor F. Cavalcante, Celso C. Ribeiro, Cid C. de Souza

11. A Scatter Search Algorithm for the Maximum Clique Problem

The objective of the Maximum Clique Problem (MCP) is to find the largest complete subgraph in a given graph. The problem is known as NP-hard and we have developed a heuristic algorithm based on a Scatter Search (SS) framework to find a lower bound for this maximization problem. The proposed algorithm was developed with two search features: a guidance search and a local search feature. For the first feature a Scatter Search algorithm was chosen with the purpose of extensively exploring regions with strategically combined solutions. The new solutions obtained in the combination phase are thereafter improved by a neighborhood search procedure based on tabu search for implementing the second feature. The computational results obtained with DIMACS clique benchmark instances show that the proposed algorithm finds solutions comparable to the ones provided by some of the most competitive algorithms for the MCP.
Luís Cavique, César Rego, Isabel Themido

12. The Noising Methods: A Survey

The aim of this paper is to summarize the principles and the applications of the noising methods, a recent family of combinatorial optimization metaheuristics. We describe their commons features and their variants and we give the list of their applications to different combinatorial optimization problems. We also show how the simulated annealing algorithm and the threshold accepting algorithm can be considered as noising methods when the components of the noising methods are properly chosen.
Irène Charon, Olivier Hudry

13. Strategies for the Parallel Implementation of Metaheuristics

Parallel implementations of metaheuristics appear quite naturally as an effective alternative to speed up the search for approximate solutions of combinatorial optimization problems. They not only allow solving larger problems or finding improved solutions with respect to their sequential counterparts, but also lead to more robust algorithms. We review some trends in parallel computing and report recent results about linear speedups that can be obtained with parallel implementations using multiple independent processors. Parallel implementations of tabu search, GRASP, genetic algorithms, simulated annealing, and ant colonies are reviewed and discussed to illustrate the main strategies used in the parallelization of different metaheuristics and their hybrids.
Van-Dat Cung, Simone L. Martins, Celso C. Ribeiro, Catherine Roucairol

14. Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems

This paper focuses on accelerating strategies used in conjunction with column generation to solve vehicle routing and crew scheduling problems. We describe techniques directed at speeding up each of the five phases of the solution process: pre-processor, subproblem, master problem, branch-and-bound, and post-optimizer. In practical applications, these methods often were key elements for the viability of this optimization approach. The research cited here shows their use led to computational gains, and notably to solutions that could not have been obtained otherwise due to practical problem complexity and size. In particular, we present recent methods directed at the integer programming aspect of the approach that were instrumental in substantially reducing the integrality gap found in certain applications, thereby helping to efficiently produce excellent quality solutions.
Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon

15. Grasp: An Annotated Bibliography

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Since 1989, numerous papers on the basic aspects of GRASP, as well as enhancements to the basic metaheuristic have appeared in the literature. GRASP has been applied to a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing. This paper is an annotated bibliography of the GRASP literature from 1989 to 2001.
Paola Festa, Mauricio G.C. Resende

16. Recent Advances in Tabu Search

We review some of the main advances witnessed in the field of Tabu Search (TS) during the last four to five years. We focus on what we see as the most significant trends in the area, namely: techniques to make the search more effective, hybrid methods, and new applications of tabu search.
Michel Gendreau

17. Lagrangean Tabu Search

Tabu Search (TS) and Lagrangean relaxation (LR) are important techniques for solving large-scale combinatorial optimization problems. They have been applied successfully to a wide range of different problems from such diverse areas as routing and scheduling, network design, cutting and packing, production planning etc. In this paper we will outline how these techniques can be combined in order to obtain an even better performance. The basic idea behind such a combination is to identify promising neighbors of a current solution in the TS framework by LR. This gives a dual price and memory controlled search procedure. The principles and results of this algorithmic framework are illustrated by applying them to the solution of the capacitated warehouse location problem.
Tore Grünert

18. A Gids Metaheuristic Approach to the Fleet Size and Mix Vehicle Routing Problem

This paper presents a new metaheuristic approach, i.e., the GIDS (Generic Intensification and Diversification Search), as well as its performance for solving the FSMVRP (Fleet Size and Mix Vehicle Routing Problem). The GIDS integrates the use of some recently developed generic search methods such as TA (Threshold Accepting) and GDA (Great Deluge Algorithm), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: (1) MIC, multiple initialization constructor; (2) GSI, generic search for intensification; (3) PSD, perturbation search for diversification. A bank of twenty FSMVRP benchmark instances was tested by several different implementations of GIDS. All programs were coded in UNIX C and implemented on a SPARC 10 SUN workstation. Results are very encouraging. We have updated the best-known solutions for two of the twenty benchmark instances; the average deviation from the twenty best solutions is merely 0.598%.
Anthony Fu-Wha Han, Yuh-Jen Cho

19. Developments of Variable Neighborhood Search

Proposed just a few years ago, Variable Neighborhood Search (VNS) is a new metaheuristic for combinatorial and global optimization, based upon systematic change of neighborhood within a possibly randomized local search. Its development has been rapid. After reviewing the basic scheme of VNS, several extensions aimed at solving large problem instances are surveyed. Issues in devising a VNS heuristic are discussed. Finally, recent applications are briefly summarized, with special attention given to VNS-based computer-aided discovery of conjectures in graph theory.
Pierre Hansen, Nenad Mladenović

20. Analyzing the Performance of Local Search Algorithms Using Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a well-defined framework to model how local search algorithms address intractable discrete optimization problems. Monte Carlo search, simulated annealing, threshold accepting, and tabu search, among others, can all be formulated as particular generalized hill climbing algorithms. Moreover, generalized hill climbing algorithms provide a structure for classifying and studying a large body of stochastic and deterministic local search algorithms. In particular, the generalized hill climbing algorithm framework can be used to develop a general Markov chain model for the application of local search algorithms to intractable discrete optimization problems. Moreover, the generalized hill climbing algorithm framework has been used to evaluate the finite-time performance of local search algorithms. This analysis is of particular interest to practitioners for whom traditional convergence results are often of limited interest and value. This paper presents a survey of recent results on how the generalized hill climbing algorithm framework has been used to model and gain insight into the performance of local search algorithms. Many of these results provide tools for comparing and evaluating different types of local search algorithms using common performance measures.
Sheldon H. Jacobson

21. Ant Colony Optimization: An Overview

Ant Colony Optimization (ACO) is a class of constructive meta-heuristic algorithms sharing the common approach of constructing a solution on the basis of information provided both by a standard constructive heuristic and by previously constructed solutions. This tutorial is composed of three parts. The first one frames the ACO approach in current trends of research on metaheuristic algorithms for combinatorial optimization; the second outlines current research within the ACO framework, reporting recent results obtained on different problems, while the third part focuses on a particular research line, the ANTS metaheuristic, providing some details on the algorithm and presenting results recently obtained on the quadratic and on the frequency assignment problems.
Vittorio Maniezzo, Antonella Carbonaro

22. Intensification Neighborhoods for Local Search Methods

In local search methods, even when they are used in sophisticated implementations of metaheuristics, basic neighborhoods are generally applied. The best neighbor can be quickly identified but, on the other hand, these neighborhoods give to the search a low visibility of the global search space to the detriment of the efficiency of the method. That is the first reason why we present in this paper new neighborhood structures, namely the neighborhood tree and the Mimausa neighborhood. Used in a local search method, these structures intensify the search around the current solution and may ensure a quicker convergence. These neighborhood structures could also be of interest for a Variable Neighborhood Search or Descent where a set of various neighborhood structures is required.
Thierry Mautor

23. New Heuristics for the Euclidean Steiner Problem in R n

We introduce two new heuristic approaches for the Euclidean Steiner Tree Problem in R n (ESTP). The first approach is an extension to n ≥ 3 of a relaxation scheme developed in the plane and based on a physical model for the ESTP. Such a model arises from the dynamics of a fluid film subject to surface tension forces. The second one is based on a local search of full Steiner tree topologies within a neighborhood for which we apply a tabu search heuristic. Some ingredients of the first approach are used in the second one. Implementations have been carried out and preliminary results are provided for certain parameters of both these heuristics.
Flávio Montenegro, Nelson Maculan, Gérard Plateau, Patrick Boucher

24. Mathematical Analysis of Evolutionary Algorithms

We analyze evolutionary algorithms which use a population of search points at each step. A popular example are genetic algorithms. We approximate genetic algorithms by an algorithm using Univariate Marginal Distributions (UMDA). UMDA generates the search points from a probability distribution. We derive difference equations for the marginal distributions which completely describe the dynamic behavior of UMDA. The key result is that UMDA transforms the discrete optimization problem to a continuous one. The continuous optimization problem is solved by gradient ascent. We show that UMDA solves many difficult multi-modal optimization problems. UMDA is extended to the Factorized Distribution Algorithm (FDA) which uses a general factorization of the search distribution into conditional and marginal distributions. We prove that FDA with Boltzmann selection converges to the set of global optima. A new adaptive selection schedule for Boltzmann selection is derived. FDA is extended to an algorithm LFDA, which computes the factorization from promising search points. LFDA is based on learning of Bayesian networks.
H. Mühlenbein, Th. Mahnig

25. Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem

The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
Koji Nonobe, Toshihide Ibaraki

26. Analysing the Run-Time Behaviour of Iterated Local Search for the Travelling Salesman Problem

Iterated Local Search (ILS) is currently the most successful meta-heuristic for solving large Travelling Salesman Problems (TSPs). In this paper we study the behaviour of ILS algorithms by measuring and analysing run-time distributions. Our analysis shows that currently available ILS algorithms suffer from stagnation behaviour when searching for very high quality solutions. Based on this observation we propose two enhanced ILS algorithms for the TSP which avoid this stagnation behaviour and achieve significantly improved performance. More generally, our study demonstrates how the analysis of runtime distributions can provide the basis for characterising and improving the performance of state-of-the-art metaheuristics, such as Iterated Local Search.
Thomas Stützle, Holger H. Hoos

27. Popmusic — Partial Optimization Metaheuristic under Special Intensification Conditions

This article introduces POPMUSIC, a meta-heuristic that has been successfully applied to various combinatorial optimization problems. This meta-heuristic is especially useful for designing heuristic methods for large combinatorial problems that can be partially optimized. The basic idea is to optimize sub-parts of solutions until a local optimum is reached. Implementations of the technique to large centroid clustering and to the problem of balancing mechanical parts are shown to be very efficient.
Éric D. Taillard, Stefan Voss

28. Subcost-Guided Simulated Annealing

This paper describes a variant of simulated annealing for problems with compound objectives, i.e. those for which a number of diverse objectives are combined into a single objective function. The method takes account not only of the progress of the overall cost but also, to a limited extent, of the progress of the individual subcosts. Various experiments using this approach are described and results given. These results are not conclusive but suggest that there may be considerable value in using this type of approach.
Mike Wright

29. A Pruning Pattern List Approach to the Permutation Flowshop Scheduling Problem

This paper investigates an approach to the permutation flowshop scheduling problem based on Tabu Search with an additional memory structure called a ‘pruning pattern list’. The pruning pattern list approach allows a better use of the critical block information. A solution of the flowshop scheduling problem is represented by a permutation of job numbers. A pruning pattern is generated from a solution by replacing job numbers inside a critical block with ‘wild cards’ so that solutions that ‘match’ the pattern would be excluded from the search. A set of pruning patterns, which is called a ‘pruning pattern list’, is used to navigate the search by avoiding solutions that would match any pattern on the list. Computational experiments using benchmark problems demonstrate the effectiveness of the proposed approach.
Takeshi Yamada
Weitere Informationen