An unsupervised machine learning method based on association rule is studied for the Quadratic Assignment Problem. Parallel extraction of itemsets and local search algorithms are proposed. The extraction of frequent itemsets in the context of local search is shown to produce good results for a few problem instances. Negative results of the proposed learning mechanism are reported for other instances. This result contrasts with other hard optimization problems for which efficient learning processes are known in the context of local search.

This chapter recalls some elements and definitions in graph theory and complexity theory. On the one hand, basic algorithmic courses very often include graph algorithms. Some of these algorithms have simply been transposed to solve difficult optimization problems in a heuristic way. On the other hand, it is important to be able to determine whether a problem falls into the category of difficult problems. Indeed, one will not develop a heuristic algorithm if there is an efficient algorithm to find an exact solution. Another objective of this chapter is to make the book self-contained.

This chapter reviews a number of typical combinatorial optimization problems. It illustrates the tenuous border that sometimes exists between an easy problem, for which effective algorithms are known, and an intractable one that differs merely by a small detail that may appear innocuous at first sight

This chapter shows how a problem can be modeled so that it can be handled efficiently by a heuristic algorithm. It gives some examples of transformations of data, constraints, and objectives. Finally, it introduces some notions of multi-objective optimization.

This chapter presents methods for constructing solutions. It starts with the branch and bound methods, widely used for the design of exact algorithms. Then two basic methods are presented, random and greedy constructions. The latter sequentially selects the elements to include to a partial solution, never changing the choices that have been made. This method can be improved by a deeper evaluation of the consequences of a choice. Beam search and the pilot method are part of it.

Improvement methods constitute the backbone of most metaheuristics. These methods repeatedly perform slight, local modifications on a current solution to the problem. Hence, for any solution, a set of neighbor solutions must be defined. Clearly, the definition of this set depends on the problem modeling. However, a natural neighborhood may turn out to be either too small to lead to quality solutions or too large, inducing prohibitive calculation times. Various approaches have been proposed to enlarge the neighborhood, such as the filter and fan method or the ejection chains. For reducing the neighborhood size, typical strategies are the granular search and the candidate list.

The chapter first recalls few properties of recursive algorithms. Next, it introduces a general recursive constructive method. Finally, it presents the large neighborhood search and the POPMUSIC metaheuristics.

This chapter is devoted to random and memory-free methods that repeatedly construct solutions or modify them. Among the most popular techniques, there are simulated annealing, threshold accepting, great deluge and demon algorithms, noising methods, late acceptance hill climbing, variable neighborhood search, and GRASP.

The first basic ingredient of heuristics is to build a solution. So, a first metaheuristic approach is to improve the process of building solutions. This chapter presents construction learning mechanisms. A typical example is artificial ants systems. Another technique is vocabulary building.

If local research constitutes the backbone of metaheuristics, tabu search, looking to learn how to iteratively modify a solution can be considered the master of metaheuristics. Moreover, this term was proposed by his inventor. This chapter focuses on the ingredients at the basis of taboo search, namely, the use of memories and tactics for exploring the solution set. Other ingredients proposed in the context of taboo search by his inventor, like the candidate lists, ejection chains, and vocabulary building have a more logical place in other chapters.

After having generated several solutions, we can seek to learn how to combine them. This chapter review techniques for generating new solution from existing ones and for managing a population of solution. The most popular method in this field is undoubtedly genetic algorithms. However, the latter are less advanced metaheuristics than memetic algorithms or scatter search. The path relinking technique is also part of this chapter. Finally, among the last metaheuristics invented, we find the particle swarm methods, which seem adapted to continuous optimization.

The last chapter of the book gives some advice on developing heuristics. It discusses the difficulty of modeling the problem and gives an example of decomposing the problem into a chain of more manageable sub-problems. Secondly, it proposes an approach for the design of a specific heuristic. Finally, some techniques for parameter tuning and comparing the efficiency of algorithms are reviewed.

This chapter gives utility codes used by various procedures presented in the book. It also gives some programs for testing many of the metaheuristics discussed in the book.

