Endüstri Mühendisliği Bölümü Koleksiyonu
Permanent URI for this collectionhttps://hdl.handle.net/20.500.11779/1942
Browse
Search Results
Article Büyük Ölçekli Etki Enbüyükleme Problemi için Lagrange Gevşetmesi Tabanlı Etkin Bir Çözüm Yöntemi(AKÜ FEMÜBİD, 2020-03-17) Güney, EvrenEtki Enbüyükleme Problemi (EEP) büyük bir sosyal ağ içindeki en etkin K tane kişiyi seçen zor bir stokastik kombinatoryal eniyileme problemidir. Son yıllarda pek çok araştırmacının ilgisini çeken bu problem için çok sayıda etkin yöntem geliştirilmiştir. Sosyal ağdaki bilginin / etkinin yayılımı çeşitli ağ akış modelleri ile tasarlandığında, elde edilen problemin amaç fonksiyonunun alt-birimsel olduğu gözlemlenmiştir. Bu sebeple basit bir açgözlü algoritma ile (1-1/e) en kötü performans garantisine erişilmiştir. Ancak, aç gözlü algoritmanın büyük boyutlu problemlerde çok uzun çözüm süreleri gerektirmesi alternatif yöntem arayışlarına neden olmuştur. Son yıllarda geliştirilen yeni yöntemler genelde büyük boyutlu ağlarda kısa sürede iyi çözümler elde ederken (1-1/e) performans garantisini de korumaktadır. Ancak pek az sayıda çalışma problemin sadece en-iyi çözümüne odaklanmıştır. Bu çalışmada Lagrange gevşetmesi tabanlı ve EEP’yi eniyi / eniyiye yakın çözen ve ölçeklenebilen bir yöntem geliştirilmiştir. Bu çerçevede, öncelikle Örneklem Ortalama Yakınsaması ile özgün probleme yakınsayan belirgin bir matematiksel model kurulmuştur. Daha sonra bu model üzerinde düğüm tabanlı Lagrange gevşetmesi tekniği uygulanmıştır. İlgili yöntem bağımsız çağlayan ve doğrusal eşik bilgi yayılım modelleri varsayımı altında çeşitli boyutlardaki sosyal ağ veri setleri (Facebook, Enron, Gnutella, arXiv) üzerinde test edilmiştir. Bütün senaryolarda eniyi / eniyiye yakın çözümlere ulaşılırken yazındaki mevcut yöntemlere göre on kata kadar hızlanma sağlanmıştır.Article Citation - WoS: 16Citation - Scopus: 18Gradual Covering Location Problem With Multi-Type Facilities Considering Customer Preferences(Elsevier, 2020-09-01) Küçükaydın, Hande; Aras, NecatiIn this paper, we address a discrete facility location problem where a retailer aims at locating new facilities with possibly different characteristics. Customers visit the facilities based on their preferences which are represented as probabilities. These probabilities are determined in a novel way by using a fuzzy clustering algorithm. It is assumed that the sum of the probabilities with which customers at a given demand zone patronize different types of facilities is equal to one. However, among the same type of facilities they choose the closest facility, and the strength at which this facility covers the customer is based on two distances referred to as full coverage distance and gradual (partial) coverage distance. If the distance between the customer location and the closest facility is smaller (larger) than the full (partial) coverage distance, this customer is fully (not) covered, whereas for all distance values between full and partial coverage, the customer is partially covered. Both distance values depend on both the customer attributes and the type of the facility. Furthermore, facilities can only be opened if their revenue exceeds a certain threshold value. A final restriction is incorporated into the model by defining a minimum separation distance between the same facility types. This restriction is also extended to the case where a minimum threshold distance exists among facilities of different types. The objective of the retailer is to find the optimal locations and types of the new facilities in order to maximize its profit. Two versions of the problem are formulated using integer linear programming, which differ according to whether the minimum separation distance applies to the same facility type or different facility types. The resulting integer linear programming models are solved by three approaches: commercial solver CPLEX, heuristics based on Lagrangean relaxation, and local search implemented with 1-Add and 1-Swap moves. Apart from experimentally assessing the accuracy and the efficiency of the solution methods on a set of randomly generated test instances, we also carry out sensitivity analysis using a real-world problem instance.