[1] Éric D. Taillard and Keld Heslgaun. POPMUSIC for the travelling salesman problem. EURO Journal of Operational Research, 2018. [ 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.

[2] É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 ]
[3] Éric D. Taillard. TSP neighbourhood reduction with POPMUSIC. In Metaheuristic Interantional Conference (MIC'17) proceedings, 2017. [ bib | .pdf ]
[4] Éric D. Taillard. Tabu search. In Patrick Siarry, editor, Metaheuristics, pages 51--76. Springer International Publishing, Cham, 2016. [ bib | DOI | http ]
[5] Éric D. Taillard. Methodology. In Patrick Siarry, editor, Metaheuristics, pages 357--379. Springer International Publishing, Cham, 2016. [ bib | DOI | http ]
[6] 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.

[7] Éric D. Taillard, Adriana C. F. Alvim, and Voss. A template for low-complexity implementation of popmusic. In Metaheuristic Interantional Conference (MIC'15) proceedings, 2015. [ bib | .pdf ]
[8] Éric D. Taillard. La recherche avec tabous. In P. Siarry (ed.), editor, Métaheuristiques, pages 49--72. Eyrolles, 2014. [ bib ]
[9] É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 ]
[10] 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 ]
[11] 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 | .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(n3/2) a solution to the capacitated p-median problem. The method is tested on location routing instances with millions of entities.

[12] 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.

[13] É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 ]
[14] Adriana C. F. Alvim and Éric D. Taillard. POPMUSIC for the world location routing problem. In Metaheuristic Interantional Conference (MIC'11) proceedings, 2011. [ bib | .pdf ]
[15] É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.

[16] 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 Interantional Conference (MIC'09) proceedings, 2009. [ bib | .pdf ]
[17] 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 ]
[18] 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 ]
[19] 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 ]
[20] 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 ]
[21] 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 ]
[22] É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 ]
[23] É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 ]
[24] 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 ]
[25] 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 ]
[26] Éric D. Taillard, Laura Helena Raileanu, and Philippe Waelti. Preprocessing and clustering large-scaled data-mining problem instances. In Metaheuristic Interantional Conference (MIC'07) proceedings, 2007. [ bib | .pdf ]
[27] Adriana C. F. Alvim and Éric D. Taillard. An efficient POPMUSIC based approach to the point feature label placement problem. In Metaheuristic Interantional Conference (MIC'07) proceedings, 2007. [ bib | .pdf ]
[28] 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 Interantional Conference (MIC'07) proceedings, 2007. [ bib | .pdf ]
[29] Peter Greistorfer and Éric D. Taillard. On the use of permutation distances in metaheuristics. In Metaheuristic Interantional Conference (MIC'07) proceedings, 2007. [ bib | .pdf ]
[30] Maxence Laurent, Éric D. Taillard, Michel Toulouse, and Teo Crainic. Parallel noising methods embedded in an adaptive memory. In Metaheuristic Interantional Conference (MIC'07) proceedings, 2007. [ bib | .pdf ]
[31] Johan Dreho, A. Pétrowsky, Patrick Siarry, and Éric D. Taillard. Metaheuristics for Hard Optimization: Methods and Case Studies. Springer, 2006. [ bib ]
[32] 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 ]
[33] Éric D. Taillard. Tutorial : Few guidelines for analyzing methods. In Metaheuristic Interantional Conference (MIC'05) proceedings, 2005. [ bib | .pdf ]
[34] A. Alvim and Éric D. Taillard. POPMUSIC for the point feature label placement. In Metaheuristic Interantional Conference (MIC'05) proceedings, 2005. [ bib | .pdf ]
[35] 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 ]
[36] É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 ]
[37] É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 ]
[38] É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 ]
[39] Éric D. Taillard. Heuristic methods for large centroid clustering problems. J. Heuristics, 9(1):51--73, 2003. Old technical report IDSIA-96-96. [ bib | .pdf ]
[40] Éric D. Taillard. A statistical test for comparing success rates. In Metaheuristic Interantional Conference (MIC'03) proceedings, 2003. [ bib | .pdf ]
[41] 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 cou╠é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
[42] 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 ]
[43] É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 ]
[44] É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 ]
[45] É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 ]
[46] Éric D. Taillard. Comparison of non-deterministic iterative methods. In Metaheuristic Interantional Conference (MIC'01) proceedings, 2001. [ bib | .pdf ]
[47] É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 ]
[48] 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.

[49] É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 ]
[50] É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.

[51] 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

[52] 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 ]
[53] 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 ]
[54] 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 ]
[55] 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
[56] É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 ]
[57] É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 ]
[58] É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.

[59] 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

[60] É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 ]
[61] Éric D. Taillard. An ant approach for structured quadratic assignment problems. In Metaheuristic Interantional Conference (MIC'97) proceedings, 1997. Technical report IDSIA-22-97. [ bib | .pdf ]
[62] 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 ]
[63] É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 ]
[64] 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 ]
[65] É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 ]
[66] 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 ]
[67] 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.

[68] 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 ]
[69] É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
[70] Éric D. Taillard. Parallel taboo search techniques for the job shop scheduling problem. INFORMS Journal on Computing, 6(2):108--117, 1994. [ bib | .pdf ]
[71] Éric D. Taillard. Recherches itératives dirigées parallèles. PhD thesis, EPFL, Lausanne, 1993. [ bib | DOI | .pdf ]
[72] 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 ]
[73] É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.

[74] É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 ]
[75] Fred Glover, Manuel Laguna, Éric D. Taillard, and Dominique de Werra. Annals of or 41. In Tabu Search. Baltzer, 1993. [ bib ]
[76] 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
[77] Éric D. Taillard. Robust taboo search for the quadratic assignment problem. Parallel Computing, 17(4-5):443--455, 1991. [ bib | .pdf ]
[78] É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.98.