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ı
- Tez No: 570124
- Danışmanlar: PROF. DR. EMRE ALPER YILDIRIM
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Time and reliability in vehicle routing problems
Başlık çevirisi yok
DUYGU TAŞ
Doktora
İngilizce
2013
Endüstri ve Endüstri MühendisliğiTechnische Universiteit EindhovenPROF. DR. TOM VAN WOENSEL
DR. NICO DELLAERT
DR. TON DE KOK
- 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
2024
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
ASSISTANT PROF. AMİNE GİZEM TİNİÇ
- 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
2016
Endüstri ve Endüstri MühendisliğiYaşar ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ TÜRSEL ELİİYİ
- 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
2013
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATMA SİBEL SALMAN
- 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
2021
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞENER AKPINAR