Özyeğin Üniversitesi, Çekmeköy Kampüsü Nişantepe Mahallesi Orman Sokak 34794 Çekmeköy İstanbul

Telefon : +90 (216) 564 90 00

Fax : +90 (216) 564 99 99

info@ozyegin.edu.tr

Ağu 05, 2022 - Ağu 11, 2022

Thesis Defense - Taha Varol (MSDS)

 

Taha Varol – M.Sc. Data Science

Prof. Dr. Okan Örsan Özener – Advisor

Asst. Prof. Dr. Erinç Albey – Co-Advisor

 

Date: 11.08.2022

Time: 15.00

Location: AB1 241

 

NEURAL NETWORK ESTIMATORS FOR OPTIMAL TOUR LENGTHS OF TSP

INSTANCES WITH ARBITRARY NODE DISTRIBUTIONS

 

Prof. Dr. Okan Örsan Özener, Özyeğin University

Asst. Prof. Dr. Erinç Albey, Özyeğin University

Prof. Dr. Ali Ekici, Özyeğin University

Asst. Prof. Dr. İhsan Yanıkoğlu, Özyeğin University

Prof. Dr. Mehmet Güray Güler, Yıldız Technical University

Abstract:

To achieve operational efficiency in logistics, we need to solve complex routing problems. Due to their complexity, these problems are often solved sequentially, i.e., using cluster-first route-second (CFRS) type frameworks. However, such two-phase frameworks generally suffer from sub-optimality arising from the first phase. To mitigate this sub-optimality, information about optimal tour lengths of potential clusters can be exploited first, thereby transforming this two-phase approach into a less myopic solution framework. In that aspect, a quick and highly accurate Traveling Salesperson Problem (TSP) tour length estimator can be utilized for searching high-quality clusters. Motivated by this, we propose novel and computationally efficient neural network-based optimal TSP tour length estimators. Our approach uses an entirely new feature set consisting of node level, instance level, and solution level features by combining the power of artificial neural networks and theoretical knowledge in the routing domain. This data and knowledge hybridization enables us to achieve predic- tions with less than 0.7 percent deviation (on average) from the optimality. Unlike previous studies, we design and use new instances mimicking real-life logistics networks and morphologies. These instance characteristics introduce a substantial com- putational cost, making our instances harder to solve. To cope with these pathologies, we devise a new and efficient way of finding lower bounds and partial solutions to TSP later to be used as solution-level predictors. We also conduct a computational study where we produce up to 100 times lower prediction error on out-of-distribution test instances. Finally, we develop an enumeration-like mechanism by incorporating proposed machine learning models and metaheuristics to solve massive-scale routing problems efficiently. We significantly outperform the state-of-the-art solver in terms of solution time and quality, demonstrating the potential of our models and the proposed method.

 

Bio:

Taha Varol received his BS degree in Industrial Engineering from Boğaziçi University in 2018. He worked as a Data Scientist at Turkish Airlines between 2016-2019. He has been working as a Graduate Teaching and Research Assistant at Özyeğin University under the supervision of Prof. Dr. Okan Örsan Özener and Asst. Prof. Dr. Erinç Albey since 2019. His research focuses on machine learning applications in large-scale route planning and optimization.