Optimization of printed circuit board drilling routes using meta-heuristic algorithms

Abstract

In the drilling process of printed circuit boards, achieving the operation with the least cost depends on the distance travelled by the drilling route. In this study, an integrated method is proposed to carry out the drilling process with the least cost and high speed. In the proposed method, the positions of electronic circuit elements to be placed on the printed circuit board are detected using image processing techniques on a two-dimensional circuit image. Annealing Simulation, Particle Swarm Optimization and Ant Colony Algorithms have been used to solve the travelling salesman problem, and their performances have been examined. When comparing the test results of the obtained models, it is observed that the Ant Colony Algorithm, at the same iteration values, provides solutions with significantly shorter route lengths compared to Simulated Annealing and Particle Swarm Optimization algorithms.

Keywords

• Image processing
• Simulated annealing algorithm
• Particle swarm optimization algorithm
• Ant colony algorithm

Baskı devre kartı delim güzergâhlarının meta-sezgisel algoritmalar kullanılarak optimizasyonu

Öz

Baskılı devre kartlarının delme işleminde, işlemin en az maliyetle gerçekleştirilmesi delim güzergahının kat ettiği mesafeye bağlıdır. Bu çalışmada, delim işleminin en az maliyetle ve yüksek hızda gerçekleştirilebilmesi için bütünleşik bir yöntem önerilmiştir. Önerilen yöntemde, baskılı devre kartı üzerine yerleştirilecek elektronik devre elemanlarının konumları iki boyutlu devre görüntüsüne görüntü işleme teknikleri kullanılarak tespit edilmiştir. Böylelikle kontrol sisteminin takip edeceği en kısa delim güzergahı, gezgin satıcı problemi sorununun çözümünde Tavlama Benzetimi, Parçacık Sürü Optimizasyonu ve Karınca Kolonisi Algoritmaları kullanılmış ve performansları incelenmiştir. Elde edilen modellerin test sonuçları kıyaslandığında aynı iterasyon değerlerinde Karınca Kolonisi Algoritmasının, Tavlama Benzetimi ve Parçacık Sürü Optimizasyonu algoritmalarına göre çok daha kısa güzergâh uzunluğuna sahip olan çözümler elde ettiği gözlemlenmiştir.

Anahtar Kelimeler

• Görüntü işleme
• Tavlama benzetimi algoritması
• Parçacık sürü optimizasyonu algoritması
• Karıca kolonisi algoritması

Kaynakça

1. [1] Karakoç M. “baskılı devre kartlarındaki delik alanlarının görüntü işleme teknikleri kullanılarak tespit edilmesi ve potansiyel delim güzergâhının genetik algoritmalar ile eniyilemesi”. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22(1), 336-345, 2018.
2. [2] Altıntaş V, Çakır A, Küçüksille EU. “Genetik algoritma ile baskı devre yerleşim optimizasyonu”. Teknik Bilimler Dergisi, 8(2), 5-10, 2018.
3. [3] Ismail MM, Othman MA, Sulaiman HA, Misran MH, Ramlee RH, Abidin AFZ, Yakop F. “Firefly algorithm for path optimization in PCB holes drilling process”. In 2012 International Conference on Green and Ubiquitous Technology, Bandung, Indonesia, 07-08 July 2012.
4. [4] Abbas AT, Hamza K, Aly MF. “CNC machining path planning optimization for circular hole patterns via a hybrid ant colony optimization approach”. Mechanical Engineering Research, 4(2), 16-29, 2014.
5. [5] Dewil R, Küçükoğlu İ, Luteyn C, Cattrysse D. “A critical review of multi-hole drilling path optimization”. Archives of Computational Methods in Engineering, 26(2), 449-459, 2019.
6. [6] Sezer A, Altan A. “Optimization of deep learning model parameters in classification of solder paste defects”. 3rd International Congress on Human-Computer Interaction, Optimization and Robotic Applications, Ankara, Turkey, 11-13 June 2021.
7. [7] Zainal Abidin NW, Ab Rashid MFF, Nik Mohamed NMZ. “ A review of multi-holes drilling path optimization using soft computing approaches”. Archives of Computational Methods in Engineering, 26(1), 107-118, 2019.
8. [8] Putera SI, Ibrahim Z. “Printed circuit board defect detection using mathematical morphology and MATLAB image processing tools”. 2nd International Conference on Education Technology and Computer, Shanghai, China, 22-24 June 2010.

