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: Belirtilmemiş.
- 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ı: 73
Ö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, 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Ü
- Konut yerleşimlerinin planlama ve uygulama süreçlerinde etkili olan sosyal donatı kararlarının batışehir örneği üzerinden değerlendirilmesi
Evaluation of social infrastructure decisions that are effective in planning and implementation processes of housing settlements through the batişehi̇r case
SONGÜL SOLA
Yüksek Lisans
Türkçe
2019
MimarlıkYıldız Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. CANDAN ÇINAR ÇITAK
- All Colors Shortest Path Problem on Trees
Ağaç Yapılarında Tüm Renkleri İçeren En Kısa Yol Problemi
MEHMET BERKEHAN AKÇAY
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Ekonomi ÜniversitesiAkıllı Mühendislik Sistemleri Ana Bilim Dalı
DOÇ. DR. HÜSEYİN AKCAN
DOÇ. DR. CEM EVRENDİLEK
- Bounding procedures on bi-directional labeling algorithm of TDVRPTW in branch-and-cut-and-price framework
Dal-ve-kesme-ve-değer algoritması çerçevesinde zamana bağımlı zaman pencereli araç rotalama probleminin iki yönlü etiketlendırme algoritması üzerinde sınırlandırma yöntemleri
SELEN KÖKTEN
Yüksek Lisans
İngilizce
2011
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. DR. TOM VAN WOENSEL
YRD. DOÇ. DR. CEM İYİGÜN