Neural network estimatorsfor optimal tour lengths of TSP instances with arbitrary node distributions

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 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.

Lojistikte operasyonel verimlilik için, karmaşık rotalama problemlerini çözmeye ihtiyaç duymaktayız. Bu problemlerin karmaşıklığından kaynaklı olarak, genelde önce-kümele sonra-rotala (ÖKSR) benzeri sıralı çözüm yöntemleri kullanılmaktadır. Fakat, bu tip iki fazlı çözüm yöntemlerinden elde edilen sonuçlar genelde alt-optimallikten muzdarip olmaktadır. Buradaki alt-optimalliği azaltmak adına, yaratılan kümelere ait optimal tur uzunlukları bilgilerinden faydalanılabilir. Bu sayede, bahsedilen iki fazlı çözüm yöntemi daha az miyopik bir çözüm yöntemine dönüştürülmüş olur. Bu bakımdan, çabuk ve yüksek isabetli bir Gezgin Satıcı Problemi (GSP) tur uzunluğu tahminleyicisi yüksek kaliteli kümeleri aramak amacıyla kullanılabilir. Buradan yola çıkarak, yeni ve hesaplama bakımından verimli, yapay sinir ağı temelli optimal GSP tur uzunluğu tahminleyicileri öneriyoruz. Yaklaşımımız, yapay sinir ağlarının gücünü rotalama alanındaki teorik bilgi ile birleştirerek düğüm seviyesi, örnek seviyesi ve çözüm seviyesi özniteliklerinden oluşan tamamen yeni bir öznitelik seti kullanmaktadır. Bu veri ve alan bilgisi hibridizasyonu, yüzde 0.7'den (ortalamada) daha az sapma ile en iyi tur uzunluğu tahminlemesine olanak sağlamaktadır. Önceki çalışmalardan farklı olarak, gerçek dünya lojistik ağ ve morfolojilerini örnek alan yeni tip örnekler tasarlayıp kullanıyoruz. Bu yeni tip örneklerin bazı karakteristik özellikleri hesaplama bakımından ciddi maliyetleri beraberinde getirerek optimal çözümlerin elde edilmesini zorlaştırmaktadır. Bu tip problem patolojileri ile başa çıkmak adına optimal GSP çözümüne ait daha sonra çözüm seviyesinde öznitelikler olarak kullanmak üzere alt sınır ve kısmi çözümler bulan yeni ve verimli bir yöntem geliştiriyoruz. Ek olarak, en iyi makine öğrenmesi modellerine göre dağılım dışı problem örneklerinde 100 kata kadar daha az tahminsel hata yaptığımızı gösteren bir hesaplamalı çalışma yapıyoruz. Son olarak, önerilen makine öğrenmesi modellerini metasezgisel yöntemlerle birleştirerek çok büyük rotalama problemlerini etkili bir şekilde numaralandırma benzeri bir mekanizma ile çözülmesini sağlayan yöntem geliştiriyoruz. Geliştirilen yöntem en gelişmiş çözücüye kıyasla hem çözüm kalitesi hem de çözüm süresi bakımından ciddi şekilde daha iyi performans göstererek önerilen modellerin ve önerilen yöntemlerin potansiyellerini ortaya koymaktadır.