[1] | Éric D. Taillard. Design of Heuristic Algorithms for Hard Optimization — With Julia Codes for the Travelling Salesman Problem. 2024. [ bib | .pdf ] |
[2] | Éric D. Taillard. Design of Heuristic Algorithms for Hard Optimization — With C Codes for the Travelling Salesman Problem. 2023. [ bib | .pdf ] |
[3] |
Thé Van Luong and Éric D. Taillard.
Unsupervised machine learning for the quadratic assignment problem.
In Luca Di Gaspero, Paola Festa, Amir Nakib, and Mario Pavone,
editors, Metaheuristics, pages 118--132, Cham, 2023. Springer
International Publishing.
[ bib |
DOI |
.pdf ]
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. |
[4] |
Éric D. Taillard.
Elements of Graphs and Complexity Theory, pages 3--29.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[5] |
Éric D. Taillard.
A Short List of Combinatorial Optimization Problems, pages
31--61.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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 |
[6] |
Éric D. Taillard.
Problem Modeling, pages 63--81.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[7] |
Éric D. Taillard.
Constructive Methods, pages 85--101.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[8] |
Éric D. Taillard.
Local Search, pages 103--129.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[9] |
Éric D. Taillard.
Decomposition Methods, pages 131--152.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[10] |
Éric D. Taillard.
Randomized Methods, pages 155--170.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[11] |
Éric D. Taillard.
Construction Learning, pages 171--183.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[12] |
Éric D. Taillard.
Local Search Learning, pages 185--198.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[13] |
Éric D. Taillard.
Population Management, pages 199--228.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[14] |
Éric D. Taillard.
Heuristics Design, pages 229--245.
Springer International Publishing, Cham, 2023.
[ bib |
DOI |
http ]
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. |
[15] |
Éric D. Taillard.
Codes, pages 247--258.
Springer International Publishing, Cham, 2023.
The http link provides access to the Python codes.
[ bib |
DOI |
http ]
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. |
[16] | Éric D. Taillard. Design of Heuristic Algorithms for Hard Optimization --- With Python Codes for the Travelling Salesman Problem. Springer, 2023. The pdf file provides the last updated version. [ bib | DOI | .pdf ] |
[17] |
Éric D. Taillard.
A Linearithmic Heuristic for the Travelling Salesman Problem.
EURO Journal of Operational Research, 297(2):442--450, 2022.
Available online June 2021.
[ bib |
DOI |
.pdf ]
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. |
[18] | Éric D. Taillard. An n log n heuristic for the TSP. In Metaheuristic International Conference (MIC'19) proceedings, 2019. [ bib | .pdf ] |
[19] |
Éric D. Taillard and Keld Heslgaun.
POPMUSIC for the travelling salesman problem.
EURO Journal of Operational Research, 272(2):420--429, 2019.
[ bib |
DOI |
.pdf ]
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. |
[20] | Éric D. Taillard and Stefan Voß. POPMUSIC. In Rafael Martí, Pardalos Panos, and Mauricio G. C. Resende, editors, Handbook of Heuristics, pages 1--15. Springer International Publishing, Cham, 2018. [ bib | DOI | http ] |
[21] | Éric D. Taillard. TSP neighbourhood reduction with POPMUSIC. In Metaheuristic International Conference (MIC'17) proceedings, pages 237--240, 2017. [ bib | .pdf ] |
[22] | Éric D. Taillard. Tabu search. In Patrick Siarry, editor, Metaheuristics, pages 51--76. Springer International Publishing, Cham, 2016. [ bib | DOI | http ] |
[23] | Éric D. Taillard. Methodology. In Patrick Siarry, editor, Metaheuristics, pages 357--379. Springer International Publishing, Cham, 2016. [ bib | DOI | http ] |
[24] |
Thé Van Luong and Éric D. Taillard.
A methodology for creating parking plans.
Technical report, MIS-TIC, Department of Industrial Ingeering,
HEIG-VD, 2015.
[ bib ]
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. |
[25] | Éric D. Taillard, Adriana C. F. Alvim, and Voss. A template for low-complexity implementation of popmusic. In Metaheuristic International Conference (MIC'15) proceedings, 2015. [ bib | .pdf ] |
[26] | Éric D. Taillard. La recherche avec tabous. In P. Siarry (ed.), editor, Métaheuristiques, pages 49--72. Eyrolles, 2014. [ bib ] |
[27] | Éric D. Taillard. Techniques de modélisation et comparaisons de méthodes. In P. Siarry (ed.), editor, Métaheuristiques, pages 313--333. Eyrolles, 2014. [ bib ] |
[28] | Thé Van Luong and Éric D. Taillard. Decomposition techniques for parking vehicles in depots. In International Conference on Metaheuristics and Nature Inspired Computing (META'2014) proceedings, 2014. [ bib | .pdf ] |
[29] |
Adriana C. F. Alvim and Éric D. Taillard.
POPMUSIC for the world location routing problem.
EURO Journal on Transportation and Logistics, 2(3):231--254,
2013.
[ bib |
DOI |
.pdf ]
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. |
[30] |
Thé Van Luong, Nouredine Melab, Éric D. Taillard, and El-Ghazali Talbi.
Parallelization strategies for hybrid metaheuristics using a single
gpu and multi-core resources.
In 12th International Conference on Parallel Problem Solving
From Nature (PPSN) prooceedings, 2012.
Only preprint technical report available.
[ bib |
.pdf ]
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. |
[31] | Éric D. Taillard. Solution au concours 2012 de la fédération francaise de jeux mathématiques. Technical report, FFJM and SIM-TIC Institute, HEIG-VD, Univ. Applied Sci. W-Switzerland, 2012. 1. prize as individual participant. [ bib | .pdf ] |
[32] | Adriana C. F. Alvim and Éric D. Taillard. POPMUSIC for the world location routing problem. In Metaheuristic International Conference (MIC'11) proceedings, 2011. [ bib | .pdf ] |
[33] |
Éric D. Taillard, Patrick Bailly, Jean-Francois Affolter, Pascal
Goulpié, and Philippe Morey.
Logiciel d'aide à la navigation pour bateau solaire -- routage
optimal du catamaran planetsolar.
Bulletin VSE/AES, 1106:22--26, 2011.
[ bib |
.pdf ]
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. |
[34] | Maxence Laurent, Éric D. Taillard, Oliver Ertz, Francis Grin, Daniel Rappo, and Sébastien Roh. From point feature label placement to map labelling. In Metaheuristic International Conference (MIC'09) proceedings, 2009. [ bib | .pdf ] |
[35] | Adriana C. F. Alvim and Éric D. Taillard. POPMUSIC for the point feature label placement problem. European Journal of Operational Research, 192(2):396--413, 2009. Errata: 15th line of Table 4 should be: 16 4 4 42 204 9388 5580 74.94 3310 4246 4187.86 4.49 9.00. [ bib | .pdf ] |
[36] | Patrick Siarry and Éric D. Taillard. Feature cluster INCOM 2006 metaheuristics: Transportation and logistics. European Journal of Operational Research, 195(3):701--702, 2009. [ bib | .pdf ] |
[37] | Alexander Ostertag, Karl F. Doerner, Richard F. Hartl, Éric D. Taillard, and Philippe Waelti. Popmusic for a real-world large-scale vehicle routing problem with time windows. JORS, 60(7):934--943, 2009. [ bib | .pdf ] |
[38] | Ernst Versteeg, Éric D. Taillard, Patrick Bailly, and Maxence Laurent. System and method for determining a location area of a mobile user. European Patent Office, 2009. Patent: EP 2 071 355 A1. [ bib | .pdf ] |
[39] | Ernst Versteeg, Éric D. Taillard, Patrick Bailly, and Maxence Laurent. System and method for determining a location area of a mobile user. US Patent Application Publication, 2009. Patent: US 2009/0156231 A1. [ bib | .pdf ] |
[40] | Éric D. Taillard and Marino Widmer. Feature cluster on papers presented at the francoro iv conference. European Journal of Operational Research, 185(3):1274--1275, 2008. [ bib | .pdf ] |
[41] | Éric D. Taillard, Philippe Waelti, and Jacques Zuber. Few statistical tests for proportions comparison. European Journal of Operational Research, 185(3):1336--1350, 2008. [ bib | .pdf ] |
[42] | Xavier Gandibleux and Eric Taillard. Sweep and path re-linking for biobjective qap. In Euro XXII : 22nd European Conference on Operational Research, Prague, Czech Republic, 2007. [ bib | .pdf ] |
[43] | David A. Elizondo, Ralph Birkenhead, Mario A. Góngora, Éric D. Taillard, and Patrick Luyima. Analysis and test of efficient methods for building recursive deterministic perceptron neural networks. Neural Networks, 20(10):1095--1108, 2007. [ bib | .pdf ] |
[44] | Éric D. Taillard, Laura Helena Raileanu, and Philippe Waelti. Preprocessing and clustering large-scaled data-mining problem instances. In Metaheuristic International Conference (MIC'07) proceedings, 2007. [ bib | .pdf ] |
[45] | Adriana C. F. Alvim and Éric D. Taillard. An efficient POPMUSIC based approach to the point feature label placement problem. In Metaheuristic International Conference (MIC'07) proceedings, 2007. [ bib | .pdf ] |
[46] | Alexander Ostertag, Karl F. Doerner, Richard F. Hartl, Éric D. Taillard, and Philippe Waelti. POPMUSIC for real world large scale multi depot vehicle routing problem with time windows. In Metaheuristic International Conference (MIC'07) proceedings, 2007. [ bib | .pdf ] |
[47] | Peter Greistorfer and Éric D. Taillard. On the use of permutation distances in metaheuristics. In Metaheuristic International Conference (MIC'07) proceedings, 2007. [ bib | .pdf ] |
[48] | Maxence Laurent, Éric D. Taillard, Michel Toulouse, and Teo Crainic. Parallel noising methods embedded in an adaptive memory. In Metaheuristic International Conference (MIC'07) proceedings, 2007. [ bib | .pdf ] |
[49] | Johan Dreho, A. Pétrowsky, Patrick Siarry, and Éric D. Taillard. Metaheuristics for Hard Optimization: Methods and Case Studies. Springer, 2006. [ bib ] |
[50] | David A. Elizondo, Ralph Birkenhead, and Éric D. Taillard. The generalisation of the recursive deterministic perceptron. In Proceedings of the International Joint Conference on Neural Networks, IJCNN 2006, part of the IEEE World Congress on Computational Intelligence, WCCI 2006, Vancouver, BC, Canada, 16-21 July 2006, pages 1776--1783, 2006. [ bib | .pdf ] |
[51] | Éric D. Taillard. Tutorial : Few guidelines for analyzing methods. In Metaheuristic International Conference (MIC'05) proceedings, 2005. [ bib | .pdf ] |
[52] | A. Alvim and Éric D. Taillard. POPMUSIC for the point feature label placement. In Metaheuristic International Conference (MIC'05) proceedings, 2005. [ bib | .pdf ] |
[53] | Zvi Drezner, Peter M. Hahn, and Éric D. Taillard. Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Annals OR, 139(1):65--94, 2005. [ bib | .pdf ] |
[54] | Éric D. Taillard, Marino Widmer, and Philippe Waelti, editors. Actes des quatrièmes journées francophones de recherche opérationnelle, Fribourg, Suisse, 1821 Août 2004, 2004. [ bib | .pdf ] |
[55] | Éric D. Taillard, Philippe Waelti, and Jacques Zuber. Un nouveau test statistique pour la comparaison de proportions. In Actes des quatrièmes journées francophones de recherche opérationnelle, 2004. [ bib | .pdf ] |
[56] | Éric D. Taillard and Gregory Burri. POPMUSIC pour le placement de légende sur des plans. In Actes des quatrièmes journées francophones de recherche opérationnelle, 2004. [ bib | .pdf ] |
[57] | Éric D. Taillard. Heuristic methods for large centroid clustering problems. J. Heuristics, 9(1):51--73, 2003. Old technical report IDSIA-96-96. [ bib | DOI | .pdf ] |
[58] | Éric D. Taillard. A statistical test for comparing success rates. In Metaheuristic International Conference (MIC'03) proceedings, 2003. [ bib | .pdf ] |
[59] |
Johann Dreo, Alain Petrowski, Éric D. Taillard, and Patrick Siarry.
Métaheuristiques pour l'optimisation difficile.
Eyrolles (Editions), November 2003.
[ bib |
http ]
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 |
[60] | Bernard Renaud, Éric D. Taillard, Sosthène Berger, and M. Perraudin. Simulation d'accidents de dépressurisation. Visions, Revue Scientifique de l'EIVD, pages 11--16, 2002. [ bib | .pdf ] |
[61] | Éric D. Taillard. Principes d'implémentation des métaheuristiques". In Jacques Teghem and Marc Pirlot, editors, Optimisation approchée en recherche opérationnelle, pages 57--79. Hermès, 2002. [ bib | .pdf ] |
[62] | Éric D. Taillard, Luca Maria Gambardella, Michel Gendreau, and Jean-Yves Potvin. Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 135(1):1--16, 2001. [ bib | .pdf ] |
[63] | Éric D. Taillard and Stefan Voss. POPMUSIC: Partial optimization metaheuristic under special intensification conditions. In C. Ribeiro and P. Hansen, editors, Essays and surveys in metaheuristics, pages 613--629. Kluwer Academic Publishers, 2001. [ bib | .pdf ] |
[64] | Éric D. Taillard. Comparison of non-deterministic iterative methods. In Metaheuristic International Conference (MIC'01) proceedings, 2001. [ bib | .pdf ] |
[65] | Éric D. Taillard. An introduction to ant systems. In Manuel Laguna and José González-Velarde, editors, Computing Tools for Modeling, Optimization and Simulation, pages 131--144. Wiley, 2000. Old technical report idsia-05-99. [ bib | .pdf ] |
[66] |
Jack Brimberg, Pierre Hansen, Nenad Mladenovic, and Éric D. Taillard.
Improvements and comparison of heuristics for solving the
uncapacitated multisource weber problem.
Operations Research, 48(3):pp. 444--460, 2000.
Old technical report IDSIA-33-97.
[ bib |
http ]
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. |
[67] | Éric D. Taillard, , Giovanni Agazzi, and Luca-Maria Gambardella. Des fourmis pour livrer du mazout. Visions, Revue Scientifique de l'EIVD, pages 3--7, 2000. [ bib | .pdf ] |
[68] |
Éric D. Taillard.
A heuristic column generation method for the heterogeneous fleet vrp.
RAIRO - Operations Research, 33(01):1--14, 1999.
[ bib |
DOI |
.pdf ]
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. |
[69] |
Luca-Maria Gambardella L.M., Éric D. Taillard, and Marco Dorigo.
Ant colonies for the quadratic assignment problem.
Journal of the Operational Research Society, 50(2):167--176,
1999.
Old technical report IDSIA-4-97.
[ bib |
.pdf ]
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 |
[70] | Luca Maria Gambardella, Éric D. Taillard, and Giovanni Agazzi. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. In David Corne, Marco Dorigo, Fred Glover, Dipankar Dasgupta, Pablo Moscato, Riccardo Poli, and Kenneth V. Price, editors, New ideas in optimization, pages 63--76. McGraw-Hill Ltd., UK, Maidenhead, UK, England, 1999. Old technical report /idsia_06_99. [ bib | .pdf ] |
[71] | Michel Gendreau, Gilbert Laporte, Christophe Musaraganyi, and Éric D. Taillard. A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & OR, 26(12):1153--1173, 1999. [ bib | .pdf ] |
[72] | Michel Gendreau, François Guertin, Jean-Yves Potvin, and Éric D. Taillard. Parallel tabu search for real-time vehicle routing and dispatching. Transportation Science, 33(4):381--390, 1999. [ bib | .pdf ] |
[73] |
Pierre Hansen, Nenad Mladenovic, and Éric D. Taillard.
Heuristic solution of the multisource weber problem as a p-median
problem.
Operations Research Letters, 22(2-3):55--62, 1998.
[ bib |
.pdf ]
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 |
[74] | Éric D. Taillard. La programmation à mémoire adaptative et les algorithmes pseudo-gloutons: nouvelles perspectives pour les méta-heuristiques. PhD thesis, Université de Versailles-Saint-Quentin-en-Yvelines, Versailles, 1998. [ bib | .pdf | .ps ] |
[75] | Éric D. Taillard. Fant: Fast ant system. Technical report, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, 1998. IDSIA Technical Report IDSIA-46-98. [ bib ] |
[76] |
Éric D. Taillard, Luca-Maria Gambardella, Michel Gendreau, and Jean-Yves
Potvin.
La programmation adaptative ou l'évolution des algorithmes
évolutifs.
Calculateurs Parallèles, 10(2), 1998.
[ bib |
.pdf ]
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. |
[77] |
Philippe Badeau, Francois Guertin, Michel Gendreau, Jean-Yves Potvin, and
Éric D. Taillard.
A parallel tabu search heuristic for the vehicle routing problem with
time windows.
Transportation Research Part C: Emerging Technologies, 5(2):109
-- 122, 1997.
Old technical report CRT95_84.
[ bib |
DOI |
.pdf ]
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 |
[78] | Éric D. Taillard and Luca-Maria Gambardella. Adaptive memories for the quadratic assignment problems. Technical report, IDSIA, 1997. IDSIA Technical Report ISDIA-87-97. [ bib | .pdf ] |
[79] | Éric D. Taillard. An ant approach for structured quadratic assignment problems. In Metaheuristic International Conference (MIC'97) proceedings, 1997. Technical report IDSIA-22-97. [ bib | .pdf ] |
[80] | Bruce L. Golden, Gilbert Laporte, and Éric D. Taillard. An adaptive memory heuristic for a class of vehicle routing problems with minmax objective. Computers & OR, 24(5):445--452, 1997. Old technical report CRT95-74. [ bib | .pdf ] |
[81] | Éric D. Taillard, Philippe Badeau, Michel Gendreau, François Guertin, and Jean-Yves Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2):170--186, 1997. Old technical report CRT95_66. [ bib | .pdf ] |
[82] | Alain Hertz, Éric D. Taillard, and Dominique de Wera. Tabu search. In Emile Aarts and Jan Karel Lenstra, editors, Local Search in Combinatorial Optimization, pages 121--136. Wiley, 1997. Old technical report ORWP9218. [ bib | .pdf ] |
[83] | Éric D. Taillard, Gilbert Laporte, and Michel Gendreau. Vehicle routeing with multiple use of vehicles. Journal of the Operations Society, 47:1065--1070, 1996. Old technical report CRT95_19. [ bib | .pdf ] |
[84] | Luca Gambardella, Gianluca Bontempi, Éric D. Taillard, Davide Romanengo, Guido Raso, and Pietro Piermari. Simulation and forecasting in intermodal container terminal. In Proceedings of the 8th European Simulation Symposium, 1996. [ bib | .pdf ] |
[85] |
Michel Gendreau, P. Badeau, F. Guertin, and Jean-Yves Potvin andÉric
D. Taillard.
A solution procedure for real-time routing and dispatching of
commercial vehicles.
In Prooceedings of the Third World Congress on Intelligent
Transport Systems, 1996.
[ bib ]
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. |
[86] | Yves Rochat and Éric D. Taillard. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1:147--167, 1995. Old technical report CRT95_13. [ bib | .pdf ] |
[87] |
Éric D. Taillard.
Comparison of iterative searches for the quadratic assignment
problem.
Location Science, 3(2):87 -- 105, 1995.
Old technical report CRT989.
[ bib |
DOI |
.pdf ]
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 |
[88] | Éric D. Taillard. Parallel taboo search techniques for the job shop scheduling problem. INFORMS Journal on Computing, 6(2):108--117, 1994. [ bib | .pdf ] |
[89] | Éric D. Taillard. Recherches itératives dirigées parallèles. PhD thesis, EPFL, Lausanne, 1993. [ bib | DOI | .pdf ] |
[90] | Fred Glover, Éric D. Taillard, and Dominique de Werra. A user's guide to tabu search. Annals of Operations Research, 41:1--28, 1993. 10.1007/BF02078647. [ bib | .pdf ] |
[91] |
Éric D. Taillard.
Parallel iterative search methods for vehicle routing problems.
Networks, 23(8):661--673, 1993.
[ bib |
DOI |
.pdf ]
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. |
[92] | Éric D. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278--285, 1993. Old technical report ORWP89_21. [ bib | .pdf ] |
[93] | Fred Glover, Manuel Laguna, Éric D. Taillard, and Dominique de Werra. Annals of or 41. In Tabu Search. Baltzer, 1993. [ bib ] |
[94] |
Frédéric Semet and Éric D. Taillard.
Solving real-life vehicle routing problems efficiently using tabu
search.
Ann. Oper. Res., 41(1-4):469--488, May 1993.
[ bib |
http ]
Keywords: combinatorial optimization, tabu search, vehicle routing problem |
[95] | Éric D. Taillard. Robust taboo search for the quadratic assignment problem. Parallel Computing, 17(4-5):443--455, 1991. [ bib | .pdf ] |
[96] |
Éric D. Taillard.
Some efficient heuristic methods for the flow shop sequencing
problem.
European Journal of Operational Research, 47(1):65--74, July
1990.
Old technical report ORWP88_12.
[ bib |
.pdf ]
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 |
This file was generated by bibtex2html 1.99.