En fazla kazanç sağlayan rota bulma problemlerinin sezgisel yöntemlerle incelenmesi
A study on heuristics methods for the vehicle routing problems with profit
- Tez No: 271489
- Danışmanlar: YRD. DOÇ. DR. FATİH ERDOĞAN SEVİLGEN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Sezgisel yöntemler, Heuristic methods
- Yıl: 2010
- Dil: Türkçe
- Üniversite: Gebze Yüksek Teknoloji Enstitüsü
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
En Fazla Kazanç Sağlayan Rota Bulma Problemleri, kontrol noktaları ve bu kontrol noktaları arasındaki bağlantıları içeren bir çizge üzerinde çalışır. Problemin amacı, bir başlangıç noktasından başlayıp, bitiş noktasında sonlanacak ve verilen maliyet kısıtını (mesafe, zaman, vb.) aşmayacak biçimde araç sayısı kadar ve toplamda en fazla kazancı sağlacak rotaları belirlemektir. Literatürde bu problemlerin tek araçlı şekli Oryantiring Problemi (OP), çok araçlı şekli ise Takım Oryantiring Problemi (TOP) olarak adlandırılmıştır.Bu tez çalışmasında, OP ve TOP çözümü için Değişken Komşu Arama (DKA) ve Parçacık Sürü Optimizasyonu (PSO) tabanlı iki yeni model geliştirilmiştir. Birinci model, DKA'nın bir versiyonu olan İndirgenmiş-DKA(İ-DKA) yöntemini kullanır. Geliştirilen modelde, İ-DKA geliştirilme amacı olan küresel aramanın yanında yerel arama için de kullanılır.İkinci model ise PSO tabanlıdır. PSO çözüm uzayını, popülasyonu oluşturan parçacıkların sistematik dolaşmasıyla tarar. PSO'nun doğrudan uygulanmasında iyi yerlerde yeterince detaylı arama yapamama ve erken yakınsama gibi zayıflıklarla karşılaşılır. Bu zayıflıklar sırayla, iyi yerler bulan parçacıklar için İ-DKA yerel aramasının çalıştırılması ve sonrasında o parçacıkların aramaya rasgele bir yerden devam ettirilmesi ile giderilmeye çalışılmıştır. Önerilen bu yeni PSO versiyonu, Güçlendirilmiş-PSO (G-PSO) olarak adlandırılmıştır. G-PSO üzerine, çözüme ihtiyaç duyacağı anda ayrık duruma getirilen ve kullanılan operatörler dahil tüm algoritmanın ayrık olarak ifade edildiği, iki yeni Ayrık G-PSO modeli geliştirilmiştir.Geliştirilen bu yeni modeller OP ve TOP için toplam 453 problemde test edilmiştir. Sonuçlar çözüm kalitesi ve performans açısından literatürdeki sonuçlarla karşılaştırıldığında, 12 problem için literatüre yeni sonuçlar kazandırılmış, diğer problemler için ise aynı yada rekabetçi sonuç üretildiği görülmüştür.
Özet (Çeviri)
The Vehicle Routing Problems with Profit are defined on a graph including control points and connections between them. Objective of the problem is to find paths, starting at an origin and ending at a destination that maximizes total profit without violating prescribed cost function (total distance, time and etc.). A path is determined for each vehicle defined by the problem. If there is only one vehicle in the problem, the problem is named as Orienteering Problem (OP), if there are more than one vehicles, it is named as Team Orienteering Problem (TOP).In this thesis, two new models based on Particle Swarm Optimization (PSO) and Variable Neighborhood Search (VNS) are proposed for solving OP and TOP. First model employs Reduced VNS (RVNS) which is a version of VNS. Providing a fast but sketchy exploration through the solution space is the strongest asset of RVNS. By using two nested RVNS, the proposed model accomplishes not only global search but also detailed local search at the same time.The second model is based on PSO. PSO is a population based metaheuristic that takes advantage of individual memory and social cooperation in a swarm. Straightforward application of PSO suffers from premature convergence and lack of intensification around the local best locations. To rectify these problems, a RVNS based local search around the best particle in the swarm is performed and a random moving strategy for this particle is employed. The proposed method is named as Strengthened PSO (StPSO). Partial and full discrete versions of this method are used for OP and TOP. The proposed models are tested aginst 453 OP and TOP benchmark problems in literature. It is observed that they generate competitive and promising results compared to the other similar methods in literature in terms of solutions quality and performance. Furthermore, improvements are achieved for 12 benchmark problems.
Benzer Tezler
- Tersine lojistik açısından katı atık yönetiminin incelenmesi ve kazanç ençoklanması üzerine bir uygulama
Investigation of solid waste management associated with reverse logistic and income maximization model application
ÖNER ÇETİN
Yüksek Lisans
Türkçe
2013
İşletmeİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. SITKI GÖZLÜ
- Evaluation des performances des projets de l'affaire électronique basé sur GRC en utilisant le tableau de bord équilibré et management de capital client
CRM bazlı e-iş proje performanslarının dengelenmiş skorkartı ve entelektüel müşteri sermayesi yönetimi ile değerlendirilmesi
BURHAN BURÇ KILIÇER
Yüksek Lisans
Fransızca
2004
Endüstri ve Endüstri MühendisliğiGalatasaray ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. ETHEM TOLGA
- Obligation convertibles en action: I'evaluation et I'application
Hisse senedi ile değiştirilebilir tahvillerin değerlemesi ve uygulanabilirlikleri
CEYDA HATIRNAZ
Yüksek Lisans
Fransızca
2002
Endüstri ve Endüstri MühendisliğiGalatasaray ÜniversitesiPROF. DR. ETHEM TOLGA
- Digital Background Calibration for Capacitor Mismatch and Gain Errors in Pipeline ADCs
Kapasitör Uyumsuzluğu ve Kazanç Hataları İçin Arka Plan Sayısal Kalibrasyonu
ENVER DERUN KARABEYOĞLU
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUFAN COŞKUN KARALAR
- Algı yönetimi ile destinasyon merkezlerinin rekabetçiliği arasındaki ilişkiyi belirlemeye yönelik bir araştırma
A research for identifiying the relationship between perception management and destination competitiveness
BAYRAM KIRMIZIGÜL