Comparing of the Deterministic Simulated Annealing Methods for Quadratic Assignment Problem

Abstract

In this study, Threshold accepting and Record to record travel methods belonging to Simulated Annealing that is meta-heuristic method by applying Quadratic Assignment Problem are statistically analyzed whether they have a significant difference with regard to the values of these two methods target functions and CPU time. Between the two algorithms, no significant differences are found in terms of CPU time and the values of these two methods target functions. Consequently, on the base of Quadratic Assignment Problem, the two algorithms are compared in the study have the same performance in respect to CPU time and the target functions values

Keywords

• Simulated Annealing, Threshold Accepting, Record to Record Travel, Quadratic Assignment Problem

Karesel Atama Problemi İçin Deterministik Tavlama Benzetim Yöntemlerinin Karşılaştırılması

Abstract

Bu çalışma da metasezgisel bir yöntem olan Tavlama Benzetimi’ne (TB) ait olan deterministik tavlama algoritmaları eşik kabulü ve kayıt kayıta gezinti yöntemleri kullanılmıştır. Karesel Atama Problemi (KAP) için uygulanarak, bu iki yöntemin amaç fonksiyon değeri ve çözüm (cpu) zamanları açısından anlamlı bir farklılığa sahip olup olmadıkları istatistiksel olarak incelenmiştir. İki algoritma arasında çözüm zamanı ve amaç fonksiyonu değeri bakımından anlamlı bir fark bulunmamıştır. Sonuç olarak, Karesel Atama Problemi üzerinden yapılan bu çalışma da karşılaştırılan iki algoritmanın çözüm zamanı ve amaç fonksiyonu değerleri bakımından aynı performansa sahip oldukları belirlenmiştir

Keywords

• Karesel Atama Problemi, Tavlama Benzetimi, Eşik kabulü, Kayıt Kayıta Gezinti

References

1. Adams, W.P., Guignard, M., Hahn, P.M., Hightower W.L. (2007) A level-2 reformulation- linearization technique bound for the quadratic assignment problem, European Journal of Operational Research, 180 (3), 983-996.
2. Angel, E., Zissimopoulos, V. (2001) On the landspace ruggedness of the quadratic assignment problems, Theoretical Computer Science, 263 (1-2), 159-172.
3. Bazaraa, M.S., Sherali, M.D. (1980) Bender’s partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Res. Logistics Q, 27, 29-41.
4. Burkard, R. E., Rendl, F., (1984) A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17, 169– 174.
5. Burkard, R.E., Çela E., Pardalos P.M., Pitsoulis L.S. (1998) The Quadratic Assignment Problem. SFB Report 126, Institute of Mathematics,Technical University Graz, Austria.
6. Christofides, N., Benavent, E. (1964) An exact algorithm for the quadratic assignment problem, Operation Research, 37, 760-768.
7. Conolly, D.T. (1990) An improved annealing scheme for the QAP. European Journal of Operational Research, 46, 93–100.
8. Dantzig, G., Fulkerson, R., Johnson, S. (1954) Solution of a Large Scale Traveling Salesman Problem, Paper P-510, The RAND Corporation, Santa Monica, California.

9. Francis, R.L., White, J.A. (1974) Facility layout and location, Englewood Cliffs, N.J.: Printice-Hall.
10. Garey, M.R., Johnson, D.S. (1979) Computers and Intracta-bility: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
11. Gülsün, B., Tuzkaya, G., Duman, C. (2009) Genetik Algoritmalar ile Tesis Yerleşimi Tasarımı ve Bir Uygulama, Doğuş Üniversitesi Dergisi, 10 (1), 73-87.
12. Güner, E., Altıparmak, F. (2003) İki Ölçütlü Tek Makinalı Çizelgeleme Problemi İçin Sezgisel Bir Yaklaşım, J. Fac. Eng. Arch. Gazi Univ., Vol 18, No 3, 27-42.
13. Goldberg, E.F.G., Maculan, N., Goldberg, M.C. (2008) A new neighborhood for the QAP, Electronic Notes in Discrete Mathematics, 30, 3-8.
14. Hahn, P., Grant, T., Hall, N. (1998) A branch-and-bound algorithm for the quadratic assignment problem based Hungarian method, European Journal of Operational Research, 108 (3), 629-640.
15. Hillier, F.S., Connors, M.M. (1966) Quadratic assignment problem algorithms and location of invisible facilities, Management Science, 13 (1), 42-57.
16. Koopmans, T.C., Beckman, M. (1957) Assignment problems and the location of economic activities, Econometrica, 25, 53-76.
17. Lawler, E. (1963) The quadratic assignment problem, Management Science, 9, 856-599.
18. Ligget, R.S. (1981) The quadratic assignment problem, Management Science, 27 (4), 442- 458.
19. Mans, B., Mautor, T., Roucairol, C. (1995) A parallel depth first search branch and bound algorithm for the quadratic assignment problem, European Journal of Operational Research, 81(3), 617-628.
20. Nissen V., Paul H. (1995) A modification of threshold accepting and its application to the quadratic assignment problem. OR Spektrum, 17, 205–210.
21. Pepper, J.W., Golden, B. L., Wasil, E.A. (2002) Solving the Travelling Salesman Problem with Annealing-based Heuristics: A Computational Study, IEEE Transactions on System, Man and Cybernetics-Part A, Vol. 32(1), 72-77.
22. Ramkumar, A.S., Ponnambalam, S.G., Jawahar, N., Suresh, R.K. (2008) Iterated fast local search algorithm for solving quadratic assignment problems, Robotics and Computer- Integrated Manufacturing, 24 (3), 392-401.
23. Rivera, P., Amado R. (2006) A Tabu Search Approach For The Traveling Salesman Problem, Universidad de Los Andes & Universidad Externado de Colombia.
24. Roucairol, C. (1987) A parallel branch and bound algorithm for the quadratic assignment problem, Discrete Applied Mathematics, 18 (2), 211-225.
25. Sahni S., Gonzalez T. (1976) P-completed Approximation Problems, Journal of the Association of Computng Machinery, 23, 555-565.
26. Shapiro, J.A., Alfa, A. S. (1995) An Experimental Analysis of the Simulated Anneling Algoritm for a Single Machine Scheduling Problem, Engineering Optimization, Vol. 24, pp 79-100.
27. Stutzle, T. (2006) Iterated local search for the quadratic assignment problem, European Journal of Operational Research, 174 (3), 1519-1539.
28. Tailard, E. (1991) Robust Tabu Search for the Quadratic Assigment Problem, Parellel Computing, 17,443-455.
29. Thonemann U.W., Bölte A. (1994) An improved simulated annealing algorithm for the quadratic assignment problem. Technical Report, Department of Production and Operations Research, University of Paderborn, Allemagne, Germany.
30. Villagra, M., Barán, B., Goméz, O. (2006) Convexidad Global en el Problema del Cajero Viajante Bi-Objetivo, Asunción, pp41.
31. Makale 16.09.2011 tarihinde alınmış, 19.02.2013 tarihinde düzeltilmiş, 13.03.2013 tarihinde kabul edilmiştir.