Geri Dön

Genetic algorithm applications for the vehicle routing problem with roaming delivery locations

Hareketli teslimat noktalı araç rotalama problemleri için geliştirilmiş genetik algoritmalar

  1. Tez No: 685317
  2. Yazar: SERKAN TURHAN
  3. Danışmanlar: PROF. DR. BAHAR YETİŞ
  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: 2021
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 84

Özet

E-ticaret endüstrisindeki son yenilikler ile müşterilerin siparişlerinin arabalarının bagajına teslim edilebildiği yeni bir teslimat seçeneği geliştirdi. Sıkça kullanılan eve yapılan teslimatlar ile karşılaştırıldığında, bu seçenek sadece kat edilen toplam mesafeyi azaltmakla kalmıyor ve başarısız teslimatları azaltarak müşteri memnuniyetini de arttırıyor. Bu seçenek ile ortaya çıkan probleme hareketli teslimat noktalı araç rotalama problemi denir. Bu tez, problem için yeni ve zaman açısından verimli bir çözüm oluşturma stratejisi önermektedir. Bu strateji problem değişkenlerinden bağımsız şekilde problem için her uygun çözümü temsil edebilir. Bu stratejiyi temel alan, polinom zamanında en iyi çözümlere yakın çözümler bulmak ve geliştirmek için yeni bir genetik algoritma önerilmiştir. Ayrıca, belirli bir dizi problem örneği için, genetik algoritmanın değişkenlerini iyileştirmek için farklı, yeni bir ince ayar algoritması önerilmiştir. Önerilen genetik algoritmanın en önemli özelliği, çözüm oluşturma zamanının problem boyutu ile doğrusal ölçekte artması ve literatürde mevcut olan en büyük problem örneği için milisaniyeler içinde bir çözüm oluşturabilmesidir. Paralel hesaplama hem ince ayar algoritmasında hem de genetik algoritmalarda uygulanabilir, bu da zamanın daha verimli kullanılmasını ve daha sürede daha iyi sonuçlar alınmasını sağlar. 5 dakikalık işlem süresi içinde, ince ayarlı genetik algoritma, 19 örneğin 8'inde en iyi çözümleri buldu, ayrıca 60 örnekten 12'sinde önceki çözüm metodolojilerinden daha iyi çözümler bulabildi. Önerilen genetik algoritmanın sonuçları ile çözücü (CPLEX) tarafından bulunan en iyi çözüm arasındaki farklar, küçük-orta ve büyük örneklerde sırasıyla (%0,0, %26,2) ve (-%6,0, %16,3) arasındadır.

Özet (Çeviri)

The recent innovations in the e-commerce industry developed a new delivery option where the orders of the customers can be delivered to the trunks of their cars. Compared to the conventional home-delivery, this option is not only able to decrease the total distance traveled but also increase the customer satisfaction by decreasing the number of failed deliveries. The problem introduced by this option is called the vehicle routing problem with roaming delivery locations. This thesis proposes a new, time-efficient solution construction strategy for the problem. The construction strategy is able to represent any feasible solution for the problem and has a complexity linearly increasing with the number of delivery nodes in the problem. Based on the constructor, a new genetic algorithm to find and improve solutions to near-optimal within polynomial time is proposed. Furthermore, a separate, new fine-tuning algorithm to improve the parameters of the genetic algorithm for a given set of problem instances is proposed. The most notable feature of the proposed genetic algorithm is the time-efficiency as it is able to construct a solution within milliseconds for the largest problem instance available in the literature and the computation time scales with the problem size linearly. Parallel computing can be implemented in both the fine-tuning and the genetic algorithm, which allows better results in a shorter processing time. Within 5 minutes of computation time, the fine-tuned genetic algorithm found optimal solutions in 8 out of 19 instances with known optimal solutions, moreover, it was able to find solutions better than the previous solution methodologies in 12 out of 60 instances used in our experiments. Gaps between the results of the proposed genetic algorithm and the best solution found by a commercial solver (CPLEX) are between (0.0%, 26.2%) and (-6.0%, 16.3%) in small-medium and large instances respectively.

Benzer Tezler

  1. A genetic algorithm for the location-routing problem with time windows

    Zaman kısıtlı yerleşim-rotalama problemi için bir genetik algoritma

    HANDE ÖZGÖNENÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

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

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

    Y.DOÇ.DR. SEDEF MERAL

  2. Heterojen filo üzerinde araç rotalama probleminin melez yaklaşımla uyum temalı çözümü

    Compatibility themed solution of the vehicle routing problem on the heterogeneous fleet

    NİSANUR BULUT

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBursa Uludağ Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ METİN BİLGİN

  3. Genetik algoritma ile araç rotalama problemlerinin çözümü için görsel rotalama yazılımı geliştirme

    Development a visual routing software for the solution of vehicle routing problems with genetic algorithm

    NOYAN SEBLA GÜNAY

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesi

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

    YRD. DOÇ. DR. MURAT AKAD

  4. Zeki yöntemler kullanılarak insansız hava aracı için dinamik ortamda rota planlaması

    Route planning for unmanned aerial vehicles in dynamic environment using intelligence methods

    BURAK GÖNÜLTAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Elektrik ve Elektronik MühendisliğiAnkara Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÖKKEŞ TOLGA ALTINÖZ

  5. Dinamik ortamlar için yeni bir gerçek zamanlı evrimsel seyrüsefer planlama ve güdümleme sistemi

    A new real time evolutionary navigation planning and guidance system for dynamic environments

    FERHAT UÇAN

    Doktora

    Türkçe

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. DENİZ TURGAY ALTILAR