Bulanık C ve K-ortalamalarla başlangıç çözümü oluşturulmuş tavlama benzetimi hibrit algoritması ile kapasite kısıtlı araç rotalama probleminin çözümü
Solution of capacitated vehicle routing problem with simulated annealing hybrid algorithm with initial solution created with fuzzy C and K-means algorithm
- Tez No: 654582
- Danışmanlar: PROF. DR. İBRAHİM Çİ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: 2020
- Dil: Türkçe
- Üniversite: Sakarya Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 97
Özet
Bu çalışmada, popüler bir problem olan Araç Rotalama Problemi (ARP) üzerinde çalışılmıştır. Bu problemde müşteriler veya şehirler ziyaret edilmeli ve ürünler haritadaki bir noktadan başlayarak her müşteriye veya şehire taşınmalıdır. Amaç, taşıma sorununu çözerek ürünleri teslim edebilmektir. Bu problem az sayıda şehir veya müşteri ile çözülmesi kolay gibi görünse de öyle değildir. Çünkü çok fazla kısıtı sağlamak zorundadır. Dolayısıyla mevcut hesaplama gücü ile bu sorun çözülemez. Müşteri sayısı arttıkça yapılacak hesaplamalar da katlanarak artmaktadır, çünkü her müşteri için tüm kısıtlar sağlanmalı ve nispeten iyi bir çözüme kısa sürede ulaşılmalıdır. Bu çalışmadaki problemi çözmek için meta-sezgisel bir yöntem olan Tavlama Benzetimi (TB) kullanılmıştır. Genel olarak TB algoritması, metallerin tavlama işlemini taklit eden değişken sıcaklık parametresine göre tekrarlayan bir işlemdir. Bizim çalışmamız için bu yöntemin en büyük sorunu, algoritmayı başlatmak için kullanılan başlangıç çözümünü rassal olarak oluşturmasıdır. Bu sebepten dolayı optimum çözüme ulaşmak için kullanılan arama uzayı büyük olduğundan, çözüm süresi (veya iterasyon sayısı) artacaktır. Daha iyi bir başlangıç çözümüyle optimum çözüme ulaşmak daha kısa zaman alacaktır. Ulaşmak istediğimiz optimum çözüm minimum mesafe olduğundan, başlangıç çözümünü iyileştirmek için K-ortalamalar (KO) ve Bulanık c-ortalamalar (BCO) kullanılarak rotalar kümelenmiştir. Bulanık mantık gereği, her verinin 0-1 arasında birden fazla kümeye dahil olabilmesi durumu, algoritmanın her çözümünde başlangıç çözümünü değiştireceğinden dolayı optimum çözüme yaklaşma durumu olacaktır. Aynı veriler ve aynı parametreler kullanılarak rassal başlangıç çözümü kullanan TB ve BCO ile başlangıç çözümü iyileştirilmiş TB ile problem çözülmüştür. BCO başlangıç arama uzayını %57 oranında azaltmıştır. Dolayısıyla BCO aynı çözüm süresinde ve aynı iretasyon sayısında optimum çözüme daha yakın sonuçlar vermiştir. Çözüm sonuçları karşılaştırılmıştır.
Özet (Çeviri)
In this study, a popular problem, Vehicle Routing Problem (VRP), has been studied. In this problem, customers or cities should be visited and transported to the customer or city, starting from a point in the products. The aim is to deliver products by solving the transportation problem. While this problem seems easy to solve with a small number of cities or customers, it is not. Because it has to provide too many constraints. Therefore, this problem cannot be solved with the available computing power. As the number of customers increases, the calculations to be made increase exponentially, because all constraints must be met for each customer and a relatively good solution must be reached in a short time. Simulation Annealing (SA), a meta-heuristic method, was used to solve the problem in this study. In general, the SA algorithm is a repetitive process based on the variable temperature parameter that mimics the annealing process of metals. The biggest problem with this method for our study is that it randomly generates the initial solution used to start the algorithm. For this reason, because the search space used to reach the optimum solution is large, the solution time (or number of iterations) will increase. With a better initial solution, it will take less time to reach the optimum solution. Since the optimum solution we want to reach is the minimum distance, the routes have been clustered using K-means and Fuzzy c-mean to improve the initial solution. Due to fuzzy logic, each data can be included in more than one cluster between 0-1, since it will change the initial solution in every solution of the algorithm, there will be a case of approaching the optimum solution. Using the same data and the same parameters, the problem was solved with SA using a random starting solution and with an initial solution optimized SA with FCM. FCM reduced the initial search space by 57%. Therefore, FCM gave results closer to the optimum solution in the same solution time and the same number of rashes. Solution results are compared.
Benzer Tezler
- Görüntü sınıflandırma algoritmalarının başlangıç değerlerinin otomatik atanması
Automatic assignment of initial values of image classification algorithms
MERVE ARSLAN
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. RECEP DEMİRCİ
- Araç rotalama problemleri için kümeleme algoritmalari ile veri işleme
Data processing with clustering algorithms for vehicle routing problems
KEREM BÜYÜKÖZDEMİR
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ANIL BAŞ
DOÇ. DR. KAZIM YILDIZ
- Kapasite kısıtlı yer seçimi ve araç rotalama problemi ve bir metasezgisel çözüm önerisi
Capacitated location routing problem and a metaheuristic solution proposal
MUSTAFA SERDAR TOKSOY
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ PINAR YILDIZ KUMRU
DOÇ. DR. KASIM BAYNAL
- Renkli histogram kullanarak içerik tabanlı görüntü erişimi
Content based image retrieval by using color histogram
MAHMUT KILIÇASLAN
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. RECEP DEMİRCİ
- Gerçek zaman uygulamaları için görüntü bölütleme yöntemlerinin geliştirilmesi
Improvement of image segmentation methods for real time applications
YUNUS KOÇ
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER ÖLMEZ