Fondements et applications des méthodes de recherche avec tabous

Soriano, P.; Gendreau, M.

Soriano, P. ; Gendreau, M.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 2, pp. 133-159.

MR Zbl

@article{RO_1997__31_2_133_0,
     author = {Soriano, P. and Gendreau, M.},
     title = {Fondements et applications des m\'ethodes de recherche avec tabous},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {133--159},
     publisher = {EDP-Sciences},
     volume = {31},
     number = {2},
     year = {1997},
     mrnumber = {1452340},
     zbl = {0876.90080},
     language = {fr},
     url = {http://archive.numdam.org/item/RO_1997__31_2_133_0/}
}

TY  - JOUR
AU  - Soriano, P.
AU  - Gendreau, M.
TI  - Fondements et applications des méthodes de recherche avec tabous
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1997
SP  - 133
EP  - 159
VL  - 31
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1997__31_2_133_0/
LA  - fr
ID  - RO_1997__31_2_133_0
ER  -

%0 Journal Article
%A Soriano, P.
%A Gendreau, M.
%T Fondements et applications des méthodes de recherche avec tabous
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1997
%P 133-159
%V 31
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1997__31_2_133_0/
%G fr
%F RO_1997__31_2_133_0

Soriano, P.; Gendreau, M. Fondements et applications des méthodes de recherche avec tabous. RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 2, pp. 133-159. http://archive.numdam.org/item/RO_1997__31_2_133_0/

Bibliographie
Cité par

1. C. A. Anderson, K. Fraugnaugh, M. Parker et J. Ryan, Path Assignment for Call Routing: An Application of Tabu Search, Annals of Operations Research, 1993, 41, p. 301-312. | Zbl

2. J. W. Barnes et M. Laguna, Solving the Multiple-Machine Weighted Flow Time Problem Using Tabu Search, IIE Transactions, 1992 (à paraître).

3. S. Benati et G. Laporte, Tabu Search Algorithms for the (r/:Tp)-Medianoid and the (r/p)-Centroid Problems, Location Science, 1994, 2, p. 193-204. | Zbl

4. D. Beyer et R. Ogier, Tabu Learning: A Neural Network Search Method for Solving Nonconvex Optimization Problems, Proceedings of the International Joint Conference on Neural/Network, IEEE and INNS, Singapour, 1991.

5. J. A. Bland et G. P. Dawson, Tabu Search and Design Optimization, Computer-Aided Design, 23, 1991, p. 195-202. | Zbl

6. J. Bovet, C. Constantin et D. De Werra, A Convoy Scheduling Problem, à paraître dans Discrete Applied Mathematics, 1991. | Zbl

7. P. Brandimarte, Routing and Scheduling in a Flexible Job Shop by Tabu Search, Annals of Operations Research, 1993, 41, p. 157-184. | Zbl

8. J. Chakrapani et J. Skorin-Kapov, Massively Parallel Tabu Search for the Quadratic Assignment Problem, Annals of Operations Research, 1993, 41, p. 327-342. | Zbl

9. M. Chams, A. Hertz et D. De Werra, Some Experiments with Simulated Annealing for Coloring Graphs, European Journal of Operations Research, 1987, 32, p. 260-266. | MR | Zbl

10. D. Costa, A Tabu Search Algorithm for Computing an Operational Time Table, European Journal of Operations Research, 1994, 76, p. 98-110. | Zbl

11. D. Costa, On the Use of Some Known Methods for T-Coloring of Graphs, Annals of Operations Research, 1993, 41, p. 343-358. | Zbl

12. T. G. Crainic, M. Gendreau, P. Soriano et M. Toulouse, A Tabu Search Procedure for Multicommodity Location/Allocation with Balancing Requirements, Annals of Operations Research, 1993, 41, p. 359-384. | Zbl

13. T. G. Crainic, M. Toulouse et M. Gendreau, Towards a Taxonomy of Parallel Tabu Search Algorithms, INFORMS J. on Computing (à paraître).

14. T. G. Crainic, M. Toulouse et M. Gendreau, A Study of Synchronous Parallelization Strategies for Tabu Search, publication CRT-934, Centre de recherche sur les transports, Université de Montréal, 1993.

15. T. G. Crainic, M. Toulouse et M. Gendreau, An Appraisal of Asynchronous Parallelization Approaches for Tabu Search Algorithms, Annals of Operations Research, 1996, 63, p. 277-299. | Zbl

16. F. Dammeyer et S. Voß, Dynamic Tabu List Management Using the Reverse Elimination Method, Annals of Operations Research, 1993, 41, p. 31-46. | Zbl

17. R. L. Daniels et J. B. Mazzola, Tabu Search Heuristic for the Flexible-Resource Flow Shop Scheduling Problem, Annals of Operations Research, 1993, 41, p. 207-230. | Zbl

18. M. Dell'Amico et T. Trubian, Applying Tabu Search to the Job-Shop Scheduling Problem, Annals of Operations Research, 1993, 41, p. 231-252. | Zbl

19. W. Domschke, P. Frost et S. Voß, Tabu Search Techniques for the Quadratic Semi-Assignment Problem, New Directions for Operations Research in Manufacturing, G. FANDEL, T. GULLEDGE et A. JONES (Eds.), Springer, 1991, p. 389-405.

20. N. Dubois et D. De Werra, EPCOT: An Efficient Procedure for Coloring Optimally with Tabu Search, Computers and Mathematics with Applications, 1993, 25, p. 35-45. | MR | Zbl

21. U. Faigle et W. Kern, Some Convergence Results for Probabilistic Tabu Search, ORSA Journal on Computing, 1992, 4, p. 32-37. | Zbl

22. C.N. Fiechter, A Parallel Tabu Search Algorithm for Large Scale Traveling Salesman Problems, Discrete Applied Mathematics, 1994, 51, p. 243-267. | MR | Zbl

23. L. J. Fogel, A. J. Owens et M. J. Walsh, Artificial Intelligence through Simulated Evolution, Wiley, New York, 1966. | Zbl

24. P. M. França, M. Gendreau, G. Laporte et F. M. Muller, The m-Traveling Salesman Problem with Minmax Objective, Transportation Science, 1995, 29, p. 267-275. | Zbl

25. C. Friden, A. Hertz et D. De Werra, STABULUS: A Technique for Finding Stable Sets in Large Graphs with Tabu Search, Computing, 1989, 42, p. 35-44. | Zbl

26. C. Friden, A. Hertz et D. De Werra, TABARIS: An Exact Algorithm Based on Tabu Search for Finding a Maximum Independent Set in a Graph, Computers and Operations Research, 1990, 17, p. 437-445. | MR | Zbl

27. B. L. Garcia, Développement de techniques de recherche tabou pour le problème de tournées de véhicules avec fenêtres de temps, publication CRT-931, Centre de recherche sur les transports, Université de Montréal, 1993.

28. B. L. Garcia, J.-Y. Potvin et J.-M. Rousseau, A Parallel Implementation of the Tabu Search for the Vehicle Routing Problem with Time Windows, Computers & Operations Research, 1994, 21, p. 1025-1033. | Zbl

29. M. Gendreau, A. Hertz et G. Laporte, A Tabu Search Algorithm for the Vehicle Routing Problem, Management Science, 1994, 40, p. 1276-1290. | Zbl

30. M. Gendreau, P. Soriano et L. Salvail, Solving the Maximum Clique Problem Using a Tabu Search Approach, Annals of Operations Research, 1993, 41, p. 385-404. | Zbl

31. F. Glover, Heuristics for Integer Programming Using Surrogate Constraints, Decision Science, 1977, 8, p. 156-166.

32. F. Glover, Future Paths for Integer Programming and Links to Artificial Intelligence, Computers and Operations Research, 1986, 5, p. 533-549. | MR | Zbl

34. F. Glover, Tabu Search - Part I, ORSA Journal on Computing, 1989, 1, p. 190-206. | Zbl

34. F. Glover, Candidate List Strategies and Tabu Search, CAAI Research Report, University of Colorado, Boulder, 1989.

35. F. Glover, Tabu Search - Part II, ORSA Journal on Computing, 1990, 2, p. 4-32. | Zbl

36. F. Glover, Multilevel Tabu Search and Embedded Search Neighborhoods for the Traveling Salesman Problem, ORSA Journal on Computing, 1991 (à paraître).

37. F. Glover, Tabu Search for Nonlinear and Parametric Optimization (with Links to Genetic Algorithms), Discrete Applied Mathematics, 1991 (à paraître). | Zbl

38. F. Glover et M. Laguna, Bandwidth Packing: A Tabu Search Approach, Management Science, 1993, 39, p. 17-29. | Zbl

39. F. Glover et M. Laguna, Tabu Search, dans Modem Heuristic Techniques for Combinatorial Problems, C. R. REEVES (Ed.), Blackwell, Oxford, 1993, p. 70-150.

40. F. Glover, E. Taillard et D. De Werra, A User's Guide to Tabu Search, Annals of Operations Research, 1992, 41, p. 3-28. | Zbl

41. P. Hansen, The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming, présenté au Congress on Numerical Methods in Combinatorial Programming, Capri, Italie, 1986.

42. P. Hansen et B. Jaumard, Algorithms for the Maximum Satisflability Problem, Computing, 1990, 44, p. 279-303. | MR | Zbl

43. P. Hansen, B. Jaumard et E. Da Silva, Average Linkage Divisive Hierarchical Clustering, Journal of Classification, 1992 (à paraître).

44. P. Hansen, B. Jaumard et M. Poggi De Aragao, Mixed Integer Column Generation Algorithms and the Probabilistic Maximum Satisfiability Problem, Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, Carnegie-Mellon, 1992. | Zbl

45. P. Hansen, E. De Luna Pedrosa Filho et C. Carneiro Ribeiro, Location and Sizing of Offshore Platforms for Oil Exploration, European Journal of Operations Research, 1992, 58, p. 202-214. | Zbl

46. A. Hertz, Tabu Search for Large Scale Timetabling Problems, European Journal of Operations Research, 1991, 54, p. 39-47. | Zbl

47. A. Hertz, Finding a Feasible Course Schedule Using Tabu Search, Discrete Applied Mathematics, 1992, 55, p. 255-270. | Zbl

48. A. Hertz, E. Taillard et D. De Werra, Tabu Search, dans Local Search in Combinatorial Optimization, J. K. LENSTRA (Ed.), à venir, aussi rapport ORWP 92/18, Département de mathématiques, École Polytechnique Fédérale de Lausanne, Suisse, 1992. | Zbl

49. A. Hertz et D. De Werra, Using Tabu Search Techniques for Graph Coloring, Computing, 1987, 29, p. 345-351. | MR | Zbl

50. A. Hertz et D. De Werra, Informatique et horaires scolaires, Output, 1989, 12, p. 53-56.

51. A. Hertz et D. De Werra, The Tabu Search Metaheuristic: How WeUsed It, Annals of Mathematics and Artificial Intelligence, 1990, 1, p. 111-121. | Zbl

52. J. H. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, MI, 1975. | MR | Zbl

53. B. Jaumard, P. Hansen et M. Poggi De Aragao, Column Generation Methods for Probabilistic Logic, ORSA Journal on Computing, 1991, 3, p. 135-148. | Zbl

54. B. Jaumard, M. Stan et J. Desrosiers, Tabu Search and a Quadratic Relaxation for the Satisfiability Problem, Cahiers du GERAD G-93-25, GERAD, École des Hautes Études Commerciales, Montréal, 1993. | Zbl

55. J. P. Kelly, B. L. Golden et A. A. Assad, Large-Scale Controlled Rounding Using Tabu Search with Strategie Oscillation, Annals of Operations Research, 1992, 41, p. 69-84. | Zbl

56. S. Kirkpatrick, C. D. Jr. Gelatt et M. P. Vecchi, Optimization by Simulated Annealing, Science, 220 (4598), 1983, p. 671-680. | MR

57. M. Laguna, J. W. Barnes et F. Glover, Tabu Search Methods for a Single Machine Scheduling Problem, Journal of Intelligent Manufacturing, 1991, 2, p. 63-74.

58. M. Laguna et F. Glover, Integrating Target Analysis and Tabu Search for Improved Scheduling Systems, Expert Systems with Applications: An International Journal, 1992 (à paraître).

59. M. Laguna et J. L. Gonzalez-Velarde, A Search Heuristic for Just-in-Time Scheduling in Parallel Machines, Journal of Intelligent Manufacturing, 1991, 2, p. 253-260.

60. S. Lin, Computer Solutions of the Traveling Salesrnan Problem, Bell System Technical Journal, 1964, 44, p. 2245-2269. | MR | Zbl

61. M. Malek, M. Guruswamy, M. Pandya et H. Owens, Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem, Annals of Operations Research, 1989, 21, p. 59-84. | MR | Zbl

62. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller et E. Teller, Equation of State Calculations by Fast Computing Machines, Journal of Chemical Physics, 1953, 21 (6), p. 1087-1091.

63. E. L. Mooney et R. L. Rardin, Tabu Search for a Class of Scheduling Problems, Annals of Operations Research, 1992, 41, p. 253-278. | Zbl

64. S. Oliveira et G. Stroud, A Parallel Version of Tabu Search and the Path Assignment Problem, Heuristics for Combinatorial Optimization, 1989, 4, p. 1-24.

65. I. Or, Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking, Ph.D. Dissertation, Northwestern University, Evanston, IL, 1976.

66. I. H. Osman, Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem, Annals of Operations Research, 1993, 41, p. 421-451. | Zbl

67. M. Pirlot, General Local Search Heuristics in Combinatorial Optimization: A Tutorial, Belgian Journal of Operations Research, Statistics and Computer Science, 1992, 32, p. 8-67. | Zbl

68. J.-Y. Potvin, T. Kervahut, B. L. Garcia et J.-M. Rousseau, A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows, publication CRT-855, Centre de recherche sur les transports, Université de Montréal, 1993.

69. V. M. Pureza et P. M. França, Vehicle Routing Problems via Tabu Search Metaheuristic, publication CRT-747, Centre de recherche sur les transports, Université de Montréal, 1991.

70. Y. Rochat et F. Semet, Tabu Search Approach for Delivering Pet Food and Flour in Switzerland, Journal of the Operational Research Society, 1994, 45, p. 1233-1246. | Zbl

71. F. Semet et E. Taillard, Solving Real-Life Vehicle Routing Problems Efficiently Using Tabu Search, Annals of Operations Research, 1993, 41, p. 469-488. | Zbl

72. J. Skorin-Kapov, Tabu Search Applied to the Quadratic Assignment Problem, ORSA Journal on Computing, 1990, 2, p. 33-45. | Zbl

73. J. Skorin-Kapov, Extensions of a Tabu Search Adaptation to the Quadratic Assignment Problem, Computers and Operations Research, 1994, 21, p. 855-865. | MR | Zbl

74. P. Soriano et M. Gendreau, Diversification Strategies in Tabu Search Algorithms for the Maximum Clique Problem, Annals of Operations Research, 1996, 63, p. 189-207. | MR | Zbl

75. P. Soriano et M. Gendreau, Tabu Search Algorithms for the Maximum Clique Problem, dans Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, D. S. JOHNSON et M. A. TRICK (Ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, American Mathematical Society, 1996. | MR | Zbl

76. B. Srivastava et W.-H. Chen, Part Type Selection Problem in Flexible Manufacturing Systems: Tabu Search Algorithms, Annals of Operations Research, 1993, 41, p. 279-297. | Zbl

77. M. Sun et P. G. Mckeown, Tabu Search Applied to the General Fixed Charge Problem, Annals of Operations Research, 1993, 41, p. 405-420. | Zbl

78. E. Taillard, Parallel Tabu Search for the Jobshpp Scheduling Problem, rapport ORWP 89/11, Département de mathématiques, École Polytechnique Fédérale de Lausanne, Suisse, 1989.

79. E. Taillard, Some Efficient Heuristic Methods for the Flowshop Sequencing Problem, European Journal of Operations Research, 1990, 47, p. 65-74. | MR | Zbl

80. E. Taillard, Robust Taboo Search for the Quadratic Assignment Problem, Parallel Computing, 1991, 17, p. 443-455. | MR

81. E. Taillard, Parallel Iterative Search Methods for Vehicle Routing Problems, Networks, 1993, 23, p. 661-673. | Zbl

82. D. De Werra et A. Hertz, Tabu Search Techniques: A Tutorial and an Application to Neural Networks, OR Spektrum, 1989, 11, p. 131-141. | MR | Zbl

83. M. Widmer et A. Hertz, A New Method for the Flow Sequencing Problem, European Journal of Operations Research, 1989, 41, pp. 186-193. | Zbl

84. M. Widmer, Job Shop Scheduling with Tooling Constraints: A Tabu Search Approach, Journal of the Operational Research Society, 1991, 24 (1), p. 75-82.

85. J. A. G. Willard, Vehicle Routing Using r-Optimal Tabu Search, M. Sc. Dissertation, The Management School, Imperial College, Londres, 1989.

86. D. L. Woodruff et M. L. Spearman, Sequencing and Batching for Two Classes of Jobs with Deadlines and Setup Times, Production and Operations Management, 1992, 1 (1), p. 87-102.

87. D. L. Woodruff et E. Zemel, Hashing Vectors for Tabu Search, Annals of Operations Research, 1992, 41, p. 123-137. | Zbl