Abstract
Recently a lot of attention has been given to simulated annealing and tabu search, two new heuristic approaches for many of the “hard” combinatorial problems, e.g scheduling problems, the traveling salesman problem and the quadratic assignment problem (QAP). In this paper, the applications of simulated annealing and tabu search to the QAP are introduced, investigated and compared.
Several improvements of the two heuristics are proposed, and their strengths and weaknesses are pointed out. It is found, that simulated annealing is the easiest one to implement and to control. Furthermore, when the CPU time is taken into consideration, simulated annealing is clearly preferable to tabu search.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burkard, R. E.: The Quadratic Assignment Problem, Discrete Location Theory, Edited by P. B. Mirchandani and R. L. Francis, Wiley Interscience (1990).
Burkard, R. E. and maschinentastaturen probleme, Zeitschrift B121–B132.
Connolly, D. T., An QAP, EJOR 46 (1990) pp. 93–100.
Elshafei, A. N., Hospital Lay-Out as a Quadratic Assignment Problem, Operational Research Quarterly 28 (1977) pp. 167–179.
Glover, F., Heuristics for Integer Programming Using Surrogate Constraints, Decision Sciences 8:1 (1977) pp. 156166.
Glover, F., Tabu Search-Part I, ORSA Journal on Computing Vol. 1 No. 3 (1989) pp. 190–206.
Glover, F., Tabu Search-Part II, ORSA ‘Journal on Computing Vol 2. No. 1 (1990) pp. 4–32.
Hertz, A. and De Werra, D., Using Tabu Search Techniques for Graph Coloring, Computing 29 (1987) pp. 345–351.
Knox, J., An Application of Tabu Search to the Symmetric Traveling Salesman Problem, Ph.D. thesis Center for Applied Artificial Intelligence, University of Colorado, Boulder (1988).
Koopmans, T. C. and Beckmann, M. J., Assignment Problems and the Location of Economic Activities, Econometrica 25 (1957) pp. 53–76.
Lawler, E. L. et al., The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, Wiley Inter-science (1985).
Lundy, M. and Mees, A., Convergence of an Annealing Algorithm, Mathematical Programmering 34 (1986) pp 111–124.
Nugent, C. E. et al., An experimental Comparison of Techniques for the Assignment of Facilities to Locations, Journal of Operations Research 16 (1968) pp. 150–173.
Skorin-Kapov, J., Tabu Search Applied to the Quadratic Assignment Problem, ORSA Journal on Computing Vol. 2, No. 1 (1990) pp. 33–45.
Steinberg, L., The Backboard Wiring Problem: A Placement Algorithm, SIAM Rev. 3 (1960) pp. 37–50.
Vollman T. and Buffa, E., The Facilities Layout Problem in Perspective, Management Science 12 (1966) pp. 450–468.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Paulli, J. (1993). A Computational Comparison of Simulated Annealing and Tabu Search Applied to the Quadratic Assignment Problem. In: Vidal, R.V.V. (eds) Applied Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, vol 396. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-46787-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-46787-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56229-0
Online ISBN: 978-3-642-46787-5
eBook Packages: Springer Book Archive