A linearithmic (n log n) randomized method based on POPMUSIC (Partial Optimization Metaheuristic Under Special Intensification Conditions) is proposed for generating reasonably good solutions to the travelling salesman problem. The method improves a previous work with empirical algorithmic complexity in n^1.6. The method has been tested on instances with billions of cities. For a lot of problem instances of the literature, a few dozens of runs are able to generate a very high proportion of the edges of the best solutions known. This characteristic is exploited in a new release of the Helsgaun's implementation of the Lin-Kernighan heuristic (LKH) that is also able to produce rapidly extremely good solutions for non-Euclidean instances. The practical limits of the proposed method are discussed on a new type of problem instances arising in a manufacturing process, especially in 3D extrusion printing.

POPMUSIC --- Partial OPtimization Metaheuristic Under Special Intensification Conditions --- is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.

This article presents a methodology for decomposing the problem of creating parking plans for a public transportation company into a series of sub-problems easier to solve. For managing easily the vehicles in depots, the company wants to use as few parking lanes as possible while grouping vehicles of the same type. This sub-problem is first solved and, possibly, several good solutions are stored. Then, the departure hour of each vehicle is assigned while taking into account various practical constraints. This second sub-problem is harder to solve and approached by using hierarchical objectives and taboo searches meta-heuristics in case an exact solution cannot be computed in reasonable time. If no acceptable solution can be found with a given grouping of vehicle, another solution to the first sub-problem is considered as starting point for the second part of the algorithm. The transportation company uses now daily the software described in the present article and has improved the management efficiency of its vehicles depots. This is in contrast with the situation occurring few years ago, where the parking plans were manually produced few times a year.

POPMUSIC --- Partial optimization metaheuristic under special intensification conditions --- is a template for tackling large problem instances. This template has been shown to be very efficient for various combinatorial problems like p-median, sum of squares clustering, vehicle routing and map labeling. In terms of algorithmic complexity, one of the most complex part of POPMUSIC template is to find an initial solution. This article presents a method for generating an appropriate initial solution to the location routing problem by producing in O(n^3/2) a solution to the capacitated p-median problem. The method is tested on location routing instances with millions of entities.

Hybrid metaheuristics are powerful methods for solving complex problems in science and industry. Nevertheless, the resolution time remains prohibitive when dealing with large problem instances. As a result, the use of GPU computing has been recognized as a major way to speed up the search process. However, to the best of our knowledge, GPU-accelerated algorithms of the literature do not take benefits of all the available CPU cores. In this paper, we introduce a new guideline for the design and implementation of effective hybrid metaheuristics using heterogeneous resources. Efficient approaches are proposed for CPU-GPU data transfer optimization, and task repartition between the GPU and the remaining CPU cores. The results obtained from the experiments demonstrate the potential of heterogeneous computing compared to a single GPU architecture.

Trouver la meilleure voie de navigation pour un véhicule solaire implique de prendre en considération de nombreux paramètres variant dynamiquement dans le temps, comme l'ensoleillement et la vitesse du vent. Une équipe de la Heig-VD a mis au point un logiciel pour optimiser le routage de PlanetSolar, le catamaran qui a réalisé le premier tour du monde mû uniquement à l'énergie photovoltaïque. la technique de calcul développée pourrait aussi être utilisée à l'avenir pour diminuer la consommation d'automobiles hybrides.

Les métaheuristiques et leurs applications. Les ingénieurs, les économistes, les décideurs se heurtent quotidiennement, quel que soit leur secteur d'activité, à des probèmes d'optimisation. Il peut s'agir de minimiser un coût de production, d'optimiser le parcours d'un véhicule ou le rendement d'un portefeuille boursier, de rationaliser l'utilisation de ressources, d'améliorer les performances d'un circuit électronique, de fournir une aide à la décision à des managers, etc. Cet ouvrage présente une famille de techniques d'optimisation, appelées "métaheuristiques", adaptées à la résolution de probèmes pour lesquels il est difficile de trouver un optimum global ou de bons optimums locaux par des méthodes plus classiques. Un ouvrage de référence illustré d'études de cas La première partie de l'ouvrage présente les principales métaheuristiques : recuit simulé, recherche avec tabous, algorithmes évolutionnaires et algorithmes génétiques, colonies de fourmis. La deuxième partie décrit différentes variantes et extensions de ces méthodes, ainsi que de nouvelles voies de recherche. Y sont également proposés des conseils méthodologiques : techniques de modélisation, comparaisons de méthodes et choix de la méthode la mieux adaptée à un probème donné. La troisième partie présente trois études de cas réels : optimisation de réseaux de mobiles UMTS (France Télécom R & D), gestion de trafic aérien (ENAC), optimisation de tournées de véhicules (ILOG).

