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ı: Belirtilmemiş.
Ö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
- The capacitated vehicle routing problem with simultaneous pickup-delivery and time windows in the sustainable food supply chains
Sürdürülebilir gıda tedarik zincirlerinde zaman pencereli ve eşzamanlı toplama-teslimatlı kapasite kısıtlı bir araç rotalama problemi
MAHDI FARSHCHI
- 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
Orta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Yükleniyor...
- 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
- Algorithms for the vehicle routing problem with time windows and the location-routing problem
Zaman çerçeveli araç rotalama problemi ve yer bulma-rotalama problemi için algoritmalar
SUAT BOĞ
- Kapasite kısıtlı araç rotalama problemi ve çözüm yöntemleri
Capacitated vehicle routing problem and solution approaches
ZEYNEP BİRECİK
