Geri Dön

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

  1. Tez No: 890445
  2. Yazar: HÜSNA TOKEL
  3. Danışmanlar: PROF. ERTAN GÜNER
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: Türkçe
  9. Üniversite: Gazi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2022

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. BÜLENT ÇATAY

    DR. MİR EHSAN HESAM SADATİ

  2. 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

    Türkçe

    2022

    Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ EDA YÜCEL

    DOÇ. DR. ÇAĞRI KOÇ

  3. 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

    Türkçe

    2018

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SELİN SONER KARA

  4. 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

    Türkçe

    2017

    Endüstri ve Endüstri MühendisliğiPamukkale Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CAN BERK KALAYCI

  5. 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

    İngilizce

    2011

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. DR. CANAN SEPİL