K shortest path problem together with arc tolerances
Başlık çevirisi mevcut değil.
- Tez No: 9665
- Danışmanlar: DOÇ. DR. CANAN SEPİL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Duyarlılık analizi, K en kısa yol yöntemi, Yöneylem araştırması, Sensitivity analysis, K shorted path method, Operations research
- Yıl: 1990
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET K EN KİSA YOL PROBLEMİ ¥E ARK TOLERANSLARI Mi N HESAPLANMASI YİLMAZ, Hakan Yüksele Lisans Tezi, End. Müh. Bölümü Tez Yöneticisi: Dec.ûr. Canan SEPİL Mayıs 1990 Bu makalede, doğrultusuz, ark uzunlukları pozitif olan şebekelerde başlangıç ve bitiş noktalan arasındaki döngüsüz K en kısa yolu etkili bir şekilde bulan ve Katoh tarafından geliştirilen yöntem ile birlikte K inci çözümün optimalitesini bozmadan ark uzunluklarında mümkün olan en büyük artış ve en büyük azalışları karakterize eden bir yöntem açıklanmaktadır. Bu toleransların K en kısa yol için hesaplanması, mevcut yollardan hangilerinin sistemde mevcut olan ve/veya eklenen kısıtlayıcıları karşıladığı ve optimal kaldığı hususunda karar verilmesinde esneklik sağlar. Katoh tarafından geliştirilen K en kısa yol yönteminin önemi m ve n sırasıyla toplam ark ve düğüm sayıları olmak üzere, bilgisayar zamanı açısından diğer yöntemlerden daha iyi olmasıdır. Bu makalede önce K en kısa yol problemi ve ark toleranslarının hesaplanmasında mevcut olan yöntemler gözden geçirilmiştir. bunu, Katoh'un geliştirdiği yöntem, kompleksitesi 0<Kn2>, izlemektedir. Son olarak, K en kısa yolların herbirinde ark toleranslarını bulmak için geliştirilen ve“cycle tracing”yönteminin bir devamı olan yeni metot açıklanmaktadır.
Özet (Çeviri)
ABSTRACT K LOO PL ESS SHORTEST PATHS TOGETHER WITH ARC TOLERANCES YILMAZ, Hakan M.S. in Industrial Engineering, Supervisor: Assoc. Prof. Canon SEPİL May 1990, This paper works 88 an efficient algorithm for finding K shortest loopless paths between two specified nodes of an undirected graph G having nonnegative arc lengths and characterizes the ranges of maximum increase and decrease in the arc lengths that can be tolerated without changing the optimally of the Kth solution. Calculating arc tolerances for K shortest paths provides flexibility fn deciding ybtcti of the K shortest paths satisfy the imposed constraints and stay optimal. The significance of the algorithm developed by Katoh is that, letting n and rn as the number of nodes and arcs in G respectively, it is better than those realized by the other algorithms i n terms of its runni ng ti me. This paper first reviews the existing algorithms for finding K shortest paths together with the several algorithms for calculating all arc tolerances. This is followed by the presentation of Katoh's algorithm which is proved to be O(KN^) in terms of time complexity in the worst case. Finally, the new method which is an extension of“cycle tracing”algorithm for finding all the arc tolerances in all K paths is combined with this method in an example problem to show how it works. Key w.ords: K shortest loopless paths, sensitivity analysis m
Benzer Tezler
- Robot kollarda optimum hareket sentezi
Optimal trajectory synthesis for manipulation robots
ÖZGÜR TURHAN
- Sönümlemeli kanallarda kafes kodlamalı sistemler için birleşik serpiştirme tekniği
Combined interleaving technique for trellis coded systems in feding channels
ERSİN ÖZTÜRK
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÜMİT AYGÖLÜ
- Wavelength routing algorithms far optical networks
Optik ağlarda yönlendirme algoritmaları
DEMETER GÖKIŞIK
Yüksek Lisans
İngilizce
1998
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SEMİH BİLGEN
- Durağan olmayan kanallarda uyarlamalı hata kontrol yöntemleri
Adaptive coding schemes for time-varying channels
ERSİN ERGEZER
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. H. ÜMİT AYGÖLÜ