Bir şebekede en kısa yol problemi için yeni bir yaklaşım
A new approach for the shortest path problem in a network
- Tez No: 99750
- Danışmanlar: Y.DOÇ.DR. SAMİM DÜNDAR
- Tez Türü: Yüksek Lisans
- Konular: Ekonometri, Econometrics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2000
- Dil: Türkçe
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Sosyal Bilimler Enstitüsü
- Ana Bilim Dalı: Ekonometri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 111
Özet
Yöneylem araştırması ve endüstri mühendisliğinde bilinen bir problem olan En Kısa Yol Problemi, Çizge Kuramının da uygulamada en çok kullanılan problemlerinden biridir. En Kısa Yol Problemi, verilen iki nokta arasındaki yollar içinden uzunluğu en kısa yolu bulma ya da verilen bir düğümden başlayan ve diğer tüm düğümlere ulaşan yollar içinden en kısa uzunlukta olan yolun bulunması olarak tanımlanır. Çizgenin düğüm sayısının büyük olduğu durumlarda bu çizgeyi alt çizgelere ayırarak problemi çözme, bilinen bir yöntemdir. Verilen çizge, düğümleri sayısı hemen hemen eşit ve kesim kirişlerinin ağırlıktan toplamı minimum olacak biçimde parçalanna aynlır. Bu çalışmada ilk olarak çizge kuramının temel kavranılan verilmiş, ardından en kısa yol problemi için iki adet algoritma birer uygulama ile sunulmuş, çizge parçalama için Kemighan Lin algoritması ve merkezleştirilmiş ağırlıklı aynt algoritmaları ele alınmıştır. Son olarak ise en kısa yol probleminin uygulanacağı çizge önce, Kemighan-Lin algoritması ile yukarıdaki kurallara uygun biçimde parçalanna aynlmış, sonra yolun başlangıç düğümü ve son düğümü dikkate alınarak, bir zincir çizge haline getirilmiş, her parça içinde amaç düğümlerle ilişkiyi sağlayacak biçimde en kısa yollar hesaplanmış, ardından bunlann geçiş kirişleri ile birleştirilmesi yöntemiyle amaç düğümler arasındaki en kısa yolu bulan bir algoritma geliştirilmiştir.
Özet (Çeviri)
Shortest Path Problem, which is well known in Industrial Engineering and Operational Research, is one of the most encountered problems of Graph Theory in application. Shortest Path Problem is defined as finding the shortest way between two given nodes or finding the shortest path from which begins from a given node and arrives to all given nodes. If the node numbers of the graph is so much, then solving problem by separating this graph to processors is an appropriate method. The given graph is separated to parts as the processors are balanced and the cutsize would be minimum. In this study, first of all basic concepts of Graph Theory is given, then two algorithms for the Shortest Path Problem are presented with an application and dealt with Kernighan Lin Algorithm to partition the graph. Finally, the graph which Shortest Path Problem would be applied on was partitioned into pieces in regard with the rules above with Kernighan-Lin Algorithm, then converted to a chain graph dealing with the starting node and target node of the problem. In all the processors, the shortest paths are calculated in order to provide relation with objective nodes and then an algorithm which finds the shortest path between objective nodes is developed by the method of uniting these with cutting edges.
Benzer Tezler
- ATM şebekelerde trafik ve yığılma kontrol problemi ve çözüm yaklaşımları
Traffic control and congestion control in ATM networks and proposed solution approaches
NİL IŞIL
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÜNSEL DURUSOY
- Dağıtık üretim sistemleri içeren dağıtım şebekelerinde akıllı gerilim kontrol yöntemi geliştirilmesi
Development of an intelligent voltage control method in distribution networks including distributed generation systems
MERVE GÜLERYÜZ HALAÇLI
Doktora
Türkçe
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞEN DEMİRÖREN
- Elektriksel adres dağıtımında yeni bir yaklaşım
A new approach to electrical address distribution
SEVBAN YENİ
Yüksek Lisans
Türkçe
2021
Coğrafyaİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. DURSUN ZAFER ŞEKER
- Şebeke etkileşimli tüketiciler ile toplu talep yönetimi
Aggregated demand side management with grid responsive consumers
MUSTAFA ALPARSLAN ZEHİR
Doktora
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA BAĞRIYANIK
- Yenilenebilir enerji santrallerinde yapay sinir ağları yöntemiyle enerji üretiminin modellenmesi ve planlanması
Modeling and planning of energy production in renewable energy stations with artificial neural networks
MUSTAFA ALPER ÖZPINAR
Doktora
Türkçe
2007
EnerjiYıldız Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF.DR. DÜRRİYE BİLGE
PROF.DR. ERALP ÖZİL