Skip to main content
SpringerLink
Log in

Applying an Extended Guided Local Search to the Quadratic Assignment Problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we show how an extended Guided Local Search (GLS) can be applied to the Quadratic Assignment Problem (QAP). GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. We present empirical results of applying several extended versions of GLS to the QAP, and show that these extensions can improve the range of parameter settings within which Guided Local Search performs well. Finally, we compare the results of running our extended GLS with some state of the art algorithms for the QAP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Amin, Simulated jumping, Annals of Operations Research (1998) to appear.

  2. R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA Journal on Computing 6(2) (1994) 126–140.

    Google Scholar 

  3. C.M. Bishop and G. Hinton, Neural Networks for Pattern Recognition (Clarendon Press, New York, 1995).

    Google Scholar 

  4. R.E. Burkard, S.E. Karisch and F. Rendl, QAPLIB – a quadratic assignment problem library, Journal of Global Optimization 10 (1997) 391–403.

    Google Scholar 

  5. A. Davenport, Extensions and evaluation of GENET in constraint satisfaction, Ph.D. Thesis, Department of Computer Science, University of Essex, Colchester, UK (July 1997).

    Google Scholar 

  6. A. Davenport, E.P.K. Tsang, K. Zhu and C.J. Wang, GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement, in: Proceedings of AAAI (1994) pp. 325–330.

  7. C. Fleurent and J.A. Ferland, Genetic hybrids for the quadratic assignment problem, in: Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 16, eds. P. Pardalos and H. Wolkowicz (Amer. Math. Soc., Providence, RI, 1994) pp. 173–187.

  8. F. Glover, Tabu search. Part I, ORSA Journal on Computing 1 (1989) 109–206.

    Google Scholar 

  9. F. Glover, Tabu search. Part II, ORSA Journal on Computing 2 (1990) 4–32.

    Google Scholar 

  10. P. Kilby, P. Prosser and P. Shaw, Guided local search for the vehicle routing problem, in: Proceedings of the 2nd International Conference on Metaheuristics (July 1997).

  11. T.L. Lau, Guided genetic algorithm, Ph.D. Thesis, Department of Computer Science, University of Essex (1999).

  12. T.L. Lau and E.P.K. Tsang, Applying a mutation-based genetic algorithm to processor configuration problems, in: Proceedings of 8th IEEE Conference on Tools with Artificial Intelligence (ICTAI '96), Toulouse, France (November 1996).

  13. T.L. Lau and E.P.K. Tsang, Solving the processor configuration problem with a mutation-based genetic algorithm, International Journal on Artificial Intelligence Tools 6(4) (1997) 567–585.

    Google Scholar 

  14. T.L. Lau and E.P.K. Tsang, Solving the radio link frequency assignment problem with the guided genetic algorithm, in: Proceedings of NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark (October 1998), paper 14b.

  15. T.L. Lau and E.P.K. Tsang, The guided genetic algorithm and its application to the general assignment problems, in: IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI '98), Taiwan (November 1998).

  16. T.L. Lau and E.P.K. Tsang, Solving large processor configuration problems with the guided genetic algorithm, in: IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI '98), Taiwan (November 1998).

  17. T.L. Lau and E.P.K. Tsang, Guided genetic algorithm and its application to radio link frequency assignment problems, to appear in Journal of Constraints.

  18. P. Mills and E.P.K. Tsang, Guided local search for solving SAT and weighted MAX-SAT problems, Journal of Automatic Reasoning 24, Special Issue on Satisfiability Problems (2000) 205–223.

    Google Scholar 

  19. P.M. Pardalos, F. Rendl and H. Wolkowicz, The quadratic assignment Problem: a survey of recent developments, in: Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 16, eds. P. Pardalos and H. Wolkowicz (Amer. Math. Soc., Providence, RI, 1994) pp. 1–42.

    Google Scholar 

  20. B. Selman, H. Kautz and B. Cohen, Noise strategies for improving local search, in: Proceedings of AAAI-94 (1994).

  21. B. Stroustrup, The C++ Programming Language, 3rd edn. (Addison-Wesley, Reading, MA, 1997).

    Google Scholar 

  22. T. Stutzle, MAX-MIN Ant system for quadratic assignment problems, Research Report AIDA–97–04, Department of Computer Science, Darmstadt University of Technology, Germany (1997).

    Google Scholar 

  23. E.D. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Computing 17 (1991) 443–455.

    Google Scholar 

  24. E.D. Taillard, Comparison of Iterative Searches for the Quadratic Assignment Problem (Location Science, 1994).

  25. E.D. Taillard and L.M. Gambardella, Adaptive memories for the quadratic assignment problem, Research Report, IDSIA, Lugano, Switzerland (1997).

    Google Scholar 

  26. U.W. Thonemann and A. Bolte, An improved simulated annealing algorithm for the quadratic assignment problem, Working paper, School of Business, Department of Production and Operations Research, University of Paderborn, Germany (1994).

    Google Scholar 

  27. E.P.K. Tsang and C. Voudouris, Fast local search and guided local search and their application to British Telecom's workforce scheduling problem, Operations Research Letters 20(3) (1997) 119–127.

    Google Scholar 

  28. E.P.K. Tsang and C.J.Wang, A generic neural network approach for constraint satisfaction problems, in: Neural Network Applications, ed. J.G. Taylor (Springer, Berlin, 1992) pp. 12–22.

    Google Scholar 

  29. C. Voudouris, Guided local search for combinatorial optimisation problems, Ph.D. Thesis, Department of Computer Science, University of Essex (1997).

  30. C. Voudouris, Guided local search – an illustrative example in function optimisation, BT Technology Journal 16(3) (1998) 46–50.

    Google Scholar 

  31. C. Voudouris and E.P.K. Tsang, Solving the radio link frequency assignment problem using guided local search, in: Proceedings of NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark, October (1998) paper 14a.

  32. C. Voudouris and E.P.K. Tsang, Guided local search and its application to the travelling salesman problem, European Journal of Operational Research 113(2) (1999) 469–499.

    Google Scholar 

  33. M.R. Wilhelm and T.L. Ward, Solving quadratic assignment problems by simulated annealing, IIE Transactions 19(1) (1987) 107–119.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Essex, Wivenhoe Park, Colchester, CO4 3SQ, UK

    Patrick Mills, Edward Tsang & John Ford

Authors
  1. Patrick Mills
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edward Tsang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. John Ford
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mills, P., Tsang, E. & Ford, J. Applying an Extended Guided Local Search to the Quadratic Assignment Problem. Annals of Operations Research 118, 121–135 (2003). https://doi.org/10.1023/A:1021857607524

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1021857607524

Search

Navigation