Capacitated vehicle routing problem with time windows
Zaman kısıtlı araç rotalama problemi
- Tez No: 185298
- Danışmanlar: YRD. DOÇ. DR. TONGUÇ ÜNLÜYURT
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2003
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Mühendislik ve Doğa Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 102
Özet
ÖZETZaman Kısıtlı Araç Rotalama Problemi, Araç Rotalama Problemi'nin biruzantısıdır. Problemde amaç, tüm kısıtları sağlayan optimal rotalar oluşturmaktır.Bu çalışmada Zaman Kısıtlı Araç Rotalama Problemi için bir doğrusal tamsayılıprogramlama modeli ve problemin çözümü için hibrid sezgisel yaklaşımlarönerilmiştir. Modeldeki amaç fonksiyonu, araçlar tarafından kat edilen toplammesafenin en küçüklenmesidir. Tüm araçlar aynı özelliklere sahiptir ve araçlarınkapasiteleri göz önünde bulundurulmaktadır.Önerilen sezgisel algoritmalar iki bölümden oluşmaktadır. Birinci bölüm dahasonra geliştirilebilmek üzere bir başlangıç çözümü oluşturmaya yöneliktir. Başlangıççözümü algoritmasının paralel ve sıralı versiyonları önerilmiştir. Her iki yaklaşım damüşterileri rotalara atarken onları gruplandırma esasına dayanmaktadır.İkinci kısım ise üç farklı prosedürü içeren bir çözüm geliştirme algoritmasıdır. Buüç prosedür rotalar arası değişim, rotalar arası taşıma ve rota içi değişim'dir. Önerilensezgisel algoritmalarda bu prosedürler iç içe, birbirine bağlanmış şekilde kullanılmıştır.Bu üç prosedürü farklı şekillerde birbirine bağlayarak kullanan iki farklı yerel aramaalgoritması geliştirilmiştir.Ayrıca, çözüm geliştirme algoritmaları dağıtma adlı yeniden başlatmaalgoritmasıyla desteklenmiştir. Çalışmada iki farklı dağıtma metodu önerilmiştir.Bunlardan biri çözümü maliyet değişimini göz önünde bulundurmadan bozmakta, diğeriise daha kötü çözümlere sabit ve belirli bir olasılıkla gitmektedir.Çalışmada önerilen hibrid sezgisel algoritmalar, tüm başlangıç çözümü, çözümgeliştirme ve dağıtma algoritmalarının farklı kombinasyonlarıdır.Algoritmalar, Solomon'un 1987 yılında oluşturduğu ve araç rotalama içingeliştirilen algoritmaların karşılaştırılmasında çok yaygın olarak kullanılan 56 problemile test edilmiştir. Hibrid algoritmalar hem bilinen bazı sezgisel-ötesi yaklaşımlarla, hemde problemlerin literatürdeki bilinen en iyi çözümleri ile karşılaştırıldığında, genelanlamda iyi sonuçlar vermektedir.
Özet (Çeviri)
ABSTRACTVehicle Routing Problem with Time Windows (VRPTW) is an extension of theCapacitated Vehicle Routing Problem. The objective is to design optimal routes thatsatisfy all of the constraints.In this study, a linear IP model and hybrid heuristics for the VRPTW areproposed. The objective function considered in the model is the total distance traveledby all vehicles. Vehicles are identical, capacities of the vehicles are finite and the timewindow constraints are assumed to be strict.The proposed hybrid heuristics are combined by two parts. The first part, whichhas both parallel and sequential versions, finds an initial solution. Both parallel andsequential initial solution algorithms are based on the idea of clustering the customerswhile doing the insertion. Second part is an improvement heuristic, which is acombination of three procedures: Inter-route exchanges, inter-route moves and intra-route exchanges. In the proposed heuristics, these operators are used nested with eachother. There are two improvement heuristics proposed that use these operators indifferent ways. The improvement algorithms are supported with a restart mechanismcalled diversification in order to escape the local optima and widen the search space. Inthis study, two diversification methods are proposed.The hybrid algorithms in this study are the combinations of the initial solution,improvement and diversification methods proposed.The algorithms have been tested on the 56 benchmark problem instances ofSolomon (1987), which were used widely in the literature. The hybrid algorithms areproven to give better results when compared to not only some known metaheuristics,but also to the best known results in the literature.
Benzer Tezler
- An algorithm for the capacitated vehicle routing problem with time windows
Teslim zaman aralığı ve araç kapasitesi kısıtlı araç rotalama problemi için bir algoritma
OSMAN PEHLİVANOĞLU
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEDEF MERAL
- Zaman bağımlı zaman pencereli heterojen filolu çok ürünlü kapasiteli bölmeli araç rotalama problemi ve çözüm önerisi
Time dependent heterogeneous fleet multi-product partial capacitated vehicle routing problem with time windows and solution approach
ERTUĞRUL AYYILDIZ
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALEV TAŞKIN GÜMÜŞ
- Kapasite kısıtlı araç rotalama problemi ve çözüm yöntemleri
Capacitated vehicle routing problem and solution approaches
ZEYNEP BİRECİK
Doktora
Türkçe
2023
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. DOĞAN ÖZGEN
- An integration of container loading and vehicle routing problems
Konteyner yükleme ve araç rotalama problemlerinin bir entegrasyonu
ECEM BARIŞ
Yüksek Lisans
İngilizce
2016
Endüstri ve Endüstri Mühendisliğiİzmir Ekonomi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ZEYNEP SARGUT
- Optimizing ready-mixed concrete transportation by a truck mixer routing model for concrete plants
Beton santralleri için bir transmikser rotalama modeli ile hazır beton taşımacılığının optimize edilmesi
OZAN AYKUT DÖNMEZ
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri MühendisliğiYaşar Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ERDİNÇ ÖNER