AI Summary & Key Takeaways
AI InsightBy 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.
📌 3 Key Takeaways
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.
Özet
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.