论文部分内容阅读
Abstract: Many optimization problems (from academia or industry) require the use of a metaheuristic to find a satisfying solution in a reasonable amount of time, even if optimality is not guaranteed. Metaheuristics can be roughly partitioned in two groups: local search methods (e.g., simulated annealing, tabu search, and variable neighborhood search) and population based algorithms (e.g., genetic algorithms, ant colonies, and scatter search). The reader is assumed to be familiar with the most popular metaheuristics. Even if there exist convergence theorems for some metaheuristics, they usually do not help to develop an efficient metaheuristic. The goal of this paper is to propose general rules which are useful when designing metaheuristics in order to produce good performance according to several criteria, independently of the class of metaheuristics employed. The discussion is illustrated for three well-known optimization problems: graph coloring, vehicle routing and job-shop scheduling.
Key words: Metaheuristics, local search, population based algorithms, optimization.
1. Introduction
Modern methods for solving complex optimization problems are often divided into exact methods and metaheuristic methods. An exact method guarantees that an optimal solution will be obtained in a finite amount of time. Among the exact methods are branch-and-bound, dynamic programming, Lagrangian relaxation based methods, and linear and integer programming based methods [1]. However, for a large number of applications and most real-life optimization problems, which are typically NP-hard [2], such methods need a prohibitive amount of time to find an optimal solution. For these difficult problems, it is preferable to quickly find a satisfying solution. If solution quality is not a dominant concern, then a simple heuristic can be employed, while if quality occupies a more critical role, then a more advanced metaheuristic procedure is warranted.
The word heuristic is from the Greek and means “to find”. The term metaheuristic was first introduced in Ref. [3], where “meta” is also from the Greek and means “beyond, in an upper level”. Many definitions of metaheuristics can be found in Ref. [4]. The following definition is given in Ref. [5]: A metaheuristic is formally defined as an iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space, learning strategies are used to structure information in order to find efficiently near-optimal solutions. There also exists a class of algorithms which combine exact methods and metaheuristics. For a survey on that topic, the reader is referred to Refs. [6-7]. More generally, a unified view on hybrid metaheuristics is given in Ref. [8]. No specific focus will be given here on such methods. There exist several ways of classifying metaheuristics [4, 9-10], but the focus will be on partitioning them into two classes: local search and population based methods. A local search method starts with an initial solution and tries to improve it iteratively. At each iteration, a modification of the current solution, called a move, is performed in order to generate a neighbor solution. The definition of a move, i.e., the definition of the neighborhood structure, depends on the problem considered. In contrast, population based methods, also called evolutionary algorithms, can be defined as iterative procedures that use a central memory to store and operate on certain solutions collected during the search process. Each iteration, called a generation, involves two complementary ingredients: cooperation and self-adaptation. In the cooperation effort, the central memory is used to build new offspring solutions, while self-adaptation consists of individually modifying the offspring solutions. The output solutions of the self-adaptation phase are used for updating the content of the central memory. In some population based algorithms, the self-adaptation phase can be performed with the use of a local search which is applied individually to some of the offspring solutions. For simplicity, such algorithms are also classified in population based methods.
Among the most popular local search methods are simulated annealing, tabu search, variable neighborhood search, and guided local search, while the most used population based methods are genetic algorithms, ant colonies, scatter search, adaptive memory algorithms, and memetic search [11]. Theoretically, there exist some convergence theorems associated with the use of metaheuristics [12-14]. Such theorems state that the search has a high probability to find an optimal solution, but in a very large amount of time, which is likely to be larger than the time needed for a complete enumeration. Therefore, such theoretical results do not have any impact in practice, and do not help to efficiently design a metaheuristic.
The performance of a metaheuristic can be evaluated according to several criteria. The most relevant criteria are (1) quality—value of the obtained results, according to a given objective function f (assumed to be minimized); (2) speed—time needed to get good results; (3) robustness—sensitivity to variations in problem characteristics and data quality; (4) ease of adaptation—the ability to organize the method so that it can appropriately apply to different specific classes of problems; (5) ability to take advantage of problem structure (considering that efficiency often depends on making effective use of properties that differentiate a given class of problems from other classes). It is usually difficult to design a metaheuristic which ranks highly by all of the preceding criteria. The reader is assumed to be at least moderately familiar with the topic of metaheuristics in general, because in contrast with existing state-of-the-art papers of tutorial nature or books [4-5, 11, 15], the goal of this paper is neither to present or discuss the most popular metaheuristics, nor to numerically compare various metaheuristics. Instead are proposed several rules to build a metaheuristic that performs well, regardless of the class of methods it represents. A few rules can already be found (with different formulations) in other papers [4, 9, 16], but this paper will propose a more exhaustive list of rules using simple formulations. This goal is reinforced in a manner to make the discussion more easily accessible to readers, by illustrating every rule according to three different well-known problems, which are graph coloring, vehicle routing and job-shop scheduling. No numerical comparison will be performed for these problems: such comparisons already exist in the literature but usually according to two criteria only, which are quality and speed. This paper is not limited to these common criteria and is positioned at a higher level, as it derives general lessons that can be made from existing algorithms in order to help the design of efficient metaheuristic for other combinatorial problems.
The paper is organized as follows: Section 2 describes the three well-known problems which will be considered for the discussion; section 3 then proposes useful rules for the design of any metaheuristic; in sections 4-5, relevant principles for the development of local search methods and respectively for population based algorithms are presented; the paper gives general conclusions in section 6.
2. Presentation of the Considered Problems
References
[1] G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
[2] M. Garey, D. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
[3] F. Glover, Future paths for integer programming and linkage to artificial intelligence, Computers & Operations Research 13 (1986) 533-549.
[4] C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys 35 (3) (2003) 268-308.
[5] I.H. Osman, G. Laporte, Metaheuristics: A bibliography, Annals of Operations Research 63 (1996) 513-623.
[6] I. Dumitrescu, T. Stuetzle, Combinations of local search and exact algorithms, Lecture Notes in Computer Science 2611 (2003) 211-223. [7] J. Puchinger, G.R. Raidl, Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification, Lecture Notes in Computer Sciences 3562 (2005) 41-53.
[8] G.R. Raidl, A unified view on hybrid metaheuristics, Lecture Notes in Computer Sciences 4030 (2006) 1-12.
[9] E.D. Taillard, L.M. Gambardella, M. Gendreau, J.-Y. Potvin, Adaptive memory programming: A unified view of metaheuristics, European Journal of Operational Research 135 (2001) 1-16.
[10] E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of Heuristics 8 (5) (2002) 541-564.
[11] M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, Springer, 2010.
[12] B. Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research 13 (1988) 311-329.
[13] U. Faigle, W. Kern, Some convergence results for probabilistic tabu search, ORSA Journal on Computing 4(1992) 32-37.
[14] F. Glover, S. Hanafi, Tabu search and finite convergence, Discrete Applied Mathematics 119 (2002) 3-36.
[15] F. Glover, G. Kochenberger, Handbook of Metaheuristics, Kluwer Academic Publishers, 2003.
[16] A. Hertz, M. Widmer, Guidelines for the use of meta-heuristics in combinatorial optimization, European Journal of Operational Research 151 (2003) 247-252.
[17] E. Malaguti, P. Toth, A survey on vertex coloring problems, International Transactions in Operational Research 17 (1) (2006) 1-34.
[18] M. Plumettaz, D. Schindl, N. Zufferey, Ant local search and its efficient adaptation to graph colouring, Journal of the Operational Research Society 61 (2010) 819-826.
[19] P. Toth, D. Vigo, Exact solution of the vehicle routing problem, in: T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, Kluwer Academic Publishers, Boston, 1998, pp. 1-31.
[20] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, F. Semet, A guide to vehicle routing heuristics, Journal of the Operational Research Society 53 (5) (2002) 512-522.
[21] G. Laporte, F. Semet, Classical heuristics for the capacitated VRP, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 109-128.
[22] M. Gendreau, G. Laporte, J.-Y. Potvin, Metaheuristics for the VRP, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 129-154.
[23] A.A. Jain, S. Meeran, Deterministic job-shop scheduling: Past, present and future, European Journal of Operational Research 113 (1999) 390-434.
[24] R. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithm, part I: Representation, International Journal of Computers and Industrial Engeneering 30 (1996) 983-997. [25] R. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies, Computers & Industrial Engineering 36 (1999) 343-364.
[26] J. Culberson, Iterated greedy graph coloring and the difficulty landscape, Tech. Rep. TR 92-07, Department of Computer Science, University of Alberta, Edmonton, 1992.
[27] C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (2004) 1985-2002.
[28] M. Gendreau, A. Hertz, G. Laporte, A tabu search heuristic for the vehicle routing problem, Management Science 40 (1994) 1276-1290.
[29] M. Vasquez, A. Dupont, D. Habet, Consistent neighbourhood in a tabu search, in: T. Ibaraki, K. Nonobe, M. Yagiura (Eds.), Metaheuristics: Progress as Real Problem Solvers, Springer-Verlag, 2005, pp. 369-388.
[30] A. Hertz, D. de Werra, Using tabu search techniques for graph coloring, Computing 39 (1987) 345-351.
[31] C. Morgenstern, Distributed coloration neighborhood search, in: D.S. Johnson, M.A. Trick (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1996, pp. 335-358.
[32] I. Bloechliger, N. Zufferey, A graph coloring heuristic using partial solutions and a reactive tabu scheme, Computers & Operations Research 35 (2008) 960-975,.
[33] E. Malaguti, M. Monaci, P. Toth, A metaheuristic approach for the vertex coloring problem, INFORMS Journal on Computing 20 (2) (2008) 302-316.
[34] J.T. Richardson, M.R. Palmer, G.E. Liepins, M.R. Hilliard, Some guidelines for genetic algorithms with penalty functions, in: Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, 1989, pp. 191-197.
[35] R.W. Hamming, Error-detecting and error-correcting codes, Bell System Technical Journal 2 (29) (1950) 147-160.
[36] R. Real, J.M. Vargas, The probabilistic basis of Jaccard’s index of similarity, Sistematic Biology 45 (3) (1996) 380-385.
[37] D. Chams, A. Hertz, D. de Werra, Some experiments with simulated annealing for coloring graphs, European Journal of Operational Research 32 (1987) 260-266.
[38] M. Gendreau, A. Hertz, G. Laporte, New insertion and postoptimization procedures for the traveling salesman problem, Operations Research 40 (1992) 1086-1094.
[39] E.D. Taillard, Parallel iterative search methods for vehicle routing problems, Networks 23 (1993) 661-673. [40] A. Volgenant, R. Jonker, The symmetric traveling salesman problem and edge exchanges in minimal 1-tree, European Journal of Operational Research 12 (1983) 394-403.
[41] N. Mladenovic, P. Hansen, Variable neighborhood search, Computers & Operations Research 24 (1997) 1097-1100.
[42] C. Avanthay, A. Hertz, N. Zufferey, A variable neighborhood search for graph coloring, European Journal of Operational Research 151(2003) 379-388.
[43] C. Fleurent, J.A. Ferland, Genetic and hybrid algorithms for graph coloring, Annals of Operations Research 63 (3)(1996) 437-461.
[44] J.-P. Watson, J.C. Beck, A.E. Howe, D. Withley, Problem difficulty for tabu search in job-shop scheduling, Artificial Intelligence 143 (2) (2003) 189-217.
[45] D.C. Mattfeld, C. Bierwirth, H. Kopfer, A search space analysis of the job shop scheduling problem, Annals of Operations Research 86 (1999) 441-453.
[46] E.D. Taillard, Parallel-taboo search techniques for the job shop scheduling problem, ORSA Journal on Computing 6(1994) 108-117.
[47] C. Bessière, Arc-consistency and arc-consistency again, Artificial Intelligence 65 (1994) 179-190.
[48] D. Johnson, C. Aragon, L. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation, Part II: Graph coloring and number partitioning, Operations Research 39 (1991) 378-406.
[49] J. Shawe-Taylor, J. Zerovnik, Ants and graph coloring, in: Proceedings of ICANNGA’01, Prague, 2001, pp. 276-279.
[50] P. Toth, D. Vigo, The granular tabu search (and its application to the vehicle routing problem), Tech. Rep. OR-98-9, DEIS-Univertity of Bologna, Italy, 1998.
[51] D. Costa, A. Hertz, Ants can colour graphs, Journal of the Operational Research Society 48 (1997) 295-305.
[52] Y. Rochat, E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics 1 (1995) 147-167.
[53] M. Dorigo, T. Stuetzle, The ant colony optimization metaheuristic: algorithms, applications, and advances, in: F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, 2002, pp. 251-285.
[54] A. Hertz, N. Zufferey, A new ant colony algorithm for graph coloring, in: Proceedings of NICSO 2006, Granada, Spain, 2006, pp. 51-60.
[55] H. Kawamura, M. Yamamoto, T. Mitamura, K. Suzuki, A. Ohuchi, Cooperative search based on pheromone communication for vehicle routing problems, IEEE Transactions on Fundamentals E81-A (1998) 1089-1096.
[56] B. Bullnheimer, R.F. Hartl, C. Strauss, Applying the ant system to the vehicle routing problem, in: S. Voβ, S. Martello, I.H. Osman, C. Roucairol (Eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, 1998, pp. 109-120. [57] B. Bullnheimer, R.F. Hartl, C. Strauss, An improved ant system for the vehicle routing problem, Annals of Operations Research 89 (1999) 319-328.
[58] M. Reimann, K. Doerner, R.F. Hartl, Analysing a unified ant system for the VRP and some of its variants, Lecture Notes in Computer Sciences 2611 (2003) 300-310.
[59] B. Yu, Z.-Z. Yang, B.Z. Yao, An improved ant colony optimization for vehicle routing problem, European Journal of Operational Research 196 (2009) 171-176.
[60] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, Ant system for job-shop scheduling, Belgian Journal of Operations Research Letters Research 34 (1994) 39-53.
[61] K.-L. Huang, C.-J. Liao, Ant colony optimization combined with taboo search for the job-shop scheduling problem, Computers & Operations Research 35 (2008) 1030-1046.
[62] J. Xu, J. Kelly, A network flow-based tabu search heuristic for the vehicle routing problem, Transportation Science 30 (1996) 379-393.
[63] S. Lin, Computer solutions of the traveling salesman problem, Bell System Technical Journal 44 (1965) 2245-2269.
[64] E. Nowicki, C. Smutnicki, A fast taboo search algorithm for the job shop problem, Management Science 42 (6)(1996) 797-813.
[65] H. Hoos, Stochastic local search—methods, models, applications, Ph.D. Thesis, Darmstadt University of Technology, 1998.
[66] I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research 41 (1993) 421-451.
[67] C. Rego, C. Roucairol, A parallel tabu search algorithm using ejection chains for the vehicle routing problem, in: I.H. Osman, J.P. Kelly (Eds.), Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, 1996, pp. 661-675.
[68] P.J.M.V. Laarhoven, E.H.L. Aarts, J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40 (1992) 113-125.
[69] E. Balas, A. Vazacopoulos, Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Tech. Rep. MSRR-609, School of Industrial Administration, Carnergie Mellon University, Pittsburg, 1994.
[70] D. Applegate, W. Cook, A computational study of the job-shop scheduling problem, ORSA Journal on Computing 3 (1991) 149-156.
[71] F. Robusté, C.F. Daganzo, R. Souleyrette, Implementing vehicle routing models, Transportation Research, Part B: Methodological 24 (4) (1990) 263-286.
[72] J. Adams, E. Balas, D. Zawak, The shifting bottleneck procedure for job shop scheduling, Management Science 34 (1988) 391-401. [73] E. Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Operations Research 17(1969) 941-957.
[74] H. Matsuo, C.J. Suh, R.S. Sullivan, A controlled search simulated annealing method for the general jobshop scheduling problem, Tech. Rep. 03-04-88, Graduate School of Business, University of Texas, Austin, 1988.
[75] P. Galinier, A. Hertz, N. Zufferey, An adaptive memory algorithm for the graph coloring problem, Discrete Applied Mathematics 156 (2008) 267-279.
[76] P. Galinier, J.-K. Hao, Hybrid evolutionary algorithms for graph coloring, Journal of Combinatorial Optimization 3(4) (1999) 379-397.
[77] C.-D. Tarantilis, C.T. Kiranoudis, Bone route: An adaptive memory-based method for effective fleet management, Annals of Operations Research 115 (2002) 227-241.
[78] J.-F. Cordeau, G. Laporte, A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society 52(2001) 928-936.
[79] D. Mester, O. Braysy, Active guided evolution strategies for large-scale vehicle routing problems with time windows, Computers & Operations Research 32 (2005) 1593-1614.
Key words: Metaheuristics, local search, population based algorithms, optimization.
1. Introduction
Modern methods for solving complex optimization problems are often divided into exact methods and metaheuristic methods. An exact method guarantees that an optimal solution will be obtained in a finite amount of time. Among the exact methods are branch-and-bound, dynamic programming, Lagrangian relaxation based methods, and linear and integer programming based methods [1]. However, for a large number of applications and most real-life optimization problems, which are typically NP-hard [2], such methods need a prohibitive amount of time to find an optimal solution. For these difficult problems, it is preferable to quickly find a satisfying solution. If solution quality is not a dominant concern, then a simple heuristic can be employed, while if quality occupies a more critical role, then a more advanced metaheuristic procedure is warranted.
The word heuristic is from the Greek and means “to find”. The term metaheuristic was first introduced in Ref. [3], where “meta” is also from the Greek and means “beyond, in an upper level”. Many definitions of metaheuristics can be found in Ref. [4]. The following definition is given in Ref. [5]: A metaheuristic is formally defined as an iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space, learning strategies are used to structure information in order to find efficiently near-optimal solutions. There also exists a class of algorithms which combine exact methods and metaheuristics. For a survey on that topic, the reader is referred to Refs. [6-7]. More generally, a unified view on hybrid metaheuristics is given in Ref. [8]. No specific focus will be given here on such methods. There exist several ways of classifying metaheuristics [4, 9-10], but the focus will be on partitioning them into two classes: local search and population based methods. A local search method starts with an initial solution and tries to improve it iteratively. At each iteration, a modification of the current solution, called a move, is performed in order to generate a neighbor solution. The definition of a move, i.e., the definition of the neighborhood structure, depends on the problem considered. In contrast, population based methods, also called evolutionary algorithms, can be defined as iterative procedures that use a central memory to store and operate on certain solutions collected during the search process. Each iteration, called a generation, involves two complementary ingredients: cooperation and self-adaptation. In the cooperation effort, the central memory is used to build new offspring solutions, while self-adaptation consists of individually modifying the offspring solutions. The output solutions of the self-adaptation phase are used for updating the content of the central memory. In some population based algorithms, the self-adaptation phase can be performed with the use of a local search which is applied individually to some of the offspring solutions. For simplicity, such algorithms are also classified in population based methods.
Among the most popular local search methods are simulated annealing, tabu search, variable neighborhood search, and guided local search, while the most used population based methods are genetic algorithms, ant colonies, scatter search, adaptive memory algorithms, and memetic search [11]. Theoretically, there exist some convergence theorems associated with the use of metaheuristics [12-14]. Such theorems state that the search has a high probability to find an optimal solution, but in a very large amount of time, which is likely to be larger than the time needed for a complete enumeration. Therefore, such theoretical results do not have any impact in practice, and do not help to efficiently design a metaheuristic.
The performance of a metaheuristic can be evaluated according to several criteria. The most relevant criteria are (1) quality—value of the obtained results, according to a given objective function f (assumed to be minimized); (2) speed—time needed to get good results; (3) robustness—sensitivity to variations in problem characteristics and data quality; (4) ease of adaptation—the ability to organize the method so that it can appropriately apply to different specific classes of problems; (5) ability to take advantage of problem structure (considering that efficiency often depends on making effective use of properties that differentiate a given class of problems from other classes). It is usually difficult to design a metaheuristic which ranks highly by all of the preceding criteria. The reader is assumed to be at least moderately familiar with the topic of metaheuristics in general, because in contrast with existing state-of-the-art papers of tutorial nature or books [4-5, 11, 15], the goal of this paper is neither to present or discuss the most popular metaheuristics, nor to numerically compare various metaheuristics. Instead are proposed several rules to build a metaheuristic that performs well, regardless of the class of methods it represents. A few rules can already be found (with different formulations) in other papers [4, 9, 16], but this paper will propose a more exhaustive list of rules using simple formulations. This goal is reinforced in a manner to make the discussion more easily accessible to readers, by illustrating every rule according to three different well-known problems, which are graph coloring, vehicle routing and job-shop scheduling. No numerical comparison will be performed for these problems: such comparisons already exist in the literature but usually according to two criteria only, which are quality and speed. This paper is not limited to these common criteria and is positioned at a higher level, as it derives general lessons that can be made from existing algorithms in order to help the design of efficient metaheuristic for other combinatorial problems.
The paper is organized as follows: Section 2 describes the three well-known problems which will be considered for the discussion; section 3 then proposes useful rules for the design of any metaheuristic; in sections 4-5, relevant principles for the development of local search methods and respectively for population based algorithms are presented; the paper gives general conclusions in section 6.
2. Presentation of the Considered Problems
References
[1] G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
[2] M. Garey, D. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
[3] F. Glover, Future paths for integer programming and linkage to artificial intelligence, Computers & Operations Research 13 (1986) 533-549.
[4] C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys 35 (3) (2003) 268-308.
[5] I.H. Osman, G. Laporte, Metaheuristics: A bibliography, Annals of Operations Research 63 (1996) 513-623.
[6] I. Dumitrescu, T. Stuetzle, Combinations of local search and exact algorithms, Lecture Notes in Computer Science 2611 (2003) 211-223. [7] J. Puchinger, G.R. Raidl, Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification, Lecture Notes in Computer Sciences 3562 (2005) 41-53.
[8] G.R. Raidl, A unified view on hybrid metaheuristics, Lecture Notes in Computer Sciences 4030 (2006) 1-12.
[9] E.D. Taillard, L.M. Gambardella, M. Gendreau, J.-Y. Potvin, Adaptive memory programming: A unified view of metaheuristics, European Journal of Operational Research 135 (2001) 1-16.
[10] E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of Heuristics 8 (5) (2002) 541-564.
[11] M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, Springer, 2010.
[12] B. Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research 13 (1988) 311-329.
[13] U. Faigle, W. Kern, Some convergence results for probabilistic tabu search, ORSA Journal on Computing 4(1992) 32-37.
[14] F. Glover, S. Hanafi, Tabu search and finite convergence, Discrete Applied Mathematics 119 (2002) 3-36.
[15] F. Glover, G. Kochenberger, Handbook of Metaheuristics, Kluwer Academic Publishers, 2003.
[16] A. Hertz, M. Widmer, Guidelines for the use of meta-heuristics in combinatorial optimization, European Journal of Operational Research 151 (2003) 247-252.
[17] E. Malaguti, P. Toth, A survey on vertex coloring problems, International Transactions in Operational Research 17 (1) (2006) 1-34.
[18] M. Plumettaz, D. Schindl, N. Zufferey, Ant local search and its efficient adaptation to graph colouring, Journal of the Operational Research Society 61 (2010) 819-826.
[19] P. Toth, D. Vigo, Exact solution of the vehicle routing problem, in: T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, Kluwer Academic Publishers, Boston, 1998, pp. 1-31.
[20] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, F. Semet, A guide to vehicle routing heuristics, Journal of the Operational Research Society 53 (5) (2002) 512-522.
[21] G. Laporte, F. Semet, Classical heuristics for the capacitated VRP, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 109-128.
[22] M. Gendreau, G. Laporte, J.-Y. Potvin, Metaheuristics for the VRP, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Philadelphia, 2002, pp. 129-154.
[23] A.A. Jain, S. Meeran, Deterministic job-shop scheduling: Past, present and future, European Journal of Operational Research 113 (1999) 390-434.
[24] R. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithm, part I: Representation, International Journal of Computers and Industrial Engeneering 30 (1996) 983-997. [25] R. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies, Computers & Industrial Engineering 36 (1999) 343-364.
[26] J. Culberson, Iterated greedy graph coloring and the difficulty landscape, Tech. Rep. TR 92-07, Department of Computer Science, University of Alberta, Edmonton, 1992.
[27] C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (2004) 1985-2002.
[28] M. Gendreau, A. Hertz, G. Laporte, A tabu search heuristic for the vehicle routing problem, Management Science 40 (1994) 1276-1290.
[29] M. Vasquez, A. Dupont, D. Habet, Consistent neighbourhood in a tabu search, in: T. Ibaraki, K. Nonobe, M. Yagiura (Eds.), Metaheuristics: Progress as Real Problem Solvers, Springer-Verlag, 2005, pp. 369-388.
[30] A. Hertz, D. de Werra, Using tabu search techniques for graph coloring, Computing 39 (1987) 345-351.
[31] C. Morgenstern, Distributed coloration neighborhood search, in: D.S. Johnson, M.A. Trick (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1996, pp. 335-358.
[32] I. Bloechliger, N. Zufferey, A graph coloring heuristic using partial solutions and a reactive tabu scheme, Computers & Operations Research 35 (2008) 960-975,.
[33] E. Malaguti, M. Monaci, P. Toth, A metaheuristic approach for the vertex coloring problem, INFORMS Journal on Computing 20 (2) (2008) 302-316.
[34] J.T. Richardson, M.R. Palmer, G.E. Liepins, M.R. Hilliard, Some guidelines for genetic algorithms with penalty functions, in: Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, 1989, pp. 191-197.
[35] R.W. Hamming, Error-detecting and error-correcting codes, Bell System Technical Journal 2 (29) (1950) 147-160.
[36] R. Real, J.M. Vargas, The probabilistic basis of Jaccard’s index of similarity, Sistematic Biology 45 (3) (1996) 380-385.
[37] D. Chams, A. Hertz, D. de Werra, Some experiments with simulated annealing for coloring graphs, European Journal of Operational Research 32 (1987) 260-266.
[38] M. Gendreau, A. Hertz, G. Laporte, New insertion and postoptimization procedures for the traveling salesman problem, Operations Research 40 (1992) 1086-1094.
[39] E.D. Taillard, Parallel iterative search methods for vehicle routing problems, Networks 23 (1993) 661-673. [40] A. Volgenant, R. Jonker, The symmetric traveling salesman problem and edge exchanges in minimal 1-tree, European Journal of Operational Research 12 (1983) 394-403.
[41] N. Mladenovic, P. Hansen, Variable neighborhood search, Computers & Operations Research 24 (1997) 1097-1100.
[42] C. Avanthay, A. Hertz, N. Zufferey, A variable neighborhood search for graph coloring, European Journal of Operational Research 151(2003) 379-388.
[43] C. Fleurent, J.A. Ferland, Genetic and hybrid algorithms for graph coloring, Annals of Operations Research 63 (3)(1996) 437-461.
[44] J.-P. Watson, J.C. Beck, A.E. Howe, D. Withley, Problem difficulty for tabu search in job-shop scheduling, Artificial Intelligence 143 (2) (2003) 189-217.
[45] D.C. Mattfeld, C. Bierwirth, H. Kopfer, A search space analysis of the job shop scheduling problem, Annals of Operations Research 86 (1999) 441-453.
[46] E.D. Taillard, Parallel-taboo search techniques for the job shop scheduling problem, ORSA Journal on Computing 6(1994) 108-117.
[47] C. Bessière, Arc-consistency and arc-consistency again, Artificial Intelligence 65 (1994) 179-190.
[48] D. Johnson, C. Aragon, L. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation, Part II: Graph coloring and number partitioning, Operations Research 39 (1991) 378-406.
[49] J. Shawe-Taylor, J. Zerovnik, Ants and graph coloring, in: Proceedings of ICANNGA’01, Prague, 2001, pp. 276-279.
[50] P. Toth, D. Vigo, The granular tabu search (and its application to the vehicle routing problem), Tech. Rep. OR-98-9, DEIS-Univertity of Bologna, Italy, 1998.
[51] D. Costa, A. Hertz, Ants can colour graphs, Journal of the Operational Research Society 48 (1997) 295-305.
[52] Y. Rochat, E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics 1 (1995) 147-167.
[53] M. Dorigo, T. Stuetzle, The ant colony optimization metaheuristic: algorithms, applications, and advances, in: F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, 2002, pp. 251-285.
[54] A. Hertz, N. Zufferey, A new ant colony algorithm for graph coloring, in: Proceedings of NICSO 2006, Granada, Spain, 2006, pp. 51-60.
[55] H. Kawamura, M. Yamamoto, T. Mitamura, K. Suzuki, A. Ohuchi, Cooperative search based on pheromone communication for vehicle routing problems, IEEE Transactions on Fundamentals E81-A (1998) 1089-1096.
[56] B. Bullnheimer, R.F. Hartl, C. Strauss, Applying the ant system to the vehicle routing problem, in: S. Voβ, S. Martello, I.H. Osman, C. Roucairol (Eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, 1998, pp. 109-120. [57] B. Bullnheimer, R.F. Hartl, C. Strauss, An improved ant system for the vehicle routing problem, Annals of Operations Research 89 (1999) 319-328.
[58] M. Reimann, K. Doerner, R.F. Hartl, Analysing a unified ant system for the VRP and some of its variants, Lecture Notes in Computer Sciences 2611 (2003) 300-310.
[59] B. Yu, Z.-Z. Yang, B.Z. Yao, An improved ant colony optimization for vehicle routing problem, European Journal of Operational Research 196 (2009) 171-176.
[60] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, Ant system for job-shop scheduling, Belgian Journal of Operations Research Letters Research 34 (1994) 39-53.
[61] K.-L. Huang, C.-J. Liao, Ant colony optimization combined with taboo search for the job-shop scheduling problem, Computers & Operations Research 35 (2008) 1030-1046.
[62] J. Xu, J. Kelly, A network flow-based tabu search heuristic for the vehicle routing problem, Transportation Science 30 (1996) 379-393.
[63] S. Lin, Computer solutions of the traveling salesman problem, Bell System Technical Journal 44 (1965) 2245-2269.
[64] E. Nowicki, C. Smutnicki, A fast taboo search algorithm for the job shop problem, Management Science 42 (6)(1996) 797-813.
[65] H. Hoos, Stochastic local search—methods, models, applications, Ph.D. Thesis, Darmstadt University of Technology, 1998.
[66] I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research 41 (1993) 421-451.
[67] C. Rego, C. Roucairol, A parallel tabu search algorithm using ejection chains for the vehicle routing problem, in: I.H. Osman, J.P. Kelly (Eds.), Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, 1996, pp. 661-675.
[68] P.J.M.V. Laarhoven, E.H.L. Aarts, J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40 (1992) 113-125.
[69] E. Balas, A. Vazacopoulos, Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Tech. Rep. MSRR-609, School of Industrial Administration, Carnergie Mellon University, Pittsburg, 1994.
[70] D. Applegate, W. Cook, A computational study of the job-shop scheduling problem, ORSA Journal on Computing 3 (1991) 149-156.
[71] F. Robusté, C.F. Daganzo, R. Souleyrette, Implementing vehicle routing models, Transportation Research, Part B: Methodological 24 (4) (1990) 263-286.
[72] J. Adams, E. Balas, D. Zawak, The shifting bottleneck procedure for job shop scheduling, Management Science 34 (1988) 391-401. [73] E. Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Operations Research 17(1969) 941-957.
[74] H. Matsuo, C.J. Suh, R.S. Sullivan, A controlled search simulated annealing method for the general jobshop scheduling problem, Tech. Rep. 03-04-88, Graduate School of Business, University of Texas, Austin, 1988.
[75] P. Galinier, A. Hertz, N. Zufferey, An adaptive memory algorithm for the graph coloring problem, Discrete Applied Mathematics 156 (2008) 267-279.
[76] P. Galinier, J.-K. Hao, Hybrid evolutionary algorithms for graph coloring, Journal of Combinatorial Optimization 3(4) (1999) 379-397.
[77] C.-D. Tarantilis, C.T. Kiranoudis, Bone route: An adaptive memory-based method for effective fleet management, Annals of Operations Research 115 (2002) 227-241.
[78] J.-F. Cordeau, G. Laporte, A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society 52(2001) 928-936.
[79] D. Mester, O. Braysy, Active guided evolution strategies for large-scale vehicle routing problems with time windows, Computers & Operations Research 32 (2005) 1593-1614.