Kapasiteli araç rotalama problemi için değişken komşuluk iniş ve tavlama benzetimi hibrit sezgisel çözüm yaklaşımı
Variable neighborhood descent and simulated annealing hybrid heuristic solution approach for capacitated vehicle routing problem
- Tez No: 890445
- Danışmanlar: PROF. ERTAN GÜNER
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: Türkçe
- Üniversite: Gazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 93
Özet
Kapasiteli araç rotalama problemi (KARP), bir depodan, sabit kapasiteli araçlar ile farklı coğrafik bölgelerde bulunan müşterilerin önceden belirlenen taleplerinin karşılanması için en uygun rotalar belirlenerek hizmet verildiği, toplam tur uzunluğunun en küçüklenmesinin amaçlandığı araç rotalama problemidir. KARP için farklı meta-sezgisel algoritmaların performanslarının birleştirilerek daha güçlü bir algoritma önerilmesi fikrinden yola çıkılarak, değişken komşu iniş ve tavlama benzetimi algoritması birleştirilerek hibrit bir sezgisel algoritma önerilmiştir. İncelemelerimize göre KARP problemleri için bu iki algoritmanın hibrit bir çözüm yaklaşımı içerisinde birleştirilerek kullanıldığı bir çalışmaya rastlanmamıştır. Bu iki algoritmanın avantajları birleştirilerek, çözümde iyileşme olduğunda aramayı yoğunlaştıran, çözümde iyileşme olmadığında belli oranda kötü çözümleri kabul ederek yerel minimuma takılmayı önleyen ve yeni çözüm kabul edilemediği durumda farklı komşuluk yapıları ile arama yapılarak çözümü çeşitlendiren çözüm yaklaşımı önerilmiştir. 22, 23, 30, 33, 51 ve 76 müşteri boyutlu problem için E veri seti DKİ-TB hibrit çözüm yaklaşımı kullanılarak çözülmüştür. Başlangıç sıcaklığı, nihai sıcaklık, soğutma oranı ve iterasyon sayısı parametrelerinin çözüm değerlerine etkisi incelenmiştir. Her bir veri seti için DKİ-TB hibrit çözüm yaklaşımı 10 kez çalıştırılarak en iyi çözüm değeri dikkate alınmıştır. Bu çözüm değerleri, KARP çözmek için kullanılan CVRP-FA ve ISA-CO algoritmalarının çözüm değerleri ile karşılaştırılmıştır. DKİ-TB hibrit çözüm yaklaşımının, literatürde mevcut olan diğer algoritmalara göre daha iyi sonuç verdiği görülmüştür. Önerilen çözüm yaklaşımının performansını incelemek amacıyla Sakarya ilinde yer alan ekmek üretimi ve dağıtımı hizmeti veren bir fırın için gerçek dünya uygulaması yapılmıştır. Uygulamada 24 ve 30 müşteri boyutlu 2 homojen araç kapasiteli mesafe kısıtlı KARP yer almaktadır. Bu problem, Tlili, Faiz ve Krichen (2014) matematiksel modeli, homojen kapasiteli mesafe kısıtlı KARP' e uyarlanarak çözülmüştür. Çözüm sonuçları DKİ-TB hibrit çözüm yaklaşımı sonuçları ile karşılaştırıldığında, DKİ-TB'nin optimal çözüme yakın sonuçlar verdiği görülmüştür. 50 müşteri boyutludan büyük problemler matematiksel model kullanılarak çözülememektedir, bu durumda DKİ-TB hibrit çözüm yaklaşımı kullanılabilir.
Özet (Çeviri)
Capacity vehicle routing problem (KARP) is a vehicle routing problem in which the most appropriate routes are determined to meet the predetermined demands of customers in different geographical regions with fixed capacity vehicles from a warehouse, and the aim is to minimize the total tour length. Starting from the idea of proposing a stronger algorithm by combining the performances of different meta-heuristic algorithms for KARP, a hybrid heuristic algorithm has been proposed by combining variable neighbor descent and simulated annealing algorithm. According to our investigations, we have not found any study in which these two algorithms are combined in a hybrid solution approach for KARP problems. By combining the advantages of these two algorithms, a solution approach has been proposed that intensifies the search when there is an improvement in the solution, prevents getting stuck in a local minimum by accepting a certain amount of bad solutions when there is no improvement in the solution, and diversifies the solution by searching with different neighborhood structures when a new solution cannot be accepted. Data set E for 22, 23, 30, 33, 51 and 76 customer size problems was solved using the DKİ-TB hybrid solution approach. The effects of initial temperature, final temperature, cooling rate and number of iteration parameters on the solution values were examined. For each data set, the DKİ-TB hybrid solution approach was run 10 times and the best solution value was taken into account. These solution values were compared with the solution values of CVRP-FA and ISA-CO algorithms used to solve KARP. It has been observed that the DKİ-TB hybrid solution approach gives better results than other algorithms available in the literature. In order to examine the performance of the proposed solution approach, a real-world application was made for a bakery providing bread production and distribution services in Sakarya province. In practice, there is a distance-restricted KARP with a capacity of 2 homogeneous vehicles of 24 and 30 customer sizes. This problem was solved by adapting the mathematical model of Tlili, Faiz, and Krichen (2014) to the homogeneous capacity distance-constrained KARP. When the solution results were compared with the DKİ-TB hybrid solution approach results, it was seen that DKİ-TB gave results close to the optimal solution. Problems larger than 50 customer sizes cannot be solved using mathematical models, in which case the DKİ-TB hybrid solution approach can be used.
Benzer Tezler
- Last mile delivery routing problem using autonomous electric vehicles
Otonom elektrikli araçlar ile son kilometre dağıtım rotalaması problemi
NIMA MORADI
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. BÜLENT ÇATAY
DR. MİR EHSAN HESAM SADATİ
- Heterojen filolu elektrikli araçlarla zaman pencereli, senkronize iş içeren evde sağlık bakım hizmeti rotalama ve çizelgeleme probleminin optimizasyonu
Optimization of the electric home healthcare routing and scheduling problem with heterogeneous fleet, and synchronized jobs having time windows
EŞREF CEBECİ
Yüksek Lisans
Türkçe
2022
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ EDA YÜCEL
DOÇ. DR. ÇAĞRI KOÇ
- Talep belirsizliği altında kapasite kısıtlı yer seçimi ve araç rotalama problemi için hibrit sezgisel bir çözüm önerisi
A hybrid heuristic solution proposal for capacitated location routing problem under demand uncertainty
ENGİN PEKEL
Doktora
Türkçe
2018
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SELİN SONER KARA
- Eş zamanlı topla dağıt araç rotalama problemi için karınca koloni sistemi ile güçlendirilmiş değişken komşuluk arama algoritması
An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery
CAN KAYA
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiPamukkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CAN BERK KALAYCI
- Vehicle routing problem in cross docks with shift-based time constraints on products
Ürünler üzerindeki vardiya bazlı zaman kısıtları ile çapraz sevkiyat depolarında araç rotalama problemi
MENEKŞE KOÇAK
Yüksek Lisans
İngilizce
2011
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. CANAN SEPİL