Neural network estimatorsfor optimal tour lengths of TSP instances with arbitrary node distributions
Gelişigüzel düğüm dağılımlarına sahip GSP örneklerinin en iyi tur uzunluğunu tahminlemek için sinir ağı tahminleyicileri
- Tez No: 760276
- Danışmanlar: PROF. DR. OKAN ÖRSAN ÖZENER, DR. ÖĞR. ÜYESİ ERİNÇ ALBEY
- Tez Türü: Yüksek Lisans
- Konular: Ulaşım, Transportation
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Veri Bilimi Ana Bilim Dalı
- Bilim Dalı: Veri Bilimi Bilim Dalı
- Sayfa Sayısı: 68
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Event-driven state estimation in electric distribution systems
Elektrik dağıtım sistemlerinde olay güdümlü durum kestirimi
FIAZ AHMAD
Doktora
İngilizce
2017
Mekatronik MühendisliğiSabancı ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
Assist. Prof. Dr. MELTEM ELİTAŞ
Prof. Dr. ASIF SABANOVIC
- Estimation of sideslip angle for highly automated vehicles: Experimental verification and evaluation
Otonom araçlarda yana kayma açısı kestirimi: Deneysel doğrulama ve değerlendirme
SEĞMEN DORAN
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUMİN TOLGA EMİRLER
- Tanı testlerinin değerlendirilmesinde kullanılan standartlar ve analitik yöntemler
Standards and analytic techniques used in evaluation of diagnostic tests
İLKER ÜNAL
Doktora
Türkçe
2010
BiyoistatistikÇukurova ÜniversitesiBiyoistatistik Ana Bilim Dalı
PROF. DR. H. REFİK BURGUT
- Gezgin satıcı probleminin çözümünde sinirsel ağ yaklaşımı
Neural network approach in the solution of traveling salesman problem
KAAN ASLAN
Yüksek Lisans
Türkçe
1999
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. A. SERMET ANAGÜN
- Debugging image classification algorithms using human assisted feedback
İnsan yardımlı geri bildirim kullanarak resim sınıflandırma algoritmalarında hata ayıklama
KADİRCAN BECEK
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. GÖZDE AKAR