Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions

Name: Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions
Author: Varol, Taha, Özener, Okan Örsan, Albey, Erinç

İsim	Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions
Yazar	Varol, Taha, Özener, Okan Örsan, Albey, Erinç
Basım Tarihi:	2024
Basım Yeri	- Informs
Konu	Traveling salesperson problem, Optimal tour length estimation, Neural networks
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0041-1655
Kayıt Numarası	b135f2c4-ed57-4141-ad0b-3a8f4b8a7c06
Lokasyon	Industrial Engineering
Tarih	2024
Örnek Metin	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.
DOI	10.1287/trsc.2022.0015
Cilt	58

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions

Yazar Varol, Taha, Özener, Okan Örsan, Albey, Erinç

Basım Tarihi 2024

Basım Yeri - Informs

Konu Traveling salesperson problem, Optimal tour length estimation, Neural networks

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0041-1655

Kayıt Numarası b135f2c4-ed57-4141-ad0b-3a8f4b8a7c06

Lokasyon Industrial Engineering

Tarih 2024

Örnek Metin 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.

DOI 10.1287/trsc.2022.0015

Cilt 58