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: Derin öğrenme, Gezgin satıcı problemi, Sinir ağları, Yönlendirme, Deep learning, Travelling salesman problem, Nerve net, Routing
- 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ı: Belirtilmemiş.
Ö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
- Extreme learning machine based on L1 and L2 norms
L1 ve L2 norma dayalı aşırı makine öğrenmesi
HASAN YILDIRIM
Doktora
İngilizce
2020
İstatistikÇukurova Üniversitesiİstatistik Ana Bilim Dalı
PROF. DR. MAHMUDE REVAN ÖZKALE ATICIOĞLU
- Randomize olmayan klinik çalışmalarda en uygun eşleştirme analizi için makine öğrenme algoritmaları ile yeni propensity skor tahmin modellerinin geliştirilmesi
Development of new propensity score estimation models with machine learning algorithms for optimal matching analysis in non-randomized clinical trials
EMRE DEMİR
Doktora
Türkçe
2019
BiyoistatistikAnkara ÜniversitesiBiyoistatistik Ana Bilim Dalı
DOÇ. DR. SERDAL KENAN KÖSE
- Multi-channels deep convolution neural network for early classification of multivariate time series
Çok kanallı derin dönüşümerken sinir ağıçok değişkenli zaman sınıflandırmasıdiziler
AHMED MUAYAD QADER QADER
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiBilişim Teknolojileri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AYÇA KURNAZ TÜRKBEN
- Physics guided neural network based state-of-charge estimator for lithium-ion batteries
Lithium-ion piller için fizik destekli sinir ağı tabanlı şarj durumu tahmincisi
FEDI SALHI
Yüksek Lisans
İngilizce
2022
Mekatronik MühendisliğiYıldız Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERHAN AKDOĞAN
- Channel estimation in OFDM system using neural network combined with artificial bee colony algorithm
Yapay arı kolonisi algoritması ile birleştirilmiş yapay sinir ağı kullanarak OFDM sisteminde kanal kestirimi
SIDRA MEO RAJPUT
Yüksek Lisans
İngilizce
2018
Elektrik ve Elektronik MühendisliğiErciyes ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. NECMİ TAŞPINAR