Aykut ORAL, Necdet GUNER, Yusuf SAHIN, Kenan KARAGUL

Gezgin Satıcı Probleminin Çözümünde İnsan Performansının Analizi

Problem Durumu: Gezgin Satıcı Sorunu (GSP), bir dizi şehri ziyaret edecek satıcı tarafından kullanılacak en kısa rotayı belirleyen bir en uygun şekle sokma problemidir. Çeşitli şekillerde genişletilip değiştirilebilen GSP, pratik ve gerçekçi bir problem türü olmakla beraber birçok optimizasyon probleminin görsel ve mekânsal çözümünün temelini oluşturur. Optimizasyon alanında yoğun olarak çalışılan GSP insan yeteneklerinin problem çözme bağlamında analizi için de kullanılmaktadır. Diğer taraftan bu problem, karar verme, motor kontrolü ve algılama çalışmaları için de içgörü (insight) problemi olarak modellenebilmektedir. İçgörü problemleri, problem çözücünün çözüm prosedürüne aşina olmadığı özel ve rutin olmayan problemlerdir. Literatürde sözlü, matematiksel ve mekânsal içgörü problemlerinin kullanıldığı çalışmalar mevcuttur. Çalışma kapsamında deneklerin çözmesi istenen GSP insan deneklerin problem çözme performanslarını analiz etmek için kullanılan bir problemdir. Bu açıdan GSP'nin mekânsal bir içgörü problemi olarak kullanılabileceği aşikârdır. GSP'nin hesaplama karmaşıklığına rağmen, önceki çalışmalar insan çözücülerin kabul edilebilir zamanlarda bu sorun için en uygun çözümlere yakın olduklarını göstermektedir (Dry ve Fontaine, 2014, s.84).Araştırmanın Amacı: Çalışma kapsamında üç soruya cevap aranmaktadır. Birinci aşamada, eğitim seviyesi dikkate alınmadan cinsiyetin problem çözme performansına bir etkisinin olup olmadığı araştırılmıştır. İkinci aşamada ise öğrencinin eğitim seviyesinin elde edilen çözüme etki edip etmediği analiz edilmiştir. Son olarak ise insan çözümlerinin bilimsel yazında bulunan ve GSP’nin çözümünde kullanılan sezgisel yöntemlerin çözümlerine kıyasla en iyi çözüme ne derece yaklaştığı belirlenmeye çalışılmıştır.Araştırmanın Yöntemi: Çalışma kapsamında istatistiksel yöntemler ile sezgisel yöntemler kullanılmaktadır. İlk olarak farklı eğitim seviyelerinde bulunan öğrencilere 15, 25 ve 35 düğümlü GSP ağ şeklinde ifade edilerek çözmeleri istenmiştir. Öğrencilerden alınan cevaplar kullanılarak eğitim seviyesinin ve cinsiyetin çözüm performansına etkisini analiz etmek için parametrik olmayan Mann-Whitney-Wilcoxon ve Mann-Whitney-U testleri kullanılmıştır. Elde edilen insan çözümlerinin kalitesinin belirlenebilmesi için sezgisel yöntemlerle elde edilen çözümler kullanılmıştır. GSP’nin çözümü için bilimsel yazında birçok sezgisel ve metasezgisel yöntem olmakla birlik, çalışma kapsamında Dış Bükey Örtü Ekleme (Convex Hull Insertion), En Yakın Komşu ve Uzay Doldurma Eğrisi (Space Filling Curve) yöntemleri ile 15, 25 ve 35 düğümlü problemler çözülmüştür.

Anahtar Kelimeler:

Problem çözme, optimizasyon, bilişsel araştırmalar

Analysis of Human Performance in the Solution of Traveling Salesman Problem

Purpose: Traveling Salesman Problem (TSP) that can be extended and modified in various ways, is a practical and realistic type of problem and forms the basis for the visual and spatial solution of many optimization problems. In this study, 15, 25 and 35 nodes Travelling Salesman Problems were solved by secondary school, high school and undergraduate students in order to examine human performance in the solution of TSP. In addition to this assessment, whether gender and education level had an impact on the quality of the solution was analyzed.Research Methods: The categorical comparisons of solutions, male-female, and educational level were examined with the help of nonparametric statistical methods. In addition, for the three levels of education, the Kruskal-Wallis Test was applied to determine whether the difference between the education levels was significant. On the other hand, the performance of human solutions was compared with the heuristic methods found in the literature.Findings: As a result, it was seen that the gender difference was not statistically significant for all problems. On the other hand, it was determined that the education level had a significant effect on the solutions. It can be concluded for the given problems that the human solutions produced as good results as the solutions obtained with other heuristic methods in the literature. Implications for Research and Practice: The findings of the study confirm previous studies. By examining the effect of the factors that affect optimization strategies, it is possible to produce human-based TSP heuristic solutions that surpass all existing heuristic algorithms.

