Analysis of online optimization problems in navigation and search on networks
Navigasyon ve arama konusunda çeşitli çevirimiçi eniyileme problemlerinin analizi
- Tez No: 544342
- Danışmanlar: PROF. DR. FATMA SİBEL SALMAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği ve Operasyon Yönetimi
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
In this thesis, we study online optimization problems that are related to navigation and search on networks. In online problems information is revealed incrementally, and decisions must be made before all information is available. We design and analyze strategies for several online problems with applications in disaster response, search-and-rescue, security, and defense. We prove worst-case competitive ratios to analyze the performance of the proposed strategies. We first study the online k-Canadian Traveler Problem (k-CTP) on O-D edge-disjoint graphs. An optimal randomized strategy was given in the literature. We prove that the given strategy cannot be implemented in some cases and modify it such that it is optimal and can be implemented in all cases. We consider the online multi-agent k-CTP. We derive improved lower bounds on the competitive ratio of deterministic strategies for the cases with limited and complete communication. We introduce two deterministic strategies and show that one of them is optimal in both cases with complete and limited communication on O-D edge-disjoint graphs. We provide lower bounds on the competitive ratio of randomized strategies for the cases without communication, with limited communication and with complete communication. We introduce a randomized online strategy which is optimal for both cases with limited and complete communication on O-D edge-disjoint graphs. We also consider the online Minimum Latency Problem with edge uncertainty. We present an optimal deterministic strategy. Moreover, we present a lower bound on the expected competitive ratio of randomized strategies. Finally, we investigate the online Discrete Search Problem with traveling and search costs on undirected graphs. We propose tight competitiveness lower bounds together with optimal deterministic and randomized strategies.
Özet (Çeviri)
Bu tezde, ağ yapıları üstünde navigasyon ve arama ile ilgili çeşitli çevrimiçi eniyileme problemleri üzerinde çalışılmıştır. Çevrimiçi problemlerde bilgiler adım adım açıklanır ve tüm bilgiler mevcut olmadan önce kararlar alınmalıdır. Tez kapsamında, afete müdahale, arama kurtarma, güvenlik ve savunma alanlarında uygulamaları olan birkaç çevrimiçi eniyileme problemi için eniyi stratejiler tasarlanıp bunların performansları teorik olarak analiz edilmiştir. Önerilen stratejilerin performanslarını analiz etmek için en kötü durumda, bilginin baştan elde olduğu (çevrimdışı) durumdaki en iyi çözüme göre, rekabetçi oranlar belirlenmiştir. İlk olarak, çevrimiçi k-Kanadalı Gezgin Problemi (k-KGP), ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenmiştir. Daha önce literatürde bu problem için bir eniyi rassal strateji verilmiştir. Bu çalışmada, bazı durumlarda bu stratejinin uygulanamaz olduğu gösterilerek, strateji her durumda uygulanabilir ve eniyi olacak şekilde değiştirilmiştir. Daha sonra çevrimiçi çok katılımcılı k-KGP ele alınmıştır. Bu problemin sınırlı ve sınırsız iletişimin olduğu iki durumuna bakılarak, literatürde verilen, deterministik stratejilerin rekabetçi oranına alt sınırı iyileştirilmiştir. Aynı iki durum, ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenerek, iki deterministik strateji geliştirilmiştir. Bunlardan bir tanesinin eniyi olduğu ispatlanmıştır. Problemin iletişimin olmadığı, sınırlı ve sınırsız iletişimin olduğu üç durumuna bakılarak, rassal stratejilerin rekabetçi oranına alt sınırlar geliştirilmiştir. Ayrıca iletişimli durumlar için rassal bir strateji geliştirilerek, bunun ayrıtları kesişmeyen yollara sahip çizgeler üzerinde eniyi olduğu ispatlanmıştır. Ayrıt belirsizliği olan çevrimiçi Minimum Gecikme Problemi de ele alınan bir başka problemdir. Bu problem için bir eniyi deterministik strateji geliştirilmiştir. Ayrıca, rassal stratejilerin beklenen rekabetçi oranına bir alt sınır bulunmuştur. Son olarak, çevrimiçi Ayrık Arama Problemi, yönlendirilmemiş çizgelerdeki seyahat ve arama maliyetleriyle incelenmiştir. Eniyi deterministik ve rassal stratejiler bulunmuştur.
Benzer Tezler
- Savaş gemisi elektrik dağıtım sisteminin arıza sonrası toparlanmasına yönelik yöntem geliştirilmesi
New developing reconfiguration method for naval shipboard power distribution system after fault situation
İZZET EMRE AFACAN
Doktora
Türkçe
2024
Elektrik ve Elektronik MühendisliğiSakarya ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ALİ YALÇIN
- Darboğaz bir makinada metasezgisel yöntemlerletoplam hazırlık zamanı minimizasyonu
Minimization of total setup time on a bottleneck machine using metaheuristic methods
MUHAMMET AYDIN
Yüksek Lisans
Türkçe
2025
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HALİL İBRAHİM DEMİR
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- Nükleer rezonasta moleküler yapıların incelenmesi (yapısal faz geçiş kuramları üzerine bir inceleme)
Başlık çevirisi yok
ABDURRAHMAN ANDİÇ
Yüksek Lisans
Türkçe
1986
Fizik ve Fizik MühendisliğiUludağ ÜniversitesiFizik Ana Bilim Dalı
PROF. DR. AYTAÇ YALÇINER
- Makro besin elementlerinin (NPK) İzmir'de Mayıs ayında açığa dikilen 4-6 cm çevre büyüklüğündeki Gladiolus cinsine ait“hunting song”ve“Novalüx”kültür çeşitlerinin yumrularının gelişmeleri üzerine etkileri
Başlık çevirisi yok
TAHA ALİ AMEN
Yüksek Lisans
Türkçe
1985
ZiraatEge ÜniversitesiPeyzaj Mimarlığı Ana Bilim Dalı
DOÇ. DR. ADNAN HATİPOĞLU