Browsing by Author "Varol, Taha"

Now showing 1 - 2 of 2

Metadata only
Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions
(Informs, 2024) Varol, Taha; Özener, Okan Örsan; Albey, Erinç; Industrial Engineering; ÖZENER, Okan Örsan; ALBEY, Erinç; Varol, Taha
It is essential to solve complex routing problems to achieve operational efficiency in logistics. However, because of their complexity, these problems are often tackled sequentially using cluster-first, route-second frameworks. Unfortunately, such two-phase frameworks can suffer from suboptimality due to the initial phase. To address this issue, we propose leveraging information about the optimal tour lengths of potential clusters as a preliminary step, transforming the two-phase approach into a less myopic solution framework. We introduce quick and highly accurate Traveling Salesperson Problem (TSP) tour length estimators based on neural networks (NNs) to facilitate this. Our approach combines the power of NNs and theoretical knowledge in the routing domain, utilizing a novel feature set that includes node-level, instance-level, and solution-level features. This hybridization of data and domain knowledge allows us to achieve predictions with an average deviation of less than 0.7% from optimality. Unlike previous studies, we design and employ new instances replicating real-life logistics networks and morphologies. These instances possess characteristics that introduce significant computational costs, making them more challenging. To address these challenges, we develop a novel and efficient method for obtaining lower bounds and partial solutions to the TSP, which are subsequently utilized as solution-level predictors. Our computational study demonstrates a prediction error up to six times lower than the best machine learning (ML) methods on their training instances and up to 100 times lower prediction error on out-of-distribution test instances. Furthermore, we integrate our proposed ML models with metaheuristics to create an enumeration-like solution framework, enabling the improved solution of massive scale routing problems. In terms of solution time and quality, our approach significantly outperforms the state-of-the-art solver, demonstrating the potential of our features, models, and the proposed method.
Metadata only
Neural network estimatorsfor optimal tour lengths of TSP instances with arbitrary node distributions
Varol, Taha; Özener, Okan Örsan; Özener, Okan Örsan; Yanıkoğlu, İhsan; Albey, Erinç; Ekici, Ali; Güler, M. G.; Department of Data Science; Varol, Taha
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 predictions 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 computational 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 rout- ing 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.