New Learning-Assisted Memetic Algorithm for the Close-Enough Traveling Salesman Problem (LA-CETSP)
5th International Conference on Informatics and Software Engineering, IISEC 2026, Ankara, Türkiye, 5 - 06 Şubat 2026, ss.364-369, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Doi Numarası: 10.1109/iisec69317.2026.11418468
- Basıldığı Şehir: Ankara
- Basıldığı Ülke: Türkiye
- Sayfa Sayıları: ss.364-369
- Anahtar Kelimeler: CETSP, Learn Heuristics, Machine Learning, Memetic Algorithm, Optimization, Survival Models
- TED Üniversitesi Adresli: Evet
Özet
The Close-Enough Traveling Salesman Problem (CETSP) is a geometric variant of the classical Traveling Salesman Problem in which each target is associated with a circular neighborhood, and visiting any point within this region is considered sufficient. Building on the success of the state-of-the-art Memetic Algorithm for CETSP (MA-CETSP), this study proposes a learning-assisted extension aimed at reducing computational overhead by filtering unpromising offspring prior to local search. While MA-CETSP combines multi-step crossover, variable neighborhood descent (VND), and diversity-preserving population management to achieve strong performance, evaluating every generated offspring with VND remains computationally expensive. To address this limitation, we modify the algorithm to record detailed geometric and cost-based features for each individual and train survival analysis models - namely Cox Proportional Hazards, Random Survival Forest, and Gradient Boosting Survival Analysis - to estimate each offspring's likelihood of survival in the population. Experiments conducted on 4 benchmark instances demonstrate that the learning-assisted variants can prune approximately 13-26% of generated offspring, substantially reducing redundant local search calls while maintaining competitive solution quality. Among the evaluated models, Cox PH provides the strongest pruning effect with minimal degradation, RSF achieves the most balanced trade-off between pruning and stability, and GBSA yields the best single-run solution but exhibits higher variability. Overall, the results indicate that learning-based survival prediction is an effective and promising strategy for accelerating metaheuristic optimization in geometric routing problems.