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

Year 2020, Volume: 20 Issue: 87, 137 - 156, 20.05.2020

Kenan Karagul Yusuf Sahın Necdet Guner Aykut Oral

Abstract

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.

Keywords

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

Analysis of Human Performance in the Solution of Traveling Salesman Problem

Abstract

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

References

• 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