Keywords:

problem solving, optimization, cognitive researches,

PDF

___

Alaykıran, K., & Engin, O. (2005). Ant colony metaheuristic and an application on traveling salesman problem. Journal of the Faculty of Engineering and Architecture of Gazi University, 20(1), 69-76. https://dergipark.org.tr/en/pub/gazimmfd/issue/6663/88878
Best, B. J., & Simon, H. A. (2000, March). Simulating human performance on the traveling salesman problem. In Proceedings of the Third International Conference on Cognitive Modeling (pp. 42-49).
Blaser, R. E., & Wilber, J. (2013). A comparison of human performance in figural and navigational versions of the traveling salesman problem. Psychological Research, 77(6), 761-772. https://doi.org/10.1007/s00426-012-0470-8
Burke, E. K., Cowling, P. I., & Keuthen, R. (1999). New models and heuristics for component placement in printed circuit board assembly. In Proceedings 1999 International Conference on Information Intelligence and Systems (Cat. No. PR00446) (pp. 133-140). IEEE.
Chowdhury, S., Tong, W., Messac, A., & Zhang, J. (2013). A mixed-discrete particle swarm optimization algorithm with explicit diversity-preservation. Structural and Multidisciplinary Optimization, 47(3), 367-388. https://doi.org/10.1007/s00158-012-0851-z
Cutini, S., Di Ferdinando, A., Basso, D., Bisiacchi, P. S., & Zorzi, M. (2005, July). A computational model of planning in the Traveling Salesman Problem. In Proceedings of the twenty-seventh annual conference of the cognitive science society. Erlbaum, Mahwah.
Dantzig, G.B., Fulkerson, D.R. & Johnson, S.M. (1954). Solution of a large-scale traveling salesman problem. Operations Research, 2(4), 393–410. https://doi.org/10.1287/opre.2.4.393
Dikmen, H., Dikmen, H., Elbir, A., Eksi, Z., & Çelik, F. (2014). Optimization and Comparison of Travelling Salesman Problem Using Ant Colony and Genetic Algorithms. Suleyman Demirel University Journal of Natural and Applied Science, 18(1), 8-13. https://dergipark.org.tr/tr/download/article-file/193799
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66. https://doi.org/10.1109/4235.585892
Dow, G. T., & Mayer, R. E. (2004). Teaching students to solve insight problems: Evidence for domain specificity in creativity training. Creativity Research Journal, 16(4), 389-398. https://doi.org/10.1080/10400410409534550
Dry, M. J., & Fontaine, E. L. (2014). Fast and Efficient Discrimination of Traveling Salesperson Problem Stimulus Difficulty. The Journal of Problem Solving, 7(1), 84-93. https://doi.org/10.7771/1932-6246.1160
Dry, M., Preiss, K., & Wagemans, J. (2012). Clustering, randomness, and regularity: Spatial distributions and human performance on the traveling salesperson problem and minimum spanning tree problem. The Journal of Problem Solving, 4(1), 1-17. https://doi.org/10.7771/1932-6246.1117
Erdem, Y., & Keskintürk, T. (2011). Kanguru Algoritması Ve Gezgin Satıcı Problemine Uygulanması. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 10(19), 51-63. http://acikerisim.ticaret.edu.tr/xmlui/bitstream/handle/11467/608/M00434.pdf?sequence=1&isAllowed=y
Freisleben, B., & Merz, P. (1996, May). A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In Proceedings of IEEE international conference on evolutionary computation (pp. 616-621). IEEE.
Graham, S. M., Joshi, A., & Pizlo, Z. (2000). The traveling salesman problem: A hierarchical model. Memory & cognition, 28(7), 1191-1204. https://doi.org/10.3758/BF03211820
Haxhimusa, Y., Carpenter, E., Catrambone, J., Foldes, D., Stefanov, E., Arns, L., & Pizlo, Z. (2011). 2D and 3D traveling salesman problem. The Journal of Problem Solving, 3(2), 167-193. https://doi.org/10.7771/1932-6246.1096
Hoffman, K. L., & Padberg, M. (1993). Solving airline crew scheduling problems by branch-and-cut. Management science, 39(6), 657-682. https://doi.org/10.1287/mnsc.39.6.657
Jati, G. K. (2011, September). Evolutionary discrete firefly algorithm for travelling salesman problem. In International Conference on Adaptive and Intelligent Systems (pp. 393-403). Springer, Berlin, Heidelberg.
Joines A., Kay, M.G., Karagul K., Tokat S. (2017). Performance analysis of Genetic Algorithm Optimization Toolbox via Traveling Salesperson Problem. In W. Sayers (Eds.) Contemporary Issues in Social Sciencesand Humanities (pp. 213-221), Landon, UK, AGP Research.
Karagul, K., Aydemir, E., & Tokat, S. (2016). Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6(2), 103-113. http://dx.doi.org/10.11121/ijocta.01.2016.00268
Kay, M. (2014). Matlog: Logistics Engineering Matlab Toolbox. Retrieved from www.ise.ncsu.edu/kay/matlog/ Accessed 15.03.2018
Kim, B. I., Koo, J., & Park, J. (2010). The combined manpower-vehicle routing problem for multi-staged services. Expert Systems with Applications, 37(12), 8424-8431. https://doi.org/10.1016/j.eswa.2010.05.036
Kong, X., & Schunn, C. D. (2007). Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem. Cognitive Systems Research, 8(3), 192-207. https://doi.org/10.1016/j.cogsys.2007.06.002
Kyritsis, M., Gulliver, S. R., Feredoes, E., & Din, S. U. (2018). Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects. Cognitive Systems Research, 52, 387-399. https://doi.org/10.1016/j.cogsys.2018.07.027
Liew, S. (2012). Introducing convex layers to the Traveling Salesman Problem. arXiv preprint arXiv:1204.2348.
MacGregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Perception & Psychophysics, 58(4), 527-539. https://doi.org/10.3758/BF03213088
MacGregor, J. N., Chronicle, E. P., & Ormerod, T. C. (2006). A comparison of heuristic and human performance on open versions of the traveling salesperson problem. The Journal of Problem Solving, 1(1), 33-43. https://doi.org/10.7771/1932-6246.1005
Malek, M., Guruswamy, M., Pandya, M., & Owens, H. (1989). Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Annals of Operations Research, 21(1), 59-84. https://doi.org/10.1007/BF02022093
Mavrovouniotis, M., & Yang, S. (2013). Ant colony optimization with immigrants’ schemes for the dynamic travelling salesman problem with traffic factors. Applied Soft Computing, 13(10), 4023-4037. https://doi.org/10.1016/j.asoc.2013.05.022
Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18, 181-186. https://doi.org/10.1016/j.endm.2004.06.029
Míča, O. (2015, November). Comparison metaheuristic methods by solving travelling salesman problem. In The international scientific conference INPROFORUM, České Budějovice, Czech Republic (pp. 161-165).
Montgomery, J., & Randall, M. (2003). The accumulated experience ant colony for the traveling salesman problem. International Journal of Computational Intelligence and Applications, 3(02), 189-198. https://doi.org/10.1142/S1469026803000938
Ormerod, T. C., & Chronicle, E. P. (1999). Global perceptual processing in problem solving: The case of the traveling salesperson. Perception & Psychophysics, 61(6), 1227-1238. https://doi.org/10.3758/BF03207625
Potvin, J. Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63(3), 337-370. https://doi.org/10.1007/BF02125403
Ratliff, H. D., & Rosenthal, A. S. (1983). Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Operations Research, 31(3), 507-521. https://doi.org/10.1287/opre.31.3.507
Sahin, Y., & Karagul, K. (2019). Solving travelling salesman problem using hybrid fluid genetic algorithm (HFGA). Pamukkale University Journal of Engineering Sciences, 25(1), 106-114. https://doi.org/10.5505/pajes.2018.81084
Stützle, T., & Hoos, H. (1997, April). The MAX-MIN ant system and local search for the traveling salesman problem. In Proceedings of IEEE international conference on evolutionary computation (pp. 309-314).
Vickers, D., Bovet, P., Lee, M. D., & Hughes, P. (2003). The perception of minimal structures: Performance on open and closed versions of visually presented Euclidean travelling salesperson problems. Perception, 32(7), 871-886. https://journals.sagepub.com/doi/abs/10.1068/p3416
Wang Y., Tian D., Li Y. (2013) An Improved Simulated Annealing Algorithm for Traveling Salesman Problem. In Lu W., Cai G., Liu W., Xing W. (eds), Proceedings of the 2012 International Conference on Information Technology and Software Engineering. Lecture Notes in Electrical Engineering, vol 211. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34522-7_56
Wang, K. P., Huang, L., Zhou, C. G., & Pang, W. (2003, November). Particle swarm optimization for traveling salesman problem. In Proceedings of the 2003 International Conference on Machine Learning and Cybernetics, 3, 1583-1585, Xi'an, China.
Yu Z., Jinhai L., Guochang, G., Rubo Z., Haiyan, Y. (2002, June). An implementation of evolutionary computation for path planning of cooperative mobile robots. Proceedings of the 4th World Congress on Intelligent Control and Automation, Shanghai, China, (pp. 1798-1802). https://doi.org/10.1109/wcica.2002.1021392
Zhao F, Li S, Sun J, Mei D. (2009). Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Industrial Engineering, 56(4), 1642-1648. https://doi.org/10.1016/j.cie.2008.10.014