Geri Dön

An adaptive large neighborhood search algorithm for the carrier-vehicle traveling salesman problem

Taşıyıcı-taşıt gezgin satıcı problemi için uyarlanabilir geniş komşuluk arama uygulaması

  1. Tez No: 570124
  2. Yazar: MÜGE YALÇINKAYA
  3. Danışmanlar: PROF. DR. EMRE ALPER YILDIRIM
  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: 2019
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 81

Özet

Birçok zorlu operasyon, farklı kabiliyetteki araçların birlikte çalışmasını ve koordinasyonunu gerektirir. Bu tarz çok araçlı sistemler, arama kurtarma ve keşif gibi çeşitli operasyonların etkisini arttırır, maliyetini azaltır ve güvenliğini sağlar. Taşıyıcı-Taşıt ikili araç sistemi, tamamlayıcı operasyonel kabiliyete sahip iki farklı aracın koordineli bir şekilde çalıştığı özel bir sistemdir. Hızlı kurtarma görevleri gibi zamanın çok kritik olduğu durumlarda aktif olarak kullanılmaktadır. Taşıyıcı'nın (ör. gemi) görevi, aracı uzun menzillere taşımaktır. Taşıt (ör. helikopter veya insansız hava aracı) ise sınırlı operasyonel kabiliyete sahip bir araçtır. Taşıyıcı'dan kalkış yapıp bir görevi gerçekleştirmek için belirli bir hedef noktasına gider ve enerji kaynağı tükenmeden Taşıyıcı ile bir noktada tekrar buluşur. Bu tezde, bu tarz operasyonlardaki uygulanabilirliğinden dolayı Taşıyıcı-Taşıt Gezgin Satıcı Problemi'ni (TTGSP) inceliyoruz. TTGSP, Taşıyıcı'nın ve Taşıt'ın bir görevi koordine bir şekilde en kısa zamanda bitirebilmesi için, her iki araç için de en makul rotaların bulunması ile ilgilenir. Bu problem için literatürde önerilen matematiksel modeller, en fazla 20 hedef noktası içeren örneklerde optimal çözüme ulaşabiliyor. Biz ise hedef noktasının daha fazla olduğu durumlarda optimale yakın sonuçlar bulabilmek için Uyarlanabilir Geniş Komşuluk Arama algoritmasını ve lokal arama sezgileri kullanarak bu algoritmanın genişletilmiş versiyonunu öneriyoruz. TTGSP'ye uyarlanmış farklı çıkarma ve yerleştirme operatörlerini inceliyoruz. Algoritmalarımızı farklı konfigürasyonlar için 10 ile 50 arasında hedef noktası içeren örneklerde test ediyoruz. 20'ye kadar hedef noktası içeren örnekler için optimale yakın sonuç elde ediyoruz. Daha fazla hedef noktası içeren örnekleri çözmede ise algoritmalarımızın literatürde önerilen diğer sezgisel metotlarla rekabet ettiğini görebiliyoruz.

Özet (Çeviri)

Several challenging operations require the cooperation and coordination of several vehicles with different capabilities. Such multi-vehicle systems may improve the effectiveness, cost, and safety of a wide range of operations such as search-and-rescue and surveillance. The Carrier-Vehicle system is a special case where two complementary vehicles with different operational capabilities work in coordination to perform time-critical tasks such as fast-rescue missions. The Carrier (e.g., a ship) is able to transport the Vehicle over long distances. The Vehicle (e.g., a helicopter or unmanned aerial vehicle), which has a limited operational capability, can take-off from the Carrier, travel to a point of interest to perform a task, and return to the Carrier without exhausting its capability. In this thesis, we study the Carrier-Vehicle Traveling Salesman Problem (CVTSP) due to its applicability in such operations. The CVTSP is concerned with finding the routes of the Carrier and the Vehicle in such a way that the Carrier and the Vehicle can complete a mission in a coordinated manner in minimum total time. The exact models proposed in the literature can solve the problem to optimality for instances containing at most 20 target points. In an attempt to find near-optimal solutions of larger instances, we propose an Adaptive Large Neighborhood Search algorithm and its extended version using local search heuristics. We incorporate different removal and insertion operators adapted to the CVTSP. We test our algorithms on data sets containing 10 to 50 target points with various settings. Up to 20 target points, we obtain near-optimal solutions. For larger instances, our results illustrate that our algorithms are competitive with the other heuristic methods proposed in the literature.

Benzer Tezler

  1. Time and reliability in vehicle routing problems

    Başlık çevirisi yok

    DUYGU TAŞ

    Doktora

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiTechnische Universiteit Eindhoven

    PROF. DR. TOM VAN WOENSEL

    DR. NICO DELLAERT

    DR. TON DE KOK

  2. Periodic vehicle routing problems with visual attractiveness and driver consistency

    Görsel elverişlilik ve sürücü tutarlılığı kısıtları ile periyodik araç rotalama problemi

    SAEEDEH AHMADI BASIR

    Doktora

    İngilizce

    İngilizce

    2024

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

    Mühendislik ve Doğa Bilimleri Ana Bilim Dalı

    ASSISTANT PROF. AMİNE GİZEM TİNİÇ

  3. An adaptive large neighborhood search algorithm for the heterogeneous pick-up and delivery vehicle routing problem with time windows

    Heterojen filolu dağıtım, toplama ve zaman pencereli araç rotalama problemi için adaptif geniş komşuluk arama algoritması

    GÖKBERK ÖZSAKALLI

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Endüstri ve Endüstri MühendisliğiYaşar Üniversitesi

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

    DOÇ. DR. DENİZ TÜRSEL ELİİYİ

  4. An adaptive large neighborhood search algorithm for selective and periodic inventory routing problem

    Seçici ve periyodik envanter rotalama problemi için uyarlanmış geniş komşu arama sezgisel algoritması

    ÖZGE TÜNCEL

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

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

    DOÇ. DR. FATMA SİBEL SALMAN

  5. An adaptive large neighbourhood search algorithm for type-II assembly line balancing problems

    Tip-II montaj hattı dengeleme problemleri için bir adaptif büyük komşuluk arama algoritması

    HÜSEYİN ALİ SÖNMEZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

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

    DOÇ. DR. ŞENER AKPINAR