Keywords: metaheuristic, optimization

The multisource Weber problem is to locate simultaneously m facilities in the Euclidean plane to minimize the total transportation cost for satisfying the demand of n fixed users, each supplied from its closest facility. Many heuristics have been proposed for this problem, as well as a few exact algorithms. Heuristics are needed to solve quickly large problems and to provide good initial solutions for exact algorithms. We compare various heuristics, i.e., alternative location-allocation (Cooper 1964), projection (Bongartz et al. 1994), Tabu search (Brimberg and Mladenovic 1996a), p-Median plus Weber (Hansen et al. 1996), Genetic search and several versions of Variable Neighbourhood search. Based on empirical tests that are reported, it is found that most traditional and some recent heuristics give poor results when the number of facilities to locate is large and that Variable Neighbourhood search gives consistently best results, on average, in moderate computing time.

This paper presents a heuristic column generation method for solving vehicle routing problems with a heterogeneous fleet of vehicles.The method may also solve the fleet size and composition vehicle routing problem and new best known solutions are reported for a set of classical problems. Numerical results show that the method is robust and efficient, particularly for medium and large size problem instances.

This paper presents HAS_QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS_QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS_QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS_QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS_QAP performance is less competitive on random, regular and unstructured problems

Good heuristic solutions for large multisource Weber problems can be obtained by solving related p-median problems in which potential locations of the facilities are users locations and then solving Weber problems for the sets of users of each facility.

Keywords: Location

This article analyses recent developments of a number of meta-heuristics with memory and shows that these general solving methods are implemented in a more and more similar way. A unified presentation of these methods is proposed under the name of adaptive memory programming. This solving scheme can be conveniently parallelised. Finally, a number of recently proposed methods for quadratic assignment and vehicle routeing problems are reviewed and presented under an adaptive memory programming point of view.

The vehicle routing problem with time windows models many realistic applications in the context of distribution systems. In this paper, a parallel tabu search heuristic for solving this problem is developed and implemented on a network of workstations. Empirically, it is shown that parallelization of the original sequential algorithm does not reduce solution quality, for the same amount of computations, while providing substantial speed-ups in practice. Such speed-ups could be exploited to quickly produce high quality solutions when the time available for computing a solution is reduced, or to increase service quality by allowing the acceptance of new requests much later, as in transportation on demand systems

Many distributions systems involve the real-time dispatch of a fleet of commercial vehicles for serving customer requests. Typical examples include courier services or less-than-truckload trucking, where vehicle routes must be determined quickly or in real-time. This paper describes an efficient solution procedure, based on the tabu search heuristic, to determine near-optimal solutions in two different problem settings: real-time routing where all customer locations are known before hand but at short notice, and real-time dispatching where requests are received and must be responded to in an on-going fashion. To provide quick response time, the solution procedure is implemented in a course-grain parallel computing environment. Computational results indicate that high-quality solutions are produced in acceptable time.

This paper compares some of the most efficient heuristic methods for the quadratic assignment problem. These methods are known as strict taboo search, robust taboo search, reactive taboo search and genetic hybrids. It is shown that the efficiency of these methods strongly depends on the problem type and that no one method is better than all the others. A fast method for tuning the short term memory parameters of taboo searches is proposed and its validity is experimentally verified on long searches. A new type of quadratic assignment problem occurring in the design of grey patterns is proposed and it is shown how to adapt and improve the existing iterative searches for this specific problem. Finally, the usual way of implementing approximations of strict taboo search is discussed and better approximations are proposed.

Keywords: Quadratic assignment problem

This paper presents two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles. Indeed, using a simple implementation of taboo search as an iterative search method, every best-known solution to classical problems was found. The first partition method (based on a partition into polar regions) is appropriate for Euclidean problems whose cities are regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence built from the shortest paths from any city to the depot. Finally, solutions that are believed to be optimum are given for problems generated on a grid.

Keywords: combinatorial optimization, tabu search, vehicle routing problem

We compare in this paper the best heuristic methods known up to now to solve the flow shop sequencing problem and we improve the complexity of the best one. Next, we apply to this problem taboo search, a new technique to solve combinatorial optimization problems, and we report computational experiments. Finally a parallel taboo search algorithm is presented and experimental results show that this heuristics allows very good speed-up.

Keywords: Flow shop, taboo search techniques, parallel algorithm, combinatorial optimization