9. [9] Zakaria SS, Amir A, Yaakob N, Nazemi S. “Automated detection of printed circuit boards (PCB) defects by using machine learning in electronic manufacturing: current approaches”. 1st International Symposium on Engineering and Technology, Perlis, Malaysia, 23 December 2019.
10. [10] Oprea S, Lita I, Cioc IB, Visan DA. “Determination of misplaced drill holes on a PCB”. 30th International Spring Seminar on Electronics Technology, Cluj-Napoca, Romania, 09-13 May 2007.
11. [11] Wang WC, Chen SL, Chen LB, Chang WJ. “A machine vision based automatic optical inspection system for measuring drilling quality of printed circuit boards”. IEEE Access, 5, 10817-10833, 2016.
12. [12] Anoop KP, Sarath NS, Kumar VS. “A review of PCB defect detection using image Processing”. International Journal of Engineering and Innovative Technology, 4(11), 188-192, 2015.
13. [13] Anitha DB, Rao M. “A survey on defect detection in bare PCB and assembled PCB using image processing techniques”. International Conference on Wireless Communications, Signal Processing and Networking, Chennai, India, 22-24 March 2017.
14. [14] Thigale MM, Gaikwad S, Nangare P, Hule N. “Defect detection and classification of printed circuit board using MATLAB”. International Research Journal of Engineering and Technology (IRJET), 4(2), 1812-1816, 2017.
15. [15] Parlar B, Sayar NÖ, Aydın Ö. “Görüntü işleme ve makine öğrenmesi tabanlı konum belirleme, robot kolu yönlendirme ve parça yerleştirme sistemi”. 8. International Management Information Systems Conference, İstanbul, Turkey, 20-22 October 2021.
16. [16] Yıldırım T, Kalaycı CB, Mutlu Ö. “Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması”. Pamukkale University Journal of Engineering Sciences (PAJES), 22(1), 64-70, 2016.
17. [17] Şahin Y, Karagül K. “Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 106-114, 2019.
18. [18] Kuzu S, Önay O, Şen U, Tunçer M, Yıldırım B, Keskintürk, T. “Gezgin satıcı problemlerinin meta sezgiseller ile çözümü”. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 1-27, 2014.
19. [19] Ayan TY. “Kaynak kısıtlı çoklu proje programlama problemi için tavlama benzetimi algoritması”. Atatürk Üniversitesi İktisadi ve İdari Bilimler Dergisi, 23(2), 101-118, 2009.
20. [20] Kirkpatrick S, Gelatt Jr CD, Vecchi MP. “Optimization by simulated annealing”. Science, 220(4598), 671-680, 1983.
21. [21] Bektur G. “A hybrid heuristic solution based on simulated annealing algorithm for energy efficient single machine scheduling problem with sequence dependent setup times”. Journal of the Faculty of Engineering and Architecture of Gazi University, 36(1), 407-420, 2021.
22. [22] Metin, S. “Benzetimli tavlama algoritması ile eksik veri tamamlama”. Fırat Üniversitesi Mühendislik Bilimleri Dergisi, 33(1), 295-301, 2021.
23. [23] Gözüdeli Y, Akcayol M. “XML Veritabanı için tavlama benzetimi ile sorgu optimizasyonu”. Bilişim Teknolojileri Dergisi, 1(1), 21-30, 2008.
24. [24] Özsağlam MY, Çunkaş M. “Optimizasyon problemlerinin çözümü için parçaçık sürü optimizasyonu algoritması”. Politeknik Dergisi, 11(4), 299-305, 2008.
25. [25] Gökçe CO, Durusu V, Ünal R. “Farklı yük çeşitleri için parçacık sürü optimizasyonu ve ziegler-nichols metodunun dc motor hız kontrolü probleminde karşılaştırılması”. Avrupa Bilim ve Teknoloji Dergisi, (33), 88-92, 2022.
26. [26] Eberhart R, Kennedy J. “A new optimizer using particle swarm theory”. Proceedings of the Sixth International Symposium On Micro Machine and Human Science, IEEE, Nagoya, Japan, 04-06 October 1995.
27. [27] Beşkirli M, Tefek MF. “Parçacık sürü optimizasyon algoritması kullanılarak optimum robot yolu planlama”. Avrupa Bilim ve Teknoloji Dergisi, Özel Sayı, 201-213, 2019.
28. [28] Özden G, Sarıçiçek İ. “Çapraz sevkiyatta kamyon çizelgeleme problemi için çözüm yaklaşımları” Pamukkale University Journal of Engineering Sciences, 25(1), 82-88, 2019.
29. [29] Dikmen H, Dikmen H, Elbir A, Ziya E, Çelik F. “Gezgin satıcı probleminin karınca kolonisi ve genetik algoritmalarla eniyilemesi ve karşılaştırılması.” Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 18(1), 8-13, 2014.
30. [30] Zhang Z, Xu Z, Luan S, Li X, Sun Y. “Opposition-based ant colony optimization algorithm for the traveling salesman problem.” Mathematics, 8(10), 2-16, 2020.
31. [31] Taşyürek M, Mehmet E. “Karınca koloni ve genetik algoritma yöntemleri kullanarak en iyi sayaç okuma güzergâhının tespit edilmesi”. Dicle Üniversitesi Mühendislik Fakültesi Mühendislik Dergisi, 13(3), 405-412, 2022.
32. [32] Serin S. Karınca Kolonisi Yaklaşımıyla Karayolu Üstyapı Rutin Bakım Çalışmalarının Planlanması. Yüksek Lisans Tezi, Süleyman Demirel Üniversitesi, Isparta Türkiye, 2009.
33. [33] Yun HY, Jeong SJ, Kim KS. “Advanced harmony search with ant colony optimization for solving the traveling salesman problem. “Journal of Applied Mathematics, 2013, 1-8, 2013.
34. [34] Akyol S, Alataş B. “Güncel sürü zekâsı optimizasyon algoritmaları”. Nevşehir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 1(1), 36-50, 2012.