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: Belirtilmemiş.
- 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ı: 135
Ö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
- Theoretical application analysis of a wind assisted propulsion system (WAPS) 'rotor sails' on the bulk carrier
Rüzgar destekli tahrik sistemlerinden (WAPS) 'rotor sail''in dökme yük gemisinde teorik uygulama analizi
ALTEMUR GÜLEÇ
Yüksek Lisans
İngilizce
2024
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
DOÇ. DR. TANZER SATIR
- Bir feribot için yakıt hücresi batarya hibrit sisteminin modellenmesi ve simulasyonu
Modeling and simulation of fuel cell battery hybrid system for a ferry
RUKİYE GÜLMEZ
Yüksek Lisans
Türkçe
2022
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ DENİZ
- Digital-twin flight modelling through machine learning for trajectory error estimation and recovery
Rota hesaplamalarında makine öğrenmesi tabanlı dijital ikiz uçuş modeli
MEVLÜT UZUN
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. GÖKHAN İNALHAN
DR. MUSTAFA UMUT DEMİREZEN
- 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
- 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
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. SITKI GÖZLÜ