You are here

Home » Content

KARESEL ATAMA PROBLEMİ İÇİN DETERMİNİSTİK TAVLAMA BENZETİM YÖNTEMLERİNİN KARŞILAŞTIRILMASI

Comparing of the Deterministic Simulated Annealing Methods for Quadratic Assignment Problem

Journal Name:

  • Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi

Publication Year:

  • 2013

Key Words:

Keywords (Original Language):

Author NameUniversity of AuthorFaculty of Author
Abstract (2. Language): 
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.
Bookmark/Search this post with
Abstract (Original Language): 
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.
FULL TEXT (PDF): 
PDF icon mak18_02-04syf037-046.pdf
  • 2
37-46
  • Turkish

REFERENCES

References: 

1. Adams, W.P., Guignard, M., Hahn, P.M., Hightower W.L. (2007) A level-2 reformulationlinearization
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.
Ünsal, M.G.: Karesel Atama Problemi İçin Deterministik Tavlama Benzetim Yöntemlerinin Karşılaştırılması
46
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.

Thank you for copying data from http://www.arastirmax.com