Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
D. Applegate, R. Bixby, V. Chvátal and W. Cook (2000) Finding tours in the TSP. Preliminary version of a book chapter available via www.keck.caam.rice.edu/concorde.html.
D. Applegate, W. Cook and A. Rohe (1999) Chained Lin-Kernighan for large traveling salesman problems. Technical Report No. 99887, Forschungsinstitut fürDiskrete Mathematik, University of Bonn, Germany.
T. Bäck (1996) Evolutionary Algorithms in Theory and Practice. Oxford University Press.
E. Balas and A. Vazacopoulos (1998) Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2), 262–275.
R. Battiti and A. Bertossi (1999) Greedy, prohibition, and reactive heuristics for graph-partitioning. IEEE Transactions on Computers, 48(4), 361–385.
R. Battiti and M. Protasi (1997) Reactive search, a history-based heuristic for MAX-SAT. ACM Journal of Experimental Algorithmics, 2.
R. Battiti and G. Tecchiolli (1994) The reactive tabu search. ORSA Journal on Computing, 6(2), 126–140.
E.B. Baum (1986) Iterated descent: A better algorithm for local search in combinatorial optimization problems. Technical report, Caltech, Pasadena, CA. manuscript.
E.B. Baum (1986) Towards practical “neural” computation for combinatorial optimization problems. In: J. Denker (ed.), Neural Networks for Computing. AIP conference proceedings, pp. 53–64.
J. Baxter (1981) Local optima avoidance in depot location. Journal of the Operational Research Society, 32, 815–819.
J.L. Bentley (1992) Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing, 4(4), 387–411.
P. Brucker, J. Hurink and F. Werner (1996) Improving local search heuristics for some scheduling problems—part I. Discrete Applied Mathematics, 65(1–3), 97–122.
P. Brucker, J. Hurink and F. Werner (1997) Improving local search heuristics for some scheduling problems—part II. Discrete Applied Mathematics, 72(1–2), 47–69.
S.A. Canute, M.G.C. Resende and C.C. Ribeiro (2000) Local search with perturbations for the prize-collecting steiner tree problem in graphs. Networks (submitted).
J. Carlier (1982) The one-machine sequencing problem European Journal of Operational Research, 11, 42–47.
V. Cerny (1985) A thermodynamical approach to the traveling salesman problem. Journal of Optimization Theory and Applications, 45(1), 41–51.
N. Christofides (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.
B. Codenotti, G. Manzini, L. Margara and G. Resta (1996) Perturbation: An efficient technique for the solution of very large instances of the Euclidean TSP. INFORMS Journal on Computing, 8, 125–133.
R.K. Congram, C.N. Potts and S.L. Van de Velde (2000) An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing (to appear).
H.A.J. Crauwels, C.N. Potts and L.N. Van Wassenhove (1998) Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 10(3), 341–350.
M. Dorigo and G. Di Caro (1999) The ant colony optimization meta-heuristic. In: D. Corne, M. Dorigo and F. Glover (eds.), New Ideas in Optimization. McGraw Hill, pp. 11–32.
T.A. Feo and M.G.C. Resende (1995) Greedy randomized adaptive search procedures. Journal of Global Optimization, 6, 109–133.
C. Fonlupt, D. Robilliard, P. Preux and E.-G. Talbi (1999) Fitness landscape and performance of meta-heuristics. In: S. Voss, S. Martello, I.H. Osman and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Boston, MA, pp. 257–268.
C. Glass and C. Potts (1996) A comparison of local search methods for flow shop scheduling. Annals of Operations Research, 63, 489–509.
F. Glover (1986) Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549.
F. Glover (1989) Tabu search—part I. ORSA Journal on Computing, 1(3), 190–206.
F. Glover (1990) Tabu search—part II. ORSA Journal on Computing, 2( 1), 4–32.
F. Glover (1995) Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA Journal on Computing, 7(4), 426–442.
F. Glover (1996) Finding a best traveling salesman 4-opt move in the same time as a best 2-opt move. Journal of Heuristics, 2, 169–179.
F. Glover (1999) Scatter search and path relinking. In: D. Corne, M. Dorigo and F. Glover (eds.), New Ideas in Optimization. McGraw Hill, pp. 297–316.
F. Glover and M. Laguna (1997) Tabu Search. Kluwer Academic Publishers, Boston, MA.
M.X. Goemans and D.P. Williamson (1996) The primal dual method for approximation algorithms and its application to network design problems. In: D. Hochbaum (ed.), Approximation Algorithms for NP-hard Problems. PWS Publishing, pp. 144–191.
P. Hansen and N. Mladenović (1999) An introduction to variable neighborhood search. In: S. Voss, S. Martello, I.H. Osman and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Boston, MA, pp. 433–58.
R. Haupt (1989) A survey of priority rule-based scheduling. OR Spektrum, 11, 3–6.
I. Hong, A.B. Kahng and B.R. Moon (1997) Improved large-step Markov chain variants for the symmetric TSP. Journal of Heuristics, 3(1), 63–81.
T.C. Hu, A.B. Kahng and C.-W.A. Tsao (1995) Old bachelor acceptance: A new class of non-monotone threshold accepting methods. ORSA Journal on Computing, 7(4), 417–425.
D.S. Johnson (1990) Local optimization and the travelling salesman problem. In: Proceedings of the 17th Colloquium on Automata, Languages, and Programming, volume 443 of LNCS, Springer Verlag, Berlin, pp. 446–461.
D.S. Johnson and L.A. McGeoch (1997) The travelling salesman problem: A case study in local optimization. In: E.H.L. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester, England, pp. 215–310.
K. Katayama and H. Narihisa (1999) Iterated local search approach using genetic transformation to the traveling salesman problem. In: Proceedings of GECCO’99, Vol. 1. Morgan Kaufmann, pp. 321–328.
B.W. Kernighan and S. Lin (1970) An efficient heuristic procedure forpartitioning graphs. Bell Systems Technology Journal, 49, 213–219.
S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi (1983) Optimization by simulated annealing. Science, 220, 671–680.
S. Kreipl (2000) A large step random walk for minimizing total weighted tardiness in ajob shop. Journal of Scheduling, 3(3), 125–138.
S. Lin and B.W. Kernighan (1973) An effective heuristic algorithm for the travelling salesman problem. Operations Research, 21, 498–516.
H.R. Lourenço (1995) Job-shop scheduling: Computational study of local search and large-step optimization methods. European Journal of Operational Research, 83, 347–364.
H.R. Lourenço (1998) A polynomial algorithm for a special case of the one-machine scheduling problem with time-lags. Technical Report Economic Working Papers Series, No. 339, Universitat Pompeu Fabra. Journal of Scheduling (submitted).
H.R. Lourenço and M. Zwijnenburg (1996) Combining the large-step optimization with tabu-search: Application to the job-shop scheduling problem. In: I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, pp. 219–236.
O. Martin and S.W. Otto (1995) Partitoning of unstructured meshes for load balancing. Concurrency: Practice and Experience, 7, 303–314.
O. Martin and S.W. Otto (1996) Combining simulated annealing with local search heuristics. Annals of Operations Research, 63, 57–75.
O. Martin, S.W. Otto and E.W. Felten (1991) Large-step Markov chains for the traveling salesman problem. Complex Systems, 5(3), 299–326.
O. Martin, S.W. Otto and E.W. Felten (1992) Large-step Markov chains for the TSP incorporating local search heuristics. Operations Research Letters, 11, 219–224.
P. Merz and B. Freisleben (2000) Fitness landscapes, memetic algorithms and greedy operators for graph bi-partitioning. Evolutionary Computation, 8(1), 61–91.
N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and M. Teller (1953) Equation of state calculations for fast computing machines. Journal of Chemical Physics, 21, 1087–1092.
M. Mézard, G. Parisi and M.A. Virasoro (1987) Spin-Glass Theory and Beyond, volume 9 of Lecture Notes in Physics. World Scientific, Singapore.
Z. Michalewicz and D.B. Fogel (2000) How to Solve it: Modern Heuristics. Springer-Verlag, Berlin.
N. Mladenović and P. Hansen (1997) Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.
H. Mühlenbein (1991) Evolution in time and space—the parallel genetic algorithm. In: Foundations of Genetic Algorithms. Morgan Kaufmann, San Mateo. pp. 316–337.
M. Nawaz, E. Enscore Jr. and I. Ham (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, 11(1), 91–95.
G.R. Schreiber and O.C. Martin (1999) Cut size statistics of graph bisection heuristics. SIAM Journal on Optimization, 10(1), 231–251.
M. Singer and M. Pinedo (1997) A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. IIE Scheduling and Logistics, 30, 109–118.
T. Stützle (1998). Applying iterated local search to the permutation flow shop problem. Technical Report AIDA-98-04, FG Intellektik, TU Darmstadt, August.
T. Stützle (1998) Local Search Algorithms for Combinatorial Problems—Analysis, Improvements, and New Applications. PhD thesis, Darmstadt University of Technology, Department of Computer Science.
T. Stützle, A. Grim, S. Linke and M. Rüttger (2000) A comparison of nature inspired heuristics on the traveling salesman problem. In: Deb et al. (eds.), Proceedings of PPSN-VI, volume 1917 of LNCS. Springer Verlag, Berlin, pp. 661–670.
T. Stützle and H.H. Hoos (2000) Analyzing the run-time behaviour of iterated local search for the TSP. Technical Report IRIDIA/2000-01, IRIDIA, Université Libre deBruxelles. Available at http://www.intellektik.informatik.tu-darmstadt.de/~tom/pub.html.
E.D. Taillard (1995) Comparison of iterative searches for the quadratic assignment problem. Location Science, 3, 87–105.
R.J.M. Vaessens, E.H.L. Aarts and J.K. Lenstra (1996) Job shop scheduling by local search. INFORMS Journal on Computing, 8, 302–317.
C. Voudouris and E. Tsang (1995) Guided Local Search. Technical Report Technical Report CSM-247, Department of Computer Science, University of Essex.
Y. Yang, S. Kreipl and M. Pinedo (2000) Heuristics for minimizing total weighted tardiness in flexible flow shops. Journal of Scheduling, 3(2), 89–108.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Kluwer Academic Publishers
About this chapter
Cite this chapter
Lourenço, H.R., Martin, O.C., Stützle, T. (2003). Iterated Local Search. In: Glover, F., Kochenberger, G.A. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 57. Springer, Boston, MA. https://doi.org/10.1007/0-306-48056-5_11
Download citation
DOI: https://doi.org/10.1007/0-306-48056-5_11
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4020-7263-5
Online ISBN: 978-0-306-48056-0
eBook Packages: Springer Book Archive